akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
//#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 55;
const int K = 19;
int p[1 << K][N], dp[1 << K][N], a[N], b[N], c[1<<K][N];
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
   // freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < (1 << n); i++)
        for (int j = 1; j <= 50; j++) dp[i][j] = 1e9;
    for (int i = 0; i < (1 << n); i++){
        int bt = __builtin_popcount(i);
        for (int j = 0; j < n; j++){
            c[i][j] = j - __builtin_popcount(i & ((1 << j) - 1));
        }
    }
    for (int i = 1; i < (1 << n); i++){
        int bt = __builtin_popcount(i);
        p[i][0] = 1e9;
        for (int j = 1; j <= 50; j++){
            for (int l = 0; l < n; l++){
                if ((i & (1 << l)) && (((abs(l - bt + 1)) % 2 == 1 && b[l] == j) || ((abs(l - bt + 1)) % 2 == 0 && a[l] == j))){
                    dp[i][j] = min(dp[i][j], p[i ^ (1 << l)][j] + c[i ^ (1 << l)][l]);
                }
            }
            p[i][j] = min(p[i][j - 1], dp[i][j]);
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= 50; i++) ans = min(ans, dp[(1 << n) - 1][i]);
    if (ans == 1e9) cout << -1; else cout << ans;
}


Measured memory_bytes: 172288
#include<iostream>
using namespace std;struct P{float x,y;int operator-=(P&a){x-=a.x;y-=a.y;}};P A,B,C,S,G;int X(P S){C.x=(B.y*S.x-B.x*S.y)/(A.x*B.y-A.y*B.x);C.y=(A.y*S.x-A.x*S.y)/(A.y*B.x-A.x*B.y);return C.x>0&C.y>0&C.x+C.y<1;}main(){for(cin>>A.x;cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>S.x>>S.y>>G.x>>G.y;){A-=C;B-=C;S-=C;G-=C;X(S)^X(G)?cout<<"OK\n":cout<<"NG\n";}}

Measured memory_bytes: 932
#include<bits/stdc++.h>
using namespace std;
#define ll long long 


int main(){
      cout << fixed << setprecision(10);
      double ans = 0;
      int n,k,z;
      cin >>n>>k;
      vector<int> v(n+1,1);//v[0]はつかわない
      for(int j=1;j>0;j++){
            z = pow(2,j);
            if(1>1.*(k-1)/z){
                  break;
            }
            for(int i=1;i<=1.*(k-1)/z && i<=n;i++){
                  v[i] ++;
            }
      }
      if(n>=k){
            ans = 1.*(n-k+1)/n;
      }
      for(int i=1;i<min(n+1,k);i++){
            z = pow(2,v[i]);
            ans += 1./(z*n);
      }
      cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll  long long
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
#define f(i,n)   for(int i=0;i<n;i++)
#define INF 1e9+5
#define LINF 1e18L+5;
#define pb push_back
#define mk make_pair
using namespace std;
/************************BELIAL**********DEVIL*********BELIAL***********DEVIL*************************/
int main()
{
    

    int n;
    cin>>n;

    //vector<int> arr(n);
    vector<int> dp(3,0);  // maintain ans of prev state 


    for(int days=0;days<n;days++)
    {
            vector<int> c(3);// for a,b,c   
             vector<int> new_dp(3,0); //ans of cur state
               for(int i=0;i<3;i++)
               	     cin>> c[i];


         for(int i=0;i<3;i++)
         {
 	 			 for(int j=0;j<3;j++)
 	 			 {
 	 			 		if(i!=j)
 	 			 		{ new_dp[j]= max(new_dp[j],dp[i]+ c[j]);  //  ans of cur state

 	 			 		}
	 			 }

         }

     dp= new_dp;




    }

    cout<<max(max(dp[0],dp[1]),dp[2]);



}

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

using namespace std;

ifstream fin("in");
ofstream fout("out");
int main()
{
    int nr,x;
    cin>>nr>>x;
    int acum=0,n=1;

    for(int i=1;i<=nr;i++)
{
    int val;
    cin>>val;
    acum=acum+val;
    if(acum<=x)
        n++;
    


}
cout<<n;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
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(b<a){a=b;return 1;}return 0;}
int main(){
	int N,R;
	cin>>N>>R;
	int ans = 0;
	if(N>=10){
		ans = R;
	}
	else{
		ans = R + 1000 - 100*N;
	}
	cout<< (ans) <<endl;
	// printf("%d\n",(ans));
	// cout<< solve() <<endl;
	// printf("%f\n",solve());
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string s;
int q;
cin>>s;
string t;
cin>>q;
for (int i=0;i<q;i++)
{
int k;
cin>>k;
if(k==1)swap(s,t);
else 
{
int f;char c;
cin>>f>>c;
if(f==1)t+=c;
else s+=c;
}
}
reverse(t.begin(),t.end());
t+=s;
cout <<t;
}

Measured memory_bytes: 1128
#include <stdio.h>
//
int sieve(int x){
  if	 (x <  2)	  { return 0; }	//素数ではない
  else if(x == 2)	  { return 1; }	//素数
  else if(x %  2 == 0){ return 0; }	//素数ではない
  
  for( int p=3; p*p<=x; p++ ){
    if(x % p == 0){ return 0; }		//素数ではない
  }
  return 1;							//素数
}
//
int main(){
  int x;
  scanf("%d",&x);
  for(int i=x; i<=100003; i++){
    if( sieve(i)==1 ){ printf("%d\n", i); return 0; }
  }
  return 0;
}

Measured memory_bytes: 1732
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	int a, b;
	cin >> a >> b;
	cout << (a * b - a - b + 1) << endl;
	return 0;
}
 

