akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("O3") 

#include <bits/stdc++.h>
using namespace std;

typedef long long int           ll;
typedef unsigned long long int  ull;
typedef long double             ld;

typedef pair<int, int>          pii;
typedef pair<ll,ll>             pll;
typedef vector<int>             vi;
typedef vector<ll>              vll;
typedef vector<pii>             vpii;
typedef vector<pll>             vpll;

#define test(t)		        int t; cin >> t; while(t--)
#define f(i, a, b)	        for(int (i) = (a); (i) < (b); ++(i))
#define all(a)		        (a).begin(), (a).end()
#define endl 		        "\n"
#define maxvec(vec)             *max_element(all(vec))
#define minvec(vec)             *min_element(all(vec))
#define maxarr(arr)             *max_element(arr, arr + n)
#define minarr(arr)             *min_element(arr, arr + n)
#define deb(x)		        cout << #x << ": " << x << endl;
#define deb2(x,y)	        cout << #x << ": " << x << " ~ " <<  #y << ": " << y << endl;
#define deba(arr)	        cout << #arr << " ~ [ "; for(auto n: arr) cout << n << " "; cout << "]" << endl;
#define debap(arr)	        cout << #arr << " ~ [ "; for(auto n: arr) cout << n.first << "-" << n.second << " "; cout << "]" << endl;
#define fast 		        ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

#define mx9		1000000007
#define mx7		10000007
#define mx6		1000006
#define mx5		200005
#define inf		1<<30                                 
#define eps		1e-9
#define mod		1000000007
#define PI		3.141592653589793238462643383279502884L

void solve()
{
    ll n;
    cin >> n;
    ll a[n], ans = 0, sq = 0, sum = 0;
    f(i, 0, n)
    {
        cin >> a[i];
        sq += (sum * a[i]);
        sq %= mod;
        
        sum += a[i];
        sum %= mod;
    }

    cout << sq << endl;
}

int main()
{
    fast;
    // test(t)
        solve();
    return 0;
}


Measured memory_bytes: 5220
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, check = 0;
  cin >> N;
  for (int i = 1; i <= 9; i++) {
    if (N % i == 0) {
      int M = N;
      M /= i;
      if (1 <= M && M <= 9) {
        check = 1;
        break;
      }
    }
  }
  if (check == 0) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
}

Measured memory_bytes: 256
def modsum(n):
	m = n
	ans = 0
	while m != 0:
		ans = ans + m % 10
		m = m / 10
	
	return ans

inpt = map(int, raw_input().split())
n = inpt[0]
a = inpt[1]
b = inpt[2]
cnt = 0

for i in range(0, n):
	ms = modsum(i+1)
	if a <= ms and ms <= b:
		cnt = cnt + i+1

print cnt

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

#define FOR(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) FOR((i),0,(n))

typedef long long ll;

const int INF=1e9+7;

string  solve(string s,int k,string t){
	if(k<0)return "UNRESTORABLE";
	for(int i=0;i<t.size();i++)if(s[i+k]!=t[i] && s[i+k]!='?')return solve(s,k-1,t);
	rep(i,t.size())s[i+k]=t[i];
	rep(i,s.size())if(s[i]=='?')s[i]='a';
	return s;
}
int main(){
	string s,t;
	cin>>s>>t;
	cout<<solve(s,s.size()-t.size()+1,t)<<endl;
	
}


Measured memory_bytes: 256
import java.util.*;


class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] X = new int[N];
        for(int i=0; i<N; i++){
            X[i] = sc.nextInt();
        }

        int[] d = new int[100];
        for(int i=0; i<100; i++){
            d[i] = i*i;
        }

        int min = Integer.MAX_VALUE;
        for(int i=0; i<100; i++){
            int dsum = 0;
            for(int j=0; j<N; j++){
                dsum += d[Math.abs(i-(X[j]-1))];
            }
            if(dsum < min) min = dsum;
        }

        System.out.println(min);
    }
}

Measured memory_bytes: 23252
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
#define inf 101010
typedef pair<int,int> pii;
typedef pair<double,pii> pp;

int main(void){
    int n,m,p,a,b;
    while (cin>>n>>m>>p>>a>>b && n) {
        a--, b--;
        vector<int> t(n);
        for (int i = 0; i < n; i++) cin >> t[i];
        vector<vector<pii> > g(m, vector<pii>());
        for (int i = 0; i < p; i++) {
            int x,y,z;
            cin>>x>>y>>z;
            x--, y--;
            g[x].push_back(make_pair(y,z));
            g[y].push_back(make_pair(x,z));
        }
        
        vector<vector<double> > d(m, vector<double>(1<<n, inf));
        priority_queue<pp, vector<pp>, greater<pp> > que;
        que.push(make_pair(0.0, make_pair(a, (1<<n)-1)));
        
        double ans = inf;
        while (!que.empty()) {
            pp p = que.top(); que.pop();
            double cost = p.first;
            int cur = p.second.first, bit = p.second.second;
            if (cur == b) {
                ans = cost;
                break;
            }
            if (cost > d[cur][bit]) continue;
            
            for (int i = 0; i < g[cur].size(); i++) {
                int to = g[cur][i].first, len = g[cur][i].second;
                for (int j = 0; j < n; j++) {
                    if (bit & 1<<j) {
                        double x = len / (double)t[j];
                        int nbit = bit & ~(1<<j);
                        if (cost+x >= d[to][nbit]) continue;
                        d[to][nbit] = cost+x;
                        que.push(make_pair(cost+x, make_pair(to, nbit)));
                    }
                }
            }
        }
        if (ans == inf) cout << "Impossible" << endl;
        else printf("%.8lf\n",ans);
    }
}

Measured memory_bytes: 4540
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <string>
#include <vector>
#include <math.h>
#include <queue>
#include <deque>
#include <map>
const int MOD = 1e9+7;
typedef long long ll;
using namespace std;

