akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define MAX_NUM (1000000000 + 7)

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

u32 dp[100010][3];
u32 abc[100010][3];

int main() {
  cout << setprecision(18);
  u32 N;
  cin >> N;
  vector<u32> a(N), b(N), c(N);
  for (u32 i = 0; i < N; ++i) cin >> abc[i][0] >> abc[i][1] >> abc[i][2];

  dp[0][0] = 0;
  dp[0][1] = 0;
  dp[0][2] = 0;

  for (u32 i = 0; i < N; ++i) {
    for (u32 j = 0; j < 3; ++j) {
      for (u32 k = 0; k < 3; ++k) {
        if (j == k) continue;
        dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + abc[i][k]);
      }
    }
  }
  u32 res = 0;
  for (u32 i = 0; i < 3; ++i) {
    if (res < dp[N][i]) res = dp[N][i];
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 3712
#設定
import sys
input = sys.stdin.buffer.readline

from collections import defaultdict
import queue

#入力受け取り
def getlist():
	return list(map(int, input().split()))

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"

#処理内容
def main():
	N = int(input())
	#1-Nの数を3で割った数の個数(あまり)
	a0 = int(N // 3)
	a1 = int((N + 2) // 3)
	a2 = int((N + 1) // 3)

	#グラフ構築
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#偶奇で判断 可能性判定	
	BF = BFS(G, 0, N)
	dist = BF.dist
	dis_even = 0
	dis_odd = 0
	for i in range(N):
		if dist[i] % 2 == 0:
			dis_even += 1
		else:
			dis_odd += 1

	ans = [0] * N
	judge = "No"
	S = [(i + 1) * 3 for i in range(a0)] + [i * 3 + 1 for i in range(a1)] + [i * 3 + 2 for i in range(a2)]
	if a2 <= dis_odd and a1 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a2:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a1:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

		print(" ".join(map(str, ans)))

	elif a1 <= dis_odd and a2 <= dis_even:
		judge = "Yes"
		c1 = 0
		c2 = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				if c1 < a1:
					ans[i] = c1 * 3 + 2
					c1 += 1
			else:
				if c2 < a2:
					ans[i] = c2 * 3 + 1
					c2 += 1

		cnt = 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = 3 * cnt
				cnt += 1

		print(" ".join(map(str, ans)))

	elif dis_odd <= a0:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 != 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1

		print(" ".join(map(str, ans)))

	else:
		cnt = 0
		for i in range(N):
			if dist[i] % 2 == 0:
				ans[i] = S[cnt]
				cnt += 1
		for i in range(N):
			if ans[i] == 0:
				ans[i] = S[cnt]
				cnt += 1

		print(" ".join(map(str, ans)))
	

if __name__ == '__main__':
	main()

Measured memory_bytes: 128712
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <numeric>
#include <sstream>
#include <queue>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int (i)=0; (i)<(n); (i)++)
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define PUSH(n,v) for(int i=0; i<(n); i++) {int j; cin >> j; v.push_back(j);}
#define ALL(v) v.begin(), v.end()
#define print(s) cout << (s) << endl

const int INF = 1e5;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> cost = vector<vector<int>>(20,vector<int>(20,INF));
    int a, b, c, d;
    REP(i,m) {
        scanf("%d,%d,%d,%d", &a, &b, &c, &d);
        cost[--a][--b] = c;
        cost[b][a] = d;
    }
    
    REP(i,n) REP(j,n) REP(k,n) {
        cost[j][k] = min(cost[j][k], cost[j][i] + cost[i][k]);
    }
    int s, g, v, p;
    scanf("%d,%d,%d,%d", &s, &g, &v, &p);
    cout << v - p - cost[--s][--g] - cost[g][s] << endl;
    return 0;
}

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

#define MOD 1000000007LL

long long fac[1000001],finv[1000001],inv[1000001];

void COMinit(){
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<1000001;i++){
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
 
long long COM(int n,int k){
	if(n<k)return 0;
	if(n<0 || k<0)return 0;
	return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD;
}
 
long long MODpow(long long a,int b){
	if(b==0)return 1;
	if(b%2==0){
		long long t=MODpow(a,b/2);
		return (t*t)%MOD;
	}
	return (a*MODpow(a,b-1))%MOD;
}

int main(){
	COMinit();
	int N;
	cin >> N;
	vector<long long> C(N);
	for(auto &i:C)cin >> i;
	sort(C.begin(),C.end());
	
	long long ans=0;
	
	
	for(int i=0;i<N;i++){
		long long add=0;
		add+=C[i]*(N+1-i);
		add%=MOD;
		ans+=add;
		ans%=MOD;
	}
	
	ans=(ans*MODpow(4,N-1))%MOD;
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 25344
fib=[0,0,1,2]
for i in range(4,100005):
  fib.append(fib[i-1]+fib[i-2])

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]

a=set(a)

p,q=0,1

for i in range(1,n+1):
  p,q=q,(p+q)%(10**9+7)*(not i in a)

print(q)

Measured memory_bytes: 486792
n, x, y = map(int, input().split())

answer = {}
for i in range(1, n):
    answer[i] = 0

for i in range(1, n):
    for j in range(i + 1, n + 1):
        strait = j - i
        shortcut = abs(x - i) + 1 + abs(y - j)
        d = min(strait, shortcut)
        answer[d] += 1

for i in answer.keys():
    print(answer[i])

Measured memory_bytes: 3572
//@author :  |< U $ |-|
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<algorithm>
#include<list>
#include<cstring>
#include<unordered_map>
#define ll long long
#define vi vector<long long>
#define pb push_back
#define pop pop_back
#define pi pair<long long ,long long>
#define vp vector<pair<long long,long long> >
#define mkp make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define map map<long long,long long>
#define inm1(b)  memset(b,-1,sizeof(b))
#define in0(b) memset(b,0,sizeof(b))
#define ininf(b) memset(b,1000000001,sizeof(b))
#define MOD         1000000007
#define I 1000000000000000001
#define t(a) cout<<a<<" "<<endl
#define tt(a,b) cout<<a<<" "<<b<<endl
#define th(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define TakeInput freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
using namespace std;
ll gcd(ll a, ll b) {  if (a == 0)  return b; return gcd(b % a, a); }

bool issafe(int i,int j,int n,int m){
    return (i<n && j<m && j>=0 && i>=0 );
}

int main(){
    jaldi
    #ifndef ONLINE_JUDGE
    TakeInput
    #endif
    
    ll w,h,m,i;
    cin>>h>>w>>m;

    unordered_map<ll,unordered_map<ll,ll> > mp;
    unordered_map<ll,ll>xs,ys;
    for(i=0;i<m;i++){
        ll x,y;
        cin>>x>>y;
        mp[x][y]++;
        xs[x]++;
        ys[y]++;
    }

    vector<ll> cadidate_x,candidate_y;
    ll max_x = 0 ,max_y = 0 ;

    for(i=0;i<=h;i++)max_x = max(max_x, xs[i]) ; 
    for(i=0;i<=w;i++)max_y = max(max_y, ys[i]) ; 

    for(i=0;i<=h;i++){
        if(xs[i] == max_x)
            cadidate_x.pb(i);
    }
    for(i=0;i<=w;i++){
        if(ys[i] == max_y)
            candidate_y.pb(i);
    }
    ll ans = max_x + max_y - 1,count=0 ;
    for(auto&  i : cadidate_x){
        for(auto& j : candidate_y){
            if(!mp[i][j]){
                ans++;
                goto c;
            }
        }
    }
    c:
    cout<<ans;



}


Measured memory_bytes: 84708
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def main():
    N = int(input())
    A = list(map(int, input().split()))

    L = [0]
    R = [0]
    for i in range(N):
        L.append(gcd(L[i], A[i]))
        R.append(gcd(R[i], A[N-i-1]))

    R.reverse()
    M = [gcd(L[i], R[i+1]) for i in range(N)]
    print(max(M))


if __name__ == '__main__':
    main()

Measured memory_bytes: 14076
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    k = kwargs["k"]
    D = kwargs["D"]
    A = kwargs["A"]
    C = [0 for i in range(n)]

    for i in range(k):
        for j in range(D[i]):
            C[A[i][j] - 1] += 1

    res = 0

    for i in range(n):
        if C[i] == 0:
            res += 1

    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    #kwargs["n"] = cin[0]
    #kwargs["n"], kwargs["k"] = cin
    #kwargs["n"] = [int(i) for i in cin][0]
    kwargs["n"], kwargs["k"] = [int(i) for i in cin]

    kwargs["D"] = []
    kwargs["A"] = []

    for i in range(kwargs["k"]):
        cin = input().split()
        #kwargs["n"] = cin[0]
        #kwargs["n"], kwargs["k"] = cin
        d = [int(i) for i in cin][0]
        #kwargs["n"], kwargs["k"] = [int(i) for i in cin]
        kwargs["D"].append(d)

        cin = input().split()
        #a = cin[0]
        #a = cin
        #a = [int(i) for i in cin][0]
        a = [int(i) for i in cin]
        kwargs["A"].append(a)

    cout = main(kwargs)
    print(cout)

Measured memory_bytes: 31192
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

template<typename T>
void zaatu(const vector<T>& v, map<T, ll>& mv, vector<T>& rv) {
    for(auto&& i: v) mv[i] = 0;
    rv.resize(mv.size());
    int cnt = 0;
    for(auto& p : mv) {
        rv[cnt] = p.fi;
        p.se = cnt++;
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    vl a(n), b(n), c(n), d(m), e(m), f(m);
    rep(i, n) cin >> a[i] >> b[i] >> c[i];
    rep(i, m) cin >> d[i] >> e[i] >> f[i];
    const int INF = 1e9+10;
    map<ll, ll> mx, my;
    vl rx, ry;
    mx[0] = 1;
    my[0] = 1;
    mx[-INF] = 1; mx[INF] = 1; mx[-INF-1] = 1; mx[INF+1] = 1;
    my[-INF] = 1; my[INF] = 1; my[-INF-1] = 1; my[INF+1] = 1;
    zaatu(a, mx, rx);
    zaatu(b, mx, rx);
    zaatu(c, my, ry);
    zaatu(d, mx, rx);
    zaatu(e, my, ry);
    zaatu(f, my, ry);
    
    using B = bitset<4>;
    vector<vector<B>> nxt(my.size()-1, vector<B>(mx.size()-1));
    rep(i, nxt.size()) rep(j, nxt[i].size()) nxt[i][j].set();

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, -1, 0, 1};

    rep(i, n) {
        auto y = my[c[i]];
        REP(x, mx[a[i]], mx[b[i]]) {
            nxt[y-1][x].reset(3);
            nxt[y][x].reset(1);
        }
    }
    rep(i, m) {
        auto x = mx[d[i]];
        REP(y, my[e[i]], my[f[i]]) {
            nxt[y][x-1].reset(2);
            nxt[y][x].reset(0);
        }
    }

    const int sx = mx[-INF], tx = mx[INF];
    const int sy = my[-INF], ty = my[INF];

    

    vector<vl> area(my.size()-1, vl(mx.size()-1));
    queue<pii> q;
    q.push({my[0], mx[0]});
    while(!q.empty()) {
        auto p = q.front();
        q.pop();
        int y = p.fi, x = p.se;
        if(area[y][x] != 0) continue;
        if(y == sy || y == ty || x == sx || x == tx) {
            cout << "INF" << '\n';
            return 0; 
        }
        {
            area[y][x] = (ry[y+1] - ry[y]) * (rx[x+1] - rx[x]);
        }
        rep(k, 4) if(nxt[y][x][k]) { 
            int ny = y+dy[k], nx = x+dx[k];
            if(area[ny][nx] == 0) q.push({ny, nx});
        }
    }
    ll ans = 0LL;
    for(auto&& low: area) ans += accumulate(all(low), 0LL);
    cout << ans << '\n';
    return 0;
}

Measured memory_bytes: 145036
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m; i<n; i++)
#define co(n) cout << n << endl
using namespace std;
int main(){
  long a, b, c=0, d=0, e, f, g, h, n;
  cin >> n;
  long x[40];
  x[0]=n;
  c++;
  while(1){
    if(n/2==0) break;
    else{
      n/=2;
      c++;
    }
  }
  a=pow(2, c)-1;
  co(a);
  
      
      
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
 
int main()
{
	int n,i,e;
	long d=0;
	long a[200],c[200]={0};
	scanf("%d",&n);
	for(i=0;i<n;i++)
	scanf("%ld",&a[i]);
	while(1)
	{
	for(i=0;i<n;i++)
	{
		if(a[i]%2==0)
		{
			e=1;
			a[i]/=2;
		}
		else
		{e=0;
		break;}
		}
		if(e==1)
		d++;
		else
		break;
	}
	printf("%ld",d);
	}


Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<string>

using namespace std;

void reverseString (string& str) {
    int left = 0;
    int right = str.size()-1;
    while (left < right) {
        swap(str[left], str[right]);
        left++;
        right--;
    }
}

int main() {
    string str;
    int n = 0;
    int f;
    string c;
    cin >> str;
    cin >> n;
    bool reverseFlag = false;
    for (int i = 0; i < n; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            reverseFlag = !reverseFlag;
        } else if (t == 2) {
            cin >> f;
            cin >> c;
            if ((f == 1) != reverseFlag){
                str.insert(0, c);
            } else {
                str.append(c);
            }
        }
    }
    if(reverseFlag) reverseString(str);
    cout << str;
}


Measured memory_bytes: 900
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 550
typedef long long ll; 
using namespace std;
ll n;
int h[N], htot;
inline void Insert(int p) {
  for (int i = htot; i > p; --i) swap(h[i], h[i + 1]);
  h[p + 1] = ++htot;
}
int main() {
  scanf("%lld", &n); ++n;
  int j = 0;
  while ((1ll << j) <= n) ++j;
  --j;
  for (int i = 1; i <= j; ++i) h[i] = i;
  htot = j;
  for (int i = j - 1; ~i; --i) if (n & (1ll << i)) {
    Insert(i);
  }
  printf("%d\n", htot + 100); 
  for (int i = 1; i <= htot; ++i)  printf("%d ", h[i]);
  for (int i = 1; i < 100; ++i) printf("%d ", i); 
  puts("100");
  return 0;
}


Measured memory_bytes: 3252
import java.util.*;

public class Main {
    //-------------------------------------------------------------//
    public static final void main(String[] args) {
        new Main().solve();
    }
    //-------------------------------------------------------------//
    private final Scanner sc = new Scanner(System.in);
    void solve() {
        long H = sc.nextInt();
        long W = sc.nextInt();

        long res = Long.MAX_VALUE;

        res = Math.min(res, W % 3 == 0 ? 0 : ((W / 3 + 1) * H) - ((W / 3) * H));
        res = Math.min(res, H % 3 == 0 ? 0 : ((H / 3 + 1) * W) - ((H / 3) * W));

        for (long w = 1; w < W; w++) {
            long a = w * H;
            long b = (H / 2) * (W - w);
            long c = (H - (H / 2)) * (W - w);
            long max = Math.max(a, Math.max(b, c));
            long min = Math.min(a, Math.min(b, c));
            res = Math.min(res, max - min);
        }

        for (long h = 1; h < H; h++) {
            long a = h * W;
            long b = (W / 2) * (H - h);
            long c = (W - (W / 2)) * (H - h);
            long max = Math.max(a, Math.max(b, c));
            long min = Math.min(a, Math.min(b, c));
            res = Math.min(res, max - min);
        }

        System.out.println(res);
    }
}

Measured memory_bytes: 22100
#include <stdio.h>

int main(void){

  //aは計算を行うための変数
  int a, i;

  //bはcの値が変わる前の値を記憶する変数
  int b = 0;

  //cはaのb+cを記憶しておく変数
  int c = 1;

  //nは入力値
  int n;
  
  scanf("%d",&n); 
  for(i=0;i<=n;i++){ 
    a = b+c;
    b = c;
    c = a;
  }
  printf("%d\n", b);
  
  return 0;
}

Measured memory_bytes: 596
s = input()
# s_list = list(s)
s_under = int(s[2:]) # YYMM
s_upper = int(s[:2]) # MMYY

if 1 <= s_under <=12 and 1<=s_upper<=12:
    print("AMBIGUOUS")
elif 1 <= s_under <=12:
    print("YYMM")
elif 1 <= s_upper <=12:
    print("MMYY")
else:
    print("NA")

Measured memory_bytes: 2940
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
# include <map>
//deque/functional/iterator/list/map/memory/numeric/queue/set/stack/utility/vector
//#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 1e9+7;

int main()
{
    int n;
    scanf("%d",&n);
    int  a[100010];
    int m[100010]={0};

    for(int i = 0;i < n;i++){
        scanf("%d",&a[i]);
        m[a[i]]++;
    }

    int flag = 0;
    if(n%2==1)//奇数
    {
        if(m[0] != 1)
			flag = 1;
        for(int i = 2;i < n;i+=2)
        {
            if(m[i] != 2)
            {
                flag = 1;
            }
        }
    }else{  //偶数
        for(int i = 1;i < n;i+=2)
        {
            if(m[i] != 2)
            {
                flag = 1;
            }
        }
    }
    long long sum = 1;

    for(int i =0;i < floor(n/2);i++)
    {
        sum = (sum * 2)% mod;
    }

    if(n%2)
    {
        if(flag)
        printf("0\n");
        else
        printf("%lld\n",sum);
    }
    else
    {
        if(flag)
        printf("0\n");
        else
        printf("%lld\n",sum);
    }

return 0;
 }

Measured memory_bytes: 1024
// created on : Sun Jun 21 2020
 
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        char a = in.next().charAt(0);
        if(Character.isUpperCase(a)){
            println("A");
        }
        else{
            println("a");
        }
        
        in.close();
        out.close();
    }

    static int MIN = Integer.MIN_VALUE;
    static int MAX = Integer.MAX_VALUE;
    static Reader in = new Reader();
    static PrintWriter out = new PrintWriter(System.out);

    static int[] readInt(int N) throws IOException { 
    	int arr[] = new int[N];
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextInt(); 
    	} 
    	return arr;
    }
    
    static long[] readLong(int N) throws IOException { 
    	long arr[] = new long[N];
    	for(int i = 0; i < N; i++){ 
    		arr[i] = in.nextLong(); 
    	} 
    	return arr;
    }
    
    static void print(Object O) {  
    	out.print(O); 
    }
    
    static void println(Object O) { 
    	out.println(O); 
    }
    
    static void println(int arr[]) { 
    	for(int i = 0; i < arr.length; i++){ 
    		print(arr[i] + " "); 
    	} 
    	println(""); 
    }
    
    static void displayRuntime(long startTime){
        long stopTime = System.currentTimeMillis();
        long elapsedTime = stopTime - startTime;
        System.out.println("Runtime: " + elapsedTime / 1000D);
    }
}

