akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <assert.h>
#include <algorithm>
#include <vector>

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

    int32_t N;
    std::cin >> N;
    std::vector<int32_t> a(N);
    int32_t max_val = 0;
    for(auto& i : a){
        std::cin >> i;
        max_val = std::max(max_val, i);
    }
    int32_t half_val = max_val / 2;
    constexpr int32_t INF = 1 << 30;
    int32_t min_diff_to_halfval = INF;
    int32_t closest_to_halfval = 0;
    for(int32_t i = 0; i < N; i++){
        if(a[i] == max_val) continue;
        if(max_val % 2 == 0){
            if(min_diff_to_halfval > std::abs(half_val - a[i])){
                closest_to_halfval = a[i];
            }
            min_diff_to_halfval = std::min(min_diff_to_halfval, std::abs(half_val - a[i]));
        }
        else if(a[i] <= half_val){
            if(min_diff_to_halfval > half_val - a[i]){
                closest_to_halfval = a[i];
            }
            min_diff_to_halfval = std::min(min_diff_to_halfval, half_val - a[i]);
        }
        else{
            if(min_diff_to_halfval > a[i] - half_val - 1){
                closest_to_halfval = a[i];
            }
            min_diff_to_halfval = std::min(min_diff_to_halfval, a[i] - half_val - 1);
        }
    }

    std::cout << max_val << " " << closest_to_halfval << std::endl;

    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(a<b){swap(a,b);}
    if(a%b==0){return b;}
    return gcd(b,a%b);
}
int main(){
    int N;
    cin>>N;
    int sub;
    cin>>sub;
    int a;
    for(int i=0;i<N-1;i++){
        cin>>a;
        sub=gcd(a,sub);
    }
    cout<<sub<<endl;
}

Measured memory_bytes: 256
n,k,l = gets.split.map(&:to_i)
b = Array.new(n){|i|i}
c = Array.new(n){|i|i}

def unifinmodoki(b,k)
    a = Hash.new{|h,k|h[k] = [k]}
    k.times do
        x,y = gets.split.map{|i|i.to_i-1}
        next if b[x] == b[y]
        x,y = y,x if a[b[x]].size > a[b[y]].size
        a[b[x]].each do |i|
            b[i] = b[y]
            a[b[y]] << i
        end
    end
    return b
end

b = unifinmodoki(b,k)
c = unifinmodoki(c,l)

cnt = Hash.new(0)
n.times do |i|
    cnt[[b[i],c[i]]] += 1
end

ans = Array.new(n)
n.times do |i|
    ans[i] = cnt[[b[i],c[i]]]
end

puts ans.join(" ")

Measured memory_bytes: 51708
#include<bits/stdc++.h>
#define ll long long 
using namespace std ;
 int main(){
	 string s ; 
	 cin>> s ; 
	 int flag = 1 ; 
	 int n = (int)s.length() ; 
	 for(int i = 0 ; i < n ; ++i){
		 if(s[i] != s[s.length() - 1 - i])
		     flag = 0 ; 
		 }
	 for(int i = 0 ;  i < (n-1)/2 ; ++i){
		 if(s[i] != s[(n-1)/2 - 1 - i])
		         flag = 0 ; 
	 }
	// cout<<flag<<endl ; 
	string q = s.substr((n+3)/2 - 1 , n  + 1- (n + 3)/2) ; 


    for(int i = 0 ;i < (int) q.length() ; ++i)
    {
		if(q[i]!= q[q.length() - 1 - i] )
		flag = 0 ; 
	}
 
	 
	 
	 
	 
	   if(flag ==0 )
	   cout<<"No"<<endl;
	   else 
	   cout<<"Yes"<<endl;
	 
	 
	 
	 
 }


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

int main(){
	int n,a,b;
	cin>>n>>a>>b;
	int res=0;
	int num=0,tmp=0,dig,sum;
	for(int i=0;i<=n;i++){
		//cout<<"ss"<<endl;
		dig=0;sum=0;
		num=i;
		while(num){
			//cout<<"te"<<endl;
			dig=num%10;
			sum+=dig;
			num/=10;
		}
		if(sum<a||sum>b){
			continue;
		}else{
			//cout<<"i:"<<i<<endl;
			res+=i;
		}
	}
	cout<<res<<endl;
}


Measured memory_bytes: 256
//
//AtCoder Beginner Contest 081
//B
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <queue>
#include <map>
#include <set>
#include <tuple>
#include <functional>
#include <cassert>
#include <bitset>
#include <numeric>

using namespace std;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define SIZE(x) (int)(x).size()
#define SIZEL(x) (ll)(x).size()
#define MSG(a) cout << #a << " " << a << endl;

using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;

