akhauriyash/Code-Regression huggingface dataset:
// Enjoy your stay.

#include <bits/stdc++.h>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define mt make_tuple
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)(x).size())

using namespace std;

typedef istringstream iss;
typedef long long ll;
typedef pair<ll,ll> pi;
typedef stringstream sst;
typedef vector<ll> vi;

int N,E,T,W[333],G[1010],C[1010],S[1010][11];
int d[333],rest[1010];
vi to[333];
int used[333];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>N>>E>>T,T--;
	rep(i,N)cin>>W[i];
	rep(i,E){
		cin>>G[i]>>C[i],G[i]--;
		rep(j,C[i]){
			cin>>S[i][j],S[i][j]--;
			to[S[i][j]].pb(i);
		}
	}

	rep(i,N){
		if(W[i] == 1) d[i] = 1;
		else d[i] = INF;
	}
	rep(i,E){
		rest[i] = C[i];
	}
	rep(_,N){
		int cur = -1, best = INF;
		rep(i,N)if(!used[i] && d[i] < best){
			cur = i;
			best = d[i];
		}
		if(cur == T){
			return cout<<d[cur]<<endl,0;
		}
		if(cur == -1){
			return cout<<-1<<endl,0;
		}

		used[cur] = 1;
		rep(i,sz(to[cur])){
			int T = to[cur][i];
			rest[T]--;
			if(rest[T] == 0){
				vi cost;
				rep(j,C[T]){
					cost.pb(d[S[T][j]]);
				}
				sort(cost.begin(),cost.end(),greater<int>());
				int c = 0;
				rep(j,sz(cost)){
					c = max(c, (int)cost[j] + j);
				}
				d[G[T]] = min(d[G[T]],c);
			}
		}
	}
}

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

typedef long long ll; 
typedef pair<int,int > pp;

 
#define sz(x) (int)x.size() 
#define PI acos(-1)
int const N=5e5;
int  mod = 998244353,oo = 1e9;
ll OO = 3e18;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int k;
	string s;
	cin>>s>>k;
	if(k==1){
		int cnt=0;
		for(int i=0;i<sz(s);i++){
			int j=i;
			while(j<sz(s)&&s[j]==s[i])j++;
			cnt+= (j-i)/2;
			i=j-1;
		}
		cout<<cnt;
	}else{
		if(sz(s)==1)cout<<k/2;
		else{
			ll cnt=0;
			if(s[0]!=s.back()){
				for(int i=0;i<sz(s);i++){
					int j=i;
					while(j<sz(s)&&s[j]==s[i])j++;
					cnt+= ((j-i)/2) *1LL* k;
					i=j-1;
				}
			}else{
				int c1=0;
				while(c1<sz(s)&&s[c1]==s[0])c1++;
				if(c1==sz(s)){
					cnt = k*1LL*sz(s) / 2;
				}else{
					int c2 = 0;
					while(c2<sz(s)&&s[sz(s)-c2-1]==s[0])c2++;
					cnt = c1/2+c2/2+(c1+c2)/2 * 1LL*(k-1);
					for(int j=c1;j<sz(s)-c2;j++){
						int u=j;
						while(s[u]==s[j])u++;
						cnt += ((u-j)/2) * 1LL * k;
						j=u-1;
					}
				}
			}
			cout<<cnt<<endl;
		}
	}
	return 0;
}



Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
#define sim template < class c
#define int long long
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << '\n'; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
typedef tree< pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
const ll MOD = 1e9 + 7 ;
const ll N = 2e5 + 10 ;
const ll INF = 1e18 + 10 ;
signed main(){
    fastio
    int x ; 
    cin >> x ;
    for(int a = -1000; a <= 1000; a++){
        int A = a * a * a * a * a - x ; 
        int L = -1000, R = 1000 ;
        debug() << imie(a) imie(A) ; 
        int ans = -1 ; 
        while(L <= R){
            int mid = L + (R - L) / 2 ;
            int t = mid * mid * mid * mid * mid; 
            if ( t == A ){
                ans = mid ; 
                break ; 
            }
            else if ( t > A ){
                R = mid - 1;
            }
            else L = mid + 1;
        }
        if ( ans != -1 ){
            cout << a << ' ' << ans << endl;
            return 0 ;
        }
    }
    return 0; 
}

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


int main() {
  string s1, s2, s3;
  cin >> s1 >> s2 >> s3;
  char a, b, c;
  a = s1[0]-32;
  b = s2[0]-32;
  c = s3[0]-32;
  cout << a << b << c << endl;
  return 0;
}

Measured memory_bytes: 256
import copy
a = [[0 for i in range(100)] for j in range(100)]
b = copy.deepcopy(a)
n, m, l = map(int, input().split())
for i in range(n):
    a[i][:m] = map(int, input().split())
for i in range(m):
    b[i][:l] = map(int, input().split())
for i in range(n):
    for j in range(l):
        c = 0
        for k in range(m):
            c += a[i][k] * b[k][j]
        print(c, end='')
        if j < l - 1:
            print(' ', end='')
        else:
            print()

Measured memory_bytes: 9196
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

using namespace std;
using namespace __gnu_pbds;

void debug_out() { cerr << endl; }
template<class T> ostream& prnt(ostream& out, T v) { out << v.size() << '\n'; for(auto e : v) out << e << ' '; return out;}
template<class T> ostream& operator<<(ostream& out, vector <T> v) { return prnt(out, v); }
template<class T> ostream& operator<<(ostream& out, set <T> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, map <T1, T2> v) { return prnt(out, v); }
template<class T1, class T2> ostream& operator<<(ostream& out, pair<T1, T2> p) { return out << '(' << p.st << ' ' << p.nd << ')'; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << H; debug_out(T...);}

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