Measured memory_bytes: 256
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cwchar>
#include <cwctype>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
using namespace std;
int main() {
    int n,ans;
    cin >>n;
    ans=n/500*1000;
    n=n-ans/2;
    ans=ans+n/5*5;
    
    cout<<ans<<endl;
       }


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
using ll=long long;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define ALL(s) s.begin(),s.end()
#define P pair<ll,ll>
#define vl vector<ll>
#define vi vector<int>
#define vvl vector<vector<ll>>
#define vvi vector<vector<int>>
#define print(n) cout<<n<<endl
const int M=100111;
const int inf=1000000007;
const long long INF=1000000000000000007;
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int ddx[8]={1,-1,0,0,1,-1,-1,1},ddy[8]={0,0,1,-1,1,-1,1,-1};



int main(){
	int n,a;
	cin>>n>>a;
	n%=500;
	if(a>=n)print("Yes");
	else print("No");


}

Measured memory_bytes: 764
#include<cstdio>
#include<algorithm>
#include<functional>
#include<cstring>
#include<iostream>
#include<cmath>
#include<queue>
#include<cctype>
#include<string>
using namespace std;
#define rep(i,a,b) for(i=a;i<b;i++)
#define INF 2100000000
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define fi first
#define sec second
#define lb lower_bound
#define ub upper_bound
#define SS stringstream
#define sz(x) ((int)(x).size())
#define clr(a,b) memset((a),(b),sizeof(a))
int main(void)
{
	int i,j,k,cnt,x,sa;
	int a,b;
	int n,kk[4545],c[4545];
	while(cin>>n,n|n) {
		for(i=0;i<n;i++) {c[i]=0,kk[i]=0;}
		rep(i,0,n+1) cin>>kk[i];
		for(i=0;i<n+1;i++) {
			x=0;
			for(j=0;j<n+1;j++) if(i!=j) {c[x]=kk[j],x++;}
			cnt=0;
			for(j=1;j<n;j++) {
				if(j==1) sa=c[j]-c[j-1];
				if(c[j]-c[j-1]!=sa) break;
				else cnt++;
			}
			if(cnt==n-1) {cout<<kk[i]<<endl;break;}
		}
	}
	return 0;
}
		

Measured memory_bytes: 3144
import sys
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	a,b=MI()
	if b%a==0:
		ans=a+b
	else:
		ans=b-a
	print(ans)











if __name__ == "__main__":
	main()


Measured memory_bytes: 9224
#include<iostream>
using namespace std;
int main(){
	int huda[101];
	int n,r;
	while(cin>>n>>r,n||r){
	int p,c;
	for(int i=0;i<101;i++)huda[i]=i+1;
		for(int i=0;i<r;i++){
			cin>>p>>c;
			for(int j=n-p-c+1;j<n-p+1;j++){
				//for(int x=0;x<n;x++)cout<<huda[x]<<" ";cout<<endl;
				int tmp=huda[n-p-c+1];
				for(int k=n-p-c+1;k<n-1;k++){
					huda[k]=huda[k+1];
				}
				huda[n-1]=tmp;
			}
		}
		cout<<huda[n-1]<<endl;
		for(int fjl=0;fjl<101;fjl++)huda[fjl]=0;
	}
	return 0;
}

Measured memory_bytes: 1156
N, M, X, Y = [int(n) for n in input().split()]
XC = [int(n) for n in input().split()]
YC = [int(n) for n in input().split()]

def main():
    max_x = max(XC)
    min_y = min(YC)
    if max_x < min_y and\
       set(range(X, Y)) & set(range(max_x, min_y)):
        print('No War')
    else:
        print('War')

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

vector<P> g[23];

int main(void){
	ll l,n=20,m=0,i,p=-1,x,j;
	for(i=1ll; i<n; ++i){
		g[i-1].push_back(P(i,0));
		++m;
	}
	cin >> l;
	x = l;
	while(x){
		++p; x /= 2;
	}
	for(i=0ll; i<p; ++i){
		g[i].push_back(P(i+1,(1<<i)));
		++m;
	}
	x = l;
	for(i=0ll; i<p; ++i){
		if(x%2 && x > 1){
			g[i].push_back(P(n-1,(x-1)*(1<<i)));
			++m;
		}
		x /= 2;
	}
	printf("%d %d\n",n,m);
	for(i=0; i<n; ++i){
		for(j=(g[i].l_ength()-1); j>=0; --j){
			printf("%d %d %d\n",i+1,(g[i][j].first+1),g[i][j].second);
		}
	}
	return 0;
}


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

int main()
{
	int n;
	std::string str;
	while (1)
	{
		std::cin >> n;
		if (n == 0)
			break;
		std::cin >> str;
		while (n > 0)
		{
			std::string str2;
			for (int i = 0; i != str.length(); ++i)
			{
				if (i > 0 && str[i - 1] == str[i])
					continue;
				int j = 1;
				while (i + j != str.length())
				{
					if (str[i] != str[i + j])
						break;
					j++;
				}
				str2 += std::to_string(j);
				str2 += str[i];
			}
			str = str2;
			//std::cout << str << std::endl;
			n--;
		}
		std::cout << str << std::endl;
	}
	return 0;
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> L(M), R(M);
    REP(i, M) cin >> L[i] >> R[i];
    ll maxL = 1, minR = N;
    REP(i, M)
    {
        maxL = max(maxL, L[i]);
        minR = min(minR, R[i]);
    }

    ll ans;
    if (maxL > minR) ans = 0;
    else ans = minR - maxL + 1;
    cout << ans << endl;
}


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

