akhauriyash/Code-Regression huggingface dataset:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

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

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    # すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    # グループの数を返す
    def group_count(self):
        return len(self.roots())

    # {ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    # print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
P = list(map(int, input().split()))

uf = UnionFind(N)

for i in range(M):
    x,y = map(int, input().split())
    uf.union(x-1,y-1) # x-1の木とy-1の木を併合する

cnt = 0
for i in range(N):
    if uf.same(i,P[i]-1):
        cnt+=1

print(cnt)

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;
#define rep(i,s,e) for(int i = (int)(s); i < (int)(e); ++i)
#define per(i,s,e) for(int i = (int)(s)-1; i >= (int)(e); --i)

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}

int main(){
  int a, b; cin >> a >> b;
  if(a < 10 && a > 0 && b < 10 &&  b > 0) cout << a * b << endl;
  else cout << -1 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
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;}
const int P = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;


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

    string s;
    cin>>s;
    int a=0,b=0,c=0;
    rep(i,s.length()){
        if(s[i]=='a')a++;
        else if(s[i]=='b')b++;
        else c++;
    }
    if(max({a,b,c})-min({a,b,c})>1){
        cout<<"NO"<<endl;
    }
    else cout<<"YES"<<endl;

//////////////////////////////////////////////////////
return 0;}

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

int main() {
  int N, K;
  cin >> N >> K;
  string S;
  cin >> S;
  if (S.at(K-1) == 'A') {
    S.at(K -1) = 'a';
  }
  if (S.at(K-1) == 'B') {
    S.at(K -1) = 'b';
  }
  if (S.at(K-1) == 'C') {
    S.at(K -1) = 'c';
  }
  cout << S << endl;
}


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

using namespace std;

typedef long long ll;

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  while (a > 0 && c > 0) {
    c -= b;
    if (c <= 0) {
      cout << "Yes" << endl;
      break;
    }
    a -= d;
    if (a <= 0) {
      cout << "No" << endl;
      break;
    }
  }
  return 0;
}

Measured memory_bytes: 3596
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    a,b =map(int, input().split())
    if a%3==0:
        print('Possible')
        exit()
    if b%3==0:
        print('Possible')
        exit()
    if (a+b)%3==0:
        print('Possible')
        exit()
    print('Impossible')

if __name__ == '__main__':
    main()

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)()
#define all(a) a.begin(),a.end()
#define vec vector
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return expm(x,big-2);
}

void f(int sx,int sy,int tx,int ty){
    rep(i,abs(sy-ty)){
        if(sy<ty)cout << 'U';
        else cout << 'D';
    }
    rep(i,abs(sx-tx)){
        if(sx<tx)cout << 'R';
        else cout << 'L';
    }
    return;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(10);
    /*--------------------------------*/

    int sx,sy,tx,ty;
    cin >> sx >> sy >> tx >> ty;

    bool lastleft=false;
    if(sx<tx)lastleft=true;

    f(sx,sy,tx,ty);
    f(tx,ty,sx,sy);
    cout << "LU";
    f(sx,sy,tx,ty);
    cout << "RDRD";
    f(tx,ty,sx,sy);
    cout << "LU" << endl;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;
using vi = vector<int>; 
using vvi = vector<vi>; 
using vl = vector<ll>; 
using vvl = vector<vl>; 
using vs = vector<string>;
using vvs = vector<vs>; 
using vc = vector<char>;
using vvc = vector<vc>; 
using vb = vector<bool>;
using vvb = vector<vb>; 

#define rep(i,n) ;for( int i =0; i < n ; i ++)
#define all(a) a.begin(),a.end()
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define f(i,a,b) for(int i=a;i<b;i++)
#define pri(a)  printf("%.14lf\n",a);
#define sz(a) ((int)a.size())
#define MOD 1000000007
bool is_int_lround(double x){
  return std::lround(x)==x;
}
ll keta(ll x){
  ll n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}

ll conbi(int n,int m){
  
  cin>>n>>m;
  vector<ll> a(100);
  a[0] =1;
  for(int i=0;i<14;i++){
    a[i+1]=a[i]*(i+1);
  }
  return a[n] /(a[m] *a[n-m]);
}

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;//繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll kaijoMOD(ll x){
  ll z=1;
  if(x==0){
    return 1;
  }
  while(x>0){
    z *=x;
    z %=MOD;
    x--;
  }
  return z;
}
ll div_num(ll n){
  vl div(n+1,1);
  for(ll i=2;i*i<=n;i++){ 
    while(n%i==0){
      n /=i;
      div[i]++;
    }
  }
  if(n!=1)div[n]++;
  ll num=1;
  for(ll i=0;i<=n;i++){
    num*=div[i];
  }
  return num;
}
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

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



//vc alp ={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
//vc Alp ={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
//cout<<""<<endl;
int main(){
  int H,W;cin>>H>>W;
  vvi F(H, vector<int> (W));
  rep(i,H){
    rep(j,W){
      cin>>F[i][j];
    }
  }
  vs ans;
  rep(i,H){
    rep(j,W){
      if(j!=W-1){
        if(F[i][j]%2==1){
          F[i][j]--;F[i][j+1]++;
          ans.push_back(to_string(i+1) + " " +to_string(j+1)+" " +to_string(i+1)+" " +to_string(j+2) );
        }
      }
      else if(j==W-1 && i!=H-1){
        if(F[i][j]%2==1){
          F[i][j]--;F[i+1][j]++;
          ans.push_back(to_string(i+1) +" "  +to_string(j+1)+" " +to_string(i+2)+" " +to_string(j+1) );
        }
      }
    }
    
  }
  cout<<ans.size()<<endl;
  rep(i,ans.size()){
   cout<<ans[i]<<endl;
  }
}







