akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <stack>
#include <list>
#include <deque>
using namespace std;
int n, m, i, j, k, t;
int a, b, c, d;
int main(){
	cin>>a>>b>>c>>d;
	if(c>=b||a>=d) cout<<0;
	else{
		if((a-c)*(b-d)<=0) cout<<min(b-a,d-c);
		else cout<<min(b,d)-max(a,c);
	}
	return 0;
}


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

int main() {
    int n;
    cin >> n;
    int d[n];
    for (int i = 0; i < n; i++){
        cin >> d[i];
    }
    int sum = 0;
    for (int i = 0; i < n-1; i++){
        for (int j = i+1; j < n; j++){
            sum += d[i]*d[j];
        }
    }
    cout << sum;

    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <ctype.h>
using namespace std;

int main(){
    char str[1200];
    gets(str);
    int i = 0;
    while(str[i] != '\0'){
        char uc, lc;
        uc = toupper(str[i]);
        lc = tolower(str[i]);

        if(lc == str[i]) printf("%c", uc);
        else printf("%c", lc);
        ++i;
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 916
n=int(input())
a=list(map(int,input().split()))
l=[None]*(n+1)
for i in range(n+1):
    if l[a[i]]==None:
        l[a[i]]=i
    else:
        p=l[a[i]]+n-i
        break
pr=10**9+7
print(n)
MAX_NUM = 10**5 + 2
fac  = [0 for _ in range(MAX_NUM)]
finv = [0 for _ in range(MAX_NUM)]
inv  = [0 for _ in range(MAX_NUM)]
fac[0]  = fac[1] = 1
finv[0] = finv[1] = 1
inv[1] = 1
for i in range(2,MAX_NUM):
    fac[i] = fac[i-1] * i % pr
    inv[i] = pr - inv[pr%i] * (pr // i) % pr
    finv[i] = finv[i-1] * inv[i] % pr
def c(n,k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n-k] % pr) % pr
for i in range(2,n+1):
    t=c(n+1,i)
    if p>=i-1:
        t-=c(p,i-1)
    print(t%pr)
print(1)

Measured memory_bytes: 24400
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forin(in, n) for(int i=0; i<n; i++) cin>>in[i]
#define forout(out, n) for(int i=0; i<n; i++) cout<<out[i]<<endl

int main(){
    int A, B; cin>>A>>B;
    for(int i=0; i<=1000; i++){
        if(i*8/100 == A && i/10==B){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<"-1"<<endl;
}


Measured memory_bytes: 3620
#include<stdio.h>
#include<math.h>
int main()
{
	int n,i;
	long long int s=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		if(i%3!=0&&i%5!=0)
		s+=i;
	}
	printf("%lld",s);
	return 0;
}


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

using namespace std;
int main() {
// #ifdef LDT
//     freopen("input.txt", "r", stdin);
//     //freopen("output.txt", "w", stdout);
// #else 
//     freopen("movie.inp", "r", stdin);
//     freopen("movie.out", "w", stdout);
// #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    long long res = 0;
    long long suma = 0;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        res += 1ll * x * x;
        suma += x;
    }
    suma *= 2;
    //find y such that n * y * y - suma * y is min
    //n * 2 * y - suma = 0
    long long best = suma / 2 / n;
    #define cost(x) ((x) * (x) * n - suma * (x))
    res = res + min({cost(best), cost(best - 1), cost(best + 1)});
    cout << res;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int (i)=0;(i)<(n);i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define MOD 1000000007
#define FOUT(n, dist) cout<<fixed<<setprecision(n)<<(dist);
#define BR cout<<endl;
#define LEN(s) s.length();
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; }
#define ALL(v) v.begin(), v.end()
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}

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

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

    long long int sum = 0, ans = 0, tem = 0;

    for(int i = 0; i < n; i++){
        sum += tem * a[i];
        sum = sum % mod;
        tem += a[i];
        tem %= mod;
    }

    cout << sum << endl;

    return 0;
}



Measured memory_bytes: 5152
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
const ll MOD = 1e9+7;
//modulo arithmetic
inline ll add(ll a, ll b)
{
	ll res = a + b;
	if(res >= MOD)
		return res - MOD;
	return res;
}

inline ll mult(ll a, ll b)
{
	ll  res = a;
	res *= b;
	if(res >= MOD)
		return res % MOD;
	return res;
}

inline ll sub(ll a, ll b)
{
	return (a%MOD-b%MOD+MOD)%MOD;
}
int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
	ll n;
	cin>>n;
	ll a[n];
	for(ll &x:a)
		cin>>x;
	ll sum=0;
	ll ans=0;
	for(ll x:a)
	{
		ans=add(ans,mult(sum,x));
		sum=add(sum,x);
	}		
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 5208
from sys import stdin
n,m = [int(x) for x in stdin.readline().rstrip().split()]

li = [list(stdin.readline().rstrip().split()) for _ in range(m)]
lin = [0]*(n+1)
wor = [0]*(n+1)

for i in li:
    if lin[int(i[0])] == 0:
        if i[1] == "WA":
            wor[int(i[0])] += 1
        elif i[1] == "AC":
            lin[int(i[0])] = 1
wa = 0
for i in range(n+1):
    if lin[i] == 1:
        wa += wor[i]

print(sum(lin),wa)


Measured memory_bytes: 27476
#!/usr/bin/env python3
N = int(input())
V, M, F = "Vacant", "Male", "Female"
left = 0
right = N
print(0)
s_left = input()
if s_left == V:
    exit()
while True:
    mid = (right + left) // 2
    print(mid)
    s_mid = input()
    if s_mid == V:
        exit()
    if s_left == s_mid:
        if (mid - left) % 2:
            right = mid
        else:
            left = mid
    else:
        if (mid - left) % 2:
            left = mid
            s_left = s_mid
        else:
            right = mid


Measured memory_bytes: 9080
#include<stdio.h>

int main()
{
    int A,B,C,D,x=0,y=0;
    scanf("%d%d%d%d",&A,&B,&C,&D);
    if(1<=A && A<=10000 && 1<=B && B<=10000 && 1<=C && C<=10000 && 1<=D && D<=10000)
    {
        x=A*B;
        y=C*D;
        if(x>y) printf("%d",x);
        else if (x==y) printf("%d",x);
        else printf("%d",y);
    }

return 0;
}

Measured memory_bytes: 1692
import java.io.*;
import java.util.StringTokenizer;
import java.util.Scanner;

public final class Main{
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        double n = stdIn.nextDouble();
        double[] a = new double[(int)n];
        for(int i=0; i<(int)n; i++){
            a[i] = stdIn.nextDouble();
        }
        
        double up = 1;
        double down = 0.0;
        for(int i=0; i<a.length; i++){
            up *= a[i];
        }
        for(int i=0; i<a.length; i++){
            down += up/a[i];
        }

        System.out.println(up/down);
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
        reader = new BufferedReader(new InputStreamReader(in));
        tokenizer = null;
    }

    public String next() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(reader.readLine());
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return tokenizer.nextToken();
    }

    public String nextLine() {
        if (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        return tokenizer.nextToken("\n");
    }

    public long nextLong() {
        return Long.parseLong(next());
    }
    
    public long nextInt() {
        return Integer.parseInt(next());
    }

}


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

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long int lli;
using namespace std;
typedef pair<int, int> ii;
#define int long long int