class Reader {
    BufferedReader reader;
    StringTokenizer tokenizer;

    Reader() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    String next() throws IOException {
        while (!tokenizer.hasMoreTokens() ) { 
            tokenizer = new StringTokenizer(reader.readLine()); 
        }
        return tokenizer.nextToken();
    }

    int nextInt() throws IOException { 
        return Integer.parseInt(next()); 
    }
    
    double nextDouble() throws IOException { 
        return Double.parseDouble(next());
    }
    
    long nextLong() throws IOException { 
        return Long.parseLong(next()); 
    }
    
    String nextLine() throws IOException { 
        return reader.readLine(); 
    }
    
    void close() throws IOException { 
        reader.close(); 
    }
}


Measured memory_bytes: 25312
/*
	Author: Dinesh Verra
	College: ABV-IIITM
	Date: 10/07/2020
*/
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp> 
// using namespace boost::multiprecision; 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define cu continue
#define br break
#define pb push_back
#define eb emplace_back
// #define mod 1000000007
#define inf LLONG_MAX
#define pll pair <ll,ll>
#define min_pq priority_queue <pll> ,vector <pll>, greater <pll> > > 
#define F first
#define S second
#define vll vector <ll>
#define vpll vector <pll>
#define dbg(n) cout<<#n<<' '<<n<<endl;
#define all(v) v.begin(),v.end()
#define nl cout<<'\n'

