akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>                 // [PRIMES]               1777 ~2^10.80
using namespace std;                     //                       10333 ~2^13.33
using ll = long long;                    // seq 1 128 | factor   100333 ~2^16.61
using vl = vector<ll>;                   //   | grep -v ' .* '  1300111 ~2^20.31
using vvl = vector<vl>;                  //                    10300777 ~2^23.30
using pll = pair<ll,ll>;                 //                   100400999 ~2^26.58
using vb = vector<bool>;                 //                  1300400999 ~2^30.28
const ll oo = 0x3f3f3f3f3f3f3f3fLL;      //                 10200500333 ~2^33.25
const double eps = 1e-9;                 //                100200400777 ~2^36.54
#define sz(c) ll((c).size())             //               1200300700111 ~2^40.13
#define all(c) begin(c),end(c)           //              10200300500777 ~2^43.21
#define mp make_pair                     //             100200300400777 ~2^46.51
#define mt make_tuple                    //            1200300400600999 ~2^50.09
#define pb push_back                     //           10200300400600111 ~2^53.18
#define eb emplace_back                  //          100200300400600333 ~2^56.48
#define xx first                         //         1200300400500800999 ~2^60.06
#define yy second                       
#define has(c,i) ((c).find(i) != end(c))
#define FOR(i,a,b) for (ll i=(a); i<(ll)(b); i++)       
#define FORD(i,a,b) for (ll i=ll(b)-1; i>=(a); i--)
/// ({ ... }) avoids some problems: http://kernelnewbies.org/FAQ/DoWhile0
/// In non-contest code it is probably better to use: do { ... } while(0)
#define TR(X) ({ if(1) cerr << "DBGDO: " << (#X) << " = " << (X) << endl; })
void update(ll node, ll count, ll prev, vl &counter, vvl &tree){
    counter[node] += count;
    ll sum = counter[node];

    for(auto nod : tree[node]){
        if(prev != nod){
            update(nod, sum, node, counter, tree);
        }
    }
}

int main() {
    ll n;
    ll q;
    cin >> n;
    cin >> q;

    vl counter(n,0);
    vvl tree(n);

    FOR(i,0,n-1){
        ll a;
        ll b;
        cin >> a;
        cin >> b;
        tree[b-1].pb(a-1);
        tree[a-1].pb(b-1);
    }



    FOR(i,0,q){
        ll r;
        ll x;
        cin >> r;
        r--;
        cin >> x;
        counter[r] += x;

    }

    update(0,0,-1,counter,tree);

    for(auto nod : counter){
        cout << nod << " ";
    }
    cout << endl;
}


Measured memory_bytes: 30464
using System;
using System.Linq;

namespace C3
{
    class Program
    {
        static void Main(string[] args)
        {
            long n = long.Parse(Console.ReadLine());
            n -= 1;
            string answerRev = "";
            for(long l = 1; l < 15;l++)
            {
                if(n >= Math.Pow(26,l))
                {
                    n -= (long)Math.Pow(26,l);
                    continue;
                }
                answerRev = "";
                for(long i = 0;i < l; i++)
                {
                    long d = n % 26;
                    answerRev += (char)(d + 'a');
                    n /= 26;
                }
                break;
            }
            string answer = new string(answerRev.Reverse().ToArray());
            Console.WriteLine(answer);
        }
    }
}