int main(){
    int n, A[100];
    cin >> n;
    for ( int i = 0; i < n; i++ ) cin >> A[i];
    
    for ( int i = n-1; i >= 0; i-- ) {
        if ( i != n-1) cout << " ";
        cout << A[i];
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 3100
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll I, O, T, J, L, S, Z, xx, jil=0;
  cin>>I>>O>>T>>J>>L>>S>>Z;
  xx=(I/2+J/2+L/2)*2;
  if(I>0&&J>0&&L>0){
    jil=3;I--;J--;L--;
  }
  jil+=(I/2+J/2+L/2)*2;
  cout<<max(xx,jil)+O<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main()
{
    int n, k, s; scanf("%d%d%d", &n, &k, &s);
    if (k == 0)
    {
        for (int i = 1; i <= n; i++) printf("%d%c", s == INF ? INF - 1 : INF, " \n"[i == n]);
        return 0;
    }
    for (int i = 1; i <= k; i++) printf("%d ", s);
    for (int i = k + 1; i <= n; i++) printf("%d%c", s == INF ? INF - 1 : INF, " \n"[i == n]);
    // int num = n - k + 1;
    // int x = s / num;
    // int y = x + s % num;
    // for (int i = 1; i <= n; i++) printf("%d%c", i % num == 0 ? y : x, " \n"[i == n]);
    return 0;
}

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

using namespace std;

int main(void){

    string str;
    int ans = 1000000007;

    cin >> str;

    string tmp;
    for(int i = 0;i < str.size()-2;i++){
        tmp = str.substr(i,3);
        if(abs(753-stoi(tmp)) < ans) ans = abs(753-stoi(tmp));
    }

    cout << ans << 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++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define mod 1000000007
#define INF 2000000000
typedef long long ll;
bool compare(pair<int, int> a, pair<int, int> b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}
// 入力



int main() {
    ll N;
    
    cin >>N;
    vector<ll> d(N); 
    rep(i,N){
        cin >> d[i];
    }
    ll sum = 0;
    rep(i,N){
        rep(j,N-i-1){
            sum += d[i]*d[j+i+1];
        }
    }
    cout << sum << endl;
    
    
    return 0;
    

}

Measured memory_bytes: 3608
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>

using namespace std;
const int N=1000005;
const int MOD=998244353;
typedef long long LL;

int n,m,fac[N],inv[N];
int Ans1,Ans2;

//LL gcd(LL x,LL y) {
//	if(!y) return x;
//	return gcd(y,x%y);
//}
//
//struct Data{
//	LL x,y;
//	Data(LL _x=0,LL _y=0) {x=_x; y=_y;}
//	friend Data operator+(const Data A,const Data B){
//		Data ret; ret.y=A.y*B.y; ret.x=A.x*B.y+A.y*B.x;
//		LL tmp=gcd(ret.x,ret.y); ret.x/=tmp; ret.y/=tmp;
//		return ret;
//	}
//	friend Data operator*(const Data A,const Data B){
//		Data ret; ret.x=A.x*B.x; ret.y=A.y*B.y;
//		LL tmp=gcd(ret.x,ret.y); ret.x/=tmp; ret.y/=tmp;
//		return ret;
//	}
//}ans;

inline int fast_pow(int x,int y){
	int ret=1;
	for(;y;y>>=1){
		if(y&1) ret=(LL)ret*x%MOD;
		x=(LL)x*x%MOD;
	}
	return ret;
}

inline int C(int x,int y){
	return (LL)fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}

int main(){
	scanf("%d%d",&n,&m);
	if(n>m) swap(n,m); fac[0]=inv[0]=1;
	int i;
	for(i=1;i<=n+m;i+=4){
		fac[i]=1ll*fac[i-1]*i%MOD;
		fac[i+1]=1ll*fac[i]*(i+1)%MOD;
		fac[i+2]=1ll*fac[i+1]*(i+2)%MOD;
		fac[i+3]=1ll*fac[i+2]*(i+3)%MOD;
	}
	for(;i<=n+m;i++) fac[i]=fac[i-1]*i%MOD;
	inv[n+m]=fast_pow(fac[n+m],MOD-2);
	for(int i=n+m-1;~i;i--) inv[i]=1ll*inv[i+1]*(i+1)%MOD;
	Ans1=1ll*2*m*C(n+m,n)%MOD; Ans2=fast_pow(C(n+m,n)*2%MOD,MOD-2);
	for(int i=1;i<=n;i++) {
		Ans1=Ans1+1ll*C(n-i+m-i,n-i)*C(i+i,i)%MOD;	
		Ans1%=MOD;
	}
	printf("%lld\n",1ll*Ans1*Ans2%MOD);
//	ans=ans+Data(1,2)*Data(C(n-i+m-i,n-i)*C(i+i,i),C(n+m,n));
//	printf("%lld\n",1ll*ans.x*fast_pow(ans.y,MOD-2)%MOD);
	return 0;	
}

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

#define nummax 100
#define arrmax 99
int top=0,S[1000];

void push(int);
int pop();

int main()
{
  int i,num,x,y;
  char moji[nummax],a;


  while(scanf("%s",moji)!= EOF )
    { 
	  if( moji[0] == '+' )
	    {
	     x = pop();
	     y = pop();
	     push(x+y);
	    }
	  else if( moji[0] == '-' )
	    {
	     x = pop();
	     y = pop();
	     push(y-x);
	    }
	  else if( moji[0] == '*')
	    {
	     x = pop();
	     y = pop();
	     push(x*y);
	    } 
	  else
	    {
	      num = atoi(moji);
	      push(num);
	    }
    }  

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

  return 0;
}

void push(int x)
{
  top++;
  S[top] = x;
}

int pop(void)
{
  top--; 
  return S[top+1];
}

Measured memory_bytes: 548
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Math;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            A();
        }

        static void A()
        {
            var ND = ReadSplitInt();
            var a = ND[1] * 2 + 1;
            Println(ND[0] / a + (ND[0] % a == 0 ? 0 : 1));
        }

        static List<long> ReadLines(long n)
        {
            var l = new List<long>();
            for (long i = 0; i < n; i++)
            {
                l.Add(ReadLong());
            }
            return l;
        }

        static void YESOrNO(bool e) => Println(e ? "YES" : "NO");

        static void YesOrNo(bool e) => Println(e ? "Yes" : "No");

        static IEnumerable<int> Range(int start, int stop)
        {
            if (start < 0 || stop < 0 || start > stop || (start <= 0 && stop <= 0))
                return new List<int>();

            return Enumerable.Range(start, stop - start);
        }

        static bool IsDigit(string str)
        {
            var i = 0;
            return int.TryParse(str, out i);
        }

        static int SumDigits(long num)
        {
            return num.ToString().Select(x => x.ToString()).Sum(int.Parse);
        }

        static int[] ToIntArray(string str)
        {
            return str.Select(x => x.ToString()).Select(int.Parse).ToArray();
        }

        static long Gcd(long a, long b) => b == 0 ? a : Gcd(b, a % b);
        static long Lcm(long a, long b) => a / Gcd(a, b) * b;

        static bool IsPrime(int x)
        {
            if (x <= 1 || (x != 2 && x % 2 == 0)) return false;
            if (x == 2) return true;

            for (int i = 3; i < x; i += 2)
                if (x % i == 0) return false;

            return true;
        }

        static string Read() => Console.ReadLine();
        static int ReadInt() => int.Parse(Read());
        static long ReadLong() => long.Parse(Read());

        static List<string> ReadSplit() => Read().Split().ToList();
        static List<int> ReadSplitInt() => Read().Split().Select(int.Parse).ToList();
        static List<long> ReadSplitLong() => Read().Split().Select(long.Parse).ToList();

        static void Print(object value) => Console.Write(value.ToString());
        static void Println(object value) => Console.WriteLine(value.ToString());

        static string Join<T>(IEnumerable<T> list) => string.Join("", list);
    }

    public static class MyExtensions
    {
        public static string Slice(this string str, int start = 0, int stop = 0)
        {
            if (start > str.Length || stop > str.Length || start < 0 || stop < 0)
                return "";

            if (stop == 0) stop = str.Length;
            return str.Substring(start, stop - start);
        }
    }
}