const double PI = 3.14159265358979323846;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll gcd(ll x, ll y) { return (x % y)? gcd(y, x % y): y; }    //最大公約数
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }            //最小公倍数

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

    vector<int> a(n);
    REP(i, n) cin >> a[i];

    bool brk = true;
    int ans = 0;
    while(brk){
        REP(i,n){
            if (a[i]%2==1) {
                brk = false;
                break;
            }else{
                a[i] /= 2;
            }
        }
        if (brk) ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3612
//BISMILLAHIR RAHMANIR RAHIM
//RABBI ZIDNI ILMA
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define endl "\n"
#define inf (1LL<<61)
#define pi acos(-1)
#define mod 1000000007
#define MOD 998244353
#define all(x) x.begin(), x.end()
#define int_pow(n, p) (ll)(pow(n, p) + 0.5)
#define fastio ios_base::sync_with_stdio(0);cout<< fixed<< setprecision(10);
#define debug(x) cout<<"["<<#x<<": "<<x<<"]\n"
#define debug2(x, y) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]\n"
#define debug3(x, y, z) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]\n"
#define debug4(x, y, z, k) cout<<"["<<#x<<": "<<x<<"]"<<"  ["<<#y<<": "<<y<<"]"<<"  ["<<#z<<": "<<z<<"]"<<"  ["<<#k<<": "<<k<<"]\n"

const ll N = 1e5 + 9;

int main()
{
    fastio
    ll a[2], b[2];
    cin>> a[0]>>a[1]>>b[0]>>b[1];
    ll ans = -inf;
    for(int i=0; i<2; i++){
        for(int j=0; j<2; j++) ans = max(ans, a[i]*b[j]);
    }
    cout<< ans;
}



Measured memory_bytes: 3656
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,num=0;
    set<int>w;
    for(int i=1; i*i<=1000000000; i++)
        w.insert(i*i);
    int a[15][15];
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
        for(int j=0; j<m; j++)
            scanf("%d",&a[i][j]);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
        {
            int ans=0;
            for(int k=0; k<m; k++)
                ans+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
            if(w.find(ans)!=w.end())
                num++;
        }
    printf("%d",num);
    return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
typedef long long int ll;
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define m0(x) memset(x,0,sizeof(x))

int main(void){
	int n,i,j,k;
	scanf("%d",&n);
	int x[n],y[n],h[n];

	rep(i,n){
		scanf("%d %d %d",&x[i],&y[i],&h[i]);
	}
	int htmp[n],flag,hmax;
	m0(htmp);
	for(i=0;i<101;i++){
		for(j=0;j<101;j++){
			flag=0;
			for(k=0;k<n&&h[k]==0;k++);
			hmax=h[k]+abs(i-x[k])+abs(j-y[k]);
			rep(k,n){
				htmp[k]=hmax-abs(i-x[k])-abs(j-y[k]);
				if(htmp[k]<0) {
					htmp[k]=0;				
				}
			}
			rep(k,n){
				if(htmp[k]!=h[k]){
					flag++;
				}
			}
			if(flag==0) goto end;
			
		}
	}

end:
	printf("%d %d %d",i,j,hmax );
	return 0;
	
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define N 200010
using namespace std;

ll n, a, ans, sum;

inline ll read(){
	ll s = 0, w = 1;
	char ch = getchar();
	for (; ch < '0' || ch > '9'; ch = getchar()) w *= ch == '-' ? -1 : 1;
	for (; ch >= '0' && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0';
	return s * w;
}

int main(){
	n = read();
	for (ll i = 1; i <= n; ++i){
		a = read();
		ans = (ans + (sum * a) % mod) % mod;
		sum = (sum + a) % mod;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 3768
#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
template<typename T> using v2 = vector<vector<T>>;
template<typename T> inline v2<T> fill(int r, int c, const T& t){ return v2<T>(r, vector<T>(c, t)); }
#define F first
#define S second

void solve(){
    int m,n;
    cin >> n>>m;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) cin >> a[i];

    sort(a.begin(), a.end(), greater<int>());

    int tot = 0;
    for(int i : a) tot += i;
    if(4*m*a[m-1] >= tot){
        cout << "Yes\n";
    }
    else{
        cout << "No\n";
    }
}

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

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

#define INF INT_MAX

using Weight = long long;
using Weights = vector<Weight>;
using Matrix = vector<Weights>;

bool WF(const Matrix &g, Matrix &dist, vector<vector<int>> &prev) {
	int V = g.size();
	dist = g;
	prev.assign(V, vector<int>(V, -1));
	for (int k = 0; k < V; ++k) {
		for (int i = 0; i < V; ++i) {
			for (int j = 0; j < V; ++j) {
				if (dist[i][k] == INF || dist[k][j] == INF) continue;
				if (dist[i][j] > dist[i][k] + dist[k][j]) {
					dist[i][j] = dist[i][k] + dist[k][j];
					prev[i][j] = k;
				}
			}
		}
	}
	for (int i = 0; i < V; ++i) if (dist[i][i] < 0) return true;
	return false;
}

void buildPath(const vector< vector<int> > &prev,
	int s, int t, vector<int> &path) {
	int u = prev[s][t];
	if (u < 0) path.push_back(s);
	else buildPath(prev, s, u, path), buildPath(prev, u, s, path);
}
vector<int> buildPath(
	const vector< vector<int> > &prev, int s, int t) {
	vector<int> path;
	buildPath(prev, s, t, path);
	path.push_back(t);
	return path;
}

int main(void) {
	int V, E;
	cin >> V >> E;
	Matrix g(V, vector<Weight>(V, INF));
	//for (int i = 0; i < V; ++i) g[i][i] = 0;
	for (int i = 0; i < E; ++i) {
		long long s, t, w;
		cin >> s >> t >> w;
		g[s][t] = w;
	}

	Matrix dist;
	vector<vector<int>> prev;
	bool nc = WF(g, dist, prev);
	if (nc) {
		cout << "NEGATIVE CYCLE" << endl;
		return 0;
	}
	for (int i = 0; i < V; ++i) {
		for (int j = 0; j < V; ++j) {
			if (i == j) cout << "0";
			else if (dist[i][j] == INF) cout << "INF";
			else cout << dist[i][j];
			if (j != V - 1)cout << " ";
		}
		cout << endl;
	}

	return 0;
}



Measured memory_bytes: 3284
import sys
input = sys.stdin.readline
INF = 10**18
def li():
    return [int(x) for x in input().split()]

N, K = li()
A = [0] + li()
for i in range(1, N-K+1):
    if A[K+i] > A[i]:
        print("Yes")
    else:
        print("No")

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

int main() {
	string s;
	cin >> s;
	int counter = 0;
	if (s[0] == '1') {
		counter += 1;
	}
	if (s[1] == '1') ++counter;
	if (s[2] == '1') ++counter;

	cout << counter << endl;
}

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

int main(void){
  string s,t,u;
  int a,b;
  
  cin >> s >> t;
  cin >> a >> b;
  cin >> u;
  if (s==u) cout << a-1 << " " << b << endl;
  else cout << a << " " << b-1 << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)
 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
 
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
 
using namespace std;

ll powa(ll a, ll b, ll c)
{
    a%=c;
    ll res = 1;
    while(b>0)
    {
        if(b&1)
            res*=a, res%=c;
        a*=a, a%=c;
        b>>=1;
    }
    return res;
}

#define N 100005

ll fact[N];
ll ifact[N];
ll ncr(ll n, ll r)
{
    if(r>n)
        return 0;
    ll ans = fact[n];
    ans*=ifact[r];
    ans%=mod;
    ans*=ifact[n-r];
    ans%=mod;
    return ans;
}

ll get(string s, ll k)
{
    if(k == 0)
        return 1;
    if(s.length() == 0)
        return 0;
    ll len = s.length();
    if(len<k)
        return 0;
    ll p1 = 0;
    ll mul = 1;
    rep(k)
        mul*=9;
    for(ll i=1;i<=len-1;i++)
        p1+=mul*(ncr(i-1,k-1));
    
    mul = 1;
    rep(k-1)
        mul*=9;
    
    for(ll dig=1;dig<((ll)s[0]-'0');dig++)
        p1+=mul*ncr(len-1,k-1);
    //cout<<"for "<<s<<" = "<<p1<<"\n";
    reverse(s.begin(), s.end());
    s.pop_back();
   while(s.length()>0 && s.back() == '0')
        s.pop_back();
    if(s.length()>0)    
            reverse(s.begin(), s.end());
    return p1 + get(s,k-1);
}


int main()
{
   FAST/**/
   
   fact[0] = 1;
   for(ll i=1;i<N;i++)
        fact[i] = fact[i-1]*i, fact[i]%=mod;
   for(ll i=0;i<N;i++)
        ifact[i] = powa(fact[i],mod-2,mod);
   
   string n;
   cin>>n;
   
   ll k;
   cin>>k;
   
   ll ans = get(n,k);
   ll cnt =  0;
   if(cnt == k)
        ans++;
   cout<<ans;
   
   return 0;        
}  

Measured memory_bytes: 1792
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>

using namespace std;

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

	if (N < 10) {
		cout << R + 100 * (10 - N) << endl;
	}
	else {
		cout << R << endl;
	}

}






Measured memory_bytes: 3468
import sys


def alg_combination_mod(n, r, mod):
    r = min(n - r, r)
    if r == 0:
        return 1
    else:
        denominator = 1
        for i in range(n, n - r, -1):
            denominator = (denominator * i) % mod
        molecule = 1
        for i in range(1, r + 1):
            molecule = (molecule * i) % mod
        return denominator * pow(molecule, mod - 2, mod) % mod


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, a, b = list(map(int, input().rstrip('\n').split()))
    all_cnt = pow(2, n, mod)
    a_cnt = alg_combination_mod(n, a, mod)
    b_cnt = alg_combination_mod(n, b, mod)
    print((all_cnt - a_cnt - b_cnt - 1) % mod)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 40508
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,f,n) for(int i=f; i<(n); i++)
int main()
{
  int ans;
  string s, t;
  cin >> s;
  cin >> t;
  ans = t.length();

  REP(i,0,s.length()-t.length()+1){
    int cnt = 0;
    REP(j,0,t.length()){
      if(s[i+j]==t[j]){
      }else{
        cnt++;
      }
    }
    ans = min(ans,cnt);
  }

  cout << ans << endl;

  //--debug : end_stoper
  //string end_stoper; cin >> end_stoper;

  return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;

int main() {
  int X, N;
  int P[100];
  cin >> X >> N;
  for (int i = 0; i < N; i++) cin >> P[i];
  
  int min = 1000;
  int mins[103];
  for (int i = 0; i <= 102; i++) mins[i] = 1000;
  int cur = 0;
  for (int i = -1; i <= 101; i++) {
    int canBeMin = 1;
    for (int j = 0; j < N; j++) {
      if (P[j] == i) {
        canBeMin = 0;
        break;
      }
    }
    int dist = abs(X - i);
    if (canBeMin == 1 && dist <= abs(X - min)) {
      min = i;
      mins[cur] = i;
      cur++;
    }
  }

  int ans = 1000;
  for (int i = 0; i < 103; i++) {
    if (abs(X - mins[i]) < abs(X - ans)) ans = mins[i];
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3624
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;}
ll LCM(ll c,ll d){return c/GCD(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
struct mint{
    using ull=unsigned long long int;
    ull v;
    mint(ll vv=0){s(vv%mod+mod);}
    mint& s(ull vv){
        v=vv<mod?vv:vv-mod;
        return *this;
    }
    //オーバーロード
    mint operator-()const{return mint()-*this;}//符号反転
    mint&operator+=(const mint&val){return s(v+val.v);}
    mint&operator-=(const mint&val){return s(v+mod-val.v);}
    mint&operator*=(const mint&val){
        v=ull(v)*val.v%mod;
        return *this;
    }
    mint&operator/=(const mint&val){return *this*=val.inv();}
    mint operator+(const mint&val){return mint(*this)+=val;}
    mint operator-(const mint&val){return mint(*this)-=val;}
    mint operator*(const mint&val){return mint(*this)*=val;}
    mint operator/(const mint&val){return mint(*this)/=val;}
    mint pow(ll n)const{
        mint res(1),x(*this);
        while(n){
            if(n&1)res*=x;
            x*=x;
            n>>=1;
        }
        return res;
    }
     mint inv()const{return pow(mod-2);}
    //拡張ユークリッドの互除法
    /* mint inv()const{
        int x,y;
        int g=extgcd(v,mod,x,y);
        assert(g==1);
        if(x<0)x+=mod;
        return mint(x);
    }*/
    friend ostream& operator<<(ostream&os,const mint&val){
        return os<<val.v;
    }//出力
    bool operator<(const mint&val)const{return v<val.v;}
    bool operator==(const mint&val)const{return v==val.v;}
    bool operator>(const mint&val)const{return v>val.v;}
};
int main(){
    ll n,k;
    cin>>n>>k;
    mint dat[k+1]={};
    mint ans=0;
    int res;
    for(int i=k;i>=1;i--){
       res=k/i;
       dat[i]=mint(res).pow(n);
       for(int j=2;i*j<=k;j++)dat[i]-=dat[i*j];
       ans+=dat[i]*mint(i);
    }
    cout<<ans<<"\n";
}

Measured memory_bytes: 4424
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define rall(c) (c).rbegin(),(c).rend()
#define double long double
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf=1e9+7;
const ll mod=1e9+7;
int main(){
    ll n,x;cin>>n>>x;
    ll ans=n;
    ll a=min(x,n-x),b=max(n-x,x);
    while(1){
        if(b%a==0){
            ans+=(b/a*2-1)*a;
            break;
        }else{
            ans+=(b/a*2)*a;
            ll c=a;
            a=b%c;
            b=c;
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = Integer.parseInt(sc.next());
		List<Integer> p = new ArrayList<Integer>();

		int sum = 0;
		for(int i=0; i<N;i++){
			int tmp = Integer.parseInt(sc.next());
			sum += tmp;
			p.add(tmp);
		}
		Collections.sort(p);
		int max = p.get(p.size()-1);
		System.out.println(sum - max / 2);
	}
}

Measured memory_bytes: 20948
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>

//#include <bits/stdc++.h>
using namespace std;
using LL = int;
using ULL = unsigned long long;
long long MOD = 1000000000 + 7;
constexpr long long INF = numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourd; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Mfor(i,mf) for(LL i=mf-1;i>=0;i--)
int h, w, n, m, k, t, s, q, last, cnt, sum, ans, dp[12][40000000], a[101000], b[10000];
string str, ss;
bool f;
char c;
int di[4][2] = { { 0,1 },{ 1,0 },{0,-1},{-1,0} };
struct Edge { LL to, cost; };
vector<LL>vec[27];
vector<Pll>v[200000];
map<Pll, LL>ma;
set<LL>st;
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

int main() {
	cin >> n >> m;
	rep(i, n) {
		cin >> a[i] >> b[i];
		b[i] /= 100;
	}
	m /= 100;
	
	rep(i, n+2)rep(j, m+2)dp[i][j] = INF;
	rep(i,n)
	dp[i][0] = 0;
	
	rep(i, n) {
		rep(j, m+1) {
			rep(k, a[i]+1) {
				if (dp[i][j] != INF) {
					if (k  == a[i])
						dp[i + 1][min(j + (i + 1)*(k ) + b[i], m)] = min({ dp[i + 1][min(j + (i + 1)*(k ) + b[i], m)], dp[i][j] + k  ,dp[i][min(j + (i + 1)*(k ) + b[i], m)] });
					else
						dp[i + 1][min(j + (i + 1)*(k ), m)] = min({ dp[i + 1][min(j + (i + 1)*(k ), m)], dp[i][j] + k ,dp[i][min(j + (i + 1)*(k ), m)] });
				}
			}
		}
		Mfor(j, m + 1) {
			dp[i][j] = min(dp[i][j], dp[i][j +1]);
		}
	}
	cout << dp[n][m] << endl;
	return 0;
}


Measured memory_bytes: 35072
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def inv(x):
    return pow(x, mod - 2, mod)

def comb(n, b):
    if b > n - b:
        b = n - b
    r = 1
    for k in range(n, n-b, -1):
        r = r * k % mod
    d = 1
    for k in range(1, b+1):
        d = d * k % mod
    return r * inv(d) % mod

def main():
    x,y = LI()
    x,y = max(x,y), min(x,y)
    if (x+y) % 3 > 0 or x > y*2:
        return 0

    c = (x+y) // 3
    xc = (x-y) + (c - (x-y)) // 2

    return comb(c,xc)


print(main())




Measured memory_bytes: 6420
import java.math.*;
import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int count = 0;
    for (int i = 0; i < n; i++) {
      boolean b = sc.nextInt() == sc.nextInt();
      if (b) {
        count++;
        if (count >= 3) {
          System.out.println("Yes");
          return;
        }
      } else {
        count = 0;
      }
    }
    System.out.println("No");
  }
}


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

int main()
{
        int N, K;
        cin >> N >> K;
        int pat = (N - 1) * (N - 2) / 2;

        if ( K > pat ) {
                cout << -1 << endl;
        } else {
                cout << (N - 1) + pat - K << endl;
                for ( int i = 2; i <= N; i++ ) {
                        cout << 1 << " " << i << endl;
                }
                int cnt = 0;
                for ( int i = 2; i <= N && cnt < pat - K; i++ ) {
                        for ( int j = i + 1; j <= N && cnt < pat - K; j++, cnt++ ) {
                                cout << i << " " << j << endl;
                        }
                }
        }

        return ( 0 );
}


Measured memory_bytes: 256
import bisect
n=int(input())
l=list(map(int,input().split()))
l.sort()
if n==2:
    print(l[1],l[0])
    exit()
m=max(l)
k=m//2
i=bisect.bisect_left(l,k)
if i==0:
    print(m,l[0])
    exit()
if abs(l[i]-k)<=abs(l[i-1]-k):
    print(m,l[i])
else:
    print(m,l[i-1])


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

int main () {
  int64_t n, k;
  cin >> n >> k;
  vector<int> h(n);
  for (int i = 0; i < n; i++) cin >> h[i];
  
  sort(h.begin(), h.end(), greater<int>());
  int64_t ans = 0;
  if (n <= k) cout << 0;
  else {
    for (int i = k; i < n; i++) ans += h[i];
    cout << ans;
  }
}


Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll n, c, x[110000], v[110000], l1[110000], l2[110000], r1[110000], r2[110000], res1, res2;
int main(void){
    // Your code here!
    cin >> n >> c;
    for (int i = 0; i < n; i++) cin >> x[i] >> v[i];
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            l1[i] = v[i] - x[i];
        } else {
            l1[i] = l1[i - 1] + v[i] - (x[i] - x[i - 1]);
        }
        l2[i] = l1[i] - x[i];
    }
    for (int i = n - 1; i >= 0; i--) {
        if (i == n - 1) {
            r1[i] = v[i] - (c - x[i]);
        } else {
            r1[i] = r1[i + 1] + v[i] - (x[i + 1] - x[i]);
        }
        r2[i] = r1[i] - (c - x[i]);
    }
    for (int i = 0; i < n; i++) {
        if (i == 0) {
            l1[i] = (0 > l1[i] ? 0 : l1[i]);
            l2[i] = (0 > l2[i] ? 0 : l2[i]);
        } else {
            l1[i] = max(l1[i], l1[i - 1]);
            l2[i] = max(l2[i], l2[i - 1]);
        }
    }
    for (int i = 0; i <= n; i++) {
        if (i == 0) {
            res1 = r1[0];
            res2 = r2[0];
        } else if (i == n) {
            res1 = max(res1, l2[i - 1]);
            res2 = max(res2, l1[i - 1]);
        } else {
            res1 = max(res1, r1[i] + l2[i - 1]);
            res2 = max(res2, r2[i] + l1[i - 1]);
        }
    }
    cout << max(res1, res2) << endl;
}


Measured memory_bytes: 5120
import java.awt.*;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    static LinkedList<Integer> adj[];
    static boolean vis[];static int dp[],inDeg[],dist[];
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n=sc.nextInt(),m=sc.nextInt();
        adj=new LinkedList[n];
        inDeg=new int[n];
        for (int i=0;i<n;i++){
            adj[i]=new LinkedList<>();
        }
        dist=new int[n];
        for (int i=0;i<m;i++){
            int a=sc.nextInt()-1,b=sc.nextInt()-1;
            adj[a].add(b);
            inDeg[b]++;
        }
        dp=new int[n];
        vis=new boolean[n];
        for (int i=0;i<n;i++){
            if (inDeg[i]==0){
                dfs(i);
            }
        }
        int ans=0;
        for (int i=0;i<n;i++){
            ans=Math.max(ans,dist[i]);
        }
        System.out.println(ans);
    }
    static void dfs(int i){
        if (vis[i])return;
        vis[i]=true;
        for (int u:adj[i]){
            dist[u]=Math.max(dist[u],dist[i]+1);
            inDeg[u]--;
            if (inDeg[u]==0){
                dfs(u);
            }
        }
    }

}

Measured memory_bytes: 112824
#include <bits/stdc++.h>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string a;
    bool flag=false;
    cin>>a;
    if(a=="a"||a=="e"||a=="i"||a=="o"||a=="u"){
        flag=true;
    }
     flag ? cout<<"vowel"<<endl : cout<<"consonant"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
int main(){
    int n,A,a=0,b=0,c=0;
    cin>>n;
    rep(i,n){
        cin>>A;
        if(A%4==0) a++;
        else if(A%2==0) b++;
        else c++;
    }
    if(b) c++;
    if(a+1>=c) cout<<"Yes";
    else cout<<"No";
}


Measured memory_bytes: 256
import Data.List

main :: IO ()
main = do
  n <- getInt
  putStrLn . concatMap show . reverse . g . unfoldr f $ n
  where
    f 0 = Nothing
    f x = Just (x `mod` 2, - x `div` 2)
    g [] = [0]
    g xs = xs

getInt :: IO Int
getInt = readLn


Measured memory_bytes: 508
#include<bits/stdc++.h>
using namespace std;
using ull=unsigned long long;
#define mod 1000000007
#define mod2 998244353 
#define PI 3.14159265
#define ll long long
#define ld long double
#define pi pair<ll,ll>
#define pb push_back
#define vi vector<ll>
#define sz size()
#define setbits(x)  __builtin_popcount(x)
#define fi first
#define se second
#define lz length()
#define all(x) (x).begin(),(x).end()
#define scf(x) scanf("%lld",&x)
#define rep(i,n) for(ll i=0;i<n;i++)
const int INF = (int)1e9;
const ll IINF=1LL<<62;
const int maxn=10000005;

//int divr[maxn];
/**/
/*void divisor()
{for(int i=2;i<sqrt(maxn);i++)
     {
          if(!divr[i])
          {
               for(int j=i*i;j<maxn;j+=i)if(!divr[j])divr[j]=i;     
          }
     }
     for(int i=1;i<maxn;i++)if(!divr[i])divr[i]=i;
}*/
 
/*const int N=1000005;
ll n;
struct line {
    long long m, c;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) { return (long double) (c - l.c) / (l.m - m); }
};
vector<pair<pi,ll>> rect;
deque<line> dq;
*/
ll modexpo(ll a,ll b)
{
     ll res=1LL;
     while(b>0)
     {
          if(b&1)res=(res*a)%mod;
          a=(a*a)%mod;
          b>>=1;
     }
     return res;
}
 
 
 
 
 
 
 




bool s[405][405];
bool used[405][405];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int main()
{
    ll n;
    cin>>n;
    ll a=1,b=1;
    for(int i=0;i<n;i++){
         ll t1,a1;cin>>t1>>a1;
         ll x=max((a-1)/t1+1,(b-1)/a1+1);
         a=t1*x;
         b=a1*x;
    }
    cout<<a+b;

}



































Measured memory_bytes: 3536
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <cstdint>
#include <numeric>
#include <cmath>

#define INF 1000000000
#define INF2 100000000000
#define LLINF 1000000000000000000
#define MOD 1000000007
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define LOOP(i,N) for(int i=0;i<N;i++)
#define LOOP1(i,N) for(int i=1;i<=N;i++)
typedef pair<int,int> P;
typedef pair<int,pair<int,int> > PP;
#define int long long


const int N = 1000000 /*値*/;
void eratosthenes(bool prime[N]){
    LOOP(i,N) prime[i] = 1;
    prime[0] = prime[1] = 0;
    LOOP(i,N){
        if(prime[i]){
            for(int j = i + i; j < N; j+=i){
                prime[j] = 0;
            }
        }
    }
}

signed main(){
  bool isprime[N];
  eratosthenes(isprime);
  int n;
  cin >> n;
  int su = 0;
  vector<int> prime;
  FOR(i,2,sqrt(n)+1){
    // cerr << "?" << endl;
    if(!isprime[i]){
      continue;
    }
    // prime.push_back(i);
    int cnt = 0;
    // int tmp = n;
    while(true){
      if(n%i == 0){
        cnt++;
        n/=i;
      }else{
        break;
      }
    }
    int ans = 0;
    while(cnt){
      if(cnt >= (ans+1)){
        ans ++;
        cnt -= ans;
      }else{
        break;
      }
    }
    // if(ans != 0)
    // cerr << i << ":" << ans << endl;

    su += ans;
  }
  if(n!=1){
    su++; // 素数が1個残ってる
  }
  if(su == 0){
    if(n == 1){
      cout << 0 << endl;
      return 0;
    }
  }else{
    cout << su << endl;
  }
}


Measured memory_bytes: 4660
#include <iostream>
#include <vector>
#include <string>
#include <stdio.h>
#include<limits.h>
#include<algorithm>
#include<queue>
#include<set>


#define MOD 1000000007

using namespace std;

long long int modpow(long long int a, long long int n) {
	if (n == 0)return 1;
	if (n == 1)return (a % MOD);

	long long int hanbun = n / 2;
	long long int amari = n % 2;

	long long int ans = (a * a) % MOD;
	ans = modpow(ans, hanbun);

	if (amari == 1)ans *= a;

	ans %= MOD;

	return ans;

}

long long int gcd(long long int a, long long int b) {
	if (a < b) {
		long long int tmp = a;
		a = b;
		b = tmp;
	}

	long long int amari = a % b;

	if (amari == 0)return b;

	return gcd(b, amari);
}

long long int lcm(long long int a, long long int b) {
	long long int ans = (a * b) % MOD;
	long long int wari = modpow(gcd(a, b), MOD - 2);
	ans = (ans * wari) % MOD;
	return ans;
}

long long int factElement[10000] = { 0 };

long long int factrial(int n) {

	if (factElement[n] != 0)return factElement[n];

	if (n == 0) {
		factElement[0] = 1;
		return factElement[n];
	}

	long long int ans = n * factrial(n - 1);
	factElement[n] = ans;
	return factElement[n];

}


int main()
{

	char a, b, c;
	cin >> a >> b >> c;

	if (a == b && b == c) {
		cout << "No" << endl;
		return 0;

	}

	cout << "Yes" << endl;

	return 0;

}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
#define rall(a) (a).rbegin(),(a).rend()
const int INF = 2e9;
using namespace std;
using Graph = vector<vector<int>>;
typedef pair<int,int> P;
typedef long long ll;

int main(){
    int a, b; cin >> a >> b;
    if(a == 1) a+=13;
    if(b == 1) b+=13;

    if(a > b) cout << "Alice" << endl;
    if(a < b) cout << "Bob" << endl;
    if(a == b) cout << "Draw" << endl;
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100
#define INFTY (1<<21)
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,M[MAX][MAX];

int prim(){

  int sum,i,u,min;
  int d[MAX],p[MAX],c[MAX];

  for(i=0;i<n;i++){
    d[i]=INFTY;
    p[i]=-1;
    c[i]=WHITE;
  }

  d[0]=0;

  while(1){
    min=INFTY;
    u=-1;
    for(i=0;i<n;i++){
      if(min>d[i] && c[i]!=BLACK){
	u=i;
	min=d[i];
      }
    }

    if(u==-1) break;
    c[u]=BLACK;
    
    for(i=0;i<n;i++){
      if(c[i]!=BLACK && M[u][i]!=INFTY){
	if(d[i]>M[u][i]){
	      d[i]=M[u][i];
	      p[i]=u;
	      c[i]=GRAY;
	    }
      }
    }
  }

  sum=0;

  for(i=0;i<n;i++){
    if(p[i]!=-1) sum+=M[i][p[i]];
  }

  return sum;
}

int main(){

  int i,j,e;
  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
      scanf("%d",&e);
      if(e==-1) M[i][j]=INFTY;
      else M[i][j]=e;
    }
  }

  printf("%d\n",prim());

  return 0;
}

