akhauriyash/Code-Regression huggingface dataset:
// Author -- xyr2005

#include<bits/stdc++.h>

#define lowbit(x) ((x)&(-(x)))
#define Finline __inline__ __attribute__ ((always_inline))
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pl;
using std::min;
using std::max;

const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x3f3f3f3f3f3f3f3f;

Finline uint rnd(){static uint seed=416;return seed+=0x71dad4bfu,seed^=seed>>5,seed+=0xc6f74d88u,seed^=seed<<17,seed+=0x25e6561u,seed^=seed>>13;}
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return (!b)?a:gcd(b,a%b);}
template <typename _Tp>Finline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>Finline void chmax(_Tp &a,const _Tp &b){(a<b)&&(a=b);}
template <typename _Tp>Finline void chmin(_Tp &a,const _Tp &b){(b<a)&&(a=b);}
template <typename _Tp>Finline void read(_Tp &x)
{
	char ch(getchar());bool f(false);while(!isdigit(ch)) f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch)) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
	f&&(x=-x);
}
template <typename _Tp,typename... Args>Finline void read(_Tp &t,Args &...args){read(t);read(args...);}
template <typename _Tp,typename... Args>Finline _Tp min(const _Tp &a,const _Tp &b,const Args &...args){return a<b?min(a,args...):min(b,args...);}
template <typename _Tp,typename... Args>Finline _Tp max(const _Tp &a,const _Tp &b,const Args &...args){return a<b?max(b,args...):max(a,args...);}
Finline int read_str(char *s)
{
	char ch(getchar());while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
	char *tar=s;*tar=ch,ch=getchar();while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *(++tar)=ch,ch=getchar();
	return tar-s+1;
}

const int N=(1<<21)+5;
int pool[N<<5],*p=pool;
int *dp[N];
int len[N],num[N],fir[N][2];
char t[N];
int main()
{
	int n,k;read(n,k);
	int cur=0;
	for(int i=0;i<=n;++i)
	{
		read_str(t);
		for(int j=0;j<1<<i;++j)
		{
			len[cur]=i,num[cur]=j;
			dp[cur]=p,p+=(1<<(n-i+1));
			if(t[j]=='1') dp[0][cur]=1;
			fir[cur][0]=fir[cur][1]=-1;
			for(int k=i-1;k>=0;--k) if(fir[cur][(j>>k)&1]==-1) fir[cur][(j>>k)&1]=k;
			++cur;
		}
	}
	cur=0;
	int ans=0,len=0;
	for(int i=0;i<=n;++i)
	{
		for(int j=0;j<1<<i;++j)
		{
			int tmp=0;
			for(int p=0;p<=n-i;++p)
			{
				for(int q=0;q<1<<p;++q)
				{
					if(~fir[tmp][0]) dp[(1<<(i+1))-1+(j<<1)][(1<<fir[tmp][0])-1+(q&((1<<fir[tmp][0])-1))]+=dp[cur][tmp];
					if(~fir[tmp][1]) dp[(1<<(i+1))-1+(j<<1|1)][(1<<fir[tmp][1])-1+(q&((1<<fir[tmp][1])-1))]+=dp[cur][tmp];
					if(tmp) dp[cur][0]+=dp[cur][tmp];
					++tmp;
				}
			}
			if(dp[cur][0]>=k&&i>len) ans=j,len=i;
			++cur;
		}
	}
	for(int i=len-1;i>=0;--i) putchar(48+((ans>>i)&1));
	putchar('\n');
	return 0;
}


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

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

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

//ａをbで割る
long long mod_div(long long a,long long b){
	if(a % b == 0)return a/b;
	long long tmp = MOD - 2,c = b,ret = 1;
	while(tmp > 0){
		if(tmp & 1){
			ret *= c;ret %= MOD;
		}
		c *= c;c %= MOD;tmp >>= 1;
	}
	return a*ret%MOD;
}
 
#define MAX_K 333333
vector<long long> kaijo(MAX_K);
long long combination(long long n, long long r){
    if(n < r || n < 0 || r < 0)
        return 0;
	if(kaijo[0] != 1){
		kaijo[0] = 1;
		for(long long i = 1;i < MAX_K;i++)kaijo[i] = (kaijo[i-1] * i) % MOD;
	}
    long long ret = kaijo[n];
	long long tmp = (kaijo[r] * kaijo[n-r]) % MOD;
    return mod_div(ret,tmp);
}

ll mpow(ll a,ll b){
	ll ret = 1;
	ll tmp = a;
	for(ll i = 0;i <= 60;i++){
		if(b & (1LL << i)){
			ret *= tmp;
			ret %= MOD;
		}
		tmp *= tmp;
		tmp %= MOD;
	}
	return ret;
}

ll comb[1111][1111];
ll dp[1111][1111];

int main(){
	
	ll n,a,b,c,d;cin >> n >> a >> b >> c >> d;
	dp[0][0] = 1;
	
	REP(i,1111){
		REP(j,1111){
			if(j == 0 || i == j)comb[i][j] = 1;
			else comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) % MOD;
		}
	}
		
	REP(i,b+1){
		REP(j,n+1)if(dp[i][j]){
			dp[i+1][j] += dp[i][j];
			dp[i+1][j] %= MOD;
			if(i < a)continue;
			ll kake = 1;
			for(ll k = 1;k <= d;k++){
				ll tmp = i * k;
				if(j + tmp > n)break;
				kake = (kake * comb[n-j-tmp+i][i]) % MOD;
				kake = mod_div(kake, k);
				if(k < c)continue;
				dp[i+1][j+tmp] += (dp[i][j] * kake) % MOD;
				dp[i+1][j+tmp] %= MOD;
			}
		}
	}
	
	SHOW2d(comb,10,10);
	SHOW2d(dp,10,10);
	
	cout << dp[b+1][n] << endl;
	
	return 0;
}


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

#define W 1000
#define N 1000

int w, n, vi, wi, maxv, maxw;
int dp[N+1][W+1];
int values[N+1];
int weights[N+1];

int main(){
    int caseNum = 1;
    while(1){
        scanf("%d", &w);
        if(w == 0)  break;

        scanf("%d\n", &n);
        memset(dp, 0, sizeof(dp));
        memset(values, 0, sizeof(values));
        memset(weights, 0, sizeof(weights));

        for(int i = 0; i < n; i++){
            scanf("%d,%d\n", &values[i+1], &weights[i+1]);
        }

        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= w; j++){
                if(j >= weights[i]){
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i]]+values[i]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        maxv = -1;
        maxw = -1;
        for(int i = 0; i <= w; i++){
            if(maxv < dp[n][i]){
                maxv = dp[n][i];
                maxw = i;
            }
        }

        printf("Case %d:\n%d\n%d\n", caseNum, maxv, maxw);
        caseNum++;
    }
    
    return 0;
}



