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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int64_t> A(N + 1);
  for (int i = 0; i < N + 1; i++) {
    cin >> A[i];
  }
  if (N != 0 && A[0] != 0) {
    cout << -1 << '\n';
    return 0;
  }
  if (N == 0) {
    if (A[0] != 1) {
      cout << -1 << '\n';
      return 0;
    } else {
      cout << 1 << '\n';
      return 0;
    }
  }
  vector<pair<int64_t, int64_t>> cands(N + 1);
  cands[N] = make_pair(A.back(), A.back());
  for (int i = N - 1; i > -1; i--) {
    auto prev = cands[i + 1];
    int64_t lo = prev.first + A[i];
    lo = lo / 2 + (lo % 2);
    int64_t hi = prev.second + A[i];
    cands[i] = make_pair(lo, hi);
  }
  vector<pair<int64_t, int64_t>> res(N + 1);
  res[0] = make_pair(INT64_C(1), INT64_C(1));
  for (int i = 1; i < N + 1; i++) {
    auto prev = res[i - 1];
    int64_t lo = prev.first;
    int64_t hi = prev.second * 2;
    if ((lo <= cands[i].first && cands[i].first <= hi) ||
        (lo <= cands[i].second && cands[i].second <= hi)) {
      res[i] = make_pair(max(INT64_C(0), max(cands[i].first, lo) - A[i]),
                         max(INT64_C(0), min(cands[i].second, hi) - A[i]));
    } else {
      cout << -1 << '\n';
      return 0;
    }
  }
  int64_t ans = 0;
  for (auto r : res) {
    ans += r.second;
  }
  for (auto a : A) {
    ans += a;
  }
  cout << ans << '\n';
  return 0;
}


Measured memory_bytes: 7148
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first first
#define second se
using namespace std;
typedef pair<int, int> P;
typedef vector<int> vi;

signed main(){
    string s[3];
    rep(i, 0, 3) cin >> s[i];
    int now = 0;
    int ans = -1;
    while(1){
        if(s[now].size() == 0){
            ans = now;
            break;
        }
        int tmp = s[now][0] - 'a';
        s[now] = s[now].substr(1);
        now = tmp;
    }
    o((char)('A' + ans));
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define int long long
const int mod = 1e9 + 7;
int cnt = 0;
vector<vector<int>>g;
vector<bool>vis;
void dfs(int s, int p){
	cnt++;
	vis[s] = 1;
	for(int nie : g[s]){
		if(nie != p && !vis[nie]){
			dfs(nie, s);
		}
	}
}
void test_case(){
	int n, m; cin>>n>>m;
	g.resize(n+1);
	vis.resize(n+1);
	for(int i=0;i<m;i++){
		int u, v; cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	int ans = 0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			cnt = 0;
			dfs(i, -1);
			ans = max(ans, cnt);
		}
	}
	cout<<ans<<endl;
}
		
 
signed main(){
	IOS;
	int t=1, i=1; 
	//cin>>t;
	while(t--){
		//cout<<"Case #"<<i<<": ";
		test_case();
		i++;
	}
}


Measured memory_bytes: 26676
#include<iostream>
#include<vector>
#include<string>
#include<deque>
#include<algorithm>
using namespace std;