template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef cc_hash_table<int, int, hash<int > > ht;


#define int long long 
#define  st first
#define  nd second

const int M = 1e8;
const int  maxn = 1e5+5;
const int  inf =  1e16;


int32_t main(){

  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  int n ;  
  cin >> n ;
  int a[n] ; 
  for(int i = 0 ; i < n  ;i++){
    cin >> a[i] ; 
  }
  int dp[n]={0} ; 
  dp[n-1] = 0 ;
  int ans = 0 ;  
  for(int i = n-2 ; i>=0 ; i--){
     if(a[i]>=a[i+1]){
       dp[i] = dp[i+1]+1;
     }
     ans = max(ans,dp[i]);
  }
  cout << ans ;


}



Measured memory_bytes: 5136
n = int(input())
t = [list(input().split()) for _ in range(n)]
BY = 380000
ans = 0

for i in range(n):
    if t[i][1] == 'JPY':
        ans += int(t[i][0])
    else:
        ans += float(t[i][0])*BY

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ll long long
#define P pair<int,int>
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(),v.end()
#define pb push_back
#define eb emplace_back
template<class T>void chmax(T &a,T b){if(a<b)a=b;}
template<class T>void chmin(T &a,T b){if(a>b)a=b;}
constexpr int INF=1000000000000000000;
constexpr int mod=1000000007;
constexpr double eps=1e-8;
const double pi=acos(-1);
int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
int Random(int mi,int ma){
    random_device rnd;
    mt19937 mt(rnd());//32bit
    //[mi,ma]
    uniform_int_distribution<int>engine(mi,ma);
    return engine(mt);
}
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}
bool prime(int a){
    if(a==1)return false;
    for(int i=2;i*i<=a;i++){
        if(a%i==0)return false;
    }
    return true;
}
int modpow(int a,int b){
    if(b==0)return 1;
    if(b%2)return modpow(a,b-1)*a%mod;
    int memo=modpow(a,b/2);
    return memo*memo%mod;
}
vector<int>kaijo,invkaijo;
void init_fact(int n){
    kaijo.resize(n+1);
    invkaijo.resize(n+1);
    kaijo[0]=1;
    for(int i=1;i<=n;i++){
        kaijo[i]=kaijo[i-1]*i;
        kaijo[i]%=mod;
    }
    rep(i,n+1)invkaijo[i]=modpow(kaijo[i],mod-2);
}
int comb(int a,int b){
    if(a<b)return 0;
    if(a<0||b<0)return 0;
    return kaijo[a]*invkaijo[a-b]%mod*invkaijo[b]%mod;
}
int inv(int x){
    x=modpow(x,mod-2);
    return x;
}

