akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
using namespace std;
 
 
int main(){
int N;
int M;
cin >> N;
vector<string> B(N);
for(int i = 0; i < N; i++){
    cin >> B[i];
}
cin >> M;
vector<string> R(M);
for(int i = 0; i < M; i++){
    cin >> R[i];
}
 
int coin = 0;
 
for(int i = 0; i < N; i++){
    int c = 0;
    for(int j = 0; j < N; j++){
        if(B[i] == B[j])c++;
    }
    for(int j = 0; j < M; j++){
        if(B[i] == R[j])c--;
    }
coin = max(coin , c);
}
 
cout << coin << endl;
}

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

long long fact(int k) {
  if (k == 0) {
    return 1;
  }

  // sum関数の中でsum関数を呼び出している
  long long f = fact(k - 1);
  return (f * k)%1000000007;
}

int main() {
	int n;
  cin >> n;
  
 cout << fact(n) << endl;




}


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

long cost[4];
long dic[3] = {2,3,5};

long dfs(long now, map<long,long> &mp){
  if(mp.count(now)) return mp.at(now);
  long ans;
  if(now > 2*1e9) ans = 2*1e18;
  else ans = now*cost[3];
  rep(i,3){
    if(now % dic[i] == 0) ans = min(ans, dfs(now/dic[i], mp) + cost[i]);
    else{
      ans = min(ans, dfs(now/dic[i], mp) + cost[i] + cost[3]*(now % dic[i]));
      ans = min(ans, dfs(now/dic[i] + 1, mp) + cost[i] + cost[3]*(dic[i] - now % dic[i]));
    }
  }
  mp[now] = ans;
  return ans;
}

void Main(){
  long n;
  cin >> n;
  rep(i,4) cin >> cost[i];
  map<long,long> mp;
  mp[0] = 0;
  mp[1] = cost[3];
  cout << dfs(n, mp) << endl;
}

int main(){
  int t;
  cin >> t;
  rep(i,t) Main();
}


Measured memory_bytes: 4468
#include <stdio.h>
#define MAX 100
#define NIL -1
#define INF 200000
#define WHITE 0
#define BLACK 2
#define GRAY 1
int n,A[MAX][MAX];
void prim(){
  int sum=0,u,v,i,d[MAX],pi[MAX],mincost;
  int color[MAX];
  for(i=0;i<n;i++){
    d[i]=INF;
    pi[i]=NIL;
    color[i]=WHITE;
  }
  d[0]=0;
  while(1){

    mincost=INF;
    u=-1;
    for(i=0;i<n;i++){
      if(color[i]!=BLACK&&d[i]<mincost){
	mincost=d[i];
	u=i;
      }
    }
    if(u==-1)break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK&&A[u][v]!=INF){
	if(A[u][v]<d[v]){
	  d[v]=A[u][v];
	  pi[v]=u;
	  color[v]=GRAY;
	}

      }
	

    }
  }
    for(i=0;i<n;i++){
      if(pi[i]!=-1)sum+=A[i][pi[i]];
    }
  
  printf("%d\n",sum);
}
int main(){
  int i,j,x;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    for(j=0;j<n;j++){
   
   scanf("%d",&A[i][j]);
   if(A[i][j]==-1)A[i][j]=INF;
	}
  }
  prim();



  return 0;
}



Measured memory_bytes: 2104
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let _n: usize = read();
    let s: Vec<char> = read::<String>().chars().collect();
    let k: usize = read();

    let ci = s[k - 1];

    for c in s {
        if ci == c {
            print!("{}", c);
        } else {
            print!("*");
        }
    }
    println!();
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
ll mod=1e9+7;

int main() {
  ll n;
  cin >> n;
  vec c(n);
  for(ll i=0;i<n;i++) {
    cin >> c[i];
  }
  vec dp(n+1);
  vec left(2e5+1,-1);
  dp[0]=1;
  for(ll i=0;i<n;i++) {
    dp[i+1]=dp[i];
    ll tc=c[i];
    if(left[tc]>-1&&left[tc]<i-1) dp[i+1]=(dp[i+1]+dp[left[tc]+1])%mod;
    left[tc]=i;
  }
  cout << dp[n] << endl;
}

Measured memory_bytes: 4992
import sys
from random import choice,randint
inp=sys.stdin.readline
out=sys.stdout.write
flsh=sys.stdout.flush
 
sys.setrecursionlimit(10**9)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]
 
def MI(): return map(int, inp().strip().split())
def LI(): return list(map(int, inp().strip().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]
def LI_(): return [int(x)-1 for x in inp().strip().split()]
def LF(): return [float(x) for x in inp().strip().split()]
def LS(): return inp().strip().split()
def I(): return int(inp().strip())
def F(): return float(inp().strip())
def S(): return inp().strip()
def pf(s): return out(s+'\n')
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def main():
    s,w=MI()
    if w>=s:
        print("unsafe")
    else:
        print("safe")

if __name__ == "__main__":
    main()

Measured memory_bytes: 9576
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#define ll long long
#define ull unsigned long long
using namespace std;

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

	ll n, w;
	cin >> n >> w;
	vector<ll> V(n);
	vector<ll> W(n);
	ll totalVal = 0;
	for (ll i = 0; i < n; i++){
		cin >> W.at(i) >> V.at(i);
		totalVal += V.at(i);
	}

	vector<ll> DP(totalVal + 1, INT32_MAX);
	//DP[i] is minimum weight needed to get a value i
	
	DP.at(0) = 0;
	for (int i = 0; i < n; i++){
		for (int j = totalVal; j >= V.at(i); j--){
			ll mn = min(DP.at(j), DP.at(j - V.at(i)) + W.at(i));
			if (mn < DP.at(j)){
				DP.at(j) = mn;
			}
		}
		int x = 5;
	}

	ll ans = 0;
	for (int i = 0; i <= totalVal; i++){
		if (DP.at(i) <= w){
			ans = i;
		}
	}

	cout << ans;
	return 0;
}


Measured memory_bytes: 1024
#include <iostream>
using namespace std;
int main(void){
    int a, b, c;
    cin >> a >> b >> c;
    if (a > b){
        int t = a;
        a = b;
        b = t;
    }
    if (b > c){
        int t = b;
        b = c;
        c = t;
    }
    if (a > b){
        int t = a;
        a = b;
        b = t;
    }
    cout << a << " " << b << " " << c << endl;
    return 0;
}