Measured memory_bytes: 636
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {

//    	File file = new File("test.txt");
//    	Scanner sc = new Scanner(file);
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] ary = new int[N][2];
        for(int i = 0; i < N; i++){
        	ary[i][0] = sc.nextInt();
        	ary[i][1] = 1;
        }
        for(int i = 0; i < M; i++){
        	int A1 = sc.nextInt();
        	int A2 = sc.nextInt();
        	if(ary[A1-1][0] < ary[A2-1][0]){
        		ary[A1-1][1] = 0;
        	}else if(ary[A1-1][0] == ary[A2-1][0]){
        		ary[A1-1][1] = 0;
        		ary[A2-1][1] = 0;
        	}else{
        		ary[A2-1][1] = 0;
        	}
        }
        sc.close();
        int ans = 0;
        for(int i = 0; i < N; i++){
        	if(ary[i][1] == 1){
        		ans++;
        	}
        }
        System.out.println(ans);
    }
}

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

bool isOrderOdd(int n) {
  int cou = 0;
  while (n >= 10) {
    n /= 10;
    ++cou;
  }
  if (cou % 2 == 0)
    return true;
  else 
    return false;
}

int search(int count[], int n) {
  if (n == 0) {
    count[n] = 0;
    return count[n];
  }
  else if (isOrderOdd(n) && count[n] < 0) {
    count[n] = search(count, n-1) + 1;
    return count[n];
  }
  else if (count[n] < 0) {
  	count[n] = search(count, n-1);
  	return count[n];
  }
}

