akhauriyash/Code-Regression huggingface dataset:
use std::collections::HashSet;
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn usize() -> usize {
    read()
}

fn vec_usize(n: usize) -> Vec<usize> {
    let mut vec = Vec::new();
    for _ in 0..n {
        vec.push(usize())
    }
    vec
}

fn main() {
    let nm = vec_usize(2);
    let n = nm[0];
    let m = nm[1];

    let mut ms: HashSet<usize> = HashSet::new();
    for i in 0..m {
        ms.insert(i + 1);
    }

    for _ in 0..n {
        let mut not_ms: HashSet<usize> = HashSet::new();
        for i in 0..m {
            not_ms.insert(i + 1);
        }
        let k = usize();
        let ks = vec_usize(k);
        for i in 0..k {
            not_ms.remove(&ks[i]);
        }
        let nms: Vec<usize> = not_ms.into_iter().collect();
        for i in 0..nms.len() {
            ms.remove(&nms[i]);
        }
    }

    println!("{}", ms.len());
}


Measured memory_bytes: 2196
#include <bits/stdc++.h>
/*
#include<algorithm>
#include<array>
#include<cassert>
#include<cmath>
#include<cstdlib>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<typeinfo>
#include<utility>
#include<vector>
*/
#define int long long int
#define double long double
using namespace std;
#define MOD 1000000007
#define INF 1000000000000000007
const int MAX_N = 1 << 17;
#define rep(i, n) for (int(i) = 0, i##_len = (n); (i) < i##_len; (i)++)
#define reps(i, x) for (int(i) = 1; (i) <= (int)(x); (i)++)
#define rrep(i, x) for (int(i) = ((int)(x)-1); (i) >= 0; (i)--)
#define rreps(i, x) for (int(i) = ((int)(x)); (i) > 0; (i)--)
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define pb push_back
#define mp make_pair
#define bit(n) ((int)(1) << (n))
#define all(x) (x).begin(), (x).end()
#define debug(x) std::cout << #x << ": " << (x) << std::endl
#define nint int
using namespace std;

int dy[] = {0, 0, 1, -1, 0};
int dx[] = {1, -1, 0, 0, 0};
typedef pair<int, int> pii;
typedef pair<double, double> dop;
template <class T>
bool chmax(T& a, const T& b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T& a, const T& b)
{
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
struct aaa {
    aaa()
    {
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout << fixed << setprecision(20);
    };
} aaaaaaa;


signed main()
{
    int n, m;
    cin >> n >> m;
    std::vector<int> s(n);
    std::vector<int> t(m);
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> t[i];
    }
    int out = 1;

    std::vector<std::vector<int>> check(n, std::vector<int>(m, 0));
    std::vector<std::vector<int>> summ(n, std::vector<int>(m, 0));
    for (int i = 0; i < n; i++) {
        std::vector<int> count(m, 0);
        for (int j = 0; j < m; j++) {
            if (s[i] == t[j]) {
                check[i][j]++;
                check[i][j] %= MOD;
            }
            if (i > 0 && j > 0 && s[i] == t[j]) {
                check[i][j] = (check[i][j] + summ[i - 1][j - 1]) % MOD;
            }
            count[j] = check[i][j];
            if (j > 0) {
                count[j] = (count[j] + count[j - 1]) % MOD;
            }
            summ[i][j] = count[j];
            if (i > 0) {
                summ[i][j] = (summ[i - 1][j] + summ[i][j]) % MOD;
            }
            /*if (j > 0) {
                summ[i][j] = (summ[i][j] + summ[i][j - 1]) % MOD;
            }*/
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            out = (out + check[i][j]) % MOD;
        }
    }
    cout << out << endl;

    return 0;
}

Measured memory_bytes: 62976
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main() {
  int n,a,i,j,count=0,frag=0;
  double sqrta;
  scanf("%d",&n);
  if(n<1 || n>10000) exit(8);
  for(i=0;i<n;i++)
    {
      scanf("%d",&a);
      if(a>=2 && n<=100000000)
	{
	  if(a == 2)
	    {
	      count++;
	      continue;
	    }
	  else if(a%2 == 0) continue;

	  sqrta = sqrt(a);
	  for(j=3;j<=sqrta;j+=2)
	    {
	      if(a%j == 0)
		{
		  frag = 1;
		  break;
		}
	    }
	  if(frag == 0)
	    {
	      count++;
	    }
	  frag = 0;
	}
    }
  printf("%d\n",count);
  return 0;
}
  



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

namespace TYC
{
	typedef long long ll;
	typedef pair<int, int> pii;

	const int N = 1e5 + 5;

	int n, A[N], B[N], Mark[N], P[N];
	pii C[N << 2];

	inline int read()
	{
		int x = 0, f = 0, ch = getchar();
		while (!isdigit(ch))
			f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))
			x = x * 10 + ch - '0', ch = getchar();
		return f ? -x : x;
	}

	ll solve()
	{
		int flag = 0, cnt = 0;
		ll ans = 0;
		memset(Mark, 0, sizeof(int[n + 1]));
		for (int i = 1; i <= n; i++)
		{
			ans += C[P[i]].first;
			int p = C[P[i]].second;
			if (p > n)
				p -= n, cnt++;
			if (++Mark[p] == 2)
				flag = 1;
		}
		return (flag || !cnt || cnt == n) ? ans : LLONG_MAX;
	}

	void work()
	{
		n = read();
		for (int i = 1; i <= n; i++)
		{
			C[i] = pii(read(), i);
			C[i + n] = pii(read(), i + n);
		}
		sort(C + 1, C + 1 + (n << 1));
		for (int i = 1; i <= n; i++)
			P[i] = i;	
		ll ans = solve();
		P[n] = n + 1;
		ans = min(ans, solve());
		P[n] = n + 2;
		ans = min(ans, solve());
		P[n - 1] = n, P[n] = n + 1;
		ans = min(ans, solve());
		printf("%lld\n", ans);
	}
}