Measured memory_bytes: 7104
#include <stdio.h>

int main(){
  int a, b;

  scanf("%d %d\n", &a, &b);
  
  if(a < b)
    printf("a < b\n");
  if(a > b)
    printf("a > b\n");
  if(a == b)
    printf("a == b\n");
      
  return 0;
}

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

int main(){
	int a[105];
	int n;
	int x=0;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	for(int j=0;j<n;j++){
		if(a[j]%2==1)
		{
			continue;
		}
		else if(a[j]%2==0)
	    {
			if(a[j]%3!=0&&a[j]%5!=0){
				cout<<"DENIED"<<endl;
				return 0;
			}
			
		}
	}
	
	
	
	cout<<"APPROVED"<<endl;
	
	return 0;
}


Measured memory_bytes: 256
//
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
#define rp(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(),(x).end()

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

	map<int,int> C;//<rate,count>
	rp(i,N){
		int a; cin>>a;
		if(a<400){C[400]++;}
		else if(a<800){C[800]++;}
		else if(a<1200){C[1200]++;}
		else if(a<1600){C[1600]++;}
		else if(a<2000){C[2000]++;}
		else if(a<2400){C[2400]++;}
		else if(a<2800){C[2800]++;}
		else if(a<3200){C[3200]++;}
		else{C[4801]++;}
	}
	int maxR=0, maxC=0;
	for(auto e:C){
		int r,c; tie(r,c)=e;
		if(maxR<r){
			maxR=r;
			maxC=c;
		}
	}
	int n = C.size();
	if(maxR<4801){
		printf("%d %d\n", n, n);
	}
	else{
		if(n>1) printf("%d %d\n", n-1, n-1+maxC);
		else  printf("%d %d\n", 1, maxC);
	}
}


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

const long long N = 1e3 + 17;
ll cnt, ans, lnt, sum, n, l1, x, y, a[N], mx, b[N][N];
pair<ll,ll>pr[N];
vector<ll>v,v2,v3;
map<ll,ll>mp;
bool used[N], t1, t2;
vector<string>sv;

int main()
{
    cin >> n;
    string s;
    double rate = 380000.0;
    double ans = 0.0;
    for(ll i = 0; i < n; i ++)
    {
        double q1;
        cin >> q1 >> s;
        if(s == "BTC")
        {
           ans += q1 * rate;
        }
        else
        {
            ans += q1;
        }
    }
    printf("%.8f", ans);
    //cout << "\nTime Elapsed : " << clock () * 1.0 / CLOCKS_PER_SEC << endl;
}


Measured memory_bytes: 256
import sys
from functools import reduce

def gcd(a, b):
    while b:
        a, b = b, a % b
    return abs(a)

def lcm(a, b):
    return abs(a // gcd(a, b) * b)

n, m, *a = map(int, sys.stdin.read().split())

def main():
    for i in range(n):
        a[i] //= 2

    res = 1
    while True:
        oe = a[0] & 1
        if oe == 0:
            for i in range(n):
                if a[i] & 1 == 1:
                    return 0
                a[i] //= 2
            res *= 2
        else:
            for i in range(n):
                if a[i] & 1 == 0:
                    return 0
            break
        
    l = reduce(lcm, a, a[0]) * res
    
    return m // l - m // (l * 2)

if __name__ == '__main__':
    ans = main()
    print(ans)

Measured memory_bytes: 14588
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  if (A * B < C * D) {
  	cout << C * D << "\n";
  }else {
  	cout << A * B << "\n";
  }
}

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


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

if(x==25)
{
	cout << "Christmas" <<  endl;
}
else if(x==24)
{
	cout << "Christmas Eve" << endl;
}
else if(x==23)
{
	cout << "Christmas Eve Eve" << endl;
}
else
{
	cout << "Christmas Eve Eve Eve" << endl;
}
	return 0;
}












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

using P = pair<int, int>;

constexpr int MAX_H = 50;
constexpr int MAX_W = 50;

int H, W;
char grid[MAX_H][MAX_W + 1];

#define OCTAS
#ifdef OCTAS
constexpr int dh[]{-1, -1, -1, 0, 0, +1, +1, +1};
constexpr int dw[]{-1, 0, +1, -1, +1, -1, 0, +1};
#else
constexpr int dh[]{-1, 0, 0, +1};
constexpr int dw[]{0, -1, +1, 0};
#endif

int main() {
  scanf("%d%d", &H, &W);
  for (int h{}; h < H; ++h) {
    scanf("%s", &grid[h][0]);
  }

  for (int h{}; h < H; ++h) {
    for (int w{}; w < W; ++w) {
      if (grid[h][w] == '#')
        continue;
      char count{};
      for (int i{}; i < sizeof(dh) / sizeof(int); ++i) {
        int nh = h + dh[i];
        if (nh < 0 || nh >= H)
          continue;
        int nw = w + dw[i];
        if (nw < 0 || nw >= W)
          continue;
        if (grid[nh][nw] == '#')
          ++count;
      }
      grid[h][w] = '0' + count;
    }
  }

  for (int h{}; h < H; ++h) {
    printf("%s\n", &grid[h][0]);
  }

  return 0;
}


Measured memory_bytes: 256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()

using namespace std ;
using ll = long long ;
using ld = long double ;
using pii = pair <int , int> ;

int const N = 2000 + 20 , MX = N * N ;
int n , a[N] , sum ;
bitset <MX> bt ;

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

	bt[0] = 1 ;

	cin >> n ;
	for (int i = 0 ; i < n ; i ++) {
		cin >> a[i] ;
		sum += a[i] ;
		bt = bt | (bt << a[i]) ;
	}

	for (int i = (sum + 1) / 2 ; i <= sum ; i ++)
		if (bt[i] == 1) return cout << i << '\n' , 0 ;
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
using namespace std;
int main(){
  int X;
  cin >> X;
  int val = 0;
  int ans = 1;
  while (val < X) {
    val = (ans * (1 + ans))/2;
    ans++;
  }
  cout << max(ans - 1,1) << endl;
}



