akhauriyash/Code-Regression huggingface dataset:
/**
 *   author: malviyanshiv
 *   created: 11 November 2019  17:46:06
**/
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

bool valid(ll md, ll k, vector<ll> &cs, vector<ll> &as){
    ll tot = 0, tp;
    for(int i = 0; i < cs.size(); i++){
        tp = cs[i] - (md/as[i]);
        if( tp > 0 )
            tot += tp;
    }

    return tot <= k ;
}

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

    ll n, k;
    cin >> n >> k;
    vector<ll> as(n), cs(n);
    ll mxa = 0, mxc = 0;
    for(int i = 0; i < n; i++){
        cin >> as[i];
        mxa = max(mxa, as[i]);
    }
    for(int i = 0; i < n; i++){
        cin >> cs[i];
        mxc = max(mxc, cs[i]);
    }

    sort(as.begin(), as.end());
    sort(cs.rbegin(), cs.rend());

    ll hg = mxa*mxc, lw = 0;
    while(lw < hg){
        ll md = (lw+hg)/2;
        if( valid(md, k, as, cs) ){
            hg = md;
        }else{
            lw = md+1;
        }
    }

    cout << lw << endl;
    return 0;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define fr(i, n) for (int i = 0; i < n; i++)
#define frab(i, a, b) for (int i = a; i < b; i++)
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const ll MOD = 1e9 + 7;
const ll INF = 2e15 + 10;
const ll MAX = 1e14 + 10;
const ld EPS = 1e-9;
const int N = 3e5 + 10;
const int M = 1e5 + 10;

int a[N];

void solve() {
    int n, k;
    cin >> n >> k;
    fr(i, n)
        cin >> a[i];
    vector<int> d(k + 1, 0);
    d[0] = 0;
    fr(i, k) {
        if (!d[i])
            fr(j, n)
                if (i + a[j] <= k)
                    d[i + a[j]] = 1;
    }
    if (d[k])
        cout << "First";
    else
        cout << "Second";
}



int main() {
    //freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    solve();
}


Measured memory_bytes: 640
n = gets.to_i
s = []
n.times do
  s.push gets.chomp
end
c = s.tally
puts "AC x "  + (c["AC"]  || 0).to_s
puts "WA x "  + (c["WA"]  || 0).to_s
puts "TLE x " + (c["TLE"] || 0).to_s
puts "RE x "  + (c["RE"]  || 0).to_s


Measured memory_bytes: 20676
N =  [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K = int(input())
print(N[K-1])

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	string s;cin >> s;
	int ans=0,sum=0;
	rep(i,n){
		if(s.at(i)=='I') sum++;
		else sum--;
		ans=max(sum,ans);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
X = list(map(int, input().split()))

if N >= M:
    print(0)
    exit()

X.sort()
L = []
for i in range(1,M):
    L.append(X[i]-X[i-1])
L.sort(reverse=True)

tmp = 0
for i in range(N-1):
    tmp += L[i]
print(X[-1]-X[0] - tmp)

Measured memory_bytes: 13960
if __name__ == "__main__":
    n = int(input())
    info = []
    for _ in range(n):
        a = int(input())
        tmp = []
        for __ in range(a):
            tmp.append(list(map(int, input().split())))
        info.append(tmp)
    
    mask = 0
    honest = [0] * n
    ans = 0
    while mask < (1 << n):
        part = 0
        is_ok = True
        for i in range(n):
            if 1  & mask >> i  == 1:
                 honest[i] = 1
                 part += 1
            else:
                honest[i] = 0

        for i in range(n):
            if honest[i] == 1:
                for w in info[i]:
                    if honest[w[0] - 1] != w[1]:
                        is_ok = False
        
        if is_ok:
            if part > ans:
                ans = part
        mask += 1
    print(ans)

Measured memory_bytes: 3064
from collections import Counter

input()
d = Counter(map(int, input().split()))
d = dict(sorted(d.items(), reverse=True))
ans = []
for i, j in d.items():
    if j >= 4:
        ans.append(i)
    if j >= 2:
        ans.append(i)
    if len(ans) >= 2:
        print(ans[0] * ans[1])
        break
else:
    print(0)

Measured memory_bytes: 34812
import math
n,d = map(int,input().split())
x = [list(map(int,input().split())) for _ in range(n)]
def distance(a,b):
  s = 0
  for i in range(d):
    s += (a[i]-b[i])**2
  return math.sqrt(s)
ans = 0
for i in range(n-1):
  for j in range(i+1,n):
    if distance(x[i],x[j])//1 == distance(x[i],x[j]):
      ans += 1
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,n,s) for(int i=(int)(s);i<(int)(n);++i)
#define RREP(i,n,s) for(int i=(int)(s);i>=(int)(n);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    int a,b,c,k;cin>>a>>b>>c>>k;

    int m = max({a,b,c});
    int m2 = m;
    REP(i,k) m2 *= 2;

    cout << (a+b+c+m2-m) << endl;
}


Measured memory_bytes: 256
#include <iostream>

#define ERR_EXTERN(int_in) ((int_in > 9) || (int_in < 1))