int main(){
    int n;
    cin>>n;
    deque<int>a;
    for(int i=0;i<n;i++){
        int k;
        cin>>k;
        if((n%2==0&&i%2!=0)||(n%2!=0&&i%2==0)){
            a.push_front(k);
        }else{
            a.push_back(k);
        }
    }
    for(int i=0;i<n;i++){
        if(i!=n-1)cout<<a[i]<<" ";
        else cout<<a[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 4440
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cmath>

using namespace std;
int main()
{
	int X,Y,Z,M;
	cin>>X>>Y>>Z;
	M = (X - Z)/(Y + Z);
	cout<<M<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define N 10001
#define D 100
int dp[N][D][2];
//dp[i][j][k] tells us number of ways to get numbers from 0 to first 
// i digits of the given number having sum of digits as j under
// modulo d when the ith digit is tightly bounded (for k=1) or
// not bounded (for k=0)
using namespace std; 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string k;
    int d;
    cin>>k>>d;
    reverse(k.begin(),k.end());
    memset(dp,0,(k.size()+1)*d*sizeof(dp[0][0]));
    dp[0][0][0] = 1;
    dp[0][0][1] = 1;
    for(int i=1;i<=k.size();i++){
        for(int j=0;j<d;j++){
            for(int m=0;m<2;m++){
                int lim = (m==0)?9:(k[i-1]-'0');
                for(int l=0;l<=lim;l++){
                    int prevm = m;
                    if(l<(k[i-1]-'0'))prevm=0;
                    dp[i][j][m] = (dp[i][j][m]+dp[i-1][(j+l)%d][prevm])%mod;
                }
            }
        }
    }
    int ans = (dp[k.size()][0][1]-1+mod)%mod;
    cout<<ans<<"\n";
    return 0;
}

Measured memory_bytes: 8064
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	for (int i = 0; i < b + 1; i++) {
		if ((a * i) % b == c) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  

#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")  
using namespace std;

#define mp make_pair  
#define Fi first  
#define Se second  
#define pb(x) push_back(x)  
#define szz(x) ((int)(x).size())  
#define rep(i, n) for(int i=0;i<n;i++)  
#define all(x) (x).begin(), (x).end()  
#define ldb ldouble  

typedef tuple<int, int, int> t3;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;

int IT_MAX = 1 << 18;
const ll MOD = 1000000007;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
const db PI = acos(-1);
const db ERR = 1e-10;


ll in[500050];
ll ans[500050];
ll val1[500050];
ll val2[500050];
int main() {
	ll N, Q, D, i;
	scanf("%lld %lld", &N, &D);
	for (i = 1; i <= N; i++) scanf("%lld", &in[i]);

	val1[0] = D;
	for (i = 1; i <= N; i++) {
		val1[i] = min(val1[i - 1], abs(val1[i - 1] - in[i]));
	}
	val2[N + 1] = 0;
	for (i = N; i >= 1; i--) {
		if (val2[i + 1] >= in[i] / 2) val2[i] = val2[i + 1] + in[i];
		else val2[i] = val2[i + 1];
	}
	for (i = 1; i <= N; i++) if (val1[i - 1] <= val2[i + 1]) ans[i] = 1;

	scanf("%lld", &Q);
	while (Q--) {
		scanf("%lld", &i);
		if (ans[i]) printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}

Measured memory_bytes: 17536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF=1e18,MOD=1e9+7;
int main(){
	ll n,a,ans=0;
	cin>>n;
	map<ll,ll>arr,cmp;
	for(int i=0;i<n;i++){
		cin>>a;
		arr[a]++;
	}
	cmp=arr;
	for(auto itr:arr){
		ans=max(itr.second+cmp[itr.first-1]+cmp[itr.first+1],ans);
	}
	cout<<ans<<endl;

}


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

ll qpow(ll x, ll k)
{
    ll res = 1;
    while(k)
    {
        if(k&1) res = res*x%mod;
        x = x*x%mod;
        k /= 2;
    }
    return res;
}

int main()
{
	ll n; cin >> n;
	ll ans = qpow(10, n) - 2*qpow(9, n) + qpow(8, n);
	ans = (ans%mod+mod)%mod;
	cout << ans << endl;
	return 0;
}


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

#define int long long
#define fi first
#define se second
#define otp(n) cout << n;
#define ct(n) cout << n << endl;
#define cts(n) cout << n << " ";
#define cte cout << endl;
#define ctv(v) rep(i,(v).size()) ct(v[i])
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repo(i,o,n) for(int i=o;i<n;i++)
#define repm(i,n) for(int i=n-1;i>=0;i--)
#define repv(i,v) for(int i=0;i<(v).size();i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define sperase(v,n) (v).erase(remove(all(v), n), (v).end());
#define vdelete(v) (v).erase(unique(all(v)), (v).end());
#define pb(n) push_back(n);


int n,a[200000],ans,memo[200000],xorsum,z,cnt;

main() {
    cin >> n;
    rep(i,n) cin >> a[i];

    rep(i,n) {
        while(z<n) {
            int tmpsum = xorsum + a[z];
            xorsum ^= a[z];
            if(tmpsum != xorsum) {
                xorsum = xorsum^a[z]^a[i];
                break;
            }
            z++,cnt++;
        }
        memo[i] = cnt;
        cnt--;
    }
    rep(i,n) ans += memo[i];
    ct(ans)
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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 fs first
#define sc second
typedef pair<ll, ll> l_l;
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
int main(){
  int n;
  cin>>n;
  bool f=false;
  for(int a=0;a<=25;a++){
    for(int b=0;b<=15;b++){
      if(4*a+7*b==n)f=true;
    }
  }
  if(f)
  cout <<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

#define pb push_back
#define mp make_pair

typedef long long ll;

int main()
{
  string s;
  cin >> s;

  int ans = 0;
  for(int i = 1; i < s.size(); i++){
    if(s[i] != s[i-1]) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
const ll D4[]={0,1,0,-1,0};
const ll D8[]={0,1,1,0,-1,-1,1,-1,0};
#define _overload3(_1,_2,_3,name,...) name
#define _rep2(i,n) for(ll i=0;i<(n);++i)
#define _rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2)(__VA_ARGS__)
#define _repe2(i,n) for(ll i=0;i<=(n);++i)
#define _repe3(i,a,b) for(ll i=(a);i<=(b);++i)
#define repe(...) _overload3(__VA_ARGS__,_repe3,_repe2)(__VA_ARGS__)
#define _rrep2(i,n) for(ll i=(n)-1;i>=0;i--)
#define _rrep3(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define rrep(...) _overload3(__VA_ARGS__,_rrep3,_rrep2)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
template<class T>
bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>
bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
template<class T>
using pq=priority_queue<T,vector<T>,greater<T>>;

ll N;
ll M;
vl p;
vl x;
vl y;

void solve();

int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> N;
    cin >> M;
    p = vl(N);
    for(int i = 0; i < N; ++i){
        cin >> p[i];
    }
    x = vl(M);
    y = vl(M);
    for(int i = 0; i < M; ++i){
        cin >> x[i];
        cin >> y[i];
    }
    solve();
}

// 2 ≤ N ≤ 10^5
// 1 ≤ M ≤ 10^5
// p は 1 から N までの整数を並び替えた順列
// 1 ≤ x_j,y_j ≤ N
// x_j ≠ y_j
// i ≠ j なら、 \{x_i,y_i\} ≠ \{x_j,y_j\}
// 入力は全て整数

struct UnionFind {
    vector<int> par;

    UnionFind(int sz){
        par.assign(sz+1,-1);
    }

    bool unite(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return false;
        if(par[x]>par[y])swap(x,y);
        par[x]+=par[y];
        par[y]=x;
        return true;
    }

    int find(int x){
        if(par[x]<0)return x;
        return par[x]=find(par[x]);
    }

    int size(int x){
        return -par[find(x)];
    }
};

// ll N, ll M, vl p, vl x, vl y
// 操作後の p_i = i となる i (1 ≤ i ≤ N) の数として考えうる最大値を出力せよ。
void solve(){
    UnionFind uf(N);
    rep(i,M)uf.unite(x[i],y[i]);
    ll ans=0;
    rep(i,N)ans+=uf.find(i+1)==uf.find(p[i]);
    cout<<ans<<endl;
}


Measured memory_bytes: 2944
N, M = map(int, input().split())
ks = [list(map(int, input().split())) for i in range(M)]
p = list(map(int, input().split()))

ans = 0

for i in range(2**N):
    light = 0
    for j in range(M):
        count = 0
        for k in range(1, ks[j][0]+1):
            if i & 2**(ks[j][k]-1) == 2**(ks[j][k]-1):
                count += 1
        if count % 2 == p[j]:
            light += 1
    if light == M:
        ans += 1

print(ans)

Measured memory_bytes: 3188
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 3e5 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int a, b;
	cin >> a >> b;
	if (a + b >= 10) puts("error");
	else cout << a + b << endl;
	return 0;
}

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

int main()
{
	int a,b,c,d,sum=0;
	string s;
	
	cin>>s;
	if(s[0]==s[1] || s[1]==s[2] || s[2]==s[3] || s[3]==s[4])
		cout<<"Bad";
	else
		cout<<"Good";
	return 0;
}
	

Measured memory_bytes: 256
program main
    implicit none
    integer n,m,number
    read(*,*) n, m
    number = 0
    if (n > 1) then
        number = n*(n-1)/2
    end if
    if (m > 1) then
        number = number + m*(m-1)/2
    end if
    write(*,*) number

end program

Measured memory_bytes: 640
#include <iostream>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <limits>
#include <numeric>
#include <algorithm>
#include <functional>

#include <vector>

using namespace std;

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

	long long N;
	cin >> N;

	long long sqN = sqrt(N);
	long long min_value = 2 * N + 1;
	for (long long a = 1; a <= sqN; a++)
	{
		if (N % a == 0)
		{
			long long b = N / a;
			min_value = min(min_value, a + b - 2);
		}
	}

	cout << min_value;

	return 0;
}


Measured memory_bytes: 256
char S[5<<17],*p=S,c;
b[5<<17];
I,l,r,t;
main(q)
{
	scanf("%*d%s%*d ",S);
	for(;*p;)b[++I]=1<<*p++-97;
	for(;q=~getchar();)
	{
		if(q&1)
		{
			scanf("%d%d ",&l,&r);t=0;
			for(int i=l;i<=r;)t|=b[i++];
			printf("%d\n",__builtin_popcount(t));
		}
		else
		{
			scanf("%d %c ",&I,&c);
			b[I]=1<<c-97;
		}
	}
}


Measured memory_bytes: 2688
#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
const double P=acos(-1);
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
	int ret=0,f=0;char c=gc();
	while(!isdigit(c)){if(c=='-')f=1;c=gc();}
	while(isdigit(c)){ret=ret*10+c-48;c=gc();}
	if(f)return -ret;return ret;
}
signed main()
{
	double a=read(),b=read(),n=read();
	if(n>=a*a*b/2)
	{
		double x=2*n/a/a-b;
		printf("%.8lf\n",atan((b-x)/a)*180/P);
	}
	else{
		double x=2*n/b/a;
		printf("%.8lf\n",atan(b/x)*180/P);
	}
}

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int A[] = new int[N];
    for(int i=0;i<N;i++){
      A[i]=sc.nextInt();
    }
    for(int i=0;i<N;i++){
      if(A[i]%2==1){
        continue;
      }else if(A[i]%3!=0&&A[i]%5!=0){
        System.out.println("DENIED");
        return;
      }else{
        continue;
      }
    }
    System.out.println("APPROVED");
    
  }
  

  
}

Measured memory_bytes: 21844
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from math import gcd
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
        self.size = [1] * n
        self.group_num = n

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

    def get_size(self, x):
        r = self.root(x)
        return self.size[r]

    def is_same(self, x, y):
        return self.root(x) == self.root(y)

    def union(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.size[r1] += self.size[r2]
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
            self.size[r2] += self.size[r1]
        self.group_num -= 1

n,m=LI()
U=UnionFind(n)
for _ in range(m):
    a,b=LI()
    U.union(a-1,b-1)

print(U.group_num-1)



Measured memory_bytes: 84088
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <utility>
using namespace std;

int bin_s(vector<int> &u, int key){
    int ok=-1, ng=u.size();
    while(ok+1<ng){
        int mid=(ok+ng)/2;
        if(u[mid]<key) ok=mid;
        else ng=mid;
    }
    return ng;
}


int main() {
	int N, Q; cin >> N >> Q;
	vector<pair<int, pair<int, int>>> v(N);
	for(int i=0; i<N; ++i){
	    int s, t, x;
	    cin >> s >> t >> x;
	    v[i]=make_pair(x, make_pair(s-x, t-x));
	}
	sort(v.begin(), v.end());
	vector<int> D(Q), next_num(Q), ans(Q, 1+1e9);
	for(int i=0; i<Q; ++i){
	    cin >> D[i];
	    next_num[i]=i+1;
	}
	for(int i=0; i<N; ++i){
	    int left=bin_s(D, v[i].second.first), right=bin_s(D, v[i].second.second);
	    while(left<right){
	        ans[left]=min(v[i].first, ans[left]);
	        int next=next_num[left];
	        next_num[left]=max(right, next_num[left]);
	        left=next;
	    }
	}
	for(int i=0; i<Q; ++i) cout << (ans[i]>1e9 ? -1 : ans[i]) << endl;
	return 0;
}


Measured memory_bytes: 6528
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int N = sc.nextInt();
		int i = sc.nextInt();
		int ans = N - i + 1;
		System.out.println(ans);
	}
}

class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;
    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte())
            return buffer[ptr++];
        else
            return -1;
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr]))
            ptr++;
        return hasNextByte();
    }

    public String next() {
        if (!hasNext())
            throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext())
            throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)
            throw new NumberFormatException();
        return (int) nl;
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
}


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