int main() {
  int n;
  cin >> n;
  int count[n+1];
  for (int i {}; i < n+1; ++i)
    count[i] = -1;
  search(count, n);
  cout << count[n];
}
  

Measured memory_bytes: 2176
const input = require('fs').readFileSync('/dev/stdin', 'utf8');

// console.log(input)

const lines = input.trim().split('\n');
// console.log(lines)

while (line = lines.shift()) {
    const numbers = line.split(' ').map(Number);

    // Edit from here
    let a = numbers[0];
    let b = numbers[1];

    if ( a === 0 && b === 0 ) { break; }

    if ( a > b ) {
        const tmp = a;
        a = b;
        b = tmp;
    } 

    const output = a + ' ' + b;
    console.log(output);
    // to here
    
}



Measured memory_bytes: 18852
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
int main(){
    vector<vector<int>> bingo(3,vector<int>(3,0));
    vector<vector<int>> ana(3,vector<int>(3,0));
    int i,j,k;
    for(i=0;i<3;i++) cin >> bingo.at(i).at(0) >> bingo.at(i).at(1) >> bingo.at(i).at(2);
    ll n;
    cin >>n;
    for(i=0;i<n;i++){
        ll a;
        cin >> a;
        for(j=0;j<3;j++){
            for(k=0;k<3;k++){
                if(bingo.at(j).at(k)==a)
                ana.at(j).at(k)++;
            }
        }
    }
    for(i=0;i<3;i++){
        if(ana.at(i).at(0)!=0&&ana.at(i).at(1)!=0&&ana.at(i).at(2)!=0){
            cout << "Yes" <<endl;
            return 0;
        }
    }
    for(i=0;i<3;i++){
        if(ana.at(0).at(i)!=0&&ana.at(1).at(i)!=0&&ana.at(2).at(i)!=0){
            cout << "Yes" <<endl;
            return 0;
        }
    }
    if(ana.at(0).at(0)!=0&&ana.at(1).at(1)!=0&&ana.at(2).at(2)!=0){
            cout << "Yes" <<endl;
            return 0;
        }
    if(ana.at(2).at(0)!=0&&ana.at(1).at(1)!=0&&ana.at(0).at(2)!=0){
            cout << "Yes" <<endl;
            return 0;
        }
        cout << "No" <<endl;
        return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    string S,T;
    cin>>S>>T;
    bool k=false;
    for(int i=0;i<S.size();i++){
        if(S.at(i)!=T.at(i)){k=true;}
    }
    if(k){cout<<"No"<<endl;}
    else{cout<<"Yes"<<endl;}
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i,l,r) for(int i = (int)l;i<(int)r;i++)
#define td(v) v.begin(),v.end()
#define sz(v) (int)v.size()
//#define M   1000000007 // 1e9 + 7
#define int long long
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline ll mod(ll n, ll m){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll a,ll b,ll m){
    
    if(b==0LL) return 1LL;
    if(b==1LL) return mod(a,m);
    ll k = mod(exp(a,b/2,m),m);
    if(b&1LL){
        return mod(a*mod(k*k,m),m);
    }
    else return mod(k*k,m);
}