Measured memory_bytes: 11892
#include <bits/stdc++.h>
using namespace std;
typedef long double ll;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  //freopen("data.in", "r", stdin);
  char c; cin >> c;
  cout << char(c + 1) << endl;
  return 0;
}





















Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int n,k;
  cin>>n>>k;
  int arr[n];
  for(int i=0;i<n;i++)
  {
    cin>>arr[i];
  }
  sort(arr,arr+n);
  int ans=0;
  for(int i=0;i<k;i++)
  {
    ans=ans+arr[i];
  }
  cout<<ans;
}

Measured memory_bytes: 3628
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] s = sc.next().toCharArray();
		char[] t = sc.next().toCharArray();
		int S = s.length; int T = t.length;
		boolean flg2 = false;
		for(int i = S - T ; i >= 0 ; i--) {
			boolean flg = true;
			for(int j = 0 ; j < T ; j++) {
				if(s[j + i] != t[j] && s[j + i] != '?') {
					flg = false;
				}
			}
			if(flg) {
				for(int j = 0 ; j < T ; j++) {
					s[j + i] = t[j];
					flg2 = true;
				}
				break;
			}
		}
		if(flg2) {
			for(int i = 0 ; i < S ; i++) {
				if(s[i] == '?') s[i] = 'a';
			}
			String ans = String.valueOf(s);
			System.out.println(ans);
		} else {
			System.out.println("UNRESTORABLE");
		}

	}
}

Measured memory_bytes: 21972
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x); i<=(y); i++)
#define per(i,x,y) for (int i=(x); i>=(y); i--)
#define N 1048576
#define ll long long
using namespace std;
int n,m,cnt,a[N],b[109],l[20][N],r[20][N],f[N],g[N];
struct node{ int x,y; node(){} node(int a,int b){ x=a,y=b; } }c[N];
const bool cmp(const node &x,const node &y){ return x.y<y.y; }
int main(){
	scanf("%d%d",&n,&m);
	for (; m; m>>=1) b[++cnt]=m; cnt++;
	rep (i,1,cnt>>1) swap(b[i],b[cnt-i+1]);
	m=1<<cnt-1;
	rep (i,1,n) scanf("%d",&a[i]);
	rep (i,1,cnt){//预处理l[i][j]和r[i][j]表示第i层第j个点所在线段的左右端点
		l[i][1]=1; r[i][n]=n;
		rep (j,2,n) l[i][j]=a[j]-a[j-1]<=b[i]?l[i][j-1]:j;
		per (j,n-1,1) r[i][j]=a[j+1]-a[j]<=b[i]?r[i][j+1]:j;
	}
	rep (i,0,m-1) g[i]=n+1,f[i]=0;//f[i]表示状态为i，从1开始延伸出去的最远长度；g[i]表示从n开始延伸的最远长度
	//状态s的意思是，如果某位为1则表示当前层选了线段
	rep (i,1,m-1) rep (j,1,cnt-1) if ((i>>j-1)&1){
		int k=i^1<<j-1;//f[k]->f[i]
		f[i]=max(f[i],f[k]<n?r[j][f[k]+1]:n);
		g[i]=min(g[i],g[k]>1?l[j][g[k]-1]:1);
	}
	rep (i,0,m-1)
		if (f[i]+1<g[m-1^i]) c[i+1]=node(f[i]+1,g[m-1^i]-1);
		else{
			rep(j,1,n) puts("Possible"); return 0;
		}
	sort(c+1,c+1+m,cmp);
	for (int i=1,j=1,k=0; i<=n; i++){
		while (j<=m && c[j].y<=r[cnt][i]){
			k=max(k,c[j].x); j++;
		}
		if (k>=l[cnt][i]) puts("Possible"); else puts("Impossible");
	}
	return 0;
}

Measured memory_bytes: 90496
#include <stdio.h>
int main(void)
{
  int x,i,j,n;
  while(1){
    int ice[10]={0};
    scanf("%d",&n);
    if(!n) break;
    for(i=0;i<n;i++){
      scanf("%d",&x);
      ice[x]++;
    }
    for(i=0;i<10;i++){
      if(!(ice[i]))
	puts("-");
      else{
	for(j=0;j<ice[i];j++)
	  putchar('*');
	putchar('\n');
      }
    }
  }
  return 0;
}

Measured memory_bytes: 572
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

int main() {
    int n, m; cin >> n >> m;
    using Graph = vector<vector<int>>;
    Graph g(n);
    while (m--) {
        int u, v; cin >> u >> v; u--, v--;
        g[u].emplace_back(v);
    }
    int s, t; cin >> s >> t; s--, t--;
    vector<vector<int>> dp(n, vector<int>(3, -1));
    queue<pair<int, int>> que;
    dp[s][0] = 0; que.emplace(s, 0);
    while (!que.empty()) {
        int u, r; tie(u, r) = que.front(); que.pop();
        int nr = (r + 1) % 3;
        for (int v: g[u]) if (dp[v][nr] == -1) {
            dp[v][nr] = dp[u][r] + 1;
            que.emplace(v, nr);
        }
    }
    if (~dp[t][0]) dp[t][0] /= 3;
    cout << dp[t][0] << endl;
    return 0;
}

Measured memory_bytes: 11136
A = input()

len0 = lenA = len(A) 
while(True):
    A = A.replace("10","").replace("01","").replace("1"*1000 + "0"*1000,"").replace("0"*1000 + "1"*1000,"")
    if lenA == len(A):
        break
    lenA = len(A)
print(len0 - lenA)


Measured memory_bytes: 3316
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		int[] ans = new int[n];
		ans[0] = 0;
		ans[1] = Math.abs(arr[0] - arr[1]);
		for (int i = 2; i < n; i++) {
			ans[i] = Math.min(ans[i - 1] + Math.abs(arr[i] - arr[i - 1]), ans[i - 2] + Math.abs(arr[i] - arr[i - 2]));
		}
		System.out.println(ans[n - 1]);
	}
}


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

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

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,W=LI()
  w=[]
  v=[]
  dp=[[0 for _ in range(W+1)] for __ in range(n+1)]
  for _ in range(n):
    a,b=LI()
    w.append(a)
    v.append(b)

  for i in range(n)[::-1]:
    for j in range(W+1):

      if j<w[i]:
        dp[i][j]=dp[i+1][j]

      else:
        dp[i][j]=max(dp[i+1][j],dp[i+1][j-w[i]]+v[i])

  return dp[0][W]