int main()
{
	TYC::work();
	return 0;
}

Measured memory_bytes: 6108
D = [[-1, 0], [1, 0], [0, -1], [0, 1]]

def puyo_rensa(old, cnt)
  check = 14.times.map{ [false] * 8 }
  res = 0
  (1..12).each do |i|
    (1..6).each do |j|
      if !check[i][j] && old[i][j] =~ /[^O.]/
        puyo_connector(i, j, old){ |arr|
          if arr.size >= 4
            arr.each do |s, t|
              D.each do |x, y|
                p, q = s + x, t + y
                check[p][q] = true if old[p][q] == 'O'
              end
              check[s][t] = true
            end
            res = 1
          end
        }
      end
    end
  end
  fld = puyo_eraser(old, check)
  if res == 1 then puyo_rensa(fld, cnt + 1)
  else cnt
  end
end

def puyo_connector(i, j, fld)
  check = 14.times.map{ [false] * 8 }
  arr = [[i, j]]
  ret = [[i, j]]
  check[i][j] = true
  until arr.empty?
    i, j = arr.shift
    D.each do |x, y|
      p, q = i + x,  j + y
      if !check[p][q] && fld[i][j] == fld[p][q]
        check[p][q] = true
        arr << [p, q]
        ret << [p, q]
      end
    end
  end
  yield(ret)
end

def puyo_eraser(fld, check)
  nfld = 14.times.map{ |i| fld[i].dup }
  pos = [0] * 7
  13.downto(0) do |i|
    (1..6).each do |j|
      if check[i][j]
        (1..i).each do |k|
          nfld[k + pos[j]][j] = fld[k - 1][j]
        end
        nfld[pos[j]][j] = '.'
        pos[j] += 1
      end
    end
  end
  nfld
end

gets.to_i.times do
  fld = 14.times.map{ ['.'] * 8 }
  12.times do |i|
    gets.chomp.split('').each_with_index do |c, j|
      fld[i+1][j+1] = c
    end
  end
  p puyo_rensa(fld, 0)
end

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

const unsigned long long MOD = 1000000007;

int main()
{
    //! Let x the number of inverted number in A
    //! the number of inverted number in B is 
    int N;
    unsigned long long K;
    cin >> N >> K;

    vector<int> A;
    for (int i = 0; i < N; ++i) {
        int a;
        cin >> a;
        A.push_back(a);
    }

    unsigned long long numInvertedInFirst = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = i+1; j < N; ++j) {
            if (A[j] < A[i]) {
                ++numInvertedInFirst;
            }
        }
    }

    unsigned long long numInvertedInSecond = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (A[j] < A[i]) {
                ++numInvertedInSecond;
            }
        }
    }

    //! the first A has numInvertedInFirst inverted pairs in it
    //! the seond A adds numInvertedInSecond inverted pairs against the first A
    //! the third A adds 2 * numInvertedInSecond inverted pairs agasint the first 2 A's
    //! the n'th A adds (n-1) * numInvertedInSecond inverted pairs against the first (n-1) A's
    //! therefore the number of inverted pairs in K repetion of A's 
    //!   = numInvertedInFirst * K + (1 + 2 + ... (K-1))numInvertedInSecond
    //!   = numInvertedInFirst * K + K(K-1)/2 numInvertedInSecond

    //! overflow check
    //! numInvertedInSecond = O(N^2)
    //! K(K-1)/2 = O(K^2)
    //! K(K-1)/2 numInvertedInSecond = O(N^2 K^2)
    //!   As N <= 2000 and K <= 10^9
    //!   O(N^2 K^2) = O(10^21)
    //! This means K^2 can fit in unsigned long long, but N^2 K^2 do not

    unsigned long long ans = (numInvertedInFirst * K + ((K * (K-1) / 2) % MOD) * numInvertedInSecond) % MOD;

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
N,M = map(int,input().split())
H = list(map(int,input().split()))
connect = [[0] for _ in range(N)]

ans = 0

for i in range(M):
    A,B = map(int,input().split())
    connect[A-1].append(H[B-1])
    connect[B-1].append(H[A-1])

for i in range(N):
    if H[i] > max(connect[i]):
        ans += 1
        
print(ans)

Measured memory_bytes: 26012
n = int(input())
l = list(map(int,input().split()))

def upright(ll):
    for i in range(len(ll)-1):
        if ll[i]>ll[i+1]:
            return False
    return True

if upright(l):
    print("YES")
    exit(0)

for i in range(n):
    for j in range(i+1,n):
        tmp = l[i]
        l[i] = l[j]
        l[j] = tmp
        if upright(l):
            print("YES")
            exit(0)
        tmp = l[i]
        l[i] = l[j]
        l[j] = tmp
print("NO")




Measured memory_bytes: 3064
/*
Author: Babin Dutta
*/
 
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mp make_pair
#define boost ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define f(i,n) for(int i=0;i<n;i++)
#define ff(i,a,b) for(int i=a;i<=b;i++)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define endl "\n"
#define inf 1e18
#define mm 998244353
 
ll power(ll x, ll y, ll p)
{
    ll res = 1;  
    x = x % p;  
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1; 
        x = (x*x) % p;  
    }
    return res;
}
ll modInverse(ll A,ll M)
{
    return power(A,M-2,M);
}