int32_t main(){
  fastio;
  int n;
  cin>>n;
  map<int,int> mp;
  int ok=1;
  for(int i=0;i<n;i++){
    int x;
    cin>>x;
    if(mp[x])ok=0;
    mp[x]++;
  }
  if(ok)cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
  // Math -> gcd it all
  // Did u check N=1? Did you switch N,M?
}

Measured memory_bytes: 12800
def possible(b):
    print('POSSIBLE' if b else 'IMPOSSIBLE')
    exit()

n, k = map(int, input().split())
A = list(set(map(int, input().split())))
n = len(A)

if k in A:
    possible(True)

if k > max(A):
    possible(False)

if n == 1:
    possible(False)

A.sort()
D = [A[i + 1] - A[i] for i in range(n - 1)]
from fractions import *
g = D[0]
for d in D:
    g = gcd(g, d)

possible(k % g == 0)

Measured memory_bytes: 19728
#include<bits/stdc++.h>
using namespace std;
struct UnionFind {
  vector<int> parent;
  vector<int> per_size;
  
  UnionFind(int n): parent(n, -1), per_size(n, 1) {}

  int root(int x){
    return (parent[x] < 0 ? x : parent[x] = root(parent[x]));
    //if(parent[x] < 0) return x;
    //else parent[x] = root(parent[x]);
  }