Measured memory_bytes: 256
S = input()
Rnum = S.split('L')
Rnum = [len(i) for i in Rnum if i != '']
Lnum = S.split('R')
Lnum = [len(i) for i in Lnum if i != '']
res = [0]*len(S)
count = 0
for i,r in enumerate(Rnum):
    l = Lnum[i]
    res[r+count-1] = int((r+1)/2) + int(l/2)
    res[r+count] = int(r/2) + int((l+1)/2)
    count += r+l
for i,r in enumerate(res):
    if i!= len(res)-1:
        print(r,end=' ')
    else:
        print(r)

Measured memory_bytes: 5864
/*
Created on 14-09-20 12:20

@author: roastedcoder

*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9+7;
const int INF = INT_MAX;
#define endl "\n"
#define pb push_back
#define roastedcoder ios_base::sync_with_stdio(false); cin.tie(NULL);
//__________________________________________________________________

ll power(ll a, ll b) {
	ll res = 1;
	while(b) {
		if(b%2) res = (res*a)%mod;
		a = (a*a)%mod;
		b /= 2;
	}
	return res%mod;
}

int main() {
	roastedcoder
	ll n; cin>>n;
	ll tmp = (power(9, n) + power(9, n))%mod;
	
	tmp = (tmp - power(8, n))%mod;
	ll res = (power(10, n) - tmp)%mod;
	cout<<(res+mod)%mod<<endl;
	return 0;
}

//__________________________________________________________________
/*
Sample Input:
869121

Sample Output:
2511445

*/



Measured memory_bytes: 3656
n = int(input())
lst = list(map(int, input().split()))

count = {}

for i in lst:
    if i in count.keys():
        count[i]+=1
    else:
        count[i]=1
# print(count)

ans = 0
for i in count:
    if count[i]>=i:
        ans += count[i]-i
    else:
        ans += count[i]
print(ans)


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

int main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> p(n, k-q);
  rep(i, q) {
    int a;
    cin >> a;
    --a;
    ++p[a];
  }
  rep(i, n) {
    if(p[i] <= 0) puts("No");
    else puts("Yes");
  }
  return 0;
}

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

int main() {
    int a,b,c;
    cin >> a >> b >> c;
    if(a==b && b==c){
        cout << 1;
    }
    else if(a!=b && b!=c && c!=a){
        cout << 3;
    }
    else{
        cout << 2;
    }
}

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

using namespace std;
int dp[100005],h[100005];
int main()
{
    int n,i,k = 2,j;
    cin >> n;
    for(i = 1;i <= n;i++)
        cin >> h[i];
    for(i = 1;i <= n;i++){
        if(i > 1)
            dp[i] = 2e9;
        for(j = i - 1;j >= i - k;j--){
            if(j >= 1)
                dp[i] = min(dp[j] + abs(h[i] - h[j]),dp[i]);
        }
    }
    cout << dp[n];
    return 0;
}


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

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

	if((N>0 || N>101) && (W<0 || W>10001)){
		return -1;
	}
	
	int v[N],w[N];
	for(int i=0; i<N; i++){
		cin >> v[i] >> w[i];

	if((v[i]<0 || v[i]>1001) && (w[i] <0 || w[i]>1001)){
		return -1;
	}
	}

	int DP[N+1][W+1];
	
	for(int j=0; j<=W; j++)
		DP[0][j] = 0;
	
	for(int i=1; i<=N; i++)
		for(int j=0; j<=W; j++)
			if(j<w[i-1])
				DP[i][j] = DP[i-1][j];
			else{
				if(DP[i-1][j]>DP[i-1][j-w[i-1]]+v[i-1])
					DP[i][j] = DP[i-1][j];
				else
					DP[i][j] = DP[i-1][j-w[i-1]]+v[i-1];
			}
			
		
	cout << DP[N][W] <<endl;

	return 0;
}

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

int main() {
  int H,W;
  cin>>H>>W;
  string map[H];
  for(int i=0;i<H;i++){
    cin>>map[i];
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(map[i][j]=='.'){
        int c=0;
        for(int k=-1;k<2;k++){
          for(int l=-1;l<2;l++){
            if(map[i+k][j+l]=='#'){
              c++;
            }
          }
        }
        string C=to_string(c);
        map[i][j]=C[0];
      }
    }
  }
  for(int i=0;i<H;i++){
    cout<<map[i]<<endl;
  }
  
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <utility>
#include <cmath>
#include <climits>

#define ll long long int
#define pb push_back
#define mk make_pair
#define pq priority_queue

using namespace std;
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;

int main(int argc, char const* argv[])
{
  int n;
  cin >> n;

  int k;
  for(int i = 1; i < 1000; i++){
    if(2 * n == i * (i + 1)){
      k = i;
      break;
    }else if(2 * n < i *  (i + 1)){
        cout << "No" << endl;
        return 0;
    }
  }
  cout << "Yes" << endl;
  cout << k + 1 << endl;
  vector<vector<int> > vec;
  vec.resize(k + 1);
  int fin = 1;
  for(int i = 0; i < k; i++){
    for(int j = 0; j < k - i; j++){
      vec[i].pb(fin + j);
    }
    for(int j = 0; j < k - i; j++){
      vec[j + i + 1].pb(fin + j);
    }
    fin = fin + k - i;
  }
  for(int i = 0; i < k + 1; i++){
    cout << k << " ";
    for(int j = 0; j < k; j++){
      cout << vec[i][j];
      if(j != k - 1)cout << " ";
    }
    cout << endl;
  }
	return 0;
}


Measured memory_bytes: 2304
import java.util.*;
import java.io.PrintWriter;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static final int MOD = 1000000007;
	public static ArrayList<Integer> list = new ArrayList<>();
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		int m = parseInt(sc.next());
		int[] s = new int[m];
		int[] c = new int[m];
		for (i = 0; i < m; i++) {
			s[i] = parseInt(sc.next());
			c[i] = parseInt(sc.next());
		}
		sc.close();
		int[] a = new int[n];
		for (i = 0; i < a.length; i++) {
			a[i] = -1;
		}
		boolean f=true;
		for (i = 0; i < m; i++) {
			if(a[s[i]-1] == -1) {
				a[s[i]-1] = c[i];
			} else if(a[s[i]-1] != c[i]) {
				f = false;
				break;
			} 
		}
		if(f) {
			for (i = 0; i < n; i++) {
				if(i < n-1 && a[i]==0) {
					f = false;
					break;
				} 
				if(a[i]==-1) {
					if(i == 0 && n > 1) {
						a[i]=1;
					} else {
						a[i]=0;
					}
				}
			}
		}
		if(f) {
			for (i = 0; i < a.length; i++) {
				out.print(a[i]);
			}
			out.println();
		} else {
			out.println(-1);
		}
	}
}