signed main(){
    cin.tie(0);ios::sync_with_stdio(false);
    int x;
    cin>>x;
    cout<<1-x<<endl;
    return 0;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define ll long long
#define REP(i, n) for (int i=0; i<n; ++i)
#define print(x) cout << x << endl;

using namespace std;

void solve() {
    string S;
    cin >> S;

    int ans = 0;
    string target = "AGCT";
    for (int i=0; i<S.length(); ++i) {
        for (int j=i+1; j<S.length()+1; ++j) {
            int left = i;
            int right = j;
            bool ok = true;
            for (int x=i; x<right; ++x) {
                if (find(target.begin(), target.end(), S[x]) == target.end()) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                ans = max(ans, right - left);
            }
        }
    }
    print(ans);
}

int main() {

    solve();
    return 0;
}


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

using namespace std;

using ll = long long;

int main() {
   ios_base::sync_with_stdio(false);
   int n;
   ll a, b, c, d;
   cin >> n >> a >> b >> c >> d;
   for (int i = 0; i < n; ++i) {
      ll l = a + c * i - d * (n - 1 - i);
      ll r = a + d * i - c * (n - 1 - i);
      if (l <= b && b <= r) {
         puts("YES");
         return 0;
      }
   }
   puts("NO");
   return 0;
}


Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

"""
・累積和の到達地点集合ごとに見る
・type1：X未満で終わる
・type2：X+1以上2X未満
・type3：2X以上、これはXが奇数の場合のみ
"""

MOD = 998244353

N,X = map(int,read().split())

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = N+N+100
fact,fact_inv = make_fact(U,MOD)
combN = fact[N] * fact_inv[:N+1] % MOD * fact_inv[N::-1] % MOD

def F1(N,X):
    # X未満で終わる場合
    def mult(P,Q):
        # 多項式の積
        dP = len(P) - 1
        dQ = len(Q) - 1
        if dP < dQ:
            dP,dQ = dQ,dP
            P,Q = Q,P
        R = np.zeros(dP+dQ+1,np.int64)
        for n in range(dQ+1):
            R[n:n+dP+1] += Q[n] * P % MOD
        R %= MOD
        return R[:X]
    def power(P,n):
        if n == 0:
            return np.array([1],dtype=np.int64)
        Q = power(P,n//2)
        Q = mult(Q,Q)
        return mult(P,Q) if n&1 else Q
    P = np.array([1,1,1],np.int64)
    Q = power(P,N)
    return Q.sum() % MOD

def F2(N,X):
    x = np.zeros(N+1,np.int64)
    # X+1+2nで終わる場合
    for n in range(X):
        m = (X-1) - (2+2*n)
        if m < 0:
            break
        # 2+2n -> X-1に含まれる2の回数ごとに
        two = np.arange(m//2+1,dtype=np.int64)
        one = m - 2*two
        coef = fact[one+two] * fact_inv[one] % MOD * fact_inv[two] % MOD
        rest = N-one-two-(2*n+2)
        ind = rest>=0
        rest = rest[ind]; coef = coef[ind]
        x[rest] += coef
    x %= MOD
    return (x * combN % MOD).sum() % MOD

def F3(N,X):
    # 2X以上の偶数。Xは奇数で、+2を連打している場合
    if X%2 == 0:
        return 0
    if X > N:
        return 0
    n = N-X+1
    return combN[:n].sum() % MOD

answer = (F1(N,X) + F2(N,X) + F3(N,X)) % MOD
print(answer)

Measured memory_bytes: 18812
import java.util.*;
 public class Main {
	public static void main(String[] args){
      Scanner sc = new Scanner(System.in);

     int N = sc.nextInt();
     int M = sc.nextInt(); 


      System.out.print(N * (N-1) / 2 + M * (M-1) / 2 );
   }
 }

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

#define endl '\n'
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

typedef long long llong;
typedef pair<int, int> pii;

void solve() {

	int n, x;
	cin >> n >> x;

	int m = 2 * n - 1;

	if (x == 1 || x == m) {

		cout << "No";

	} else {


		list <int> ans;

		ans.pb(x - 1);
		ans.pb(x);
		ans.pb(x + 1);

		int add = 0;
		int limit = (m - 3) / 2;

		for (int i = 1; i <= m; i++) {

			if ( i < x - 1 || i > x + 1) {

				if (add < limit) ans.push_front(i);
				else ans.push_back(i);

				add++;

			}

		}

		cout << "Yes" << endl;
		for (int val : ans) cout << val << endl;


	}

	
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);

	#ifdef LOCAL
		ifstream in("in");
		cin.rdbuf(in.rdbuf());
	#endif

	solve();

	return 0;

}

Measured memory_bytes: 7808
#include<cstdio>
using namespace std;
long long a,b,c,k,Ans;
int main(){
	scanf("%lld%lld%lld%lld",&a,&b,&c,&k);
	if(a>b&&a>c) Ans=b+c+a*((long long)1<<k);else
	if(b>a&&b>c) Ans=a+c+b*((long long)1<<k);else Ans=a+b+c*((long long)1<<k);
	printf("%lld",Ans);
	return 0;
} 

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

 
int main() {
  string s,t;
  cin>>s>>t;
  
  int cnt=0;
  for(int i=0;i<s.size();i++){
    if(s.at(i)==t.at(i))
      cnt++;
  }
  
  cout<<cnt<<endl;
  
  return 0;
}

Measured memory_bytes: 256
N,K,Q = map(int,input().split())
score = [K-Q]*N
A = [0]*Q
for i in range(Q):
    A[i] = int(input())

for a in A:
    score[a-1] += 1

for i in map(lambda x:['No','Yes'][x>0],score):
    print(i)

Measured memory_bytes: 10428
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
int N,Q;
string S;
#define MAXQ 100001
int l[MAXQ],r[MAXQ];
int main(){
    cin >> N >> Q;
    cin >> S;
    rep(i,Q){
        cin >> l[i] >> r[i];
        l[i]--,r[i]--;
    }
    int ans[MAXQ];
    fill(ans,ans+N,0);
    rep(i,N-1){
        if(S[i]=='A'&&S[i+1]=='C'){
            ans[i+1]++;
        }
        ans[i+1]+=ans[i];
    }
    rep(i,Q){
        cout << ans[r[i]]-ans[l[i]] << endl;
    }
    return 0;

}

Measured memory_bytes: 2176
/* 
 * Project: AtCoder Beginners Contest 064 A - RGB Cards
 * Author: toms74209200 <https://github.com/toms74209200>
 *
 * Created on 2020/04/04
 * Copyright (c) 2020 toms74209200
 * 
 * This software is released under the MIT License.
 * http://opensource.org/licenses/mit-license.php
 */
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int r;
int g;
int b;

void solve() {

int number = 0;
int rem = 0;

number = 100*r + 10*g + b;
rem = number & 3;

    if (rem == 0)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

int main() {

    cin >> r >> g >> b;

    solve();

}


Measured memory_bytes: 256
A=[[0,0],[1,0],[0,1],[1,1]]
B=[[0,0],[0,1],[0,2],[0,3]]
C=[[0,0],[1,0],[2,0],[3,0]]
D=[[0,0],[-1,1],[0,1],[-1,2]]
E=[[0,0],[1,0],[1,1],[2,1]]
F=[[0,0],[0,1],[1,1],[1,2]]
G=[[0,0],[1,0],[-1,1],[0,1]]
humen=[]
gentenx="0"
genteny="0"
kigou=[]
ans=[]
s=""
while(1):
    
    
    if len(humen)>=8:
        for y in range(0,8):#y
            for x in range(0,8):#x
                if humen[y][x]=="1" and gentenx=="0" and genteny=="0":#位置記憶
                    gentenx=x
                    genteny=y
                    kigou.append([0,0])
                elif humen[y][x]=="1" :
                    kigou.append([x-gentenx,y-genteny])
        if A==kigou:ans.append("A")
        if B==kigou:ans.append("B")
        if C==kigou:ans.append("C")
        if D==kigou:ans.append("D")
        if E==kigou:ans.append("E")
        if F==kigou:ans.append("F")
        if G==kigou:ans.append("G")
        kigou=[]
        humen=[]
        gentenx="0"
        genteny="0"
    try: s=str(input(""))
    except:break
    if s!="":humen.append(list(s))

for i in ans:
    print(i)



Measured memory_bytes: 5568
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
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
from operator import mul
from functools import reduce


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 1000000007


l = S()
pop_cnt = 0
ans = 0
for i in range(len(l)):
    if l[i] == '1':
        ans = (ans + pow(2, pop_cnt, mod) * pow(3, len(l) - i - 1, mod)) % mod
        pop_cnt += 1
ans = (ans + pow(2, pop_cnt, mod)) % mod


print(ans)

Measured memory_bytes: 42096
while True:
    n = int(input())
    if n == 0 :
        break
    ice = list([0] * 10)
    for i in range(n) :
        a = int(input())
        ice[a] += 1
    
    for i in range(10) :
        if ice[i] > 0 :
            for j in range(ice[i]):
                print("*", sep="", end="")
            print("")
        else :
            print("-")


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

bool isok(long n){
    string s=to_string(n);
    for (int i = 0; i < s.length()-1; ++i) {
        if(s[i]+1!=s[i+1])return false;
    }
    return true;
}

int main() {
    int n;
    cin>>n;
    vector<long> a(n);
    for (int i = 0; i < n; ++i) {
        cin>>a[i];
    }
    long ans=-1;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if(i==j)continue;
            if(isok(a[i]*a[j]))ans=max(a[i]*a[j],ans);
        }
    }
    cout<<ans<<endl;
    return 0;
}


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

int main() {
  int X, Y;
  cin >> X >> Y;
  
  vector<int> vec(13);
  vec = { 0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1 };
  
  if( vec.at(X) == vec.at(Y) ){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
    
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<cmath>
 
#define rep(i,x) for(int i=0;i<(int)(x);i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
 
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e10
 
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; }
typedef long long ll;
typedef std::pair<ll, ll> P;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
 
using namespace std;

int main()
{
    ll n, k;
    cin >> n >> k;
    ll ans = -1;
    vector<ll> v(n);
    vector<ll> d;
    vector<ll> rr(n);
    ll sum = 0;

    rep(i, n){
        cin >> v[i];
        sum += v[i];
    }
    for(ll i=1; i*i<=sum; i++){
        if(sum%i==0){
            d.push_back(i);
            if(i*i != sum) d.push_back(sum/i);
        }
    }
    sort(all(d));

    rep(i, d.size()){
        ll ss = 0;
        rep(j, n){
            rr[j] = v[j] % d[i]; 
            ss += rr[j];
        }
        sort(all(rr));
        ll pp = 0;
        ll aa = INF;
        
        rep(j, rr.size()){
            pp += rr[j];
            if(ss >= d[i]*(rr.size()-1-j)){
                aa = pp;
                break;
            }
        }
        if(aa <= k){
            ans = d[i];
        }
    }
    cout << ans;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int MAXN = 101;
int n;
int a[MAXN] , s[MAXN];
int main(){
	cin >> n;
	for(int i = 1 ; i <= n ; ++ i){
		cin >> a[i];
		s[a[i]] ++;
	}
	sort(a + 1 , a + n + 1);
	int root = a[1] , sum = 1;
	for(int i = 2 ; i <= n ; ++ i)
		if(a[i] == a[1])
			sum ++;
		else
			break;
	if(sum >= 3){
		cout << "Impossible" << endl;
		return 0;
	}
	else if(sum == 2){
		if(a[1] == 1){
			if(n == 2)
				cout << "Possible" << endl;
			else
				cout << "Impossible" << endl;
		}
		else{
			for(int i = a[1] + 1 ; i < 2 * a[1] ; ++ i)
				if(s[i] == 0){
					cout << "Impossible" << endl;
					return 0;
				}
				else
					s[i] --;
			for(int i = a[1] + 1 ; i < 2 * a[1] ; ++ i)
				if(s[i] == 0){
					cout << "Impossible" << endl;
					return 0;
				}
				else
					s[i] = 0;
			for(int i = a[1] + 1 ; i <= n ; ++ i)
				if(s[i] != 0){
					cout << "Impossible" << endl;
					return 0;
				}
			cout << "Possible" << endl;
		}
	}
	else{
		for(int i = a[1] + 1 ; i <= 2 * a[1] ; ++ i)
			if(s[i] == 0){
				cout << "Impossible" << endl;
				return 0;
			}
			else
				s[i] --;
		for(int i = a[1] + 1 ; i <= 2 * a[1] ; ++ i)
			if(s[i] == 0){
				cout << "Impossible" << endl;
				return 0;
			}
			else
				s[i] --;
		for(int i = 2 * a[1] + 1 ; i <= n ; ++ i)
			if(s[i] != 0){
				cout << "Impossible" << endl;
				return 0;
			}
		cout << "Possible" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))

res=b[a[0]-1]
last=a[0]
for i in range(1,n):
	if last+1==a[i]:
		res+=b[a[i]-1]+c[a[i]-2]
	else:
		res+=b[a[i]-1]
	last=a[i]
print(res)

Measured memory_bytes: 38384
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
li = []
cnt = 0
for i in range(n):
    a = list(map(int,input().split()))
    for j in range(m):
        li.append(a[j] * b[j])
    if sum(li) + c > 0:
        cnt =  cnt + 1
    li = []
print(cnt)

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

int main(void){
    string s;
    cin >> s;
    vector<long long> a(100010, 0),c(100010, 0);
    vector<int> b;
    long long ans = 0, wa = 1000000007;
    long long cnt = 0;
    long long isAinLeft = 0, hatena = 1, isCinLeft = 0;
    for(int i=0;i<s.size();++i){
        if(s[i]=='A'){
            isAinLeft = 1;
            a[i+1] = a[i] + hatena;
        }else if(s[i]=='?'){
            long long tmp = hatena;
            if(isAinLeft){
                hatena *= 3;
                hatena %= wa;
            }else{
                isAinLeft = 1;
                hatena = 3;
            }
            a[i+1] = a[i]*3 + tmp;
        }else{
            a[i+1] = a[i];
        }
        a[i+1] %= wa;
    }
    for(int i=0;i<s.size();++i){
        if(s[i]=='B' || s[i]=='?'){
            b.push_back(i);
        }
    }
    hatena = 1;
    for(int i=s.size()-1;i>0;--i){
        if(s[i]=='C'){
            isCinLeft = 1;
            c[i-1] = c[i] + hatena;
        }else if(s[i]=='?'){
            long long tmp = hatena;
            if(isCinLeft){
                hatena *= 3;
                hatena %= wa;
            }else{
                isCinLeft = 1;
                hatena = 3;
            }
            c[i-1] = c[i]*3 + tmp;
        }else{
            c[i-1] = c[i];
        }
        c[i-1] %= wa;
    }
    for(int i=0;i<b.size();++i){
        ans += (a[b[i]]*c[b[i]])%wa;
        ans %= wa;
    }
    if(ans<0) ans += wa;
    cout << ans%wa << endl;
}

Measured memory_bytes: 2556
//HSI
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
using namespace std;
int main(){
    int N,M;
    cin >> N >> M;
    
    int a = 1;
    for(int i=0; i<M; i++){
       a *= 2;
    }

    long long ans = 1900*a*M + 100*a*(N-M);
    cout << ans << endl;
    return 0;
    
}

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

int a[100000];
int b[100000];
int c[100000];
int N;
int ans[3][100000];

int max(int x,int y){
  if(x<y) return y;
  else return x;
}

int main(){
  scanf("%d",&N);
  for(int i=0;i<N;i++){
    scanf("%d",&a[i]);
    scanf("%d",&b[i]);
    scanf("%d",&c[i]);
  }
  //printf("%d\n",N);

  ans[0][0]=a[0];
  ans[1][0]=b[0];
  ans[2][0]=c[0];
  for(int i=1;i<N;i++){
    ans[0][i] = max(ans[1][i-1],ans[2][i-1])+a[i];
    ans[1][i] = max(ans[2][i-1],ans[0][i-1])+b[i];
    ans[2][i] = max(ans[0][i-1],ans[1][i-1])+c[i];
    //printf("%d,%d,%d\n",ans[0][i], ans[1][i],ans[2][i]);
  }
  printf("%d\n",max(max(ans[0][N-1],ans[1][N-1]),ans[2][N-1]));
}


Measured memory_bytes: 2560
#include<iostream>
#include<vector>
#include<functional>
#include<climits>
#include<algorithm>
#include<iomanip>
using namespace std;

template<typename T>
struct Seg{
private:
    vector<T> node;
    int n;
    function<T(T,T)> f;
    T def;

public:
    Seg(int siz, T d, function<T(T,T)> f) : def(d), f(f) {
        n = 1;
        while(n < siz)  n *= 2;
        node.resize(2*n-1, def);
    }
    Seg(vector<T> v, T d, function<T(T,T)> f) : def(d), f(f){
        n = 1;
        while(n < v.size())  n *= 2;
        node.resize(2*n-1);
        for(int i = 0; i < v.size(); i++)   node[n-1+i] = v[i];
        for(int i = n-2; i >= 0; i--)   node[i] = f(node[2*i+1], node[2*i+2]);
    }

    void update(int x, T val){
        x += n-1;
        node[x] = val; /* ! */
        while(x){
            x = (x-1)/2;
            node[x] = f(node[2*x+1], node[2*x+2]);
        }
    }

    T query(int a, int b, int k=0, int l=0, int r=-1){
        if(r < 0)   r = n;
        if(b <= l || r <= a)    return def;
        if(a <= l && r <= b)    return node[k];
        T lx = query(a, b, 2*k+1, l, (l+r)/2);
        T rx = query(a, b, 2*k+2, (l+r)/2, r);
        return f(lx, rx);
    }
};

int main(){
    int n;
    cin >> n;
    vector<int> xs, t(n), a(n);
    for(int i = 0; i < n; i++){
        cin >> t[i] >> a[i];
        xs.push_back(t[i]);
    }
    int q;
    cin >> q;
    vector<int> l(q), r(q);
    for(int i = 0; i < q; i++){
        cin >> l[i] >> r[i];
        xs.push_back(l[i]);
        xs.push_back(r[i]);
    }
    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(),xs.end()),xs.end());
    int siz = xs.size();
    auto f = [&](int x)->int{
        return lower_bound(xs.begin(),xs.end(),x)-xs.begin();
    };
    Seg<double> seg(siz, 1.0, [](double x, double y){return x*y;});
    for(int i = 0; i < n; i++){
        seg.update(f(t[i]), (100-10*a[i])/100.0);
    }
    for(int i = 0; i < q; i++){
        cout << fixed << setprecision(12) << 1000000000*seg.query(f(l[i]), f(r[i])) << endl;
    }
    return 0;
}


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

class Graph {
    int N;
    vector<vector<int>> edge;
    vector<vector<int>> dp;

public:
    Graph(int N) : N(N), edge(N) {}
    void add(int a, int b) {
        edge[a].emplace_back(b);
        edge[b].emplace_back(a);
    }
    int dfs(int i, int state) {
        if (state == (1 << N) - 1) {
            return 1;
        }
        int res = 0;
        for (auto &j : edge[i]) {
            if (!(state >> j & 1)) {
                res += dfs(j, state | (1 << j));
            }
        }
        return res;
    }
    int ans() {
        return dfs(0, 1);
    }
};

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

    int N, M;
    cin >> N >> M;
    Graph graph(N);
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        graph.add(a, b);
    }
    cout << graph.ans() << endl;

    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