  void unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if(rx == ry) return;
    if(per_size[rx] < per_size[ry]) swap(rx, ry);
    per_size[rx] += per_size[ry];
    parent[ry] = rx;
    //for(int i = 0; i < per_size.size(); ++i) cout << i << ": " << per_size[i] << endl;
  }

  bool is_same(int x, int y){
    return root(x) == root(y);
  }

  int size(int x){
    return per_size[root(x)];
  }

};

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  UnionFind relation(n);
  //int friends[100001];
  //vector<int> block[100001];
  vector<int> friends(n, 0);
  vector<int> block[n];
  for(int i = 0, x, y; i < m; ++i){
    cin >> x >> y;
    x--;
    y--;
    friends[x]++;
    friends[y]++;
    relation.unite(x, y);
  }
  for(int i = 0, x, y; i < k; ++i){
    cin >> x >> y;
    x--;
    y--;
    block[x].push_back(y);
    block[y].push_back(x);
  }
  int ans;
  for(int i = 0; i < n; ++i){
    ans = relation.size(i) - friends[i] - 1;
    for(auto tgt: block[i]){
      if(relation.is_same(tgt,i)) ans--;
    }
   cout << (i ? " " : "") << ans;
  }
  cout << endl;
}


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

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

const int N = 2e5 + 5;
int n, a[N], b[N];
int s[3 * N], p[3 * N];

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

  for (int i = 0; i < n; ++i) s[i] = b[i] ^ b[(i + 1) % n];
  for (int i = 0; i < n; ++i) s[i + n + 1] = a[i] ^ a[(i + 1) % n];
  for (int i = 2 * n + 1; i <= 3 * n; ++i) s[i] = s[i - n];
  s[n] = -1;

  int now = p[0] = -1;
  for (int i = 1; i <= 3 * n; ++i) {
    while (now + 1 && s[now + 1] != s[i]) now = p[now];
    p[i] = s[now + 1] == s[i] ? ++now : (now = -1);
  }

  for (int i = 2 * n; i < 3 * n; ++i) {
    if (p[i] == n - 1) {
      int k = i - 2 * n;
      int x = a[k] ^ b[0];
      printf("%d %d\n", k, x);
    }
  }
}