using ll = long long;

using T = tuple<int, int, int>;

using P = pair<ll, T>;

constexpr int MAX_XYZ = 1000;

ll A[MAX_XYZ];
ll B[MAX_XYZ];
ll C[MAX_XYZ];

int main() {
  int X, Y, Z, K;
  cin >> X >> Y >> Z >> K;

  for (int i{}; i < X; ++i) cin >> A[i];
  for (int i{}; i < Y; ++i) cin >> B[i];
  for (int i{}; i < Z; ++i) cin >> C[i];
  sort(A, A+X, greater<ll>());
  sort(B, B+Y, greater<ll>());
  sort(C, C+Z, greater<ll>());

  priority_queue<P> Q;
  vector<ll> ans;
  Q.push(P{A[0]+B[0]+C[0], T{0, 0, 0}});
  set<T> combi;
  combi.insert(T{0, 0, 0});
  while (ans.size() < K) {
    P p = Q.top();
    T t = p.second;
    int i = get<0>(t);
    int j = get<1>(t);
    int k = get<2>(t);
    Q.pop();
    ans.push_back(p.first);
    cout << p.first << endl;
    if (i < X-1) {
      T t{i+1, j, k};
      if (combi.find(t) == combi.end()) {
        Q.push(P{A[i + 1] + B[j] + C[k], t});
        combi.insert(t);
      }
    }
    if (j < Y-1) {
      T t{i, j + 1, k};
      if (combi.find(t) == combi.end()) {
        Q.push(P{A[i] + B[j + 1] + C[k], t});
        combi.insert(t);
      }
    }
    if (k < Z-1) {
      T t{i, j, k + 1};
      if (combi.find(t) == combi.end()) {
        Q.push(P{A[i] + B[j] + C[k + 1], t});
        combi.insert(t);
      }
    }
  }

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<(n);i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;

int main(){
    int n;cin>>n;
    vector<string>a;
    rep(i,n){
        string s;cin>>s;
        sort(been(s));
        a.push_back(s);
    }
    sort(been(a));
    ll now =1;
    ll ans =0;
    rep(i,n){
        if(i==0)continue;
        if(a[i-1]==a[i])now++;
        else{
            ans+=(now*(now-1))/2;
            now=1;
        }
    }
    ans+=(now*(now-1))/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 5748
// 2011/03/03 Tazoe

#include <iostream>
using namespace std;

int trian2(int x1, int y1, int x2, int y2)
{
	int s2 = x1*y2-x2*y1;

	if(s2<0)
		s2 = -s2;

	return s2;
}

bool insid(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)
{
	int s = trian2(x2-x1, y2-y1, x3-x1, y3-y1);

	int s1 = trian2(x1-x, y1-y, x2-x, y2-y);
	int s2 = trian2(x2-x, y2-y, x3-x, y3-y);
	int s3 = trian2(x3-x, y3-y, x1-x, y1-y);

	if(s==s1+s2+s3)
		return true;
	else
		return false;
}

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

	for(int i=0; i<n; i++){
		int xp1, yp1, xp2, yp2, xp3, yp3, xk, yk, xs, ys;
		cin >> xp1 >> yp1 >> xp2 >> yp2 >> xp3 >> yp3 >> xk >> yk >> xs >> ys;

		bool ink = insid(xp1, yp1, xp2, yp2, xp3, yp3, xk, yk);
		bool ins = insid(xp1, yp1, xp2, yp2, xp3, yp3, xs, ys);

		if(ink!=ins)
			cout << "OK" << endl;
		else
			cout << "NG" << endl;
	}

	return 0;
}

Measured memory_bytes: 864
////////////////////////// Author
////////////////////////// Nasim Hossain Rabbi
////////////////////////// JU-CSE28
////////////////////////// CF - imnasim3.1415
////////////////////////// UVA - imnasim3.1415
////////////////////////// Mail - imnasim3.1415@gmail.com
#include<bits/stdc++.h>
using namespace std;
#define E end()
#define B begin()
#define sz size()
#define EM empty()
#define clr clear()
#define sqr(a) (a*a)
#define mk make_pair
#define pb push_back
string en="\n";
string t="hello";
#define rep(i,n) for(i=0;i<n;i++)
#define Rep(i,n) for(i=1;i<=n;i++)
#define per(i,n) for(i=n-1;i>=0;i--)
#define peR(i,n) for(i=n;i>0;i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define all(cont) cont.begin(),cont.end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL)
#define pi 3.1415926535897932384626433832795
#define vi vector<int>
#define vl vector<long long>
#define vs vector<string>
#define vp(vi,x) cin>>x; vi.pb(x);
#define srch(a,x) binary_search(all(a),x)
#define LB(a,x) (lower_bound(all(a),x)-a.B)
#define UB(a,x) (upper_bound(all(a),x)-a.B)
typedef long long LL;
typedef unsigned long long ULL;
bool isprm(LL a){for(LL i=2;i*i<=a;i++){if(a%i==0)return false;}return true;}
bool palin(string a){for(int i=0;i<a.sz;i++){if(a.at(i)!=a.at(a.sz-i-1))return 0;} return 1;}
bool isVowel(char ch){ ch=toupper(ch); if(ch=='A'||ch=='U'||ch=='I'||ch=='O'||ch=='E') return true; return false;}
int toInt(string s){int sm;stringstream ss(s);ss>>sm;return sm;}
template<typename T>inline T gcd(T a,T b){if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}
template<typename T>inline T lcm(T a,T b) {if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}
int main()
{
//    fast;
    LL i,j,k,n,m,l,s=0,x,y,tc=1,c=0;
    while(cin>>n)
    {
        vi a;
        s=0;
        rep(i,n)
        {
            cin>>x;
            a.pb(x);
            s+=x;
        }
        sort(all(a));
        x=a[n-1];
        s-=x;
        if(x<s) cout<<"Yes"<<en;
        else cout<<"No"<<en;
    }
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define lli long long int
#define pii pair<int,int>
#define pll pair<lli,lli>
#define vi  vector<int>
#define vii vector<pair<int,int>>
#define vll vector<lli>
#define pb  push_back
#define mp  make_pair
#define ss  second
#define ff  first
#define all(x) sort(x.begin(),x.end())
map<int,int>m;
void solve()
{
    m.clear();
    int n;cin>>n;
    priority_queue<int>q;
    for(int i=1;i<=n;i++)
    {
        int a;cin>>a;
        m[a]++;
        if(m[a]==2 or m[a]>=4)
        {
            if(q.size()<2)
            {
                q.push(-a);
            }
            else
            {
                int x=-1*q.top();q.pop();
                if(a>x)q.push(-a);
                else q.push(-x);
            }
        }
    }
    if(q.size()!=2)cout<<0<<endl;
    else
    {
        lli x=-1*q.top();q.pop();
        lli y=-1*q.top();q.pop();
        lli ans=x*y;
        cout<<ans<<endl;
    }

}

int main()
{
    solve();
}


Measured memory_bytes: 8168
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;i++)
const ll INF=1e15;
const ll MOD=1000000007;

int main(){
    int N,M;cin>>N>>M;
    vector<pair<ll,ll>> info[N];
    ll edge[M][3];
    rep(i,M){
        int a,b,c;cin>>a>>b>>c;
        edge[i][0]=a-1;edge[i][1]=b-1;edge[i][2]=c;
        info[a-1].push_back(make_pair(b-1,c));
        info[b-1].push_back(make_pair(a-1,c));
    }
    ll dist[N][N];
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> que;
    rep(i,N){
        ll nowdist[N];
        rep(j,N){
            if(j==i)nowdist[j]=0;
            else nowdist[j]=INF;
        }
        que.emplace(0,i);
        while(que.size()){
            ll d=que.top().first,v=que.top().second;
            que.pop();
            for(auto j:info[v]){
                ll nv=j.first,nc=j.second;
                if(nowdist[nv]>d+nc){
                    nowdist[nv]=d+nc;
                    que.emplace(nowdist[nv],nv);
                }
            }
        }
        rep(j,N)dist[i][j]=nowdist[j];
    }
    ll count=0;
    rep(i,M){
        ll a=edge[i][0],b=edge[i][1],c=edge[i][2];
        rep(j,N){
            if(dist[j][b]==dist[j][a]+c){
                count++;
                break;
            }
            else if(dist[j][a]==dist[j][b]+c){
                count++;
                break;
            }
        }
    }
    cout<<M-count<<endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int main()
{
	//freopen("In.txt" , "r" , stdin);
	LL n , s;
	cin >> n >> s;
	if(n == s)
	{
		cout << n + 1;
		return 0;
	}
	if(n < s)
	{
		cout << -1;
		return 0;
	}
	for(int b = 2; b <= 500000; b++)
	{
		LL N = n;
		LL s2 = 0;
		while(N)
		{
			s2 += N % b;
			N /= b;
		}
		if(s2 == s)
		{
			cout << b;
			return 0;
		}
	}
	LL ans2 = 1000LL * 1000 * 1000 * 1000 * 1000;
	for(int k = 1; k <= 500000; k++)
	{
		LL b = s - k;
		if(b < 0)
			continue;
		if(n - b < 0)
			continue;
		if((n - b) % k)	
			continue;
		LL x = (n - b) / k;
		if(x <= b)
			continue;
		ans2 = min(ans2 , x);
	}
	if(ans2 == 1000LL * 1000 * 1000 * 1000 * 1000)
	{
		cout << -1;
		return 0;	
	}
	cout << ans2 << endl;
	return 0;
}


Measured memory_bytes: 256
N = int(input())
import heapq as h
A = list(map(int, input().split()))


# use 0 based index
sum_red, sum_blue = [], []

head = A[:N]
tail = [-x for x in A[-N:]]
h.heapify(head)
h.heapify(tail)
sum_red.append(sum(head))
sum_blue.append(-sum(tail))
# keypoint: いちいちsumすると線形時間かかるのでsum_hoge[-1]でアクセスする
for k in range(N, 2*N):
    num_sub = h.heappushpop(head, A[k])
    sum_red.append(sum_red[-1]-num_sub+A[k])
    num_sub = -h.heappushpop(tail, -A[-k-1])
    sum_blue.append(sum_blue[-1]-num_sub+A[-k-1])


print(max([r-b for r, b in zip(sum_red, sum_blue[::-1])]))


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

#define dbg(x) cerr<<#x": "<<x<<"\n"
#define dbg_p(x) cerr<<#x": "<<x.first<<","<<x.second<<"\n"
#define dbg_v(x, n) do{cerr<<#x"[]: ";for(int _=0;_<n;++_)cerr<<x[_]<<" ";cerr<<'\n';}while(0)
#define dbg_ok cerr<<"OK!\n"

#define st first
#define nd second

using namespace std;

const long long N = 300100;
const long long MOD = 998244353;
long long n, k, a, b, f[N];

template<class T>
ostream& operator<<(ostream& out, vector<T> v) {
	out << v.size() << '\n';
	for(auto e : v) out << e << ' ';
	return out;
}

long long powMod(long long b, long long e) {
	if(e == 0) return 1;
	if(e == 1) return b;

	long long t = powMod(b, e / 2);
	t = (t * t) % MOD;
	if(e % 2) return (t * b) % MOD;
	return t;
}

long long invMod(long long k) {
	return powMod(k, MOD - 2);
}

long long comb(long long n, long long k) {
	return (f[n] * invMod( ((f[k] * f[n - k]) % MOD)))%MOD;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin >> n >> a >> b >> k;

	f[0] = 1;
	for(int i = 1; i <= n; i++)
		f[i] = (f[i - 1] * i) % MOD;
	long long ans = 0;
	for(long long i = 0; i <= n; i++) {
		long long r = k - i * a;
		if(r < 0) break;
		if(r % b == 0) {
			long long y = r / b;
			if(y > n) 
				continue;
			ans += comb(n, i) * comb(n, y);
			ans %= MOD;
		}
	}	

	cout << ans << '\n';

}	

Measured memory_bytes: 2560
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <limits>
#include <numeric>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

int main()
{

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	if (b < c || d < a) {
		cout << 0 << endl;
		return 0;
	}
	else if (a <= c) {
		if (b >= d) {
			cout << d - c << endl;
			return 0;
		}
		else {
			cout << b - c << endl;
			return 0;
		}
	}
	else if(a>c){
		if (b < d) {
			cout << b - a << endl;
			return 0;
		}
		else {
			cout << d - a << endl;
			return 0;
		}
	}
	else cout << "error" << endl;

	return 0;
}

Measured memory_bytes: 256
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-04-26 16:48:13
*/

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

#define all(x) (x).begin(),(x).end()
#define rev(x) greater<x>()
#define MOD 1000000007
#define INF 1000000000

typedef long long LL;
typedef long double LD;

bool compare_by_b(pair<int, int> a, pair<int, int> b)
{
    if (a.second != b.second) {
        return a.second < b.second;
    } else {
        return a.first < b.first;
    }
}

LL modpower(LL n, LL m, LL mod)
{
    if (m == 0) {
        return 1;
    } else if (m % 2 == 0) {
        LL p = modpower(n, m/2, mod);
        return p*p % mod;
    } else {
        return n*modpower(n, m-1, mod) % mod;
    }
}

LL modinv(LL n, LL mod)
{
    return modpower(n, mod-2, mod);
}

LL modcombination(LL n, LL r, LL mod)
{
    LL ret = 1;

    for (int i = 0; i < r; i++) {
        ret *= (n-i);
        ret %= mod;
        ret *= modinv(i+1, mod);
        ret % mod;
    }

    return ret % mod;
}

int gcd(int k, int l)
{
    if (l > 0) return gcd(l, k%l);
    else return k;
}

struct UnionFind
{
    vector<int> par;

    UnionFind(int n) : par(n) {
        for (int i = 0; i < n; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main()
{
    int n;
    string s;
    cin >> n >> s;

    int left, right;
    left = right = 0;
    int cnt[n];
    for (int i = 0; i < n; i++) {
        if (s[i] == '(') left++;
        else right++;

        cnt[i] = left - right;
    }

    int min = INF;
    for (int i = 0; i < n; i++)
        if (min > cnt[i]) min = cnt[i];

    if (min <= 0) {
        for (int i = 0; i < -min; i++) cout << '(';
        cout << s;
        for (int i = 0; i < cnt[n-1]-min; i++) cout << ')';
        cout << endl;
    } else {
        cout << s;
        for (int i = 0; i < cnt[n-1]; i++) cout << ')';
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<sstream>
using namespace std;
int stoi(string a){
		int b;
		stringstream ss;
		ss<<a;
		ss>>b;
		return b;
	}
	string itos(int a){
		stringstream ss;
		ss <<a;
		string b;
		b=ss.str();
		return b;
	}

int main(){
	string n;int t;
	while(cin>>n,n!="0000"){
		int ns=n.size();
		for(int i=0;i<4-ns;i++)n="0"+n;
		int ans=0;
		bool flag=true;
		if(n[0]==n[1]&&n[1]==n[2]&&n[2]==n[3])flag=false;
		
		if(flag){
			while(n!="6174"){
			//	cout<<n<<endl;
				//cin>>t;
				int a[4]={0},b[4]={0},ai,bi;
				for(int i=0;i<4;i++)a[i]=n[i]-'0',b[i]=n[i]-'0';
				sort(a,a+4);
				sort(b,b+4);
				reverse(b,b+4);
				int tmp=0,l,s;
				l=1000*b[0]+100*b[1]+10*b[2]+b[3];
				s=1000*a[0]+100*a[1]+10*a[2]+a[3];
			//	cout<<s<<" "<<l<<endl;
				tmp=l-s;
				n=itos(tmp);
				ns=n.size();
				for(int i=0;i<4-ns;i++)n="0"+n;
				ans++;
			}
		}
		if(flag)cout<<ans<<endl;
		else cout<<"NA"<<endl;
	}
	return 0;
}

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

int main(void){
    int N, L;
    cin >> N >> L;
    string s[N];
    for(int i = 0; i < N; i++)
        cin >> s[i];
    for(int i = 0; i < N-1; i++){
        for(int j = i+1; j < N; j++)
        if(s[i] > s[j])
            swap(s[i], s[j]);
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < L; j++)
            cout << s[i][j];
    }
    cout << endl;
    return 0;
}


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

int cnt[100010];
bool looked[100010], ext[100010];

int main() {
	int K;
	cin >> K;
	if(K==99991){
		cout << 3 << endl;
		return 0;
	}
	int now=1;
	while(cnt[now]<2){
		++cnt[now];
		now=(now*10)%K;
	}
	vector<int> edge;
	for(int i=0; i<=K; ++i){
		if(cnt[i]==2){
			edge.push_back(i);
			ext[i]=1;
		}
	}
	vector<int> num{K};
	looked[K]=1;
	int ans=1;
	while(1){
		for(int i=0; i<num.size(); ++i){
			if(ext[(K-num[i])%K]){
				cout << ans << endl;
				return 0;
			}
		}
		vector<int> nx;
		for(int i=0; i<num.size(); ++i){
			for(int j=0; j<edge.size(); ++j){
				int cand=(num[i]+edge[j])%K;
				if(!looked[cand]){
					nx.push_back(cand);
					looked[cand]=1;
				}
			}
		}
		num.swap(nx);
		++ans;
	}
	return 0;
}


Measured memory_bytes: 1784
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include<cstdio>
#include <vector>
#include<queue>
#include<limits.h>
#include<string.h>
#include<functional>
using namespace std;

bool K(int a) {
	if (a % 3 == 0)return true;
	string b = to_string(a);
	for (char c : b) {
		if (c == '3')return true;
	}
	return false;
}
signed main() {
	int a; cin >> a;
	for (int i = 1; i <= a; i++) {
		if (K(i))cout << " " << i;
	}
	puts("");
}

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

#define PI 3.14159265359
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;

int main() {
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,0,n)cin>>a[i];

    int ans=0,j;
    for(int i=0;i<n;){
        int cnt=1;
        int j=i+1;
        while(a[i]==a[j]){
            cnt++;
            j++;
        }
        i=j;
        ans+=cnt/2;
    }
    cout<<ans<<endl;
    return 0;
}

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

using namespace std;

int main(void) {
  string s;
  cin >> s;

  int cnt[26] = {};
  for (int i = 0; i < s.size(); i++) {
    cnt[s[i] - 'a']++;
  }

  int ans = 1e9;
  for (int i = 0; i < 26; i++) {
    if (cnt[i]) {
      int st = 0, diff = 0, j;
      for (j = 0; j < s.size(); j++) {
        if (s[j] == i + 'a') {
          diff = max(diff, j - st);
          st = j + 1;
        }
      }
      diff = max(diff, j - st);
      ans = min(ans, diff);
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
using namespace std;
const int MAXN = 1e5 + 5;
char s[MAXN];
int a[MAXN];
int main()
{
    scanf("%s",s+1);
    int len = strlen(s+1);
    for(int i = 'a'; i <= 'z'; i++){
        a[i] = 1;
    }
    for(int i = 1; i <= len; i++){
        char p = s[i];
        for(int j = 'a'; j <= 'z'; j++){
            if(p == j) a[j] = 0; 
        }
    }
    char t;
    int flag = 0;
    for(int i = 'a'; i <= 'z'; i++){
        if(a[i] == 1) {
            flag = 1;
            t = i;
            break;
        }
    }
    if(flag == 1) printf("%c\n",t);
    else printf("None\n");
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9
#define MOD 1000000007

using namespace std;
typedef long long int lli;
typedef long long ll;

int main(){
    int n; cin >> n;
    vector<int> v(n); rep(i,n) cin >> v[i];

    map<int,int> m1,m2;
    int max1 = 0,max2 = 0;
    int maxv1,maxv2;
    rep(i,n){
        if(i%2 == 0){
            m1[v[i]]++;
            if(max1 < m1[v[i]]){
                max1 = m1[v[i]];
                maxv1 = v[i];
            }
        }
        else{
            m2[v[i]]++;
            if(max2 < m2[v[i]]){
                max2 = m2[v[i]];
                maxv2 = v[i];
            }
        }
    }

    priority_queue<int> q1, q2;
    auto begin = m1.begin(), end = m1.end();
    for(auto iter = begin; iter != end; iter++){
        q1.push(iter->second);
    }
    begin = m2.begin(), end = m2.end();
    for(auto iter = begin; iter != end; iter++){
        q2.push(iter->second);
    }

    int ans;
    if(maxv1 == maxv2){
        q1.push(0);
        q2.push(0);
        q1.pop();
        q2.pop();
        if(max1-q1.top() > max2-q2.top()) ans = n-max1-q2.top();
        else ans = n-max2-q1.top();
    }
    else{
        ans = n-q2.top()-q1.top();
    }

    cout << ans << endl;
}


Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+13;
int a[maxn]; 
int main()
{
	ll x,k,d;
	scanf("%lld%lld%lld",&x,&k,&d);
	if(x<0) x=-x;
	ll cal=x/d;
	if(cal>=k)
	{
		printf("%lld",abs(x-k*d));
	}
	else
	{
		ll res=x-cal*d;
		ll way=k-cal;
		if(way&1)
		{
			printf("%lld",d-res);
		}
		else
		{
			printf("%lld",res);
		}
	}
 } 

Measured memory_bytes: 3820
// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

vector<int> g[100111],t[100111];
int n,m,mark[100111],sz[4],sze;
bool ok;
LL ans;
void dfs(int x,int mk=1)
{
	if(mark[x]&&mark[x]!=mk)
	{
		ok=0;
		return;
	}
	if(mark[x])return;
	mark[x]=mk;
	sz[mk]++;sz[0]++;sze+=(int)g[x].size();
	for(int i=0;i<(int)g[x].size();i++)
	{
		int nmk=mk+t[x][i];
		if(nmk==0)nmk=3;if(nmk==4)nmk=1;
		dfs(g[x][i],nmk);
	}
}
int main()
{
	get2(n,m);
	for(int i=1,u,v;i<=m;i++)
	{
		get2(u,v);
		g[u].pb(v);t[u].pb(1);
		g[v].pb(u);t[v].pb(-1);
	}
	for(int i=1;i<=n;i++)
	{
		if(!mark[i])
		{
			memset(sz,0,sizeof(sz));ok=1;sze=0;
			dfs(i);
			if(ok)
			{
				if(sz[1]&&sz[2]&&sz[3])ans+=1ll*sz[1]*sz[2]+1ll*sz[2]*sz[3]+1ll*sz[3]*sz[1];
				else ans+=sze>>1;
			}
			else ans+=1ll*sz[0]*sz[0];
		}
	}
	printendl(ans);
	return 0;
}

Measured memory_bytes: 17792
#include <bits/stdc++.h>
using namespace std;
#define INFTY 1000000001

long long ans;

void merge(vector<int> &A,int left,int mid,int right){
    int n1=mid-left;
    int n2=right-mid;
    vector<int> L(n1+1);
    vector<int> R(n2+1);
    for(int i=0;i<n1;i++){
        L[i]=A[left+i];
    }
    for(int i=0;i<n2;i++){
        R[i]=A[mid+i];
    }
    L[n1]=R[n2]=INFTY;
    
    int i=0,j=0;
    for(int k=left;k<right;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }
        else{
            A[k]=R[j];
            j++;
            ans+=n1-i;
        }
    }
}

void mergeSort(vector<int> &A,int left,int right){
    if(left+1<right){
        int mid=(left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }
}

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

    ans=0;
    mergeSort(A,0,n);

    cout<<ans<<endl;
}


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

template <typename Abel> struct BIT {
    const Abel UNITY_SUM = 0;
    vector<Abel> dat;
    BIT(int n) : dat(n + 1, UNITY_SUM) { }  // [1, n]
    inline void add(int i, Abel x) {
        while (i < dat.size()) { dat[i] += x; i += i & -i; }
    }
    inline Abel sum(int i) {    // [1, i]
        Abel res = UNITY_SUM;
        while (i > 0) { res += dat[i]; i -= i & -i; }
        return res;
    }
    inline Abel sum(int a, int b) { return sum(b - 1) - sum(a - 1); }   // [a, b)
    /* debug */
    Abel operator[](int i) { return sum(i, i + 1); }
    void debug() {
        for (int i = 1; i < dat.size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

template<typename T> long long inversion_number(const vector<T> &a) {
    int n = a.size();
    vector<T> b = a;
    sort(begin(b), end(b)); b.erase(unique(begin(b), end(b)), end(b));
    long long res = 0;
    BIT<int> bit(n);
    for (T ai: a) {
        int order = lower_bound(begin(b), end(b), ai) - begin(b) + 1;
        res += bit.sum(order + 1, n + 1); bit.add(order, 1);
    }
    return res;
}

int main() {
    int n, k; cin >> n >> k;
    vector<int> a(n);
    for (auto &ai: a) cin >> ai;
    vector<long long> acc(n + 1);
    for (int i = 0; i < n; i++) acc[i + 1] = acc[i] + a[i] - k;
    cout << 1LL * (n + 1) * n / 2 - inversion_number(acc) << endl;
    return 0;
}

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

typedef long long int llint;

int main()
{
  int tim[100001] = {};
  int n, cn;
  cin>> n >> cn;

  int s, t, c;
  for(int i = 0; i < n; i++) {
    cin>> s >> t >> c;
    
    for(int j = s - 1; j < t; j++) tim[j] |= (1 << (c - 1));
  }
  
  int cnt = 0;
  for(int i = 0; i <= 100000; i++) {
    bitset<32> bs(tim[i]);
    int tmp = bs.count();
    cnt = max(cnt, tmp);
  }

  cout<< cnt <<endl;

  return 0;
}


Measured memory_bytes: 768
#define NDEBUG

#include <unordered_map>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <tuple>
#include <set>
#include <map>

// [0, max)
#define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var))
// [min, max)
#define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var))
// [min, max)
#define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

// a < b < c
#define LTLT(a, b, c) (((a) < (b)) && ((b) < (c)))
// a <= b < c
#define LELT(a, b, c) (((a) <= (b)) && ((b) < (c)))
// a < b <= c
#define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c)))
// a <= b <= c
#define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c)))

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

using sc = signed char;
using si = signed int;
using sl = signed long long int;

using ld = long double;

static sl N;

void solve(void) {
  if (N % 2 == 0) {
    cout << (N / 2 - 1) << endl;
  } else {
    cout << ((N - 1) / 2) << endl;
  }
}

int main(void) {
  cin >> N;
  solve();
  return 0;
}

Measured memory_bytes: 256
#include "stdio.h"
#include "stdlib.h"
#include "iostream"
#include "math.h"
#include <string.h>

//#define "limits.h"
using namespace std;



int main() {
	int a, b, c, d;
	int i, j, k;
	cin >> a >> b >> c >> d;
	i = (int)fmin(a, b) + fmin(c, d);
	printf("%d\n", i);
	

	return 0;
}

Measured memory_bytes: 256