Measured memory_bytes: 11348
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
local function array(dimension, default_val) local n=dimension local m={}if default_val~=nil then m[1]={__index=function()return default_val end}end for i=2,n do m[i]={__index=function(p, k)local c=setmetatable({},m[i-1])rawset(p,k,c)return c end}end return setmetatable({},m[n])end
----

---
local MOD = math.floor(10^9) + 7
local L = read.l():totable()
local N = #L
local tbl = array(2, 0)
local FIT = 0
local SMALLER = 1
tbl[0][FIT] = 1

for i=1,N do
    -- decide tbl[i] from tbl[i-1]
    local ld = tonumber(L[i])
    local oldtbl = tbl[i-1]
    local newtbl = tbl[i]
    local function has_transition(na, nb, oldfs, newfs)
        if na == 0 and nb == 0 then
        elseif na == 0 and nb == 1 then
        elseif na == 1 and nb == 0 then
        elseif na == 1 and nb == 1 then
            return false
        end
        local constraint_digit = ld
        local new_digit = na + nb
        if oldfs == FIT and newfs == FIT then
            return new_digit == constraint_digit
        elseif oldfs == FIT and newfs == SMALLER then
            return new_digit < constraint_digit
        elseif oldfs == SMALLER and newfs == FIT then
            return false
        elseif oldfs == SMALLER and newfs == SMALLER then
            return true
        end
    end
    local function do_transition(newfs, oldfs)
        local v = oldtbl[oldfs]
        newtbl[newfs] = (newtbl[newfs] + v) % MOD
    end
    for na=0,1 do
        for nb=0,1 do
            for oldfs=0,1 do
                for newfs=0,1 do
                    if has_transition(na, nb, oldfs, newfs) then
                        do_transition(newfs, oldfs)
                    end
                end
            end
        end
    end
end
local ans = (tbl[N][FIT] + tbl[N][SMALLER]) % MOD
print(ans)

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

using namespace std;

using ll = long long;

#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 input(...) __VA_ARGS__; in(__VA_ARGS__)

template <class T>
void print(vector<T> a) {
  cout << "[ ";
  REP(i, a.size()) cout << a[i] << " ";
  cout << "]" << endl;
}

void print() {
  std::cout << std::endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cout << head << " ";
  print(std::forward<Tail>(tail)...);
}

void in() { }

template <class Head, class... Tail>
void in(Head&& head, Tail&&... tail) {
  cin >> head;
  in(std::forward<Tail>(tail)...);
}

ll n;
vector<ll> a;