template <typename A1>
void prn(A1&& arg)
{
	cout<<arg<<'\n';
}
template <typename A1, typename... A>
void prn(A1&& arg, A&&... args)
{
	cout<<arg<<' ';
	prn(args...);
}

ll mpow(ll x, ll y, ll mod)
{
	if(mod==0) return 0;
	ll res=1;
	while(y>0)
	{
		if(y&1) res=(res*x)%mod;
		x=(x*x)%mod;
		y>>=1;
	}
	return res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	#ifndef ONLINE_JUDGE
	freopen("/home/dinesh_verra/cpp/input.txt","r",stdin);
	// freopen("/home/dinesh_verra/cpp/output.txt","w",stdout);
	#endif

	ll n;
	cin>>n;
	string s;
	cin>>s;
	ll x=0;
	for(ll i=0;i<n;i++) if(s[i]=='1') x++;
	ll a[3][n+5],idx=-1;
	for(ll i=0;i<=n;i++) a[0][i]=0,a[1][i]=0,a[2][i]=0;
	for(ll i=0;i<n;i++)
	{
		if(s[i]=='1')
		{
			a[0][i]=mpow(2ll,(n-i-1),x-1);
			a[1][i]=mpow(2ll,(n-i-1),x);
			a[2][i]=mpow(2ll,(n-i-1),x+1);
			idx=i;
		}
		else
		{
			a[0][i]=0;
			a[1][i]=0;
			a[2][i]=0;
		}
	}
	for(ll i=1;i<n;i++)
	{
		a[0][i]=(a[0][i-1]+a[0][i]);
		if(x!=1) a[0][i]%=(x-1);
		a[1][i]=(a[1][i-1]+a[1][i]);
		if(x!=0) a[1][i]%=x;
		a[2][i]=(a[2][i-1]+a[2][i])%(x+1);
	}
	ll ans[n+5],tmp;
	ll b[n+5],y;
	for(ll i=0;i<n;i++)
	{
		b[i]=1;
		if(x==1 && idx==i)
		{
			b[i]=0;
		}
		if(s[i]=='1' && (x!=1))
		{
			tmp=a[0][n-1];
			tmp=(tmp-mpow(2ll,n-i-1,x-1)+(x-1))%(x-1);
			ans[i]=tmp;
		}
		else
		{
			tmp=a[2][n-1];
			tmp=(tmp+mpow(2ll,n-i-1,x+1))%(x+1);
			ans[i]=tmp;
		}
	}
	for(ll i=0;i<n;i++)
	{
		tmp=ans[i];
		while(tmp>0)
		{
			y=__builtin_popcountll(tmp);
			tmp%=y;
			b[i]++;
		}
		prn(b[i]);
	}
}

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