inline void swap(int &a, int &b) {
    int tmp = a;
    a = b;
    b = tmp;
}

signed main() {
    int N; cin >> N;
    vector<ii> tasks(N);
    for(auto&& t : tasks) {
        int _a, _b; cin >> _a >> _b;
        t = ii(_a, _b);
    }
    sort(
        tasks.begin(),
        tasks.end(),
        [](const ii& x, const ii& y) {
            return x.second < y.second;
        }
    );

    int time = 0;
    for (int i = 0; i < N; i++) {
        time += tasks[i].first;
        if (time > tasks[i].second) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1792
//
//  sheep_wolves.cpp
//  learningCplusplus
//
//  Created by Tran Duc Chinh on 2020/04/04.
//  Copyright © 2020 Tran Duc Chinh. All rights reserved.
//

#include <iostream>
#include <math.h>
using namespace std;
typedef long long ll;
ll mod = 1000000007;


int main(int argc, const char* argv[]) {

  int s, w;
  std::cin >> s >> w;

  if (w >= s) {
    std::cout << "unsafe" << std::endl;
  }
  else {
    std::cout << "safe" << std::endl;
  }

  return 0;
}


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



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

	ll r, d, x;
	cin >> r >> d >> x;
	for (int i = 1; i <= 10; i++)
		cout << (x = r * x - d) << endl;
}


Measured memory_bytes: 384
#include<stdio.h>

int main(){
   int a,b,c;
   scanf("%d %d %d",&a,&b,&c);
   if((a+b)==c||(b+c)==a||(a+c)==b){
    printf("Yes");
   }
   else{
    printf("No");
   }
    return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ff first
#define ss second
#define int long long
#define pb push_back
#define mp make_pair
#define pq priority_queue<int> 
#define pqs priority_queue<int,vector<int>, greater<int>>
#define setbits(x) __builtin_popcountll(x)  // no of ones in setbit
#define zrobits(x) __builtin_ctzll(x)       //101000 here 3..no of 0 aftrer 1sr right one 
#define mod 1000000007
#define inf 1e18
#define prDouble(x)  cout<<fixed<<setprecision(10)<<x     // ans upto 5 decimal place 
#define mk(ar,n,type) type *arr=new type[n];
#define w(x) int x;cin>>x;while(x--)
int dp[100000]={0} ;  


void fn(int arr[],int k,  int n)
{

	dp[0]=0 ; 
	for(int i=1; i<=k; i++)
	{
		int f=0 ; 
		for(int j=0 ; j<n; j++)
		{
			if( i-arr[j]>=0 and dp[i-arr[j]]==0)
			{
				f=1; 
				dp[i]=1; 
				break ; 
			}
		}
		if(f==0)
		{
			dp[i]=0 ; 
		}
	}

	if(dp[k]==1)
	{
		cout<<"First"; 
	}
	else
	{
		cout<<"Second"; 
	}

}

int32_t main()
{
	int n, k ;
	cin>>n>>k ; 
	// std::vector<int> v;
	int v[1000000]; 
	for(int i=0 ; i<n; i++)
	{
		int x;
		cin>>x; 
		// v.push_back(x); 
		v[i]=x  ; 
	}

	fn(v, k, n) ; 
}



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

int main(void) {
  int N;
  cin >> N;
  vector<int> a(N);
  bool odd = false;
  for (int i = 0; i < N; i++) {
    cin >> a[i];
    if (a[i] % 2 != 0) odd = true;
  }
  if (odd) cout << "first" << endl;
  else cout << "second" << endl;

  return 0;
}

Measured memory_bytes: 640
import logging
import heapq

logging.basicConfig(level=logging.INFO, format="%(message)s")
#logging.disable(logging.CRITICAL)

def calc_(s):
    return int(s) * (-1)

def main():
    N, M = map(int, input().split())
    L_1 = list(map(calc_, input().split()))
    logging.info("Hello!")

    heapq.heapify(L_1)
    
    for i in range(M):
        temp = heapq.heappop(L_1) * (-1)
        temp = temp // 2
        heapq.heappush(L_1, temp * (-1))

    print(sum(list(L_1)) * (-1))
        
if __name__ == "__main__":
    main()

    


Measured memory_bytes: 15392
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>

int main(void){
    int i,j,k;
    int r;
    
    scanf("%d",&r);
    
    
    printf("%d\n",3*r*r);
    
    
    return 0;
}


Measured memory_bytes: 128
n = gets.to_i
nums = readline.split.map(&:to_i)
count = 0

nums.each_with_index do |m, i|
view = true
  nums.each_with_index do |n, j| 
    if i == j
      break
    end
    if m < n
      view = false
      break
    end
  end
  if view
    count += 1
  end
end

p count

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

int N;
string S, T, ans;

int main() {
  cin >> N;
  cin >> S >> T;
  rep(i, N) {
    ans += S[i];
    ans += T[i];
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
    char n[4];
    cin>>n;
    if((n[0]==n[1]&&n[1]==n[2])||(n[1]==n[2]&&n[2]==n[3])) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

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

int main() {
  char c;
  cin >> c;
  string s;
  if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
    s = "vowel";
  }
  else {
    s = "consonant";
  }
  
  cout << s << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;

const int maxm = 200005;
const int maxn = 200005;
const int inf = 0x7fffffff;

struct DINIC {
	int s, t, maxflow, tmp, tot;
	int eu[maxm], et[maxm], ef[maxm], ep[maxm];
	int d[maxn], a[maxn];
	bool v[maxn];
	queue<int> q;
	void add(int x,int y,int c,int l) {
		++ tot;
		et[tot] = y;
		eu[tot] = c;
		ef[tot] = a[x];
		a[x] = tot;
		ep[tot] = tot + l;
	}

	bool bfs() {
		memset(d,0,sizeof d);
		memset(v,0,sizeof v);
		q.push(s);
		d[s] = 1;
		while(!q.empty()) {
			int now = q.front();
			q.pop();
			for(int i = a[now]; i; i = ef[i]) {
				if(eu[i]>0 && d[et[i]]==0) {
					d[et[i]] = d[now] + 1;
					q.push(et[i]);
				}
			}
		}
		return d[t] != 0;
	}

	int dfs(int x, int y) {
		if(x == t) {
			tmp+=y;
			return y;
		}
		v[x] = 1;
		int z = 0;
		for(int i = a[x]; i; i = ef[i]) {
			if(eu[i]>0 && d[x]+1==d[et[i]] && y!=0 && !v[et[i]]) {
				int j = dfs(et[i], min(y, eu[i]));
				if(j) {
					eu[i] -= j;
					eu[ep[i]] += j;
					z += j;
					y -= j;
				}
			}
		}
		return z;
	}   

	void dinic() {
		tmp = 0;
		while(bfs()) {
			while(dfs(s, inf)) {
				maxflow += tmp; 
				tmp = 0;
			}
		}
	}

	void clear() {
		tot = 0;
		maxflow = 0;
		memset(a, 0, sizeof a);
		memset(ef, 0, sizeof ef);
	}
} flow;

void make_graph() {
	int n,m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++ i) {
		int x, y;
		scanf("%d%d", &x, &y);
		flow.add(x, y, 1, 1);
		flow.add(y, x, 1, -1);
	}
	scanf("%d%d", &flow.s, &flow.t);
}

int main() {
	int T;
//	scanf("%d", &T);
	//while(T --) 
	{
		make_graph();
		flow.dinic();
		printf("%d\n", flow.maxflow);
		int ans = 0;
		for(int i = 1; i <= flow.tot; ++ i) {
			if(flow.eu[i] == 0 && i % 2 == 0) ans ++;
		}
		printf("%d\n", ans);
		for(int i = 1; i <= flow.tot; ++ i) {
			if(flow.eu[i] == 0 && i % 2 == 0) printf("%d\n", i/2);
		}
		flow.clear();
	}
}

Measured memory_bytes: 4400
#include <bits/stdc++.h>
#define ll long long
#define ALL(x) x.begin(),x.end()
#define MOD (1000000000+7)
using namespace std;
#define PI 3.14159265359
#define tMOD 998244353
#define mkpr(x,y) make_pair(x,y)


ll N;

int main(){

  cin>>N;
  vector<ll> A(N);

  for(ll i=0;i<N;i++){
    cin>>A[i];
  }

ll eend=0;
  vector<ll> num(3);
  ll kanou=1;
  sort(ALL(num));
  for(ll i=0;i<N;i++){
    ll tmp=0;
    if(num[0]==A[i]){
      tmp++;
    }
    if(num[1]==A[i]){
      tmp++;
    }
    if(num[2]==A[i]){
      tmp++;
    }
    kanou*=tmp;
    kanou%=MOD;
    if(num[0]==A[i]){
      num[0]++;
      continue;
    }
    else if(num[1]==A[i]){
       num[1]++;
      continue;
    }
    else if(num[2]==A[i]){
      num[2]++;
      continue;
    }
    else{
      eend=1;
      break;
    }
  }

  if(eend==1){
    cout<<0<<endl;
  }
  else{
    cout<<kanou%MOD<<endl;
  }

}

/*


ll funn(ll now,ll a0,ll a1,ll a2){
  if(now>=N){
    return a0+a1+a2;
  }
  ll sum=0;
  if(A[now]==a0){
    sum+=funn(now+1,a0+1,a1,a2)%MOD;
     cout<<sum<<endl;
    sum%=MOD;
  }
  if(A[now]==a1){
    sum+=funn(now+1,a0,a1+1,a2)%MOD;
     cout<<sum<<endl;
      sum%=MOD;
  }
  if(A[now]==a2){
    sum+=funn(now+1,a0,a1,a2+1)%MOD;
     cout<<sum<<endl;
      sum%=MOD;
  }
  if(A[now]!=a0||A[now]!=a1||A[now]!=a2){
    enddd=1;
     funn(now+1000000000000,a0,a1,a2);
  }
  //cout<<sum<<endl;
  return sum%MOD;
}
*/

Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include<sstream>

using namespace std;
#define ll long long
#define mod 1000000007


int main() {
    string s;
    cin >> s;
    if (s.find("RRR") < 10) {
        cout << "3\n";
    } else if (s.find("RR") < 10) {
        cout << "2\n";
    } else if (s.find("R") < 10) {
        cout << "1\n";
    } else {
        cout << 0 << "\n";
    }
}

Measured memory_bytes: 3564
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <functional>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    cout << N * N * N << endl;

    return 0;
}


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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;

const ll mod = 1e9+7;
const int maxn = 1e6 + 5;





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

    int n;
    cin>>n;
    bool win = false;
    for (int i=0; i<n; i++) {
	int x;
	cin>>x;
	if (x%2==1) win=true;
    }

    cout<<(win ? "first\n" : "second\n");
    
    
    return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>

int main() {
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; i++) {
		std::cin >> a[i];
	}
	std::vector<long long> pathL(n + 1, 0), cycL(n + 1, 0);
	for(int i = 0; i < n; i++) {
		long long pathCost = a[i] % 2 == 1 ? a[i] : a[i] - 1;
		pathL[i+1] = std::max(pathCost + pathL[i], 0LL);
		long long cycCost = a[i] % 2 == 0 ? a[i] : a[i] - 1;
		if(a[i] == 0) {
			cycCost = -2;
		}
		cycL[i+1] = std::max(cycCost + cycL[i], 0LL);
		pathL[i+1] = std::max(pathCost + cycL[i], pathL[i+1]);
	}
	std::vector<long long> pathR(n + 1, 0), cycR(n + 1, 0);
	for(int i = n-1; i >= 0; i--) {
		long long pathCost = a[i] % 2 == 1 ? a[i] : a[i] - 1;
		pathR[i] = std::max(pathCost + pathR[i+1], 0LL);
		long long cycCost = a[i] % 2 == 0 ? a[i] : a[i] - 1;
		if(a[i] == 0) {
			cycCost = -2;
		}
		cycR[i] = std::max(cycCost + cycR[i+1], 0LL);
		pathR[i] = std::max(pathCost + cycR[i+1], pathR[i]);
	}
	long long ans = 0;
	for(int i = 0; i <= n; i++) {
		//std::cout << "on " << i << " got path (" << pathL[i] << ", " << pathR[i] << ") and cyc (" << cycL[i] << ", " << cycR[i] << ")\n";
		ans = std::max(ans, pathL[i] + cycR[i]);
		ans = std::max(ans, pathR[i] + cycL[i]);
		ans = std::max(ans, cycL[i] + cycR[i]);
		//std::cout << "got ans " << ans << '\n';
	}
	ans = -ans;
	for(int i = 0; i < n; i++) {
		ans += a[i];
	}
	std::cout << ans << '\n';
}

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

int N, M, Q;

vector<int> p,q;

int train[501][501], c[501][501];

int sub_solve(int k, int l){
	int ans=0;
	for(int i=k;i<=l;i++){
		ans += c[i][l];
		//cout << ans << endl;
	}
	return ans;
}


void solve(){
	int count;

	for(int i=1;i<=N;i++){
		count = 0;
		for(int j=i;j<=N;j++){
			count += train[i][j];
			c[i][j] = count;
		}
	}

	for(int i=0;i<Q;i++){
		cout << sub_solve(p[i],q[i]) << endl;
	}
}


int main(){
	cin >> N >> M >> Q;
	int l,r;
	for(int i=0;i<M;i++){
		cin >> l >> r;
		train[l][r]++;
	}

	p.resize(Q); q.resize(Q);

	for(int i=0;i<Q;i++){
		cin >> p[i] >> q[i];
	}


	solve();

	

	return 0;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll MOD = 1000000007;
ll dp[60][60][3000];
int main() {
  int N, A;
  cin >> N >> A;
  vector<int> x(N);
  REP(i, N) cin >> x[i];
  // REP(i, 60) dp[i][0][0] = 1;
  dp[0][0][0] = 1;
  REP(i, N) REP(j, N) REP(k, 2600) {
    if (dp[i][j][k] != 0) {
      dp[i + 1][j + 1][k + x[i]] += dp[i][j][k];
      dp[i + 1][j][k] += dp[i][j][k];
    }
  }
  ll ans = 0;
  REP(i, 3000) REP(j, N + 1) {
    if (j == 0) continue;
    if (i % j == 0) {
      if (i / j == A) ans += dp[N][j][i];
    }
  }
  cout << ans << endl;
}

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int MOD = 1000000007;
const int INF = 2147483647;

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

//myfuncs
//素数判定
template<class T> inline T isPrime(T x) {
    bool ret = true;
    if (x < 2) {
        ret = false;
    }
    for (LL i = 2; i <= sqrt(x); i++) {
        if (x%i == 0) {
            ret = false;
        }
    }
    return ret;
}

//Union FInd
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//main code

int main(int argc, char const* argv[])
{
    LL h,w;
    cin >> h >> w;
    LL smax = 0, smin = INF, ans = INF;

    for (LL i = 1; i < h; i++) {
        smax = max(i*w,(h-i)*((w+1)/2));
        smin = min(i*w,(h-i)*(w/2));
        ans = min(ans,smax - smin);
        smax = max(i*w,((h-i+1)/2)*w);
        smin = min(i*w,((h-i)/2)*w);
        ans = min(ans,smax - smin);
    }

    for (int i = 1; i < w; i++) {
        smax = max(i*h,(w-i)*((h+1)/2));
        smin = min(i*h,(w-i)*(h/2));
        ans = min(ans,smax - smin);
        smax = max(i*h,((w-i+1)/2)*h);
        smin = min(i*h,((w-i)/2)*h);
        ans = min(ans,smax - smin);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cstdio>
#define int long long
#define pb push_back
#define mp make_pair
#define INF 0x3f3f3f3f
#define Inf 1000000000000000000LL
#define F first
#define S second
using namespace std;
typedef pair<int,int>pii;
int l,r;
int ans=3000;
signed main(){
	cin>>l>>r;
	for(int i=l;i<=r;i++){
		if(i%2019==0){
			puts("0");
			return 0;
		}
	}
	for(int i=l;i<=r;i++)
		for(int j=l;j<=r;j++)if(i!=j){
			ans=min(ans,i*j%2019);
		}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;

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

typedef pair<ll, pii> pipii;

int main() {
	int n, m;
	while(cin >> n >> m, n) {
		if(m == 0) {
			cout << 1 << endl;
			continue;
		}
		vector<pipii> v(m);
		rep(i, m) {
			cin >> v[i].first >> v[i].second.first >> v[i].second.second;
		}
		sort( v.begin(), v.end() );
		set<int> infe;
		infe.insert(1);
		rep(i, m) {
			pii p = v[i].second;
			if( infe.find(p.first) != infe.end() ) {
				infe.insert(p.second);
			}
		}
		cout << infe.size() << endl;
	}

	return 0;
}

Measured memory_bytes: 2396
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
#include <queue>
#include <tuple>
#include <cmath>
#include <bitset>
#include <cctype>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
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<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
    auto val = table(args...);
    return vector<decltype(val)>(n, move(val));
}
const ll INF = 1e10;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
const ll MAX = 200005;
vector<vector<ll>> Next(string s){
    int n = s.size();
    vector<vector<ll>> res(n+1,vector<ll>(26,n));
    for(int i = n-1;i >= 0;i--){
        rep(j,26){
            res[i][j] = res[i+1][j];
        }
        res[i][s[i]-'a'] = i;
    }
    return res;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s,t = "";
    cin >> s;
    ll n = s.size();
    rep(i,n){
        t += s[n-i-1];
    }
    vector<vector<ll>> ns = Next(s);
    vector<vector<ll>> nt = Next(t);
    vector<vector<ll>> dp(n+1,vector<ll>(n+1,0));
    dp[0][0] = 1;
    rep(i,n){
        rep(j,n){
            rep(k,26){
                if(ns[i][k] + nt[j][k] + 2 > n) continue;
                dp[ns[i][k]+1][nt[j][k]+1] += dp[i][j];
                dp[ns[i][k]+1][nt[j][k]+1] %= MOD;
            }
        }
    }
    ll ans = 0,c;
    rep(i,n+1){
        rep(j,n+1){
            c = 1;
            if (i+j > n) continue;
            rep(k,26){
                if(ns[i][k]+1+j <= n) c++;
            }
            ans += c*dp[i][j]%MOD;
            ans %= MOD;
        }
    }
    PRINT((ans+MOD-1)%MOD);
}



Measured memory_bytes: 35360
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#define _USE_MATH_DEFINES
using namespace std;
typedef long long ll;
double pi = 3.141592653589793;
ll mod = 1000000007;

int main() {
    priority_queue<int> Q;
    string word;
    while (true) {
        cin >> word;
        if (word == "insert") {
            int i;
            cin >> i;
            Q.push(i);
        } else if (word == "extract") {
            cout << Q.top() << endl;
            Q.pop();
        } else {
            break;
        }
    }
}



Measured memory_bytes: 6900
#include<stdio.h>
const int SIZE=100;
int data[SIZE];
int sp=0;
int size(){
  return sp;
}
int empty(){
  return sp<=0;
}
int top(){
  return data[sp-1];
}
void pop(){
  sp--;
}
void push(int v){
  data[sp]=v;
  sp++;
}
int main(){
  int n,k;
  while(scanf("%d",&n)!=EOF){
    if(n==0){
      printf("%d\n",top());
      pop();
    }else{
      push(n);
    }
  }
  return 0;
}

Measured memory_bytes: 2640
a, b, t = input().split()
a = int(a)
b = int(b)
t = int(t)
ans = 0
for i in range(t + 1):
    if i > t:
        break
    elif i >= a and i % a == 0:
        ans += b
    else:
        ans += 0
print(ans)

Measured memory_bytes: 3060
import java.io.FileNotFoundException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		new Main().run();
	}

	void run() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] cnt = new int[1_000_00 + 2];
		for (int i = 0; i < n; ++i) {
			a[i] = sc.nextInt();
			++cnt[a[i]];
		}

		int ans = 0;
		for (int i = 0; i <= 100000; ++i) {
			ans = Math.max(ans, cnt[i] + (i > 0 ? cnt[i - 1] : 0) + cnt[i + 1]);
		}
		System.out.println(ans);
	}

	static void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}