# main()
print(main())


Measured memory_bytes: 181560
#include <bits/stdc++.h>
#include <algorithm>
#define rep2(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i,n) rep2(i,0,n)
#define all(x) (x).begin(), (x).end()
#define sz size()
#define pb push_back
#define bg begin()
#define ed end()
#define fi first()
#define se second()
using namespace std;
using ll = long long;
using vint = vector<int>;
using pint = pair<int,int>;
using vpint = vector<pint>;
template <typename T>
T sq(T x){
  return x * x;
}
ll mod = 1e9 + 7;

signed main (){
  ll X , t;
  cin >> X >> t;
int  ans = X -t;
  cout << max(0,ans) << endl;

    return 0;
}


Measured memory_bytes: 3616
def mergesort(l):
    n = len(l)
    if(n == 1):
        return l
    elif(n <= 2):
        if(l[0] > l[1]):
            return [l[1],l[0]]
        else:
            return l
    else:
        tmp1 = mergesort(l[:n//2])
        tmp2 = mergesort(l[n//2:])
        x = n//2
        y = n-x
        l = []
        for i in range(n):
            if(tmp1[-x] < tmp2[-y]):
                l.append(tmp1[-x])
                x -= 1
            else:
                l.append(tmp2[-y])
                y -= 1
            if(x*y == 0):
                if(x == 0):
                    l += tmp2[-y:]
                else:
                    l += tmp1[-x:]
                break
        return l
n,k = map(int,input().split())
p = list(map(int,input().split()))
p = mergesort(p)
q = 0
for i in range(k):
    q += p[i]
print(q)

Measured memory_bytes: 67888
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

#define INFI 1000

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

  //白ならtrue
  vector<vector<bool>> Map(H + 1, vector<bool>(W + 1, false));
  vector<vector<int>> shortest(H + 1, vector<int>(W + 1, INFI));

  int whiteCount = 0;

  vector<string> tmpstr(H);
  for (int i = 0; i < H; i++) {
    cin >> tmpstr[i];
  }

  for (int i = 1; i < H + 1; i++) {
    for (int j = 1; j < W + 1; j++) {
      if (tmpstr[i - 1][j - 1] == '.') {
        whiteCount++;
        Map[i][j] = true;
      }
    }
  }

  shortest[1][1] = 1;
  queue<pair<int, int>> que;
  que.push(make_pair(1, 1));

  int dx[4] = {0, 1, 0, -1};
  int dy[4] = {1, 0, -1, 0};

  while (!que.empty()) {
    pair<int, int> tmp = que.front();
    que.pop();
    for (int i = 0; i < 4; i++) {
      int nx = tmp.first + dx[i];
      int ny = tmp.second + dy[i];

      if (1 <= nx && nx <= W && 1 <= ny && ny <= H && Map[ny][nx] == true &&
          shortest[ny][nx] == INFI) {
        shortest[ny][nx] = shortest[tmp.second][tmp.first] + 1;
        que.push(make_pair(nx, ny));
      }
    }
  }

  int ans;

  if (shortest[H][W] != INFI) {
    ans = whiteCount - shortest[H][W];
  } else {
    ans = -1;
  }

  cout << ans << "\n";
  return 0;
}


Measured memory_bytes: 256
l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())

print(l[K-1])



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

typedef struct{
  int no;
  int KOMA;
}P;

int main(){

  int n,p;
  P mem[50];
  while(1){
    for(int i=0;i<50;i++)mem[i].no=i,mem[i].KOMA=0;
    int ban=0;

    cin >> n >> p;
    int WAN = p;

    if(n==0 && WAN==0) break;

    while(1){
      if(ban==n)ban=0;
      if(WAN>0){
	mem[ban].KOMA++,WAN--;
      }else{
	WAN=mem[ban].KOMA;
	mem[ban].KOMA=0;
      }
      if(p==WAN){  //勝判定
	cout << ban << endl;   //
	break;                 //
      }
      ban++;
    }
  }
}

Measured memory_bytes: 1160
#pragma GCC optimize("O3")
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<cstdlib>
#include<set>
#include<vector>
#include<sstream>
#include<queue>
#include <iomanip>
#include<unordered_set>
constexpr auto INF = 9223372036854775807;
typedef long long int ll;
typedef unsigned long long int ull;
typedef unsigned long int ul;
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i+=1)
#define endl '\n'
#define all(x) x.begin(),x.end()
using namespace std;
inline int mex(unordered_set<int> st)
{
    int m = 0;
    while (st.find(m) != st.end())
    {
        m += 1;
    }
    return m;
}
inline int calculateGrundy(int n)
{
    if (n == 1)
        return 0;
    unordered_set<int> mexi;
    for (int i = 1; i <= sqrt(n); i += 1)
    {
        if (n % i == 0)
        {
            if (n / i != n)
                mexi.insert(calculateGrundy(n / i));
            mexi.insert(calculateGrundy(i));
        }
    }
    return mex(mexi);
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    cin >> s;
    string one = "", sec = "";
    ll rev_sum = 0;
    ll q;
    cin >> q;
    f(i, 0, q)
    {
        ll t;
        cin >> t;
        if (t == 1)
        {
            rev_sum += 1;
            rev_sum %= 2;
        }
        else
        {
            ll f;
            string c;
            cin >> f >> c;
            if (rev_sum == 0 && f == 1)
            {
                one = c + one;
            }
            else if (rev_sum == 0 && f == 2)
            {
                sec += c;
            }
            else if (rev_sum == 1 && f == 1)
            {
                sec += c;
            }
            else if (rev_sum == 1 && f == 2)
            {
                one = c + one;
            }
        }
    }
    string ans = "";
    if (rev_sum == 0)
        s = one + s + sec;
    else
    {
        reverse(all(sec));
        reverse(all(s));
        reverse(all(one));
        s = sec + s + one;
    }
    cout << s;
    return 0;
}

Measured memory_bytes: 1316
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
const ll BIG=1e15;

vector<int> s[30],t;

int main(){
    string S,T;
    cin>>S>>T;
    for(int i=0;i<S.size();i++){
        s[S.at(i)-'a'].push_back(i);
    }

    for(int i=0;i<T.size();i++) t.push_back(T.at(i)-'a');
    int N=S.size();
    bool able=true;
    ll amari=N-1, shou=-1;
    for(int i=0;i<t.size();i++){
        int x=t.at(i);
        if(s[x].size()==0) {able=false; break;}
        auto itr=upper_bound(s[x].begin(),s[x].end(),amari);
        if(itr==s[x].end()) {shou++; amari=s[x].at(0);}
        else amari=*itr;
    }
    if(!able) cout<<-1<<endl;
    else cout<<N*shou+amari+1<<endl;
    
}

Measured memory_bytes: 1728
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <functional>
#include <queue>
#include <cstring>
#include <string>
#include <cstdio>
#include <cstdlib>

#define int long long

using namespace std;

int n, p;
vector<int> a;

int memo[51][5001];
bool checked[51][5001];

int rec(int idx, int sum) {
  if (idx >= n) {
    if (sum % 2 == p) {
      return 1;
    } else {
      return 0;
    }
  }

  if (checked[idx][sum]) {
    return memo[idx][sum];
  }
  int ret = rec(idx + 1, sum + a[idx]) + rec(idx + 1, sum);

  checked[idx][sum] = true;
  return memo[idx][sum] = ret;
}

signed main() {
  cin >> n >> p;
  a.resize(n);

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

  cout << rec(0, 0) << endl;





  return 0;
}

Measured memory_bytes: 1280
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <tuple>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
#include <cassert>
#include <random>
constexpr long long int MOD = 1000000007LL;

long long int power(const long long int base, const int exp) {
	switch (exp) {
	case 0: return 1LL;
	case 1: return base % MOD;
	default: return power(base * base % MOD, exp / 2) * power(base, exp % 2) % MOD;
	}
}
long long int inverse(const long long int base) {
	return power(base, MOD - 2);
}
long long int power_by_size(const int size) {
	static std::vector<long long int> memo(200001, -1);
	if (memo[size] >= 0) return memo[size];
	return memo[size] = power(2, size);
}
long long int inverse_by_size(const int size) {
	static std::vector<long long int> memo(200001, -1);
	if (memo[size] >= 0) return memo[size];
	return memo[size] = inverse(power(2, size));
}
void move_root(int from, int to, std::vector<int>& size, const std::vector<std::vector<int>>& nodes) {
	int root_size = size[from];
	int child_size = size[to];
	size[from] -= child_size;
	size[to] = root_size;
}
long long int prob(int root, const std::vector<int>& size, const std::vector<std::vector<int>>& nodes) {
	long long int not_hole = inverse_by_size(size.size() - 1);
	for (const auto child : nodes[root]) {
		not_hole += inverse_by_size(size.size() - 1 - size[child]) * (1 - inverse_by_size(size[child]) + MOD) % MOD;
		not_hole %= MOD;
	}
	return (1 - not_hole + MOD) * inverse_by_size(1) % MOD;
}
long long int cal_estimate(int root, int prev, std::vector<int>& size, const std::vector<std::vector<int>>& nodes) {
	long long int result = prob(root, size, nodes);
	for (const auto next : nodes[root]) if (next != prev) {
		move_root(root, next, size, nodes);
		result += cal_estimate(next, root, size, nodes);
		result %= MOD;
		move_root(next, root, size, nodes);
	}
	return result;
}
int main() {
	int n; std::cin >> n;
	std::vector<std::vector<int>> nodes(n);
	std::vector<int> size(n, 0), prev(n, -1);
	for (auto i = 1; i < n; ++i) {
		int a, b; std::cin >> a >> b; --a; --b;
		nodes[a].push_back(b); nodes[b].push_back(a);
	}
	std::stack<int> stack; stack.push(0);
	while (!stack.empty()) {
		auto top = stack.top(); stack.pop();
		if (top >= 0) {
			stack.push(-top - 1);
			size[top] = 1;
			for (const auto next : nodes[top]) if (size[next] == 0) {
				prev[next] = top;
				stack.push(next);
			}
		}
		else {
			if (prev[-top - 1] >= 0) {
				size[prev[-top - 1]] += size[-top - 1];
			}
		}
	}
	std::cout << cal_estimate(0, -1, size, nodes) << std::endl;
}

Measured memory_bytes: 26112
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define Mod 1000000007
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
#define INF 999999999999999999
#define NN (ll)(1e6+5)
int mod(string s,int a) 
{ 
    int ans=0; 
    for (int i=0;i<s.length();i++) 
         ans=(ans*10+(int)s[i]-'0')%a; 
    return ans; 
}
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {    
       ll n,i;
       cin>>n;
       string ans="";
       //n--;
       while(1)
       {
           ll x;
           if(n<=26)
           {
               ans+=(char)(n+'a'-1);
               break;
           }
           x=n%26;
           //cout<<x<<" ";
           if(x==0)
            x=26;
           ans+=(char)(x+'a'-1);
           n/=26;
           if(x==26)
            n--;
           //cout<<n<<"\n";
       }
       reverse(ans.begin(),ans.end());
       cout<<ans<<"\n";
   }
}