ll gcd(ll x, ll y){
	if (x < y){
		ll temp = x;
		x = y;
		y = temp;
	}
	if (x % y) return gcd(y, x%y);
	return y;
}


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

	left[0] = a[0];
	for (int i = 1; i < n; i++){
		left[i] = gcd(a[i], left[i-1]);
	}
	right[n-1] = a[n-1];
	for (int i = n-2; i >= 0; i--){
		right[i] = gcd(a[i], right[i+1]);
	}
	
	int ans = max(left[n-2], right[1]);
	for (int i = 1; i < n-1; i++){
		ans = max(ans, (int)gcd(left[i-1], right[i+1]));
	}
	cout << ans << endl;
 	return 0;
}


Measured memory_bytes: 1408
import re

input_line = input()
s = input()

content = s

pattern = '^' + input_line + '\w$'

# compile後match
try:
    repatter = re.compile(pattern)
    result = repatter.match(content)
    result.group()
    print ('Yes')
except:
    print ('No')

# print(result.group())
# print(result)

Measured memory_bytes: 70628
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main()
{
    char day[5];

    scanf("%s", day);

    if (strcmp(day, "SUN") == 0)
    {
        printf("7\n");
    }
    else if (strcmp(day, "MON") == 0)
    {
        printf("6\n");
    }
    else if (strcmp(day, "TUE") == 0)
    {
        printf("5\n");
    }
    else if (strcmp(day, "WED") == 0)
    {
        printf("4\n");
    }
    else if (strcmp(day, "THU") == 0)
    {
        printf("3\n");
    }
    else if (strcmp(day, "FRI") == 0)
    {
        printf("2\n");
    }
    else if (strcmp(day, "SAT") == 0)
    {
        printf("1\n");
    }
    return 0;
}

Measured memory_bytes: 128
// In the name of God

#include <bits/stdc++.h>

using namespace std;

const int N = 85;

int grid[N][N];
bool vis[N][N][N*N*2];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;	
	cin >> n >> m;
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			cin >> grid[i][j];
		}
	}
	for(int i=0;i<n;i++) {
		for(int j=0;j<m;j++) {
			int x;
			cin >> x;
			grid[i][j] = abs(grid[i][j] - x);
		}
	}
	queue< pair< int, pair<int,int> > >  q;
	vis[0][0][grid[0][0]] = 1;
	q.push( make_pair( grid[0][0], make_pair(0, 0) ) );

	while(!q.empty()) {
		auto now = q.front();
		pair<int,int> pos = now.second;
		int val = now.first;
		q.pop();
		if(pos.first != n-1) {
			int v = grid[pos.first+1][pos.second];
			int go1 = val + v;
			int go2 = abs(val - v);
			if(vis[pos.first+1][pos.second][go1] != 1) {
				vis[pos.first+1][pos.second][go1] = 1;
				q.push( make_pair( go1, make_pair(pos.first+1, pos.second) ) );
			}
			if(vis[pos.first+1][pos.second][go2] != 1) {
				vis[pos.first+1][pos.second][go2] = 1;
				q.push( make_pair( go2, make_pair(pos.first+1, pos.second) ) );
			}
		}

		if(pos.second != m-1) {
			int v = grid[pos.first][pos.second+1];
			int go1 = val + v;
			int go2 = abs(val - v);
			if(vis[pos.first][pos.second+1][go1] != 1) {
				vis[pos.first][pos.second+1][go1] = 1;
				q.push( make_pair( go1, make_pair(pos.first, pos.second+1) ) );
			}
			if(vis[pos.first][pos.second+1][go2] != 1) {
				vis[pos.first][pos.second+1][go2] = 1;
				q.push( make_pair( go2, make_pair(pos.first, pos.second+1) ) );
			}
		}
	}
	for(int i=0;i<N*N*2;i++) {
		if(vis[n-1][m-1][i]) {
			cout << i;
			exit(0);
		}
	}
	return 0;
}


Measured memory_bytes: 98944
#include<stdio.h>
#include<algorithm>
using namespace std;
long long ans[1100000];
int prime[1100];
int p[1100];
int main(){
	int t;scanf("%d",&t);
	p[0]=p[1]=-1;
	for(int i=2;i<1100;i++){
		if(~p[i]){
			p[i]=1;for(int j=i+i;j<1100;j+=i)p[j]=-1;
		}
	}
	int sz=0;
	for(int i=0;i<1100;i++)if(~p[i])prime[sz++]=i;
	for(int i=1;i<1010000;i++){
		int now=i;
		int val=i;
		for(int j=0;j<sz;j++){
			if(now%prime[j]==0){
				val-=val/prime[j];
				while(now%prime[j]==0)now/=prime[j];
			}
		}
		if(now>1)val-=val/now;
		ans[i]=ans[i-1]+val;
	}
	while(t--){
		int a;scanf("%d",&a);
		printf("%lld\n",ans[a]+1);
	}
}

Measured memory_bytes: 9192
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cassert>
#include <cmath>
#include <complex>
#include <bitset>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define rep(i, a, b) for(int (i) = (a), __omega = (b); (i) <= __omega; ++(i))
#define down(i, a, b) for(int (i) = (a), __omega = (b); (i) >= (b); --(i))
#define openfile(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout)
using namespace std;

int n, m; 

int f[300010], v;

struct edge { int to; edge *next; } e[300010], *et = e, *last[300010];

void add(int u, int v) { *++et = (edge) {v, last[u]}, last[u] = et; }

struct node {
	int cnt;
	node *ls, *rs;
} t[8000010], *ct = t, *root[300010];

#define Ls rt->ls, l, mid
#define Rs rt->rs, mid+1, r

void build(node *&rt, int l, int r) {
	rt = ++ct;
	if(l == r) return;
	int mid = (l+r)>>1;
	build(Ls);
	build(Rs);
}

void modify(node *&rt, int l, int r, int pos) {
	if(r < pos || pos < l) return;
	*++ct = *rt; rt = ct;
	if(l == r) {
		rt->cnt++;
		return;
	}
	int mid = (l+r)>>1;
	modify(Ls, pos);
	modify(Rs, pos);
	rt->cnt = (rt->ls->cnt)+(rt->rs->cnt); 
}