int main(){
    int r, g, b;
    int maked_int;
    std::cin >> r >> g >> b;
    if(ERR_EXTERN(r) || ERR_EXTERN(g) || ERR_EXTERN(b)){
        std::cout << "Invalid range value!" << std::endl;
        return 1;}
    maked_int = (r * 100) + (g * 10) + b;
    if((maked_int%4)==0){
        std::cout << "YES" << std::endl;
    }else{
        std::cout << "NO" << std::endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main( void )
{
  int a, b, c ;
  scanf("%d %d %d", &a, &b, &c ) ;
  if( a+b >= c ) {
  	printf("%d\n", b+c ) ;
  } else {
    printf("%d\n", b*2+a+1 ) ;
  }
  return 0 ;
}


Measured memory_bytes: 128
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int min = Integer.MAX_VALUE;
		int max = -Integer.MIN_VALUE;
		long sum = 0;
		
		for(int i = 0; i < n; i++) {
			int a = sc.nextInt();
			min = Math.min(min, a);
			max = Math.max(max, a);
			sum = sum + a;
		}
		
		System.out.println(min + " " + max + " " + sum);
	}
}



Measured memory_bytes: 41688
n=int(input())
f=[0]*n
for i in range(n):
  x=list(map(int,input().split()))
  for j in range(len(x)):
    if x[j]==1:
      f[i]+=1<<j
  
p=[[0 for j in range(10)] for i in range(n)]

for i in range(n):
  p[i]=list(map(int,input().split()))

ans=10**9*(-1)-1
for i in range(1,2**10):
  pro=0
  for j in range(len(f)):
    open=0
    for k in range(10):
      if (i>>k)&1==1 and (f[j]>>k)&1==1:
        open+=1
    pro+=p[j][open]
  if ans<pro:
    ans=pro
print(ans)


Measured memory_bytes: 3064
import java.util.Scanner;
 
class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        System.out.print(a*b);
System.out.print(" ");
System.out.println(2*a+2*b);
    }
}


Measured memory_bytes: 26116
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define sz(v) (ll((v).size()))
#define forn(i,n) for(ll i=0;i<(n);i++)
#define forr(i,n) for(ll i=(n)-1;i>=0;i--)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
#define clr(x) memset(x,0,sizeof(x))

const ll N = 1e5+5;
ll c[N],d[N];

int main()
{
	ios_base::sync_with_stdio(false);

	clr(c);clr(d);
	ll n;cin>>n;

	if(n==2){
		ll p,q;cin>>p>>q;cout<<(p==q)<<endl;
		return 0;
	}


	forn(i,n/2){ll x;cin>>x;c[x]++;cin>>x;d[x]++;}
	vector<pair<ll,ll>>a,b;
	forn(i,N){
		a.pb(mp(c[i],i));
		b.pb(mp(d[i],i));
	}
	sort(all(a));reverse(all(a));
	sort(all(b));reverse(all(b));

	ll x=0;
	if(a[0].S != b[0].S)x=a[0].F+b[0].F;
	else {
		x= max(a[1].F + b[0].F , a[0].F + b[1].F);
	}
	cout<<n-x<<endl;
}


Measured memory_bytes: 5220
//
// Created by Tetsuya Shiota on 2019/03/09.
//

#include<iostream>

using namespace std;

int main(){
    int H, W;
    cin >> H >> W;

    int ans = H * W;

    int h, w;
    cin >> h >> w;

    ans -= h * W;
    ans -= w * H;
    ans += h * w;

    cout << ans <<endl;


}

Measured memory_bytes: 888
#include <stdio.h>
#include <string.h>
int main()
{
    char a[50]={0},b[50]={0},min[50]={0},temp[50];
    int result=0,i,j,count,count2=0;
    scanf("%s",a);
    scanf("%s",b);
    for(i=strlen(a)-strlen(b);i>=0;i--)
    {
       count=0;
       for (j=i;j<strlen(b)+i;j++)
       {
           if (a[j]==b[j-i]||a[j]=='?')
           {
               count++;
           }
       }
       if (count==strlen(b))
       {
           count2++;
           strcpy(temp,a);
           for (j=i;j<strlen(b)+i;j++)
           {
               a[j]=b[j-i];
           }
           for (j=0;j<strlen(a);j++)
           {
               if (a[j]=='?') a[j]='a';
           }
           if (count2==1) strcpy(min,a);
           if (strcmp(min,a)>0) strcpy(min,a);
           strcpy(a,temp);
       }
    }
    if (count2>0) printf("%s",min);
    if(count2==0){
        printf("UNRESTORABLE\n");
    }
    return 0;
}


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

string st;

int main()
{
    cin>>st;
    if(st[0]=='Y' && st[1]=='A' && st[2]=='K' && st[3]=='I')
        puts("Yes");
    else 
        puts("No");
    return 0;
}

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

using namespace std;
using LL = long long;
using P = pair<int, int>;

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

#define pb(a) push_back(a)
#define all(x) (x).begin(),(x).end()

const int INF = (int)1e9;
const LL INFL = (LL)1e18;
const int MOD = 1e9 + 7;

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

    string s;
    cin >> s;
    vector<vector<LL>> dp(s.size()+1, vector<LL>(4, 0));
    dp[0][0] = 1;
    REP(i, s.size()){
        REP(j, 4){
            if(s[i] == '?') dp[i+1][j] += dp[i][j] * 3 % MOD;
            else dp[i+1][j] += dp[i][j];
            dp[i+1][j] %= MOD;
        }
        if(s[i] == 'A' || s[i] == '?') dp[i+1][1] += dp[i][0];
        if(s[i] == 'B' || s[i] == '?') dp[i+1][2] += dp[i][1];
        if(s[i] == 'C' || s[i] == '?') dp[i+1][3] += dp[i][2];
        
        REP(j, 4) dp[i+1][j] %= MOD;
    }
    
    cout << dp[s.size()][3] << endl;
}


Measured memory_bytes: 7376
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define Graph vector< vector<ll> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = (1LL << 40);