Measured memory_bytes: 3648
n = int(input())
x = y = 1
for i in range(n):
    t, a = map(int, input().split())
    bx = 1 if x % t else 0
    by = 1 if y % a else 0
    k = max(x//t + bx, y//a + by)
    x, y = t*k, a*k
print(x+y)

Measured memory_bytes: 3060
H,W,K=[int(a) for a in input().split(" ")]
wp = [0]*(W-1)
wv = [0]*W
curr, prev = [0]*W, [0]*W
prev[0] = 1
mod = 1000000007

def comb(n):
    prev, curr = [1,1], [0,0]
    if n<1: return 1
    for i in range(n-1):
        curr[0] = prev[1]
        curr[1] = prev[0]+prev[1]
        prev,curr = curr,prev
    return sum(prev)

for i in range(W):
    nl, nr = max(0,i-1), max(0, W-i-2)
    wv[i] = comb(nl)*comb(nr)

for i in range(W-1):
    nl, nr = max(0, i-1), max(0, W-i-3)
    wp[i] = comb(nl)*comb(nr)

for i in range(H):
    for i in range(W):
        curr[i]=0
    for i in range(W):
        curr[i] = (curr[i] + (wv[i]*prev[i])%mod)%mod
        if i>=1:
            curr[i-1] = (curr[i-1]+(wp[i-1]*prev[i])%mod)%mod
        if i<=W-2:
            curr[i+1] = (curr[i+1]+(wp[i]*prev[i])%mod)%mod
    prev, curr = curr, prev
print(prev[K-1]%mod)

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

// s1がs2の部分文字列
bool substring(string s1,string s2){
    int n1 = s1.size();
    int n2 = s2.size();
    if(n1>n2) return false;
    int j=0;
    rep(i,n2){
        if(s1[j]==s2[i]){
            j++;
        }
    }
    return j==n1;
}

int main(void){
    string s;
    cin>>s;
    cout<<((substring(s,"AKIHABARA")&&substring("KIHBR",s)) ? "YES" : "NO")<<endl;
}


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

using namespace std;
using ll = long long;

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

  int n;
  cin >> n;
  vector<double> p(n);
  for (int i = 0; i < n; i++)
    cin >> p[i];

  // dp[i][j] := i番目までを調べた時に表がj枚出ている確率
  vector<vector<double>> dp(n + 1, vector<double>(n + 1, 0));
  dp[0][0] = 1;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= i; j++) {
      // 表
      dp[i + 1][j + 1] += dp[i][j] * p[i];
      // 裏
      dp[i + 1][j] += dp[i][j] * (1 - p[i]);
    }
  }

  double ans = 0;
  for (int j = n / 2 + 1; j <= n; j++) {
    ans += dp[n][j];
  }
  cout << fixed << setprecision(10) << ans << endl;

  return 0;
}