int query(node *rt, int l, int r, int L, int R) {
	if(r < L || R < l) return 0;
	if(L <= l && r <= R) return rt->cnt;
	int mid = (l+r)>>1;
	return query(Ls, L, R)+query(Rs, L, R);
}

int main() {
	//freopen("train.in", "r", stdin);
	//freopen("train.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		if(l) add(l, r); else v++;
	}
	build(root[0], 1, m);
	for(int i = 1; i <= m; i++) {
		root[i] = root[i-1];
		for(edge *it = last[i]; it; it = it->next)
			modify(root[i], 1, m, it->to);
	}
	f[1] = n-v;
	for(int i = 2; i <= m; i++)
		for(int j = i; j <= m; j += i)
			f[i] += query(root[j], 1, m, j, m)-query(root[j-i], 1, m, j, m);//l : [j-i+1, j], r : [j, m]
	for(int i = 1; i <= m; i++)
		printf("%d\n", f[i]+v);
	return 0;
}


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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素


int main(){
    string s,t;
    cin>>s>>t;
    int len=s.size();
    REP(i,len){
        if(s[i]!=t[i]){
            cout<<"No"<<endl;
            return 0;
        }
    }
    if(t.size()==len+1 && t[len]<='z' && t[len]>='a') cout<<"Yes";
    else cout<<"No";
    cout<<endl;
    return 0;
}




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

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
using namespace std;
using ll = long long;

int main() {
    FAST;

    unordered_map<ll, ll> mp;

    ll n, q, i, a, b, c, sum = 0;
    cin >> n;

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

    cin >> q;
    for (i = 0; i < q; ++i) {
        cin >> b >> c;

        sum -= b * mp[b];
        sum += c * mp[b];

        mp[c] += mp[b];
        mp[b] = 0;

        cout << sum << "\n";
    }

    return 0;
}


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

struct Dice {
  int faces[6+1];
  Dice() : faces{0, 1, 2, 3, 4, 5, 6} {}
  void order(char cmd) {
    switch (cmd) {
      case 'E':
        swap(faces[1], faces[4]);
        swap(faces[4], faces[6]);
        swap(faces[6], faces[3]);
        break;
      case 'N':
        swap(faces[1], faces[2]);
        swap(faces[2], faces[6]);
        swap(faces[6], faces[5]);
        break;
      case 'S':
        swap(faces[1], faces[5]);
        swap(faces[5], faces[6]);
        swap(faces[6], faces[2]);
        break;
      case 'W':
        swap(faces[1], faces[3]);
        swap(faces[3], faces[6]);
        swap(faces[6], faces[4]);
        break;
    }
  }
};


int main() {
  int labels[6+1];
  for (int i{1}; i <= 6; ++i)
    cin >> labels[i];
  string cmds;
  cin >> cmds;
  Dice d;
  for (int i{}; i < cmds.size(); ++i)
    d.order(cmds[i]);
  cout << labels[d.faces[1]] << endl;
}



Measured memory_bytes: 3176
using System;
using System.Linq;
using System.Collections.Generic;
public class Test
{
    public static void Main()
    {
        var input = Console.ReadLine().Split(' ').Select(v => int.Parse(v)).ToArray();
        Console.WriteLine(Math.Min(input[1]/input[0],input[2]));
        Console.ReadKey();
    }
}

Measured memory_bytes: 13396
import java.util.Scanner;

public class Main{
	public static void main(String args[]){
      Scanner scan = new Scanner(System.in);
      long N = scan.nextInt();
      long D = scan.nextInt();

      int ans = 0;
      for(int i = 0;i < N;i++){
        long x = scan.nextInt();
        long y = scan.nextInt();
        if((x * x + y * y) <= D * D){
            ans++;
        }
      }
        System.out.println(ans);
    }
}

Measured memory_bytes: 59328
def addPlus(s,n):
    total = 0
    ps = [s]
    org = s
    for i in range(1,len(org)):
        ps.append(org[:i] + '+' + org[i:])

    for i in range(1,n):
        curr = ps[:]
        for itm in curr:
            for j in range(1,len(itm)):
                pros = itm[:j] + '+' + itm[j:]
                if pros not in ps:
                    if '++' not in pros:
                        ps.append(pros)
    # print(ps)
    for itm in ps:
        total += eval(itm)

    print(total)

if __name__ == '__main__':
    s = input()
    addPlus(s,len(s) - 1)

Measured memory_bytes: 3064
// In the name of God
#include <bits/stdc++.h>

using namespace std;
#define Size(x) ((int)(x).size())
#define pb push_back
#define LD_OUT setprecision(12) << fixed
typedef long long ll;
typedef long double ld;
typedef pair<int,int>pii;
const int INF = 1e9 + 10;
const int MN = 1e5 + 10;

int deg[MN];
int n , m;

int main()
{
	ios_base :: sync_with_stdio(false) ,cin.tie(0) , cout.tie(0);
	cin >> n >> m;
	for(int i=0;i<m;++i){
		int a,b;cin>>a>>b;--a,--b;
		deg[a]++ , deg[b]++;
	}
	for(int i=0;i<n;++i) if(deg[i]%2) return cout << "NO\n" , 0;
	cout << "YES\n";
	return 0;
}


Measured memory_bytes: 640
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
 
class Program{
    static void Main(){
        int n = int.Parse(Console.ReadLine());
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            int num = int.Parse(Console.ReadLine());
            if(IsPrime(num)) cnt++;
        }
        Console.WriteLine(cnt);
    }

    static bool IsPrime(int x){
        if(x == 2) return true;
        if(x % 2 == 0) return false;
        for (int i = 3; i <= Math.Sqrt(x); i += 2)
        {
            if(x % i == 0) return false;
        }
        return true;
    }
}

Measured memory_bytes: 9136
process.stdin.setEncoding("utf-8");

const VALUE = 0;
const WEIGHT = 1;

