akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <bits/stdc++.h>
#define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
using namespace __gnu_pbds;

typedef tree<pair<long long int,long long int>,null_type,less<pair<long long int,long long int> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int h,w,k,black=0;
vector<vector<char> > a;

bool check(vector<int> row,vector<int> cols)
{
//    for(int i=0;i<row.size();i++)
//        cout<<row[i]<<" ";
//    cout<<endl;
//    for(int i=0;i<cols.size();i++)
//        cout<<cols[i]<<" ";
//    cout<<endl;
    set<pair<int,int> > s;
    for(int i=0;i<row.size();i++)
    {
        for(int j=0;j<w;j++)
        {
            if(a[row[i]][j] == '#')
                s.insert({row[i],j});
        }
    }
    for(int i=0;i<cols.size();i++)
    {
        for(int j=0;j<h;j++)
        {
            if(a[j][cols[i]] == '#')
                s.insert({j,cols[i]});
        }
    }
    if((black-(int)s.size()) == k)
        return 1;
    return 0;
}
int power(int base,int p)
{
    int ans=1;
    while(p)
    {
        if(p&1)
            ans*=base,p--;
        else
            base*=base,p/=2;
    }
    return ans;
}
void go()
{
    int x=6,ans=0;
    cin>>h>>w>>k;
    a.resize(h,vector<char>(w));
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            cin>>a[i][j];
            if(a[i][j] == '#')
                black++;
        }
    }
    for(int i=0;i<power(2,h);i++)
    {
        vector<int> rows;
        int temp=i,cnt=0;
        while(temp)
        {
            if(temp&1)
                rows.push_back(cnt);
            temp=temp>>1,cnt++;
        }
        x=6;
        for(int j=0;j<power(2,w);j++)
        {
            int temp=j,cnt=0;
            vector<int> cols;
            while(temp)
            {
                if(temp&1)
                    cols.push_back(cnt);
                temp=temp>>1,cnt++;
            }
            if(check(rows,cols))
                ans++;
        }
    }
    cout<<ans;
}
int main()
{
    //FIO;
//    int t;
//    cin>>t;
//    while(t--)
        go();
    return 0;
}


Measured memory_bytes: 3588
[n,k]=list(map(int,input().split()))
ablist=[]
for i in range(n):
    ablist.append(list(map(int,input().split())))
ablist=sorted(ablist,key=lambda x:x[0])
bwa=[0]
for i in range(n):
    bwa.append(bwa[-1]+ablist[i][1])
ind=1
while True:
    if bwa[ind-1]<k<=bwa[ind]:
        break
    ind+=1
print(ablist[ind-1][0])

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

int gcd(int a, int b){
  if(a>b) return gcd(b,a);
  else if(b%a == 0) return a;
  else{
    return gcd(b%a,a);
  }
}

int main(){
  int N;
  cin>>N;
  int a,b;
  cin>>a;
  for(int i=0;i<N;i++){
    b=a;
    cin>>a;
    a=gcd(a,b);
  }
  cout<<a<<endl;
}

Measured memory_bytes: 256
def binary_search_loop(data, target):
    imin = 0
    imax = len(data) - 1
    while imin <= imax:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return imid
        elif target < data[imid]:
            imax = imid - 1
        else:
            imin = imid + 1
    return False
