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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int W = 0;W < (n);W++)cerr << v[W] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007

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

char tmp[100];
int place;

int m_minus(int num){
	return 2 - num;
}

int m_op(int a,int b,char c){
	if(c == '*')return min(a,b);
	else return max(a,b);
}

int dfs(){
	if(tmp[place] == '-'){
		place++;
		return m_minus(dfs());
	}
	else if(tmp[place] == '('){
		place++;
		int a = dfs();
		char c = tmp[place];
		place++;
		int b = dfs();
		place++;
		return m_op(a,b,c);
	}
	else{
		int ret = tmp[place] - '0';
		place++;
		return ret;
	}
}

int main(){
	
	string str;
	while(cin >> str,str[0] != '.'){			
		int ans = 0;
		
		REP(i,3){
			REP(j,3){
				REP(k,3){
					REP(l,str.size()){
						if(str[l] == 'P'){
							tmp[l] = '0' + i;
						}
						else if(str[l] == 'Q'){
							tmp[l] = '0' + j;
						}
						else if(str[l] == 'R'){
							tmp[l] = '0' + k;
						}
						else tmp[l] = str[l];
					}
					place = 0;
					if(dfs() == 2){
						ans++;
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3068
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>

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

const int inf = 1e9 + 7;
#define EPS 1e-9

int main() {
	string s;
	cin >> s;
	int n = s.size();
	int res=0;

	stack<char> st;
	rep(i, n) {
		if (st.empty() || st.top() == s[i] || (st.top() == 'T' && s[i] == 'S')) {
			st.push(s[i]);
		}
		else if(st.top() == 'S' && s[i]=='T'){
			res += 2;
			st.pop();
		}
	}
	cout << n-res << endl;
	return 0;
}

Measured memory_bytes: 644
while True:
    c = 0
    n, x= map(int, input().split())
    if n == 0 and x == 0:
        break
    for i in range(1, n + 1):
        for j in range(1, n + 1 ):
            if j <= i:
                continue
            for k in range(1, n + 1):
                if k <= j:
                    continue
                if i != j and i != k and j != k and i + j + k == x:
                    c += 1
    print(c)


Measured memory_bytes: 5596
#include<bits/stdc++.h>
#include<math.h>
#include<vector>
#define SIZE 100000 
using namespace std;
int mincost[10][10];
int main(void){
	int i,j,Q;
	cin >> Q;
	int l[Q];
	int k;
	int result;
	int r[Q];
	bool primes[SIZE+1];
	bool flag;
	int orderprime[SIZE/10];//順に素数を格納する方
	int recordedprime=2;
	for(i=0;i<Q;i++){
		cin >> l[i] >> r[i];
	}
	primes[1] = false;
	primes[2] = true;
	primes[3] = true;
	orderprime[0]  = 2;
	orderprime[1]  = 3;

	for(i=2;i<=SIZE/2;i++){//素数表,全ての番号に振る
		primes[i*2]=false;
		primes[i*2+1] = true;
	}
	for(i=2;i<SIZE/2;i++){
		flag = false;
		for(j=0;j<recordedprime;j++){
			if((i*2+1)%orderprime[j]==0){ //割り切れた
				primes[i*2+1] = false;
				flag = true;
				break;
			}
		}
		if(flag == false){
			orderprime[recordedprime]=i*2+1;//新しい素数発見
			recordedprime +=1;
		}
	}
	//cout << orderprime[12];
	/*for(i=0;i<SIZE;i++){
		if(primes[i]==true){
			cout << 1 << endl;
		}else{
			cout << 0 << endl;
		}
		//cout << primes[i] << endl;
		//cout << orderprime[i] << endl;
	}*/
	for(i=0;i<Q;i++){
		result = 0;
			k=0;
			flag = true;
			while(1){
				if(orderprime[k]<l[i]){
					k+=1;
					continue;
				}else{
					break;
				}
			}
			for(k=k;orderprime[k]<=r[i];k++){ //素数を一つ一つ判定してく
				if(primes[(orderprime[k]+1)/2]==true){
					result += 1;
				}
			}
		cout << result << endl;
	}
	return 0;
}

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

int scoreR[100000];
int scoreS[100000];
int scoreP[100000];
bool checked[100000];

int main(void) {
	int N, K, R, S, P;
	string T;
	cin >> N >> K >> R >> S >>P >> T;

	// スコアに変換、逆順に入れる
	for (int i = 0; i < N; i++) {
		switch (T[i]) {
		case 'r':
			scoreP[i] = P;
			scoreR[i] = 0;
			scoreS[i] = 0;
			break;
		case 's':
			scoreR[i] = R;
			scoreP[i] = 0;
			scoreS[i] = 0;
			break;
		case 'p':
			scoreS[i] = S;
			scoreP[i] = 0;
			scoreR[i] = 0;
			break;
		}
	}

	for (int i = 0; i < N; i++) checked[i] = false;

	long long ans = 0;
	for (int i = N-1; i >= 0; i--) {
		if (checked[i]) continue;

		checked[i] = true;
		// 最初の点だけは固定です
		long long preR = scoreR[i];
		long long preS = scoreS[i];
		long long preP = scoreP[i];

		for (int j = i - K;  j >= 0; j -= K) {
			checked[j] = true;
			long long tmpR, tmpS, tmpP;
			// グーを出す、前回はpreR
			tmpR = max(preS, preP) + scoreR[j];
			// チョキを出す、前回はpreS
			tmpS = max(preR, preP) + scoreS[j];
			// パーを出す、前回はpreP
			tmpP = max(preR, preS) + scoreP[j];

			preR = tmpR;
			preS = tmpS;
			preP = tmpP;
		}
		// 一番高いものを採用
		ans += max(max(preR, preS), preP);

	}
	cout << ans << endl;
	return 0;
}


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

ll a[3002];
ll dp[3002][3002];

ll rec(int l, int r, bool f){
    if(r < l) return 0;
    ll left, right;
    if(dp[l + 1][r]) left = dp[l + 1][r];
    else left = dp[l + 1][r] = rec(l + 1, r, !f);
    if(dp[l][r - 1]) right = dp[l][r - 1];
    else right = dp[l][r - 1] = rec(l, r - 1, !f);
    if(f) return max(right + a[r], left + a[l]);
    else return min(right - a[r], left - a[l]);
}

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i++) cin >> a[i];
    cout << rec(0, n - 1, true) << endl;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int h,w;cin >> h >> w;
	vector<string> a(h+2);
	rep(i,h){
		string s;
		cin >> s;
		a.at(i+1)=" "+s+" ";
	}
	rep(i,w+2){
		a[0]+=" ";
		a[h+1]+=" ";
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;++j){
			if(a[i][j]=='.'){
				int cnt=0;
				for(int x=-1;x<=1;x++){
					for(int y=-1;y<=1;++y){
						if(x==0 && y==0) continue;
						else{
							if(a[i+x][j+y]=='#') cnt++;
						}
					}
				}
				a[i][j]='0'+cnt;
			}
		}
	}
	rep(i,h){
		cout << a[i+1].substr(1,w) << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    int A, B; cin >> A >> B;
    A--, B--;

    int n = 100;
    cout << n << " " << n << endl;

    vector<vi> f(n, vi(n));
    int bd = n/2;
    rep(i, bd){
        rep(j, n){
            f[i][j] = 1;
        }
    }

    rep(i, 1, bd-1){
        rep(j, 1, n-1){
            if(i % 2 or j % 2) continue;
            if(A > 0) f[i][j] = 0, A--;
        }
    }
    rep(i, bd+1, n-1){
        rep(j, 1, n-1){
            if(i % 2 or j % 2) continue;
            if(B > 0) f[i][j] = 1, B--;
        }
    }

    rep(i, n){
        rep(j, n){
            cout << (f[i][j] == 1 ? '#':'.');
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() 
{
	int i, j, H, W;
	while (1) {
    		cin >> H >> W;
		if(H == 0 && W == 0) {
        			break;
		}	
		for (i = 1; i <= H; i++) {
			for (j = 1; j <= W; j++) {
				if ((i + j) % 2 == 0)
                        			cout << "#";
                        		else
                        			cout << ".";
            		}
		 	cout << endl;
		}
		cout << endl;
	}
	return 0;
}



Measured memory_bytes: 3080
using System;

namespace AtCoder.ABC._123
{
    class d
    {
        static void Main(string[] args)
        {
            var line = Console.ReadLine().Trim();
            var spl = line.Split(' ');
            var X = int.Parse(spl[0]);
            var Y = int.Parse(spl[1]);
            var Z = int.Parse(spl[2]);
            var K = int.Parse(spl[3]);
            line = Console.ReadLine().Trim();
            var XList = Array.ConvertAll(line.Split(' '), new Converter<string, long>(x => long.Parse(x)));
            line = Console.ReadLine().Trim();
            var YList = Array.ConvertAll(line.Split(' '), new Converter<string, long>(x => long.Parse(x)));
            line = Console.ReadLine().Trim();
            var ZList = Array.ConvertAll(line.Split(' '), new Converter<string, long>(x => long.Parse(x)));
            var list = new long[X * Y];
            var cnt = 0;
            foreach(var x in XList)
            {
                foreach(var y in YList)
                {
                    list[cnt] = x + y;
                    cnt++;
                }
            }
            Array.Sort(list);
            var list2 = new long[X * Y > K ? K : X * Y];
            Array.ConstrainedCopy(list, X * Y < K ? 0 : X * Y - K, list2, 0, X * Y > K ? K : X * Y);
            var list3 = new long[Z * (X * Y > K ? K : X * Y)];
            cnt = 0;
            foreach (var k in list2)
            {
                foreach (var z in ZList)
                {
                    list3[cnt] = k + z;
                    cnt++;
                }
            }
            Array.Sort(list3);
            for (var i = 0; i < K; ++i)
            {
                Console.WriteLine(list3[Z * (X * Y > K ? K : X * Y) - i - 1]);
            }
        }
    }
}


Measured memory_bytes: 44768
import java.util.*;

//public class Main {
//	public static void main(String[] args) {
//		Scanner sc = new Scanner(System.in);
//		int n = Integer.parseInt(sc.next());
//		int k = Integer.parseInt(sc.next());
//		String inputs = sc.next();
//		String[] input = inputs.split("");
//		String output = "";
//		for(int i=0;i<n;i++) {
//			if(i == k-1) {
//				output = output + input[i].toLowerCase();
//			}else {
//				output = output + input[i];
//			}
//		}
//		System.out.println(output);
//	}
//}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int b = n%100;
		int a = (n-b)/100;
		String judge = "";
		if(a>12 || a == 0) {
			if(13>b && b>0) {
				judge = "YYMM";
			}else {
				judge = "NA";
			}
		}else {
			if(13>b && b>0) {
				judge = "AMBIGUOUS";
			}else {
				judge = "MMYY";
			}
		}
		System.out.println(judge);
	}
}


Measured memory_bytes: 21844
n=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
count=0
for a,b in zip(A,B):
   if a>b:count -=a-b
   elif b>a:count +=(b-a)//2

print("Yes" if count>=0 else "No")

Measured memory_bytes: 4660
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

k = INT()
if k <= 10:
    print(k)
    exit()
arr = [0 for _ in range(15)]
arr[1] = 1
for i in range(k - 10):
    for j in range(12):
        #print(j, arr[j], sum(range(arr[j], arr[j] + j)))
        flag = True
        for k in range(j):
            if arr[k] == arr[k + 1] + 1 or arr[k] == 9:
                continue
            flag = False
        #print(j, flag)
        if flag and sum(arr[j + 1:]) == 0 and arr[j] < 9:
            #print('c', j)
            arr[j] += 1
            for k in reversed(range(j)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif arr[j] == arr[j + 1] + 1 and arr[j + 1] < arr[j + 2] + 1:
            #print('a', j)
            arr[j + 1] += 1
            for k in reversed(range(j + 1)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif sum(arr[:j + 1]) == 9 * (j + 1) and arr[j + 1] < 9 and (arr[j + 1] < arr[j + 2] + 1 or arr[j + 2] == 0):
            #print('d', j)
            arr[j + 1] += 1
            for k in reversed(range(j + 1)):
                arr[k] = max(0, arr[k + 1] - 1)
            break
        elif (arr[j] == arr[j + 1] or arr[j] == arr[j + 1] - 1) and arr[j] < 9:
            #print('b', j)
            arr[j] += 1
            break
    #print(i + 10, arr)
arr.reverse()
for i in range(15):
    arr[i] = str(arr[i])
ans = ''.join(arr)
ans = int(ans)
print(ans)

Measured memory_bytes: 74964
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#include <string>
#include <set>
#include <cmath>
using namespace std;
typedef long long LL;
const int N = 1005;
int n , a[N];
int main() {
    vector<int> v;
    scanf("%d" , &n);
    for (int i = 0 ; i < n ; ++ i)
        scanf("%d" , &a[i]);
    for (int i = 0 ; i < n ; ++ i) {
        int x = 0 , j = i;
        while (j < n && x < 10000000) {
            x = x * 10 + a[j ++];
            v.push_back(x);
        }
    }
    sort(v.begin() , v.end());
    int res = 0;
    for (int i = 0 ; i < v.size() ; ++ i) {
        if (res == v[i])
            ++ res;
    }
    cout << res << endl;
    return 0;
}

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

using namespace std;

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


	long long l, g;
	long long p, a;

	p = max(C, D);
	a = min(C, D);


	do {
		g = p % a;
		p = a;
		a = g;
	} while (g != 0);


	g = p;
	l = C * D / g;



	long long countUA = A - 1 - (A - 1) / C - (A - 1) / D + (A- 1) / l;
	long long countUB = B - (B / C) - (B / D) + (B / l);

	cout << countUB - countUA << endl;


	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
const int maxn = 500, dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
int n, ans, dis[maxn + 10][maxn + 10];
int p[maxn * maxn + 10];
bool is[maxn + 10][maxn + 10], in[maxn + 10][maxn + 10];
queue<pii > qu;

void ins(int x, int y) {
	in[x][y] = 1; qu.push(make_pair(x, y));
}

void work() {
	while (!qu.empty()) {
		pii p = qu.front(); qu.pop();
		in[p.fi][p.se] = 0;
		for (int i = 0; i < 4; ++i) {
			pii q = p;
			q.fi += dir[i][0]; q.se += dir[i][1];
			if (q.fi > 0 && q.fi <= n && q.se > 0 && q.se <= n) {
				int w = dis[p.fi][p.se] + (!is[q.fi][q.se]);
				if (w < dis[q.fi][q.se]) {
					dis[q.fi][q.se] = w;
					if (!in[q.fi][q.se]) ins(q.fi, q.se);
				}
			}
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n * n; ++i) scanf("%d", &p[i]);
	memset(dis, 0x3f, sizeof dis);
	for (int i = 0; i <= n + 1; ++i)
		for (int j = 0; j <= n + 1; ++j)
			if (i == 0 || i == n + 1 || j == 0 || j == n + 1) {
				dis[i][j] = 0;
				ins(i, j);
			}
	work();
	for (int i = 1; i <= n * n; ++i) {
		int x = (p[i] - 1) / n + 1, y = p[i] - (x - 1) * n;
		ans += dis[x][y] - 1;
//		printf("|%d %d %d|\n", x, y, dis[x][y]);
		is[x][y] = 1;
		for (int j = 0; j < 4; ++j)
			ins(x + dir[j][0], y + dir[j][1]);
		work();
	}
	printf("%d", ans);
}


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

using namespace std;

int main(){
  string S;
  cin >> S;
  
  sort(S.begin(), S.end());
  
  if(S[0]==S[1] and S[2]==S[3] and S[1]!=S[2]) cout << "Yes" << endl;
  else cout << "No" << endl;
  
  return 0;
}

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

int main(){
  int a,b;
  string s;
  cin>>a>>b>>s;
  for(int i=0; i<s.size(); i++){
    if(((i>a && i<a+b+1) || i<a) && s[i]=='-') {
      cout<<"No";
      return 0;
    }
    if(i==a && s[i]!='-') {
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main (){
	while(1){
	int x,h; double S;
	cin >> x >> h ; if(x==0&&h==0) break;
	S=x*sqrt((double)4*h*h+x*x)+x*x ;
	cout << fixed << setprecision(6) ;
	cout << S << '\n' ;
	};
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int INF = 1e9;
const int MOD = 1000000007;
#define rep(i,n) for(int i=0;i<n;i++)
 
int main() {
  int n,k;
  string s;
  cin >> n >> k;
  cin >> s;
  if(s[0]=='0'){
    vector<pp> zo;
    zo.push_back(make_pair(0,0));
    char now = '0';
    int now_c = 0,a;
    rep(i,s.size()){
      if(s.at(i) == now) now_c ++;
      else{
        if(now =='0'){
          a = now_c; 
          now_c = 1;
          now = '1';
        }else{
          zo.push_back(make_pair(a,now_c));
          now_c = 1;
          now = '0';
        }
      }
    }
    if(s.at(s.size()-1) == '0') zo.push_back(make_pair(now_c,0));
    else zo.push_back(make_pair(a,now_c));
    int ans = 0;
    if( zo.size() <= k+1) ans = s.size();
    else{
      rep(i,k+1) ans += zo.at(i).first + zo.at(i).second;
      int i = k+1,res = ans;
      while(i < zo.size()){
        res += zo.at(i).first + zo.at(i).second;
        res -= zo.at(i-k).first + zo.at(i-k-1).second;
        ans = max(ans,res);
        i++;
      }
    }
    cout << ans << endl;
  }
  else{
    vector<pp> zo;
    zo.push_back(make_pair(0,0));
    char now = '0';
    int now_c = 0,a;
    rep(i,s.size()){
      if(s.at(i) == now) now_c ++;
      else{
        if(now =='0'){
          a = now_c; 
          now_c = 1;
          now = '1';
        }else{
          zo.push_back(make_pair(a,now_c));
          now_c = 1;
          now = '0';
        }
      }
    }
    if(s.at(s.size()-1) == '0') zo.push_back(make_pair(now_c,0));
    else zo.push_back(make_pair(a,now_c));
    //rep(i,zo.size()) cout << zo.at(i).first << zo.at(i).second << endl;
    int ans = 0;
    if( zo.size() <= k+2) ans = s.size();
    else{
      rep(i,k+2) ans += zo.at(i).first + zo.at(i).second;
      int i = k+2,res = ans;
      while(i < zo.size()){
        res += zo.at(i).first + zo.at(i).second;
        res -= zo.at(i-k).first + zo.at(i-k-1).second;
        ans = max(ans,res);
        //cout << i << " " <<  ans << endl;
        i++;
        
      }
    }
    cout << ans << endl;
  }
    
  return 0;
}




Measured memory_bytes: 1020
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;
    vector<int> h(N);
    for(int i = 0; i < N; i++){
        cin >> h[i];
    }
    
    sort(h.begin(), h.end());
    
    int res = INT_MAX;
    
    for(int i = 0; i <= N - K; i++){
        res = min(res, h[K + i - 1] - h[i]);
    }
    
    cout << res << endl;
}

Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>

using namespace std;

const int MOD = 1000003;

struct mint {
  int n;
  mint(int n_ = 0) : n(n_) {}
};

mint operator+(mint a, mint b) { a.n += b.n; if (a.n >= MOD) a.n -= MOD; return a; }
mint operator-(mint a, mint b) { a.n -= b.n; if (a.n < 0) a.n += MOD; return a; }
mint operator*(mint a, mint b) { return a.n == 0 || b.n == 0 ? 0 : (long long)a.n * b.n % MOD; }
mint &operator+=(mint &a, mint b) { return a = a + b; }
mint &operator-=(mint &a, mint b) { return a = a - b; }
mint &operator*=(mint &a, mint b) { return a = a * b; }
ostream &operator<<(ostream &o, mint a) { return o << a.n; }

vector<mint> F_{1, 1}, R_{1, 1}, I_{0, 1};

void check_fact(int n) {
  for (int i = I_.size(); i <= n; i++) {
    I_.push_back(I_[MOD % i] * (MOD - MOD / i));
    F_.push_back(F_[i - 1] * i);
    R_.push_back(R_[i - 1] * I_[i]);
  }
}

mint I(int n) { check_fact(n); return I_[n]; }
mint F(int n) { check_fact(n); return n < 0 ? 0 : F_[n]; }
mint R(int n) { check_fact(n); return n < 0 ? 0 : R_[n]; }
mint C(int n, int r) { return F(n) * R(n - r) * R(r); }
mint P(int n, int r) { return F(n) * R(n - r); }
mint H(int n, int r) { return n == 0 ? (r == 0) : C(n + r - 1, r); }

mint modpow(mint a, long long b) {
  mint res = 1;
  while (b > 0) {
    if (b & 1) res *= a;
    a *= a;
    b >>= 1;
  }
  return res;
}

mint modinv(mint n) {
  int a = n.n;
  int b = MOD;
  int s = 1;
  int t = 0;
  while (b != 0) {
    int q = a / b;
    a -= q * b;
    s -= q * t;
    swap(a, b);
    swap(s, t);
  }
  if (s < 0) s += MOD;
  return s;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int Q;
  cin >> Q;
  while (Q--) {
    mint a, d;
    int n;
    cin >> a.n >> d.n >> n;
    if (d.n == 0) {
      cout << modpow(a, n) << '\n';
      continue;
    } else if (a.n == 0) {
      cout << 0 << '\n';
      continue;
    }
    mint ans = modpow(d, n);
    mint x = a * modinv(d);
    if (x.n + n - 1 >= MOD) {
      cout << 0 << '\n';
    } else {
      ans *= F(x.n + n - 1) * R(x.n - 1);
      cout << ans.n << '\n';
    }
  }
}


Measured memory_bytes: 14668
#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <limits.h>
#include <math.h>
#include <list>
#define rep(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

int main() {
    list<int> a;
    auto c = a.end();
    int q;
    cin >> q;
    rep(i,q) {
        int t;
        cin >> t;
        switch(t) {
            case 0:
            int x;
            cin >> x;
            c = a.insert(c, x);
            break;
            case 1:
            int d;
            cin >> d;
            if (d > 0) rep(j,d)  c++;
            else       rep(j,-d) c--;
            break;
            case 2: 
            c = a.erase(c);
            break;
        }
    }
    for (auto itr = a.begin(); itr != a.end(); itr++)
        cout << *itr << endl;
    return 0;
}


Measured memory_bytes: 18644
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
using namespace std;

#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define PF push_front
#define MP make_pair
#define LL long long
#define ULL unsigned LL
#define LD long double
#define pii pair<int,int>
#define pll pair<LL,LL>
#define vi vector<int>
#define vl vector<LL>
#define vii vector<vi>

const double pi = 3.14159265358979323846264;
const int mod=1000000007;
const int h=21;

int main(){
	LL n,k;
    cin>>n>>k;
    vl a(n);
    vl mx(1<<h,0);
    vl c(44,0);
    FOR(i,0,n){
        cin>>a[i];
        FOR(j,0,42){
            if((a[i]>>j)&1){
                c[j]++;
            }
        }
    }
    FOR(i,0,1<<h){
        LL v=0;
        FOR(j,0,h){
            if((i>>j)&1)v+=(1LL<<j)*(n-c[j]);
            else v+=(1LL<<j)*(c[j]);
        }
        mx[i]=v;
        if(i!=0){
            mx[i]=max(mx[i],mx[i-1]);
        }
    }
    LL ans=0;
    FOR(i,0,1<<h){
        LL v=0;
        FOR(j,0,h){
            if((i>>(j))&1)v+=(1LL<<(j+h))*(n-c[j+h]);
            else v+=(1LL<<(j+h))*(c[j+h]);
        }
        if(i>(k>>h))break;
        else if(i==((k>>h))){
            v+=mx[k&((1<<h)-1)];
        }else{
            v+=mx[(1<<h)-1];
        }
        ans=max(ans,v);
    }
    cout<<ans;


}


Measured memory_bytes: 17408
a=input()

P=a[-2:]
Q=a[0:2]

if int(P)<=12 and int(Q)<=12 and not int(P)==0 and not int(Q)==0:
    print('AMBIGUOUS')
elif (int(P)>12 or int(P)==0) and (int(Q)>=12 or int(Q)==0): 
    print('NA')
elif (int(P)<=12 and not int(P)==0 )and (int(Q)>=12 or int(Q)==0):
    print('YYMM')
elif (int(P)>=12 or int(P)==0) and (int(Q)<=12 and not int(Q)==0):
    print('MMYY')

Measured memory_bytes: 3064
#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 998244353

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

ll calPoint(pair<P, P> test, ll place){
	ll ret = 0;
	if(place < test.FI.SE){
		return test.SE.FI * place;
	}
	ret += test.FI.SE * test.SE.FI;
	return ret + test.SE.SE * (place - test.FI.SE);
}

bool check(vector<pair<P, P>> &v, ll mid, ll now, ll x, ll n){
	ll cou = mid / x;
	ll amari = mid % x;
	if(cou == v.size())return true;

	REP(i, cou){
		now += v[i].FI.FI;
	}
	REP(i, n){
		ll point = calPoint(v[i], amari);
		if(i < cou){
			now -= v[i].FI.FI;
			now += v[cou].FI.FI + point;
			if(now >= 0)return true;
			now += v[i].FI.FI;
			now -= v[cou].FI.FI + point;
		}
		else {
			now += point;
			if(now >= 0)return true;
			now -= point;
		}
	}

	return false;

}

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

	ll n, x;cin >> n >> x;
	vector<pair<P, P>> v;
	ll now = 0;
	REP(i, n){
		ll b, l , r;cin >> b >> l >> r;
		v.EB(MP(l * b + r * (x - b), b), MP(l, r));
		now -= l * b;
	}

	sort(ALL(v), greater<pair<P, P>>());

	ll l = -1;
	ll r = x * n;
	while(r - l > 1){
		ll mid = (l + r) / 2;
		if(check(v, mid, now, x, n))r = mid;
		else l = mid;
	}

	cout << r << endl;

	return 0;
}


Measured memory_bytes: 6256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,k,sum,i;
	cin>>a>>b>>c>>k;
	if(a>b) swap(a,b);
	if(a>c) swap(a,c);
	if(b>c) swap(b,c);
	for(i=1;i<=k;i++)
		c*=2;
	sum=a+b+c;
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
t=[[0 for i in range(n)] for j in range(n)]
A,B=[],[]
for _ in range(m):
    a,b=map(int,input().split())
    A.append(a-1)
    B.append(b-1)
    t[a-1][b-1]=1
    t[b-1][a-1]=1
ans=0
for i in range(m):
    t[A[i]][B[i]]=0
    t[B[i]][A[i]]=0
    
    q=[0]
    visited={0}
    while q:
        temp=q.pop()
        for j in range(n):
            if j not in visited and t[temp][j]==1:
                q.append(j)
                visited.add(j)
    if len(visited)!=n: ans+=1
    t[A[i]][B[i]]=1
    t[B[i]][A[i]]=1
print(ans)

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

struct edge{int s,t,n;}e[1010];
int n,h[1010],v[1010];
bitset <5010> a[1010];

int dfs(int x)
{
	int sum=0,s;
	a[x][0]=1;
	for (int i=h[x],y; y=e[i].t,i; i=e[i].n)
		s=dfs(y),sum+=s+v[y],a[x]=(a[x]<<s)|(a[x]<<v[y]);
	s=v[x];
	for (; (~s)&&(!a[x][s]); s--);
	if (s<0)  puts("IMPOSSIBLE"),exit(0);
	return sum-s;
}

void work()
{
	scanf("%d",&n);
	for (int i=2,p; i<=n; i++)
		scanf("%d",&p),e[i]=(edge){p,i,h[p]},h[p]=i;
	for (int i=1; i<=n; i++)  scanf("%d",&v[i]);
	dfs(1);
	puts("POSSIBLE");
}

int main()
{
	work();
	return 0;
}


Measured memory_bytes: 2048
var    i,j,k,m,n:longint; 
  s,st:string;
begin
  read(s);
    m:=maxlongint;
     for i:=1 to length(s) do
       if s[i]='F'then n:=i; 
     for i:=length(s) downto 1 do 
       if s[i]='C'then m:=i;
   if m<n then writeln('Yes') 
  else writeln('No');  
end.

Measured memory_bytes: 128
#pragma comment(linker, "/stack:20000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/detail/standard_policies.hpp>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)

#define dbg(x) cerr << (#x) << " --> " << (x) << nl;
#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

#define Toktama ""

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
//typedef tree < pair <int, int>, null_type, less < pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 1e5 + 7, inf = 1e9 + 7, mod = 1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

int get_int() {
  char x = getchar();
  bool mns = 0;
  while (!isdigit(x)) mns |= x == '-', x = getchar();
  int res = 0;
  while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
  if (mns) res = -res;
  return res;
}
void add(int &x, int y) {
  x += y;
  if (x >= mod) x -= mod;
  if (x < 0) x += mod;
}
int mult(int x, int y) {
  return x * 1ll * y % mod;
}
int sum(int x, int y) {
  add(x, y);
  return x;
}

int n, p;
int a[N];

ll dp[100][5111];
ll calc(int v = 1, int sum = 0) {
  if (v > n) {
    if (sum % 2 == p) return 1;
    return 0;
  }
  if (~dp[v][sum]) return dp[v][sum];
  ll res = 0;
  res += calc(v + 1, sum);
  res += calc(v + 1, sum + a[v]);
  return dp[v][sum] = res;
}
void solve() {
  cin >> n >> p;
  rep(i, 1, n)
    cin >> a[i];
  memset(dp, -1, sizeof(dp));
  cout << calc();
}
int main() {
  #ifndef Toktama
    freopen (Toktama".in", "r", stdin);
    freopen (Toktama".out", "w", stdout);
  #endif
  Kazakhstan
  int t = 1;
  while (t--)
    solve();
  ioi
}


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

typedef long long int int64;

typedef struct line{
  int64 a,b;
} line;

int64 func(line l,int x){
  return l.a*x+l.b;;
}

void run(void){
  int n;
  int64 c;
  scanf("%d%lld",&n,&c);
  int *h=(int *)calloc(n,sizeof(int));
  int i;
  for(i=0;i<n;i++) scanf("%d",h+i);
  int64 *dp=(int64 *)calloc(n,sizeof(int64));
  line *q=(line *)calloc(n,sizeof(line));
  int front=0,last=0;
  q[last++]=(line){-2*h[0],(int64)h[0]*h[0]};
  for(i=1;i<n;i++){
    const int x=h[i];
    while(front+1<last && func(q[front],x)>=func(q[front+1],x)) front++;
    dp[i]=(int64)x*x+c+func(q[front],x);
    const line l={-2*x,dp[i]+(int64)x*x};
    while(front+1<last){
      const line a=q[last-2];
      const line b=q[last-1];
      if((l.a-b.a)*(a.b-l.b)<(l.a-a.a)*(b.b-l.b)) break;
      last--;
    }
    q[last++]=l;
  }
  printf("%lld\n",dp[n-1]);
}

int main(void){
  run();
  return 0;
}


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

long int gcd(long int a, long int b){
	long int c;
	if (a > b) swap(a, b);
	while (b % a > 0){
		c = b % a;
		b = a;
		a = c;
	}
	return a;
}

int main(){	
	long int A, B;
	cin >> A >> B;
	vector<int> p;
    long int g = gcd(A, B);
    long int n = 1;
	for (int i = 2; (long long)i*i <= g; i++) {
		while (g % i == 0) {
            g /= i;
            if (n < i) {
            	n = i;
            	p.push_back(i);
            }
        }
	}
    if (g > n) p.push_back(g);
    cout << (int) p.size()+1 << endl;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

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

	if (A + B < C + D) {
		cout << "Right" << endl;
	}
	else if (A + B > C + D) {
		cout << "Left" << endl;
	}
	else cout << "Balanced" << endl;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef map<int, int> mi;
typedef set<int> si;
#define VV(T) vector<vector< T > >
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define invrep(i, n) for(int i = (n)-1; i >= 0; i--)        // n-1, n-2, ..., 0
#define invREP(i, x, n) for(int i = (n)-1; i >= (x; i--)    // n-1, n-2, ..., x
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define PB push_back

#define COUT(x) cout << (x) << endl
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECCOUT(x) for(auto&youso_: (x) )cout<<youso_<<" ";cout<<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; }

ll dp[110][100100] = {0};
ll weight[110], value[110];

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

    int N, W; cin >> N >> W;
    rep(i, N) cin >> weight[i] >> value[i];

    rep(i, N){
        REP(sum_w, 0, W+1){

            if (sum_w - weight[i] >= 0){
                chmax(dp[i + 1][sum_w], dp[i][sum_w - weight[i]] + value[i]);
            }

            chmax(dp[i + 1][sum_w], dp[i][sum_w]);
        }
    }

    COUT(dp[N][W]);
}

Measured memory_bytes: 79360
/*#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>*/
#include<bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>	// Common file
#include <ext/pb_ds/tree_policy.hpp> 		// Including */
using namespace std;
//using namespace __gnu_pbds;
/*
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename F, typename S>
using ordered_map = tree<F, S, less<F>, rb_tree_tag, tree_order_statistics_node_update>;
*/

 
 
#define FOR(i,a,b)      for(i = a; i <= b; i++)
#define For(a,b)        for(int i=a; i<=b; i++)
#define REP(i,a,b)      for(i = a; i >= b; i--)
#define Rep(a,b)        for(int i=a; i>=b; i--)
#define F               first
#define S               second
#define pf              printf
#define sf              scanf
#define RESET(a,b)      memset(a,b,sizeof(a))
#define CLR(a)          memset(a,0,sizeof(a))
#define sqr(a)          ((a) * (a))
 
/*----------------------Graph Moves----------------*/
//const int fx[] = {+1, -1, +0, +0};
//const int fy[] = {+0, +0, +1, -1};
//const int fx[] = {+0, +0, +1, -1, -1, +1, -1, +1};   	// Kings Move
//const int fy[] = {-1, +1, +0, +0, +1, +1, -1, -1};  	// Kings Move
//const int fx[] = {-2, -2, -1, -1,  1,  1,  2,  2};	// Knights Move
//const int fy[] = {-1,  1, -2,  2, -2,  2, -1,  1};	// Knights Move
/*------------------------------------------------*/
 

int main()
{
	long a,b;
	long ans=0;
	cin>>a>>b;
	ans=(a-1)*(b-1);
	cout<<ans<<endl;
	return 0;	
}

Measured memory_bytes: 256
#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
using namespace std;
namespace mp = boost::multiprecision;

int cal(int x) {
  //cout << x << " " << di << endl;
  if (x == 0) return 0;
  else {
    int x2 = x, di = 0;
    while(x > 0) {
      if (x & 1) di++;
      x >>= 1;
    }
    x2 %= di;
    return cal(x2) + 1;
  }
}

int main() {
  int n; cin>>n;
  mp::cpp_int x = 0, u = 1;
  string s; cin>>s;
  for(int i=0;i<n-1;i++) u <<= 1;
  int di = 0;
  for(int i=0;i<n;i++) {
    x += (s[i] - '0') * u;
    u >>= 1;
    di += (s[i] - '0');
  }
  // cout << x << " " << di << endl;
  int x1 = 0;
  if (di > 1) x1 = static_cast<int>(x % (di-1));
  int x2 = static_cast<int>(x % (di+1));
  
  int p[n];
  int q1[n]={}, q2[n]={};
  //cout<<di-1<<" "<<di+1<<endl;
  int r = 1;
  for(int i=0;i<n;i++) {
    if (di <= 1) break;
    r %= di-1;
    q1[i] = r;
    r <<= 1;
    //cout<<q1[i]<<" ";
  } //cout<<endl;
  r = 1;
  for(int i=0;i<n;i++) {
    r %= di+1;
    q2[i] = r;
    r <<= 1;
    //cout<<q2[i]<<" ";
  } //cout<<endl;
  int an[n];
  
  for(int i=0;i<n;i++) {
    //cout << x1 << " " << x2 << " " << x << " " << u << endl;
    if (s[i] == '1') {
      //x^=u;
      if (di == 1) an[i] = 0;
      else {
        int x3 = x1 - q1[n-1-i];
        if (x3 < 0) x3 += di-1;
        //cout <<x3 << endl;
        an[i] = cal(x3) + 1;
        //cout << "@ "<<cal(x3) + 1 << endl;
      }
    } else {
      //x^=u;
      int x4 = x2 + q2[n-1-i];
      x4 %= di+1;
      //cout << x4 << endl;
      an[i] = cal(x4) + 1;
      // cout << cal(x4) + 1 << endl;
    }
    //x^=u;
    /*
    if (x & u) di--; else di++;
    x ^= u;
    cout << cal(x, di) << endl;
    x ^= u;
    if (x & u) di++; else di--;
    */
  }
  
  for(int i=0;i<n;i++) cout<<an[i]<<endl;
  //cout << x << endl;
}

Measured memory_bytes: 6124
#include <iostream>
#include <iomanip>
#include <random>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <sstream>
#include <bitset>
#include <cassert>
#include <fstream>
#include <queue>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
	#define DBG(X) cout << #X << "=" << (X) << '\n';
#else
	#define DBG(X)
#endif

using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::pair;
using std::swap;
using std::sort;
using std::lower_bound;
using std::unique;

using int64 = long long int;
using pii   = pair<int, int>;
using pii64 = pair<int64, int64>;

const int NIL = -1;
const int INF = (int)2e9;
const int64 INF64 = (int64)2e18;

void init_IO() {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
}

const int MAX_N = (int)1e5 + 777;

int parent[MAX_N], rank[MAX_N];

void init_dsu(int n) {
	for(int i = 0; i < n; ++i) {
		parent[i] = i;
		rank[i]   = 1;
	}
}

int get_parent(int v) {
	while(parent[v] != v) {
		v = parent[v];
	}

	return v;
}

int64 connect(int v, int u) {
	v = get_parent(v);
	u = get_parent(u);

	if(v != u) {
		if(rank[v] > rank[u])
			swap(v, u);

		int64 to_add = rank[v] * 1LL * rank[u];

		parent[v] = u;
		rank[u] += rank[v];

		return to_add;
	} else {
		return 0;
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	init_dsu(n);

	vector<pii> edges;

	for(int i = 0; i < m; ++i) {
		int v, u;
		cin >> v >> u;
		--v, --u;

		edges.emplace_back(v, u);
	}

	std::reverse(edges.begin(), edges.end());
	int64 cur = n * 1LL * (n - 1);
	cur /= 2;

	vector<int64> answ;

	for(auto& ed: edges) {
		answ.push_back(cur);
		cur -= connect(ed.first, ed.second);
	}

	for(int i = m - 1; i >= 0; --i) {
		cout << answ[i] << '\n';
	}
}

int main() {
	init_IO();
	solve();

	return 0;
}


Measured memory_bytes: 3828
r,c = map(int,raw_input().split())
sheet = []
for i in range(0,r):
    sheet.append(map(int,raw_input().split()))
total = [0] * (c+1)
for line in sheet:
    sum = 0
    for i,tmp in enumerate(line):
        total[i] += tmp 
        sum += tmp
    total[-1] += sum
    print " ".join(map(str,line))+" "+str(sum)
print " ".join(map(str,total))

Measured memory_bytes: 4296
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
//#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  vector<int> a(3);
  rep(i,3)cin>>a[i];
  sort(ALL(a));
  bool flag=false;
  if(a[0]==a[1]&&a[0]!=a[2])flag=true;
  else if(a[1]==a[2]&&a[0]!=a[2])flag=true;
  if(flag)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
INF = float("inf")


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


def LCM(a, b):
    return a*b//GCD(a, b)


def solve(N: int, T: "List[int]"):
    ans = 1
    for i in range(N):
        ans = LCM(ans, T[i])

    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    T = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, T)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#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, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

	int N, M, X;
	cin >> N >> M >> X;
	vector<int> C(N);
	vector<vector<int>> A(N, vector<int>(M));
	REP(i, N) {
		cin >> C[i];
		REP(j, M) {
			cin >> A[i][j];
		}
	}
	int res = INT_MAX;
	for (int bit = 0; bit < (1 << N); ++bit) {
		int sum_c = 0;
		vector<int> sum_a(M);
		REP(i, N) {
			if (bit >> i & 1) {
				sum_c += C[i];
				REP(j, M) {
					sum_a[j] += A[i][j];
				}
			}
		}
		bool ok = true;
		REP(j, M) {
			if (sum_a[j] < X) ok = false;
		}
		if (ok) {
			res = min(res, sum_c);
		}
	}
	if (res == INT_MAX) {
		cout << -1 << endl;
	} else {
		cout << res << endl;
	}

	return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
 
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define ll long long
using namespace std;
void file(){
	#ifndef ONLINE_JUDGE
    	freopen("tst.txt", "r", stdin);
	#endif	
}
const int N=1e5+5,MAX=3e7,MOD=1e9+7;


int n,m;
std::vector<int> g[N];

int dist[N][4];
int main()
{	
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

	scanf("%d %d",&n,&m);

	for(int i=0;i<N;i++)for(int j=0;j<4;j++)dist[i][j]=1e9;
	
	for(int i=0;i<m;i++){
		int a,b;

		scanf("%d %d",&a,&b);
		g[a].pb(b);
	}

	int src , dest;

	scanf("%d %d",&src,&dest);

	queue<pair<int,int>>q;

	q.push({src,0});
	dist[src][0]=0;
	while(!q.empty()){
		int u = q.front().first , curr = q.front().second;
		q.pop();
		for(auto v : g[u]){
			if(dist[v][(curr+1)%3]>dist[u][curr]+((curr+1)%3==0)){
				dist[v][(curr+1)%3]=dist[u][curr]+((curr+1)%3==0);
				q.push({v,(curr+1)%3});
			}
		}
	}
	if(dist[dest][0]>=1e9)printf("-1\n");
	else printf("%d\n",dist[dest][0]);	
}

Measured memory_bytes: 7296
//include
//------------------------------------------
#include <bits/stdc++.h>
using namespace std;
//conversion
//------------------------------------------
inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}
//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;
//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const long long INF = 1000000007;
//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))
//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
// chmax chmin
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main(void){
    ll N=50,K; cin >> K;
    ll a[N]; REP(i,N) a[i] = i+(K/N);
    K %= N;
    REP(i,K){
        a[i] += N;
        REP(j,N){
            if(i==j) continue;
            a[j]--;
        }
    }
    cout << N << endl;
    REP(i,N-1) cout << a[i] << " ";
    cout << a[N-1] << endl;
    return 0;
}

Measured memory_bytes: 256