function knapsack(items, weight) {
  const memo = [];
  const list = [null, ...items];
  for (let i = 0; i < list.length; i++) {
    for (let w = 0; w <= weight; w++) {
      // 容量0のときはすべて0
      if (w === 0) {
        memo[i] = [0];
      } else if (i === 0) {
        memo[i][w] = 0;
      } else if (list[i][WEIGHT] > w) {
        memo[i][w] = memo[i - 1][w];
      } else {
        memo[i][w] = Math.max(
          memo[i - 1][w - list[i][WEIGHT]] + list[i][VALUE],
          memo[i - 1][w]
        );
      }
    }
  }
  return memo[items.length][weight];
}

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

const lines = [];

rl.on("line", line => lines.push(line));
rl.on("close", () => {
  // eslint-disable-next-line no-unused-vars
  const [[n, w], ...items] = lines.map(l =>
    l.split(" ").map(x => parseInt(x, 10))
  );
  // eslint-disable-next-line no-console
  console.log(knapsack(items, w));
});



Measured memory_bytes: 37684
N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X = sorted(X, key = lambda x: x[1])

# a[i]はA[i]まで終わらせるためにかかる累積時間
a = [0] * N
a[0] = X[0][0]
for i in range(1, N):
	a[i] = a[i - 1] + X[i][0]

for j in range(N):
	if a[j] > X[j][1]:
		print("No")
		exit()
print("Yes")


Measured memory_bytes: 58260
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string a, b;
  cin>> a >> b;
  a += b;
  int n = stoi(a);
  string txt = "No";
  
  for(int i = 0; i * i <= n; i++) {
    if(i * i == n) txt = "Yes";
  }
  
  cout<< txt <<endl;
  
  return 0;
}


Measured memory_bytes: 256
N,K,*V = `dd`.split.map &:to_i
ans = 0
(0...N).each{ |i|
  (i..N).reverse_each{ |j|
    k = K - (i + N-j)
    break if k < 0
    gems = (V[0...i] + V[j..-1]).sort
    s = gems.inject(0,:+)
    w = gems[0...[gems.size,k].min].reduce(0){ |a,v| a + (v > 0 ? 0 : v) }
    x = s - w
    ans = [ans, x].max
  }
}
p ans


Measured memory_bytes: 2056
N = int(input())
if N == 2:
  ans = 2 * int(input())
else:
  B = list(map(int, input().split()))
  ans = B[0] + B[N-2]
  for i in range(1, N-1):
    ans += min(B[i], B[i-1])
print(ans)

Measured memory_bytes: 61920
import java.util.*;
import java.math.*;

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

    BigInteger n, m, tmp1, tmp2;
    tmp1 = new BigInteger(String.valueOf(10000));
    tmp2 = new BigInteger(String.valueOf(0));
    Scanner sc = new Scanner(System.in);
    int a, b;

    String t[] = {"", "Man", "Oku", "Cho", "Kei", "Gai", "Jo", "Jou", "Ko", "Kan",
      "Sei", "Sai", "Gok", "Ggs", "Asg", "Nyt", "Fks", "Mts"};

    while(true){
      a = Integer.parseInt(sc.next());
      b = Integer.parseInt(sc.next());
      if(a == 0) break;

      n = new BigInteger(String.valueOf(a));
      n = n.pow(b);

      String ans = "";
      int p = 0;

      while(!n.equals(tmp2)){
        m = n.remainder(tmp1);
        long temp = m.longValue();
        if(temp != 0){
          ans = String.valueOf(temp) + t[p] + ans;
        }
        n = n.divide(tmp1);
        p++;
      }

      System.out.println(ans);
    }
  }
}



Measured memory_bytes: 26812
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Problem[] problems = new Problem[n];
        for (int j = 0; j < n; j++) {
            int l = in.nextInt();
            int r = in.nextInt();
            problems[j] = new Problem(l, r);
        }
        Arrays.sort(problems);
        List<Problem> remProblems = new ArrayList<>(n);
        boolean[] isRemProblem = new boolean[n];
        int maxL = 0;
        for (int j = 0; j < n; j++) {
            Problem problem = problems[j];
            if (problem.l > maxL) {
                isRemProblem[j] = true;
                maxL = problem.l;
                remProblems.add(problem);
            }
        }
        int answer = 0;
        for (int j = 0; j < n; j++) {
            if (!isRemProblem[j]) {
                Problem problem = problems[j];
                answer = Math.max(answer, problem.r - problem.l + 1);
            }
        }
        answer += Math.max(0, remProblems.get(0).r - remProblems.get(remProblems.size() - 1).l + 1);
        for (int j = 0; j < remProblems.size() - 1; j++) {
            answer = Math.max(
                    answer,
                              Math.max(0, remProblems.get(0).r - remProblems.get(j).l + 1)
                            + Math.max(0, remProblems.get(j + 1).r - remProblems.get(remProblems.size() - 1).l + 1));
        }
        for (int j = 1; j < remProblems.size() - 1; j++) {
            Problem problem = remProblems.get(j);
            answer = Math.max(answer, problem.r - problem.l + 1 + Math.max(0, remProblems.get(0).r - remProblems.get(remProblems.size() - 1).l + 1));
        }
        System.out.println(answer);
    }

    static class Problem implements Comparable<Problem> {
        final int l;
        final int r;

        Problem(int l, int r) {
            this.l = l;
            this.r = r;
        }

        @Override
        public int compareTo(Problem o) {
            if (r != o.r) {
                return r - o.r;
            } else {
                return o.l - l;
            }
        }
    }
}