#define ull unsigned long long
#define rep(i,n,N) for(ll i=n;i<=N;++i)
#define rap(i,n,N) for(int i=n;i>=N;--i)
#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
//#define ff fi.fi
//#define fs fi.se
#define sf se.fi
#define ss se.se
#define lc (id<<1)
#define rc ((id<<1)|1)
#define db(x) cerr << ">>>>>> " << #x << " -> " << x << endl
#define nani(x) cerr <<  "Line " << __LINE__ << ": " << #x << " is " << x << endl
#define all(x) x.begin(),x.end()
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define plll pair<ll,pll>
#define piii pair<int,pii>
#define piiii pair<pii,pii>
#define psi pair<string,int>
#define endl '\n'
const int MAX = 5e5+5;
const ll MAX2 = 11;
const ll MOD = 1000000007;
const ll MOD2 = 1000005329;
const ll INF = 2e18;
const int dr[]={1,0,-1,0,1,1,-1,-1,0};
const int dc[]={0,1,0,-1,1,-1,1,-1,0};
const double pi = acos(-1);
const double EPS = 1e-9;
const int block = 2000;

ll rem,spd,tim,zpd,zrem;

int main(){
//	cout<<fixed<<setprecision(10);
//    freopen("input.txt", "r", stdin);
//	freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>rem;
    if(!rem)return cout<<"0\n",0;
    spd = 1;
    while(1){
    	++tim;
    	rem-=spd;
    	if(!rem)break;
    	//cek 3x
    	zpd = spd*3;
    	zrem = rem;
    	while(zpd!=1)zrem-=zpd, zpd/=3;
    	if(zrem>=0){
    		spd*=3;
    		continue;
		}
		//cek normal
		zpd = spd;
    	zrem = rem;
    	while(zpd!=1)zrem-=zpd, zpd/=3;
		if(zrem>=0)continue;
		spd/=3;
	}
	cout<<tim<<endl;
    return 0;
}