void solve(){
    int a,b,k; cin>>a>>b>>k;
    vector<int> v;
    for(int i=1;i<=min(a,b);i++){
    	if(a%i == 0 && b%i == 0) v.pb(i);
	}
	cout<<v[v.size()-k]<<endl;
}
 
int main(){
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	boost;
	int t=1; //cin>>t;
	for(int i=1;i<=t;i++) solve();
	return 0;
}

Measured memory_bytes: 3672
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define INF INT_MAX;
typedef long long ll;
using namespace std;


int main(){
  int n;
  cin >> n;
  int cont[n]['z'-'a'+1]={0};
  rep(i,n){
    string s;
    cin >> s;
    sort(all(s));
    for(int j=0;j<s.size();j++){
      cont[i][s.at(j)-97]++;
    }
  }

  for(int i=0;i<'z'-'a'+1;i++){
    int m = INF;
    for(int j=0;j<n;j++){
      int x = cont[j][i];
      m = min(x,m);
    }

    for(int k=0;k<m;k++){
      printf("%c",'a'+i);
    }

  }
}

Measured memory_bytes: 256
import sys
from collections import deque

S = input()
Q = int(input())
QUERY = sys.stdin.readlines()

state = 0
q1 = deque()
q2 = deque()
for i in range(Q):
    query = QUERY[i]
    if query[0] == '1':
        state ^= 1
    else:
        _, F, C = query.split()
        F = int(F)
        if (state + F) % 2 == 1:
            q1.appendleft(C)
        else:
            q2.append(C)

ans = ''
if state == 0:
    while q1:
        ans += q1.popleft()
    ans += S
    while q2:
        ans += q2.popleft()
else:
    while q2:
        ans += q2.pop()
    ans += ''.join(list(reversed(S)))
    while q1:
        ans += q1.pop()
print(ans)


Measured memory_bytes: 18532
a = [int(input()) for i in range(int(input()))]
a_s = sorted(a)[::-1]
mx, submx = a_s[0], a_s[1]
cnt = a.count(mx)
for n in a:
    if n!=mx: print(mx)
    elif cnt>1: print(mx)
    else: print(submx)

Measured memory_bytes: 14616
#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<cmath>
#include <algorithm>
using namespace std;
using ll = long long;

typedef pair<int,int> P;
 
int main(void){
    string S,T;
    cin >>S>>T;
    int min=T.length();
    for(int m=0;m<S.length()-T.length()+1;m++){
        int misCount=0;
        for(int k=0;k<T.length();k++){
            if(S[m+k]!=T[k]){
                misCount++;
            }
        }
        if(min >misCount){
            min=misCount;
        }
    }
    cout <<min<<endl;

}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
int main(){
  int64_t L[87];
  L[0]=2;
  L[1]=1;
  
  int x;
  cin >> x;
  for (int i=2;i<=x;i++){
    L[i] = L[i-2]+L[i-1];
  }
  cout << L[x] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <math.h>
using namespace std;

int main(){

    int n,k;cin>>n>>k;
    int tmp;
    int cnt=0;

    for(int i=0;i<n;++i){
        cin>>tmp;
        if(tmp>=k){
            cnt++;
        }
    }

    cout<<cnt<<endl;


}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
n = int(input())
a = list(map(int,input().split()))

#最小値と最大値の間の値になる。
min_a = min(a)
max_a = max(a)

cost = []

i = min_a
while i <= max_a:
    cost.append(sum(map(lambda x:(x-i)**2,a)))
    i+=1
print(min(cost))


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

int a[3][3];


string sol(map<int,int> hash){
	int flag = 0;

	//2 
	if(hash[a[0][0]] and hash[a[0][1]] and hash[a[0][2]]){
		return "Yes";
	}
	//3 
	if(hash[a[0][0]] and hash[a[1][0]] and hash[a[2][0]]){
		return "Yes";
	}
	//4 
	if(hash[a[2][0]] and hash[a[1][1]] and hash[a[0][2]]){
		return "Yes";
	}
	// 5
	if(hash[a[1][0]] and hash[a[1][1]] and hash[a[1][2]]){
		return "Yes";
	}
	//6
	if(hash[a[0][1]] and hash[a[1][1]] and hash[a[2][1]]){
		return "Yes";
	}
	// 7
	if(hash[a[0][2]] and hash[a[1][2]] and hash[a[2][2]]){
		return "Yes";
	}
	// 8
	if(hash[a[2][0]] and hash[a[2][1]] and hash[a[2][2]]){
		return "Yes";
	}

	if(hash[a[0][0]] and hash[a[1][1]] and hash[a[2][2]]){
		return "Yes";
	}

	return "No";
}

int main(){
	
	map<int,int> hash;

	for(int i = 0; i < 3; i++){
		for(int j = 0; j < 3; j++){
			int x; cin>>x;
			a[i][j] = x; 

		}
	}

	int n; cin>>n;
	for(int i = 0; i < n; i++){
		int x; cin>>x;
		hash[x]++;
	}
	cout<<sol(hash);


}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<limits.h>
#include<math.h>

using namespace std;
#define MOD 1000000007


static long long int fact[200000] = { 0 };

long long int factrial(long long int num) {
	if (num == 0)return 1;
	if (num == 1)return 1;
	if (fact[num] != 0)return fact[num];

	long long int ans = 1;

	ans = num * factrial(num - 1) % MOD;
	fact[num] = ans;
	return ans;



}

long long int superpow(long long int num, long long int count) {
	if (count == 0)return 1;
	if (count == 1)return num;

	long long int wk = superpow(num, count / 2);

	if (count % 2 == 0)return (wk * wk) % MOD;

	return (((wk * wk) % MOD) * num) % MOD;

}

long long int inv(long long int num) {

	return superpow(num, MOD - 2) % MOD;

}

//nCrのやつ
long long int comb(long long int n, long long int r) {
	if (n == r)return 1;
	if (r == 0)return 1;
	long long int ans = 1;

	ans = factrial(n);

	long long int wk = 1;

	wk = factrial(r);
	
	ans = (ans * inv(wk)) % MOD;

	wk = 1;
	
	wk = factrial(n - r);

	ans = (ans * inv(wk)) % MOD;

	return ans;
}

long long int min(long long int a, long long int b) {
	if (a > b)return b;
	return a;



}

int main()
{
	int n, m;

	cin >> n >> m;

	int a[30][30];
	int k[30];
	for (int i = 0; i < n; i++) {
		cin >> k[i];

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

	int ans[30] = { 0 };

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < k[i]; j++) {
			ans[a[i][j] - 1]++;
		}
	}
	
	int anscount = 0;

	for (int i = 0; i < m; i++) {
		if (ans[i] == n)anscount++;


	}

	cout << anscount << endl;








	return 0;



}



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