int main () {
  int n, x; cin >> n >> x;
  
  int64_t ans =0;
  int a[100005];
  for (int i=0; i<n; i++)	{
    cin >> a[i];
  }
  for (int i=0; i<n-1; i++) {
    if (a[i] + a[i+1] > x) {
      ans += a[i] + a[i+1] - x;
      a[i+1] = max(0, x-a[i]);
    }
  }
  cout << ans  << endl;
}

Measured memory_bytes: 640
// Header {{{
#include <bits/stdc++.h>

using namespace std;
template<typename T>
using reversed_priority_queue = std::priority_queue<T, std::vector<T>, std::greater<T> >;
typedef unsigned long long int ull;
typedef long long int ll;
#define rep(i,a,b) for (ll i=(a); i<(b); i++)
typedef pair<ll,ll> PLL;
// }}}

signed main() {
    ll n, total=0;
    cin>>n;
    vector<ll> s(n);
    rep(i,0,n){
        cin>>s[i];
        total+=s[i];
    }
    sort(begin(s),end(s));
    if (total>0 && total%10==0) {
        rep(i,0,n){
            if (s[i]%10!=0){
                total-=s[i];
                break;
            }
        }
    }
    if (total%10==0){
        total=0;
    }
    cout<<total<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include <string>
using namespace std;
int main(){
  string s,t;
  cin >> s>> t;
  int si=s.size();
  for(int i=0;i<si;i++){
    if(t[0]==s[i]){
      string g=s.substr(i);
      g+=s.substr(0,i);
      if(t==g) {
        cout <<"Yes"<<endl;
        return 0;
      }
    }
  }
  cout <<"No"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define inf 1000000000
#define IOS ios_base::sync_with_stdio(0);cin.tie(0)
#define meM(y,a) memset(y,a,sizeof y)
#define sC(a) scanf("%d",&a)
#define alL(a) a.begin(),a.end()
#define prinT(a,sz)  cout<<a[0];for(int i=1;i<sz;i++)cout<<" "<<a[i];cout<<endl
#define ranD srand(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int>pi;
typedef pair<ll,ll>pll;
int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};
//int gx[]={0,0,1,1,1,-1,-1,-1};
//int gy[]={1,-1,0,1,-1,0,1,-1};
const int N=23;
int lvl[N][N];
char adj[N][N];
int n,m;
int bfs(pi st)
{
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)lvl[i][j]=inf;
    queue<pi>q;
    q.push(st);
    lvl[st.ff][st.ss]=0;
    int res=0;
    while(!q.empty())
    {
        int x=q.front().ff,y=q.front().ss;
        q.pop();
        for(int k=0;k<4;k++)
        {
            int xx=x+fx[k];
            int yy=y+fy[k];
            if(xx>=0&&xx<n&&yy<m&&yy>=0){
                if(lvl[x][y]+1<lvl[xx][yy]&&adj[xx][yy]=='.')
                {
                    q.push({xx,yy});
                    lvl[xx][yy]=lvl[x][y]+1;
                    res=max(res,lvl[xx][yy]);
                }
            }
        }
    }
    return res;
}
int main()
{
    IOS;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)cin>>adj[i][j];
    int ans=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(adj[i][j]=='#')continue;
            ans=max(ans,bfs({i,j}));
        }
    }
    cout<<ans<<endl;
}








Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(ll i=0;i<(n);i++)
#define rrep(i,n) for(ll i = 1; i <= (n); ++i)
#define drep(i,n) for(ll i = (n)-1; i >= 0; --i)
#define all(v) v.begin(),v.end()
#define len(x) (ll)(x).length()
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define pb push_back
#define sz(x) (ll)(x).size()
#define v(T) vector<T>
#define vv(T) vector<vector<T>>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
ll gcd(ll a,ll b){if(a%b==0){return b;}else{return(gcd(b,a%b));}}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
const int INF=1e9;
const ll MX = 1e18;
const int MOD=INF+7;
const int di[] = {-1,0,1,0};
const int dj[] = {0,-1,0,1};
const double PI=acos(-1);
 