int main(){
    int N, M;
    cin >> N >> M;
    Graph G(N, vector<ll>(N, INF));
    rep(i, M){
        int s, t, d;
        cin >> s >> t >> d;
        G[s][t] = d;
    }
    rep(i, N){
        G[i][i] = 0;
    }

    rep(k, N){
        rep(i, N){
            if(G[i][k] == INF) continue;
            rep(j, N){
                if(G[k][j] == INF) continue;
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }

    bool negative = false;
    rep(i, N){
        if(G[i][i] < 0){
            negative = true;
            break;
        } 
    }

    if(negative) cout << "NEGATIVE CYCLE" << endl;
    else{
        rep(i, N){
            rep(j, N){
                if(j) cout << ' ';
                if(G[i][j] == INF) cout << "INF";
                else cout << G[i][j];
            }
            cout << endl;
        }
    }
}


Measured memory_bytes: 3248
n = int(input())
c = []
s = []
f = []
for i in range(n - 1):
  ci, si, fi = map(int, input().split())
  c.append(ci)
  s.append(si)
  f.append(fi)
for i in range(n):
  t = 0
  for j in range(i, n - 1):
    t = max(t, s[j])
    t = (t + f[j] - 1) // f[j] * f[j] + c[j]
  print(t)


Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import math

# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    A = inputInt()
    
    tmp = N*N
    print(tmp-A)
    
            	
if __name__ == "__main__":
	main()


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

int main(){
    long long n,a,b;
    cin >> n >> a >> b;
    int ans= 0;
    for (int i = 1; i <= n; i++){
        int sum = 0;
        int t = i;
        while (t > 0){
            sum += t % 10;
            t /= 10;
        }
        if (sum >= a && sum <= b){
            ans += i;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define all(x) (x).begin(),(x).end()
#define S(x) (int)(x).size()
#define L(x) (int)(x).length()
#define debug(x) cerr << #x << " " << x << endl;
#define debug_p(x) cerr << #x << " [" << x.fi << " " << x.se << "]"<<endl;
#define debug_v(x) {cerr << #x << " "; for (auto ioi : x) cerr << ioi << " "; cerr << endl;}
#define debug_vp(x) {cerr << #x << " "; for (auto ioi : x) cerr << '[' << ioi.fi << " " << ioi.se << ']'; cerr << endl;}
#define debug_v_v(x) {cerr << #x << "/*\n"; for (auto ioi : x) { for (auto ioi2 : ioi) cerr << ioi2 << " "; cerr << '\n';} cerr << "*/" << #x << endl;}
#define gen_clock(x) ll x = clock(); cerr << "Clock " << #x << " created" << endl;
#define check_clock(x) cerr << "Time spent in " << #x << ": " << (double)(clock() - x)/CLOCKS_PER_SEC << endl; x = clock();
#define reset_clock(x) x = clock()

const int mod = 1e9+7;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
const int infi = 0x3f3f3f3f;

void solve()
{
	int n;
	cin>>n;
	n%=10;
	if(n==3)
	{
		cout<<"bon";
	}
	else if(n==0 || n==1 || n==6 || n==8)
	cout<<"pon";
	else cout<<"hon";
}

int main()
{
	IOS
	int t=1;
	//cin>>t;
	while(t--)
	{
		solve();
	}
}


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

vector<long long> input(long long N) {
  vector<long long> res(N);
  for (int i = 0; i < N; i++) {
    cin >> res.at(i);
  }
  return res;
}

int main(){
    long long N, A, B;
    long long sum = 0;
    cin >> N >> A >> B;
    vector<long long> X(N);
    X = input(N);
    for(int i = 1; i < N; i++)sum += min(A * (X[i] - X[i - 1]), B);
    cout << sum << endl;
}

Measured memory_bytes: 1792
#B
N = int(input())
A = list(map(int,input().split()))
S = sum(A)
f = 0
b = S
M = S
for i in range(N-1):
    f+=A[i]
    b-=A[i]
    #print(f,b)
    M = min(M,abs(f-b))
    
print(M)


Measured memory_bytes: 26764
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <vector>
#include <climits>
using namespace std;

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

	auto w = t.length();
	vector<string> prev(w + 1);
	vector<string> next(w + 1);
	for (auto i = 0; i < s.length(); ++i)
	{
		for (auto j = 0; j < w; ++j)
		{
			string* pstr = nullptr;
			if (prev[j + 1].length() > next[j].length())
			{
				pstr = &prev[j + 1];
			}
			else
			{
				pstr = &next[j];
			}

			if (s[i] == t[j])
			{
				if (pstr->length() > prev[j].length())
				{
					next[j + 1] = *pstr;
				}
				else
				{
					next[j + 1] = prev[j];
					next[j + 1] += s[i];
				}
			}
			else
			{
				next[j + 1] = *pstr;
			}
		}

		swap(prev, next);
	}

	cout << prev[w] << endl;

	return 0;
}


Measured memory_bytes: 7808
// vvvvvvvvvvvv TEMPLATE vvvvvvvvvvvv
#include <bits/stdc++.h>
using namespace std; using ll = long long; using P = pair<ll, ll>;
const ll linf = 1e18; const double eps = 1e-12, pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define each(i,a) for (auto&& i : a)
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
#define pb push_back
#define eb emplace_back
#define all(a) begin(a),end(a)
#define chmin(x,v) x = min(x, v)
#define chmax(x,v) x = max(x, v)
#define min(x,y) (x < y ? x : y)
#define max(x,y) (x < y ? y : x)
template<typename Head> void out(Head h) { cout << h << endl; } template<typename Head, typename... Tail>void out(Head h, Tail... t) { cout << h << " "; out(t...); }
template<typename T> istream& operator>>(istream& is, vector<T>& v) { each(x,v) is >> x; return is; }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { rep(i,v.size()) { if (i) os << " "; os << v[i]; } return os; }
ostream& operator<<(ostream& os, const vector<string>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) { rep(i,v.size()) { if (i) os << endl; os << v[i]; } return os; }
template<typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { return os << "(" << p.first << ", " << p.second << ")"; }
struct yes_no : std::numpunct<char> { string_type do_truename() const { return "Yes"; } string_type do_falsename() const { return "No"; } };
void solve(); int main() {
  ios::sync_with_stdio(false); cin.tie(0); locale loc(locale(), new yes_no); cout.imbue(loc); cout << fixed << setprecision(10) << boolalpha;
  solve();
}
// ^^^^^^^^^^^^ TEMPLATE ^^^^^^^^^^^^

void solve() {
  ll n; cin >> n;
  vector<ll> h(n); cin >> h;
  vector<ll> dp(n, linf);
  dp[0] = 0;
  rep(i, n) {
    rep(j, 1, 3) {
      ll ni = i + j;
      if (ni >= n) continue;
      chmin(dp[ni], dp[i] + abs(h[i] - h[ni]));
    }
  }
  cout << dp[n-1] << endl;
}


Measured memory_bytes: 1792
import java.util.Scanner

fun main(args: Array<String>) {
	val scanner = Scanner(System.`in`)
	val list = mutableListOf<Int>()
	while (true){
		val n = scanner.nextInt()
		val s = scanner.nextInt()
		if (n==0 && s==0) break
		else list.add(rec(s, n, 0))
	}
	list.forEach(::println)
}

fun rec(sum: Int, cnt: Int, min: Int): Int{
	if (cnt+min-1>9) return 0
	if (sum !in (2*min+cnt-1)*cnt/2..(18-cnt+1)*cnt/2) return 0
	if (cnt==1) return if (sum in min..9) 1 else 0
	var a = 0
	for (i in min..9) {
		a+= rec(sum-i, cnt-1, i+1)
	}
	return a
}


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

public class Main {

	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);

		int n = sc.nextInt();
		int[] a = sc.nextIntArray(n);

		int o = 1;
		for (int i = 0; i < n; i++) {
			if (a[i] % 2 == 0) o *= 2;
		}

		out.println((int) Math.pow(3, n) - o);
		out.flush();
	}

}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (ptr < buflen) return true;
		else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) return false;
		}
		return true;
	}

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

	private boolean isPrintableChar(byte c) {
		return '!' <= c && c <= '~';
	}

	private void skipUnprintable() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
	}

	public boolean hasNext() {
		skipUnprintable();
		return hasNextByte();
	}

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

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

	public int[] nextIntArray(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}

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

	public long[] nextLongArray(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++) {
			a[i] = nextInt();
		}
		return a;
	}
}

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