Measured memory_bytes: 60552
fn main(){
    let mut vec: Vec<i32> = Vec::with_capacity(5);

    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let ws = s.split_whitespace();

    for v in ws {
        let t: i32 = v.parse().unwrap();
        vec.push(t);
    }

    for (i, v) in vec.iter().enumerate() {
        if *v == 0 {
            println!("{}", i + 1);
        }
    }
}

Measured memory_bytes: 2104
N = int(input())
Ai = list(map(int, input().split()))
Ai.sort(reverse=True)

score_a = 0
score_b = 0
for i in range(N):
    if i % 2 == 0:
        score_a += Ai[i]
    else:
        score_b += Ai[i]
print(score_a - score_b)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#pragma gcc optimize("ofast")
using namespace std;

#define ll long long //data types used often, but you don't want to type them time by time
#define ull unsigned long long
#define ui unsigned int
#define mod 1000000007
#define us unsigned short
#define IOS ios_base::sync_with_stdio(0); //to synchronize the input of cin and scanf
#define INF LONG_MAX
#define PI 3.1415926535897932384626
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define rep(x,j,n)for(int x=j;x<n;x++)
typedef vector<pair<ll,ll>> vpi;
typedef vector<ll> vi;
typedef vector<vi> vvi;

ll modexp(ll a,ll b,ll m)
{
    ll r=1;
    a=a%m;
    while(b>0)
    {
        if(b&1){r=(r*a)%m;}
        b=b>>1;
        a=(a*a)%m;
    }
    return r%m;
}