int main(){
  int R,G,B,N,a=0;
  cin >> R >> G >> B >> N;
  for(int i=0; i*R<=N; i++){
    for(int j=0; i*R+j*G<=N; j++){
      if((N-i*R-j*G)%B==0){
        a++;
      }
    }
  }
  cout << a << endl;
}

Measured memory_bytes: 764
#include<stdio.h>
main()
{
    char a[4];
    int i;
    while(scanf("%s",a)==1){
        for(i=0;i<=2;i++){
            if(a[i]==a[i+1]){
                printf("Bad\n");
                break;
            }
        }
        if(i==3){
            printf("Good\n");
        }
    }
}


Measured memory_bytes: 128
def fee(w):
  acc = 1150
  if w <= 10:
    return acc
  w -= 10
  if w <= 10:
    return acc + 125 * w
  acc += 1250
  w -= 10
  if w <= 10:
    return acc + 140 * w
  acc += 1400
  w-= 10
  return acc + 160 * w



while True:
  w = int(input())
  if w == -1:
    break
  print(4280 - fee(w))


Measured memory_bytes: 5596
#include <bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
ifstream in("in.txt");
vector<int>a;
int n;
void hah(int k, int j){
    if(j==n){
        for(auto it:a){
            cout<<char('a'+it);
        }
        cout<<"\n";
        return;
    }
    for(int i=0; i<=k; ++i){
        a.push_back(i);
        hah(k,j+1);
        a.pop_back();
    }
    if(k+1<=j){
        a.push_back(k+1);
        hah(k+1, j+1);
        a.pop_back();
    }
}
int main(){
    cin>>n;
    hah(0,0);
    return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;


//void warshall_floyd(int n){
//    for(int k=0;k<n;k++){
//        for(int i=0;i<n;i++){
//            for(int j=0;j<n;j++){
//                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
//            }
//        }
//    }
//}
//ll calc_digit(ll N) {
//    ll res = 0;
//    while (N) {
//        ++res;
//        N /= 10;
//    }
//    return res;
//}
//ll sum_digit(ll N) {
//    ll res = 0;
//    while (N) {
//        res += N % 10;
//        N /= 10;
//    }
//    return res;
//}


int main() {
    int n; cin >> n;
    multimap<ll,ll> m;
    ll sum = 0;
    for(int i = 0;i < n;i++){
        ll a; cin >> a;
        sum += a;
        if(m.find(a) == m.end()){
            m.insert(make_pair(a,1));
        }else{
            m.find(a)->second++;
        }
    }
    int q; cin >> q;
    for(int i = 0;i < q;i++){
        ll s,t; cin >> s >> t;
        auto e = m.find(s);
        auto f = m.find(t);
        if(e == m.end()) m.insert(make_pair(s,0));
        if(f == m.end()) m.insert(make_pair(t,0));
        auto x = m.find(s);
        auto y = m.find(t);
        sum -= s*x->second;
        sum -= t*y->second;
        y->second+=x->second;
        x->second = 0;
        sum += t*y->second;
        cout << sum << endl;
    }
}




Measured memory_bytes: 9380
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;
#define INF (1 << 30) - 1
#define LINF 1LL << 60
using ll = long long;
using P = pair<int, int>;

const int mod = 1000000007;
struct mint {
  ll x; 
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};

mint f(int n){ 
  if(n == 0)return 1;
  mint x = f(n / 2); 
  x *= x; 
  if(n % 2 == 1)x *= 2;
  return x;
}

mint choose(int n, int a){
  mint x = 1, y = 1;
  for(int i = 0; i < a; ++i){
    x *= n - i;
    y *= i + 1;
  }
  return x / y;
}


int n;
vector<vector<int>> g;

mint fact[1001000];
mint inv_fact[1001000];

void init(){
	fact[0] = 1;
	inv_fact[0] = 1;
	for(int i = 1; i < 1001000; ++i){
		fact[i] = fact[i - 1] * (mint)i;
		inv_fact[i] = (mint)1 / fact[i];
	}
}

mint dp1[200100];
mint dp2[200100];

vector<int> sub_size;
vector<int> sub_size2;
void dfs1(int v, int p = -1){
	sub_size[v] = 1;
	dp1[v] = 1;
	for(auto nv : g[v]){
		if(nv == p)continue;
		dfs1(nv, v);
		sub_size[v] += sub_size[nv];
		dp1[v] *= dp1[nv] * inv_fact[sub_size[nv]];
	}
	dp1[v] *= fact[sub_size[v] - 1];
}

void dfs2(int v, int p = -1, mint d_par = 1, int size_par = 0){
	mint div = 1;
	dp2[v] = 1;
	sub_size2[v] = 1;
	for(auto nv : g[v]){
		if(nv == p){
			sub_size2[v] += size_par;
			dp2[v] *= d_par * inv_fact[size_par];
			div *= d_par * inv_fact[size_par];
		}
		else{
			sub_size2[v] += sub_size[nv];
			dp2[v] *= dp1[nv] * inv_fact[sub_size[nv]];
			div *= dp1[nv] * inv_fact[sub_size[nv]];
		}
	}

	dp2[v] *= fact[n - 1];

	for(auto nv : g[v]){
		if(nv == p)continue;
		mint cnt = fact[sub_size[nv]] * div;
		cnt *= fact[n - 1 - sub_size[nv]] / dp1[nv];
		dfs2(nv, v, cnt, n - sub_size[nv]);
	}
}

int main(){
  init();
  cin >> n;
  g.resize(n);
  for(int i = 0; i < n - 1; ++i){
  	int a, b;
  	cin >> a >> b;
  	--a;
  	--b;
  	g[a].push_back(b);
  	g[b].push_back(a);
  }

  sub_size.resize(n);
  sub_size2.resize(n);
  dfs1(0);
  dfs2(0);
  for(int i = 0; i < n; ++i)cout << dp2[i].x << endl;
  return 0;
}


Measured memory_bytes: 34292
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

def cmb_1(n, r):
    if n < r:
        return 0
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

N, M = getNM()
A = getList()

alta = []
for i in A:
    alta.append(i % M)

imos = [0]
for i in range(N):
    imos.append((alta[i] + imos[i]) % M)

ans = 0
for i in Counter(imos).values():
    ans += cmb_1(i, 2)
print(ans)

Measured memory_bytes: 109108
n = STDIN.gets.to_i
t, a = STDIN.gets.strip.split(" ").map(&:to_i)
hs = STDIN.gets.strip.split(" ").map(&:to_i)
ds = hs.map { |h| (a - (t - h * 0.006)).abs() }.map.with_index { |v, i| [v,i] }.sort_by { |v, i| v }
puts ds[0][1] + 1

Measured memory_bytes: 1912
#include "bits/stdc++.h"
#include <iostream>
using namespace std;
const double EPS = 1e-10;

int main() {

	complex<double> a, b, c, d, e, f;
	while (cin >> a.real() >> a.imag() >> b.real() >> b.imag() >> c.real()
			>> c.imag() >> d.real() >> d.imag()) {
		e = a - b;
		f = c - d;
		if (abs(e.real() * f.real() + e.imag() * f.imag()) < EPS) {
			cout << "YES" << endl;
		} else {
			cout << "NO" << endl;
		}
	}
}

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

int main()
{
        int N;
        cin >> N;
        int D;
        int X;
        cin >> D >> X;
        int a[N];

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

        int total = 0;
        int taberu = 0;
        for (int i = 0; i < N; ++i) {

                int tabeta = 0;
                for (int j = 0; j < D; ++j) {

                        taberu = a[i] * tabeta + 1;
                        if (j == taberu - 1) {
                                total++;
                                tabeta++;
                        }

                }
        }

        total += X;

        cout << total << endl;


}


Measured memory_bytes: 256
s = int(input())
n = input()
str_list = list(n)
w_cnt = str_list.count('W')
r_cnt = str_list.count('R')
if w_cnt == 0 or r_cnt == 0:
    print(0)
else:
    w_result = str_list[r_cnt:]
    r_result = str_list[:r_cnt]
    r = w_result.count('R')
    w = r_result.count('W')
    if w <= r:
        print(w)
    else:
        print(r)


Measured memory_bytes: 78008
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

A, B = map(int, input().split())

print("Possible" if len(list(filter(lambda x: x % 3 == 0, [A, B, A + B]))) > 0 else "Impossible")

Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define rep2(i,n) for(int i=0;i<=n;i++)
#define repr(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define P pair<long long,long long>
#define double long double
#define vector2(a,b,c) vector<vector<int>> a(b/*縦！w*/,vector<int>(c/*横！w*/))
#define INF 1e10
#define MOD 1e9+7
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; }
using Graph = vector<vector<int>>;
signed main(){
  int a,b;
  cin>>a>>b;
  vector<int> c(b);
  rep(i,b)
    cin>>c[i];
  int d=0;
  rep(i,b){
  d+=c[i];
  }
    if(a<=d)
      cout<<"Yes";
  else
    cout<<"No";
}