Measured memory_bytes: 23892
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp> // Common file 
//#include <ext/pb_ds/tree_policy.hpp> 
#define int long long
#define pb push_back
#define ff first
#define ss second
#define ii insert
#define ld long double
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define ppb pop_back
#define nuenxfiu ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define input freopen("input.txt", "r", stdin),freopen("output.txt", "w", stdout);
#define TT int testcases;cin>>testcases;while(testcases--)
#define mk make_pair
#define MAX ((int)2e9+17)
#define mod ((int)1e9+7)
#define MOD 1000003
//int fact[1000007]={0};
#define N (int)1e6+10
int fpow(int n, int k, int p = mod) {int r = 1; while(k > 0) {if (k & 1) r = r * n%p; n = n * n%p; k = k >> 1;} return r;}
int expo(int x,int y){ int res=1; while(y) {if(y%2) res=(res*x%mod)%mod; x=(x*x)%mod; y/=2; } return res;}
int sub(int a, int b) {return (a%mod - b%mod + mod)%mod;}
int mul(int a, int b) {return ((a%mod)*(b%mod) + mod)%mod;}
int inv(int x) {return expo(x, mod-2);}
using namespace std;



void solve()
{
	int x;;
	cin>>x;
	
	vector<pair<int,int>>v;
	
	for(int i=0;i*i*i*i<=1e18/i;i++)
	{
		v.pb({i*i*i*i*i,i});
		v.pb({-i*i*i*i*i,-i});
	}	
	
	sort(v.begin(),v.end());
	
	int q=sz(v);
	
	for(int i=1;i<q;i++)
	{
		for(int j=0;j<i;j++)
		{
			if(v[i].ff-v[j].ff==x)
			{
				cout<<v[i].ss<<" "<<v[j].ss<<endl;
				return ;
			}
		}
	}
}
signed main()
{
    
	nuenxfiu
	//TT
	solve();
     return 0;
}

Measured memory_bytes: 3748
n=int(input())
l=[list(map(int,input().split())) for _ in range (n)]
for z in range(n):
    l[z][0],l[z][1]=l[z][1],l[z][0]
l.sort()
t=0
for i in range(n):
    t+=l[i][1]
    if t>l[i][0]:
        print("No")
        exit()
print("Yes")



Measured memory_bytes: 52328
#include <iostream>
#include <iomanip>
#include<vector>
#include <algorithm>
#include <queue>
#include<string>
#include <map>
#include <cmath>
#include <deque>
#include <list>
#include <stack>
#include <queue>
#include <utility>
#include <set>
#include <bitset>
typedef long long ll;
typedef long double ld;

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