int main(){
    ll n,m; cin>>n>>m;
    vector<vector<char> >arr(n+1,vector<char>(m+1));
    rep(i,0,n)rep(j,0,m)cin>>arr[i+1][j+1];
    vvi dp(n+1,vi(m+1,0));
    rep(i,1,n+1)
    {
        rep(j,1,m+1)
        {
            if(i==1&&j==1)dp[i][j] = 1;
            else if(arr[i][j] == '.')
            {
                dp[i][j] = (dp[i-1][j]%mod + dp[i][j-1]%mod)%mod;
            }
        }
    }
    cout<<dp[n][m]%mod<<endl;
    return 0;
}


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

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

const int mod=1000000000+7;

int addm(int& a,int b) {return (a+=b)<mod?a:a-=mod;}

template<class T,class U> bool smin(T& a,U b) {return a>b?(a=b,1):0;}
template<class T,class U> bool smax(T& a,U b) {return a<b?(a=b,1):0;}

int N;
int a[100000];

int solve() {
	int nodd=0,sum=0,oi;
	bool s1=0;
	for (int i=0;i<N;i++) {
		sum^=a[i]-1;
		if (a[i]&1) nodd++,oi=i;
		if (a[i]==1) s1=1;
	}
	if (nodd>1 || (sum&1) || s1) return sum&1;

	a[oi]--;
	int g=0;
	for (int i=0;i<N;i++) g=__gcd(g,a[i]);
	for (int i=0;i<N;i++) a[i]/=g;

	return !solve();
}

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

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

	if ((N==1 && a[0]>1) || (N>1 && solve())) cout << "First\n";
	else cout << "Second\n";

}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int,int>
#define ff first
#define ss second
#define boost ios::sync_with_stdio(false);cin.tie(nullptr)
#include "string"
	