Measured memory_bytes: 1164
import java.util.*;
import java.lang.*;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int count = n;
        for (int i = 0; i <= n; i++) {
            int c = 0;
            int m = i;
            while (m > 0) {
                c += m % 6;
                m /= 6;
            }
            m = n - i;
            while (m > 0) {
                c += m % 9;
                m /= 9;
            }
            if (c < count) {
                count = c;
            }
        }
        System.out.println(count);
    }
}

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

int main() {
    // #ifndef ONLINE_JUDGE
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // #endif
    string s;
    cin>>s;
    int n = s.size();
    for(int i = 0;i < n;i++) {
        if((i+1)%2 != 0) {
            if(s[i] == 'L') {
                cout<<"No\n";
                return 0;
            }
        }
        else {
            if(s[i] == 'R') {
                cout<<"No\n";
                return 0;
            }
        }
    }
    cout<<"Yes\n";
}

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

int main() {
    int n;
    cin >> n;
    
    vector<int> x(n);
    rep(i,n) {
     cin >>x.at(i);
    }
    
    int count = 0;
    vector<int> a(8);
    
    rep(i,n) {
        if(x.at(i)<=3199){
        a.at(x.at(i)/400)++;
        }
        else{
            count++;
        }
     }
    int sum =0;
    rep(i,8) {
     if(a.at(i) >0) {
      sum++;
     }
    }
    
    if(sum >0) {
    cout << sum << ' ' << count+sum;
    } else {
     cout << 1 << ' ' << count;
    }
    
    
    }


Measured memory_bytes: 3556
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int[] a=new int[4];
		int[] b=new int[4];
		while(sc.hasNext()){
			int hit=0;
			int blow=0;
			for(int i=0;i<4;i++){
				a[i]=sc.nextInt();
			}
			for(int i=0;i<4;i++){
				b[i]=sc.nextInt();
			}
			for(int i=0;i<4;i++){
				for(int j=0;j<4;j++){
					if(a[i]==b[j]){
						if(i==j){
							hit++;
						}else{
							blow++;
						}
					}
				}
			}
			System.out.println(hit+" "+blow);
		}
	}
}