int main() {
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int ansT1 = C / B;
    int ansA1 = A / D;
    int ansT2 = C % B;
    int ansA2 = A % D;
    if (ansT2!=0) {
        ansT1++;
    }
    if (ansA2!=0) {
        ansA1++;
    }
    if (ansT1<=ansA1) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

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

int main() {
  ll n;
  cin >> n;
  for (ll i = 1; i <= 3500; i++){
    for (ll j = 1; j <= 3500; j++){
      ll numerator = i * j * n;
      ll denominator = 4 * i * j - n * (i + j);
      if(denominator <= 0)continue;
      if(numerator % denominator == 0){
        ll num = numerator / denominator;
        cout << i << " " << j << " " << num << endl;
        return 0;
      }
    }
  }
}

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

int main(){
	int in, ans;
	cin >> in;

	if(in >= 400 && in <= 599)
		ans = 8;
	else if(in >= 600 && in <= 799)
		ans = 7;
	else if(in >= 800 && in <= 999)
		ans = 6;
	else if(in >= 1000 && in <= 1199)
		ans = 5;
	else if(in >= 1200 && in <= 1399)
		ans = 4;
	else if(in >= 1400 && in <= 1599)
		ans = 3;
	else if(in >= 1600 && in <= 1799)
		ans = 2;
	else
		ans = 1;

	cout << ans;
}


Measured memory_bytes: 3632
from collections import defaultdict


def create_id(p, o):
    return str(p).zfill(6) + str(o).zfill(6)


n, m = [int(i) for i in input().split()]
db = defaultdict(list)
for i in range(m):
    p, y = [int(i) for i in input().split()]
    db[p].append((y, i))

ans = [None] * m
for p in db:
    db[p].sort()
    for i in range(len(db[p])):
        ans[db[p][i][1]] = create_id(p, i + 1)
print(*ans, sep="\n")


Measured memory_bytes: 46308
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<numeric>
#include<utility>

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

#define INF 1000000000
#define MOD 1000000007

typedef  long long ll;

using namespace std;

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

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

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

ll gcd(ll  a,ll b){
    ll r;
    if(a < b){
        ll tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r = a % b){
        a = b;
        b = r;
    }
    return b;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

ll r_fuct[2000];
ll fuct[2000];

//MOD逆元
void conb(ll n,ll k){
    fuct[0] = 1;
    for(int i = 1;i < k+1;i++){
        fuct[i] *= fuct[i-1]%MOD;
        
        ll b = MOD, u = 1, v = 0;
        ll value = fuct[i];
        while (b) {
            ll t = value / b;
            value -= t * b;
            swap(value, b);
            u -= t * v;
            swap(u, v);
        }
        u %= MOD;
        if (u < 0) u += MOD;
        r_fuct[i] = u;
    }
}

void solve() {
   int a,b;
   cin >> a >> b;
   cout << max(max(a+b,a-b),a*b) << endl;
}

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	solve();
	return 0;
}


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

using namespace std;


void replace(string* s, long index, string oneword, long k) {
	string word = "";
	for (long i = 0; i < k; i++) {
		word += oneword;
	}
	if (index == 0) {
		*s = word + s->substr(index + word.length(), s->length() - word.length());
	}
	else if (index + word.length() == s->length()) {
		*s = s->substr(0, index) + word;
	}
	else {
		*s = s->substr(0, index) + word + s->substr(index + word.length(), s->length() - word.length() - index);
	}
}

void replace(string* s,long index, string word) {

	if (index == 0) {
		*s = word + s->substr(index + word.length(),s->length()-word.length());
	}
	else if (index + word.length() == s->length()) {
		*s = s->substr(0, index) + word;
	}
	else {
		*s = s->substr(0, index) + word + s->substr(index + word.length(), s->length() - word.length() - index);
	}
}

int main() {
	string kari_s;
	cin >> kari_s;
	string s = "";
	long answer = 0;
	bool flug = true;
	
	if (kari_s.length() < 3) {
		cout << 0 << endl;
		return 0;
	}

	for (long i = 0; i < kari_s.length(); i++) {
		if (i == kari_s.length() - 1) {
			s += kari_s.substr(i, 1);
			break;
		}
		else {
			if (kari_s.substr(i, 2) == "BC") {
				s += "D";
				i++;
			}
			else {
				s += kari_s.substr(i, 1);
			}
		}
	}

	long tenti = 0;

	for (long i = 0; i < s.length(); i++) {
		if (s.substr(i, 1) == "A") {
			tenti++;
		}
		else if (s.substr(i, 1) == "D") {
			answer += tenti;
		}
		else {
			tenti = 0;
		}
	}
	cout << answer << endl;

	return 0;
}

Measured memory_bytes: 776
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define int long long
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define fast  ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mod 1000000007
// order_of_key and *find_by_order
int32_t main()
{
	fast;
	int x;
	cin >> x;
	vector<int > v;
	map<int, int > m;
	for (int i = 0; i < 1500; i++) {
		int ans = i * i * i * i * i;
		v.push_back(ans);
		v.push_back(-1 * ans);
		m[ans] = i;
		m[-ans] = -i;
	}
	for (auto it : m) {
		if (m.find(x + it.first) != m.end()) {
			cout   << m[x + it.first] << " " << it.second;
			return 0;
		}
	}







}

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

typedef long long ll;

ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

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

    ll g = gcd(A, B);

    int res = 1;
    for (ll i = 2; i * i <= g; i++) {
        if (g % i == 0) {
            res++;
            while (g % i == 0) {
                g /= i;
            }
        }
    }
    if (g != 1) res++;

    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define REP(i, a, b) for (ll i = a; i < b; i++)
typedef pair<ll,ll> pi;
typedef vector<ll> vi;
ll mod = 1e9 + 7;
ll k;
string s;

ll f[2000005];
ll invf[2000005];
ll p26[2000005];
ll p25[2000005];

ll power(ll a, ll b){
	a %= mod;
	if (b == 0) return 1;
	if (b == 1) return a;
	ll half = power(a, b/2);
	half *= half;
	half %= mod;
	if (b % 2 == 1){
		half *= a;
		half %= mod;
	}
	return half;
}

void init(){
	f[0] = 1;
	p25[0] = 1;
	p26[0] = 1;
	invf[0] = power(f[0], mod - 2);
	REP(i, 1, 2000001){
		f[i] = i*f[i - 1];
		f[i] %=mod;
		invf[i] = power(f[i], mod - 2);
		p25[i] = p25[i - 1]*25;
		p25[i]%=mod;
		p26[i] = p26[i - 1]*26;
		p26[i]%=mod;
	}
}

ll choose(ll n, ll k){
	return (((f[n]*invf[n - k])%mod)*invf[k])%mod;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	init();
	cin >> k;
	cin >> s;
	ll answer = 0;
	ll t = k + s.length();
	REP(i, (int)s.length() - 1, t){
		ll curans = 1;
		curans *= p26[t - 1 - i];
		//curans *= power((ll)26, t - 1 - i);
		curans *= choose(i, (ll)s.length() - 1);
		curans %= mod;
		//curans *= power((ll)25, i - (s.length()-1));
		curans *= p25[i - (s.length() - 1)];
		curans %= mod;
		answer += curans;
		answer %= mod;
	}
	cout << answer << endl;
}

Measured memory_bytes: 66756
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		String result = "a == b";

		if (a > b) {
			result = "a > b";
		}	
		if (a < b) {
			result = "a < b";
		}

		System.out.println(result);
	}
}

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


int main()
{
	int l, r;
	cin >> l >> r;

	int l_q = l / 2019;
	int l_r = l % 2019;
	int r_q = r / 2019;
	int r_r = r % 2019;

	int ans;
	if (l_q == r_q) {
		int min = 2018;
		for (int i = l_r; i < r_r; i++) {
			for (int j = l_r + 1; j <= r_r; j++) {
				int r = (i * j) % 2019;
				if (r < min) {
					min = r;
				}
			}
		}
		ans = min;
	} else {
		ans = 0;
	}

	cout << ans << endl;
}


Measured memory_bytes: 256
a = gets.split.map(&:to_i)
b = gets.split.map(&:to_i)
c = gets.split.map(&:to_i)
A=[]
B=[]
C=[]
if a[5]-a[2]<0
  A[2] = a[5]+60-a[2]
  a[4] = a[4]-1
else
  A[2] = a[5]-a[2]
end

if a[4]-a[1]<0
  A[1] = a[4]+60-a[1]
  a[3] = a[3]-1
else
  A[1] = a[4]-a[1]
end

A[0] = a[3]-a[0]

if b[5]-b[2]<0
  B[2] = b[5]+60-b[2]
  b[4] = b[4]-1
else
  B[2] = b[5]-b[2]
end

if b[4]-b[1]<0
  B[1] = b[4]+60-b[1]
  b[3] = b[3]-1
else
  B[1] = b[4]-b[1]
end

B[0] = b[3]-b[0]

if c[5]-c[2]<0
  C[2] = c[5]+60-c[2]
  c[4] = c[4]-1
else
  C[2] = c[5]-c[2]
end

if c[4]-c[1]<0
  C[1] = c[4]+60-c[1]
  c[3] = c[3]-1
else
  C[1] = c[4]-c[1]
end

C[0] = c[3]-c[0]

puts A.join(' ')
puts B.join(' ')
puts C.join(' ')