int32_t main() {
	boost;
	int n;
	cin >> n;
	int ans[n+1] = {0};
	for(int i = 1;i * i <= n; i++) {
		for(int j = 1; j *j <= n; j++) {
			for(int k = 1; k* k <= n; k++) {
				int tt = i*i + j*j + k*k + i*j + i*k + j*k;
				if(tt <= n)
					ans[tt]++;
				else break;
			}
		}
	}
	for(int i=1;i<=n;i++)
		cout << ans[i] << endl;
}



Measured memory_bytes: 3684
import java.util.Scanner;

/**
 * Double Factorial
 */
public class Main {

    public static void main(String[] args) throws Exception {
        try (Scanner sc = new Scanner(System.in)) {
            long N = sc.nextLong();

            if (N % 2 == 1) {
                System.out.println(0);
                return;
            }

            long c = 0;
            long x = 10;
            while (true) {
                if (N / x == 0) {
                    break;
                }

                c += N / x;
                x *= 5;
            }

            System.out.println(c);
        }
    }

}


Measured memory_bytes: 21204
a, b, c = map(int, input().split())
if a == 5 and b == 5 and c == 7:
    print('YES')
elif a == 5 and b == 7 and c == 5:
    print('YES')
elif a == 7 and b == 5 and c == 5:
    print('YES')