Measured memory_bytes: 1024
def check(m):
    tmpa = [-1] * 2 * n
    for i in xrange(2 * n - 1):
        if a[i] < m:
            tmpa[i] = 0
        else:
            tmpa[i] = 1

    idx = n -1
    while idx < 2 * n - 1:
        idx += 1
        if tmpa[idx - 1] == tmpa[idx]:
            rr = tmpa[idx]
            ridx = idx - 1
            break
    else:
        rr = -1
        ridx = 2 * n - 1

    idx = n - 1
    while idx > 0:
        idx -= 1
        if tmpa[idx + 1] == tmpa[idx]:
            ll = tmpa[idx]
            lidx = idx + 1
            break
    else:
        ll = -1
        lidx = -1

    if rr == ll == -1:
        if n % 2 == 0:
            if tmpa[n - 1] == 1:
                return False
            else:
                return True
        else:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
    elif ridx - (n - 1) == (n - 1) - lidx:
        if rr != ll:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
        else:
            if rr==1:
                return True
            else:
                return False
    elif ridx - (n - 1) > (n - 1) -lidx:
        if ll == 1:
            return True
        else:
            return False
    else:
        if rr == 1:
            return True
        else:
            return False

n = int(raw_input())
a = map(int,raw_input().split())
l = 1
r = 2 * n
while r - l > 1:
    m = (r + l)/2
    if check(m):
        l = m
    else:
        r = m