int main() {
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  while(true){
    c-=b;
    if(c<=0){
      cout<<"Yes"<<endl;
      return 0;
    }
    a-=d;
    if(a<=0){
      cout<<"No"<<endl;
      return 0;
    }
  }
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define REP(i,N) for(i=0;i<N;i++)
#define MAX_I INT_MAX //1e9
#define MIN_I INT_MIN //-1e9
#define MAX_UI UINT_MAX //1e9
#define MAX_LL LLONG_MAX //1e18
#define MIN_LL LLONG_MIN //-1e18
#define MAX_ULL ULLONG_MAX //1e19
  typedef long long ll;
  typedef pair<int,int> PII;
  typedef pair<char,char> PCC;
  typedef pair<ll,ll> PLL;
  typedef pair<char,int> PCI;
  typedef pair<int,char> PIC;
  typedef pair<ll,int> PLI;
  typedef pair<int,ll> PIL; 
  typedef pair<ll,char> PLC; 
  typedef pair<char,ll> PCL; 

int main(void){
  int N,X;cin >> N >> X;
  int i,m[N];
  int minimum = MAX_I;
  REP(i,N){
    cin >> m[i];
    minimum = min(m[i],minimum);
    X-=m[i];
  }
  cout << N + X/minimum << endl;
  return 0;
}


Measured memory_bytes: 256
N, M, P = map(int, input().split())
from collections import deque,defaultdict
edge1 = [[] for _ in range(N)]
edge2 = [[] for _ in range(N)]
for i in range(M):
    a,b,c= map(int, input().split())
    edge1[a-1].append([b-1,P-c])
    edge2[b-1].append([a-1,P-c])
edges1 = set()
d = deque([0])
visited1 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge1[v]:
        if visited1[w*10**8+v*10**4+u] == False:
            visited1[w*10**8+v*10**4+u] = True
            edges1.add(w*10**8+v*10**4+u)
            d.append(u)
edges2 = set()
d = deque([N-1])
visited2 = defaultdict(lambda: False)
while len(d):
    v = d.popleft()
    for u,w in edge2[v]:
        if visited2[w*10**8+u*10**4+v] == False:
            visited2[w*10**8+u*10**4+v] = True
            edges2.add(w*10**8+u*10**4+v)
            d.append(u)
new_edge = list(edges1&edges2)
d = [10**10]*N
d[0] = 0
n = 0
while True:
    n += 1
    update = False
    for e in new_edge:
        w = e//10**8
        v = e%10**8//10**4
        u = e%10**4
        if d[u]>d[v]+w:
            d[u] = d[v]+w
            update = True
    if update == False:
        break
    if n==N and update==True:
        print(-1)
        exit()
print(max(0,-d[-1]))

Measured memory_bytes: 54888
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<string>

using namespace std;

int main(){
  int n; cin >> n;
  vector<int> d;
  for(int i = 0; i < n ; i++){
    int t;
    cin >> t;
    d.push_back(t);
  }
  sort(d.begin(), d.end());
  cout << d[n/2] - d[n/2-1] << endl;
}


Measured memory_bytes: 892
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define all(x) (x).begin(), (x).end()
#define int long long
#define double long double
int gcd(int x, int y){
    if (y == 0)
        return x;
    x = x % y;
    gcd(y, x);
}
main()
{
	int n,k;
	cin>>n>>k;
	int count=0;
	int count2=0;
	if(k%2==0){
		for(int i=1;i<=n;i++){
			if(i%k==k/2) count++;
		}
		for(int i=1;i<=n;i++){
			if(i%k==0) count2++;
		}
		cout<<count*count*count+count2*count2*count2<<endl;
	}else{
		for(int i=1;i<=n;i++){
			if(i%k==0) count++;
		}
		cout<<count*count*count<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
<?php

class Answer
{
    private $N;
    private $numbers;

    public function __construct()
    {
        $this->N = trim(fgets(STDIN));
        $number = trim(fgets(STDIN));
        $this->numbers = explode(' ', $number);
    }

    public function bubbleSort()
    {
        $numbers2 = $this->numbers;

        for ($i = 0; $i < $this->N; ++$i) {
            for ($j = $this->N - 1; $j > $i; --$j) {
                $value_j = $numbers2[$j];
                $value_j_1 = $numbers2[$j - 1];
                if ($value_j[1] < $value_j_1[1]) {
                    list($numbers2[$j], $numbers2[$j - 1]) = [$numbers2[$j - 1], $numbers2[$j]];
                }
            }
        }
        echo implode(' ', $numbers2)."\n";

        if (true === $this->isStable($this->numbers, $numbers2)) {
            echo 'Stable'."\n";
        } else {
            echo 'Not stable'."\n";
        }
    }

    public function selectionSort()
    {
        $numbers2 = $this->numbers;

        for ($i = 0; $i < $this->N; ++$i) {
            $minj = $i;
            for ($j = $i; $j < $this->N; ++$j) {
                $value_j = $numbers2[$j];
                $value_minj = $numbers2[$minj];
                if ($value_j[1] < $value_minj[1]) {
                    $minj = $j;
                }
            }
            list($numbers2[$i], $numbers2[$minj]) = [$numbers2[$minj], $numbers2[$i]];
        }
        echo implode(' ', $numbers2)."\n";

        if (true === $this->isStable($this->numbers, $numbers2)) {
            echo 'Stable'."\n";
        } else {
            echo 'Not stable'."\n";
        }
    }

    public function isStable($in, $out)
    {
        for ($i = 0; $i < $this->N; ++$i) {
            $value_i = $in[$i];
            for ($j = $i + 1; $j < $this->N; ++$j) {
                $value_j = $in[$j];
                for ($a = 0; $a < $this->N; ++$a) {
                    for ($b = $a + 1; $b < $this->N; ++$b) {
                        if ($value_i[1] === $value_j[1] and $in[$i] === $out[$b] and $in[$j] === $out[$a]) {
                            return false;
                        }
                    }
                }
            }
        }

        return true;
    }
}

$answer = new Answer();
$answer->bubbleSort();
$answer->selectionSort();



Measured memory_bytes: 9428
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: u64,
        mut a: [u64; n],
        q: u64,
    }

    let mut sum: u64 = 0;
    let mut a_counter: [u64; 100001] = [0; 100001];
    for i in 0..a.len() {
        sum += a[i as usize];
        a_counter[a[i as usize] as usize] += 1;
    }

    for _i in 0..q {
        input! {
            b: u64,
            c: u64,
        }
        // b != c
        if c > b {
            let d = c - b;
            sum += d * a_counter[b as usize];
        } else {
            let d = b - c;
            sum -= d * a_counter[b as usize];
        }

        a_counter[c as usize] += a_counter[b as usize];
        a_counter[b as usize] = 0;
        println!("{}", sum);
    }
}


Measured memory_bytes: 5220
PROGRAM popularVote
      IMPLICIT NONE
      integer(16) :: m,n
      integer(16) :: a(100)
      logical :: mask(100)
      real(16) :: th !threshold
      
      read*,n,m
      read*,a(1:n)
      
      th = real(sum(a(1:n))) / real( 4*m )
      
      mask = a>=th
      
      if( count(mask(1:n))>=m )then
        print*,'Yes'
      else
        print*,'No'
      end if
      
      
      
      
      END PROGRAM

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define gc getchar_unlocked
#define fo(i,n) for(i=0;i<n;i++)
#define Fo(i,k,n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define tr(it, a) for(auto it = a.begin(); it != a.end(); it++)
#define PI 3.1415926535897932384626
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define GET_BIT(n, i) (((n) & (1LL << ((i)-1))) >> ((i)-1)) // i start from 1
#define SET_BIT(n, i) ((n) | (1LL << ((i)-1)))
#define CLR_BIT(n, i) ((n) & ~(1LL << ((i)-1)))
typedef pair<int, int>  pii;
typedef pair<ll, ll>  pl;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pl>    vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;
void myInit();
int mpow(int base, int exp);
void ipgraph(int m);
void dfs(int u, int par);
const int MOD = 1000000007;
const int N = 3e5, M = N;
//=========TQR==============
vi g[N];

int main() {
	myInit();
	FIO;
	int n, i;
	cin >> n;
	vl a(n), pre(n);

	unsigned ll ans = 0;
	fo(i, n) {
		cin >> a[i];
		if (i == 0)
			pre[i] = a[i];
		else
			pre[i] = (pre[i - 1] + a[i]) % MOD;
	}
	Fo(i, 1, n) {
		ans = (ans + (a[i] * pre[i - 1]) % MOD) % MOD;
	}
	cout << ans << endl;
	return 0;
}

void myInit() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
}