Measured memory_bytes: 3204
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll>P;
ll p[200020][2];
ll r[200020][2];
ll root(ll x, ll yojo) {
	return p[x][yojo] == x ? x : p[x][yojo] = root(p[x][yojo],yojo);
}
void unite(ll x, ll y,ll yojo) {
	x = root(x, yojo);
	y = root(y, yojo);
	if (x == y)return;
	if (r[x][yojo] < r[y][yojo])p[x][yojo] = y;
	else {
		p[y][yojo] = x;
		if (r[x][yojo] == r[y][yojo])r[x][yojo]++;
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	ll n, k, l, x, y;
	cin >> n >> k >> l;
	for (int i = 1; i <= n; i++) {
		p[i][0] = p[i][1] = i;
	}
	for (int i = 0; i < k; i++) {
		cin >> x >> y;
		unite(x, y, 0);
	}
	for (int i = 0; i < l; i++) {
		cin >> x >> y;
		unite(x, y, 1);
	}
	map<P, ll>mp;
	ll a, b;
	for (int i = 1; i <= n; i++) {
		a = root(i, 0);
		b = root(i, 1);
		mp[make_pair(a, b)]++;
	}
	for (int i = 1; i <= n; i++) {
		a = root(i, 0);
		b = root(i, 1);
		cout << mp[make_pair(a, b)];
		if (i == n)cout << endl;
		else cout << ' ';
	}
	return 0;
}


Measured memory_bytes: 16384
#include <bits/stdc++.h>
#define For(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define Fordown(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;

bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}