int main() {
  cin >> n;
  a = vector<ll>(n);
  REP(i, n) {
    cin >> a[i];
    a[i]++;
  }

  ll amax = *max_element(a.begin(), a.end());
  vector<ll> dp(n + 1, 0);
  dp[0] = -(amax + 1);

  REPD(i, n) {
    ll index = distance(dp.begin(), upper_bound(dp.begin(), dp.end(), -(a[i] + 1)) - 1);
    dp[index + 1] = -a[i];
  }

  REPD(i, n + 1) {
    if (dp[i] != 0) {
      cout << i << endl;
      break;
    }
  }
}



Measured memory_bytes: 4384
import Data.List
import Data.Maybe
import qualified Data.ByteString.Char8 as BS
import Control.Monad

main = do
	[k, s] <- getIntList
	print $ length $ [(x, y, z) | x <- [0..k], y <- [0..k], let z = s - x - y, z >= 0 && z <= k && x + y + z == s]

-- IO --
readInt :: BS.ByteString -> Int
readInt = fst . fromJust . BS.readInt

readIntList :: BS.ByteString -> [Int]
readIntList = map readInt . BS.words

getInt :: IO Int
getInt = readInt <$> BS.getLine

getIntList :: IO [Int]
getIntList = readIntList <$> BS.getLine

Measured memory_bytes: 636
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    double a[n];
    double b=0;
    cout << fixed << setprecision(6);
    for(int i=0;i<n;i++){
        cin>>a[i];
        a[i]=1/a[i];
        b+=a[i];
    }
    cout<<1/b<<endl;
}

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

using namespace std;
using ll = long long;


int main() {
    int n,a;
    cin >> n;
    int nums[100002]={};
    for(int i=0;i<n;i++){
            cin >> a;
            nums[a-1]++,nums[a]++,nums[a+1]++;
    }
    int temp=0,ans;
    for(int i=0;i<=100001;i++){
        if(temp<nums[i]){
             temp=nums[i];
        }
    }
    cout << temp << endl;
	return 0;
}

Measured memory_bytes: 640
N = int(input())
if N==0:
  print(0)
  exit()

ans = []
while N != 0:
    if N % 2 == 1:
        ans.append("1")
        N -= 1
    else:
        ans.append("0")
    N //= - 2

ans = "".join(ans)[::-1]
print(ans)


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

vector<string> all;
int h, w;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

typedef pair<int, int> P;

void bfs(int x, int y){
	char c = all[y][x];
	all[y][x] = ' ';
	queue<P> q;
	q.push(P(x, y));
	while (!q.empty()){
		P p = q.front(); q.pop();
		for (int i = 0; i < 4; ++i){
			int tmpx = p.first + dx[i], tmpy = p.second + dy[i];
			if (0 <= tmpx && tmpx < w && 0 <= tmpy && tmpy < h && all[tmpy][tmpx] == c){
				all[tmpy][tmpx] = ' ';
				q.push(P(tmpx, tmpy));
			}
		}
	}
}

void solve(){
	int ans = 0;
	for (int i = 0; i < h; ++i){
		for (int j = 0; j < w; ++j){
			if (all[i][j] == '@' || all[i][j] == '#' || all[i][j] == '*'){
				bfs(j, i);
				++ans;
			}
		}
	}
	cout << ans << endl;
}

int main(){
	while (cin >> h >> w){
		if (h == 0 && w == 0)
			break;
		all.clear();
		for (int i = 0; i < h; ++i){
			string tmp;
			cin >> tmp;
			all.push_back(tmp);
		}
		solve();
	}
	return 0;
}

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

const int INF = 100100100;
const int MOD = (int)1e9 + 7;
typedef long long ll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main() {
  int n;
	cin >> n;
	vector<ll> ma(n);
	REP(i,n) cin >> ma[i];
	int ans = 0;
	REP(i,n) FOR(j,i+1,n) ans += ma[i] * ma[j];
  cout << ans << endl;
}


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

int main(){
	ll n,k;
	cin >> n >> k;
	string s;
	cin >> s;
	int score = 0;
	rep(i,n-1) {
		if(s[i] == s[i+1]) score++;
	}
	int ans = min(score+2*k, n-1);
	cout << ans <<endl;
	return 0;
}


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

// アナグラムの判定法
// 1: 文字種とその回数が一致することをsetなどで確認
// 2: ソートした結果が等しいかを確認