Measured memory_bytes: 73788
#include<bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
/*
#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_upd>
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
*/
using namespace std;

#define LL long long
#define LD long double
#define PB push_back
#define MP make_pair
#define all(x) x.begin(), x.end()

const LL MOD = 998244353;
const LD EPS = 0.0000001 ;

LL pows(LL a, LL b)
{
	if (b == 0) return 1LL;
	LL temp = pows(a, b / 2);
	temp = (temp * temp) % MOD;
	if (b % 2) temp = (temp * a) % MOD;
	return temp;
}

const int N = 3005;

LL dp[N][N];

int arr[N];
int n;

LL solve(int idx, int sum)
{
	if (sum == 0) return (n - idx + 1LL);
	if (idx >= n) return 0;
	if (sum < 0) return 0;
	LL &ans = dp[idx][sum];
	if (ans != -1) return ans;
	ans = 0;
	ans = (solve(idx + 1, sum) + solve(idx + 1, sum - arr[idx])) % MOD;
	return ans;
}

int main(void)
{
	memset(dp, -1, sizeof(dp));
	int s; cin >> n >> s;
	for (int i = 0; i < n; i++) cin >> arr[i];

	LL ans = 0;

	for (int i = 0; i < n; i++){
		LL temp = solve(i + 1, s - arr[i]);
		temp = (temp * (i + 1LL)) % MOD;
		ans = (ans + temp) % MOD;
	}

	cout << ans << endl;

	return 0;
}




Measured memory_bytes: 70912
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#define llong long long
#define INF (__INT32_MAX__ / 2)
#define EPS 10e-8

using namespace std;
typedef pair<int, int> ipair;
llong modulo(llong left, llong right) { return (left % right + right) % right; }

int N, K;
string S;

int section_count(string S) {
    string aSa = "a" + S;
    int res = 0;
    for(int i = 1; i < N + 1; ++i) {
        if(aSa[i] != aSa[i - 1]) {
            res++;
        }
    }
    return res;
}


int main(int argc, char **argv) {
    cin >> N >> K >> S;

    int sections = section_count(S);
    int res = N - sections;

    int X = sections % 2 == 1 ? 
            (sections - 1) / 2 : (sections - 2) / 2;
    
    X = min(K, X);
    sections -= X * 2;
    K -= X;
    res += X * 2;

    if(K > 0 && sections > 1) {
        res++;
    }

    cout << res << endl;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
 long long n,t[1000]={},a[1000]={};
 cin>>n;
 for(int i=0;i<n;i++){
  cin>>t[i]>>a[i];
  if(i)
   if(a[i-1]>a[i] || t[i-1]>t[i]){
    long long j=1;
    if((a[i-1]-1)/a[i]>(t[i-1]-1)/t[i]) j+=(a[i-1]-1)/a[i];
    else j+=(t[i-1]-1)/t[i];
    a[i]*=j;
    t[i]*=j;
   }
 }
 cout<<a[n-1]+t[n-1]<<endl;
 return 0;
}

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