using namespace std;

int main()
{
    int i, j, k, l;
    int h, w; cin >> h >> w;
    int bom_count = 0;
    string board[h]; for (i=0; i<h; i++) cin >> board[i];

    for (i=0; i<h; i++)
    {
        for (j=0; j<w; j++)
        {
            if (board[i].at(j) == '.')
            {
                bom_count = 0;
                for (k=-1; k<=1; k++)
                {
                    for (l=-1; l<=1; l++)
                    {
                        if ((0<=(i+k) && (i+k)<h) && (0<=(j+l) && (j+l)<w))
                        {
                            if (board[i+k].at(j+l) == '#') bom_count++;
                        }
                    }
                }
                cout << bom_count;
            }
            else cout << '#';
        }
        cout << endl;
    }
}

Measured memory_bytes: 3616
use std::io::prelude::*;

fn input<T>() -> T
where
    T: std::str::FromStr,
{
    let stdin = std::io::stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}

fn main() {
    let c: Vec<Vec<char>> = (0..3)
        .map(|_| input::<String>().chars().collect())
        .collect();
    println!("{}{}{}", c[0][0], c[1][1], c[2][2]);
}


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

int main() {
  string S;
  cin >> S;
  map<char, int> N;
  for (int i = 0; i < S.size(); i++) {
    if (N.count(S.at(i))) N.at(S.at(i)) += 1;
    else N[S.at(i)] = 1;
  }
  string ans = "Yes";
  for (auto p : N) {
    int k = p.second;
    if (k % 2 == 1) {
      ans = "No";
      break;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int N = 1e5+9;


int n;
ll h[N];

void Yes() {
    cout << "Yes" << endl;
    exit(0);
}


void No() {
    cout << "No" << endl;
    exit(0);
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++)  cin >> h[i];

    ll ng = 0;
    for(int i = 1; i <= n; i++) {
        if(h[i] <= ng)  No();
        ng = max(ng, max(0LL, h[i]-2));
    }
    Yes();
}

Measured memory_bytes: 1024
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// 入力
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		List<Vector2d> p = new ArrayList<>();
		for (int i=0; i<n; i++) {
			double x = sc.nextDouble();
			double y = sc.nextDouble();
			p.add(new Vector2d(x, y));
		}
		sc.close();
		System.out.println(String.format("%1$.1f", solve(p)));
	}

	static class Vector2d {
		Vector2d(Double x, Double y){
			this.x = x;
			this.y = y;
		}
		Double x;
		Double y;
		public String toString() {
			return String.format("%1$.10f %2$.10f", x, y);
		}
	}

	public static Double solve(List<Vector2d> p) {
		Double v2times = 0.0;
		int s = p.size();
		for (int i=0; i<s; i++) {
			v2times += (p.get(i).x * p.get((i+1)%s).y - p.get(i).y * p.get((i+1)%s).x);
		}
		return v2times / 2;
	}
}