Measured memory_bytes: 6888
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n, a, d;
vector<pair<ll, pair<ll, ll>>> intervals;
int main()
{
	scanf("%lld%lld%lld", &n, &a, &d);
	if (d == 0)
	{
		printf("%lld\n", a==0?1:n + 1);
		return 0;
	}

	for (ll k = 0; k <= n; k++)
	{
		ll q = (a * k) / d, r = (a * k) % d;
		if (r < 0) { r += d; q--; }
		q += k * (k - 1) / 2;
		ll l = k * (n - k);
		intervals.push_back(make_pair(r, make_pair(q, q + l)));
	}
	sort(intervals.begin(), intervals.end());
	int j;
	ll ans = 0;
	for (int i = 0; i < intervals.size(); i=j)
	{
		ll s = intervals[i].second.first;
		ll e = intervals[i].second.second;
		for (j = i; j < intervals.size() &&
			intervals[i].first == intervals[j].first; j++)
		{
			ll s2 = intervals[j].second.first;
			ll e2 = intervals[j].second.second;
			if (s2 <= e) e = max(e, e2);
			else break;
		}
		ans += e - s + 1;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 8560
#include <iostream>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
#include<cstring>
#include<string>
#include<cassert>
#include<cmath>
#include<climits>
#include<iomanip>
#include<bitset>
#include<unordered_map>

using namespace std;

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define rep(i,j,n) for(ll (i)=(j);(i)<(n);(i)++)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
typedef pair<ll, ll> P;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

const int loose = 0;
const int tight = 1;

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

//グラフ関連
struct Edge {//グラフ
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
		to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

class SumSegTree {
private:

	int _sum(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l)return 0;    // 交差しない
		if (a <= l && r <= b)return dat[k];   // a,l,r,bの順で完全に含まれる
		else {
			int s1 = _sum(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
			int s2 = _sum(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
			return s1 + s2;
		}
	}
public:
	int n, height;
	vector<int> dat;

	// 初期化（_nは最大要素数）
	SumSegTree(int _n) {
		n = 1;
		height = 1;
		while (n < _n) {
			n *= 2;
			height++;
		}
		dat = vector<int>(2 * n - 1, 0);
	}

	// 場所i(0-indexed)にxを足す
	void add(int i, int x) {
		i += n - 1; // i番目の葉ノードへ
		dat[i] += x;
		while (i > 0) { // 下から上がっていく
			i = (i - 1) / 2;
			dat[i] += x;
		}
	}

	// 区間[a,b)の総和。ノードk=[l,r)に着目している。
	int sum(int a, int b) {
		return _sum(a, b, 0, 0, n);
	}
};

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

	ll n;
	cin >> n;
	string s;
	cin >> s;

	vector<SumSegTree> seg(26,SumSegTree(n));

	REP(i, n) {
		seg[s[i] - 'a'].add(i, 1);
	}

	ll q;
	cin >> q;

	while (q--) {
		ll qq;
		cin >> qq;
		if (qq == 1) {
			ll i;
			string t;
			cin >> i >> t;
			i--;
			seg[t[0] - 'a'].add(i, 1);
			seg[s[i] - 'a'].add(i, -1);
			s[i] = t[0];
		}
		else {
			ll l, r;
			cin >> l >> r;
			l--; r;
			ll ans = 0;
			REP(i, 26) {
				if (seg[i].sum(l, r) >= 1) {
					ans++;
				}
			}
			cout << ans << en;
		}
	}

	return 0;
}

Measured memory_bytes: 111516
using System;
using System.Collections.Generic;
using System.Linq;
using static Atcoder;
using System.Threading.Tasks;
using System.ComponentModel;

public class Hello
{

    public static void Main()
    {
        int a = intRead();
        string ans = "";
        if (a < 1200) ans = "ABC";
        else if (a < 2800) ans = "ARC";
        else ans = "AGC";
        Console.WriteLine(ans);

    }
}


public class Atcoder
{
    static void Swap<T>(ref T a, ref T b)
    {
        var t = a;
        a = b;
        b = t;
    }
    public static long LCM(long a, long b)
    {
        long c = a * b;
        if (a < b) Swap(ref a, ref b);
        long d = a % b;
        while (d != 0)
        {
            a = b;
            b = d;
            d = a % b;
        }
        return c / b;
    }
    public static string strReverce(string s)
    {
        return new string(s.Reverse().ToArray());
    }
    public static int intRead()
    {
        return int.Parse(Console.ReadLine());
    }
    public static bool IsPrime(int n)
    {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        //double sqrtNum = Math.Sqrt(n);
        for (int i = 3; i < n; i += 2)
        {
            if (n % i == 0) return false;
        }
        return true;
    }
    public static string[] SpRead(char c)
    {
        return Console.ReadLine().Split(c);
    }
    public static int[] SpIntRead(char c)
    {
        return Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
    }

}


Measured memory_bytes: 11092
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define dfor(i,a,b) for(ll i=(a);i>=(b);i--)
#define mem(u, vis) memset(u, vis, sizeof(u))
#define ll long long
#define ull unsigned long long
#define MOD  1000000007
#define MAX  1e9
#define pb   push_back
#define F    first
#define S    second


signed main() {
	ll t=1;
	//cin>>t;
	while(t--){
		ll n, W;
		cin>>n>>W;
		ll w[n], v[n];
		rep(i,n){
			cin>>w[i]>>v[i];
		}
		vector<ll> dp(W+1,0);
		for(ll i = 0; i < n; ++i){
			for(ll j = W; j>=w[i]; --j){
				dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
			}
		}
		cout<<dp[W];

		
	}
	
}

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

#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
typedef long long s64;
//typedef __int128 s64;
const int N=2e6+5,D=1e9+7;
s64 mi(s64 x,int y=D-2)
{
	s64 ans=1;
	while(y)
	{
		if(y&1)ans=ans*x%D;
		x=x*x%D;y>>=1; 
	}
	return ans;
}
s64 jie[N],niv_jie[N]; 
void init_jie(int n)
{
	jie[0]=1;
	rep(i,1,n)jie[i]=jie[i-1]*i%D;
	niv_jie[n]=mi(jie[n]);
	per(i,n,1)niv_jie[i-1]=niv_jie[i]*i%D;
//	rep(i,0,n)assert(jie[i]*niv_jie[i]%D==1);
}
s64 C(int n,int m)
{
	if(m<0||m>n)return 0;
//	assert(n<N);
	return jie[n]*niv_jie[m]%D*niv_jie[n-m]%D;
}
int x[6],y[6];

int main()
{
#ifdef kcz
	freopen("1.in","r",stdin);
#endif
	init_jie(N-1);
	rep(i,0,5)scanf("%d",x+i);
	rep(i,0,5)scanf("%d",y+i);
	--x[0];--y[0];
	--x[2];--y[2];
	++x[5];++y[5];
	s64 ans=0,w[2]={1,-1};
	rep(i0,0,1)
	rep(j0,0,1)
	rep(i2,4,5)
	rep(j2,4,5)
/*	rep(i0,1,1)
	rep(j0,1,1)
	rep(i2,4,4)
	rep(j2,4,4)*/ 
	rep(i1,2,3)
	rep(j1,2,3)
	{
		s64 sum=0;
		int n=x[i1]-x[i0],m=y[j1]-y[j0],_n=x[i2]-x[i0],_m=y[j2]-y[j0];
		rep(tmp,0,1)
		{
			rep(i,0,n)(sum+=(i+m)*C(m+i,i)%D*C(_n-i+_m-(m+1),_m-(m+1)))%=D;
			swap(n,m);swap(_n,_m);
		}
		ans+=sum*w[i0!=j0]*w[i2!=j2]*w[i1!=j1];
	}
	cout<<(long long)((ans%D+D)%D);
}

Measured memory_bytes: 31488
import sys
sys.setrecursionlimit(10**9)

H, W = map(int, input().split())
S = [input() for i in range(H)]

visited = set()
def dfs(x, y, c, white, black):
  global visited
  for dx, dy in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and (xx, yy) not in visited and S[xx][yy]!=c:
      cc = S[xx][yy]
      if cc == '.':
        white += 1
      else:
        black += 1
      visited.add((xx, yy))
      white, black = dfs(xx, yy, cc, white, black)
  return white, black

ans = 0
for x in range(H):
  for y in range(W):
    if (x, y) not in visited:
      visited.add((x, y))
      c = S[x][y]
      if c == '.':
        white = 1; black = 0
      else:
        white = 0; black = 1
      white, black = dfs(x, y, c, white, black)
      ans += white * black

print(ans)

Measured memory_bytes: 253268
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define repd(i,a,b) for(int i=a;i>=b;--i)
#define rvc(i,S) for(int i=0;i<(int)S.size();++i)
#define fore(i,x) for(int i = head[x] ; i ; i = e[i].next)
#define mp make_pair
#define pb push_back
#define maxn 1000005
#define ll long long 
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const ll INF = 0x3f3f3f3f;
int n,m;
int vis[maxn];
int a[maxn],f[maxn][2],Max[maxn*4][2];
pair<int,int> query(int node,int l,int r,int lx,int rx)
{ if(lx>rx) return mp(0,0);
  if(lx<=l&&rx>=r) return mp(Max[node][0],Max[node][1]);
  pair<int,int> ans=mp(0,0);
  int mid=(l+r)>>1;
  if(lx<=mid) ans=query(node<<1,l,mid,lx,rx);
  if(rx>=mid+1)
    { pair<int,int> y=query(node<<1|1,mid+1,r,lx,rx);
      ans.fi=max(ans.fi,y.fi);
      ans.se=max(ans.se,y.se);
	}
return ans;
}
void add(int node,int l,int r,int pos,int id)
{ if(l==r)
   {Max[node][0]=f[id][0];Max[node][1]=f[id][1];
    return;
   }
   int mid=(l+r)>>1;
   if(pos<=mid) add(node<<1,l,mid,pos,id);
   else         add(node<<1|1,mid+1,r,pos,id);
   Max[node][0]=max(Max[node<<1][0],Max[node<<1|1][0]);
   Max[node][1]=max(Max[node<<1][1],Max[node<<1|1][1]);
}
bool check(int val,int lef)
{ if(lef<0) return 0;
  pair<int,int> y=query(1,1,n,val+1,n);
  if(!((y.fi-lef)&1)) return y.first>=lef;
  else                return y.se>=lef;
}
signed main()
{ cin>>n;
  rep(i,1,n) scanf("%d",&a[i]);
  for(int x=0,i=1;i<=n;i++)
  { x=max(x,a[i]);
    if(x==a[i])  ++vis[i];
  }
  repd(i,n,1) vis[i]+=vis[i+1];
  repd(i,n,1)
   { int t=1+(vis[i]!=vis[i+1]);//1 or 2
     pair<int,int> y=query(1,1,n,a[i]+1,n);
     f[i][(y.fi+t)&1]=max(f[i][(y.fi+t)&1],y.fi+t);
     f[i][(y.se+t)&1]=max(f[i][(y.se+t)&1],y.se+t);
     add(1,1,n,a[i],i);
   }
  if(!check(0,vis[1])) {puts("-1");return 0;}	
  int len[2]={0},pos[2]={0};
  rep(i,1,n)
  { f[i][0]=f[i][1]=0;
    add(1,1,n,a[i],i);
	int x=a[i]>a[pos[0]]?i:pos[0];
	int y=len[0]+(x==i);
	if(check(a[x],len[1]+vis[i+1]-y)||check(a[pos[1]],y+vis[i+1]-len[1])) 
	 {putchar('0');
	  len[0]=y;
	  pos[0]=x;
	 }
	else
	 {pos[1]=a[i]>a[pos[1]]?i:pos[1];
	  len[1]+=pos[1]==i;
      putchar('1');
	 }
  }
return 0;	
}

Measured memory_bytes: 16768
#include <iostream>
#include <cstdlib>
#include <string>
#include <memory.h>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
typedef pair<int, int> P;

const int INF = 1 << 29;
int memo[600];
int n, m;
struct edge{
  int to;
  int cost;
  edge(){};
  edge(int to, int cost){
    this->to = to;
    this->cost = cost;
  }

};

vector<edge> G[600];

int dijkstra(int s, int t){
  fill(memo,memo + 600,INF);
  priority_queue<P, vector<P>, greater<P> > que;
  que.push(P(0, s));
  memo[s] = 0;
  while(!que.empty()){
    P p = que.top();
    que.pop();
    int cost = p.first;
    int v = p.second;
    if(cost > memo[v]) continue;
    if(v == t) return memo[t];
    rep(i, (int)G[v].size()){
      edge e = G[v][i];
      int nxt = e.to;
      int c = e.cost;
      if(memo[nxt] > cost + c){
	memo[nxt] = cost + c;
	que.push(P(cost + c, nxt));
      }
    }
  }
  return INF;
}

map<string, int> mp;

int main(){
  string s, p, g;
  while(cin >> n >> m && (n || m)){
    rep(i, 600) G[i].clear();
    mp.clear();
    int cnt = 0;
    cin >> s >> p >> g;
    if(!mp[s]) mp[s] = cnt++;
    if(!mp[p]) mp[p] = cnt++;
    if(!mp[g]) mp[g] = cnt++;
    rep(i, m){
      string a, b;
      int d, t;
      cin >> a >> b >> d >> t;
      if(!mp[a]) mp[a] = cnt++;
      if(!mp[b]) mp[b] = cnt++;
      G[mp[a]].push_back(edge(mp[b], d / 40 + t));
      G[mp[b]].push_back(edge(mp[a], d / 40 + t));
    }
    cout << dijkstra(mp[s], mp[p]) + dijkstra(mp[p], mp[g]) << endl;
  }
  return 0;
}

Measured memory_bytes: 0
import itertools
n = int(input())
ns = list(range(1,n+1))
cs = list(itertools.combinations(ns, 2))
top = n if n % 2 == 0 else n-1

for nn in range(n):
  tpl = (nn+1, top-nn)
  if tpl[0] >= tpl[1]:
    break
  #print(f'removing {tpl}')
  cs.remove(tpl)

print(len(cs))
for a, b in cs:
  print('{0} {1}'.format(a, b))



Measured memory_bytes: 3720
// ABC 147-C
// 2019.12.23 bal4u

#include <stdio.h>
#include <ctype.h>

#define gc() getchar_unlocked()

int in() {   // 非負整数の入力
	int n = 0; int c;
	do c = gc();
	while (isspace(c));
	do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0');
	return n;
}

/* 2^16までのビット数を数える */
int bitcount(int x) {
	x = ((x & 0xAAAAAA) >>  1) + (x & 0x555555);
	x = ((x & 0xCCCCCC) >>  2) + (x & 0x333333);
	x = ((x & 0xF0F0F0) >>  4) + (x & 0x0F0F0F);
	x = ((x & 0x00FF00) >>  8) + (x & 0xFF00FF);
	return x;
}

int N;
int A[20];
int x[20][20], y[20][20];

int check(int b) {
	int i, j;
	
	for (i = 1; i <= N; ++i) {
		if ((b >> (i-1)) & 1) {
			for (j = 1; j <= A[i]; ++j) {
				if (y[i][j] != ((b >> (x[i][j]-1)) & 1)) return 0;
			}
		}
	}
	return 1;
}
				
int main()
{
	int i, j, ans;
	
	N = in();
	for (i = 1; i <= N; ++i) {
		A[i] = in();
		for (j = 1; j <= A[i]; ++j) {
			x[i][j] = in(), y[i][j] = in();
		}
	}
	ans = 0;
	for (i = (1<<N)-1; i; --i) {
		if ((j = bitcount(i)) > ans && check(i)) ans = j;
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include<stdio.h>
#include<iostream>
#include<stack>
#include<algorithm>
using namespace std;
#define MAX 1400
struct Rectangle{int height; int pos;};

int getLargestRectangle(int size,int buffer[])
{
  stack<Rectangle> S;
  int maxv=0;
  buffer[size]=0;
  for(int i=0;i<=size;i++)
    {
      Rectangle rect;
      rect.height=buffer[i];
      rect.pos=i;
      if(S.empty())
	{
	  S.push(rect);
	}
      else
	{
	  if(S.top().height < rect.height)
	    {
	      S.push(rect);
	    }
	  else if(S.top().height > rect.height)
	    {
	      int target=i;
	      while(!S.empty() && S.top().height >= rect.height)
		{
		  Rectangle pre = S.top();S.pop();
		  int area = pre.height * (i-pre.pos);
		  maxv=max(maxv,area);
		  target=pre.pos;
		}
	      rect.pos=target;
	      S.push(rect);
	    }
	}
    }
  return maxv;
}

int H,W;
int buffer[MAX][MAX];
int T[MAX][MAX];

int getLargestRectangle()
{
  for(int j=0;j<W;j++)
    {
      for(int i=0;i<H;i++)
	{
	  if(buffer[i][j])
	    {
	      T[i][j]=0;
	    }
	  else
	    {
	      T[i][j]=(i > 0) ? T[i-1][j] + 1 : 1;
	    }
	}
    }
  int maxv=0;
  for(int i=0;i<H;i++)
    {
      maxv=max(maxv,getLargestRectangle(W,T[i]));
    }
  return maxv;
}


int main(void)
{
  scanf("%d %d",&H,&W);
  for(int i=0;i<H;i++)
    {
      for(int j=0;j<W;j++)
	{
	  scanf("%d",&buffer[i][j]);
	}
    }
  cout << getLargestRectangle() << endl;
  return 0;
}

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

int main(){
  string s;
  cin >> s;
  if (s[0] == s[1]) {
    cout << "1 2" << endl;
    return 0;
  }
  for (int i = 1; i < s.size() - 1; i++) {
    if (s[i] == s[i + 1]) {
      cout << i + 1 << " " << i + 2 << endl;
      return 0;
    }
    if (s[i - 1] == s[i + 1]) {
      cout << i << " " << i + 2 << endl;
      return 0;
    }
  }
  cout << "-1 -1" << endl;
  return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
 
int main() {
	long long int a,b,c,k,sum=0;
	cin>>a>>b>>c>>k;
	if(k>=a)
	{
		sum += a;
		k = k-a;
		a = 0;
	}
	if(a>k && k!=0)
	{
		sum +=k;
		k =0;
	}
	if(k>=b)
	{
		k = k-b;
		b = 0;
	}
	if(b>k && k!=0)
	{
		sum +=0;
		k =0;
	}
	if(k>=c)
	{
		k = k-c;
		sum = sum - c;
		c =0;
	}
	if(c>k && k!=0)
	{
		sum = sum-k;
		k=0;
		
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int flag = 0;
  string str1, str2, str3;
  cin >> str1 >> str2;
  str1 = str1 + str1;
  
  for(int i = 0; i < str1.size() / 2; i++){
    str3 = str1.substr(i, str2.size());
    if(str3 == str2){
      cout << "Yes" << endl;
      flag++;
      break;
    }
  }
  if(flag == 0) cout << "No" << endl;
}


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

int main() {
  int N;
  cin >> N;
  vector<int> v(N);
  for (int i = 0; i < N; i++){
    cin >> v.at(i);
  }
  int kaunto = 0;
  int flag = 0;
  int tugi = 0;
  for (int i = 0; i < N; i++){
    kaunto += 1;
    if (v.at(tugi) == 2){
      flag = 1;
      break;
    }
    tugi = v.at(tugi) -1;
  }
  if (flag == 1){
    cout << kaunto << endl;
  }else{
    cout << -1 << endl;
  }
}

Measured memory_bytes: 768
#include<stdio.h>
#include<string.h>
int main()
{
int i,a,b,count=0;
char s[25],t[25];
gets(s);
gets(t);
a=strlen(s);
b=strlen(t);
if(a<b)
{
for(i=0;i<a;i++)
  {
  if(s[i]!=t[i])
    {
    printf("No\n");
    count=count+1;
    break;
    }
  }
  if(count==0)
  printf("Yes\n");
}
return 0;
}

Measured memory_bytes: 1532