print(l)

Measured memory_bytes: 19992
import java.util.*;

public class Main {
	Scanner sc = new Scanner(System.in);
	final int MOD = 1000000007;
	final int MAX = Integer.MAX_VALUE;
	final long LMAX = Long.MAX_VALUE;
	int len = (int)1e6 + 1;

	void doIt() {
		int A = sc.nextInt();
		int B = sc.nextInt();
		int H = sc.nextInt();
		int M = sc.nextInt();
		double argA = Math.PI * (double)H / 6.0 + Math.PI * (double)M / 6.0 / 60.0;
		double argB = Math.PI * (double)M / 30.0;
		double Ax = A * Math.cos(argA);
		double Ay = A * Math.sin(argA);
		double Bx = B * Math.cos(argB);
		double By = B * Math.sin(argB);
		double ans = Math.sqrt((Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By));
		System.out.println(ans);
	}

	
	
	public static void main(String[] args) {
		new Main().doIt();
	}

}


Measured memory_bytes: 35812
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main(){
    int N;
    int ans = 0;
    int a[110];
    cin >> N;
    for (int i = 0; i < N;i++)
        cin >> a[i];
    int num[110] = {0};
    for (int i = 0; i < N; i++){
        num[a[i]]++;
    }
    for (int i = 0; i <= 100;i++){
        if (num[i]) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num,init) vector<ll> name((num),(init));
#define op(i) cout<<(i)<<endl;
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define mat(name,fnum,snum,init); vector<vector<ll>> name((fnum),vector<ll>((snum),(init)));

int main(){
    mat(c,3,3,0);
    vec(a,2,0);
    vec(b,2,0);
    rep(i,3){
        rep(j,3){
            cin>>c[i][j];
        }
    }
    a[0]=c[0][1]-c[0][0];
    a[1]=c[0][2]-c[0][0];
    repf(i,1,3){
        if(a[0]!=c[i][1]-c[i][0]||a[1]!=c[i][2]-c[i][0]){
            opN;
            return 0;
        }
    }
    a[0]=c[1][0]-c[0][0];
    a[1]=c[2][0]-c[0][0];
    repf(i,1,3){
        if(a[0]!=c[1][i]-c[0][i]||a[1]!=c[2][i]-c[0][i]){
            opN;
            return 0;
        }
    }
    opY;
    return 0;

}

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

height=list(map(int,input().split()))

tower=[0]*N

for i in range(M):
    A,B=map(int,input().split())
    if height[A-1]<height[B-1]:
        tower[A-1]=1
    elif height[A-1]>height[B-1]:
        tower[B-1]=1
    else:
        tower[A-1]=1
        tower[B-1]=1
    
print(tower.count(0))

Measured memory_bytes: 20116
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
s=[]
for i in range(m):
    s.append(lmp())
p=lmp()
ans=0
for i in range(2**n):#全てのスイッチの入れ方
    ans+=1
    for j in range(m):#全ての電球に対するチェック
        c=0
        for k in range(1,s[j][0]+1):#各電球に対するチェック
            if ((i>>(s[j][k]-1)) & 1):
                c+=1
        if (c-p[j])%2==1:
            ans-=1
            break
print(ans)

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

int main() {
  int N;
  cin >> N;
  vector<int> vec(N, 0);

  for (int i = 0; i < N; i++) {
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  
  int alice = 0, bob = 0;
  for (int i = 0; i < N; i++) {
    if (i % 2 == 0) {
      alice += vec.at(i);
    }
    else {
      bob += vec.at(i);
    }
  }
  
  cout << alice - bob << endl;
}


Measured memory_bytes: 256
using System;

namespace _0184
{
    class Program
    {
        static void Main(string[] args)
        {
            while(true)
            {
                int n = int.Parse(Console.ReadLine());
                if(n==0)
                {
                    break;
                }
                int[] X = new int[7];
                for (int i = 0; i < n; i++)
                {
                    int now = int.Parse(Console.ReadLine());
                    if (now > 60)
                    {
                        X[6]++;
                    }
                    else
                    {
                        X[now / 10]++;
                    }
                }
                for (int i = 0; i < 7; i++)
                {
                    Console.WriteLine(X[i]);
                }
            }
        }
    }
}

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

int main(){
  long k, a, b;
  cin >> k >> a >> b;
  if(a+2>=b)cout << k+1;
  else {
    long bs=1;
    bool yen=false;
    for(int i=0; i<k; i++){
      if(yen){
        yen=false;
        bs+=b;
        continue;
      }
      if(bs>=a && i<k-1){
        bs-=a;
        yen=true;
      }
      else bs++;
    }
    cout << bs;
  }
  return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define int long long
//#define double long double
#define endre getchar();getchar();return 0
#define moder (int)(1e9+7)
#define inf (int)(3e18+7)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P pair<int,int>
#define all(v) v.begin(),v.end()
#define prique(T) priority_queue<T,vector<T>,greater<T>>
#define vecunique(vec) sort(vec.begin(), vec.end());decltype(vec)::iterator result = std::unique(vec.begin(), vec.end());vec.erase(result, vec.end())
using namespace std;

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x%mod;
		}
		x = x * x%mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)*mod_pow(kai(x - y), moder - 2, moder) % moder*mod_pow(kai(y), moder - 2, moder) % moder;
}
/*--------Library Zone!--------*/