Measured memory_bytes: 28904
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <tuple>
#include <math.h>
#include <iomanip>

using namespace std;

class Sover {
};

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

	vector<double> x(n), r(n);
	vector<double> L, R;

	for (int i = 0; i < n; i++)
	{
		cin >> x[i] >> r[i];
		L.emplace_back(x[i] - r[i]);
		R.emplace_back(x[i] + r[i]);
	}

	sort(L.begin(), L.end(), greater<double>());
	sort(R.begin(), R.end());

	double left = L[0];
	double right = R[0];
	double bottom = left;
	double top = right;
	double thres = 0.0001;
	while (bottom + thres < top) {
		double mid = (bottom + top) / 2;
		double mid2 = (bottom + mid) / 2;

		double bottom_height = 1e9;
		double mid_height = 1e9;
		double mid2_height = 1e9;
		for (int i = 0; i < n; i++) {
			double dx = abs(bottom - x[i]);
			double tmp_bottom_height = 0;
			if (dx < thres)tmp_bottom_height = r[i];
			else tmp_bottom_height = sqrt(r[i] * r[i] - dx * dx);

			dx = abs(mid - x[i]);
			double tmp_mid_height = 0;
			if (dx < thres)tmp_mid_height = r[i];
			else tmp_mid_height = sqrt(r[i] * r[i] - dx * dx);

			dx = abs(mid2 - x[i]);
			double tmp_mid2_height = 0;
			if (dx < thres)tmp_mid2_height = r[i];
			else tmp_mid2_height = sqrt(r[i] * r[i] - dx * dx);

			bottom_height = min(bottom_height, tmp_bottom_height);
			mid_height = min(mid_height, tmp_mid_height);
			mid2_height = min(mid2_height, tmp_mid2_height);
		}

		if (bottom_height <= mid2_height + thres
			&& mid2_height < mid_height + thres) {
			bottom = mid2;
		}
		else {
			top = mid;
		}
	}

	double res = 1e9;
	for (int i = 0; i < n; i++) {
		double dx = abs(bottom - x[i]);
		if (dx < thres)res = min(res, r[i]);
		else res = min(res, sqrt(r[i] * r[i] - dx * dx));
	}

	cout << fixed << setprecision(10) << res;
}


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

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

  vector<ll> cnt(100001, 0);
  rep(i, n) cnt[a[i]] += b[i];
  ll c = 0;
  rep(i, 100001) {
    c += cnt[i];
    if (c >= k) {
      cout << i << endl;
      break;
    }
  } 
  return 0;
}

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


int main(){
  int m1,d1,m2,d2,a;
  cin >> m1 >> d1;
  cin >> m2 >> d2;
  a=0;
  if(m1==2){
    if(d1==28){
      a=1;
    }
  }else if(m1==4){
    if(d1==30){
      a=1;
    }
  }else if(m1==6){
    if(d1==30){
      a=1;
    }
  }else if(m1==9){
    if(d1==30){
      a=1;
    }
  }else if(m1==11){
    if(d1==30){
      a=1;
    }
  }else{
    if(d1==31){
      a=1;
    }
  }
  cout << a << endl;
  return 0;
}


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

count = 0
for _ in range(n):
    total = c
    a = list(map(int, input().split()))
    for bn, an in zip(b, a):
        total += bn * an
    if total > 0:
        count += 1

print(count)


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

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

int d[6][4]={{2,3,5,4}, {1,4,6,3}, {1,2,6,5}, {1,5,6,2}, {1,3,6,4}, {2,4,5,3}};

int main(){
	while(1){
		int n;
		cin >> n;
		if(n==0) break;
		
		vector<vector<int> > num(50, vector<int>(50, 0));
		vector<vector<int> > hei(50, vector<int>(50, 0));
		int sx=25, sy=25;
		for(int i=0; i<n; i++){
			int top, front;
			cin >> top >> front;
			int x=sx, y=sy;
			//roll
			while(1){
				int dir[4];
				for(int j=0; j<4; j++){
					if(d[top-1][j]==front){
						for(int k=0; k<4; k++){
							dir[k] = d[top-1][(j+k)%4];
						}
					}
				}
				
				int mvdir=-1;
				int mpip=3;
				for(int j=0; j<4; j++){
					if(dir[j]>mpip &&  hei[x+dx[j]][y+dy[j]]<hei[x][y]){
						mpip = dir[j];
						mvdir = j;
					}
				}
				if(mvdir==-1){
					hei[x][y]++;
					num[x][y] = top;
					break;
				}
				
				if(mvdir==0){
					front = top;
				}else if(mvdir==2){
					front = 7-top;
				}
				top = dir[(mvdir+2)%4];
				x += dx[mvdir];
				y += dy[mvdir];
			}
		}
		
		vector<int> count(7, 0);
		for(int i=0; i<50; i++){
			for(int j=0; j<50; j++){
				count[num[i][j]]++;
			}
		}
		for(int i=1; i<6; i++){
			cout << count[i] << " ";
		}
		cout << count[6] << endl;
	}
	return 0;
}

Measured memory_bytes: 3040
from itertools import permutations
n, m = map(int, input().split())
pair = [tuple(map(int, input().split())) for i in range(m)]
num = [i+1 for i in range(n)]
box = []
for p in permutations(num):
    if p[0] == 1:
        box.append(p)