Measured memory_bytes: 9728
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <string>
#include <vector>
#include <map>
#include <functional>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
#define MIN(a, b) (((a) < (b)) ? (a) : (b))



using namespace std;
typedef long long int ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pint;
const ll inf = (1LL << 60);
const ll mod = 1000000007;




ll N;
string A, B, C;

int main() {

	cin >> N >> A >> B >> C;

	ll ans = inf;
	ll sum = 0;

	rep(i, N) {
		if (A[i] == B[i] && A[i] !=  C[i]) {
			sum += 1;
		}

		else if (A[i] == C[i] && A[i] != B[i]) {
			sum += 1;

		}

		else if (B[i] == C[i] && A[i] != B[i]) {
			sum += 1;
		}
		else if(B[i] != C[i] && A[i] != B[i]){
			sum += 2;
		}

	}


	cout << sum << endl;

	return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

ll N, K;

bool check(ll x, vector<ll> &A){
	vector<ll> B(N);
	REP(i, N) B[i] = A[i];

	REP(i, N) B[i] %= x;
	sort(B.begin(), B.end());
	ll S = 0;
	REP(i, N) S += B[i];
	ll r = S/x;
	ll key = 0;
	//cout << B << endl;
	REP(i, N-r){
		key += B[i];
	}
	//dump(key)
	if(r>0 && r<N){
		if(K >= key){
			return true;
		}else{
			return false;
		}
	}
	else return false;
}

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

    
    cin >> N >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

  	ll S = 0;
  	REP(i, N) S += A[i];
  	ll sS = sqrt(S) + 2;
  	set<ll> st;
  	for(int i=1;i<=sS;i++){
  		if(S%i == 0) st.insert(i), st.insert(S/i);
  	}
  	//dump(S)
  	ll ma = 1;
  	for(auto x: st){
  		//dump(x)
  		if(check(x, A)) ma = max(ma, x);
  	}
  	cout << ma << endl;
    return 0;
}

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