void file() {
#ifdef zjp_shadow
	freopen ("C.in", "r", stdin);
	freopen ("C.out", "w", stdout);
#endif
}

int n, k;
const int N = 10;
bool dis[N];
void input() {
	n = read();
	k = read();
	For (i, 1, k) {
		int val = read();
		dis[val] = true;
	}
}

inline bool check (int x) {
	for (; x; x /= 10)
		if (dis[x % 10] ) return false;
	return true ;
}

void solve() {
	for (; !check(n); ++n) ;
}

void output() {
	printf ("%d\n", n);
}

int main () {
	file() ;
	input() ;
	solve() ;
	output() ;
    return 0;
}


Measured memory_bytes: 256
use proconio::input;
use proconio::marker::{Chars};
use std::iter::Iterator;
use std::collections::HashSet;

fn main() {
    input! {
    s: Chars,
    t: Chars,
    }

    let mut ans = true;
    for i in 0..s.len() {
        if s[i] != t[i] {
            ans = false;
        } 

        if(t.len() != s.len() + 1){
            ans = false;
        }

    }

    if ans {
        println!("Yes");

    }else{

        println!("No");
    }

}


Measured memory_bytes: 2108
#include<stdio.h>
#include<string.h>

int main()
{
  char arr[1000];
  char text[100];
  char str[1000];
  char test[1000];
  int n;
  int n1, n2;
  int t;
  int t2 = 0;
  scanf("%s", arr);
  scanf("%d", &n);
  for(int i = 0; i < n; i++)
    {
      scanf("%s %d %d", text, &n1, &n2);
      if(strcmp(text, "replace") == 0)
	{
	  scanf("%s", str);
	  for(int j = n1; j <= n2; j++)
	    {
	      arr[j] = str[t2];
	      t2++;
	    }
	  t2 = 0;
	}
      if(strcmp(text, "reverse") == 0)
	{
	  strcpy(test, arr);
	  t = n2;
	  for(int j = n1; j <= n2; j++)
	    {
	      arr[j] = test[t];
	      t--;
	    }
	}
      if(strcmp(text, "print") == 0)
	{
	  for(int i = n1; i <= n2; i++)
	    {
	      printf("%c", arr[i]);
	    }
	  printf("\n");
	}
    }
}


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