else:
    print('NO')


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

using namespace std;
using ll = long long;

int main()
{
    ll N, K, Q;
    cin >> N >> K >> Q;

    vector<ll> A(Q), P(N, K-Q);
    for(int i=0; i<Q; ++i){cin >> A[i]; A[i]--;}

    for(int i=0; i<Q; ++i) ++P[A[i]];

    for(int i=0; i<N; ++i){
        if(P[i] > 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 2176
/*
    Author: aksayushx
*/
#include<bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
#define mp make_pair
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef long double ld;

/*
void compute()
{
	fac[0]=1;
	for(ll i=1;i<=10000;i++)
	fac[i]=(i*fac[i-1])%mod;
}
ll power(ll x, ll y)  
{  
    ll res = 1; 
    x = x % mod;
    while (y > 0)  
    {  
        if (y & 1)  
            res = (res*x) % mod;  
        y = y>>1; 
        x = (x*x) % mod;  
    }  
    return res;  
} 
ll modInverse(ll n) 
{ 
    return power(n, mod-2); 
}
ll nCr(ll n,ll r) 
{ 
    if (r == 0) 
        return 1; 
    return (fac[n] * modInverse(fac[r]) % mod * modInverse(fac[n - r]) % mod) % mod; 
}*/ 
int n;
vector<ll> a;
vector<vector<vector<ll>>> dp;
ll optimal(int lx,int rx,int turn)
{
    if(dp[lx][rx][turn]!=-1)
    return dp[lx][rx][turn];
    if(lx>rx)
    return 0;
    if(lx==rx)
    {
        if(turn)
        return a[lx];
        else
        return -1*a[lx];
    }
    if(turn)
    {
        ll x=a[lx]+optimal(lx+1,rx,false);
        ll y=a[rx]+optimal(lx,rx-1,false);
        dp[lx][rx][1]=max(x,y);
        return dp[lx][rx][1];
    }
    else
    {
        ll x=optimal(lx+1,rx,true)-a[lx];
        ll y=optimal(lx,rx-1,true)-a[rx];
        dp[lx][rx][0]=min(x,y);
        return dp[lx][rx][0];
    }
}
void aksayushx()
{
    cin>>n;
    a.resize(n);
    for(int i=0;i<n;i++)
    cin>>a[i];
    dp.assign(n,vector<vector<ll>>(n,vector<ll>(2,-1)));
    ll score=optimal(0,n-1,1);
    cout<<score;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int test=1;
    //cin>>test;
    while(test--)
        aksayushx();
    return 0;
}


Measured memory_bytes: 495824
#include<stdio.h>

int main(void)
{
	int w, h, x, y, r;
	scanf("%d %d %d %d %d", &w, &h, &x, &y, &r);

	if (0<x && x<=100 && 0<y && y<=100)
	{
		if (r<=x && r<=y && r<=h-y && r<=w-x)
		{
			printf("Yes\n");
		}
		else
		{
			printf("No\n");
		}
	}
	else
	{
		printf("No\n");
	}

	return 0;
}

Measured memory_bytes: 584
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  int cnt[4] = {0, 0, 0, 0};
  for (int i = 0; i < N; i++) {
    string S;
    cin >> S;
    if (S == "AC") {
      cnt[0]++;
    } else if (S == "WA") {
      cnt[1]++;
    } else if (S == "TLE") {
      cnt[2]++;
    } else if (S == "RE") {
      cnt[3]++;
    }
  }
  cout << "AC x " << cnt[0] << endl;
  cout << "WA x " << cnt[1] << endl;
  cout << "TLE x " << cnt[2] << endl;
  cout << "RE x " << cnt[3] << endl;
  return 0;
}


Measured memory_bytes: 3656
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int X = Integer.parseInt(sc.next());
		int t = Integer.parseInt(sc.next());
		sc.close();

		if(X - t >= 0) {
			System.out.println(X - t);
		}else {
			System.out.println(0);
		}

	}
}