def isOK(mid, x):
    print(str(mid), flush=True)
    s = input().strip()
    if s == "Vacant":
        exit()
    if (x and s == "Male") or (not x and s == "Female"):
        return True
    else:
        return False


ok = 0
ng = N

print("0", flush=True)
S = input().strip()
if S == "Vacant":
    exit()

if S == "Male":
    kijun = True
else:
    kijun = False

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if mid % 2 == 0:
        if isOK(mid, kijun):
            ok = mid
        else:
            ng = mid
    else:
        if isOK(mid, not kijun):
            ok = mid
        else:
            ng = mid



Measured memory_bytes: 9164
def getStart(field):
    search_field = field[1:]  
    for y in range(len(search_field)):
        for x in range(len(search_field[0])):
            if search_field[y][x] == "S":
                return x,y+1


def bfs(field,start_x,start_y,goal_N):
    direction = [[-1,0],[1,0],[0,-1],[0,1]]
    gotten_cheese = 1
    distance = 0
    que = []
    que.append([start_x,start_y,gotten_cheese,distance])
    INF = 1
    min_path = [[INF for j in range(field[0][1])] for i in range(field[0][0])]
    while len(que) != 0:
        current = que.pop(0)
        for d in direction:
            nx = current[0] + d[0]
            ny = current[1] + d[1]
            if 0 <= nx < field[0][1] and 1 <= ny < field[0][0]+1 and field[ny][nx] != "X" and min_path[ny-1][nx] == INF:
                if field[ny][nx] == current[2]: 
                    if field[ny][nx] == goal_N: 
                        print(current[3]+1)
                        return
                    else: # not goal, but could eat cheese
                        que = []
                        que.append([nx,ny,current[2]+1,current[3]+1])
                        min_path = [[INF for j in range(field[0][1])] for i in range(field[0][0])]
                        break
                else:
                    que.append([nx,ny,current[2],current[3]+1])
                    min_path[ny-1][nx] = 0


def main(field):

    sx,sy = getStart(field)
    bfs(field,sx,sy,field[0][2])

matrix = []
while True:
    row = input().rstrip().split()
    if len(row) == 3:
        re_row = []
        for i in row:
            re_row.append(int(i))
        matrix.append(re_row)
    else:
        re_row = []
        for char in row[0]:
            if char.isdigit():
                re_row.append(int(char))
            else:
                re_row.append(char)
        matrix.append(re_row)
    if len(matrix) == int(matrix[0][0]) + 1:
        main(matrix)
        break

Measured memory_bytes: 34252
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
using P=pair<long long,long long>;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);  
  
  string x;
  cin >> x;
  int n=x.size();
  int pointer=0,sum=0;
  rep(i,n){
    if(x[i]=='S'){
      pointer++;
    }
    else{
      if(pointer==0)continue;
      pointer--;
      sum++;
    }
  }
  cout << n-2*sum << endl;
}


Measured memory_bytes: 720