int main()
{
	int N;
	cin >> N;
	int res = N;
	for (int i = 1; i < N; i++) {
		int x = i, y = N - i, sum = 0;
		while (x) sum += x % 10, x /= 10;
		while (y) sum += y % 10, y /= 10;
		res = min(res, sum);
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
int MOD = 1000000007;

signed main(){
    int N;
    cin >> N;
    
    int A[N];
    int guusu = 0;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(A[i]%2 == 0) guusu++;
    }
    
    int sum = pow(3,N);
    int hiku = 0;
    if(guusu == 0) hiku = 1;
    else hiku = pow(2,guusu);
    
    cout << sum - hiku << endl;
    
    
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
using namespace std;
int main(){
  int N,M;
  cin >> N;
  cin >> M;
  int hiyou[1000];
  int kijun[1000];
  for(int i = 0;i < N;i++)
    cin >> hiyou[i];
  
  for(int i = 0;i < M;i++)
    cin >> kijun[i];
  
  int vote[1000] = {};
  
  for(int i = 0;i < M;i++){
    for(int j = 0;j < N;j++){
      if(kijun[i] >= hiyou[j]){ 
	vote[j]++;
	break;
      }
    }
  }
  for(int i = M;i > 0 ;i--){
    for(int j = 0;j < N;j++){
      if(i == vote[j]){
	cout << j + 1 <<endl;
	return 0;
      }
    }
  }   
}

Measured memory_bytes: 1168
#include<cstdio>

using namespace std;

int main(){
	for(int t=1,n;scanf("%d",&n),n;t++){
		int cell[10][10],type=0,cnt=1,x=0,y=0;
		while(!(x==n-1 && y==n-1)){
			if(type%2==0){
				if((y==0 || y==n-1) && x<n-1)
						cell[y][x++]=cnt++;
				else	cell[y++][x]=cnt++;
			}
			else if(type==1)
				while(0<x && y<n-1)	cell[y++][x--]=cnt++;
			else
				while(0<y && x<n-1)	cell[y--][x++]=cnt++;
			type=(type+1)%4;
		}
		cell[n-1][n-1]=cnt;

		printf("Case %d:\n",t);
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++)	printf("%3d",cell[i][j]);
			putchar('\n');
		}
	}

	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(){
  int N,K,d,A,S;
  int T[102];
  scanf("%d %d\n",&N,&K);
  S=N;
  for(int i=1;i<=N;i++) T[i]=0;
  for(int i=1;i<=K;i++){
    scanf("%d\n",&d);
    for(int j=1;j<=d;j++){
      scanf("%d",&A);
      T[A]=1;
    }
  }
  for(int i=1;i<=N;i++) S-=T[i];
    
  printf("%d\n",S);
  return 0;
}

Measured memory_bytes: 1736
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cassert>
#include<climits>
#include<deque>
#include<queue>
#include<set>
#include<map>
#include<cstring>
#include<string>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 50*50
#define MAX_V 50*50

using namespace std;

//

struct edge{
  int to,cap,rev;
  edge(int to=IINF,int cap=IINF,int rev=IINF):to(to),cap(cap),rev(rev){}
};
 
vector<edge> G[MAX_V];
bool used[MAX_V];
 
void add_edge(int from,int to,int cap){
  G[from].push_back(edge(to,cap,G[to].size()));
  G[to].push_back(edge(from,0,(int)G[from].size()-1));
}
 
int dfs(int v,int t,int f){
  if(v == t)return f;
  used[v] = true;
  for(int i=0;i<G[v].size();i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to,t,min(f,e.cap));
      if(d > 0){
	e.cap -= d;
	G[e.to][e.rev].cap += d;
	return d;
      }
    }
  }
  return 0;
}
 
int max_flow(int s,int t){
  int flow = 0;
  for(;;){
    memset(used,0,sizeof(used));
    int f = dfs(s,t,IINF);
    if(f == 0)return flow;
    flow += f;
  }
}

//

int counter[4];// H W C M
int csum[4];
int N[3]; // Nw Nc Nm
int limit[3][MAX];
int input_buf[3][MAX][MAX];
int Grave[3][2];
int V;

inline bool first_input(){
  bool fin = true;
  rep(i,4){
    cin >> counter[i];
    if(i == 0)csum[i] = counter[i];
    else      csum[i] = 2*counter[i] + csum[i-1];
    if( counter[i] >= 0 )fin = false;
  }
  rep(i,3){
    cin >> N[i];
    if( counter[i] >= 0 )fin = false;
  }
  return !fin;
}

int main(){
  while(first_input()){
    rep(i,3){
      rep(j,counter[i+1]){
	cin >> limit[i][j];
	rep(k,limit[i][j]){
	  cin >> input_buf[i][j][k];
	  input_buf[i][j][k]--;
	}
      }
    }

    int source = csum[3],sink = source+1;
    Grave[0][0] = sink+1       , Grave[0][1] = Grave[0][0]+1;
    Grave[1][0] = Grave[0][1]+1, Grave[1][1] = Grave[1][0]+1;
    Grave[2][0] = Grave[1][1]+1, Grave[2][1] = Grave[2][0]+1;

    V = Grave[2][1]+1;
    rep(i,V)G[i].clear();

    rep(i,3)rep(j,counter[i+1])add_edge(csum[i]+j,csum[i]+j+counter[i+1],1);

    rep(i,counter[0])add_edge(source,i,1);
    rep(i,counter[3])add_edge(csum[2]+i+counter[3],sink,1);
    rep(i,3){
      rep(j,counter[i+1]){
	rep(k,limit[i][j]){
	  add_edge(input_buf[i][j][k]+((i-1)>=0?csum[i-1]:0)+((i)?counter[i]:0),csum[i]+j,1);
	}
      }
    }

    rep(k,2){
      int coef = ((k==0)?0:counter[k]);
      rep(i,counter[k])add_edge(((k-1)>=0?csum[k-1]:0)+i+coef,Grave[k][0],1);
      add_edge(Grave[k][0],Grave[k][1],N[k]);
      rep(i,counter[k+2])add_edge(Grave[k][1],csum[k+1]+i,1);
    }

    rep(i,counter[2])add_edge(csum[1]+i+counter[2],Grave[2][0],1);
    add_edge(Grave[2][0],sink,N[2]);

    int tmp;
    cout << (tmp=max_flow(source,sink)) << endl;
    assert(0 <= tmp && tmp <= counter[0] );

  }
  return 0;
}