Measured memory_bytes: 91928
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int N;
V<ll> A;
VV<int> G;
V<int> sz;
ll dp[5010][2][5010];
ll inner[2][5010];
ll ninner[2][5010];
ll inf = 1e18;
void dfs(int v,int p){
	sz[v] = 1;
	for(int u:G[v]) if(u!=p) dfs(u,v),sz[v] += sz[u];
	int S = 1;
	inner[0][0] = inner[1][0] = A[v];
	if(A[v]<0) inner[1][0] = inf;
	for(int u:G[v]) if(u!=p){
		rep(i,2) rep(j,S+sz[u]) ninner[i][j] = inf;
		rep(allp,2) rep(c,S) if(inner[allp][c] != inf){
			rep(uallp,2) rep(uc,sz[u]+1) if(dp[u][uallp][uc] != inf){
				chmin(ninner[allp&uallp][c+uc],inner[allp][c] + dp[u][uallp][uc]);
				if(uallp==1 || dp[u][uallp][uc]<0){
					chmin(ninner[allp][c+uc+1],inner[allp][c]);
				}
			}
		}
		rep(i,2) rep(j,S+sz[u]) inner[i][j] = ninner[i][j];
		S += sz[u];
	}
	rep(i,2) rep(j,S) dp[v][i][j] = inner[i][j];
}
int main(){
	cin>>N;
	A.resize(N);
	G.resize(N);
	sz.resize(N);
	rep(i,N) cin>>A[i];
	rep(i,N-1){
		int x,y;
		cin>>x>>y;
		x--,y--;
		G[x].pb(y);
		G[y].pb(x);
	}
	dfs(0,-1);
	int ans = N;
	rep(allp,2) rep(c,N) if(dp[0][allp][c] != inf){
		if(allp==1 || dp[0][allp][c]<0) chmin(ans,c);
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 391808
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#include<queue>
#include<tuple>
#include<stdio.h>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int long long n, a, b;
	cin>>n>>a>>b;
	int long long c=n/(a+b);
	cout<<c*a+min((n-c*(a+b)), a)<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<sstream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
using uint = unsigned int;
using ll = long long;
enum : int { M = (int)1e9 + 7 };
enum : ll { MLL = (ll)1e18L + 9 };
using namespace std;
#ifdef LOCAL
#include"rprint2.hpp"
#else
#define FUNC(name) template <ostream& out = cout, class... T> void name(T&&...){ }
FUNC(prints) FUNC(printe) FUNC(printw) FUNC(printew) FUNC(printb) FUNC(printd) FUNC(printde);
#endif

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    int num = 1;
    for(int i = 0; i < n; i++){
        num = num + k < num * 2 ? num + k : num * 2;
    }
    cout << num << '\n';
}


Measured memory_bytes: 888
class UnionFindTree:
    _node_num = 0
    _parent_list = []
    _tree_len = []
    _num_trees = 0

    def __init__(self, node_num):
        self._node_num = node_num
        self._parent_list = [-1 for i in range(node_num+1)]
        self._tree_len = [0 for i in range(node_num+1)]
        self._num_trees = node_num

    def _root(self, node):
        root = node
        while self._parent_list[root] != -1:
            root = self._parent_list[root]
        return root

    def union(self, x, y):
        xr = self._root(x)
        yr = self._root(y)
        if xr == yr:
            return
        if self._tree_len[xr] < self._tree_len[yr]:
            self._parent_list[xr] = yr
            self._tree_len[yr] += 1
        else:
            self._parent_list[yr] = xr
            self._tree_len[xr] += 1
        self._num_trees -= 1

    def get_num_trees(self):
        return self._num_trees

def main():
    N, M = map(int, input().split())

    uft = UnionFindTree(N)
    for i in range(M):
        x, y, z = map(int, input().split())
        uft.union(x, y)
    print(uft.get_num_trees())

if __name__ == '__main__':
    main()


Measured memory_bytes: 53664
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long N, A, B, minsum, maxsum;

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

	if (A > B || (A < B && N==1)) {
		puts("0");
		return 0;
	}

	if (A == B || (A < B && N == 2)) {
		puts("1");
		return 0;
	}


	minsum = A*(N - 1) + B;
	maxsum = B*(N - 1) + A;
	cout << maxsum - minsum+1;
	
	


}

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

using namespace std;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define reppe(i,a,b) for(int i = (int)(a) ; i <= (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
#define repme(i,a,b) for(int i = (int)(a) ; i >= (int)(b) ; --i)

typedef long long ll;

long long GCD(long long a, long long b){if(b==0)return a;return GCD(b,a%b);}

int main() {
    string S; cin >> S;
    int Q; cin >> Q;
    int count1 = 0;
    string a = "";
    string z = "";
    repp(i,0,Q) {
        int d; cin >> d;
        if (d == 1) {
            count1 += 1;
            continue;
        }
        int f; cin >> f;
        string c; cin >> c;
        if ((count1 % 2 == 0 && f == 1) || (count1 % 2 == 1 && f == 2)) a = c + a;
        else z += c;                           
    }
    S = a + S + z;
    if (count1 % 2 == 0) cout << S << endl;
    else {
        reverse(S.begin(), S.end());
        cout << S << endl;
    } 

}


Measured memory_bytes: 1360
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp3
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.ReadLine();
            var s = Console.ReadLine().Trim().Split(' ').Select(int.Parse).OrderBy(_ => _).ToArray();
            var i = s[s.Length / 2] - s[s.Length / 2 - 1];
            Console.WriteLine(i);
        }
    }
}


Measured memory_bytes: 24032
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <cstdint>

using namespace std;

unsigned long long int magicfunc(unsigned long long int *a,unsigned long long int n){
    
    unsigned long long int sum=a[0],xsum=a[0],ans=0;
    
    unsigned long long int l=0,r=0;
    
    while(l<n){
        while((sum+a[r+1])==(xsum^a[r+1])&&r+1<n){
            r++;
            sum+=a[r];
            xsum^=a[r];
        }
        ans+=r+1-l;
        cerr<<l<<" "<<r<<endl;
        sum-=a[l];
        xsum^=a[l];
        l++;
    }
    
    return ans;
    
}