Measured memory_bytes: 28560
n,S = map(int,input().split())
s=S // 1000
a= int(s//10)
m=0

for x in range(a+1):
    b = int((s-10*x)//5)
    for y in range(b+1):
        if 10*x + 5*y + (n-x-y) == s:   

            print(x,y,n-x-y)
            m=1
            break
    if m==1:
        break
        

if m==0:
    print(-1,-1,-1)    

Measured memory_bytes: 40812
#include "bits/stdc++.h"
#include<unordered_map>
#include<unordered_set>
#pragma warning(disable:4996)
using namespace std;

void get_cycle(vector<int>&ans,const vector<vector<int>>&edges, vector<int>&used,const int color,const int now) {
	if (used[now]==color) {
		ans = vector<int>(1, now);
		return;
	}
	else if(used[now]==-1){
		used[now] = color;
		for (auto e : edges[now]) {
			get_cycle(ans, edges, used, color, e);
			if (!ans.empty()) {
				ans.emplace_back(now);
				return;
			}
		}
	}
}

vector<int> get_num(const int now,const vector<vector<int>>&edges,const int not_go,bool flag) {
	if (edges[now].empty()) {
		return vector<int>(1,0);
	}
	else {
		set<int>tos;
		for (auto e : edges[now]) {
			if (e == not_go) {
				continue;
			}
			else {
				tos.emplace(get_num(e, edges, not_go,false)[0]);
			}
		}
		if (flag) {
			vector<int>kouhos;
			for (int i = 0; i < 1000000; ++i) {
				if (tos.find(i) == tos.end()) {
					kouhos.push_back(i);
					if (kouhos.size() == 2)return kouhos;
				}
			}
		}
		else {
			for (int i = 0; i < 1000000; ++i) {
				if (tos.find(i) == tos.end()) {
					return vector<int>(1,i);
				}
			}
		}
	}
}

bool check(vector<vector<int>>&kouhos) {
	bool ok = false;
	for (int l = 0; l < 2; ++l) {
		int now = kouhos[0][l];
		for (int i = 1; i < kouhos.size(); ++i) {
			if (kouhos[i][0] == now) {
				now = kouhos[i][1];
			}
			else {
				now = kouhos[i][0];
			}
		}
		if (l == 0) {
			if (now != kouhos[0][0])ok = true;
		}
		else {
			if (now == kouhos[0][0])ok = true;
		}
	}
	return ok;
}

int main() {
	int N; cin >> N;
	vector<vector<int>>edges(N);
	for (int i = 0; i < N; ++i) {
		int a; cin >> a;
		edges[a - 1].push_back(i);
	}
	vector<int>used(N, -1);
	vector<int>cycle_ids;
	for (int i = 0; i < N; ++i) {
		get_cycle(cycle_ids, edges, used, i, i);
		if (!cycle_ids.empty())break;
	}
	cycle_ids.erase(cycle_ids.begin());
	reverse(cycle_ids.begin(), cycle_ids.end());
	vector<vector<int>>kouhos(cycle_ids.size());
	for (int i = 0; i < cycle_ids.size(); ++i) {

		auto cid = cycle_ids[i];
		kouhos[i] = get_num(cycle_ids[i], edges, cycle_ids[(i + 1) % cycle_ids.size()], true);
	}
	bool ok = check(kouhos);
	if (!ok)cout << "IM";
	cout << "POSSIBLE" << endl;
	return 0;
}

Measured memory_bytes: 33652
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
const ll MOD = 998244353;
//const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<58);

template<class T> bool chmin(T &a, const T &b){
    if(a > b) {a = b; return true;}
    else return false;
}
template<class T> bool chmax(T &a, const T &b){
    if(a < b) {a = b; return true;}
    else return false;
}

ll calc(mat &s, vec &c, vec &ans){
    ll res = 0;
    vec last(26, 0);
    rep(day, N){
        last[ans[day]] = day + 1;
        rep(i, 26){
            if(i == ans[day]){
                res += s[day][i];
            }else{
                res -= c[i] * (day + 1 - last[i]);
            }
        }
    }
    return res;
}

int main() {
    cin>>N;
    vec c(26), last(26, 0), ans(N);
    mat s(N, vec(26)), ans_another(26, vec(1, 0));
    rep(i,26) cin>>c[i];
    rep(i,N) rep(j, 26) cin>>s[i][j];
    ll score = 0;
    rep(day, N){
        vec temp(26, 0);
        rep(i, 26) temp[i] += s[day][i];
        rep(i, 26) temp[i] += c[i] * (day + 1 - last[i]);
        auto ite = max_element(ALL(temp));
        ans[day] = ite - temp.begin();
        ans_another[ans[day]].push_back(day + 1);
        last[ite - temp.begin()] = day + 1;
        rep(i, 26){
            if(i == ans[day]){
                score += s[day][i];
            }else{
                score -= c[i] * (day + 1 - last[i]);
            }
        }
    }
    rep(i,26) ans_another[i].push_back(N + 1);

    mat minus(N + 1, vec(26, 0));
    priority_queue<P> pque;
    rep(i, 26){
        vec &table = ans_another[i];
        int id = 0;
        reps(day, 1, N){
            if(table[id + 1] == day){
                ++id;
            }else{
                ll weight = s[day - 1][i], len = table[id + 1] - table[id] - 1;
                ll wh = day - table[id];
                weight += c[i] * ((len * (len + 1) / 2) - (wh * (wh - 1) / 2 + (len - wh) * (len - wh + 1) / 2));
                pque.emplace(weight, day * 26 + i);
            }
        }
    }
    rep(check, 30000){
        P p = pque.top();
        pque.pop();
        ll day = p.se / 26, i = p.se % 26;
        --day;
        ll old = ans[day];
        ans[day] = i;
        if(!chmax(score, calc(s, c, ans))){
            ans[day] = old;
        }
    }

    rep(i,N) cout<<ans[i] + 1<<'\n';
}


Measured memory_bytes: 3952
import sys

I = list(map(int, input().split()))
A_i = list(map(int,input().split()))
A_i = [i for i in A_i if 1 <= i and i <= 10**4]
H = I[0]
N = I[1]

if not 1 <= H or not H <= 10**9 or not 1 <= N or not N <= 10**5:
    print("error")
    sys.exit()

A_i = sorted(A_i, reverse=True) # 降順ソート
A_i = A_i[:N]
A = sum(A_i)

if H <= A:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 13964
#include <bits/stdc++.h>
using namespace std;

int main() {
  int n;
  cin >> n;
  bool four = false;
  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    if (s == "Y")
      four = true;
  }
  cout << (four ? "Four" : "Three") << endl;
}

Measured memory_bytes: 256
import math
N = int(input())
M = list(map(int, input().split()))
alice = 0
bob = 0
M.sort()
for i in range(math.ceil(N/2)): 
    alice += M[2*i]
    if N % 2 != 0 and i == int(N/2):
        break
    bob += M[2*i+1]
print(abs(alice - bob))

Measured memory_bytes: 3060
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<algorithm>

using namespace std;

#define LL long long
string s;


int main() {
	cin >> s;
	int x=0, o=0;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'o')o++;
		else x++;
	}
	if (o + (15 - (int)s.size()) >= 8)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())

activity = [list(map(int, input().split())) for _ in range(N)]

dp = [[0] * 3 for _ in range(N)]

dp[0][0] = activity[0][0]
dp[0][1] = activity[0][1]
dp[0][2] = activity[0][2]

for i in range(1, N):
    dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + activity[i][0]
    dp[i][1] = max(dp[i-1][2], dp[i-1][0]) + activity[i][1]
    dp[i][2] = max(dp[i-1][0], dp[i-1][1]) + activity[i][2]

print(max(dp[N-1]))


Measured memory_bytes: 47280
import math
import copy 
S = list(input())
K = int(input())
S1 = copy.copy(S)

x = S[0]
c1 = 0
c2 = 0
for i in range(len(S)-1):
    if x == S[i+1]:
        c1 += 1
    else:
        c2 += math.ceil(c1/2)
        c1 = 0
    x = S[i+1]
c2 += math.ceil(c1/2)
a = c2

S.extend(S1)
x = S[0]
c1 = 0
c2 = 0
for i in range(len(S)-1):
    if x == S[i+1]:
        c1 += 1
    else:
        c2 += math.ceil(c1/2)
        c1 = 0
    x = S[i+1]

c2 += math.ceil(c1/2)
b = c2

S.extend(S1)

x = S[0]
c1 = 0
c2 = 0
for i in range(len(S)-1):
    if x == S[i+1]:
        c1 += 1
    else:
        c2 += math.ceil(c1/2)
        c1 = 0
    x = S[i+1]
c2 += math.ceil(c1/2)
c = c2

if K == 1:
    print(a)
elif b-a ==  c-b:
    print(a+(K-1)*(b-a))