ans = 0
for p in box:
    already = []
    state = True
    for i in range(n-1):
        if p[i] in already:
            state = False
            break
        if (min(p[i], p[i+1]), max(p[i], p[i+1])) not in pair:
            state = False
            break
        already.append(p[i])
    if state:
        ans += 1
print(ans)


Measured memory_bytes: 3572
// Problem: E - Coprime
// Contest: AtCoder - AtCoder Beginner Contest 177
// URL: https://atcoder.jp/contests/abc177/tasks/abc177_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

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

#define int long long
#define endl "\n"
#define deb(x) cout << #x << " -> " << x << endl;
#define print(x)                         \
    for (auto x_ : x) cout << x_ << " "; \
    cout << endl;
#define pb push_back
#define all(x) x.begin(), x.end()
#define mod 1000000007  // 1e9 + 7
#define prec(x, y) fixed << setprecision(y) << x

const int N = (int)1e6 + 3;
bool visited[N] = {};

void solve() {
    int n;
    cin >> n;
    int e_count, o_count;
    e_count = o_count = 0;
    int a[n];
    for (auto &x : a) {
        cin >> x;
        if (x & 1)
            o_count++;
        else
            e_count++;
    }

    bool okay = true;

    for (int i = 0; i < n; ++i) {
        for (int k = 1; k * k <= a[i]; ++k) {
            if (a[i] % k == 0) {
                int factor1 = a[i] / k;
                int factor2 = k;

                if (factor1 != 1 && visited[factor1]) {
                    okay = false;
                    break;
                }

                if (factor2 != 1 && visited[factor2]) {
                    okay = false;
                    break;
                }

                else {
                    visited[factor1] = true;
                    visited[factor2] = true;
                }
            }
        }
    }

    if (okay) {
        cout << "pairwise coprime";
        return;
    }

    int total_gcd = __gcd(a[0], a[1]);
    for (int i = 2; i < n; ++i) total_gcd = __gcd(total_gcd, a[i]);

    if (total_gcd == 1) {
        cout << "setwise coprime\n";
        return;
    }

    cout << "not coprime\n";
    return;
}

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

    int tc = 1;
    // cin >> tc;
    while (tc--) {
        solve();
    }
}


Measured memory_bytes: 12420
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#define last(x, y) (x)[(x).size() - (y)]
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define in(X) ((X) - '0')
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7;
const ll hs = 199;
//const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

bool inv = false;
int n, mx = 0;
int a[50];
vector<pair<int, int>> op;

void add(int x, int y) {
	if (!inv) op.push_back({ x + 1, y + 1 });
	else op.push_back({ n - x, n - y });
}

int main() {
	fast;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (abs(a[i]) > abs(mx)) mx = a[i];
	}
	if (mx < 0) {
		inv = true;
		for (int i = 0; i < n - i - 1; i++)
			a[i] = -a[i], a[n - i - 1] = -a[n - i - 1], swap(a[i], a[n - i - 1]);
		mx = -mx;
	}
	int x = -1;
	while (a[++x] != mx);
	add(x, 0), add(x, 0);
	for (int i = 1; i < n; i++) {
		add(i - 1, i), add(i - 1, i);
	}
	cout << op.size() << endl;
	for (auto &i : op) cout << i.first << " " << i.second << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

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

    string S; cin >> S;

    if(S[2] == S[3] && S[4] == S[5]) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;

}

Measured memory_bytes: 256
NIL = -1
class Node:
    parent = NIL
    left = NIL
    right = NIL
    type = NIL
    depth = NIL
    sibling = NIL
    degree = NIL
    height = NIL
    
def setHeight(u):
    h1 = h2 = 0
    if T[u].right != NIL:
        h1 = setHeight(T[u].right) + 1
    if T[u].left != NIL:
        h2 = setHeight(T[u].left) + 1
    if h1 == h2 == NIL:
        return NIL
    else:
        return max(h1,h2)

def getDepth(u):
    d = 0
    while T[u].parent != NIL:
        u = T[u].parent
        d += 1
    return d

def getSibling(u):
    if T[u].parent == NIL:
        return NIL
    if T[T[u].parent].left != u and T[T[u].parent].left != NIL:
        return T[T[u].parent].left
    if T[T[u].parent].right != u and T[T[u].parent].right != NIL:
        return T[T[u].parent].right
    return NIL

def getDegree(u):
    deg = 0
    if T[u].left != NIL:
        deg += 1
    if T[u].right != NIL:
        deg += 1
    return deg

n = int(input())
T = [0]*n

for i in range(n):
    T[i] = Node()
for i in range(n):
    id,l,r = map(int,input().split())
    T[id].left = l
    T[id].right = r
    
for i in range(n):
    if T[i].left != NIL:
        T[T[i].left].parent = i
    if T[i].right != NIL:
        T[T[i].right].parent = i

for i in range(n):
    if T[i].parent == NIL:
        T[i].type = 'root'
    elif T[i].parent != NIL and (T[i].left != NIL or T[i].right != NIL):
        T[i].type = 'internal node'
    else:
        T[i].type = 'leaf'

for i in range(n):
    T[i].depth = getDepth(i)
    T[i].sibling = getSibling(i)
    T[i].degree = getDegree(i)
    T[i].height = setHeight(i)
for i in range(n):
    print('node ',i,': parent = ',T[i].parent,', sibling = ',T[i].sibling,', degree = ',T[i].degree,', depth = ',T[i].depth,', height = ',T[i].height,', ',T[i].type,sep = '')

Measured memory_bytes: 7872
n = int(input())
list_S = list(input())
left_W = 0
left_E = 0
right_W = list_S.count("W")
right_E = list_S.count("E")
ans = n