int n, x, a[105], sum;
signed main() {
	cin >> n >> x;
	rep(i, n) {
		cin >> a[i];
		sum += a[i];
	}
	if (sum < x) {
		cout << n - 1 << endl;
		endre;
	}
	sort(a, a + n);
	rep(i, n) {
		if (x >= a[i]) {
			x -= a[i];
		}
		else {
			cout << i << endl;
			endre;
		}
	}
	cout << n << endl;
	endre;
}

Measured memory_bytes: 256
/*
    C
*/
#include <bits/stdc++.h>
#define MAX 105

using namespace std;

int N;
int ans, B[MAX];

int main() {
	ios::sync_with_stdio(0);
	cin >> N;
	B[0] = B[N] = INT_MAX;
	for(int i = 1; i < N; ++i) cin >> B[i]; 
	for(int i = 1; i <= N; ++i) ans += min(B[i], B[i - 1]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
int main() {
   ll int n;
   cin>>n;
   string s[n];
   ll count=0;
   for(int i=0;i<n;i++){
    cin>>s[i];
   }
   unordered_map<string,int> mp;
   for(int i=0;i<n;i++){

    if(mp.find(s[i])==mp.end())
    {
        count++;
        mp[s[i]]=1;
   }
}
cout<<count<<'\n';
return 0;
}


Measured memory_bytes: 23944
import sys
import os
import math
import bisect
import collections
import itertools
import heapq

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    q = 0
    for a in A:
        q += a - 1

    print(q)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

long long  fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; i++) {
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
int main() {
	string s;
	cin >> s;
	for (int i = 0; i < s.size(); i++) {
		cout << "x";
	}
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define cmin(a,b) (a>b?a=b:a)
#define cmax(a,b) (a<b?a=b:a)
#define mem(a,k) memset(a,k,sizeof(a))
#define lop(i,s,t) for(int i=s;i<(t);++i)
#define rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
#define fore(i,v) for(int i=g[v],d=es[i].d;i;i=es[i].nxt,d=es[i].d)
using namespace std;

#define Pr(f,...) //fprintf(stderr,f,##__VA_ARGS__),fflush(stderr)

typedef long long ll;

template<typename T>
void read(T &x){
	x=0; 
	char c;
	for(c=getchar();!isdigit(c);c=getchar()); 
	for(;isdigit(c);c=getchar())x=x*10+c-'0'; 
}

/*
const int N=,P=;

int mul(int a,int b){ return 1ll*a*b%P; }
int add(int a,int b){ a+=b; return a>=P?a-P:a; }
int sub(int a,int b){ a-=b; return a<0?a+P:a; }
int gcd(int a,int b){ return !b?a:gcd(b,a%b); }
*/


const int N = 3e5 + 50; 
int n, a[N]; 

int main(int argc,char *argv[]){
#ifdef CURIOUSCAT
	freopen("d.in", "r", stdin); 
#endif
	bool suc = true;
	read(n); 
	rep(i, 1, n) read(a[i]); 
	sort(a + 1, a + n + 1); 
	if (a[1] == a[n] && a[1] == 0) { 
		puts("Yes");
		return 0; 
	}
	suc &= n % 3 == 0; 
	Pr("suc = %d \n", suc); 
	int x = a[n / 3], y = a[n / 3 + 1], z = a[n / 3 * 2 + 1]; 
	suc &= a[1] == x && y == a[n / 3 * 2] && z == a[n];  
	Pr("suc = %d \n", suc); 
	if ((x ^ y) == z || (x ^ z) == y || (y ^ z) == x) ;
	else suc &= false;
	puts(suc ? "Yes" : "No"); 
	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
#include <string.h>
#include <ctype.h>

int main(void) {
	char buf[256];
	int  i;
	
	fgets(buf, sizeof(buf), stdin);
	
	for (i=0; i<strlen(buf); i++) {
		putchar(toupper(buf[i]));
	}
	
	return 0;
}

Measured memory_bytes: 916
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define repp(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ppb pop_back()
#define ALL(a) (a).begin(),(a).end()
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;

bool nCr_odd(int n,int r){
    return (n&r)==r;
}

signed main(){
    int n; cin >> n;
    string s; cin >> s;
    if(n==2){
        int x=s[0]-'0',y=s[1]-'0';
        cout << abs(x-y) << endl;
        return 0;
    }
    int s1[n],s2[n-1];
    rep(i,n) s1[i]=s[i]-'0';
    bool exist1=0;
    rep(i,n-1){
        s2[i]=abs(s1[i+1]-s1[i]);
        if(s2[i]==1) exist1=1;
    }
    if(exist1){
        rep(i,n-1){
            if(s2[i]==2) s2[i]=0;
        }
        int odd=0;
        rep(i,n-1){
            odd+=nCr_odd(n-2,i)*s2[i];
        }
        odd%=2;
        if(odd) cout << 1 << endl;
        else cout << 0 << endl;
    }else{
        rep(i,n){
            if(s2[i]==2) s2[i]=1;
        }
        int odd=0;
        rep(i,n-1){
            odd+=nCr_odd(n-2,i)*s2[i];
        }
        odd%=2;
        if(odd) cout << 2 << endl;
        else cout << 0 << endl;
    }
}



Measured memory_bytes: 9220
import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		PrintWriter ou = new PrintWriter(System.out);
		int n = Integer.parseInt(sc.next());
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) a[i] = Integer.parseInt(sc.next());
		sc.close();
		boolean check = true;
		int yono = 0;
		while(check){
			int cou = 0;
			for(int i = 0 ; i < n ; i++){
				if(a[i] != 0){
					cou++;
					a[i]--;
				}else{
					if(cou != 0) yono++;
					cou = 0;
				}
			}
			if(cou != 0) yono++;
			boolean ch = true;
			for(int i = 0 ; i < n && ch ; i++){
				if(a[i] != 0) ch = false;
			}
			if(ch) check = false;
		}
		ou.print(yono + "\n");
		ou.flush();
    }
}

Measured memory_bytes: 38396
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MOD=1000000007;

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  ll sum=0;
  for(int i=0;i<n;i++){
    cin >> a.at(i);
    sum=sum+a.at(i);
  }
  ll sumh=sum/2;
  ll suma=0;
  for(int i=0;i<n;i++){
    suma=suma+a.at(i);
    if(suma==sumh){
      cout << 0 << endl;
      return 0;
    }
    if(suma>sumh){
      if((suma-sumh)<=(sumh-suma+a.at(i))){
        cout << 2*suma-sum << endl;
        return 0;
      }
      else{
        cout << sum-2*(suma-a.at(i)) << endl;
        return 0;
      }
    }
  }
}

Measured memory_bytes: 4832
#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <stdint.h>
#include <queue>
#include <bitset>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define PI (3.14159265358979323846)
#define INF (2147483647)
#define INF_LL (9223372036854775807)
#define DIV_NUM (1000000007)
typedef long long ll;

// 配列初期化テンプレ
template<typename A, size_t N, typename T>
void Fill(A(&array)[N], const T& val) {
	std::fill((T*)array, (T*)(array + N), val);
}


int main() {

	string S, T;
	cin >> S >> T;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] != T[i]) {
			cout << "No" << endl;
			return 0;
		}
	}

	cout << "Yes" << endl;
	return 0;

}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
#include <ratio>
const long long INF = LLONG_MAX / 2;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i, r, n) for(int i=(ll)(r); i<(ll)(n); i++) 
#define REP(i, n) FOR(i, (0), n)
#define ALL(r) r.begin(), r.end()
#define ll long long int
using namespace std;
vector<ll> v;
vector<pair<ll, ll>> vp;
vector<vector<ll>> vv(110, vector<ll>(50, 0));
vector<tuple<ll, ll, ll>> vt;
set<ll> st;
map<ll, ll> mp;