int main()
{
    int N;
    cin >> N;
    map<string, long long> table;
    for (int i = 0; i < N; i++)
    {
        string s;
        cin >> s;
        sort(s.begin(), s.end());
        table[s]++;
    }
    long long ans = 0;
    for (auto item : table)
    {
        ans += item.second * (item.second - 1) / 2;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 11136
#include <bits/stdc++.h>
typedef long long int ll;
#define FOR(i, a, b) for (ll i = (signed)(a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define EREP(i, n) for (int i = (n)-1; i >= 0; --i)
#define MOD 1000000007
#define pb push_back
#define INF 93193111451418101
#define MIN -93193111451418101
#define EPS 1e-11
#define tp(a, b, c) make_tuple(a, b, c)
#define lb(a, b) lower_bound((a).begin(), (a).end(), (b))
#define ub(a, b) upper_bound((a).begin(), (a).end(), (b))
using namespace std;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
template <typename T> void fill_all(T &arr, const T &v) { arr = v; }
template <typename T, typename ARR> void fill_all(ARR &arr, const T &v) {
  for (auto &i : arr) {
    fill_all(i, v);
  }
}
//------------------変数-----------------------//
ll n;
double sx, sy, gx, gy;
struct rou {
  double x, y, r;
};
std::vector<rou> v;
//-------------------関数----------------------//
struct edge {
  ll to;
  double cost;
  edge() {}
  edge(ll to_, double cost_) : to(to_), cost(cost_) {}
};
std::vector<edge> graph[1009];

// O(ElogV)ダイクストラ
double D[1009];
void Dijkstra(uint32_t s) {
  using P = std::pair<double, ll>; // cost pos
  std::priority_queue<P, std::vector<P>, std::greater<P>> que;
  std::fill(std::begin(D), std::end(D), (double)INF);

  D[s] = 0;
  que.emplace(0, s);
  while (!que.empty()) {
    auto p = que.top();
    que.pop();
    const auto &nowpos = p.second;
    const auto &nowcost = p.first;
    if (D[nowpos] < nowcost) {
      continue;
    }
    for (const auto &e : graph[nowpos]) {
      auto cost = nowcost + e.cost;
      if (cost < D[e.to]) {
        D[e.to] = cost;
        que.emplace(cost, e.to);
      }
    }
  }
}
int main() {
  cin >> sx >> sy >> gx >> gy;
  cin >> n;
  v.emplace_back(rou{sx, sy, 0});
  v.emplace_back(rou{gx, gy, 0});
  REP(i, n) {
    double xx, yy, rr;
    cin >> xx >> yy >> rr;
    v.emplace_back(rou{xx, yy, rr});
  }
  REP(i, (signed)v.size()) {
    REP(j, (signed)v.size()) {
      if (i == j)
        continue;
      double dis = pow((v[i].x - v[j].x), 2) + pow(v[i].y - v[j].y, 2);
      dis = sqrt(dis);
      dis -= v[i].r + v[j].r;
      if (dis < 0) {
        dis = 0;
      }
      graph[i].pb(edge{j, dis});
      graph[j].pb(edge{i, dis});
    }
  }
  Dijkstra(0);
  printf("%.10f\n", D[1]);
}


Measured memory_bytes: 38512
import heapq
n, m = map(int, input().split())
a = [int(i) * (-1) for i in input().split()]
heapq.heapify(a)
for i in range(m):
    x = heapq.heappop(a) * (-1) // 2
    heapq.heappush(a, x * (-1))
print(-sum(a))


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

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)
#define all(v) (v).begin(),(v).end()

#define PII pair<int,int>
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define debug(x) {cout <<#x <<" = " <<x <<endl; }
#define debug2(x,y) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y <<endl; } 
#define debug3(x,y,z) {cerr <<#x <<" = " <<x << ", "<<#y<<" = "<< y << ", " << #z << " = " << z <<endl; } 
#define debugv(x) {{cout <<#x <<" = "; FORE(itt, (x)) cerr <<*itt <<", "; cerr <<endl; }}
#define debugt(t,n) {{cerr <<#t <<" = "; FOR(it,0,(n)) cerr <<t[it] <<", "; cerr <<endl; }}

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
#define jeb() fflush(stdout);

using namespace std;

const int max_n = 1234567;
int deg[max_n];
VI g[max_n];

int nxt(int v, int p) {
	FORE(i, g[v]) {
		if (*i == p) continue;
		return *i;
	}
}

bool rob(int v, int start, int zab, int prev) {
	if (v == zab) return false;
	if (v == start) return true;
	int w = nxt(v, prev);
	return rob(w, start, zab, v);
}

int main() {
	make2(n, m);
	FOR(i,0,n) deg[i] = 0;
	FOR(i,0,m) {
		make2(a, b); a--; b--;
		g[a].pb(b);
		g[b].pb(a);
		deg[a]++;
		deg[b]++;
	}
	bool ok = true;
	FOR(i,0,n) {
		if (deg[i]%2 == 1) ok = false;
	}
	if (!ok) {
		printf("No\n"); return 0;
	}
	ok = false;
	int czwr = 0;
	FOR(i,0,n) {
		if (deg[i] >= 6) ok = true;
		if (deg[i] == 4) czwr++;
	}
	if (ok || (czwr >= 3)) {
		printf("Yes\n");
		return 0;
	} else if (czwr <= 1) {
		printf("No\n");
		return 0;
	}
	VI v;
	FOR(i,0,n) {
		if (deg[i] == 4) v.pb(i);
	}
	ok = false;
	FORE(i, g[v[0]]) {
		if (rob(*i, v[0], v[1], v[0])) {
			printf("Yes\n");
			return 0;
		} 
	}
	printf("No\n");
}






Measured memory_bytes: 34048
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        double m=sc.nextDouble();
		double s=0;

  		double[] a=new double[n];
		for(int c=0;c<n;c++){
    		a[c]=sc.nextInt();
          	s+=a[c];
    	}
  
  		double e=s/(4*m);
  		int count=0;
    
		for(int c=0;c<n;c++){
        	if(a[c]>=e){
            	count++;
            }
        }
 	if(count>=m){
    		System.out.println("Yes");
    	}else{
     		System.out.println("No");
   	 }



    }
}



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

using namespace std;

const int mod = 1e9 + 7;
int cnt[27];

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < n; ++i) ++cnt[s[i] - 'a'];
    int ans = 1;
    for (int i = 0; i < 26; ++i) ans = 1ll * ans * (cnt[i] + 1) % mod;
    ans = (ans + mod - 1) % mod;
    cout << ans << endl;
    return 0;
}


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