else:
    print((K//2)*b+(K%2)*(c-b))

Measured memory_bytes: 3444
import java.util.*;
public class Main{
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int r = sc.nextInt();
    if(r<1200){
      System.out.println("ABC");
    }else if(1200<=r && r<2800){
      System.out.println("ARC");
    }else if(r>=2800){
      System.out.println("AGC");
    }
  }
}


Measured memory_bytes: 21716
#include<bits/stdc++.h>

#define MAX 100

using namespace std;

int main(){
    string s;
    string t;
    string test;

    cin >> s >> t;
    test = t + t;

/*
    cout << s << endl;
    cout << t << endl;
    cout << test << endl;
*/
    if(test.find(s) != -1){
        cout << "Yes";
    }else{
        cout << "No";
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <unordered_map>
#include <unordered_set>
 
int main(int argc, char const *argv[])
{
    int N;
    std::cin >> N;
    std::vector<int> A(N);
    int i = 0;
    int t  = N;
    while (t-- > 0) {
        std::cin >> A[i++];
    }
 
    std::vector<long long int> dp(N + 1, 0);
    std::vector<int> color (3, 0);
 
    dp[0] = 1;
    color[0] = 0;
    for (int i = 1; i <= N; i++) {
        int mm = 0;
        long long int c = 0;
        for (int j = 0; j < 3; j++) {
            if (A[i - 1] == color[j]) {
                mm = j;
                c++;
            }
        }
        if (c == 0) {
            std::cout << 0 << std::endl;
            return 0;
        }
        color[mm]++;
        dp[i] = (dp[i - 1] * c) % 1000000007;
    }
    std::cout << dp[N] << std::endl;
    return 0;
}

Measured memory_bytes: 1408
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		String str = sc.next();
		int count = 0;

		for (int i = 0; i < str.length(); i++) {
			count += str.charAt(i) == '1' ? 1 : 0;
		}

		System.out.println(count);
	}
}

Measured memory_bytes: 22868
import java.util.*;

public class Main {
	private static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		String o = sc.next();
		String e = sc.next();
		int ol = o.length();
		int el = e.length();
		StringBuilder sb = new StringBuilder();
		for (int i = 0;i < ol;i++) {
			sb.append(o.substring(i,i+1));
			if (i<el) sb.append(e.substring(i,i+1));
		}
		System.out.println(sb.toString());
	}
}


Measured memory_bytes: 23636
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> v;
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		cin >>a;
		v.push_back(a);
	}
	sort(v.begin(),v.end());
	long ans = 0;
//	cout << " "<< v[0] << " " << v[1] << " "<< v[2] << " " << v[3] <<endl;
	v.push_back(10000000);
	for (int i = 0; i < n-2; i++) {
		for (int j = i+1; j < n-1; j++) {
			int L = j;
			int  R=n;
			while ((R-L)>1) {
				if (v[(L + R) / 2] < (v[i] + v[j])) {//  mid OK  last  R =L+1
					L = (L + R) / 2;
				}
				else R= (L + R) / 2;
			}
			ans += (L - j);

		}
	}

	cout << ans << endl;;
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
	public static void main(String args[]){
		Scanner sca=new Scanner(System.in);
		int num=sca.nextInt();
		int arr[]=new int[num];
		
		for(int i=0;i<num;i++){
			arr[i]=sca.nextInt();
		}
		
		for(int i=0;i<num;i++){
			System.out.print("node "+(i+1)+": key = "+arr[i]+", ");
			if((i-1)/2>=0 && i!=0){
				System.out.print("parent key = "+arr[(i-1)/2]+", ");
			}
			if(i*2+1<num){
				System.out.print("left key = "+arr[i*2+1]+", ");
			}
			if(i*2+2<num){
				System.out.print("right key = "+arr[i*2+2]+", ");
			}
			System.out.println();
		}
		
		
	}	
}



Measured memory_bytes: 27376
import Control.Applicative

func x y z k =
  if x>k || y>k || z>k || x<0 || y<0 || z<0 then
    0
  else
    1


main = do
  (k:s:_) <- (map (read::String->Int)) . words <$> getLine

  print $ sum $ map (\x ->
                 sum $ map (\y ->
                        let
                          z = s-x-y
                        in
                          func x y z k
                        )
                 [0..k])
    [0..k]


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void printmatrix(vector<vector<T> > ar){
    for (int i = 0; i < (int)ar.size(); i++) {
        for (int j = 0; j < (int)ar.size(); j++) {
            cout << ar[i][j];
        }
        cout << endl;
    }
}

template<typename T>
void printvector(vector<T> vec){
    for (int i = 0; i < (int)vec.size(); i++) {
        cout << vec[i] << endl;
    }
}


int main(int argc, char const* argv[])
{
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    int total=0;
    while ((x > 0) || (y > 0)) {
        if ( ( (a >= 2*c) && (x > 0) ) || ( (b >= 2*c) && (y > 0) ) || ( (a+b >= 2*c) && (x > 0) && (y > 0) )) {
            total += 2*c;
            x -= 1;
            y -= 1;
        }else if (x > 0) {
            total += a;
            x--;
        }else if (y > 0){
            total += b;
            y--;
        }
    }

    cout << total << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main()
{
	int a,b,c;
	cin>>a>>b>>c;

	int count=0;

	while(b>=a)
	{
		b = b-a;
		count+=1;
		if(count==c)
			break;
	}

	cout<<count<<endl;
	return 0;
}


Measured memory_bytes: 256
import itertools
n = int(input())
aa1 = list(map(int, input().split()))
aa2 = list(map(int, input().split()))
aa2.reverse()
aa1 = list(itertools.accumulate(aa1))
aa2 = list(itertools.accumulate(aa2))
aa2.reverse()
ans = 0
for i in range(n):
    tmp = aa1[i] + aa2[i]
    ans = max(ans, tmp)
print(ans)

Measured memory_bytes: 3064
from fractions import gcd
from functools import reduce

# 最小公倍数
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
  
N = int(input())
T = [int(input()) for _ in range(N)]

ans = lcm_list(T)
print(ans)

Measured memory_bytes: 5244
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)n; i++)
using ll = long long;