using namespace std;
int main() {
  int n;
  cin >> n;
  int num[n];
  for (int i = 0; i < n; i++) {
    cin >> num[i];
  }

  int diffCnt = 0;
  for (int i = 0; i < n; i++) {
    if (i + 1 != num[i]) {
      diffCnt++;
    }
  }
  if (diffCnt <= 2) {
    cout << "YES" << endl;
    return 0;
  }

  cout << "NO" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define lli long long int
#include<climits>
#include<unordered_map>
#include<algorithm>
#include<bitset>
#include<map>
#define pb push_back
using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int>arr(n+1);
    for(int i=1;i<=n;i++)  cin>>arr[i];
    int k =1;
    int b =0;
    for(int i=1;i<=n;i++)
    {
        if(arr[i]==k)
        {
            k++;
        }
        else b++;
    }
    
    if(b!=n) cout<<b<<endl;
    else cout<<-1<<endl;
}



Measured memory_bytes: 4048
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;



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

	int n, i, j, k;
	cin >> n;
	bool valid = false;
	for (i = 1; i <= 9; i++) {
		if ((n % i == 0)  && (n / i <= 9)) 
			valid = true;
	}

	if (valid) cout << "Yes\n";
	else cout << "No\n";


	return 0;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
class Main
{
    public static void main(String[] args) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if(x >= 30)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 35596
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    ll a,b;
    cin >> a >> b;
    if(abs(a-b)>=2){
        cout << 0 << endl;
        return 0;
    }
    ll ans = 1;
    ll now = a;
    rep(i,a){
        ans *= now;
        ans %= mod;
        now--;
    }
    now = b;
    rep(i,b){
        ans *= now;
        ans %= mod;
        now--;
    }
    if(a==b) ans *= 2;
    ans %= mod;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  char number[4];
  scanf("%s", number);
  if((number[0] == number[1] && number[1] == number[2]) || (number[1] == number[2] && number[2] == number[3])) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }
  return 0;
}


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

int main(){
	string str;
	int q, l;
	deque<char> deq;
	deque<char> :: iterator it;
	cin >> str >> q;
	l = str.size();
	for(int i = 0; i < l; i++)
		deq.push_back(str[i]);
	int flag = 0;
	int t, c;
	char s;
	for(int i = 0; i < q; i++){
		scanf("%d",&t);
		if(t == 1) flag = !flag;
		else if(t == 2){
			scanf("%d %c",&c,&s);
			if(!flag){
				if(c == 1)
					deq.push_front(s);
				else if(c == 2)
					deq.push_back(s);
			}
			else {
				if(c == 2)
					deq.push_front(s);
				else if(c == 1)
					deq.push_back(s);				
			}
		}
	}
	if(!flag){
		for(it = deq.begin(); it != deq.end(); it++)
			printf("%c", *it);		
	}
	else{
		for(it = deq.end() - 1; it != deq.begin() - 1; it--)
			printf("%c", *it);			
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 896
#include<iostream>
using namespace std;
int main(){
    int m,d;
    cin >> m >> d;
    int ans = 0;
    for(int i=4;i<=m;i++){
        for(int j=22;j<=d;j++){
            if((j/10)*(j%10) == i&&(j/10) >= 2 && (j%10)>=2){
                ans ++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
  
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL
  
Node root;
  
Node treeMinimum(Node x){
  
  
}
  
Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key){
    return u;
  }
  if(k<u->key){
    return treeSearch(u->left,k);
  }
  else{
    return treeSearch(u->right,k);
  }
}
  
Node treeSuccessor(Node x){
  
  
}
  
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  
  
  
}
  
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
  
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while(x!=NIL){
    y=x;
    if(z->key<x->key){
      x=x->left;
    }
    else{
      x=x->right;
    }
  }
  z->parent=y;
    if(y==NIL){
      root=z;
    }
    else if(z->key<y->key){
      y->left=z;
    }
    else{
      y->right=z;
    }
  }
  
  
void inorder(Node u){
  if (u->left != NIL){
    inorder(u->left);
  }
  printf(" %d", u->key);
  if (u->right != NIL){
    inorder(u->right);
  }
}
void preorder(Node u){
  printf(" %d",u->key);
  if (u->left != NIL){
    preorder(u->left);
  }
  if (u->right != NIL){
    preorder(u->right);
  }
}
  
  
int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }
  
  return 0;
}