Measured memory_bytes: 18296
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=100005;
int n;
int A[MAX_N];
int rec[MAX_N];
priority_queue <int> q;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>A[i];
		rec[A[i]]++;
	}
	for(int i=1;i<MAX_N;i++)
	{
		if(rec[i])
		{
			q.push(rec[i]);
		}
	}
	while(!q.empty())
	{
		int t=q.top();
		if(t==1)break;
		q.pop();
		while(t>=3)t-=2;
		if(t>=q.top() && t==2)
		{
			t=1;
			int t2=q.top();
			q.pop();
			t2--;
			if(t2)q.push(t2);
		}
		if(t)q.push(t);
	}
	int ans=0;
	while(!q.empty())
	{
		ans+=q.top();
		q.pop();
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
    long long int N,K;
    cin >> N >> K;
    vector<long long int> H(N);
    for(int i = 0;i < N;i++) cin >> H[i];
    sort(H.begin(),H.end());
    long long int ans  = 9876543210;
    for(int i = 0;i < N-K+1;i++){
      ans = min(ans,H[i+K-1]-H[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
n=int(input())
an=[int(input()) for _ in range(5)]
m = min(an)
if m == 1:
    print(5+n-1)
elif m >= n:
    print(5)
else:
    if n%m != 0:
        print(n//min(an)+5)
    else:
        print(n//min(an)+4)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define INF 2147483647
#define inf 1000000007
#define SYOU(x) setprecision(x)
#define abs(x,y) max(x,y)-min(x,y)
#define mp make_pair
#define fi first
#define se second
using namespace std;
int i[100],u[100][5];
vector<int> ii;
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long a,b,c,d=0,e=0,f=0,g=0,h,j;
  string s;
  cin >>s;
  for(int n=0;n<s.size();n++){
    if(n%2==0) cout <<s[n];
  }
  cout<<'\n';
  return (0);
}


Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REP(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main () {

  ll N;
  cin >> N;

  // vector<ll> ans;
  // ans.push_back(0); // ans[0] = 0;
  // REP(i, 1, N) {
  //   if (i == 1) {
  //     ans.push_back(1);
  //   }
  //   else {

  //   }
  // }

  ll ans = 0;
  REP(i, 1, N+1) { // sum to ans
    string temp;
    temp = to_string(i);
    ll saijo = (ll)stoi(temp.substr(0, 1).c_str());
    ll saika = i % 10;
    ll aida = (i - saijo * pow(10, temp.length()-1) ) / 10;
    if ( (1 <= i) and (i <= 9) ) {
      ans++;
    }
    else {
      if (saika == 0) {
        // do nothing
        continue;
      }
      // cout << "i: " << i << ", (saijo, saika) = " << saijo << ", " << saika << endl;
      if (saijo > saika) {
        ll added_num = 0;
        for (int i=2; i<=(int)temp.length(); i++) { // ketasuu
          added_num = added_num + pow(10, i - 2) * 2;
        }
        // cout << "added_num: " << added_num << endl;
        ans += added_num;
      }
      else if (saijo == saika) {
        ll added_num = 0;
        for (int i=1; i<=(int)temp.length(); i++) { // ketasuu
          if (i == 1) {
            added_num = added_num + 2;
          }
          else if (i == (int)temp.length()) {
            // if i == 2, aida = 0;
            // cout << "aida: " <<  aida << endl;
            added_num = added_num + (aida+1)*2 - 1; // -1 means (12341, 12341)
          }
          else {
            added_num = added_num + pow(10, i-2)*2;
          }
        }
        // cout << "__ added_num: " << added_num << endl;
        ans += added_num;
      }
      else { // saijo < saika
        ll added_num = 0;
        for (int i=2; i<=(int)temp.length()-1; i++) { // ketasuu
          added_num = added_num + pow(10, i-2)*2;
        }
        // cout << "** added_num: " << added_num << endl;
        ans += added_num;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    A=list(map(int,input().split()))
    ans=1
    C=[0]*(n+1)
    C[0]=3
    for a in A:
        ans*=C[a]
        ans%=MOD
        C[a]-=1
        C[a+1]+=1
    print(ans)
resolve()

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

int x;
vector<int> v;

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> x;
	for(int i=1; i*i<=x; ++i){
		int t = i*i;
		v.push_back(t);
		if(i == 1) continue;
		while(t*i <= x){
			t *= i;
			v.push_back(t);
		}
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for(int i=0; i<v.size(); ++i)
		if(v[i] <= x){
			cout << v[i] << "\n";
			return 0;
		}
}

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

int main(){
    int64_t n;
    cin >> n;
  	int a,b;
    for ( a = 1 ; a <= pow(n,0.5) ; a++ ){
        if ( n % a == 0 ) b = n/a;
        a++;
    }
    int cnt = 0;
    while( b > 0 ){
            cnt++;
            b /= 10;
    }
    cout << cnt << endl;
}

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

int main() {
    int n, k; cin >> n >> k;
    vector<int> h(n, 0);

    for (int i = 0; i < n; i += 1) 
        cin >> h[i];
        
    vector<int> dp(n, 0);

    dp[0] = 0;

    for (int i = 1; i < n; i += 1) {
        dp[i] = numeric_limits<int> :: max();
        for (int delta = 1; delta <= k and i - delta >= 0; delta += 1)
            dp[i] = min(dp[i], dp[i - delta] + abs(h[i] - h[i - delta]));
    }
    
    cout << dp[n - 1] << "\n";
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int n,k;
int a[105];
bool f[100005][2],vis[100005][2];
bool DFS(int l,int pl){
	if(vis[l][pl]){
		return f[l][pl];
	}
	vis[l][pl]=1;
	bool res=0;
	for(int i=n;i>0;--i){
		if(a[i]<=l){
			res|=!DFS(l-a[i],!pl);
		}
	}
	return f[l][pl]=res;
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;++i){
		cin>>a[i];
	}
	if(DFS(k,0)){
		cout<<"First\n";
	}
	else{
		cout<<"Second\n";
	}
	return 0;
}

Measured memory_bytes: 6912
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;

int main() {
	long long int N, M;
	cin >> N >> M;
	if (2 * N - M >= 0) {
		cout << M / 2 << endl;
		return 0;
	}
	else {
		M = (M - 2 * N) / 4;
		cout << N + M << endl;
		return 0;
	}
}

Measured memory_bytes: 256
from itertools import accumulate

N, W = map(int, input().split())
wv = {}
w1 = 0
for i in range(N):
  w, v = map(int, input().split())
  if i == 0:
    w1 = w
  if w in wv:
    wv[w].append(v)
  else:
    wv[w] = [v]

for w in wv:
  wv[w].sort(reverse=True)
  wv[w] = [0] + list(accumulate(wv[w]))

w2 = w1+1; w3 = w1+2; w4 = w1+3
for w in [w1, w1+1, w1+2, w1+3]:
  if w not in wv:
    wv[w] = [0]

ans = 0
for n1 in range(len(wv[w1])):
  for n2 in range(len(wv[w2])):
    for n3 in range(len(wv[w3])):
      for n4 in range(len(wv[w4])):
        w = w1*n1 + w2*n2 + w3*n3 + w4*n4
        if w <= W:
          ans = max(ans, wv[w1][n1]+wv[w2][n2]+wv[w3][n3]+wv[w4][n4])

print(ans)

Measured memory_bytes: 42988
#include<iostream>
#include<string>

using namespace ::std;

int main(){
  string S;
  cin >> S;
  
  if(S == "Sunny") {cout << "Cloudy" << endl;}
  else if(S == "Cloudy") {cout << "Rainy" << endl;}
  else {cout << "Sunny" << endl;}
  
  return 0;
}  


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef vector<lint> LIV;
#define rep(i,n) for(int i=0;i<n;++i)
#define MAXN 100010
#define MAXM 1100000
#define all(v) v.begin(),v.end()
#define inf 2147483647
#define linf 1152921504606846976

#include "bits/stdc++.h"
using namespace std;
typedef long long lint;
typedef vector<lint> LIV;
#define rep(i,n) for(int i=0;i<n;++i)
#define MAXN 100010
#define MAXM 1100000
#define all(v) v.begin(),v.end()
#define inf 2147483647
#define linf 1152921504606846976
#define MAX_N 100010

int main(){
	lint n;cin>>n;
	lint ans=1;
	for(int i=2;i<100;++i){
		lint cur=i;
		while(cur<=n){
			cur*=i;
			if(cur<=n)ans=max(ans,cur);
		}
	}cout<<ans<<endl;
}

//sub-EOF


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


int main(void) {
	int H, W, h, w;
	cin >> H >> W >> h >> w;
	
	if ((W%w>0)||(H%h>0)) {
		cout << "Yes" << endl;
		for (int y = 1; y <= H; y++) {
			for (int x = 1; x <= W; x++) {
				if ((x%w==0) && (y%h==0)) {
					cout << -((h*w-1)*1000+1) << " ";
				} else {
					cout << 1000 << " ";
				}
			}
			cout << endl;
		}
	} else {
		cout << "No" << endl;
	}
	return 0;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#include <vector>
#include <queue>

using namespace std;
typedef long long int64;

const int P = 998244353;
const int MAXN = 3011;
int dp[MAXN];
int n, s, ans;

inline int add(int x, int y) { x += y; x -= x >= P ? P : 0; return x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline void incr(int& x,int y) { x = add(x, y); }

int main(void)
{
	cin >> n >> s;
	for (int i = 1;i <= n; ++i)
	{
		int v;
		cin >> v;
		for (int j = s - v; j >= 0; --j)
			incr(dp[j + v], dp[j]);
		incr(dp[v], i);
		incr(ans, dp[s]);
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
n,p=map(int,input().split())
flag=0;a=list(map(int,input().split()))
ans=0
for i in range(n):
  if a[i]%2!=0:
    flag=1

if flag==0 and p==0:
  ans=2**n
elif flag==0 and p==1:
  ans=0

if flag==1:
  ans=2**(n-1)
print(ans)

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

int main()
{
    ll N, K;
    cin >> N >> K;
    vector<ll> p(N);
    rep(i, N) cin >> p[i];
    sort(p.begin(), p.end());
    ll ans = 0;
    rep(i, K) ans += p[i];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
def cmpNumVal(a, b)
  if a > b
      s = 'a > b'
  elsif a < b
      s = 'a < b'
  else
      s = 'a == b'
  end
end
      
a, b = gets.chomp.split.map(&:to_i)

puts cmpNumVal(a, b)


Measured memory_bytes: 6848
#include <iostream>
#include <algorithm>
using namespace std;
int main(void){
    
    int A, B;
    int wa, sa, seki;
    int ans;
    cin >> A >> B;
    
    wa = A + B;
    sa = A - B;
    seki = A * B;
    
    if(wa > sa) ans = wa;
    else ans = sa;
    
    if(ans > seki) cout << ans << endl;
    else cout << seki << endl;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <complex>

using namespace std;
typedef complex<double> C;
typedef vector<C> VC;
typedef vector<VC> VVC;

void fft(VC &f, int n, int dir) {
	if (n == 1) return;
	VC f0, f1;
	for(int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			f0.push_back(f[i]);
		} else {
			f1.push_back(f[i]);
		}
	}
	fft(f0, n / 2, dir);
	fft(f1, n / 2, dir);
	C zeta = polar(1.0, 2 * M_PI * dir / n);
	C now = C(1.0);
	for(int i = 0; i < n; i++) {
		f[i] = f0[i % (n / 2)] + now * f1[i % (n / 2)];
		now *= zeta;
	}
}

inline int getMinimumPowerOf2(int size) {
	int n = 1;
	while(n < size) n <<= 1;
	return n;
}

void fft2d(VVC &A, int dir = 1) {
	for(int i = 0; i < A.size(); i++) {
		VC f;
		for(int j = 0; j < A[i].size(); j++) {
			f.push_back(A[i][j]);
		}
		fft(f, f.size(), dir);
		for (int j = 0; j < f.size(); j++) {
			A[i][j] = f[j];
		}
	}
	for(int j = 0; j < A[0].size(); j++) {
		VC f;
		for(int i = 0; i < A.size(); i++) {
			f.push_back(A[i][j]);
		}
		fft(f, f.size(), dir);
		for (int i = 0; i < f.size(); i++) {
			A[i][j] = f[i];
		}
	}
}

VVC comb2d(VVC A, VVC B) {
	int n = getMinimumPowerOf2(A.size() + B.size()), m = getMinimumPowerOf2(A[0].size() + B[0].size());
	A.resize(n);
	B.resize(n);
	for (int i = 0; i < A.size(); i++) {
		A[i].resize(m);
	}
	for (int i = 0; i < B.size(); i++) {
		B[i].resize(m);
	}
	fft2d(A);
	fft2d(B);
	VVC ret(n, VC(m, 0));
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			ret[i][j] = A[i][j] * B[i][j];
		}
	}
	fft2d(ret, -1);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			ret[i][j] /= n * m;
		}
	}
	return ret;
}


constexpr char chars[] = {'#', '.'};
constexpr int num_chars = sizeof(chars);

int main() {
	int N, M;
	cin >> N >> M;
	vector<string> A(N), B(M);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < M; i++) {
		cin >> B[i];
	}
	int n = getMinimumPowerOf2(N + M);
	VVC score(n, VC(n, C(0)));
	for (int c = 0; c < num_chars; c++) {
		VVC cA, cB;
		for (int i = 0; i < N; i++) {
			cA.push_back(VC());
			for (int j = 0; j < N; j++) {
				cA[i].push_back(C(A[i][j] == chars[c]));
			}
		}
		for (int i = 0; i < M; i++) {
			cB.push_back(VC());
			for (int j = M - 1; j >= 0; j--) {
				cB[i].push_back(C(B[M - i - 1][j] == chars[c]));
			}
		}
		VVC ret = comb2d(cA, cB);
		for (int i = 0; i < score.size(); i++) {
			for (int j = 0; j < score[0].size(); j++) {
				score[i][j] += ret[i][j];
			}
		}
	}
	bool flag = false;
	for (int i = 0; i < score.size(); i++) {
		for (int j = 0; j < score[0].size(); j++) {
			if ((int)(real(score[i][j]) + 0.1) == M * M) {
				flag = true;
				break;
			}
		}
		if (flag) break;
	}

	if (flag) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 1416
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())


ans = 0


def check(s: str)->bool:
    return '3' in s and '5' in s and '7' in s


def dfs(s: str)->int:
    ret = 0
    if int(s) > N:
        return 0
    else:
        if check(s):
            ret += 1
        r3 = dfs(s+"3")
        r5 = dfs(s+"5")
        r7 = dfs(s+"7")

        ret += r3+r5+r7
    return ret


print(dfs("0"))


Measured memory_bytes: 3060
while True:
    L = int(input())
    if L == 0:
        break
    
    flag = True
    ans = -1
    d = 0
    for i in range(12):
        M,N = [int(i) for i in input().split()]
        d = d + M - N
        if d >= L and flag:
            ans = i+1
            flag = False
    
    if ans >= 0:
        print(ans)
    else:
        print("NA")



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

signed main() {

    int A,B,C;
    cin >> A >> B >> C;
    if(C-(A-B)<0) {
        cout << 0 << endl;
    }
    else{
        cout << C-(A-B) << endl;
    }
    return 0;
}

Measured memory_bytes: 3608
#include<iostream>

using namespace std;

int main(void)
{
	int N,i,j,tmp,ans=0;

	cin >> N;
	
	for(i=1;i<=N;i++)
	{
		tmp=i;
		j=0;

		while(tmp>=1)
		{
			tmp=tmp/10;

			j++;
		}
		if(j%2==1)
			ans=ans+1;
	}

	cout << ans << endl;

	return 0;
}


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

int main(){
  int h1,m1,h2,m2,k;
  cin>>h1>>m1>>h2>>m2>>k;
  int x=h1*60+m1;
  int y=h2*60+m2;
  cout<<y-x-k;
}


Measured memory_bytes: 3592
#include<stdio.h>
#include<string.h>
int main(){
  char s[100000];
  int i;
  scanf("%s",s);
  for(i=97;i<124;i++){
    if(strchr(s,i)==0) break;
  }
  if(i==123)puts("None");
  else printf("%c",i);
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
    int k, x, y, n, sum = 0;

    cin >> n >> k >> x >> y;
    if(n>k)
    {
    for (int i = 0; i < k; i++)
    {
        sum += x;
    }
    for (int i = 0; n - k > i; i++)
    {
        sum += y;
    }
    }
    else{
    for (int i = 0; i < n; i++)
    {
        sum += x;
    }
    }
    cout << sum << endl;

    return 0;
}


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

int main(void)
{
  char A[200];
  int h,i,j,m,n;
  char t;

  scanf("%s",A);
  n=strlen(A);
  while (A[0]!='-'){
    scanf("%d",&m);
    for (i=0;i<m;i++){
      scanf("%d",&h);
      while(h-->0){
        t=A[0];
        for (j=1;j<n;j++){
          A[j-1]=A[j];
        }
        A[n-1]=t;
      }
    }

    for (i=0;i<n;i++)
      printf("%c",A[i]);
    printf("\n");
    scanf("%s",A);
    n=strlen(A);
  }

  return 0;
}

Measured memory_bytes: 568
#include <iostream>
#include <string.h>
#include <string>
using namespace std;


void b_i18n(void) {
	string s;
	cin >> s;
	int word_len = s.size()-2;
	string s_out = s[0] + to_string(word_len) + s[s.size() - 1];
	cout << s_out << endl;

}

int main()
{
	b_i18n();
    return 0;
}

Measured memory_bytes: 3700
#include <stdio.h>

int main(){
	int i, x;

	i = 1;
	while (1){
		scanf("%d", &x);
		if (x == 0){
			break;
		}
		else{
			printf("Case %d: %d\n",i,x);
			i = i + 1;
		}
	}
	return 0;
}

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

const int MAX_N = 300000;
int n, m;
bool one_to[MAX_N], to_n[MAX_N];

int main(void) {
    cin >> n >> m;
    string ans = "IMPOSSIBLE";
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if (a == 0) one_to[b] = true;
        if (b == n-1) to_n[a] = true;
    }
    for (int i = 0; i < n; i++) {
        if (one_to[i] && to_n[i]) {
            ans = "POSSIBLE";
            break;
        }
    }  
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmin(S &a, T b){
  if(a>b){
    a=b;
  }
  return a;
}
int M, N, R, V[8], d[200][200];
int main(){
  int RZTsC2BF, i, j, k, res, tmp;
  rd(N);
  rd(M);
  rd(R);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<R;Lj4PdHRW++){
      rd(V[Lj4PdHRW]);
    }
  }
  {
    int KL2GvlyY;
    for(KL2GvlyY=0;KL2GvlyY<(R-1) + 1;KL2GvlyY++){
      V[KL2GvlyY]--;
    }
  }
  sort(V, V+R);
  {
    int Q5VJL1cS;
    for(Q5VJL1cS=0;Q5VJL1cS<(N-1) + 1;Q5VJL1cS++){
      {
        int e98WHCEY;
        for(e98WHCEY=0;e98WHCEY<(N-1) + 1;e98WHCEY++){
          d[e98WHCEY][Q5VJL1cS] = 1073709056;
        }
      }
    }
  }
  {
    int cTE1_r3A;
    for(cTE1_r3A=0;cTE1_r3A<(N-1) + 1;cTE1_r3A++){
      d[cTE1_r3A][cTE1_r3A] = 0;
    }
  }
  for(RZTsC2BF=0;RZTsC2BF<M;RZTsC2BF++){
    rd(i);
    rd(j);
    rd(k);
    i--;
    j--;
    d[i][j] = d[j][i] = k;
  }
  for(k=0;k<N;k++){
    for(i=0;i<N;i++){
      for(j=0;j<N;j++){
        chmin(d[i][j], d[i][k]+d[k][j]);
      }
    }
  }
  res = 1073709056;
  do{
    tmp = 0;
    {
      int FmcKpFmN;
      for(FmcKpFmN=1;FmcKpFmN<(R-1) + 1;FmcKpFmN++){
        tmp += d[V[FmcKpFmN]][V[FmcKpFmN - (1) + (0)]];
      }
    }
    chmin(res, tmp);
  }
  while(next_permutation(V,V+R));
  wt_L(res);
  putchar_unlocked('\n');
  return 0;
}
// cLay varsion 20170908-1 [beta]

// --- original code ---
// int N, M, R, V[8];
// int d[200][200];
// {
//   int i, j, k;
//   int res, tmp;
// 
//   rd(N,M,R,V(R));
//   V[0..R-1]--;
//   sort(V, V+R);
//   d[0..N-1][0...N-1] = int_inf;
//   d[0..N-1][0..N-1] = 0;
//   rep(M){
//     rd(i,j,k);
//     i--; j--;
//     d[i][j] = d[j][i] = k;
//   }
//   rep(k,N) rep(i,N) rep(j,N) d[i][j] <?= d[i][k]+d[k][j];
// 
//   res = int_inf;
//   do{
//     tmp = 0;
//     tmp += d[V[1..R-1]][V[0..]];
//     res <?= tmp;
//   }while(next_permutation(V,V+R));
//   wt(res);
// }


Measured memory_bytes: 384
import java.util.*;
import java.io.*;

/*
   AtCoder contest code
   coder : yoichidon
 */
import java.util.*;
import java.io.*;

public class Main {
    public static int positiveRangeCount(int[] h){
        int ans=0;
        for(int n=0; n<h.length; n++){
            if(h[n]>0 && (n==0 || h[n-1]<=0)) ans++;
        }
        return ans;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] h = new int[N];
        for(int n=0; n<N; n++) h[n]=sc.nextInt();

        int water = 0;
        while(positiveRangeCount(h) >0){
            water += positiveRangeCount(h);
            for(int n=0; n<N; n++) h[n]--;
        }

        System.out.println(water);

    }
}


Measured memory_bytes: 22996
use std::io;
fn main() {
  let mut input_line = String::new();
  io::stdin().read_line(&mut input_line).unwrap();
  let n = input_line.trim().parse::<u64>().unwrap();
  
  let q = n / 11u64;
  let r = n % 11u64;
  let mut res = 2 * q;
  if r > 6 { res += 2; }
  else if r > 0 { res += 1; }
  println!("{}", res);
}


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

#include <ext/pb_ds/assoc_container.hpp> //required
#include <ext/pb_ds/tree_policy.hpp> //required

using namespace __gnu_pbds; 
using namespace std;

template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
typedef long long  ll;
typedef vector<ll> VL;
typedef vector<int> VI;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;
#define pb push_back

#define F first
#define S second
#define SZ(a) int((a).size())
#define ALL(a) a.begin(),a.end()
#define fr(i,x,y) for(int i=x;i<y;i++)
#define frr(i,x,y) for(int i=x-1;i>=y;i--)
#define inf 1e18+1
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int mod=1000000007;
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll power(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;}a=a*a;b>>=1;}return ans;}
ll powerm(ll a,ll b){ll ans=1;while(b!=0){if(b&1){ans*=a;ans%=mod;}a=a*a;a%=mod;b>>=1;}return ans%mod;}
// string to integer stoi()
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
vector<VL> adj;
VL visit2,val;

void dfs(ll v,ll pos)
{
    visit2[v]=1;
    val[pos]++;
    for(auto to:adj[v])
    {
        if(visit2[to]==-1)
        {
            dfs(to,pos);
        }
    }
    return;
}
void solve()
{
    ll n,m;
    cin>>n>>m;
    adj.assign(n,VL());
    fr(i,0,m)
    {
        ll x,y;
        cin>>x>>y;
        x--,y--;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    ll comp=0;
    visit2.assign(n,-1);
    val.assign(n+1,0);
    fr(i,0,n)
    {
        if(visit2[i]==-1)
        {
            comp++;
            dfs(i,comp);
        }

    }
    ll ct=0;
    fr(i,0,n+1)
    {
        if(val[i]>=1)
        {
            ct=max(ct,val[i]);
        }
    }
    ll ans=ct;
    // if(n%ct!=0)
    //     ans++;
    cout<<ans<<endl;
    return;
}
int main()
{
    IOS;
    ll t=1;
    //cin>>t;
    while(t--)
    {
        //cout<<"Case #"<<pp-t<<":\n";
        solve();
    }
    return 0;
}
/* stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
*/
/*
recursion - matrix exponential

*/
// BITMASK:
// 1)When some constrall is of the order of 15-20, think of bitmask DP.
// 2)When some constrall is around 40, try out meet in the middle
// 3) See Strings,palindromes,prefix,suffix etc -> KMP,Z algorithm

Measured memory_bytes: 23452
#include<bits/stdc++.h>
using namespace std;
#define mod   1000000007
#define ll long long
ll n,k;
vector<int> v[100005];
ll dfs(int t,int par,int col){
    if(v[t].size()>col-1) return 0;
    if(par==-1) col--;
    else col-=2;
    ll res=1;
    for(int i=0;i<v[t].size();i++){
        if(v[t][i]==par) continue;
        res=res*col%mod*dfs(v[t][i],t,k)%mod;
        col--;
    }
    return res%mod;
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n-1;i++){
        int a,b; cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    ll ans=k;
    ans=ans*dfs(1,-1,k)%mod;
    cout<<ans<<endl;
}


Measured memory_bytes: 11520
#include<iostream>
using namespace std;
int main(){
	int maisuu, a[15000], b[15000];
	long long int a_p = 0, b_p = 0;
	int anser[2][10];
	int hasi;
	for (int i = 0; i < 5; i++){
		cin >> maisuu;
		if (maisuu == 0){
			break;
		}
		for (int i2 = 0; i2 < maisuu; i2++){
			cin >> a[i2];
			cin >> b[i2];
		}
		for (int i2 = 0; i2 < maisuu; i2++){
			if (a[i2] < b[i2]){
				b_p += a[i2] + b[i2];
			}
			else if (a[i2]>b[i2]){
				a_p += a[i2] + b[i2];
			}
			else if (a[i2] == b[i2]){
				a_p += a[i2];
				b_p += b[i2];
			}
		}
		anser[0][i] = a_p;
		anser[1][i] = b_p;
		maisuu = 0;
		a_p = 0;
		b_p = 0;
		hasi = i;
	}
	for (int i = 0; i <= hasi; i++){
		cout << anser[0][i] << " " << anser[1][i] << endl;
	}
	return 0;
}

Measured memory_bytes: 3068
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll mod= 1e9 + 7;

int f(int x,int y,int z){
  return x*x+y*y+z*z+x*y+y*z+z*x;
}

int main(){
  int n;
  cin >>n;
  int a[100000]={};
    for(int x=1;x<100;x++){
      for(int y=1;y<100;y++){
        for(int z=1;z<100;z++){
          a[f(x,y,z)]++;
        }
      }
    }
  
  for(int i=1;i<=n;i++){
    cout << a[i] << endl;
  }
}

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

using namespace std;

using ll = long long;
constexpr int mo = 1e9+7;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;
constexpr ll mo2 = 998244353;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll x;
    cin>>x;
    for(ll a=-1000;a<=1000;++a){
        for(ll b=-1000;b<=1000;++b){
            ll A = a*a*a*a*a;
            ll B = b*b*b*b*b;
            if(A- B == x){
                cout << a << " " <<b << endl;
                return 0;
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 105
#define INF 100000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 100005;
const int MOD = 1000000007;
int main(){
    string s;
    int k;
    cin>>s>>k;
    map<string,int>m;
    for(int i=0;i<SZ(s);i++){
        for(int j=0;j<=5;j++){
            string t="";
            for(int l=i;l<=i+j;l++){
                if(l>=SZ(s))continue;
                t.push_back(s[l]);
            }
            m[t]++;
        }
    }
    int i=0;
    for(auto p:m){
        string t=p.first;
        i++;
        if(i==k){
            OUT(t);
            break;
        }
    }
    return 0;
}

Measured memory_bytes: 2432
fun main(args: Array<String>) {
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toDouble() }

    var s = 0.0
    val max = a.max()!!
    for (i in a){
        s += max/i
    }
    println(max/s)
}

Measured memory_bytes: 38184
n = gets.to_i
wa = Array.new(34).map{[0,0]}
ans = "0"*34
wa[0][0] = 1
for i in 1..33
  if i%2 == 0
    wa[i][0] = 2**i
  else
    wa[i][1] = -2**i
  end
  wa[i][0] += wa[i-1][0]
  wa[i][1] += wa[i-1][1]
end
s = []
while n != 0
  if n > 0
    for i in 0..33
      if wa[i][0] >= n
        s << i
        n -= 2**i
        break
      end
    end
  else
    for i in 0..33
      if wa[i][1] <= n
        s << i
        n += 2**i
        break
      end
    end
  end
end
s.each do |i|
  ans[i] = "1"
end
p ans.reverse.to_i

Measured memory_bytes: 1788
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
int powint(int a, int x){
	int res = 1;
	REP(i,x){
		res = res *a; 
	}
	return res;
}

using namespace std;

int main(){
	string N;
	cin>>N;
	cout<<N.substr(0,N.size()-8)<<endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define inf 100000000000
#define int long long int
#define hell (int)(1e9+7)

using namespace std;

void solve(){
    int k;
    cin>>k;
    queue <int> q;
    for(int i=1;i<10;i++)
        q.push(i);
    vector <int> v;
    while(!q.empty()&&v.size()<1e6){
        int s=q.front();
        v.push_back(s);
        q.pop();
        int d=s%10;
        q.push(s*10+d);
        if(d==0)
            q.push(s*10+d+1);
        else if(d==9)
            q.push(s*10+d-1);
        else{
            q.push(s*10+d+1);
            q.push(s*10+d-1);
        }
    }
    sort(begin(v),end(v));
    cout<<v[k-1];
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	//cin>>t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}


Measured memory_bytes: 26192
package main

import (
	"fmt"
	"sort"
)

func main() {
	var n int
	fmt.Scan(&n)
	list := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&list[i])
	}
	sortList := make([]int, n)
	copy(sortList, list)
	sort.Sort(sort.IntSlice(sortList))
	for i := 0; i < n; i++ {
		if list[i] == sortList[n-1] {
			fmt.Println(sortList[n-2])
		} else {
			fmt.Println(sortList[n-1])
		}

	}

}


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

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int a,b,c;
	cin>>a>>b>>c;
	int c5=0,c7=0;
	
	if(a==5)
		c5++;
	else if(a==7)
		c7++;
	if(b==5)
		c5++;
	else if(b==7)
		c7++;
	if(c==5)
		c5++;
	else if(c==7)
		c7++;
	
	if(c5==2 && c7==1)
		cout<<"YES"<< endl;
	else
		cout<<"NO"<< endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define FOR(i,start,end) for(int i=start;i<=end;i++)
const int INF = 1001001001;
using namespace std;
typedef long long ll;

typedef pair<int, bool> P;

P A[3][3];
int N;

bool eval() {
  bool res = false;
  rep(i,3) {
    if(A[i][0].second &&
       A[i][1].second &&
       A[i][2].second )
      res = true;
  }
  rep(i,3) {
    if(A[0][i].second &&
       A[1][i].second &&
       A[2][i].second )
      res = true;
  }
  if(A[0][0].second &&
     A[1][1].second &&
     A[2][2].second)
    res = true;

  if(A[0][2].second &&
     A[1][1].second &&
     A[2][0].second)
    res = true;

  return res;
}
void check(int n) {
  rep(i,3){
    rep(j,3){
      if(A[i][j].first == n)
	A[i][j].second = true;
    }
  }
}

int main()
{
  int N;
  int res=0;
  rep(i,3){
    rep(j,3){
      cin >> A[i][j].first;
      A[i][j].second = false;
    }
  }
  cin >> N;
  rep(i,N) {
    int b;
    cin >> b;
    check(b);
  }
  if(eval()) cout << "Yes" << endl;
  else  cout << "No" << endl;
}


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

const int maxn=2e5+10;
const int mo=1e9+7;

int n,x[maxn],v[maxn],t[maxn];
int L[maxn],R[maxn],dp[maxn],pre[maxn];

int main()
{
#ifdef h10
	freopen("E.in","r",stdin);
	freopen("E.out","w",stdout);
#endif
	int i;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%d%d",&x[i],&v[i]);
	memcpy(t,x,sizeof(x));
	sort(t+1,t+n+1);
	for (i=1;i<=n;i++)
		x[i]=lower_bound(t+1,t+n+1,x[i])-t;

	memcpy(t,v,sizeof(v));
	sort(t+1,t+n+1);
	for (i=1;i<=n;i++)
		v[i]=lower_bound(t+1,t+n+1,v[i])-t;

	for (i=1;i<=n;i++)
		t[x[i]]=v[i];
	L[n]=t[n];
	for (i=n-1;i>=1;i--)
		L[i]=min(L[i+1],t[i]);
	R[1]=t[1];
	for (i=2;i<=n;i++)
		R[i]=max(R[i-1],t[i]);

	int p=1;
	dp[0]=pre[0]=1;
	for (i=1;i<=n;i++)
	{
		while (R[p]==i)
		{
			pre[i]=(pre[i-1]+dp[i])%mo;
			(dp[i]+=pre[R[p]])%=mo;
			if (i!=1) (dp[i]+=mo-pre[L[p]-2])%=mo;
			p++;
		}
		pre[i]=(pre[i-1]+dp[i])%mo;
	}
	printf("%d\n",dp[n]);
}


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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';

template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }

int main() {
    int N, T;
    int A[100005];
    int maxdiff = 0;
    int minv = INF;
    map <int, int> cnt;

    cin >> N >> T;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        minv = min(minv, A[i]);
        maxdiff = max(maxdiff, A[i] - minv);
    }
    
    int ct = 0;
    for (int i = 0; i < N; i++) {
        cnt[A[i]]++;
        ct += cnt[A[i] - maxdiff] > 0;
        cnt[A[i] - maxdiff] = max(0, cnt[A[i] - maxdiff] - 1);
    }

    cout << ct << endl;

    return (0);
}

Measured memory_bytes: 9984
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  string s;
  cin >> s;
  for(int i = 0; i < s.size(); i++){
    char c = s[i];
    char next_c = s[i + 1];
    if(c == next_c){
      s.erase(i, 1);
      i--;
    }
  }
  cout << s.size() << endl; 
}

Measured memory_bytes: 512
import math

n, h = map(int, input().split())
array = [[int(x) for x in input().split()] for x in range(n)]

array = sorted(array, key=lambda x:x[0], reverse=True)
tmp_a = array[0][0]
array = sorted(array, key=lambda x:x[1], reverse=True)
cnt = 0
for a, b in array:
    if h <= 0:
        print(cnt)
        exit()
    if b > tmp_a:
        h -= b
        cnt += 1
    else:
        break
print(cnt+math.ceil(h/tmp_a))


Measured memory_bytes: 23648
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
total = 0
pre = n + 2
for i in range(n):
    total += B[A[i] - 1]
    if pre + 1 == A[i] - 1:
        total += C[pre]
    pre = A[i] - 1
print(total)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <utility>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
const int INF = 1<<30; 
const int MOD = 1e9 + 7;
const int dy[] = {1, 0, -1, 0};
const int dx[] = {0, 1, 0, -1};
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b, x;
    cin >> a >> b >> x;
    if(a == 0)
    {
        cout << b / x + 1 << endl;
    }
    else
    {
        cout << b / x  - (a - 1) / x << endl;
    }
    return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define REP(NAME, NUM) for (size_t NAME = 0; NAME < (NUM); ++NAME)
#define BREP(NAME, NUM) for (size_t NAME = (NUM)-1; NAME >= 0; --NAME)
#define ALL(NAME) (NAME).begin(), (NAME).end()
#define VEC(TYPE, A, NAME, INIT) vector<TYPE> NAME(A, INIT)
#define VEC2(TYPE, A, B, NAME, INIT) vector<vector<TYPE>> NAME(A, vector<TYPE>(B, (INIT)))

int main()
{
	int n;
	cin >> n;
	
	int m = n % 2 == 0
		? n * ( n - 2 ) / 2
		: ( n - 1 ) * ( n - 1 ) / 2;
	cout << m << endl;
	int k = ( n / 2 ) * 2 + 1;
	for( int i = 1; i <= n; ++i )
	{
		for( int j = i + 1; j <= n; ++j )
		{
			if( i + j == k ) continue;
			cout << i << " " << j << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int N;
    cin >> N;
    vector<ll> A(N),B(N);
    rep(i,0,N)cin >> A[i];
    rep(i,0,N)cin >> B[i];
    ll sumA = 0,sumB = 0;
    rep(i,0,N)sumA += A[i];
    rep(i,0,N)sumB += B[i];
    if(sumA < sumB){
        cout << -1 << endl;
        return 0;
    }
    ll sub = 0,cnt = 0;
    rep(i,0,N){
        if(A[i] < B[i]){
            cnt++;
            sub += B[i] - A[i];
        }   
    }
    if(sub <= 0){
        cout << 0 << endl;
        return 0;
    }
    vector<ll> dif(N);
    rep(i,0,N)dif[i] = A[i] - B[i];
    sort(dif.rbegin(), dif.rend());
    rep(i,0,N){
        sub -= dif[i];
        cnt++;
        if(sub <= 0){
            cout << cnt << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define Phuong // <3
typedef pair<int,int> ii;


int main()
{
#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
#endif // ONLINE_JUDGE
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int a,b,c;
    cin >> a >> b >> c;

    cout << max(c-a+b,0) ;
    return(0);
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
"""
Created on Tue May  7 13:31:56 2019

@author: 70723224
"""

def resale(V, C):

    result = 0
    for v, c in zip(V, C):
        if v > c:
            result += v - c
            
    return result


if __name__ == '__main__':
    
#    print('Input: ')
    n = int(input())
    v = list(map(int, input().split()))
    c = list(map(int, input().split()))
    
#    print('---------------------')
#    print('Output: ')
    print(resale(v,c))
    
    
    
#    a = list(map(int, input().split()))
#    N = a[0]
#    b = (len(a)-1)/2+1
#    V = a[1:b]
#    C = a[b:]    
#    print(calc(V, C))


Measured memory_bytes: 3060
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<complex>
#include<sstream>
#include<climits>

#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int MAX_Q = 300;
int Q;
ll A[MAX_Q], B[MAX_Q], C[MAX_Q], D[MAX_Q];

//gcd(a, b)を求める。
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}


int main() {
  cin >> Q;
  rep(i,Q) cin >> A[i] >> B[i] >> C[i] >> D[i];


  for (int i = 0; i < Q; ++i) {
    if (A[i] < B[i] || D[i] < B[i]) {
      cout << "No" << endl;
    } else {
      ll s = A[i] - ((A[i]-C[i]+B[i]-1)/B[i])*B[i];
      if (s < 0) {
        cout << "No" << endl;
        continue;
      }
      ll g = gcd(B[i], D[i]);
      ll xce = ((s/g)+1) * g;
      if (B[i] - xce + s > C[i]) cout << "No" << endl;
      else cout << "Yes" << endl;
    }
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#define MAX 10000
#define MMIINN -2000000200
using namespace std;
typedef long long ll;

class Heap{
public:
  int index;
  ll HeapArray[MAX+1];

  Heap(){
    index=0;
    for(int i=0;i<=MAX;i++)HeapArray[i]=MMIINN;
  }

  void insert(ll v){
    index++;
    HeapArray[index]=v;
  }

  ll getValue(int i){
    return HeapArray[i];
  }

  ll getParent(int i){
    return HeapArray[i/2];
  }

  ll getLeft(int i){
    return HeapArray[2*i];
  }

  ll getRight(int i){
    return HeapArray[2*i+1];
  }



};


int main(){
  int n;
  ll val;
  Heap H;
  cin >> n;
  for(int i=0;i<n;i++){
    cin >> val;
    H.insert(val);
  }

  for(int i=1;i<=n;i++){
    printf("node %d: key = %lld, ",i,H.getValue(i));
    if(i != 1)printf("parent key = %lld, ",H.getParent(i));
    if(H.getLeft(i) != MMIINN)printf("left key = %lld, ",H.getLeft(i));
    if(H.getRight(i) != MMIINN)printf("right key = %lld, ",H.getRight(i));
    printf("\n");
  }



  return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
int n, M, x;
int m[15][15], cost[15];
int main()
{
    scanf("%d%d%d", &n, &M, &x);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &cost[i]);
        for (int j = 1; j <= M; j++)
            scanf("%d", &m[i][j]);
    }
    int ans = INF;
    for (int i = 0; i <= ((1<<n) - 1); i++) {
        int a[15];
        memset(a, 0, sizeof(a));
        int res = 0;
        for (int j = 0; j < n; j++) {
            if((i>>j)&1) {
                for (int k = 1; k <= M; k++)
                    a[k] += m[j + 1][k];
                res += cost[j + 1];
            }
        }
        bool f = true;
        for (int j = 1; j <= M; j++) {
            if(a[j] < x) f = false;
        }
        if(f) ans = min(ans, res);
    }
    if(ans == INF) printf("-1\n");
    else cout << ans << endl;
}


Measured memory_bytes: 3764