int mpow(int base, int exp) {
	base %= MOD;
	int result = 1;
	while (exp > 0) {
		if (exp & 1) result = ((ll)result * base) % MOD;
		base = ((ll)base * base) % MOD;
		exp >>= 1;
	}
	return result;
}

void ipgraph(int n, int m) {
	int i, u, v;
	while (m--) {
		cin >> u >> v;
		g[u - 1].pb(v - 1);
		g[v - 1].pb(u - 1);
	}
}

void dfs(int u, int par) {
	for (int v : g[u]) {
		if (v == par) continue;
		dfs(v, u);
	}
}

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

using namespace std;

int main()
{
	int ar[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  	int k;
  	cin>>k;
  	cout<<ar[k-1]<<endl;


	return 0;
}

Measured memory_bytes: 256
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
template<typename T> ll min(ll a, const T&& b) { return a < b ? a : b; }
template<typename T> ll min(const T&& a, ll b) { return a < b ? a : b; }
template<typename T> ll max(ll a, const T&& b) { return a > b ? a : b; }
template<typename T> ll max(const T&& a, ll b) { return a > b ? a : b; }
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

void solve() {
  ll n, k; cin >> n >> k;
  if (k == 1) {
    cout << 0 << endl;
  }
  else {
    cout << n - k << endl;
  }
}


Measured memory_bytes: 764
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
	int A, B;
	cin >> A >> B;
	vector<string> ans(100, "");
	for(int i=0; i<50; ++i) ans[0] += "##";
	for(int i=1; i<50; ++i) ans[i]=ans[0];
	for(int i=0; i<50; ++i) ans[50] += "..";
	for(int i=51; i<100; ++i) ans[i]=ans[50];
	for(int i=0; i+1<A; ++i) ans[(i/50)*2][(i%50)*2]='.';
	for(int i=0; i+1<B; ++i) ans[51+(i/50)*2][(i%50)*2]='#';
	cout << 100 << ' ' << 100 << endl;
	for(int i=0; i<100; ++i) cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 256
from heapq import heappush, heappop, heapify, heapreplace
from collections import defaultdict


class Solution:
    def main(self):
        N, X = map(int, input().split())
        L = [0] + list(map(int, input().split()))
        cum = 0
        res = 0
        for i in range(len(L)):
            cum += L[i]
            if cum <= X:
                # print(cum)
                res += 1
            else:
                break

        print(res)

if __name__ == '__main__':
    Solution().main()

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

#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
#define INF 1000000000000
#define MOD 1000000007
#define MAX 2000000000
using ll = long long;
using Graph = vector<vector<ll>>;
using P = pair<int,int>;

//全点対間最短距離を求める問題なのでわーシャルフロイド法を使用する。
int main(){
  ll H,W; cin>>H>>W;
  vector<vector<ll>> dp(H*W,vector<ll>(H*W,INF));
  vector<string> S(H);
  rep(i,H)cin>>S.at(i);
  rep(i,H)for(ll j = 1; j < W; j++)if(S.at(i).at(j-1)=='.'&&S.at(i).at(j)=='.'){
    dp.at(i*W+j).at(i*W+j-1)=1;
    dp.at(i*W+j-1).at(i*W+j)=1;
  }
  rep(i,W)for(ll j = 1; j < H; j++)if(S.at(j-1).at(i)=='.'&&S.at(j).at(i)=='.'){
    dp.at((j-1)*W+i).at(j*W+i)=1;
    dp.at(j*W+i).at((j-1)*W+i)=1;
  }

  ll N = H*W;
  rep(i,N)dp.at(i).at(i)=0;
  rep(k,N){
    rep(i,N){
      rep(j,N){
        dp.at(i).at(j) = min(dp.at(i).at(j),dp.at(i).at(k)+dp.at(k).at(j));
      }
    }
  }
  ll res = 0;
  rep(i,N)rep(j,N){
    if(i!=j&&dp.at(i).at(j)!=INF)res=max(res,dp.at(i).at(j));
  }
  cout<<res<<endl;
  return 0;
}



Measured memory_bytes: 1664
def nibu_right(a,A): #a in A(sorted)
    if a<A[0]:return 0
    elif A[-1]<a:return len(A)
    else:
        mi = 0
        ma = len(A)-1
        while ma-mi>1:
            mid = (ma+mi)//2
            if a < A[mid]:
                ma = mid
            else:
                mi = mid
        if A[ma]==a:
            return ma+1
        else:
            return ma

def nibu_left(a,A): #a in A(sorted)
    if a<A[0]:return -1
    elif A[-1]<a:return len(A)-1
    else:
        mi = 0
        ma = len(A)-1
        while ma-mi>1:
            mid = (ma+mi+1)//2
            if a > A[mid]:
                mi = mid
            else:
                ma = mid
        if A[mi]==a:
            return mi-1
        else:
            return mi




n = int(input())
A = list(map(int,input().split()))
A.sort()
B = list(map(int,input().split()))
B.sort()
C = list(map(int,input().split()))
C.sort()

ans = 0
for i in range(n):
    ans += (nibu_left(B[i],A)+1) * (n-nibu_right(B[i],C))
print(ans)

Measured memory_bytes: 24180
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#pragma GCC optimize ("O3")
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define Would
#define you
#define please

const int M = 1e9;
const int cm = 1 << 17;
char cn[1 << 17], ct;
char* ci;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[1 << 21];
char* di;

int main() {
	di = dn;
	ci = cn + cm;
	int N = getint();
	int A[500001];
	*A = getint();
	int d[500000];
	rep(i, N) {
		*(d + i) = getint();
		int ab = abs(*(A + i) - *(d + i));
		if (*(A + i) < ab) *(A + i + 1) = *(A + i);
		else *(A + i + 1) = ab;
	}
	int B[500000];
	*(B + N - 1) = 1;
	for (int i = N - 1; i >= 1; i--) {
		if (*(B + i) >= M || *(B + i) * 2 <= *(d + i)) *(B + i - 1) = *(B + i);
		else *(B + i - 1) = *(B + i) + *(d + i);
	}
	int Q = getint();
	char n[3] = { 'N', 'O', '\n' };
	char y[4] = { 'Y', 'E', 'S', '\n' };
	rep(i, Q) {
		int q = getint();
		q--;
		if (*(A + q) < *(B + q)) {
			memcpy(di, n, 3);
			di += 3;
		}
		else {
			memcpy(di, y, 4);
			di += 4;
		}
	}

	fwrite(dn, di - dn, 1, stdout);

	Would you please return 0;
}

Measured memory_bytes: 9600
#include <cstdio>
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
#include <iterator>

using lli=long long;

int main(){
  int N;
  std::cin >> N;

  std::vector<std::tuple<lli, lli>> Di_arr(N);
  for(int i = 0; i < N; i++){
    lli tmp;
    std::cin >> tmp;
    Di_arr[i] = std::make_tuple(tmp, i+1);
  }

  std::sort(Di_arr.begin(), Di_arr.end(), [](const std::tuple<lli, lli>& l, const std::tuple<lli, lli>& r){ return std::get<0>(l) > std::get<0>(r); });
  std::vector<lli> D_arr(N), re_arr(N);
  for(int i = 0; i < N; i++){
    D_arr[i] = std::get<0>(Di_arr[i]);
    re_arr[i] = std::get<1>(Di_arr[i]);
  }

  std::vector<std::tuple<lli, lli>> node_info(N, std::make_tuple(1, 0));

  bool fail=false;
  std::vector<std::tuple<lli, lli>> edges;
  for(int i = 0; i < N-1; i++){
    lli nnodes, length;
    std::tie(nnodes, length) = node_info[i];
    lli parent_d = D_arr[i]-(N-nnodes)+nnodes;
    auto parent_it = std::lower_bound(D_arr.rbegin(), D_arr.rend(), parent_d);
    if(parent_it == D_arr.rend() || *parent_it != parent_d){
      fail=true;
      break;
    }
    lli parent = std::distance(D_arr.begin(), parent_it.base()-1);
    edges.push_back(std::make_tuple(i, parent));
    std::get<0>(node_info[parent]) += nnodes;
    std::get<1>(node_info[parent]) += length+nnodes;
  }
  if(std::get<1>(node_info[N-1]) != D_arr[N-1]) fail=true;

  if(fail){
    std::cout << -1 << std::endl;
  }else{
    for(auto&& it: edges){
      std::cout << re_arr[std::get<0>(it)] << " " << re_arr[std::get<1>(it)] << "\n";
    }
  }

  return 0;
}



Measured memory_bytes: 7792
n, q = map(int, input().split())
tree = [list() for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    tree[a-1].append(b-1)
    tree[b-1].append(a-1)
c = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    c[p-1] += x

stack = [0]
j = [False] * n # すでに探索したか
while stack:
    node = stack.pop()
    j[node] = True
    for snode in tree[node]:
        if j[snode]:
            continue
        c[snode] += c[node]
        stack.append(snode)

print(*c)


Measured memory_bytes: 105600
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <string>
#include <queue>
#include <fstream>
#include <string>
#include <math.h>
#include <set>
#include <string>
#include <bitset>
#include <fstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
//typedef pair<ll, P> T;

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define revrep(i, n) for (ll i = (n) - 1; i >= 0; i--)
#define f first
#define s second
#define pb push_back

ll mod = 1000000007;
const ll INF = 100000000000010000;
//const ull B = 998244353;
//ll kai[3010];

//void pres(double A, ll x = 20) { printf("%.20f\n", x); }

vector<ll> dx = { 0, 1, 0, -1, 1, -1, 1, -1, 0};
vector<ll> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0};

void chmin(double& x, double y) {
	x = min(x, y);
}

void chmax(double& x, double y) {
	x = max(x, y);
}

ll pow_long(ll x, ll y) {
	ll res = 1;
	while (y > 0) {
		if (y % 2 == 1) res *= x;
		x *= x;
		y /= 2;
	}
	return res;
}

void test() {
	cout << "888888888888888888888888" << endl;
}

ll gcd(ll x, ll y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}

ll pow_mod(ll x, ll k) {
	x %= mod;
	ll res = 1;
	while (k > 0) {
		if (k % 2) {
			res *= x; res %= mod;
		}
		x *= x; x %= mod;
		k /= 2;
	}
	return res;
}

ll div_mod(ll x) {
	return pow_mod(x, mod - 2);
}

//コンビネーション
const int MAXcomb = 1000010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAXcomb; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = mod - inv[mod%i] * (mod / i) % mod;
		finv[i] = finv[i - 1] * inv[i] % mod;
	}
}
ll comb(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * finv[k] % mod * finv[n - k] % mod;
}