Measured memory_bytes: 21844
//Trie + comp
//CF2016qB-E
#include<stdio.h>
#include<string.h>

#define lk 32

typedef struct{
  int lp;
  int par;
  int bkw;
  int chi[lk];
}trn;

int trc=0;
trn trie[524288];

void trinit(){
  int i;
  trie[0].lp=0;
  trie[0].par=-1;
  trie[0].bkw=-1;
  for(i=0;i<lk;i++){
    trie[0].chi[i]=-1;
  }
  trc=1;
}

void crn(int x,int pt){
  int i;
  trie[x].chi[pt]=trc;
  trie[trc].par=x;
  trie[trc].bkw=pt;
  trie[trc].lp=trie[x].lp+1;
  for(i=0;i<lk;i++){
    trie[trc].chi[i]=-1;
  }
  trc++;
}

int run(char s[]){
  int i,l=strlen(s),v=0,c;
  for(i=0;i<=l;i++){
    if(i!=l){c=s[i]-'`';}
    else{c=0;}
    if(trie[v].chi[c]==-1){
      crn(v,c);
    }
    v=trie[v].chi[c];
  }
  return v;
}

void tricomp(){
  int i,j,c,tac;
  for(i=0;i<trc;i++){
    if(trie[i].par==-1){continue;}
    c=0;
    for(j=0;j<lk;j++){
      if(trie[i].chi[j]!=-1){tac=trie[i].chi[j];c++;}
    }
    if(c==1){
      trie[trie[i].par].chi[trie[i].bkw]=tac;
      trie[tac].par=trie[i].par;
      trie[tac].bkw=trie[i].bkw;
    }
  }
}

int main(){
  trinit();
  int n,i,j,w[524288]={0},id[524288]={0},q,k,res,v,vp,f;
  char s[524288],p[32];
  scanf("%d",&n);
  for(i=1;i<=n;i++){
    scanf("%s",s);
    id[i]=run(s);
    w[id[i]]++;
  }
  tricomp();
  for(i=trc-1;i>=0;i--){
    if(trie[i].par==-1){continue;}
    w[trie[i].par]+=w[i];
  }
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d%s",&k,p);
    res=0;
    v=id[k];
    while(trie[v].par!=-1){
      vp=trie[v].par;
      f=0;
      if(trie[v].bkw==0){f=1;}
      for(j=0;j<26;j++){
        if(f==1 && trie[vp].chi[p[j]-'`']!=-1){
          res+=w[trie[vp].chi[p[j]-'`']];
        }
        if(trie[v].bkw==p[j]-'`'){f=1;}
      }
      v=vp;
    }
    printf("%d\n",n-res);
  }
}


Measured memory_bytes: 60160
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define INF 1000000000
#define mod 1000000007
using ll=long long;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

void solve(){
    int n;cin>>n;
    int g[n][n];// g[i][j] : (i, j)から外に向かって移動するときにいる人の数（自分含め）
    int v[n][n];
    rep(i,n)rep(j,n)g[i][j]=1+min({i,j,n-1-i,n-1-j}),v[i][j]=1;

    int ans=0;
    rep(_,n*n){
        int p;cin>>p;p--;

        priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,
            greater<pair<int,pair<int,int>>>> que;

        {
            int i=p/n,j=p%n;
            int res=INF;
            rep(k,4){
                int ni=i+dx[k],nj=j+dy[k];
                if(0<=ni and ni<n and 0<=nj and nj<n) chmin(res,g[ni][nj]);
                else res=0;
            }
            ans+=res;
            g[i][j]=res;
            que.push({res,{i,j}});
            v[i][j]=0;
        }

        while(!que.empty()){
            auto pp=que.top();que.pop();
            auto pos=pp.second;
            auto cost=pp.first;
            int i=pos.first,j=pos.second;
            rep(k,4){
                int ni=i+dx[k],nj=j+dy[k];
                if(0<=ni and ni<n and 0<=nj and nj<n){
                    if(chmin(g[ni][nj],cost+v[ni][nj])) que.push({g[ni][nj],{ni,nj}});
                }
            }
        }
        // cout<<"ans : "<<ans<<endl;
        // rep(i,n){
        //     rep(j,n){
        //         cout<<g[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
    }
    cout<<ans<<endl;
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    solve();
    return 0;
}


Measured memory_bytes: 5624
#include <stdio.h>

int main () {

    int x, y, temp ;
	
    scanf ("%d %d", &x, &y ) ;
    
    if ( y > x ) { 
	temp = x ;
	x = y ;
        y = temp ;
    }
	while  ( x % y != 0 ) {

	x = x % y ;
 	if ( y > x ) {
		temp = x ;
		x = y ;
		y = temp ; 
        }
    }
 
    printf ("%d\n" , y) ;
    return 0 ;
}

Measured memory_bytes: 592
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {

	int R,C,N;
	ArrayList<Point> edge;

	private void solve() {

		Scanner io = new Scanner(System.in);
		R = io.nextInt();
		C = io.nextInt();
		N = io.nextInt();
		
		edge = new ArrayList<Point>();

		for(int i=0;i<N;i++){
			int x1 = io.nextInt();
			int y1 = io.nextInt();
			int x2 = io.nextInt();
			int y2 = io.nextInt();
			
			int p1 = trans(x1,y1);
			int p2 = trans(x2,y2);
			if(p1==-1||p2 ==-1) continue;
			
			edge.add(new Point(p1,i));
			edge.add(new Point(p2,i));
			
		}
		
		Collections.sort(edge);
		
		LinkedList<Point> stack = new LinkedList<Point>();
		for(int i=0;i<edge.size();i++){
			if(stack.isEmpty()){
				stack.push(edge.get(i));
			}else{
				if(stack.peek().id==edge.get(i).id){
					stack.pop();
				}else{
					stack.push(edge.get(i));
				}
			}
		}

		System.out.println((stack.isEmpty())?"YES":"NO");
	}
	
	private int trans(int x,int y){
		if(y==0){
			return x;
		}else if(x==R){
			return R+y;
		}else if(y==C){
			return 2*R+C-x;
		}else if(x==0){
			return 2*R+2*C-y;
		}else{
			return -1;
		}
	}
	
	public static void main(String[] args) {
		new Main().solve();
	}
}