int main(){
  int a, b;
  cin >> a >> b;
  string s = "", t = "";
  rep(i,b) s += '0' + a;
  rep(i,a) t += '0' + b;
  if(s < t) cout << s << endl;
  else cout << t << endl; 
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ll long long
using namespace std;

ll rec(int n, ll x) {
  if (n == 0) return 1;
  ll len=(1LL<<(n+1))-3;
  ll num=(1LL<<n)-1;
  if (x==1) return 0;
  else if (x<=len+1) return rec(n-1, x-1);
  else if (x==len+2) return num+1;
  else if (x<=(len+1)*2) return num+1+rec(n-1, x-len-2);
  else return num*2+1;
}

int main() {
  int N; ll X;
  cin>>N>>X;
  cout<<rec(N, X)<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  bool ok = false;
  CIN(N);
  REP(i, 100/4 + 1) {
    REP(j, 100/7 + 1) {
      if (i * 4 + j * 7 == N) ok = true;
    }
  }

  OK(ok);
  return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;

int h,w;
char plot[1000+5][1000+5];
int dp[1000+5][1000+5];

void solve(){
	memset(dp,0,sizeof(dp));
	dp[1][1] = 1;
	for(int i = 2;i<=w;i++)
		if(plot[1][i] != '#')
			dp[1][i] = dp[1][i-1];

	for(int i = 2;i<=h;i++)
		if(plot[i][1] != '#')
			dp[i][1] = dp[i-1][1];


	for(int i = 2;i<=h;i++){
		for(int j = 2;j<=w;j++){
			if(plot[i-1][j] != '#'){
				dp[i][j] = (dp[i][j]%MOD + dp[i-1][j]%MOD)%MOD;
			}
			if(plot[i][j-1] != '#'){
				dp[i][j] = (dp[i][j]%MOD + dp[i][j-1]%MOD)%MOD;
			}	
		}
	}

}

int main(){
	cin>>h>>w;
	for(int i= 1;i<=h;i++)
		for(int j = 1;j<=w;j++)
			cin>>plot[i][j];


	solve();
	cout<<dp[h][w]<<endl;
}

Measured memory_bytes: 5120
n = gets.chomp.to_i

max_i = 0
max_i_score = nil
n.times do
  i, score = gets.chomp.split.map(&:to_i)
  if i > max_i
    max_i = i
    max_i_score = score
  end
end

puts(max_i + max_i_score)

Measured memory_bytes: 1788
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };
const int c_div = 1000000007; //10^9 + 7


int ans[100];

int main() {

	int A, B, C;
	scanf("%d%d%d", &A, &B, &C);

	for (int i = A; i < 100000000; i += A) {
		if (i%B == C) {
			printf("YES");
			return 0;
		}
	}
	printf("NO");






}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int N;
int dp[18][1<<18];
pii A[20];

int main() {
	cin >> N;
	for (int i=0; i<N; i++) cin >> A[i].va;
	for (int i=0; i<N; i++) cin >> A[i].vb;

	for (int i=0; i<(1<<N); i++) {
		for (int j=0; j<N; j++) dp[j][i] = 2e9;
	}
	for (int i=0; i<N; i++) dp[i][1<<i] = 0;

	for (int i=0; i<(1<<N); i++) {
		for (int j=0; j<N; j++) {
			if (!(i>>j&1)) continue;
			int prv = i ^ (1<<j);
			int idx = 0, cost = 0, num;
			for (int k=0; k<N; k++) {
				idx += (prv>>k&1);
				if (k>j) cost += (prv>>k&1);
			}
			if (idx%2 == j%2) num = A[j].va;
			else num = A[j].vb;

			for (int k=0; k<N; k++) {
				if (!(prv>>k&1)) continue;
				int t;
				if (k%2 == idx%2) t = A[k].vb;
				else t = A[k].va;
				if (t > num) continue;
				dp[j][i] = min(dp[j][i], dp[k][prv]+cost);
			}
		}
	}

	int ans = 2e9;
	for (int i=0; i<N; i++)
		ans = min(ans, dp[i][(1<<N)-1]);
	cout << (ans > 1e9 ? -1 : ans);
}

Measured memory_bytes: 18688
let _ =
  let round x =
    let eps = 0.0005 in
    let ux = if x > 0.0 then x else (-1.0) *. x in
    if ux < eps then 0.0 else x in
  try
    while true do
      let a, b, c, d, e, f = Scanf.scanf "%f %f %f %f %f %f\n" (fun a b c d e f -> (a,b,c,d,e,f)) in
      let dt = a *. e -. b *. d in
      let x = (c *. e -. b *. f) /. dt in
      let y = (a *. f -. c *. d) /. dt in
      Printf.printf "%.3f %.3f\n" (round x) (round y)
    done
  with
    End_of_file -> ()

Measured memory_bytes: 2488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef vector<int> vec1;
typedef vector<string> vec2;
typedef vector<double> vec3;

int main() {
  
  int n;
  cin >> n;
  vec2 s(n);
  for(int i = 0; i < n; i++) cin >> s.at(i);
  sort(s.begin(),s.end());
  
  int ans = 1;
  for(int i = 1; i < n; i++) {
    if(s.at(i-1) != s.at(i)) {
      ans++;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 9544
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define PI 3.14159265358979323846
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;

int main(void) {
	int num = 12800, i, j, k, h, w, a;
	cin >> h >> w;
	vector<vector<int>> d(h + 1, vector<int>(w + 1, 0));
	vector<vector<vector<char>>> dp(h + 1, vector<vector<char>>(w + 1, vector<char>(num + 1, 0)));
	rep(i, h) {
		rep(j, w) {
			cin >> d[i][j];
		}
	}
	rep(i, h) {
		rep(j, w) {
			cin >> a;
			d[i][j] -= a;
			d[i][j] = abs(d[i][j]);
		}
	}
	dp[0][0][d[0][0]] = 1;
	rep(i, h) {
		rep(j, w) {
			rep(k, num) {
				if (dp[i][j][k]) {
					dp[i][j + 1][min(k + d[i][j + 1], num)] = 1;
					dp[i][j + 1][abs(k - d[i][j + 1])] = 1;
					dp[i + 1][j][min(k + d[i + 1][j], num)] = 1;
					dp[i + 1][j][abs(k - d[i + 1][j])] = 1;
				}
			}
		}
	}
	vector<char>& x = dp[h - 1][w - 1];
	rep(k, x.size()) {
		if (x[k])
			break;
	}
	cout << k << "\n";
	return 0;
}

Measured memory_bytes: 86620
N,L=map(int,input().split())
Ans=[0]*N
for i in range(N):
    Ans[i]=L+i
remove=1000000000
for i in range(N):
    if remove>=abs(Ans[i]):
        remove=abs(Ans[i])
        re=i
print(sum(Ans)-Ans[re])

Measured memory_bytes: 3060
// D - Walk and Teleport

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

ll X[100000];

int main() {
	ll N, A, B;
	cin >> N >> A >> B;

	for (int i=0; i<N; i++) {
		cin >> X[i];
	}

	ll ans = 0;
	for (int i=0; i<N-1; i++) {
		ans += min((X[i+1] - X[i]) * A, B);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, n) for(int i = 1; i < n; i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define P pair<int, int>
typedef long long ll;
const int mod = 1e9+7;

int main(){
  string s;
  cin >> s;
  int n = s.size()-1;
  ll ans = 0;
  for(int i = 0; i < (1<<n); i++){
    ll tmp = 0;
    bitset<10> b(i);
    rep(j,n+1){
      ll a = s[j] - '0';
      tmp = tmp*10 + a;
      if(b.test(j) || j == n){
        ans += tmp;
        tmp = 0;
      }
    }
  }
  cout << ans << endl;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int n, m;
    cin >> n >> m;
    vector<ll> v1(n);
    vector<ll> v2(n);
    vector<ll> v3(n);
    vector<ll> v4(n);
    vector<ll> v5(n);
    vector<ll> v6(n);
    vector<ll> v7(n);
    vector<ll> v8(n);
    ll a, b, c;
    for (int i = 0; i < n;i++)
    {
        cin >> a >> b >> c;
        v1[i] = a + b + c;
        v2[i] = a + b - c;
        v3[i] = a - b + c;
        v4[i] = a - b - c;
        v5[i] = -a + b + c;
        v6[i] = -a + b - c;
        v7[i] = -a - b + c;
        v8[i] = -a - b - c;
    }


    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());
    sort(v4.begin(), v4.end());
    sort(v5.begin(), v5.end());
    sort(v6.begin(), v6.end());
    sort(v7.begin(), v7.end());
    sort(v8.begin(), v8.end());
    

    ll s1 = 0, s2 = 0, s3 = 0, s4 = 0, s5 = 0, s6 = 0, s7 = 0, s8 = 0;
    for (int i = 0, j = n-1; i < m; i++,j--){
        s1 += v1[j];
        s2 += v2[j];
        s3 += v3[j];
        s4 += v4[j];
        s5 += v5[j];
        s6 += v6[j];
        s7 += v7[j];
        s8 += v8[j];
    }
    ll ve[] = { s1, s2, s3, s4, s5, s6, s7, s8 };
    ll ma = s1;
    for (int i = 0; i < 8; i++)
    {
        ll vo = ve[i];
        if (ma < vo)
        {
            ma = vo;
        }
    }
    cout << ma << endl;
}

Measured memory_bytes: 256
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

readl= lambda: list(map(int, sys.stdin.readline().split()))
readt= lambda: tuple(map(int, sys.stdin.readline().split()))
read = lambda: sys.stdin.readline().rstrip()
readi = lambda: int(read())
readmi = lambda: map(int, sys.stdin.readline().split())
readms = lambda: map(str, sys.stdin.readline().split())

t = readi()
print((t - 2) * 180)



Measured memory_bytes: 6480
#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    ll res = 0;
    vector<ll> a(n + 1), b(n);
    rep (i, n + 1) cin >> a[i];
    rep (i, n) cin >> b[i];
    rep (i, n) {
        if (b[i] >= a[i]) {
            b[i] -= a[i];
            res += a[i];
            if (b[i] >= a[i + 1]) {
                res += a[i + 1];
                a[i + 1] = 0;
            } else {
                res += b[i];
                a[i + 1] -= b[i];
            }
        } else {
            a[i] -= b[i];
            res += b[i];
        }
    }
    cout << res << endl;

    return 0;
}



Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
      Scanner scan = new Scanner(System.in);
      int a =  scan.nextInt();
      int b =  scan.nextInt();
      int c =  scan.nextInt();
      int x =  scan.nextInt();
      int count=0;
      for(int i=0;i<=a;++i){
        for(int j=0;j<=b;++j){
          for(int k=0;k<=c;++k){
            int sum = 500*i+100*j+50*k;
            if(sum==x)
            count++;
          }
        }
      }
      System.out.println(count);
      scan.close();
      
  }
}


Measured memory_bytes: 24916
#include <algorithm>
#include <climits>
#include <cmath>
#include <iostream>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <vector>

const int mod = 1e9 + 7;
const int kmax = 510000;

long long fact[kmax], fact_inv[kmax], inv[kmax];

int gcd(int a, int b)
{
    if (!b) {
        return a;
    }

    return gcd(b, a % b);
}

void init_comb()
{
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < kmax; i++) {
        fact[i] = fact[i - 1] * i % mod;
        inv[i] = mod - inv[mod % i] * (mod / i) % mod;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
    }
}

long long comb(int n, int r)
{
    if (n < r) {
        return 0;
    }

    if (n < 0 || r < 0) {
        return 0;
    }

    return fact[n] * (fact_inv[r] * fact_inv[n - r] % mod) % mod;
}

template <typename T, T N>
class UnionFind {
    T parent_[N];
    T rank_[N];
    T size_[N];

public:
    UnionFind();
    T Root(T idx);
    bool IsSame(T x, T y);
    void Unite(T x, T y);
    T GetSize(T idx);
};

template <typename T, T N>
UnionFind<T, N>::UnionFind()
{
    for (T i = 0; i < N; i++) {
        parent_[i] = i;
        rank_[i] = 0;
        size_[i] = 1;
    }
}

template <typename T, T N>
T UnionFind<T, N>::Root(T idx)
{
    return parent_[idx] == idx ? idx : parent_[idx] = Root(parent_[idx]);
}

template <typename T, T N>
bool UnionFind<T, N>::IsSame(T x, T y)
{
    return Root(x) == Root(y);
}

template <typename T, T N>
void UnionFind<T, N>::Unite(T x, T y)
{
    x = Root(x);
    y = Root(y);
    if (x == y) {
        return;
    }

    if (rank_[x] < rank_[y]) {
        parent_[x] = y;
        size_[y] += size_[x];
    } else {
        parent_[y] = x;
        size_[x] += size_[y];
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
}

template <typename T, T N>
T UnionFind<T, N>::GetSize(T idx)
{
    return size_[Root(idx)];
}

int main()
{
    int m1, d1, m2, d2;
    std::cin >> m1 >> d1 >> m2 >> d2;

    std::cout << (m1 != m2 ? 1 : 0) << std::endl;
}


Measured memory_bytes: 888
#include <iostream>
#include <string>

using namespace std;


int main(){
    int c0, c1;
    c0 = c1 = 0;
    string S;
    cin >> S; 
    for(int i = 0; i < S.size(); i++){
        if(S[i] == '0') c0++;
        else c1++;
    }
    cout << 2*min(c0, c1) << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>

int main(){
    
    std::string str;
    
    std::getline(std::cin, str);
    std::string::size_type size = str.size();
    
    for(int i=0; i<size; i++){
        if('A'<=str[i] && str[i]<='Z'){
            str[i]=tolower(str[i]);
        }else if('a'<=str[i] && str[i]<='z'){
            str[i]=toupper(str[i]);
        }
    }
    
    std::cout<<str<<std::endl;
    
    return 0;
}


Measured memory_bytes: 3216
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define ff first
#define ss second
#define ll long long
#define vi vector<int>
#define vii vector<vi>
#define vs vector<string>
#define vss vector<vs>
#define pii pair<int, int>
#define all(x) x.begin(), x.end()
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define repr(i, a, n) for (int i = (n); i >= (a); --i)
using namespace std;
const int INF(1 << 30);
const ll LLINF(1LL << 55LL);

void Main() {
  int a, b, c;
  cin >> a >> b >> c;
  if (c >= a && c <= b)
    puts("Yes");
  else
    puts("No");
}

int main() {
  std::cin.tie(nullptr);                  // 標準入出力高速化
  std::ios_base::sync_with_stdio(false);  // SとS++の入出力出力を非同期
  std::cout << std::fixed << std::setprecision(15);  // 小数を10進数表示
  Main();
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  int a,b;
  cin >> a >> b;
  cout << max({a+b, a-b, a*b}) << endl;
  return 0;
}


Measured memory_bytes: 256
// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools

#include <bits/stdc++.h>

using namespace std;

using i64 = long long;

const i64 MOD = 1e9 + 7;
const i64 INF = i64(1e18) + 7;


template <typename T>
bool chmin(T& x, T y){
    if(x > y){
        x = y;
        return true;
    }
    return false;
}

template <typename T>
bool chmax(T& x, T y){
    if(x < y){
        x = y;
        return true;
    }
    return false;
}


void solve(long long h, long long w, long long n){
    cout << (n + max(h, w) - 1) / max(h, w) << endl;
}


signed main(){
    long long H;
    scanf("%lld",&H);
    long long W;
    scanf("%lld",&W);
    long long N;
    scanf("%lld",&N);
    solve(H, W, N);
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;

#define all(x)  x.begin(), x.end()

int n;
int used[2020];
vector<int> a, ans;

void dfs(int v) {
        used[v] = true;
        ans.push_back(a[v]);
        for (int u = 0; u < n; u ++) {
                if (!used[u] && __gcd(a[v], a[u]) != 1) dfs(u);
        }
}

int main() {
        scanf("%d", &n);
        a.resize(n);
        for (int i = 0; i < n; i ++) scanf("%d", &a[i]);
        sort(all(a));
        for (int i = 0; i < n; i ++) if (!used[i]) dfs(i);
        for (int i = 0; i < n; i ++) {
                int p = i;
                for (int j = i - 1; j >= 0 && __gcd(ans[i], ans[j]) == 1; j --) {
                        if (ans[j] < ans[i]) p = j;
                }
                rotate(ans.begin() + p, ans.begin() + i, ans.begin() + i + 1);
        }
        for (int i = 0; i < n; i ++) cout << ans[i] << (i == n - 1 ? '\n' : ' ');
        return 0;
}


Measured memory_bytes: 384
import std.stdio, std.conv, std.functional, std.string;
import std.algorithm, std.array, std.container, std.range, std.typecons;
import std.bigint, std.numeric, std.math, std.random;
import core.bitop;

string FMT_F = "%.10f";

static File _f;
void file_io(string fn) { _f = File(fn, "r"); }
static string[] s_rd;
T _RD(T = long)() { while(!s_rd.length) s_rd = readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T _RD(T = long)(File f) { while(!s_rd.length) s_rd = f.readln.chomp.split; string res = s_rd[0]; s_rd.popFront; return res.to!T; }
T[] _RDA(T = long)(T fix = 0) { auto r = readln.chomp.split.to!(T[]); r[] += fix; return r; }
T[] _RDA(T = long)(File f, T fix = 0) { auto r = f.readln.chomp.split.to!(T[]); r[] += fix; return r; }
T RD(T = long)() { if (_f.isOpen) return _RD!T(_f); else return _RD!T; }
T[] RDA(T = long)(T fix = 0) { if (_f.isOpen)  return _RDA!T(_f, fix); else return _RDA!T(fix); }

size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

void chmin(T)(ref T x, T y) { x = min(x, y); } void chmax(T)(ref T x, T y) { x = max(x, y); }
bool inside(T)(T x, T b, T e) { return x >= b && x < e; }
T lcm(T)(T x, T y) { return x * (y / gcd(x, y)); }

//long mod = 10^^9 + 7;
long mod = 998_244_353;
//long mod = 1_000_003;
void moda(T)(ref T x, T y) { x = (x + y) % mod; }
void mods(T)(ref T x, T y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(T)(ref T x, T y) { x = (x * y) % mod; }
void modpow(T)(ref T x, T y) { if (!y) { x = 1; return; } auto t = x; x.modpow(y>>1); x.modm(x); if (y&1) x.modm(t); }
void modd(T)(ref T x, T y) { y.modpow(mod - 2); x.modm(y); }

void main()
{
	auto H = RD;
	auto W = RD;
	auto M = RD;
	auto cntH = new long[](H);
	auto cntW = new long[](W);
	bool[long[2]] b;
	foreach (i; 0..M)
	{
		auto h = RD-1;
		auto w = RD-1;
		b[[h, w]] = true;
		++cntH[h];
		++cntW[w];
	}

	long y, x;
	foreach (i; 0..H)
		y.chmax(cntH[i]);
	foreach (i; 0..W)
		x.chmax(cntW[i]);

	long ans;
	auto index = cntW.MAKE_IDX!"a > b";
	(){
	foreach (i; 0..H)
	{
		if (cntH[i] < y) continue;
		foreach (j; index)
		{
			if (cntW[j] < x) break;
			if (b.get([i, j], false) == false)
			{
				ans = cntH[i] + cntW[j];
				return;
			}
			else
			{
				ans = cntH[i] + cntW[j] - 1;
			}
		}
	}}();

	writeln(ans);
	stdout.flush;
	debug readln;
}


Measured memory_bytes: 49360
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x"=" << x <<endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3

#define MAX_N 1000000001

int main(){
	cin.sync_with_stdio(false);
	int n, l;
	cin >> n >> l;

	string s[n];
	rep(i, n) {
		cin >> s[i];
	}

	sort(s, s + n);

	rep(i, n){
		cout << s[i];
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#define lli long long int 
int main() {
	// your code goes here
	lli i,k,m;
	for(i=1;i<=5;i++)
	{
		cin>>k;
		if(k==0)
		m=i;
	}
	cout<<m;
	return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

void dump(vector<int> d)
{
    rep(i, d.size())
    {
        printf("%d ", d[i]);
    }
    cout << endl;
}

int main()
{
    int N;
    cin >> N;
    vector<int> L(N);
    rep(i, N)
    {
        cin >> L[i];
    }

    // cout << N
    //      << endl;
    // dump(L);
    sort(L.begin(), L.end());
    // dump(L);

    int count = 0;
    rep(a, N)
    {
        for (int b = a + 1; b < N; b++)
        {
            int ab = L[a] + L[b];
            int r = lower_bound(L.begin(), L.end(), ab) - L.begin();
            int l = b + 1;
            //c= [l,r)
            count +=max(0, r-l);
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
N, W = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(N)]

dp = [[0]*(N+1) for _ in range(W+1)]

for w in range(1, W+1):
	for i in range(1, N+1):
		# take one
		if D[i-1][0] <= w:
			dp[w][i] = max(dp[w][i-1], dp[w-D[i-1][0]][i-1] + D[i-1][1])
		# ignore
		dp[w][i] = max(dp[w][i], dp[w][i-1])

#print(dp)
print(max(dp[-1]))

Measured memory_bytes: 162644
#include <bits/stdc++.h>
using namespace std;

int count_div(int num) {
    map<int, int> divs{
        {3, 0},
        {5, 0},
        {7, 0},
        {11, 0},
        {13, 0}
    };
    int keys[] = {3, 5, 7, 11, 13};

    for (int i = 0; i < 5; i++) {
        while(num%keys[i] == 0) {
            divs[keys[i]]++;
            num /= keys[i];
        }
    }

    return (divs[3]+1)*(divs[5]+1)*(divs[7]+1)*(divs[11]+1)*(divs[13]+1);
}

int main() {
    int N;
    cin >>N;
    int ret = 0;

    for (int i = 1; i <= N; i++) {
        if (i%2==1) {
            int t = count_div(i);
            if (t == 8) ret++;
        }
    }
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 3600
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AIZU {
	class Program {
		#region Reserve
		static int cin() { return cin(-1); }
		static int cin(int D) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static int[] cins(char spliter) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			int[] Res = new int[ss.Length];
			for (int i = 0; i < ss.Length; i++)
				Res[i] = int.Parse(ss[i]);
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		#endregion
		
		static void Main(string[] args) {
			int[] I= cins();
			int N = I[0], A = I[1], B = I[2];
			List<long> H = new List<long>();
			for (int i = 0; i < N; i++) H.Add(cin());
			H.Sort((i,j)=>Math.Sign(j-i));
			long Limit = (long)Math.Ceiling((double)H.First()/B);
			long lo = 0,hi = Limit+1;
			while (hi - lo > 1) {
				long mid = (hi + 1 + lo) / 2;
				long Bass = mid * B;
				int count = 0;
				while (count < H.Count()&&H[count] > Bass) count++;
				long Time = H.Take(count).Sum(s => (long)Math.Ceiling((double)(s-mid*B) / (A-B)));
				if (mid < Time) lo = mid;
				else hi = mid;
			}
			long Bassf = lo * B;
			int countf = 0;
			while (countf < H.Count() && H[countf] > Bassf) countf++;
			long Timef = H.Take(countf).Sum(s => (long)Math.Ceiling((double)(s - lo * B) / (A - B)));
			print(lo<Timef?hi:lo);
			Console.ReadLine();
		}
	}
}

Measured memory_bytes: 19420
#include <bits/stdc++.h>
using namespace std;
int mod =1e9+7;

int main(){
int n,k;
cin>>n>>k;
vector<int>A(n+1);
for(int i=1;i<=n;++i)
    cin >>A[i];
int dp[n+1][k+1];
dp[0][0]=1;
for(int i=1;i<=k;++i)
    dp[0][i]=0;
for(int i=1;i<=n;++i){

    vector<int>sum(k+1);
    sum[0]=dp[i-1][0];
     for(int j=1;j<=k;++j)
        sum[j]=(sum[j-1]+dp[i-1][j])%mod;
     for(int j=0;j<=k;++j){
        if(j<=A[i])
            dp[i][j]=sum[j];
        else{
            int l = j-A[i]-1;
            dp[i][j]=(sum[j]-sum[l]+mod)%mod;
        }
     }
     sum.clear();
}
cout <<dp[n][k]<<endl;

return 0;

}



Measured memory_bytes: 43332
#include <bits/stdc++.h>
#define INF 2000000000000000000
#define ll long long
#define pb push_back
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll K, Q;
  cin >> K >> Q;
  vector<ll> D(K);
  for (ll i = 0; i < K; ++i) {
    cin >> D.at(i);
  }
  for (ll query = 0; query < Q; ++query) {
    ll N, X, M;
    cin >> N >> X >> M;
    vector<ll> mod_D = D;
    ll zero_num = 0;
    ll sum = 0;
    for (ll i = 0; i < K; ++i) {
      mod_D.at(i) %= M;
      sum += mod_D.at(i);
      if (mod_D.at(i) == 0) {
        zero_num += 1;
      }
    }
    ll ans = N - 1;
    ll zero_minus = 0;
    sum *= (N - 1) / K;
    for (ll i = 0; i < (N - 1) % K; ++i) {
      sum += mod_D.at(i);
      if (mod_D.at(i) == 0) {
        zero_minus += 1;
      }
    }
    // cout << ans << "\n";
    ans -= (sum + X % M) / M;
    // cout << (sum + X - 1) / M << "\n";
    ans -= ((N - 1) / K) * zero_num;
    ans -= zero_minus;
    cout << ans << "\n";
  }
}


Measured memory_bytes: 3724
from sys import exit, stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
count, ignore = 0, 0
for i, a in enumerate(A):
    if ignore == 1:
        ignore = 0
        continue
    if a-1 == i:
        count += 1
        if i != N-1:
            if A[i+1] != i+1:
                ignore = 1
print(count)

Measured memory_bytes: 13880
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define mkp make_pair
#define fi first
#define se second
void read(int &x){
	register char ch=getchar();x=0;
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';x=x*10+ch-'0',ch=getchar());
}
void write(int x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
struct gra{
	int to,col,val;
};
struct query{
	int v,val;
};
struct ask{
	int u,v,val,id;
};
int n,m,siz[100004],p[100004],h[100004],nxt[100004];
vector<gra>g[100004];
vector<query>q[100004];
void dfs1(int x,int par){
	siz[x]=1,p[x]=par;
	int maxx=0;
	for(int i=0;i<g[x].size();i++)if(g[x][i].to!=par){
		nxt[g[x][i].to]=g[x][i].val;
		q[g[x][i].col].push_back((query){g[x][i].to,g[x][i].val});
		dfs1(g[x][i].to,x),siz[x]+=siz[g[x][i].to];
		if(maxx<siz[g[x][i].to])maxx=siz[g[x][i].to],h[x]=g[x][i].to;
	}
}
int cnt,cmp[100004],pre[100004];
void dfs2(int x,int par,int H){
	cmp[x]=++cnt,pre[cnt]=nxt[x],nxt[x]=H;
	if(h[x])dfs2(h[x],x,H);
	for(int i=0;i<g[x].size();i++)if(g[x][i].to!=h[x]&&g[x][i].to!=par)
		dfs2(g[x][i].to,x,g[x][i].to);
}
void init(){
	for(int i=2;i<=n;i++)pre[i]+=pre[i-1];
}
int isans(int l,int r,int x){
	return cmp[l]<=cmp[x]&&cmp[x]<=cmp[r];
}
int ans[100004];
void lca_ans_sp(int u,int v,int id){
	while(1){
		if(cmp[u]>cmp[v])swap(u,v);
		int L=nxt[v];
		if(isans(L,v,u)){
			ans[id]+=pre[cmp[v]]-pre[cmp[u]];
			return;
		}
		ans[id]+=pre[cmp[v]]-pre[cmp[L]-1];
		v=p[L];
	}
}
vector<ask>a[100004];
int bit1[100004],bit2[100004];
void add(int id,int a1,int a2){
	while(id<=n){
		bit1[id]+=a1,bit2[id]+=a2;
		id+=(id&-id);
	}
}
pii got(int id){
	pii ret=mkp(0,0);
	while(id){
		ret.fi+=bit1[id],ret.se+=bit2[id];
		id-=(id&-id);
	}
	return ret;
}
pii qry(int l,int r){
	pii A=got(l-1),B=got(r);
	return mkp(B.fi-A.fi,B.se-A.se);
}
pii fans(int u,int v){
	pii ret=mkp(0,0);
	while(1){
		if(cmp[u]>cmp[v])swap(u,v);
		int L=nxt[v];
		if(isans(L,v,u)){
			pii gt=qry(cmp[u]+1,cmp[v]);
			ret.fi+=gt.fi,ret.se+=gt.se;
			return ret;
		}
		pii gt=qry(cmp[L],cmp[v]);
		ret.fi+=gt.fi,ret.se+=gt.se;
		v=p[L];
	}
}
int main(){
	read(n),read(m);
	for(int i=1;i<n;i++){
		int A,B,C,D;read(A),read(B),read(C),read(D);
		g[A].push_back((gra){B,C,D});
		g[B].push_back((gra){A,C,D});
	}
	dfs1(1,-1);
	dfs2(1,-1,1);
	init();
	for(int i=1;i<=m;i++){
		int C,D,A,B;read(C),read(D),read(A),read(B);
		lca_ans_sp(A,B,i);
		a[C].push_back((ask){A,B,D,i});
	}
	for(int i=1;i<n;i++)if(!a[i].empty()){
		for(int j=0;j<q[i].size();j++)add(cmp[q[i][j].v],q[i][j].val,1);
		for(int j=0;j<a[i].size();j++){
			pii ret=fans(a[i][j].u,a[i][j].v);
			ans[a[i][j].id]-=ret.fi;
			ans[a[i][j].id]+=ret.se*a[i][j].val;
		}
		for(int j=0;j<q[i].size();j++)add(cmp[q[i][j].v],-q[i][j].val,-1);
	}
	for(int i=1;i<=m;i++)write(ans[i]),puts("");
}

Measured memory_bytes: 27140
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

template <class T>
void chmax(T &a, T b) {
    if (b > a) a = b;
}

constexpr int W = (int)1e+5, K = 9;

int dp[1 << K][W + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    n++;

    vector<int> v(n), w(n);
    for (int i = 1; i < n; i++) {
        cin >> v[i] >> w[i];
    }

    int n1 = min(1 << K, n);
    for (int i = 1; i < n1; i++) {
        int i0 = i / 2;
        for (int j = 0; j < w[i]; j++) {
            dp[i][j] = dp[i0][j];
        }
        for (int j = w[i]; j <= W; j++) {
            dp[i][j] = max(dp[i0][j], dp[i0][j - w[i]] + v[i]);
        }
    }

    vector<ll> s(1 << K);
    s[0] = 0;

    int q;
    cin >> q;

    while (q--) {
        int i, j;
        cin >> i >> j;

        int r;

        if (i < 1 << K) {
            r = dp[i][j];

        } else {
            ll p[K];
            int h0;
            for (int h = 0;;) {
                p[h++] = (ll)v[i] << 32 | w[i];
                i /= 2;
                if (i < 1 << K) {
                    h0 = h;
                    break;
                }
            }

            r = dp[i][j];
            for (int h = 0; h < h0; h++) {
                int m = 1 << h;
                for (int l = m; l < m << 1; l++) {
                    s[l] = s[l & ~m] + p[h];
                    int v1 = s[l] >> 32, w1 = s[l];
                    if (w1 > j) continue;
                    chmax(r, dp[i][j - w1] + v1);
                }
            }
        }

        cout << r << '\n';
    }

    return 0;
}

Measured memory_bytes: 205068
N = int(input())
A= input()
B= input()
C= input()

total=0
for n in range(N):
  counter=0
  if A[n] == B[n] and B[n] == C[n]: 
    counter=0
  if A[n] != B[n] and A[n] == C[n] :
    counter=1
  if A[n] == B[n] and A[n] != C[n]: 
    counter=1
  if B[n] == C[n] and A[n] != B[n]:
    counter=1
  if A[n] != B[n] and B[n] != C[n] and C[n] != A[n]:
    counter=2

  total +=counter

print(total)

Measured memory_bytes: 3064