Measured memory_bytes: 9908
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner scan = new Scanner(System.in);
    String s = scan.next();
    
    int counter = 0;
    
    for(int i = 0; i < s.length()/2; i ++){
      if(s.charAt(i) != s.charAt(s.length() - 1 - i)){
        counter += 1;
      }
    }
    
    System.out.println(counter);
  }
}


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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }
template <class T> void amin(T& a,T b){ a=min(a,b);}
template <class T> void amax(T& a,T b){ a=max(a,b);}

int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int n; ll k;
	cin >>n >>k;
	vector<ll> x(n);
	rep(i, n) cin >>x[i];
	
	vector<vector<ll>> dp(44, vector<ll>(2, -(1LL<<60)));
	dp[43][0] = 0;
	repr(i, 42, 0){
		ll ks = 1LL<<i;
		int ct =0;
		rep(j, n) ct += (x[j]>>i) &1;
		int ct2 = n -ct;
		//dbg(ct,ct2,ks,k);
		if((k>>i) &1){
			dp[i][0] = max(dp[i][0], dp[i+1][0] + ks * ct2 );
			dp[i][1] = max(dp[i][1], dp[i+1][0] + ks * ct );
		}else{
			dp[i][0] = max(dp[i][0], dp[i+1][0] + ks * ct );
		}
		
		dp[i][1] = max(dp[i][1], dp[i+1][1] + ks * max(ct, ct2) );
		
	}
	cout << max(dp[0][0], dp[0][1]) <<"\n";
/*	VI ct(43, 0),  uk(43, 0);
	rep(i, n){
		rep(j, 43){
			if(max(k, x[i]) >= (1LL<<j)) uk[j]++;
			if((x[i] >>j &1)) ct[j]++;
		}
	}
	for(auto x :ct) printf("%d, ",x); puts("");
	for(auto x :uk) printf("%d, ",x); puts("");
	ll res=0;
	rep(i, 43){
		ll ks=1LL<<i;
		//dbg(i, ct[i], n-ct[i]);
		res += ks * max(ct[i], (ks<=k? uk[i]-ct[i]: 0));
	}
	cout << res <<"\n";
*/
	return 0;
}


Measured memory_bytes: 1024
#include<algorithm>
#include<stack>
#include<ctime>
#include<cstring>
#include<cmath>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<queue>
using namespace std;
inline int read(){
	int num=0,f=1;char x=getchar();
	while(x<'0'||x>'9'){if(x=='-')f=-1;x=getchar();}
	while(x>='0'&&x<='9'){num=num*10+x-'0';x=getchar();}
	return num*f;
}
#define ll long long 
const int maxn=200005;
int n,cnt,mod[2];
char s1[maxn],s[maxn];
int d[maxn][2],re[2];
int sta[25];
int solve(int x){
	if(!x)return 0;
	int t=0;
	for(int i=0;i<=20;++i)t+=((x&sta[i])>0);
	return 1+solve(x%t);
}
int main(){
	n=read();
	scanf("%s",s1);
	sta[0]=1;for(int i=1;i<=20;++i)sta[i]=sta[i-1]*2;
	for(int i=0;i<n;++i)s[i]=s1[n-i-1];
	for(int i=0;i<n;++i)cnt+=(s[i]=='1');//cout<<cnt<<endl;
	mod[0]=cnt-1;mod[1]=cnt+1;
	d[0][0]=d[0][1]=1;
	for(int i=1;i<n;++i){
		if(mod[0])d[i][0]=d[i-1][0]*2%mod[0];
		d[i][1]=d[i-1][1]*2%mod[1];
	}
	for(int i=0;i<n;++i){
		if(mod[0])re[0]=(re[0]+(s[i]=='1')*d[i][0])%mod[0];
		re[1]=(re[1]+(s[i]=='1')*d[i][1])%mod[1];
	}
	//cout<<re[0]<<' '<<re[1]<<endl;
	for(int i=n-1,t;i>=0;--i){
		if(s[i]=='1'){
			if(mod[0]){
				t=((re[0]-d[i][0])%mod[0]+mod[0])%mod[0];
				printf("%d\n",1+solve(t));
			}
			else puts("0"); 
		}
		if(s[i]=='0'){
			t=(re[1]+d[i][1])%mod[1];
			printf("%d\n",1+solve(t));
		}	
	}
	return 0;
}


Measured memory_bytes: 5660
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        List<int> A = new List<int>();

        for(int i = 0; i < N; i++) {
            A.Add(int.Parse(Console.ReadLine()));
        }

        int maxValue = A.Max();
        int cntMaxValue = A.Count(m => m == maxValue);
        int secondMaxValue = 0;

        if(cntMaxValue == 1) {
            var B = A.Where(m => m != maxValue);
            secondMaxValue = B.Max();
        }

        for(int i = 0; i < N; i++) {
        
            if(cntMaxValue > 1) {
                Console.WriteLine(maxValue);
                continue;
            }
            
            if (A[i] == maxValue) {
                Console.WriteLine(secondMaxValue);
            }
            else {
                Console.WriteLine(maxValue);
            }

        }
    }
}



Measured memory_bytes: 20308
#include <bits/stdc++.h>
using namespace std;
#define forx(i, a, b) for (int i = (a); i < (b); i++)
#define rep(j, n) for (int j = 0; j < (n); j++)

typedef long long ll;