int main() {
  int64_t f[100][10];

  int n;
  std::cin >> n;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      std::cin >> f[i][j];
    }
  }

  int64_t p[100][11];

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 11; j++) {
      std::cin >> p[i][j];
    }
  }

  int64_t u = -10000000000;

  for (int i = 1; i < (1 << 10); i++) {
    int64_t u_t = 0;

    for (int j = 0; j < n; j++) {
      int c = 0;
      for (int k = 0; k < 10; k++) {
        if ((i & (1 << k)) != 0) {
          c += f[j][k];
        }
      }
      u_t += p[j][c];
    }
    u = std::max(u, u_t);
  }

  std::cout << u << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

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

    int n;
    cin >> n;
    double ans=0;
    if(n%2==0){ 
        ans=n/2;
        ans/=n;
        printf("%.10f\n",ans); 
        return 0;
    }
    ans = (n+1)/2;
    ans/=n;
    printf("%.10f\n",ans); 
    return 0;
}

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

using namespace std;
typedef long long LL;
int _max(int x, int y) {return x > y ? x : y;}
int _min(int x, int y) {return x < y ? x : y;}
int read() {
	int s = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
	return s * f;
}
void put(int x) {
	if(x >= 10) put(x / 10);
	putchar(x % 10 + '0');
}

int bin[19], ans[1 << 18];
int a[1 << 18], mx1[1 << 18], mx2[1 << 18];

int main() {
	int n = read();
	bin[0] = 1; for(int i = 1; i <= 18; i++) bin[i] = bin[i - 1] << 1;
	for(int i = 0; i < bin[n]; i++) a[i] = read(), mx1[i] = a[i];
	for(int i = 1; i < bin[n]; i <<= 1) {
		for(int j = 0; j < bin[n]; j += i << 1) {
			for(int k = 0; k < i; k++) {
				if(mx1[j + k] > mx1[j + k + i]) mx2[j + k + i] = mx1[j + k + i], mx1[j + k + i] = mx1[j + k];
				else if(mx1[j + k] > mx2[j + k + i]) mx2[j + k + i] = mx1[j + k];
				if(mx2[j + k] > mx2[j + k + i]) mx2[j + k + i] = mx2[j + k];
			}
		}
	} for(int i = 1; i < bin[n]; i++) ans[i] = mx1[i] + mx2[i], ans[i] = _max(ans[i], ans[i - 1]);
	for(int i = 1; i < bin[n]; i++) put(ans[i]), puts("");
	return 0;
}


Measured memory_bytes: 7168
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;cin>>n;
	string s;cin>>s;

	int ans = 0;
	unordered_set<char> st;
	st.insert(s[0]);

	for(int i=1;i<n;i++){
		unordered_set<char> tt;
		
		for( int j=i;j<n;j++ )tt.insert(s[j]);
		
		int cnt = 0;
		
		for(auto it:tt){
		    if(st.find(it)!=st.end())cnt++;
		}
		
// 		ans=max((unsigned long)ans,min(tt.size(),st.size()));
        ans=max(ans,cnt);
		st.insert(s[i]);
	}
	cout<<ans<<endl;
	return 0;

}

Measured memory_bytes: 3596
//! Framework <https://github.com/vain0x/procon>

#![allow(non_snake_case)]
#![allow(unused_imports)]

use std::collections::*;

pub struct Scan(Box<dyn Iterator<Item = &'static str>>); // '

impl Scan {
    fn new() -> Self {
        let mut buf = String::new();
        let read_line = move || {
            std::io::stdin().read_line(&mut buf).unwrap();
            Box::leak(buf.split_off(0).into_boxed_str()).split_whitespace()
        };
        Scan(Box::new(std::iter::repeat_with(read_line).flatten()))
    }

    pub fn word<T: std::str::FromStr>(&mut self) -> T {
        self.0.next().unwrap().parse().ok().unwrap()
    }

    pub fn list<T: std::str::FromStr>(&mut self, len: usize) -> Vec<T> {
        std::iter::repeat_with(|| self.word()).take(len).collect()
    }
}

fn main() {
    let mut scan = Scan::new();

    let c = scan.word::<String>().chars().next().unwrap();

    println!("{}", if c.is_ascii_uppercase() { "A" } else { "a" });
}


Measured memory_bytes: 2140
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

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

for i in range(m):
    for j in range(2):
        A[i][j] -= 1

U = UnionFind(n)
ans = n * (n-1) // 2
ANS = []
for i in range(m-1, -1, -1):
    ANS.append(ans)
    a = A[i][0]
    b = A[i][1]
    ua = U.find(a)
    ub = U.find(b)
    if ua != ub:
        ans -= U.parents[ua] * U.parents[ub]
        U.union(ua, ub)

for i in range(len(ANS)-1, -1, -1):
    print(ANS[i])

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

using namespace std;

#define rep(i) for(int i=0;i<2;i++)

const int K = 1024;
int sum[2][K<<1][K<<1];

void solve() {
    int n,k;
    cin >> n >> k;
    int m = k<<1;
    for (int _ = 0; _ < n; _++) {
        int x,y; char c;
        cin >> x >> y >> c;
        sum[c=='B'][x%m+1][y%m+1] += 1;
    }
    rep(c){
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= m; j++) {
                sum[c][i][j] += sum[c][i][j-1];
            }
            for (int j = 1; j <= m; j++) {
                sum[c][i][j] += sum[c][i-1][j];
            }
        }
    }
    auto q = [&](int c, int x,int y,int u,int v){
        return sum[c][u][v] - sum[c][x][v] - sum[c][u][y] + sum[c][x][y];
    };
    int res = 0;
    rep(c)
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            int w = 0;
            w += q(c, 0,0, k-i,k-j);
            w += q(c, m-i,0, m,k-j);
            w += q(c, 0,m-j, k-i,m);
            w += q(c, k-i,k-j, m-i,m-j);
            w += q(c, m-i,m-j, m,m);
            int b = 0;
            b += q(c^1, k-i,0, m-i,k-j);
            b += q(c^1, 0,k-j, k-i,m-j);
            b += q(c^1, m-i,k-j, m,m-j);
            b += q(c^1, k-i,m-j, m-i,m);
            res = max(res, w+b);
        }
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 33024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vii = vector<vi>;
using Pll = pair<ll, ll>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define F first
#define S second
const int MOD = 1e9+7;
const int INF = 2e9;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main(){
  ll n,m,x;
  cin >> n>>m>>x;
  vi c(n);
  vii a(n, vi(m));
  rep(i,n){
    cin >> c[i];
    rep(j,m){
      cin >> a[i][j];
    }
  }
  ll ans = INF;
  for (int tmp = 0; tmp < (1 << 12); tmp++){
    vi t(m,0);
    ll money = 0;
    bitset<12> s(tmp);
    // ビット列を出力
    rep(i,n){
      if(s[i]){
        money += c[i];
        rep(j,m){
          t[j] += a[i][j];
        }
      }
    }
    bool z = true;
    rep(i,m){
      if(t[i]<x){
        z = false;
      }
    }
    if(z){
      chmin(ans, money);
    }
  }
  if(ans==INF){
    print(-1);
  }
  else{
    print(ans);
  }
}