class Point implements Comparable<Point>{
	int pos;
	int id;
	// equals method must be changed !! 
	
	public Point(int x,int y){
		this.pos = x;
		this.id = y;
	}

	@Override
	public boolean equals(Object o){
		return pos == ((Point)o).pos &&
			   id == ((Point)o).id;
	}
	@Override
	public int compareTo(Point o) {
		return Integer.compare(this.pos,o.pos);
	}
	@Override
	public int hashCode(){
		return Integer.hashCode(pos*id);
	}
}


Measured memory_bytes: 109140
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long int;
vector<int> f(vector<int>& a) {
  int n = a.size();
  vector<int> res(n);
  rep(i,n) res[i] = a[i]^a[(i+1)%n];
  return res;
}
template<typename T>
struct MP {
  int n;
  T t;
  vector<int> a;
  MP() {}
  MP(const T& t): t(t) {
    n = t.size();
    a = vector<int>(n+1);
    a[0] = -1;
    int j = -1;
    for (int i = 0; i < n; ++i) {
      while (j != -1 && t[j] != t[i]) j = a[j];
      j++;
      a[i+1] = j;
    }
  }
  int operator[](int i) { return a[i];}
  vector<int> findAll(const T& s) {
    vector<int> res;
    int j = 0;
    for (int i = 0; i < s.size(); ++i) {
      while (j != -1 && t[j] != s[i]) j = a[j];
      j++;
      if (j == n) {
        res.push_back(i-j+1);
        j = a[j];
      }
    }
    return res;
  }
};

int main() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  rep(i,n) scanf("%d",&a[i]);//cin >> a[i];
  rep(i,n) scanf("%d",&b[i]);//cin >> b[i];
  vector<int> xa = f(a);
  vector<int> xb = f(b);
  MP<vector<int>> mp(xa);
  xb.insert(xb.end(), xb.begin(), xb.end());
  vector<int> res = mp.findAll(xb);
  vector<int> ks;
  for (int p : res) ks.push_back(n-p);
  sort(ks.begin(), ks.end());
  for (int k : ks) {
    if (k >= n) continue;
    int x = a[k]^b[0];
    printf("%d %d\n", k, x);
  }
  return 0;
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> k >> n;
  int next;
  cin >> next;
  int _max = -1e9; 
  int sum = 0;
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    _max = max(_max, x - next);
    sum += x - next;
    next = x;
  }
  _max = max(_max, k - sum);
  cout << k - _max << '\n';  
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
void swap(int *a,int *b){
	int temp;
	temp = *a;
	*a = *b;
	*b = temp;
	return;
}
int sort(int A[],int N){
	int i,j,sw;
	sw = 0;
	unsigned short flag = 1;
	for(i = 0; flag;i++){
		flag = 0;
		for(j = N-1; j >= i+1;j--){
			if(A[j] < A[j-1]){
				swap(&A[j],&A[j-1]);
				flag = 1;
				sw++;
			}
		}
	}
	return sw;
}
int main(void){
	int R[100],r,i,sw;
	scanf("%d",&r);
	for(i = 0; i < r; i++) scanf("%d",&R[i]);
	sw = sort(R,r);
	for(i = 0; i < r; i++){
		if(i) printf(" ");
		printf("%d",R[i]);
	}
	printf("\n%d\n",sw);
	return 0;
}


Measured memory_bytes: 2100
# ALDS1_2_A.py
def bubbleSort(A: list, N: int):
    cnt = 0
    isEnd = False
    while not isEnd:
        isEnd = True
        for i in range(1, N):
            if A[i] < A[i-1]:
                tmp = A[i]
                A[i] = A[i-1]
                A[i-1] = tmp
                isEnd = False
                cnt += 1
    return A, cnt


N = int(input())
A = list(map(int, input().split()))
A, cnt = bubbleSort(A, N)
print(*A)
print(cnt)



Measured memory_bytes: 5608
#include <iostream>
using namespace std;
using lint = long long;
using Cut = tuple<lint, lint>;
int N;
lint arr[200'001];
lint ans = 0x3f3f3f3f3f3f3f3f;

Cut mergeCut(const Cut &l, const Cut &r) {
    lint lm, lM, rm, rM;tie(lm, lM) = l, tie(rm, rM) = r;
    return Cut(min(lm, rm), max(lM, rM));
}

Cut cutting(int b, int e) {
    lint midv = (arr[e-1] - arr[b-1])/2;
    int idx = upper_bound(arr+b, arr+e, midv + arr[b-1]) - arr - 1;
    if(idx == b-1) idx++;
    if(idx == e) idx-=2;
    lint l = abs(arr[e-1] - arr[idx] - (arr[idx] - arr[b-1]));
    lint r = abs(arr[e-1] - arr[idx+1] - (arr[idx+1] - arr[b-1]));
    if(l < r) return Cut(min(arr[e-1] - arr[idx],  arr[idx] - arr[b-1]), max(arr[e-1] - arr[idx], arr[idx] - arr[b-1]));
    else return Cut(min(arr[e-1] - arr[idx+1],  arr[idx+1] - arr[b-1]), max(arr[e-1] - arr[idx+1], arr[idx+1] - arr[b-1]));
}

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

    cin>>N;
    for(int i = 1; i <= N; i++) cin>>arr[i];
    for(int i = 1; i <= N; i++) arr[i] += arr[i-1];

    for(int cut = 3; cut <= N-1; cut++) {
        lint m, M;tie(m, M) = mergeCut(cutting(1, cut), cutting(cut, N+1));
        ans = min(ans, M - m);
    }

    cout<<ans<<'\n';

    return 0;
}

Measured memory_bytes: 1792