int main()
{
	string s;
	cin >> s;
	int pa=500000, pz=0;
	REP(i,s.size())
	{
		if (s[i] == 'A') pa = min(pa, i);
		if (s[i] == 'Z') pz = max(pz, i);
	}
	cout << pz - pa + 1 << endl;
}

Measured memory_bytes: 644
#include<iostream>
#include<math.h>
#include<vector>
#include<array>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
#include<deque>
#include<set>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vector<ll>> mat;

int main(){
    int H,N;cin>>H>>N;
    vec A(1010),B(1010);
    for(int i=1;i<=N;i++){
        cin>>A[i]>>B[i];
    }
    mat dp(1010,vec(10010));
    //初期化
    for(int h=1;h<=H;h++){
        dp[0][h]=pow(10,18);
    }
    for(int n=1;n<=N;n++){
        dp[n][0]=0;
    }
    //漸化式
    for(int n=1;n<=N;n++){
        for(int h=1;h<=H;h++){
            if(h>=A[n]) dp[n][h]=min(dp[n-1][h],B[n]+dp[n][h-A[n]]);
            else        dp[n][h]=min(dp[n-1][h],B[n]);
        }
    }
    cout<<dp[N][H]<<endl;
    return 0;
}

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

typedef long long ll;
ll INF = 1LL << 60;
ll MAX = 100010;

vector<int> check;

int
main() 
{

  int n; cin >> n;
  vector<int> arr(n);
  ll ans = 0;
  rep(i, 0, n){
    int tmp;
    cin >> tmp;
    ans += tmp - 1 % tmp;
  }
  
  cout << ans << endl;

}




Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int toInt(const vector<int>& a){
    int ret = 0;
    for(int i=0; i<5; ++i)
        ret |= max(a[i], 0) << (i*2);
    return ret;
}

vector<int> toVector(int a){
    vector<int> ret(5);
    for(int i=0; i<5; ++i){
        ret[i] = a & 3;
        a >>= 2;
    }
    return ret;
}

int getScore(vector<int>& a, int b){
    int ret = 0;
    for(int i=0; i<5; ++i){
        if(a[i] != -1 && (b & 3))
            ret += 50 + 10 * (b & 3);
        b >>= 2;
    }
    return ret;
}

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

    while(--n >= 0){
        vector<vector<int> > grade(5, vector<int>(5));
        for(int i=0; i<5; ++i){
            for(int j=0; j<5; ++j){
                cin >> grade[i][j];
                -- grade[i][j];
            }
        }

        vector<int> dp(1<<10, -1);
        dp[toInt(grade[0])] = 0;
        for(int i=0; i<4; ++i){
            vector<int> nextDp(1<<10, -1);
            for(int j=0; j<(1<<10); ++j){
                if(dp[j] == -1)
                    continue;
                for(int k=0; k<(1<<8); ++k){
                    vector<int> a = toVector(j);
                    vector<int> b = grade[i+1];
                    for(int l=0; l<4; ++l){
                        (a[l]   += (k>>(l*2)) & 3) %= 4;
                        (a[l+1] += (k>>(l*2)) & 3) %= 4;
                        (b[l]   += (k>>(l*2)) & 3) %= 4;
                        (b[l+1] += (k>>(l*2)) & 3) %= 4;
                    }
                    int a1 = toInt(a);
                    int b1 = toInt(b);
                    nextDp[b1] = max(nextDp[b1], dp[j] + getScore(grade[i], a1)); 
                }
            }
            dp.swap(nextDp);
        }

        int ret = 0;
        for(int i=0; i<(1<<10); ++i){
            ret = max(ret, dp[i] + getScore(grade[4], i));
        }
        cout << ret << endl;
    }

    return 0;
}

Measured memory_bytes: 0