Measured memory_bytes: 3596
import java.io.*;
import java.util.StringTokenizer;

class Main{

static final PrintWriter out=new PrintWriter(System.out);
static boolean[] hasParent;

static class Node{
int id;
int p;
int rank;
int k;
int[] c;
String type;
Node(int id){
this.id=id; this.p=-1; this.rank=-1; this.type="internal node";
}
}

public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
int num=Integer.parseInt(br.readLine());
Node[] ns=new Node[num];
hasParent=new boolean[num];
StringTokenizer st;
StringBuilder sb;
for(int i=0;i<num;i++){
ns[i]=new Node(i);
}
for(int i=0;i<num;i++){
st=new StringTokenizer(br.readLine());
int id=Integer.parseInt(st.nextToken());
Node n=ns[id];
int k=Integer.parseInt(st.nextToken());
n.k=k;
if(k==0) n.type="leaf";
else{
n.c=new int[k];
for(int j=0;j<k;j++){
int c=Integer.parseInt(st.nextToken());
n.c[j]=c;
ns[c].p=id;
hasParent[c]=true;
}
}
}
for(int i=0;i<num;i++){
if(ns[i].rank<0) ns[i].rank=setRank(i,ns);
}
for(int i=0;i<num;i++){
Node an=ns[i];
sb=new StringBuilder();
sb.append("node ");
sb.append(i);
sb.append(": parent = ");
sb.append(an.p);
sb.append(", depth = ");
sb.append(an.rank);
sb.append(", ");
sb.append(an.type);
sb.append(", [");
if(an.k!=0){
for(int j=0;j<an.k;j++) sb.append((j==an.k-1)?an.c[j]:an.c[j]+", ");
}
sb.append("]");
sb.append(System.getProperty("line.separator"));
out.print(sb);
}
out.flush();
}

private static int setRank(int now,Node[] ns){
if(ns[now].rank>=0) return ns[now].rank;
if(!hasParent[now]){
ns[now].type="root";
return ns[now].rank=0;
}
return ns[now].rank=setRank(ns[now].p,ns)+1;
}
}

Measured memory_bytes: 84712
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const long long INF = 1e15;

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

    ll n;
    cin >> n;
    ll ans = 0;
    for(ll i = 1; i < n; i++){
        ans += n/i;
        if(n%i == 0) ans--;
    }
    cout << ans << endl;
    return 0;
}

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

int main(){

 ll k,n;
  
  cin >> k >> n;
  
  ll diffMax;
  ll first;
  ll pre;
  
  rep(i,n){
    ll current;
    ll diff;
    cin >> current;
    diff = current - pre;
    if(i == 0){
      first = current;
      pre = first;
      continue;
    }else if(i == n-1){
      diff = max(diff,(k - current) + first);
    }
    diffMax = max(diffMax,diff);
    pre = current;
  }
  
  cout << k - diffMax << 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)++)
#define OUT(a) cout << (a) << "\n"
#define ll long long
#define uint unsigned int
#define ushort unsigned short
#define ulong unsigned long

ll MOD = 10e9 + 7;

int main() {
    int n,d;
    cin >> n >> d;
    int range = d*2+1;
    cout << (n+range-1) / range << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
robots = []
for _ in range(n):
    x, l = map(int, input().split())
    robots.append((x + l, x - l))
robots.sort()

cur = -float('inf')
ans = 0
for i in range(n):
    t, s = robots[i]
    if cur <= s:
        ans += 1
        cur = t

print(ans)

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

char biggest_char(string s) {
  char res = s[0];
  rep(i, s.size()) res = max(res, s[i]);
  return res;
}

int main() {
  int n;
  cin >> n;
  set<string> ans;
  queue<string> que;
  que.push("a");
  while (1) {
    string s = que.front();
    que.pop();
    if (s.size() > n) break;
    if (s.size() == n) ans.insert(s);
    char b = biggest_char(s);
    for (char c = 'a'; c <= b+1; ++c) {
      string ns = s + c;
      que.push(ns);
    }
  }
  for (auto itr = ans.begin(); itr != ans.end(); ++itr) cout << *itr << endl;
  return 0;
}

Measured memory_bytes: 34572