int main(int argc , char **argv){
    
    unsigned int n; cin>>n;
    
    unsigned long long int a[n];
    for(unsigned int i=0;i<n;i++)cin>>a[i];
    cout<<magicfunc(a,n)<<endl;
    
    
    return 0;
    
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long int
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define pci pair<char,int
#define mii map<int,int>
#define mll map<long long int,long long int>
#define mci map<char,int>
#define umii unordered_map<int,int>
#define umll unordered_map<long long int,long long int>
#define umci unordered_map<char,int>
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define mod 1000000007
using namespace std;
#define maxval 10003000

int main(){
   IOS;
ll t;t=1;//cin>>t;
while(t--){
ll n;cin>>n;string s;cin>>s;
if(n>=s.size())cout<<s;
else{
    for(ll i=0;i<n;i++) cout<<s[i];
   cout<<"...";
}

} 
    
    

    
return 0;    
}

Measured memory_bytes: 3596
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int n;
	int max_dif=0;
	int dif;
	cin >> n;
	vector<int> a(100);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0;i<n; i++) {
		for (int j = 0; j < n ; j++) {
			if (a[i] > a[j])dif = a[i] - a[j];
			else dif = a[j] - a[i];
			if (dif > max_dif) max_dif = dif;
		}
	}
	cout << max_dif;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