int main()
{
    int sum=0,n;
    cin >> n;
    vector<int> a(n+2);
    forx(i,1,n+1){
        cin >> a[i];
        sum += abs(a[i] - a[i - 1]);
    }
    sum += abs(a[n]);
    forx(i,1,n+1){
        if ((a[i - 1] <= a[i] && a[i] <= a[i + 1]) || (a[i - 1] >= a[i] && a[i] >= a[i + 1]))
        {
            cout << sum << endl;
        }
        else{
            cout << sum - 2*min(abs(a[i] - a[i - 1]) , abs(a[i] - a[i + 1])) << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int W, H, N;
    cin >> W >> H >> N;
    vector<vector<int> > data(N, vector<int>(3));
    for (int i=0; i<N; i++) {
        for (int j=0; j<3; j++) {
            cin >> data.at(i).at(j);
        }
    }
    int area = W * H;
    int x_max = 0;
    int x_min = W;
    int y_max = 0;
    int y_min = H;
    for (int i=0; i<N; i++) {
        if (data.at(i).at(2) == 1) x_max = max(x_max, data.at(i).at(0));
        if (data.at(i).at(2) == 2) x_min = min(x_min, data.at(i).at(0));
        if (data.at(i).at(2) == 3) y_max = max(y_max, data.at(i).at(1));
        if (data.at(i).at(2) == 4) y_min = min(y_min, data.at(i).at(1));
    }
    if (x_min - x_max > 0 && y_min - y_max > 0) {
        int area = (x_min - x_max) * (y_min - y_max);
        cout << area << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
    
}

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

#define lint long long
#define P pair<int, int>

int main() {
    lint N;

    cin >> N;

    lint ans = 0;

    for(int i = 1; i < sqrt(N); ++i){
        if(N % i == 0){
            if(N / i > i){
                lint tmp = N / i - 1;
                if(N % tmp == 0){
                    continue;
                }
                ans += tmp;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;
class Player implements Comparable<Player>{
	int party;
	int num;
	String time;
	Player(int p,int n,String t){
		this.party = p;
		this.num = n;
		this.time = t;
	}
	/*@Override
	public int compareTo(Player p) {
		return this.time.compareTo(p.num);
	}
	*/
	public String getTime() {
        return time;
    }
	@Override
	public int compareTo(Player o) {
		// TODO Auto-generated method stub
	
		return this.time.compareTo(((Player) o).getTime());
	}
	
}

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		Player[] person = new Player[24];
		int[] rank1 = new int[8];
		int[] rank2 = new int[8];
		int[] rank3 = new int[8];
		int[][] rank = new int[3][8];
		int cnt1 = 0;
		int cnt2 = 0;
		int cnt3 = 0;
		for(int i = 0;i < 3;i++){
			for(int j = 0;j < 8;j++){
				person[i*8+j] = new Player(i,sc.nextInt(),sc.next());
			}
		}
		Arrays.sort(person);
		/*
		for(int i = 0;i < 24;i++){
			if(person[i].party == 0){
				rank1[cnt1] = i;
				cnt1++;
			}else if(person[i].party == 1){
				rank2[cnt2] = i;
				cnt2++;
				
			}else{
				rank3[cnt3] = i;
				cnt3++;
			}
		}
		*/
		for(int i = 0;i < 24;i++){
			if(person[i].party == 0){
				rank[0][cnt1] = i;
				cnt1++;
			}else if(person[i].party == 1){
				rank[1][cnt2] = i;
				cnt2++;
				
			}else{
				rank[2][cnt3] = i;
				cnt3++;
			}
		}
		for(int i = 0;i < 3;i++){
			for(int j = 0;j < 2;j++){
				System.out.println(person[rank[i][j]].num+" "+person[rank[i][j]].time);
				person[rank[i][j]].time = "999";
			}
		}
		Arrays.sort(person);
		for(int j = 0;j < 2;j++){
			System.out.println(person[j].num+" "+person[j].time);
		}
		
	}
}

Measured memory_bytes: 25852
#include <string>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <iostream>
#include <functional>
#include <algorithm>
#include <sstream>
#include <iterator>
#include <cmath>

using namespace std;
typedef long long ll;

int main()
{
	string S;
	cin >> S;
	int N = S.size();
	ll ans = 0;
	for (int bit = 0; bit < (1 << (N - 1)); bit++) {
		int prev = 0;
		ll tmp = 0;
		for (int i = 0; i < N - 1; i++) {
			if (bit & (1 << i)) {
				tmp += stoll(S.substr(prev, i - prev + 1));
				prev = i + 1;
			}
		}
		tmp += stoll(S.substr(prev));
		ans += tmp;
	}
	cout << ans << endl;
	return 0;
}


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


int main()
{
    int A,B;
    char a[100];
    scanf("%d%d",&A,&B);
    scanf("%s",a);

    if(strlen(a)==A+B+1&&a[A]=='-')
    {
        int flag=1;
        for(int i=0;a[i]!='\0';i++)
        {
            if(i==A)
                continue;
            if(a[i]<'0'||a[i]>'9')
            {
                flag=0;
                printf("No\n");
                break;
            }
        }
        if(flag) printf("Yes\n");
    }
    else
         printf("No\n");
    return 0;
}


Measured memory_bytes: 256
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, *A = map(int, read().split())
    M = 61
    C = [0] * M
    for a in A:
        for i in range(M):
            if not a:
                break
            a, r = a // 2, a % 2
            if r:
                C[i] += 1

    ans = 0
    p = 1
    for c in C:
        ans = (ans + c * (N - c) * p) % MOD
        p = p * 2 % MOD

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 136480
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char s[10000];
    scanf("%s",s);
    int n=strlen(s);
    int h=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]>='a'&&s[i]<='z')
        {printf("%c",s[i]);h++;}
        if(h==3)
            break;
    }
	return 0;
}


Measured memory_bytes: 3764
#include<stdio.h>
int main(){
int a[100],b[100],i=0;
do{
scanf("%d %d",&a[i],&b[i]);
i++;
}while(a[i-1]!=0||b[i-1]!=0);
for(int x=0;x<i-1;x++){
for(int y=0;y<a[x];y++){
for(int z=0;z<b[x];z++){
printf("#");
}
printf("\n");
}
printf("\n");
}
}

Measured memory_bytes: 1000