ll N, M;
ll u, v;
ll S, T;
vector<ll> E[100010];
ll len[100010][3];
priority_queue<P, vector<P>, greater<P>> que;

void solve() {
	cin >> N >> M;
	rep(i, M) {
		cin >> u >> v;
		E[u].pb(v);
	}
	cin >> S >> T;
	rep(i, N) rep(j, 3) len[i + 1][j] = INF;
	que.push(P(0, S));
	while(que.size()) {
		P p = que.top(); que.pop();
		if (len[p.s][p.f % 3] <= p.f) continue;
		len[p.s][p.f % 3] = p.f;
		for (ll e: E[p.s]) {
			if (len[e][(p.f + 1) % 3] == INF) que.push(P(p.f + 1, e));
		}
	}
	if (len[T][0] != INF) cout << len[T][0] / 3 << endl;
	else cout << -1 << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll T = 1;
	//cin >> T;
	rep(i, T) solve();
}


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

typedef long long ll;
typedef pair<int, int> P;

int MOD=1e9+7;
ll INF=1e18;

int dx[]={1, -1, 0, 0};
int dy[]={0, 0, 1, -1};

int main(){
    int n; cin>>n; 
    map<int, int> cnt;
    for(int i=0; i<n; i++){
        int a; cin>>a;
        cnt[a]++;
    }

    int ans=0;
    for(auto itr=cnt.begin(); itr!=cnt.end(); itr++){
        if(itr->second % 2 == 1) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 4992