n = int(input())
lista = list(map(int, input().split()))
listb = sorted(lista)
for i in range(n):
    if binary_search_loop(listb, lista[i]) + 1 <= (n // 2):
        print(listb[(n // 2)])
    else:
        print(listb[(n // 2) - 1])

Measured memory_bytes: 95956
N = int(input())
S = []
for i in range(N):
  S.append(str(input()))
           

print('AC x %d' % S.count('AC'))
print('WA x %d' % S.count('WA'))
print('TLE x %d' % S.count('TLE'))
print('RE x %d' % S.count('RE'))
  

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

#define ln                '\n'
#define all(dat)           dat.begin(), dat.end()
#define loop(i, to)        for (int i = 0; i < to; ++i)
#define cont(i, to)        for (int i = 1; i <= to; ++i)
#define circ(i, fm, to)    for (int i = fm; i <= to; ++i)
#define foreach(i, dat)    for (__typeof(dat.begin()) i = dat.begin(); i != dat.end(); ++i)

typedef long long          num;

using namespace std;

int n;
string s, t;

int main() {
    cin >> n >> s >> t;
    loop (i, n) {
        cout << s[i] << t[i];
    }
    cout << ln;
}

Measured memory_bytes: 256
<?php
list($n) = ints();
for ($i = 0; $i < $n; ++$i) list($a[], $b[]) = ints();
sort($a);
sort($b);
if ($n % 2) { // nが奇数
    $M = $b[intdiv($n, 2)]; // bの中央値
    $m = $a[intdiv($n, 2)]; // aの中央値
    echo $M - $m + 1; // m~Mで１刻み
} else { // nが偶数
    $M = ($b[intdiv($n, 2) - 1] + $b[intdiv($n, 2)]) / 2; // bの中央値
    $m = ($a[intdiv($n, 2) - 1] + $a[intdiv($n, 2)]) / 2; // aの中央値
    echo ($M - $m) * 2 + 1; // m~Mで0.5刻み
}
function ints()
{
    return array_map('intval', explode(' ', trim(fgets(STDIN))));
}


Measured memory_bytes: 30972
#include <bits/stdc++.h> 
using namespace std; 
int n , m , in[200004] , dp[200004];
vector<int>vi[200004];
bool vis[200004];
int dfs(int node){
	if(vis[node])return dp[node];
	int mxn = 0;
	vis[node] = true;
	for(auto it : vi[node]){
		mxn = max(dfs(it) + 1 , mxn);
	}
	return dp[node] = mxn;
}
int main(){
	cin>>n>>m;
	for(int i = 0 , u , v; i < m ; i++){
		scanf("%d%d" , &u , &v);
		vi[u].push_back(v);
		in[v]++;
	}
	for(int i = 1 ;i <= n ; i++){
		if(!vis[i] && in[i] == 0)
			dfs(i);
	}
	int ans = 0;
	for(int i = 1 ; i <= n ; i++){
		ans = max(ans , dp[i]);
	}
	cout<<ans;
	return 0;
}  


Measured memory_bytes: 14080
N = int(input())
L = sorted([int(x) for x in input().split(' ')], reverse=True)

count = 0
while len(L) > 2:
    a = L.pop(0)
    ic = len(L) - 1
    for ib, b in enumerate(L):
        diff = a - b
        while L[ic] <= diff and ib < ic:
            ic -= 1
        count += ic - ib
        if ib >= ic:
            break

print(count)

Measured memory_bytes: 3188
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
Node root;
Node treeMinimum(Node x){
  while(x->left != NIL)   
    x = x->left;
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL)
    x = x->right;
  return x;
}

Node treeSearch(Node u, int k){
  while(u != NIL && k != u->key)
    {
      if(k < u->key) u = u->left;
      else u = u->right;
    }
  return u;
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);
  
  if(y->left != NIL)
    {
      x = y->left;
    }else{
    x = y->right;
  }
  
  if(x != NIL) x->parent = y->parent;
  
  if(y->parent == NIL)
    {
      root = x;
    }else{
    if(y == y->parent->left)
      {
	y->parent->left = x;
      }else{
      y->parent->right = x;
    }
  
    if(y != z)
      {
	z->key = y->key;
      }
    free(y);
  }
}

  void insert(int k)
  {
    Node y = NIL;
    Node x = root;
    Node z;
    z = malloc(sizeof(struct node));
    z->key = k;
    z->left = NIL;
    z->right = NIL;
    while(x != NIL){
      y = x;
      if(z->key < x->key){
	x = x->left;
      }else{
	x = x->right;
      }
      z->parent = y;
    }
    if(y == NIL)
      {
	root = z;
      }
    else if(z->key < y->key)
      {
	y->left = z;
      }
    else
      {
	y->right = z;
      }
  }

  void inorder(Node u)
  {
    if(u == NIL)
      {
	return;
      }
    inorder(u->left);
    printf(" %d", u->key);
    inorder(u->right);
  }
  void preorder(Node u)
  {
    if(u == NIL)
      {
	return;
      }
    printf(" %d", u->key);
    preorder(u->left);
    preorder(u->right);
  }


  int main()
  {
    int n, i, x;
    char com[20];
    scanf("%d", &n);

    for ( i = 0; i < n; i++ )
      {
	scanf("%s", com);
	if ( com[0] == 'f' )
	  {
	    scanf("%d", &x);
	    Node t = treeSearch(root, x);
	    if ( t != NIL ) printf("yes\n");
	    else printf("no\n");
	  }
	else if ( com[0] == 'i' )
	  {
	    scanf("%d", &x);
	    insert(x);
	  }
	else if ( com[0] == 'p' )
	  {
	    inorder(root);
	    printf("\n");
	    preorder(root);
	    printf("\n");
	  }
	else if ( com[0] == 'd' )
	  {
	    scanf("%d", &x);
	    treeDelete(treeSearch(root, x));
	  }
      }
    return 0;
  }
  



Measured memory_bytes: 20448
#include <bits/stdc++.h>
using namespace std;
int main()
{
  vector<int>a(2);
  cin>>a[0]>>a[1];
  int i=0,ans=0;
  while(i<2)
  {
    if(a[i]==1)ans+=300000;
    if(a[i]==2)ans+=200000;
    if(a[i]==3)ans+=100000;
    i++;
  }
  if(a[0]==1 && a[1]==1)ans+=400000;
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <numeric>

int main()
{
	long long n, p;

	std::cin >> n >> p;

	std::vector<long long> v(n);

	for (size_t i = 0; i < n; i++)
	{
		std::cin >> v[i];
		v[i] %= 2;
	}

	std::vector<std::vector<long long> > dp(n + 1, std::vector<long long>(2, 0));

	dp[0][0] = 1;

	for (size_t i = 1; i <= n; i++)
	{
		if (v[i - 1] == 0) {
			dp[i][0] = dp[i - 1][0] * 2;
			dp[i][1] = dp[i - 1][1] * 2;
		}
		else {
			dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
			dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
		}
	}

	std::cout << dp[n][p] << std::endl;

	return 0;
}


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

const long long INF = 1LL << 60;

int main() {
  int n,mins=100000000,ans;
   cin >> n;
  int x[n+10];
  rep(i,n){
    cin >> x[i];
  }
  
  int str=0;
  REP(i,100){
  	rep(j,n){
      str+=(x[j]-i)*(x[j]-i);
    }
    mins=min(mins,str);
    str=0;
  }
  
  cout << mins << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string.h>

using namespace std;
typedef long long int ll;

int main(){

    int N;
    cin >> N;
    string name[N];
    int q[5];
    memset(q, 0, sizeof(q));
    for(int i=0; i<N; i++){
        cin >> name[i];
        char first = name[i][0];
        if(first == 'M'){
            q[0] ++;
        }else if(first == 'A'){
            q[1] ++;
        }else if(first == 'R'){
            q[2] ++;
        }else if(first == 'C'){
            q[3] ++;
        }else if(first == 'H'){
            q[4] ++;
        }
    }

    ll total = 0;
    total = (ll)q[0] * q[1] * q[2] + (ll)q[0] * q[1] * q[3] + (ll)q[0] * q[1] * q[4] + (ll)q[0] * q[2] * q[3] + (ll)q[0] * q[2] * q[4] + (ll)q[0] * q[3] * q[4] + (ll)q[1] * q[2] * q[3] + (ll)q[1] * q[2] * q[4] + (ll)q[1] * q[3] * q[4] + (ll)q[2] * q[3] * q[4];
    

    cout << total << endl;

    return 0;
}

Measured memory_bytes: 6144
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
using ll = long long;
using graph = std::vector<std::vector<ll>>;

using namespace std;
graph G(100005);
bool seen[100005];

bool solve(int current){
    if(seen[current]) return true;
    seen[current] = true;
    for(int i = 0;i < G[current].size(); i++){
        solve(G[current][i]);
    }
}
int main() {
    ll N,M;
    cin >> N >> M;

    for(int i = 0; i < 100005; i++){
        G[i] = vector<ll>(0);
        seen[i] = false;
    }
    for(int i = 0; i < M; i++){
        ll X,Y,Z;
        cin >> X >> Y >> Z;
        X--;Y--;
        G[X].push_back(Y);
        G[Y].push_back(X);
    }
    ll count = 0;
    for(int i = 0; i < N; i++){
        if(!solve(i)){
            count++;
        }
    }
    cout << count << endl;


}


Measured memory_bytes: 8960
#include <stdio.h>

typedef struct _XY{
	int x;
	int y;
} XY;

int main(){
	int n;
	int i0;
	int i,j,k,l;
	int x,y;
	XY P[3001];
	int judR;
	int judLen;
	int Area2,Area2Max;
	int trgtX,trgtY;
	int trgtX2,trgtY2;
	int jud1,jud2;
	
	while(1){
		scanf("%d\n",&n);
		if(n==0)break;
		Area2Max=0;
		for(i0=0;i0<n;i0++){
			scanf("%d %d\n",&x,&y);
			P[i0].x=x;P[i0].y=y;
		}

		for(i=0;i<n;i++){
			for(j=i+1;j<n;j++){
				Area2=(P[i].x-P[j].x)*(P[i].x-P[j].x) + (P[i].y-P[j].y)*(P[i].y-P[j].y);
				
				if(Area2%2==0 && Area2/2 >Area2Max){
					trgtX=(P[i].x+P[j].x)+(P[j].y-P[i].y);
					trgtY=(P[i].y+P[j].y)+(-P[j].x+P[i].x);
					trgtX2=(P[i].x+P[j].x)-(P[j].y-P[i].y);
					trgtY2=(P[i].y+P[j].y)-(-P[j].x+P[i].x);
					if(trgtX2%2==0 && trgtY2%2==0 && trgtX2<10002 && trgtY2<10002 && trgtX2>0 && trgtY2>0){
					if(trgtX%2==0 && trgtY%2==0 && trgtX<10002 && trgtY<10002 && trgtX>0 && trgtY>0){
						trgtX/=2;trgtY/=2;
						jud1=-1;
						jud2=-1;
						for(k=0;k<n;k++){
							if(P[k].x==trgtX && P[k].y==trgtY){
								jud1=k;
								break;
							}					
						}
						if(jud1!=-1){
								trgtX2/=2;trgtY2/=2;
								for(k=0;k<n;k++){
									if(P[k].x==trgtX2 && P[k].y==trgtY2){
										jud2=k;
										break;
									}					
								}
						}
						if(jud1!=-1 && jud2!=-1){
							Area2Max=Area2/2;
//printf("P[%d]=(%d,%d)\tP[%d]=(%d,%d)\tP[%d]=(%d,%d)\tP[%d]=(%d,%d)\n",i,P[i].x,P[i].y,j,P[j].x,P[j].y,jud1,P[jud1].x,P[jud1].y,jud2,P[jud2].x,P[jud2].y);
						}
					}
					}
				}
			}
		}
		printf("%d\n",Area2Max);
	}
	return 0;
}

Measured memory_bytes: 624
from collections import deque
 
 
# In[30]:
 
 
def main():
    H,W = map(int, input().split())
    ch,cw = map(int, input().split())
    dh,dw = map(int, input().split())
    s = ["#"*(W+4)]
    s.append("#"*(W+4))
    for i in range(H):
        s.append("##"+input()+"##")
    s.append("#"*(W+4))
    s.append("#"*(W+4))
    
    ans = [[-1]*(W+4) for _ in range(H+4)]
    for i in range(H+4):
        for j in range(W+4):
            if s[i][j] == "#":
                ans[i][j] = -2
    ch += 1; cw += 1
    dh += 1; dw += 1
    ans[ch][cw] = 0
    
    move = [[-1,0],[1,0],[0,-1],[0,1]]
    magic = [
        [-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],\
        [-1,-2],[-1,-1],[-1,0],[-1,1],[-1,2],\
        [0,-2],[0,-1],[0,0],[0,1],[0,2],\
        [1,-2],[1,-1],[1,0],[1,1],[1,2],\
        [2,-2],[2,-1],[2,0],[2,1],[2,2]
        ]
    
    mylist = deque([[ch,cw]])
    mylist2 = deque([])
    while len(mylist) > 0:
        x,y = mylist.popleft()
        mylist2.append([x,y])
        for p,q in move:
            v1,v2 = x+p,y+q
            if ans[v1][v2] == -1:
                mylist.append([v1,v2])
                ans[v1][v2] = ans[x][y]
        if len(mylist) == 0:
            while len(mylist2) > 0:
                x2,y2 = mylist2.popleft()
                for v1,v2 in magic:
                    i,j = x2+v1,y2+v2
                    if ans[i][j] == -1:
                        ans[i][j] = ans[x2][y2]+1
                        mylist.append([i,j])
    print(ans[dh][dw])
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 23536
#include <cstdio>
#include <iostream>
#include <stack>
using namespace std;

static const int MAX_NUM = 100;

void dsf_cal(int matrix[][MAX_NUM + 1], int state[], int time[][2], int index, int num)
{
    static int t = 1;
    stack<int> S;

    S.push(index);
    state[index]   = 1;
    time[index][0] = t;
    ++t;

    while (S.empty() != true) {
        int i;
        int target = S.top();
        for (i = 1; i < num + 1; i++) {
            if (matrix[target][i] == 1) {
                if (state[i] == 0) {
                    S.push(i);
                    state[i]   = 1;
                    time[i][0] = t;
                    ++t;
                    break;
                }
            }
        }
        if (i == num + 1) {
            time[target][1] = t;
            ++t;
            S.pop();
        }
    }

    return;
}

void DSF(int matrix[][MAX_NUM + 1], int num)
{
    int state[MAX_NUM+1]   = {0};
    int time[MAX_NUM+1][2] = {0};

    for (int i = 1; i < num+1; i++) {
        if (state[i] == 0) {
            dsf_cal(matrix, state, time, i, num);
        }
    }

    for (int i = 1; i < num+1; i++) {
        printf("%d %d %d\n", i, time[i][0], time[i][1]);
    }

    return;
}

int main(void)
{
    int num;
    int index, elemNum, tmp;
    int matrix[MAX_NUM + 1][MAX_NUM + 1] = {0};

    scanf("%d", &num);
    for (int i = 0; i < num; i++) {
        scanf("%d %d", &index, &elemNum);
        for (int j = 0; j < elemNum; j++) {
            scanf("%d", &tmp);
            matrix[index][tmp] = 1;
        }
    }

    DSF(matrix, num);

    return 0;
}

Measured memory_bytes: 3256
#include <iostream>
using namespace std;
int main(void)
{
    int a, b;
    cin >> a >> b;
    if (a >= 13)
    {
        cout << b << endl;
    }
    else if (a >= 6)
    {
        cout << b / 2 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define pb push_back
#define ub upper_bound
#define lb upper_bound
#define mp make_pair
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SORT(c) sort((c).begin(),(c).end())
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
 
typedef long long ll;
const ll INF = LLONG_MAX - 100;
const ll mod = 1e9 + 7;
const int MAX_N = 2e5 + 5;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
 
int fac[MAX_N], inv[MAX_N];
 
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return a * b / GCD(a, b);}
ll POW(ll a, ll b, bool usemod = true) {ll c = 1LL; while (b > 0) {if (b & 1LL) {if(!usemod)c*=a;else c = a * c%mod;}if (!usemod) a*=a;else a = a * a%mod; b >>= 1LL;}return c;}
void _nCr() {fac[0] = 1LL; for (int i = 1LL; i < MAX_N; i++) {fac[i] = fac[i - 1LL] * i%mod;}for (int i = 0; i < MAX_N; i++) {inv[i] = POW(fac[i], mod - 2);}}
ll nCr(ll n, ll r) {return (fac[n] * inv[r] % mod)*inv[n - r] % mod;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}

class Warshall_Floyd {
public:
	vector<vector<int>> d;
	int nodecnt = -1;

	Warshall_Floyd(int n) {
		d = vector<vector<int>>(n,vector<int>(n,INF));
		nodecnt = n;
	}

	void add(int s,int e,int cost) {
		d[s][e] = cost;
	}

	bool wf() {
		for (int k = 0;k < nodecnt;k++) {
			for (int i = 0;i < nodecnt;i++) {
				for (int j = 0;j < nodecnt;j++) {
					//k経由でi->j
					d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
				}
			}
		}
	}
};

bool ng[10];
bool check(int n) {
	int keta = 1;
	while (true) {
		if (pow(10,keta) > n) break;
		keta++;
	}
	REP (i,keta) {
		if (ng[n % 10]) {return false;}
		n /= 10;
	}
	return true;
}

bool solve() {
	int n,k; cin >> n >> k;
	REP (i,k) {int x;cin >> x; ng[x] = true;}
	int tmp = n;
	while (true) {
		if (check(tmp)) {cout << tmp << endl; return 0;}
		tmp++;
	}
	// cout << check(tmp) << endl;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft first
#define sd second
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

struct modint{
    ll a;
    const ll MOD=1e9+7;
    modint(ll a_=0){
        a=((a_%MOD)+MOD)%MOD;
    }
    modint inv()const{
        ll n=1,m=MOD-2,A=a;
        while(m){
            if(m&1)(n*=A)%=MOD;
            (A*=A)%=MOD;
            m>>=1;
        }
        modint y(n);
        return y;
    }
    bool operator==(const modint& x){
        return a==x.a;
    }
    bool operator!=(const modint& x){
        return a!=x.a;
    }
    modint& operator=(const modint& x){
        a=x.a;
        return *this;
    }
    modint operator+(const modint& x){
        modint y(a+x.a);
        return y;
    }
    modint operator-(const modint& x){
        modint y(a-x.a);
        return y;
    }
    modint operator*(const modint& x){
        modint y(a*x.a);
        return y;
    }
    modint operator/(const modint& x){
        return *this * x.inv();
    }
    modint& operator+=(const modint& x){
        *this=*this+x;
        return *this;
    }
    modint& operator-=(const modint& x){
        *this=*this-x;
        return *this;
    }
    modint& operator*=(const modint& x){
        *this=*this*x;
        return *this;
    }
    modint& operator/=(const modint& x){
        *this=*this/x;
        return *this;
    }
};
istream& operator>>(istream &in,modint& x){
    ll a_;
    in>>a_;
    modint y(a_);
    x=y;
    return in;
}
ostream& operator<<(ostream &out,const modint& x){
    out<<x.a;
    return out;
}
modint pwr(ll a,ll b){
    modint n(1),A(a);
    while(b){
        if(b&1) n*=A;
        A*=A;
        b>>=1;
    }
    return n;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m,a;
    cin>>n>>m;
    vector<bool> v(n+1);
    fr(i,m){
        cin>>a;
        v[a]=1;
    }
    vector<modint> dp(n+1);
    dp[0]=1;
    Fr(i,n){
        if(v[i]) continue;
        dp[i]+=dp[i-1];
        if(i>1) dp[i]+=dp[i-2];
    }
    cout<<dp[n]<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;
int main()
{
    string s, t;
    cin >> s >> t;

    sort(all(s));
    sort(all(t));
    reverse(all(t));

    int sl = (int)s.size();
    int tl = (int)t.size();

    bool flag = true;
    rep(i, min(sl, tl)) {
        if (s[i] < t[i]) {
            cout << "Yes" << endl;
            return 0;
        }
        else if (s[i] > t[i]) {
            flag = false;
            break;
        }
    }

    if (flag) {
        if (sl < tl) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long ll;
#define endl '\n'

void solve() {
    ll n, k;
    cin >> n >> k;

    vector<ll> arr(n);
    for (auto &a: arr) {
        cin >> a;
    }
 
    vector<int> next(n, -1);
    int cur = 0;

    vector<int> steps;
    while (next[cur] == -1) {
        // cout << cur << " ";
        next[cur] = arr[cur] - 1;
        cur = next[cur];
        steps.push_back(cur);
    }
    int cycle = cur;

    int len = 1;
    cur = next[cycle];
    while (cur != cycle) {
        cur = next[cur];
        ++len;
    }
    // cout << '\n' << len << endl;

    int done = steps.size() - len;
    int rem = (k - done) % len;

    if (k <= steps.size()) {
        cout << 1 + steps[k - 1] << endl;
    } else {
        cur = cycle;
        // cout << rem << endl;
        while (rem) {
            cur = next[cur];
            --rem;
        }
        cout << 1 + cur << endl;
    }
}

int main() {
    FAST_IO;

    int t;
    // cin >> t;
    t = 1;

    while (t--) {
        solve();
    }
    
    return 0;
}

Measured memory_bytes: 6584
# AOJ 1160: How Many Islands?
# Python3 2018.7.15 bal4u

# UNION-FIND library
class UnionSet:
	def __init__(self, nmax):
		self.size = [1]*nmax
		self.id = [i for i in range(nmax+1)]
	def root(self, i):
		while i != self.id[i]:
			self.id[i] = self.id[self.id[i]]
			i = self.id[i]
		return i
	def connected(self, p, q): return self.root(p) == self.root(q)
	def unite(self, p, q):
		i, j = self.root(p), self.root(q)
		if i == j: return
		if self.size[i] < self.size[j]:
			self.id[i] = j
			self.size[j] += self.size[i]
		else:
			self.id[j] = i
			self.size[i] += self.size[j]
# UNION-FIND library

def id(r, c):
	global w
	return r*w+c

mv = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]

while True:
	w, h = map(int, input().split())
	if w == 0: break
	arr = [[] for r in range(h)]
	u = UnionSet(w*h)
	for r in range(h): arr[r] = list(map(int, input().split()))
	for r in range(h):
		for c in range(w):
			if not arr[r][c]: continue
			for i in range(8):
				r2, c2 = r + mv[i][0], c + mv[i][1]
				if r2 < 0 or r2 >= h or c2 < 0 or c2 >= w or not arr[r2][c2]: continue
				u.unite(id(r, c), id(r2, c2))
	ans = 0
	for r in range(h):
		for c in range(w):
			if arr[r][c] and u.root(id(r, c)) == id(r, c): ans += 1
	print(ans)



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

using namespace std;

class Solution {
public:
	void solve() {
		int n, m, l, k;
		cin >> n >> m >> l >> k;
		while (m <= n) {
			m <<= 1;
			k--;
		}
		while (l <= m) {
			l <<= 1;
			k--;
		}
		if (k < 0)
			cout << "No\n";
		else
			cout << "Yes\n";
		return;
	};
};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	Solution solution;
	solution.solve();
	return 0;
}

Measured memory_bytes: 3636
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        n: u64,
        k: u64,
    }
    println!("{}", if (n - 1) >= (k - 1) * 2 { "YES" } else { "NO" })
}


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

#define int long long

using namespace std;



int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;

    vector<bool> vect;

    for(int i = 0 ; i < N ; i++)
    {
    	int a, b;
    	cin >> a >> b;
    	vect.push_back(a == b);
    }

    bool flag = false;

    for(int i = 0 ; i < N-2 ; i++)
    {
    	if(vect[i] && vect[i+1] && vect[i+2])flag = true;
    }

    if(flag)cout << "Yes" << '\n';
    else cout << "No" << '\n';

    return 0;
}

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

int f(int x){
  int ret=0;
  while(x>0){
    ret +=x%10;
    x /=10;
  }
  return ret;
  
}

int main(){
  int n; cin>>n;
  cout<<(n%f(n)? "No":"Yes")<<endl;
}

Measured memory_bytes: 3632
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<cmath>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<stdio.h>
#include<queue>
using namespace std;
int main()
{
  int x,t;
  cin>>x>>t;
  int ans=max(x-t,0);
  cout<<ans<<endl;
  system("pause");
  return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
using namespace std;
typedef long long Long;
typedef vector<int> VI;
typedef vector<VI> VVI;

long long go(int X, int Y, VI V) {
	int N = V.size();
	int DC = N-1;
	long long t = 0;
	for (int i = 0; i < X; ++i) {
		if (DC >= 2 && DC-2 >= X-i-1) {
			t -= 2 * V[i];
			DC -= 2;
		} else {
			t -= V[i];
			DC -= 1;
		}
	}
	DC = N - 1;
	reverse(V.begin(), V.end());
	for (int i = 0; i < Y; ++i) {
		if (DC >= 2 && DC-2 >= Y-i-1) {
			t += 2 * V[i];
			DC -= 2;
		} else {
			t += V[i];
			DC -= 1;
		}
	}
	return t;
}

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

	VI V(N);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &V[i]);
	}
	sort(V.begin(), V.end());

	cout << max(go(N/2, N - N/2, V), go((N+1)/2, N - (N+1)/2, V)) << endl;

	return 0;
}

Measured memory_bytes: 1408
#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;

int a[205];

int work(int x){
	int ok=0;
	while(x%2==0){
		x/=2;
		//if(x%2!=0)return ok;
		ok++;
	}
	return ok;
}

int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	int x=0,ans=1<<30;
	for(int i=1;i<=n;i++){
		if(a[i]%2==0)x++;
	}
	if(x!=n){
		puts("0");
		return 0;
	}
	int sum=0;
	for(int i=1;i<=n;i++){
		sum=work(a[i]);
		//cout<<sum<<endl;
		ans=min(ans,sum);
	}
	/*while(x==n){
		x=0;
		for(int i=1;i<=n;i++){
			if(a[i]%2==0)x++;
		}
		if(x!=n)break;
		for(int i=1;i<=n;i++){
			a[i]/=2;
		}
		ans++;
	}*/
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define print(ele) cout << (ele) << endl
#define print10(ele) cout << fixed << setprecision(10) << (ele) << endl

using namespace std;
typedef long long ll;
typedef vector<int> ivec;
typedef vector<string> svec;
typedef vector<ll> lvec;

const int mod = 1e9 + 7;
const ll INF = 1000000000000000000LL;

int main() {
  int A, B, M;
  cin >> A >> B >> M;
  ivec a(A);
  int am = 1e6;
  REP(i, A) {
    int tmp;
    cin >> tmp;
    am = min(am, tmp);
    a[i] = tmp;
  }
  ivec b(B);
  int bm = 1e6;
  REP(i, B) {
    int tmp;
    cin >> tmp;
    bm = min(bm, tmp);
    b[i] = tmp;
  }
  int ans = 1e8;
  REP(i, M) {
    int x, y, c;
    cin >> x >> y >> c;
    x--;
    y--;
    ans = min(ans, a[x] + b[y] - c);
  }
  ans = min(am + bm, ans);
  print(ans);
  return 0;
}

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

int main(){
    int N; cin >> N;
    string S; cin >> S;
    
    if(N%2==1){
        cout << "No";
        return 0;
    }
    
    for (int i=0; i<=N/2-1; i++){
        if(S[i]!=S[N/2+i]){
            cout << "No";
            return 0;
        }
    }
    cout << "Yes";
    
}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sun May 31 15:56:57 JST 2020
 **/

signed main() {
    Int n;
    std::cin >> n;
    std::vector<std::tuple<Int, Int, char, Int, std::string>> a(n);
    for (auto& x : a) {
        std::cin >> std::get<0>(x) >> std::get<1>(x) >> std::get<2>(x) >> std::get<3>(x) >> std::get<4>(x);
    }
    std::sort(a.begin(), a.end());
    for (auto& x : a) {
        std::cout << std::get<0>(x) << " " << std::get<1>(x) << " " << std::get<2>(x) << " " << std::get<3>(x) << " "
                  << std::get<4>(x) << "\n";
    }
}



Measured memory_bytes: 11928
#include<iostream>
using namespace std;

const int MAX=100;
int INFTY=1<<30;
int WHITE=0;
int GRAY=1;
int BLACK=2;

int n,m[MAX][MAX];

void prim()
{
	int u,minv;
	int d[MAX],p[MAX],color[MAX];
	for(int i=0;i<n;i++){
		d[i]=INFTY;
		p[i]=-1;
		color[i]=WHITE;
	}
	d[0]=0;
	while(1)
	{
		minv=INFTY;
		u=-1;
		for(int i=0;i<n;i++)
			if(minv>d[i]&&color[i]!=BLACK){
				u=i;
				minv=d[i];
			}
			if(u==-1) break;
			color[u]=BLACK;
			for(int v=0;v<n;v++)
			if(color[v]!=BLACK&&m[u][v]!=INFTY)
			if(d[v]>m[u][v]){
				p[v]=u;
				d[v]=m[u][v];
				color[v]=GRAY;
			}
	}
	int sum=0;
	for(int i=0;i<n;i++)
	if(p[i]!=-i) sum+=m[i][p[i]];
	cout<<sum<<endl;
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			int e;
			cin>>e;
			m[i][j]=(e==-1)? INFTY:e;
		}
	}
	prim();
	return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <algorithm>
#include <cmath>
#include <stack>
#include <set>
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()

vector<vector<int>> vv;

void ink(int x, int y) {
    if (x >= 0 && x < 10 && y >= 0 && y < 10) {
        vv[x][y]++;
    }
}

void big(int x, int y) {
    ink(x-2,y);
    ink(x-1,y);
    ink(x,y);
    ink(x+1,y);
    ink(x+2,y);
    ink(x-1,y-1);
    ink(x,y-1);
    ink(x+1,y-1);
    ink(x-1,y+1);
    ink(x,y+1);
    ink(x+1,y+1);
    ink(x,y-2);
    ink(x,y+2);
}

void mid(int x, int y) {
    ink(x-1,y);
    ink(x,y);
    ink(x+1,y);
    ink(x-1,y-1);
    ink(x,y-1);
    ink(x+1,y-1);
    ink(x-1,y+1);
    ink(x,y+1);
    ink(x+1,y+1);
}

void small(int x, int y) {
    ink(x-1,y);
    ink(x,y);
    ink(x+1,y);
    ink(x,y-1);
    ink(x,y+1);
}

int countBlank() {
    int cnt = 0;
    REP(i,10) REP(j,10) if (vv[i][j] == 0) cnt++;
    return cnt;
}

int getThickest() {
    int t = 0;
    REP(i,10) REP(j,10) if (vv[i][j] > t) t = vv[i][j];
    return t;
}

int main() {
    REP(i,10) {
        vector<int> v(10,0);
        vv.push_back(v);
    }
    
    int x, y, s;
    string t;
    while(cin >> t) {
        x = t[0] - '0';
        y = t[2] - '0';
        s = t[4] - '0';
        switch (s) {
            case 1:
                small(x,y);
                break;
            case 2:
                mid(x,y);
                break;
            case 3:
                big(x,y);
                break;
                
            default:
                break;
        }
    }
    
    cout << countBlank() << endl << getThickest() << endl;
    
    return 0;
}

Measured memory_bytes: 3148
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007
using namespace std;

int main(void){
	int N,M;
	cin>>N>>M;
	ll A[N];
	pair<ll,ll> B[M];
	rep(i,N)cin>>A[i];
	rep(i,M)cin>>B[i].second>>B[i].first;
	sort(A,A+N);
	sort(B,B+M);

	//rep(i,N)cout<<i<<":"<<A[i]<<"|";
	//cout<<endl;
	//rep(i,M)cout<<"b:"<<B[i].first<<"c:"<<B[i].second<<endl;
	

	int id=M-1;
	ll ans=0;
	rep(i,N){
		if(A[i]<B[id].first && id>-1){
			ans+=B[id].first;
			B[id].second--;
			if(B[id].second==0)id--;
		}
		else ans+=A[i];
		//cout<<i<<":"<<ans<<endl;
	}
	cout<<ans<<endl;
	return 0;
}


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

using namespace std;

int main(){
	//~ freopen("input.txt", "r", stdin);
	//~ freopen("output.txt", "w", stdout);
	int n;
	scanf("%d", &n);
	map <long long, long long> mp;
	long long ans = 0;
	for (int i = 0; i < n; i++){
		long long x;
		scanf("%lld", &x);
		ans += x;
		mp[x]++;
	}
	int q;
	scanf("%d", &q);
	while (q--){
		long long x, y;
		scanf("%lld %lld", &x, &y);
		int c = mp[x];
		ans -= x * 1LL * c;
		ans += y * 1LL * c;
		mp[y] += c;
		mp[x] = 0;
		printf("%lld\n", ans);
	}
	return 0;
}


Measured memory_bytes: 9548
# -*- coding: utf-8 -*-

class RingBuffer(list):
    def __init__(self, MAX):
        list.__init__(self)
        self.head = 0
        self.tail = 0
        self.MAX = MAX
        self[:] = [None]*MAX

    def isEmpty(self):
        return self.head == self.tail
    
    def enque(self,x):
        self[self.tail] = x
        if self.tail + 1 == self.MAX:
            self.tail = 0
        else:
            self.tail += 1

    def deque(self):
        x = self[self.head]
        if self.head + 1 == self.MAX:
            self.head = 0
        else:
            self.head += 1
        return x



if __name__ == '__main__':

    n, q = [int(c) for c in input().split(" ")]
    P = RingBuffer(n+1)
    
    for i in range(n):
        P_name, P_time = input().split(" ")
        P.enque([P_name, int(P_time)])

    time = 0
    while not P.isEmpty():
        P_name, P_time = P.deque()
        
        if P_time > q:
            time = time + q
            P_time = P_time - q
            P.enque([P_name, P_time])
        else:
            time = time + P_time
            print(P_name, time)




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

#define REP(i, n) for(int i = 0; i < n; i++)
using namespace std;

int main()
{   
    string s;
    cin >> s;

    int cnt = 0, cnt_tmp = 0;
    REP(i, s.size()) {
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T') {
            cnt_tmp++;
            cnt = max(cnt, cnt_tmp);
        }

        else
            cnt_tmp = 0;
        
    }
    cout << cnt << endl;

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
 
int main() {
  int N;
  cin >> N;
  long long A[N+10],S[N+10],count=1,ans=0;
  S[0]=0;
  for(int i=1; i<=N; i++) cin >> A[i];
   for(int i=1; i<N+1; i++){
    S[i]=S[i-1]+A[i];
  }  sort(S,S+N+1);
  long long temp=S[0];
  for(int i=1; i<=N; i++){
    if(temp==S[i]){
      ans+=count;
      count+=1;
    }else{
      temp=S[i];
      count=1;
    }
  }
 cout << ans << endl;
  }

Measured memory_bytes: 3328
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
int que[1000000][3];
char str[1000][1001],flg[1000][1000]; 
int main(void){
	int i,j,k;
	int x,y,xx,yy,h,w,n,tai,p1,p2;
	int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
	int min,max=1000000;
	cin>>h>>w>>n;
	for(i=0;i<=h;i++){
		for(j=0;j<=w;j++) flg[i][j]=1;
	}
	for(i=0;i<h;i++) cin>>str[i];
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(str[i][j]=='S'){
				que[0][0]=i; que[0][1]=j; que[0][2]=0;
				flg[i][j]==0;
			}
		}	
	}
	tai=1; p1=0; p2=0;
	for(i=1;i<=n;i++){
		//cout<<i<<endl;
		if(p2>max) break;
		while(1){
			y=que[p1][0]; x=que[p1][1];
			if(str[y][x]-'0'==tai){
				tai++;
		//		printf("aaaaaaaa\n");
				for(j=0;j<h;j++){
					for(k=0;k<w;k++) flg[j][k]=1;
				}
				flg[y][x]==0;
				que[0][0]=y; que[0][1]=x; que[0][2]=que[p1][2];
				p1=0; p2=0;
				break;
			}
			for(j=0;j<4;j++){
				yy=y+dy[j]; xx=x+dx[j];
				if(yy>=0&&xx>=0&&yy<h&&xx<w&&str[yy][xx]!='X'&&flg[yy][xx]!=0){
					p2++;
					que[p2][0]=yy; que[p2][1]=xx; que[p2][2]=que[p1][2]+1;
					flg[yy][xx]=0;
//					printf("yy=%d xx=%d\n",yy,xx);
				}
			}
			p1++;
			//printf("%d %d\n",p1,p2);
		}
		min=que[p1][2];
	}
	cout<<min<<endl;
	return 0;
}

Measured memory_bytes: 9992
def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    a.sort()
    
    sm = 0
    ans = 0
    for i in range(n-1):
        sm += a[i]
        if sm * 2 >= a[i+1]:
            ans += 1
        else:
            ans = 0
    print(ans+ 1)

solve()

"""
5 6
4 7 9 3 4
"""

Measured memory_bytes: 20188
D, G = gets.split.map(&:to_i)
ps, cs = [], []
(1..D).each do |i|
    ps[i], cs[i] = gets.split.map(&:to_i)
end

SUM = ps[1, D].inject(:+)
dp = Array.new(D+1){Array.new(SUM+1, 0)}
(1..D).each do |i|
    (0..SUM).each do |j|
        (0..ps[i]).each do |k|
            next if j < k
            result = dp[i-1][j-k] + 100*i*k
            result += cs[i] if k == ps[i]
            dp[i][j] = result if dp[i][j] < result
        end
    end
end

(1..SUM).each do |i|
    if dp[D][i] >= G
        puts i
        exit
    end
end

Measured memory_bytes: 1916
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fast_input() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}


int solve(int N, int M) {
    vector<int> problems(M+1);
    int ret = 0;
    for (int i = 0; i < N; i++) {
        int d, v; cin >> d >> v;
        problems[d] = max(problems[d], v);
    }
    for (int i = 1; i <= M; i++) {
        ret += problems[i];
    }
    return ret;
}

int main(void) {
    int N, M;
    vector<int> ans;
    while (1) {
        cin >> N >> M;
        if (!N && !M) break;
        ans.push_back(solve(N, M));
    }
    for (int &i : ans) {
        cout << i << endl;
    }
    return 0;
}   



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

template <typename _Tp> inline _Tp read(_Tp&x){
	char c11=getchar(),ob=0;x=0;
	while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')ob=1,c11=getchar();
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

const int N=501000;
int ps[N],lim[N],d[N];
int n,Q,x;

int main(){
	read(n);read(ps[0]);
	for(int i=1;i<=n;++i)
		read(d[i]),ps[i]=min(ps[i-1],abs(ps[i-1]-d[i]));
	lim[n+1]=1;
	for(int i=n;i;--i)
		if((lim[i+1]<<1)<=d[i])lim[i]=lim[i+1];
		else lim[i]=min((int)2e9,lim[i+1]+d[i]);
	read(Q);while(Q--){
		read(x);
		puts(ps[x-1]>=lim[x+1]?"YES":"NO");
	}return 0;
}

Measured memory_bytes: 7808
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip()
na = lambda: list(map(int, stdin.readline().split()))
ni = lambda: int(ns())

n = ni()

if n % 2 == 1:
    print(0)
    exit()

n //= 2
cnt = 0
while n > 0:
    cnt += n // 5
    n //= 5
print(cnt)



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

namespace H
{
    public class Program
    {
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);
            Solve();
            Console.Out.Flush();
        }

        public static void Solve()
        {
            var HW = Console.ReadLine().Trim().Split(' ').Select(int.Parse).ToArray();
            var (H, W) = (HW[0], HW[1]);
            var grid = new bool[H][];
            for (var i = 0; i < H; i++)
            {
                var s = Console.ReadLine();
                grid[i] = s.Select(x => x == '#').ToArray();
            }
            const int p = (int)1e9 + 7;

            var dp = new long[H][].Select(x => x = new long[W]).ToArray();
            dp[0][0] = 1;
            for (var i = 0; i < H; i++)
            {
                for (var j = 0; j < W; j++)
                {
                    if (i > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % p;
                    if (j > 0) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % p;
                    if (grid[i][j]) dp[i][j] = 0;
                }
            }

            // Console.WriteLine(string.Join("\n", dp.Select(x => string.Join(" ", x))));
            Console.WriteLine(dp[H - 1][W - 1]);

        }
    }
}


Measured memory_bytes: 41116
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long; 
using ld = long double;
#define endl "\n"
//#define int long long
#define all(V) V.begin(),V.end()
#define rep(i, n) for (int i = 0; i < n; i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
const int MOD = 1e9 + 7;
const ll INF = 1LL << 60;
const int inf = 1 << 25;
constexpr long double pi = 3.141592653589793238462643383279;
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll fact_mod(ll n, ll mod) {
    ll f = 1; for (int i = 2; i <= n; i++) f = f * (i % mod) % mod;
    return f;
}
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a * b / gcd(a, b);
}
ll keta(ll n) {
    if (n == 0) return 1;
    ll count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
ll mch(ll n) {
    if (n == 1) return 1;
    else return n * mch(n - 1);
}
ll pow_mod(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = (res * x) % mod; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % mod;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}
ll inv_mod(ll a, ll mod) {
    ll b = mod, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= mod;
    if (u < 0) u += mod;
    return u;
}
bool is_prime(const unsigned n) {
    switch (n) {
    case 0: // fall-through
    case 1: return false;
    case 2: // fall-through
    case 3: return true;
    } // n > 3 が保証された
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (unsigned i = 5; i * i <= n; i += 6) {
        if (n % i == 0) return false; // (6の倍数)-1
        if (n % (i + 2) == 0) return false; // (6の倍数)+1
    }
    return true;
}
//関数とか

//宣言とか

/*signed*/int main(void) {
    string s;
    cin >> s;
    if (s[s.size() - 1] == 's') cout << s << "es" << endl;
    else cout << s << 's' << endl;
    return 0;
}

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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

ll N, K;
vector<ll> a, f;

signed main() {
  cin >> N >> K;
  a.resize(N);
  f.resize(N);
  rep(i,N) cin >> a[i];
  rep(i,N) cin >> f[i];
  sort(begin(a), end(a));
  sort(begin(f), end(f));
  reverse(begin(f), end(f));

  ll ng = -1, ok = 1000000000000;
  while(ng+1<ok) {
    ll m = (ng+ok)/2;
    ll k = 0;
    rep(i,N) {
      if (a[i]*f[i] <= m)
        continue;
      ll d = a[i]*f[i] - m;
      k += (d+f[i]-1)/f[i];
    }
    if (k <= K)
      ok = m;
    else
      ng = m;
  }
  cout << ok << endl;
}


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

using i64 = long long;
using P = pair<i64, i64>;


void solve(long long A, long long B){
    cout << (6 - A - B) << endl;
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    solve(A, B);
    return 0;
}


Measured memory_bytes: 256