Measured memory_bytes: 19360
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int mod = 1e9+7;
const int maxn = 2e5+5;
ll n,m;
int a[maxn];
int b[maxn];
int dp[maxn];
int main() {
	ll h;
	cin>>h>>n;
	for(int i=0;i<maxn;i++)
		dp[i] = INF;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		cin>>b[i];
	}
	dp[0] = 0; 
	for(int i=1;i<=n;i++)
		for(int j=1;j<=h;j++){
			if(j>=a[i]) 
				dp[j] = min(dp[j],dp[j-a[i]]+b[i]);
			else 
				dp[j] = min(dp[j],b[i]);
		}
	cout<<dp[h]<<endl;
    return 0;
}



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

int gcd(int p, int q) {
  if (p % q == 0)
    return q;
  
  return gcd(q, p % q);
}

int main() {
  int k;
  cin >> k;
  
  int sum = 0;
  for (int a = 1; a <= k; a++) {
     for (int b = 1; b <= k; b++) {
       for (int c = 1; c <= k; c++) {
         sum += gcd(gcd(a, b), c);
       }
     }
  }
  
  cout << sum << endl;

  return 0;
}

Measured memory_bytes: 3600
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <cctype>

using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<long, long>;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
#define rep(i, n) for(int i = 0; i<n; i++)
#define rep_s(i, start, n) for(int i= start;  i<n; i++)
#define rep_down(i, n) for(int i = n-1; i>=0; i--)
#define rep_down_s(i, n, start) for(int i = n-1; i>=start; i--)
#define ALL(a) (a).begin(), (a).end()
#define ALL_str(a) (a).cbegin(), (a).cend()

string alphabet_upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet_lower  = "abcdefghijklmnopqrstuvwxyz";
string numbers = "0123456789";

/*
using edge = struct {int to; ll cost;};
vector<edge> tree[limit];
ll depth[limit];

void dfs(int v, int p, ll d){
  depth[v] = d;
  //cout <<"v: " << v << endl;
  for (auto &e: tree[v]){
    //cout << "e.to: " << e.to << endl;
    if (e.to == p) continue;
    dfs(e.to, v, d+e.cost);
  }
}
*/
int keta_sum(int num){
  int dig, sum = 0;
  while(num){
    dig = num % 10;
    sum = sum + dig;
    num = num / 10;
  }
  return sum;
}

ll binary_search(ll left_key, ll border, ll low, ll high) {
     // 配列 a の左端と右端
    ll mid = (low+high)/2;
    while (high > low+1) {
       mid = (low+high)/2;
        if (left_key*mid>border) high = mid;
        else if (left_key*mid<border) low = mid;
        else {
          mid =mid-1;
          break;
        }
    }
    return mid;
}

bool IsPrime(ll a){
  ll b = sqrt(a);
  b++;
  while(b-->=2){
    if (a%b==0) return false;
  }
  return true;
}

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;
    }
};

int main(void){
  ll N, M, A, B, C, D, K,W, H, Q, X, Y;
  ll ans;
  string S, T;
  cin >> N >> M;
  ll p[N+1];
  
  rep_s(i,1, N+1) cin>>p[i];
  ll x, y;
  UnionFind tree(N+1);
  rep(i, M){
    cin >> x >> y;
    tree.unite(x, y);
    /*
    if (tree.same(x, y)) cout << "true" << endl;
    else cout << "false" << endl;
    */
  }
  ans = 0;
  rep_s(i,1, N+1){
    if (tree.same(i, p[i])) ans++;
  }
  cout << ans << endl;

}


Measured memory_bytes: 1408
# include <bits/stdc++.h>
 
using namespace std;
 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
    ~debug() { cerr << endl; }
    eni(!=) cerr << boolalpha << i; ris; }
    eni(==) ris << range(begin(i), end(i)); }
    sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
    }
    sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
    }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
# define forn(i, n) for (ll i = 0; i < int(n); i++)
# define rfor(n, i) for (ll i = (n - 1); i >= 0; --i)
# define all(V) V.begin(), V.end()
# define rall(V) V.rbegin(), V.rend()
# define len(V) (int)V.size()
# define ll long long
# define ld long double
# define ff first
# define ss second
# define pb push_back
# define mp make_pair
# define endl '\n'
# define M_PI 3.14159265358979323846
 
void solve()
{
        int n; cin >> n;
        vector<pair<int, int>> a(n);
        forn(i, n)
        {
                int x; cin >> x;
                a[i] = {x, i + 1};
        }       
        sort(all(a));
        forn(i, n) cout << a[i].second << ' ';
}
 
int main()
{
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        solve();
}

Measured memory_bytes: 1664
#include<iostream>
#include <cstring>
#define MAX 105
using namespace std;
int width,height;
int ans = 0;
int dx[] = {-1,0,0,1};
int dy[] = {0,-1,1,0};
char ar[MAX][MAX];
void dfs(int row,int col,char s)
{
	ar[row][col] = '!';
	for(int i = 0;i<4;i++)
	{
		int nx = col+dx[i],ny = row+dy[i];
		if(nx>=0&&nx<width&&ny>=0&&ny<height&&ar[ny][nx]==s)
		{
			dfs(ny,nx,s);
		}
	}
}
int main()
{
	while(cin >> height >> width&&width)
	{
		for(int i = 0;i<height;i++)
			cin >> ar[i];
		for(int i = 0;i<height;i++)
		{
			for(int j = 0;j<width;j++)
				if(strchr("*@#",ar[i][j]))
					{	
						ans++;
						dfs(i,j,ar[i][j]);
					}
		}
		cout << ans <<endl;
		ans = 0;
	}
	return 0;
 } 

Measured memory_bytes: 1644