for i, s in enumerate(list_S):
    if s == "W":
        left_W += 1
        right_W -= 1
    elif s == "E":
        left_E += 1
        right_E -= 1

    if i == 0 and s == "W":
        ans = min(ans, right_E)
    elif i == n-1 and s == "E":
        ans = min(ans, left_W)
    else:
        ans = min(ans, left_W+right_E)

print(ans)

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

int main () {
  int N   , A[3][3] ; 
  int C[3][3]   ; 

  
  for( int i = 0 ; i < 3 ; i++){
    for (int j = 0 ; j < 3 ; j++){
      cin >> A[i][j] ; 
      C[i][j] = 0 ; 
    }
    
  }
  
  cin >> N ; 
  int  B[N] ; 
  
  for(int i = 0 ; i < N ; i++){
    cin >> B[i] ; 
  }
  
    
  for( int i = 0 ; i < 3 ; i++){
    for (int j = 0 ; j < 3 ; j++){
      for(int k = 0 ; k < N ; k++){
      	if(A[i][j] == B[k]){
        C[i][j] = 1 ; 
        }
      }
    }
  }
  
  for(int i = 0 ; i < 3 ; i++){
    if(C[0][i] * C[1][i] * C[2][i] == 1){
      cout << "Yes" << endl ; 
      return 0 ; 
    }
    
    else if(C[i][0] * C[i][1] * C[i][2] == 1){
      cout << "Yes" << endl ; 
      return 0 ; 
    }
    
    else if(C[0][0] * C[1][1] * C[2][2] == 1){
      cout << "Yes" << endl ; 
      return 0 ; 
    }
    
    else if(C[0][2] * C[1][1] * C[2][0] == 1){
      cout << "Yes" << endl ; 
      return 0 ; 
    }
    
  }
  
  cout << "No" << endl ; 
  

  
  
}



Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int long long
#define S second
#define F first
#define pb push_back
#define sz size()
using namespace std;
const int N=1e6+7;
const int mod=1e9+7;
int b[N],c[N],a[N],dp[N],ans[N] ;
int n,x=1,k,w,m,y ;
vector < int > vec ;
vector < int > adj[N] ;
multiset < int > st ;
void dfs(int x)
{
    for (auto z : adj[x])
    {
        dp[z]=max(dp[z],dp[x]+1) ;
        a[z]-- ;
        if (a[z]==0)
            dfs(z),a[z]=-1 ;
    }
}
main()
{
    cin >> n >> m ;
    for (int i=1; i<=m ; i++)
    {
        cin >> x >> y ;
        adj[x].pb(y) ;
        a[y]++ ;
    }
    for (int i=1; i<=n; i++)
        if (a[i]==0)
            dfs(i) ;
    y=0 ;
    for (int i=1; i<=n; i++)
        y=max(y,dp[i]);
    cout << y << endl ;

}



Measured memory_bytes: 37792
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  ll s = 0;
  map<ll, ll> mp;
  for(int i=0;i<n;i++){
    ll t;std::cin >> t;
    s += t;
    auto itr = mp.find(t);
    if(itr==mp.end()) mp.emplace(t, 1);
    else (*itr).second++;
  }
  ll q;std::cin >> q;
  for(int i=0;i<q;i++){
    ll a, b;std::cin >> a >> b;
    auto itr = mp.find(a);
    if(itr==mp.end()){
      std::cout << s << '\n';
      continue;
    }
    ll num = (*itr).second;
    mp.erase(itr);
    auto tt = mp.find(b);
    if(tt==mp.end()) mp.emplace(b, num);
    else (*tt).second += num;
    ll sa = (b - a)*num;
    s += sa;
    std::cout << s << '\n';
  }

  return 0;
}


Measured memory_bytes: 7116
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <queue>
#include <map>
#include <cstdio>
#include <cmath>
#include <unordered_map>
#include <iomanip>
using namespace std;

int main() {
  int c = 0, d = 0;
  string s;
  cin >> s;
  int n = s.length();
  if (n % 2 == 0){
    for (int i = 0; i < n/2; i++){
      if (s.at(i) != s.at(n-1-i)){
        c++;
      }
    }
  }
  else{
    for (int i = 0; i < (n-1)/2; i++){
      if (s.at(i) != s.at(n-1-i)){
        d++;
      }
    }
  }
  cout << max(c,d) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
using namespace std;
using ll = long long;
 
int main() {
	int n;
	cin >> n;
	vector <int> a(n);
	for (int i =0; i < n ; i++) cin >> a[i];
	int count =0;
	for (int i =1; i < n-1 ; i++) {
		if (a[i] > a[i-1] && a[i] > a[i+1]) continue;
		if (a[i] < a[i-1] && a[i] < a[i+1]) continue;
		count++;
	}
	cout << count << endl;
	return 0;
}


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

ll Pow(ll a, ll n) {
  if (n == 1) return a;
  if (n % 2 == 1) return (a * Pow(a, n-1));
  ll t = Pow(a, n/2);
  return (t*t);
}

int main() {
  int N, P;
  cin >> N >> P;
  bool odd = false;
  for (int i = 0; i < N; i++) {
    int tmp;
    cin >> tmp;
    if (tmp % 2 == 1) {
      odd = true;
      break;
    }
  }
  if (!odd) {
    if (P % 2 == 0) cout << Pow(2, N);
    else cout << 0 << endl;
  }
  else cout << Pow(2, N-1);
}


Measured memory_bytes: 256
X,Y = map(int,input().split())
P = 10**9 + 7
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

if (X+Y)%3 != 0:
    ans = 0
elif min(X,Y)*2 < max(X,Y):
    ans = 0
else:
    A = (min(X,Y)-abs(X-Y))//3+abs(X-Y)
    B = (min(X,Y)-abs(X-Y))//3
    ans = 1
    for i in range(A):
        ans = ans*(A+B-i)%P
    for i in range(1,A+1):
        ans = ans*mod_inv(i,P)%P
print(ans)


Measured memory_bytes: 41068
n = int(input())
a = list(map(int, input().split()))

e = 0
o = 0
for i in a:
    if i % 2 == 0:
        e += 1
    else:
        o += 1 

ans = 3 ** len(a) - (2 ** e) * (1 ** o) 
print(ans)

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

public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        int test_cases = 1;
        Solver s = new Solver();
        for (int i = 1; i <= test_cases; i++) {
            s.solve(i, in, out);
        }
        out.close();
    }
}