int main(){
    string s;
    cin >> s;
    int ans=0;

    for(int i=1;i < s.size();i++)
    {
        if(s.at(i)==s.at(i-1)){
            if(s.at(i)=='0'){
                s.at(i)='1';
            }else{
                s.at(i) = '0';
            }
            ans++;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 512
use std::io;
use std::io::BufRead;

fn main() {
    let mut sc = Scanner::new(std::io::stdin());
    let n: usize = sc.next().unwrap();

    let mut g: Vec<Vec<usize>> = vec![vec![]; n];
    for _ in 0..n - 1 {
        let a: usize = sc.next().unwrap();
        let b: usize = sc.next().unwrap();
        let a = a - 1;
        let b = b - 1;
        g[a].push(b);
        g[b].push(a);
    }

    let mut d1 = vec![0; n];
    let mut d2 = vec![0; n];

    f(&g, &mut d1, 0, n, 0);
    f(&g, &mut d2, n - 1, n, 0);

    let mut a = 0;
    for i in 0..n {
        if d1[i] <= d2[i] {
            a += 1;
        }
    }
    println!("{}", if a > n - a { "Fennec" } else { "Snuke" });
}

fn f(g: &Vec<Vec<usize>>, ds: &mut Vec<usize>, i: usize, p: usize, d: usize) {
    ds[i] = d;
    for j in g[i].iter() {
        if *j != p {
            f(g, ds, *j, i, d + 1);
        }
    }
}

/// Scanner
///
/// # Example
/// ```
/// use contest::io::scanner;
/// let mut sc = scanner::Scanner::new("1 2 \n\n \r\t \n 3.5".as_bytes());
/// assert_eq!("1".to_string(), sc.next::<String>().unwrap());
/// assert_eq!(2, sc.next().unwrap());
/// assert_eq!(3.5, sc.next().unwrap());
/// assert_eq!(None, sc.next::<i32>());
/// ```

pub struct Scanner<R: io::Read> {
    br: io::BufReader<R>,
    // Read tokens are stored in reversed order per line.
    buf: Vec<String>,
}

impl<R: io::Read> Scanner<R> {
    pub fn new(r: R) -> Scanner<R> {
        Scanner {
            br: io::BufReader::new(r),
            buf: vec![],
        }
    }
    #[inline]
    pub fn next<T>(&mut self) -> Option<T>
        where T: std::str::FromStr,
              T::Err: std::fmt::Debug
    {
        self.next_string().map(|s| s.parse::<T>().expect("Parse failed: "))
    }
    fn next_string(&mut self) -> Option<String> {
        self.buf.pop().or_else(|| match self.update() {
            true => self.next_string(),
            false => None,
        })
    }
    #[inline]
    fn update(&mut self) -> bool {
        let mut s = String::new();
        let res = self.br.read_line(&mut s);
        match res.expect("I/O error.") {
            0 => false,
            _ => {
                self.buf = s.split_whitespace().map(|x| x.to_string()).rev().collect();
                true
            }
        }
    }
}


Measured memory_bytes: 18684
#include<bits/stdc++.h>
#define ll long long
#define pii_ pair<int,int>
#define mp_ make_pair
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 1e5+5;
const ll M = 1e9+7;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
ll qpow(ll a,ll b) {ll s=1;while(b){if(b&1)s=(s*a)%M;a=(a*a)%M;b>>=1;}return s; }
char s[maxn];
ll fac[maxn],inv[maxn];
void init()
{
    int n = 1e5+2;
    fac[0] = 1;
    rep(i,1,n) fac[i] = fac[i-1]*i%M;
    inv[n] = qpow(fac[n],M-2);
    per(i,n-1,0) inv[i] = inv[i+1]*(i+1)%M;
}
ll C(int a,int b) {return fac[a]*inv[b]%M*inv[a-b]%M;}
int main()
{
    fastio();
    init();
    cin>>s+1;
    int n = strlen(s+1);
    ll ans = 0;
    int cnt = 0;
    rep(i,1,n){
        if(s[i]=='1') ans = (ans + qpow(2,cnt)*qpow(3,n-i)%M)%M,cnt++;
    }
    ans = (ans + qpow(2,cnt))%M;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 5272
#include <iostream>
using namespace std;
int main() {
    int a[] = {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};
    int n; cin >> n; cout << a[n-1] << endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    String s = sc.next();
    int leng = s.length();
    StringBuffer str = new StringBuffer(s);
    String ss = str.reverse().toString();
    if(leng == 2){
      System.out.println(s);
    }else{
      System.out.println(ss);
    }
    
  }
}

Measured memory_bytes: 35420
#include<bits/stdc++.h>
using namespace std;
int main(){
  vector<int> a(3);
  for(int i=0;i<3;i++){
    cin>>a[i];
  }
  sort(a.begin(),a.end());
  cout<<(a[0]+a[1]==a[2] ? "Yes":"No")<<endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define re(n) for (int i = 0; i < (n); ++i)
#define rej(n) for (int j = 0; j < (n); ++j)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector <int> vi;
typedef pair <int, int> pii;
typedef vector <pair <int, int>> vii;

const ld PI = acos((ld)-1);

int main() {
    #ifndef LOCALDEBUG
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #endif  // LOCALDEBUG
    int n, m;
    cin >> n >> m;
    multiset <int, greater <int>> s;
    re(n) {
        int x;
        cin >> x;
        s.insert(x);
    }
    re(m) {
        int x = *s.begin();
        s.erase(s.begin());
        x /= 2;
        s.insert(x);
    }
    ll ans = 0;
    while(sz(s)) {
        ans += *s.begin();
        s.erase(s.begin());
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
using ll = unsigned long long;

int m1, d1, m2, d2;

void input() {
    cin >> m1 >> d1 >> m2 >> d2;
}

void solve() {
    if(m1 + 1 == m2) {
        cout << 1 << endl;
    }
    else {
        cout << 0 << endl;
    }
}
int main() {
    input();
    solve();
}


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

#define INF 1001001001
#define LINF 1001001001001001001
#define MOD 1000000007
#define MOD2 998244353

template<class T,class U>bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U>bool chmin(T &a, const U &b){if(b<a){a=b;return 1;}return 0;}

#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
#define rep1(i,a,b) for(int a_=(a),b_=(b),i=a_;i<b_;++i)
#define repr(i,n) for(int _i=(n),i=_i;i>0;--i)

#define db(x) cerr<<#x<<" = "<<x<<" ";
#define db2(x,y) cerr<<"("<<#x<<", "<<#y<<") = ("<<x<<", "<<y<<") ";
#define db3(x,y,z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = ("<<x<<", "<<y<<", "<<z<<") ";
#define ln cout<<endl;

#define all(a)  (a).begin(),(a).end()
#define dig(n)  to_string(n).length()

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define se second
#define fi first

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,pii> ppii;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return (a*b)/gcd(a,b);}

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

int main(){
    bool flag=false;
    ll ans=0,sum=0;

    int n;
    cin >>n;
    vector<int>a(n);

    rep(i,n){
        cin>>a[i];
        a[i] -= i+1;
        sum += a[i];
    }

    sort(all(a));

    rep(i,n){
        ans += abs(a[i] - a[n/2]);
    }

    //cout <<fixed<<setprecision(16)<< << endl;
    cout<<ans<<endl;
    //if(flag)cout << "Yes" <<endl;
    //else cout << "No" <<endl;
    
    return 0;
}


Measured memory_bytes: 1024
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.StringTokenizer;

public class Main {
	private static final int MOD = (int)Math.pow(10, 9);
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		int a = sc.nextInt();
		String s = sc.next();
		StringBuilder sb = new StringBuilder();
		
		for (char c: s.toCharArray()) {
			char newChar = (char)(('A'+(c - 'A' + a)%26));
			sb.append("" + newChar);
		}
		
		System.out.println(sb.toString());
	}
	
	static class FastReader {
	    BufferedReader br;
	    StringTokenizer st;
	
	    public FastReader() {
	      br = new BufferedReader(new InputStreamReader(System.in));
	    }
	  
	    String next() { 
	      while (st == null || !st.hasMoreElements()) {
	        try {
	          st = new StringTokenizer(br.readLine());
	        } catch (IOException  e) {
	          e.printStackTrace();
	        }
	      }
	      return st.nextToken();
	    }
	
	    int nextInt() {
	      return Integer.parseInt(next());
	    }
	
	    long nextLong() {
	      return Long.parseLong(next());
	    }
	
	    double nextDouble() { 
	      return Double.parseDouble(next());
	    }
	
	    String nextLine() {
	      String str = "";
	        try{
	            str = br.readLine();
	        } catch (IOException e) {
	            e.printStackTrace();
	        }
	        return str;
	      }
	  }
}


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

int main() {
    int a, b;
    cin >> a >> b;
    for (int i = min(a, b); i <= max(a, b); i++) {
        if (b - i == i - a) {
            cout << i << endl;
            return 0;
        }
    }
    cout << "IMPOSSIBLE" << endl;
}

Measured memory_bytes: 256
import math
from collections import deque
from collections import defaultdict
import itertools as it

#自作関数群
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	if len(res)==0:
		res = [n]
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def fact(n):#階乗
	ans = 1
	m=n
	for _i in range(n-1):
		ans*=m
		m-=1
	return ans
def comb(n,r):#コンビネーション
	if n<r:
		return 0
	l = min(r,n-r)
	m=n
	u=1
	for _i in range(l):
		u*=m
		m-=1
	return u//fact(l)
def combmod(n,r,mod):
	return (fact(n)/fact(n-r)*pow(fact(r),mod-2,mod))%mod
def printQueue(q):
	r=copyQueue(q)
	ans=[0]*r.qsize()
	for i in range(r.qsize()-1,-1,-1):
		ans[i] = r.get()
	print(ans)
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.parents = [-1]*n

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

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

		if x==y:
			return

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

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

	def size(self,x):
		return -1*self.parents[self.find(x)]

	def same(self,x,y):
		return self.find(x)==self.find(y)

	def members(self,x): # much time
		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()} # 1~n
def bitArr(n):#ビット全探索
	x = 1
	zero = "0"*n
	ans = []
	ans.append([0]*n)
	for i in range(2**n-1):
		ans.append(list(map(lambda x:int(x),list((zero+bin(x)[2:])[-1*n:]))))
		x+=1
	return ans;
def arrsSum(a1,a2):
	for i in range(len(a1)):
		a1[i]+=a2[i]
	return a1
def maxValue(a,b,v):
	v2 = v
	for i in range(v2,-1,-1):
		for j in range(v2//a+1): #j:aの個数
			k = i-a*j
			if k%b==0:
				return i
	return -1
def copyQueue(q):
	nq = queue.Queue()
	n = q.qsize()
	for i in range(n):
		x = q.get()
		q.put(x)
		nq.put(x)
	return nq
def get_sieve_of_eratosthenes(n):
	data = [2]
	#data = [0,0,0]
	for i in range(3,n+1,2):
		data.append(i)
		data.append(0)
	for i in range(len(data)):
		interval = data[i]
		if interval!=0:
			for j in range(i+interval,n-1,interval):
				data[j] = 0
	ans = [x for x in data if x!=0]
	#ans = data[:]
	return ans

n = readInt()
a = readInts()
a.sort()

#max_a = 10**6
max_a = a[-1]
ans = [0]*(max_a+1)

for i in a:
	if ans[i]!=2:
		ans[i]+=1
for i in set(a):
	if ans[i]:
		for j in range(i*2,len(ans),i):
			ans[j]=0

print(ans.count(1))

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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

/*
2で割った余りが0になる袋と1の袋を数える
2^n0 * n1から偶数個選ぶ通り=2^n1 /2
2^(n0+n1-1)=2^(N-1)

*/

int main()
{
    lint n,p;
    cin >> n>>p;
    vector<lint> a(n);
    int n1 = 0;
    REP(i,n){
        cin >> a[i];
        n1 += ((a[i] % 2)==1);
    }
    lint ans = pow(2, n - 1);

    //lint ans = (1<<(n-1));
    //cout << n1 << "\n";
    if(n1==0){
        if(p==1)
        ans = 0;
        else
            ans *=2;
    }

    cout << ans <<"\n";

    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main()

{
	int n;
	scanf("%d", &n);
	
	if(n % 2 == 0)
	{
		printf("%d", n/2);
	}
	else if(n % 2 != 0)
	{
		printf("%d", n/2 +1);
	}
	 return 0;

}

Measured memory_bytes: 3196
#include <bits/stdc++.h>
using namespace std;
typedef pair<long long,long long> fdl;
typedef vector <fdl> vec;
int n,tot;
int ch[140010][2],val[140010];
long long len[140010];
long long mid;
vec f[140010]; 
void cal(vec &a,fdl b) 
{
    if(a.empty())a.push_back(b);
    else if(a.back().first == b.first)a.back().second = min(a.back().second,b.second);
    else if(b.second < a.back().second)a.push_back(b);
}
vec merge(vec a,vec b) 
{
    vec res;
	res.clear();
    int siz1 = a.size(),siz2 = b.size();
	int fldl1 = 0,fldl2 = 0;
    while(fldl1 != siz1 && fldl2 != siz2) 
	{
        if(a[fldl1].first < b[fldl2].first)cal(res,a[fldl1++]);
        else cal(res,b[fldl2++]);
    }
    while(fldl1 != siz1)cal(res,a[fldl1]),fldl1++;
    while(fldl2 != siz2)cal(res,b[fldl2]),fldl2++;
    return res;
}
vec init(vec a,vec b) 
{
    vec res;
	res.clear();
    int siz1 = a.size(),siz2 = b.size();
	int fldl1 = 0,fldl2 = 0;
    if(!siz2)return res;
    while(fldl1 != siz1) 
	{
        while(fldl2 != siz2 && a[fldl1].second + b[fldl2].first <= mid)fldl2++;
        if(fldl2)fldl2--;
        if(a[fldl1].second + b[fldl2].first <= mid)res.push_back(make_pair(a[fldl1].first,b[fldl2].second));
        fldl1++;
    }
    return res;
}
void dfs(int u) 
{
    if(!val[u]) 
	{
        f[u].clear();
        f[u].push_back(make_pair(len[u],len[u]));
        return;
    }
    dfs(ch[u][0]);
	dfs(ch[u][1]);
	mid += (len[u] << 1) ;
    vec tmp1 = init(f[ch[u][0]],f[ch[u][1]]);
    vec tmp2 = init(f[ch[u][1]],f[ch[u][0]]);
    f[u] = merge(tmp1,tmp2);
    mid -= (len[u] << 1);
}
int main() 
{
    scanf("%d",&n);
    int x,y;
    for(int i = 2;i <= n;i++) 
	{
    	scanf("%d%d",&x,&y);
		ch[x][val[x]] = i;
		val[x]++;
        len[i] = len[x] + y;
    }
    long long l,r = 1ll * 19602800100;
    while(l < r) 
	{
        mid = (l + r) >> 1;
        dfs(1);
        if(!f[1].empty())r = mid;
        else l = mid + 1;
    }
    printf("%lld",r);
    return 0;
}

Measured memory_bytes: 38348
#include <cmath>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll inf = 1000000007;
int main(void) {
    int ac = 0;
    int wa = 0;
    int tle = 0;
    int re = 0;
    int n;
    cin >> n;
    string s;
    for (int i = 0; i < n; i++) {
        cin >> s;
        if (s == "AC") {
            ac++;
        }
        if (s == "WA") {
            wa++;
        }
        if (s == "TLE") {
            tle++;
        }
        if (s == "RE") {
            re++;
        }
    }
    cout << "AC x" << " " << ac << endl;
    cout << "WA x" << " " << wa << endl;
    cout << "TLE x" << " " << tle << endl;
    cout << "RE x" << " " << re << endl;
    return 0;
}




Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF         1e9
#define INFLL       1e18
#define EPS         1e-9
#define REP(i,n)    for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)   for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)   for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)  for(ll i=(n);i>0;--i)
#define REPC(i,obj) for(auto i:obj)
#define ALL(obj)    (obj).begin(),(obj).end()
#define SETP(n)     cout<<fixed<<setprecision(n)
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

signed main()
{
	for (ll n = in(); n != 0; n = in()) {
		ll ans = 0;
		vector<ll>s(n);
		REP(i, n) s[i] = in();
		while (true) {
			vector<ll>prev(s);
			map<ll, ll>mp;
			REP(i, n)++mp[s[i]];
			REP(i, n)s[i] = mp[s[i]];
			if (s == prev)break;
			++ans;
		}
		cout << ans << endl;
		REP(i, n) {
			if (i != 0)cout << ' ';
			cout << s[i];
		}
		cout << endl;
	}
}


Measured memory_bytes: 3008