class Solver {
    void solve(int test_number, InputReader in, PrintWriter out) throws IOException {
        int n = in.nextInt();
        out.println((n / 10 == 9 || n % 10 == 9) ? "Yes" : "No");
    }
}


class InputReader {
    BufferedReader br;
    StringTokenizer st;

    public InputReader()
    {
        br = new BufferedReader(new
                InputStreamReader(System.in));
    }

    String next()
    {
        while (st == null || !st.hasMoreElements())
        {
            try
            {
                st = new StringTokenizer(br.readLine());
            }
            catch (IOException  e)
            {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

    long nextLong()
    {
        return Long.parseLong(next());
    }

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

    String nextLine()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
}

Measured memory_bytes: 21460
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)n; i++)
#define REPvec(itr, mp) for (auto itr = mp.begin(); itr != mp.end(); itr++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007  // 1e9+7
using namespace std;
typedef long long int ll;
typedef vector<int> vecint;
typedef vector<ll> vecll;
typedef vector<string> vecstr;
typedef vector<bool> vecbool;
typedef vector<vector<int>> vec2int;
typedef pair<int, int> P;
////////////////////////////////////////////////
void init() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
}
////////////////////////////////////////////////
int main() {
  init();
  int n;
  cin >> n;
  vecint a(n, 0);
  for (auto &e : a) cin >> e;
  map<int, int> mp1, mp2;
  REP(i, n) {
    mp1[a[i] + i]++;
    mp2[i - a[i]]++;
  }
  ll ans = 0;
  REPvec(itr, mp1) {
    if (mp2.count(itr->first)) {
      ans += (ll)itr->second * (ll)mp2[itr->first];
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 21292
#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#include <functional>
#include <bitset>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef pair<ll,ll> P;
typedef vector<P> vpl;
typedef tuple<ll,ll,ll> tapu;
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(int i=(a); i<(b); i++)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const int inf = 1<<30;
const ll linf = 1LL<<62;
const int MAX = 510000;
ll dy[8] = {0,1,0,-1,1,-1,1,-1};
ll dx[8] = {1,0,-1,0,1,-1,-1,1};
const double pi = acos(-1);
const double eps = 1e-7;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){
	if(a>b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){
	if(a<b){
		a = b; return true;
	}
	else return false;
}
template<typename T1,typename T2> inline void print2(T1 a, T2 b){cout << a << " " << b << "\n";}
template<typename T1,typename T2,typename T3> inline void print3(T1 a, T2 b, T3 c){
	cout << a << " " << b << " " << c << "\n";
}
const int mod = 1e9 + 7;
//const int mod = 998244353;

int calc(string s, map<char,int> mp){
	ll res = 0;
	rep(i,s.size()){
		if('2'<=s[i]&&s[i]<='9'){
			res += (s[i]-'0')*mp[s[i+1]];
			i++;
		}else{
			res += mp[s[i]];
		}
	}
	return res;
}

int main(){
	map<char,int> mp;
	mp['m'] = 1000; mp['c'] = 100; mp['x'] = 10; mp['i'] = 1;
	string mcxi = "mcxi";
	ll q; cin >> q;
	while(q--){
		string s,t; cin >> s >> t;
		ll ret = calc(s,mp) + calc(t,mp);
		ll now = 1000;
		string ans;
		rep(i,4){
			if(ret / now >= 2){
				ans.push_back((char)(ret/now+'0'));
				ans.push_back(mcxi[i]);
			}
			else if(ret / now == 1) ans.push_back(mcxi[i]);
			ret = ret % now;
			if(ret == 0) break;
			now /= 10;
		}
		cout << ans << endl;
	}
}


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

using namespace std;

int main () {
  int n, k;
  cin >> n >> k;
  vector<int> p(n, 0);
  for (int i = 0; i < n; i++)
    cin >> p[i];
  sort(p.begin(), p.end());
  int s = 0;
  for (int i = 0; i < k; i++)
    s += p[i];
  cout << s;
}


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

int main(){
  int n;
  cin>>n;
  char s[n];
  for(int i=0;i<n;i++){
    cin>>s[i];
  }
  int a;
  cin>>a;
  a--;
  for(int i=0;i<n;i++){
    if(s[i]!=s[a]) s[i]='*';
    cout<<s[i];
  }
  cout<<endl;
}

Measured memory_bytes: 256
n,k = map(int,input().split())
v = list(map(int,input().split()))
r = min(n,k)
ans = -10**10
for i in range(0,r+1):
  for a in range(i+1):
    b = i - a
    val = sorted(v[:a]+v[(n-b):])
    s = sum(val)
    for j in range(min(k-i,len(val))):
      if val[j] < 0:
        s -= val[j]
      else:
        break
    ans = max(ans,s)
print(ans)

Measured memory_bytes: 3064