akhauriyash/Code-Regression huggingface dataset:
import bisect
A, B, Q = map(int, input().split())
s = [-10**10 - 1, -10**10] + [int(input()) for _ in range(A)] + [2*10**10]
t = [-10**10 - 1, -10**10] + [int(input()) for _ in range(B)] + [2*10**10]
x = [int(input()) for _ in range(Q)]


def func(c, d, z):
    i = bisect.bisect_left(c, z)
    j = bisect.bisect_left(d, z)
    if c[i - 1] < d[j - 1] and c[i] < d[j]:
        return min(z - c[i - 1], z + c[i] - 2 * d[j - 1], 2 * c[i] - z - d[j - 1], d[j] - z)
    elif c[i - 1] < d[j - 1] and c[i] >= d[j]:
        return min(z - c[i - 1], z + c[i] - 2 * d[j - 1], 2 * d[j] - z - c[i - 1], c[i] - z)
    elif c[i - 1] >= d[j - 1] and c[i] < d[j]:
        return min(z - d[j - 1], z + d[j] - 2 * c[i - 1], 2 * c[i] - z - d[j - 1], d[j] - z)
    else:
        return min(z - d[j - 1], z + d[j] - 2 * c[i - 1], 2 * d[j] - z - c[i - 1], c[i] - z)


for z in x:
    print(func(s, t, z))

Measured memory_bytes: 16152
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define sort(s) sort(s.begin(),s.end())
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<int>>
constexpr auto mod = 1000000007;


//2のn乗を求めるよ！！！
int ni(int n) {
	if (n == 0)return 1;
	int x = ni(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;
}

//フィボナッチ数列のx番目を求めるよ！
int f(int x, vector<int> s) {
	if (x == 0)return 0;
	if (x == 1)return 1;
	if (s[x] != 0)return s[x];
	s[x] = f(x - 1, s) + f(x - 2, s);
	return s[x];
}

//aとｂの最大公約数を求めるよ！
llint gcd(llint a, llint b) {
	if (a < b)swap(a, b);
	if (b == 0)return a;
	return gcd(b, a % b);
}



// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// mod. m での a の逆元 a^{-1} を計算するよ！
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


//aCbをmod.mで割った余りを求める
ll int c(ll int a, ll int b, ll int m) {
	ll int ans = 1;
	for (ll int i = 0; i < b; i++) {
		ans *= a - i;
		ans %= m;
	}
	for (ll int i = 1; i <= b; i++) {
		ans *= modinv(i, m);
		ans %= m;
	}
	return ans;
}

//m進数のn桁を全列挙やで
void dfs(int m, int n) {

	stack<string> st;
	st.push("");
	while (!st.empty()) {
		string now = st.top();
		st.pop();
		if (now.size() == n) {
			cout << now << endl;
		}
		else {
			for (int i = m - 1; i >= 0; i--) {
				string next = now + to_string(i);
				st.push(next);
			}
		}
	}
}
void press(string& v) { v.erase(unique((v).begin(), (v).end()), v.end()); }

int main() {
	int n,k;
	cin >> n>>k;
	hei(int) a(n);
	rep(i, 0, n)cin >> a[i];
	sort(a);
	int x = 1;
	rep(i, 0, n-1) {
		if (a[i] != a[i + 1])x++;
	}
	hei(int) t(x,1);
	int y =0;
	rep(i, 0, n - 1) {
		if (a[i] == a[i + 1])t[y]++;
		else {
			y++;
		}
	}
	sort(t);
	int ans = 0;
	rep(i, 0, x-k)ans += t[i];
	cout << ans << endl;
	return 0;
}

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

int main(void) {
    string S;
    string output = "Good\n";

    cin >> S;
    for(int i=1;i<S.size();i++) {
        if(S[i-1] == S[i]) output = "Bad\n";
    }

    cout << output ;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
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; }
// const ll INF = 1LL <<60;
const int INF = 10000;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

const int MAX = 510000;
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;
}


//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始
int main(){
  string s;
  cin>>s;
  int left = 0,right = s.size()-1;
  int ans = 0;
  while(left<right){
    if(s[left]==s[right]){
      left++;
      right--;
    }
    else if(s[left]!='x'&&s[right]=='x'){
      ans++;
      right--;
    }
    else if(s[left]=='x'&&s[right]!='x'){
      ans++;
      left++;
    }
    else{
      cout<<-1<<endl;
      return 0;
    }
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 512
unittest
{
	assert( [ "ant", "obe", "rec" ].parse.expand.solve == "abc" );
	assert( [ "edu", "cat", "ion" ].parse.expand.solve == "ean" );
}



import std.conv;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
	stdin.byLineCopy.parse.expand.solve.writeln;
}

auto parse( Range )( Range input )
if( isInputRange!Range && is( ElementType!Range == string ) )
{
	auto css = new string[ 3 ];
	foreach( ref cs; css )
	{
		cs = input.front.strip;
		input.popFront;
	}
	return tuple( css );
}

auto solve( string[] css )
{
	auto s = "";
	foreach( i, cs; css )
	{
		s ~= cs[ i ];
	}
	
	return s;
}


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

int main(){
	string A,B,C;
	cin>>A>>B>>C;
	int posa=0 , posb=-1 , posc=-1;
	char aux;
	aux=A[0];
	for(int i=0 ; i<10000 ; i++){
		if(posa==A.size()){cout<<"A"; break;}
		if(posb==B.size()){cout<<"B"; break;}
		if(posc==C.size()){cout<<"C"; break;}
		
		if(aux=='a'){
			posa++;
			aux=A[posa];
		}
		if(aux=='b'){
			posb++;
			aux=B[posb];
			
		}
		if(aux=='c'){
			posc++;
			aux=C[posc];
		}

	}
	return 0;
}

Measured memory_bytes: 256
s=int(input())
mod=10**9+7
fact=[1]*(2*s+1)
inv=[1]*(2*s+1)
for i in range(2,2*s+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],-1,mod)
for i in range(2*s,1,-1):
    inv[i-1]=inv[i]*i%mod
def comb(x,y):return  0 if not(x>=y>=0) else fact[x]*inv[y]%mod*inv[x-y]%mod
def h(ball,sect):return 0 if sect==0 or ball< 0 else fact[ball+sect-1]*inv[ball]%mod*inv[sect-1]%mod
ans=0
for i in range(1,s//3+1):
    ans=(ans+h(s-3*i,i))%mod
print(ans)

Measured memory_bytes: 9280
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define ll long long
using namespace std;

int main()
{
	string pre, result;
	int ans = 0;
	cin >> pre >> result;

	for (int i = 0; i < 3; i++) {
		if (pre[i] == result[i])ans++;
	}

	printf("%d", ans);

	return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++){
    cin >> d[i];
  }
  sort(d.begin(), d.end());
  cout << d[N / 2] - d[N / 2 - 1] << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <bitset>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>

using namespace std;

#define ll long long
#define vecll vector<long long>
#define vec2ll vector<vector<long long>>
#define vecbool vector<bool>
#define vecpairll vector<pair<long long,long long>>
#define forll(s,a,b) for(long long s = a;s < b;s++)
#define forllde(s,a) for(long long s = a;s > 0;s--)

int main()
{
	ll n;
	string s = "Yes";

	cin >> n;

	vector<string> a(n),buf;

	forll(i, 0, n)
		cin >> a[i];

	sort(a.begin(), a.end());

	buf.push_back(a[0]);

	forll(i, 1, a.size())
	{
		if (a[i - 1] != a[i])
			buf.push_back(a[i]);
	}

	cout << buf.size();

}


Measured memory_bytes: 17844
#include <iostream>
using namespace std;
int main()
{
  int k;
  std::cin>>k;
  int total=0;
  int flag=0;
  for(int i=0;i<1e7;i++)
  {
    total=(total*10+7)%k;
    if(total==0)
    {
      std::cout<<i+1;
      flag=1;
      break;
    }
  
  }
  if(flag==0)
  {
    std::cout<<-1;
  }
}

Measured memory_bytes: 3648
x = gets.to_i
onigiri = 0
while onigiri * 100 <= x
  sandwich = 0
  while sandwich * 101 + onigiri * 100 <= x
    kukki = 0
    while kukki * 102 + sandwich * 101 + onigiri * 100 <= x
      cake = 0
      while cake * 103 + kukki * 102 + sandwich * 101 + onigiri * 100 <= x
        candy = 0
        while candy * 104 + cake * 103 + kukki * 102 + sandwich * 101 + onigiri * 100 <= x
          if (x - candy * 104 - cake * 103 - kukki * 102 - sandwich * 101 - onigiri * 100) % 105 == 0
            puts 1
            exit
          end
          candy += 1
        end
        cake += 1
      end
      kukki += 1
    end
    sandwich += 1
  end
  onigiri += 1
end
puts 0

Measured memory_bytes: 14244
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
  int N;
  cin >> N;
  vector<int> A(N + 1);
  A[0] = -1;
  for(int i = 1; i <= N; i++) {
    cin >> A[i];
  }
  vector<int> B(N + 1);
  B[0] = -1;
  for(int i = 1; i <= N; i++) {
    cin >> B[i];
  }
  vector<int> C(N + 1);
  C[0] = -1;
  for(int i = 1; i < N; i++) {
    cin >> C[i];
  }
  int ans = 0;
  for(int i = 1; i <= N; i++) {
    ans += B[i];
  }
  for(int i = 1; i < N; i++) {
    if(1 == A[i + 1] - A[i]) {
      ans += C[A[i]];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
n = gets.to_i
a = n.times.map {gets.to_i}

min = a[0]
max_diff = a[1] - a[0]

for i in 1..n-1
  diff = a[i] - min
  if max_diff < diff
    max_diff = diff
  end

  if a[i] < min
    min = a[i]
  end
end
puts max_diff


Measured memory_bytes: 10576
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
ll mod=1e9+7;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
    	cin>>a[i];
    }
    ll x=0;
    for(int i=0;i<n;i++){
    	for(int j=0;j<n;j++){
    		if(a[j] < a[i]) x++;
    	}
    }
    ll p=0;
    for(int i=0;i<n;i++){
    	for(int j=i+1;j<n;j++){
    		if(a[j] < a[i]) p++;
    	}
    }
    ll ans=  (k*p)%mod + ((((k*(k-1))/2)%mod)*x)%mod;
    cout<<ans%mod;
}

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

int main(){
  int N;
  string S;
  int K;
  cin >> N;
  cin >> S;
  cin >> K;
  for(int i=0;i<S.size();i++){
    if(S[i] != S[K-1]){
      S[i] = '*';
    }
  }
  cout << S;
  return 0;
}



Measured memory_bytes: 764
N = int(input())

pairs = [list(map(int, input().split(" "))) for _ in range(N)]
#pairs = sorted(pairs, key=lambda x: x[0])

counts = [[0 for _ in range(N)] for _ in range(N)]
for i, (x1, y1) in enumerate(pairs):
    for j, (x2, y2) in enumerate(pairs):
        if i == j:
            continue
        
        dx = x2 - x1
        dy = y2 - y1

        count = 0
        for x, y in pairs:
            if [x+dx, y+dy] in pairs:
                count += 1

        #x3 = x2 + dx
        #y3 = y2 + dy

        #while [x3, y3] in pairs:
        #    count += 1
        #    x3 = x3 + dx
        #    y3 = y3 + dy

        counts[i][j] = count

#import numpy as np
#print(np.asarray(counts))


max_count = max([max(elm) for elm in counts])
#print(max_count)

out = N - max_count
print(out)

Measured memory_bytes: 3064
#include <stdio.h>
int main(){
    int a,b;
    char op;
    for(;;){
        scanf("%d %c %d",&a,&op,&b);
        if(op=='?'){
            break;
        }else if(op=='+'){
            printf("%d\n",a+b);
        }else if(op=='-'){
            printf("%d\n",a-b);
        }else if(op=='*'){
            printf("%d\n",a*b);
        }else if(op=='/'){
            printf("%d\n",a/b);
        }
    }

    return 0;
}


Measured memory_bytes: 2060
#include <cstdio>
#include <algorithm>
using namespace std;
int a[100005];
int main(){
	int i, j, n;
	
	scanf("%d", &n);
	for(i=1; i<=n; i++) scanf("%d", &a[i]);
	sort(a+1, a+1+n);
	for(i=1; i<n and min(a[n]-a[i], a[i])<min(a[n]-a[i+1], a[i+1]); i++);
	printf("%d %d", a[n], a[i]);
} 

Measured memory_bytes: 512
#2020-03-19
house = [[[0 for heya in range(10)] for kai in range(3)] for mune in range(4)] 

kensu = int(input())
for i in range(kensu):
    b,f,r,v = map(int,input().split())
    house[b-1][f-1][r-1] += v

for mune in range(4):    
    for kai in range(3):
        for heya in range(10):
            print(f' {house[mune][kai][heya]}',end='')
        print()
    if mune < 3:
        print('#' * 20)


Measured memory_bytes: 5636
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from fractions import Fraction
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations, accumulate
from operator import add, mul, sub, itemgetter, attrgetter


import sys
# sys.setrecursionlimit(10**6)
# readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(readline())


def read_int_n():
    return list(map(int, readline().split()))


def read_float():
    return float(readline())


def read_float_n():
    return list(map(float, readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def ep(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.perf_counter()
        ret = f(*args, **kwargs)
        e = time.perf_counter()

        ep(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, U, V, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    def dfs(u):
        s = [u]
        d = {u: 0}
        while s:
            u = s.pop()
            for v in g[u]:
                if v in d:
                    continue
                d[v] = d[u] + 1
                s.append(v)
        return d

    du = dfs(U)
    dv = dfs(V)

    ans = 0
    for v in sorted(du.keys()):
        if du[v] < dv[v]:
            ans = max(ans, dv[v] - 1)

    return ans


def main():
    N, U, V = read_int_n()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, U, V, AB))


if __name__ == '__main__':
    main()


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

#define REP(i, n) for (int i = 0; i < n; i++)
typedef pair<int, int> P;

void solve() {
    int N;
    cin >> N;
    if (N == 0) exit(0);
    vector<int> p(N);
    REP(i, N) { cin >> p[i]; }
    // dp[i][j]=i番目までで、おつりがj円の時の、{500円玉の枚数のmax,消費金額のmin}
    vector<vector<P>> dp(N + 1, vector<P>(50500, {-1, 1e8}));
    dp[0][0] = {0, 0};
    REP(i, N) {
        REP(j, 50005) {
            if (dp[i][j].first == -1) continue;
            int otsuri = (1000 - p[i] % 1000) % 1000;
            int cnt = dp[i][j].first;
            int cost = dp[i][j].second;
            //買わない
            if (cnt > dp[i + 1][j].first) {
                dp[i + 1][j] = {cnt, cost};
            } else if (cnt == dp[i + 1][j].first && cost < dp[i + 1][j].second) {
                dp[i + 1][j] = {cnt, cost};
            }

            //おつりが500円以上の時(1000円で買えば500円がもらえる)
            if (otsuri >= 500) {
                // 500円のmaxを増やせるとき
                if (cnt + 1 > dp[i + 1][j + otsuri - 500].first) {
                    dp[i + 1][j + otsuri - 500] = {cnt + 1, cost + p[i]};
                }
                //消費金額のminを小さくできるとき
                else if (cnt + 1 == dp[i + 1][j + otsuri - 500].first &&
                         cost + p[i] < dp[i + 1][j + otsuri - 500].second) {
                    dp[i + 1][j + otsuri - 500] = {cnt + 1, cost + p[i]};
                }
            } else {
                //手持ちのおつりと合わせて500円がもらえる
                if (j + otsuri >= 500) {
                    int d = 500 - otsuri;  // 500円との差額
                    //買うけど500円はもらわない
                    if (cnt > dp[i + 1][j + otsuri].first) {
                        dp[i + 1][j + otsuri] = {cnt, cost + p[i]};
                    } else if (cnt == dp[i + 1][j + otsuri].first && cost + p[i] < dp[i + 1][j + otsuri].second) {
                        dp[i + 1][j + otsuri] = {cnt, cost + p[i]};
                    }

                    // 500円のmaxを増やせるとき
                    if (cnt + 1 > dp[i + 1][j - d].first) {
                        dp[i + 1][j - d] = {cnt + 1, cost + p[i]};
                    }
                    //消費金額のminを小さくできるとき
                    else if (cnt + 1 == dp[i + 1][j - d].first && cost + p[i] < dp[i + 1][j - d].second) {
                        dp[i + 1][j - d] = {cnt + 1, cost + p[i]};
                    }
                } else {
                    if (cnt > dp[i + 1][j + otsuri].first) {
                        dp[i + 1][j + otsuri] = {cnt, cost + p[i]};
                    } else if (cnt == dp[i + 1][j + otsuri].first && cost + p[i] < dp[i + 1][j + otsuri].second) {
                        dp[i + 1][j + otsuri] = {cnt, cost + p[i]};
                    }
                }
            }
        }
    }
    int cnt_max = 0;
    REP(j, 50001) { cnt_max = max(cnt_max, dp[N][j].first); }
    int mn_cost = 1e9;
    REP(j, 50001) {
        if (dp[N][j].first == cnt_max) {
            mn_cost = min(mn_cost, dp[N][j].second);
        }
    }
    cout << cnt_max << " " << mn_cost << endl;
}
int main() {
    while (true) solve();
}


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

int main() {
  int N, M;
  cin >> N >> M;
  
  vector<int> vec(M*2);
  
  for(int i = 0; i < M*2; i++){
  int c;
  cin >> c;
  vec.at(i) = c;
  
  }
 
  
  vector<int> veca(M);
  
  for(int i = 0; i< M; i++){
    veca.at(i) = vec.at(i*2);
  }
  
    vector<int> vecb(M);
  
  for(int i = 0; i< M; i++){
    vecb.at(i) = vec.at(i*2 + 1);
  }

  
  for(int j = 0; j < N; j++){
    int c = 0;
    int d = 0;
    for(int i = 0; i < M; i++){
      if(veca.at(i) == j + 1 ){
        c++;
      }
      if(vecb.at(i) == j + 1 ){
        d++;
      }
    }
    cout << c + d << endl;
  }
}


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

#define rep(i,n) for(int i=0; i<n; i++)

int main(){
	int s1,s2;
	while( cin >> s1 >> s2, s1||s2 ){
		int ms = s1+s2;
		int mi = 0;
		rep(i,4){
			cin >> s1 >> s2;
			if( ms < s1+s2 ){
				ms = s1 + s2;
				mi = i+1;
			}
		}
		cout << (char)('A'+mi) << " " << ms << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6+23;
vector<pii> g[maxn];
int n,s;
int d[maxn];
bool vis[maxn];
priority_queue<pair<int,int>> q;
void dij(int s)
{
    memset(d,0x3f,sizeof(d));
    memset(vis,false,sizeof(vis));
    q.push({0,s});d[s]=0;
    while(!q.empty()){
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(pii t:g[x]){
        	int y=t.first;
        	int z=t.second;
        	if(d[y]>d[x]+z){
                d[y]=d[x]+z;
                q.push({-d[y],y});
            }
        }
    }
}


int main(){
	cin>>n;
	s=n;
	for(int i=1;i<9;i++) g[s].push_back({i,i});
	for(int i=1;i<n;i++){
		int k=i*10;
		for(int j=0;j<10;j++){
			g[i].push_back({(k+j)%n,j});
		}
	}
	dij(s);
	cout<<d[0];
}


Measured memory_bytes: 44788
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 998244353;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) { a = b; return true;}
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) { a = b; return true;}
    return false;
}
class ModCom {
    public:
        ModCom(int _n, long long _mod){
            assert(_n>=2);
            n = _n+1;
            mod = _mod;
            fac.assign(n,0);
            finv.assign(n,0);
            inv.assign(n,0);
            init();
        }

        long long com(int _n, int k){
            if(_n < k){return 0;}
            if(_n < 0 || k < 0){return 0;}
            return fac.at(_n) * (finv.at(k) * finv.at(_n - k) % mod) % mod;
        }

    private:
        int n;
        long long mod;
        vector<long long> fac;
        vector<long long> finv;
        vector<long long> inv;

        void init(void){
            fac.at(0) = fac.at(1) = 1;
            finv.at(0) = finv.at(1) = 1;
            inv.at(1) = 1;
            for(int i = 2;i < n; i++){
                fac.at(i) = fac.at(i - 1) * i % mod;
                inv.at(i) = mod - inv.at(mod % i) * (mod / i) % mod;
                finv.at(i) = finv.at(i - 1) * inv.at(i) % mod;
            }
            return;
        }
};
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,a,b,k;cin>>n>>a>>b>>k;
    ModCom com(n+50,MOD);
    vector<pair<ll,ll>> cand;
    rep(i,n+1){
        if(k<a*i){
            continue;
        }
        if((k-a*i)%b==0&&(k-a*i)/b<=n){
            cand.push_back(make_pair(i,(k-a*i)/b));
        }
    }
    ll res = 0;
    for(auto x:cand){
        ll tmp = 1;
        tmp *= com.com(n,x.first);
        tmp *= com.com(n,x.second);
        tmp %= MOD;
        res += tmp;
        res %= MOD;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 12784
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N, K = get_ints
R, S, P = get_ints
T = gets.chomp

points = {
  'r' => P,
  's' => R,
  'p' => S
}

sum = 0
tx = T.split('')
wins = []
tx.each.with_index do |x, index|
  if index < K || tx[index - K] != x || !wins[index - K]
    sum += points[x]
    wins[index] = true
  end
end

puts sum


Measured memory_bytes: 20460
#include <bits/stdc++.h>
 
using namespace std;
 
#define xx         first
#define yy         second
#define pb         push_back
#define mp         make_pair
#define LL         long long
#define inf        INT_MAX/3
#define mod        1000000007ll
#define PI         acos(-1.0)
#define linf       (1ll<<60)-1
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define REP(I,N)   FOR(I,0,N)
#define For(I,N)   for(int I=1;I<=(N);I++)
#define ALL(A)     ((A).begin(), (A).end())
#define set0(ar)   memset(ar,0,sizeof ar)
#define vsort(v)   sort(v.begin(),v.end())
#define setinf(ar) memset(ar,126,sizeof ar)
#define SZ(X) ((int)(X.size()))
#define LG(X) ((int)(X.length()))
#define CL(X) (X).clear()
#define MAXEL(A,B) (*max_element(A,B))
#define MINEL(A,B) (*min_element(A,B))
#define ROPEN(X) freopen(X,"r",stdin)
#define WOPEN(X) freopen(X,"w",stdout)
#define BG(X) (X.begin())
#define EN(X) (X.end())
#define VI vector<int>
#define PII pair<int,int>
 
//cout << fixed << setprecision(20) << p << endl;
 
template <class T> inline T bigmod(T p,T e,T M){
    LL ret = 1;
    for(; e > 0; e >>= 1){
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    } return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(auto& e:arr){
		cin>>e;
	}
	sort(arr,arr+n);
	LL ans=0;
	for(int i=0;i<n-k;i++){
		ans+=arr[i];
	}
	cout<<ans<<endl;
	return 0;
}


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

int main(void) {
  ll n;
  string s;
  cin >> n;
  cin >> s;
  
  ll cnt = 0;
  for (ll i = 0; i < n; i++) {
    if (s[i] == 'A') {
      if (s[i+1] == 'B' && s[i+2] == 'C') {
        cnt++;
        i += 2;
      }
    }
  }
  cout << cnt << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define repi(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = long long;
using u32 = unsigned long long;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using vi32 = vector<i32>;
using vu32 = vector<u32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf64 = vector<f64>;
using vstr = vector<string>;
using vvi32 = vector<vi32>;
using vvu32 = vector<vu32>;
using vvi64 = vector<vi64>;
using vvu64 = vector<vu64>;
using vvf64 = vector<vf64>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

int dp[10010];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  int n, W;
  cin >> n >> W;
  vi32 v(n), w(n);
  rep(i, n) cin >> v[i] >> w[i];
  rep(i, 10010) dp[i] = -1e9;
  dp[0] = 0;
  rep(i, n) rrep(j, W) {
    if (dp[j] >= 0 && j + w[i] <= W) 
      amax(dp[j + w[i]], dp[j] + v[i]);
  }
  int ans = 0;
  rrep(i, W + 1) amax(ans, dp[i]);
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 3232
#include <cstdio>

int main()
{
    int b, f, r, m, n, i, v;
    int hou[4][3][10];
    for (b = 0; b < 4; b++)
    {
        for (f = 0; f < 3; f++)
        {
            for (r = 0; r < 10; r++)
            {
                hou[b][f][r] = 0;
            }
        }
    }
    scanf("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf("%d %d %d %d", &b, &f, &r, &v);
        b -= 1;
        f -= 1;
        r -= 1;
        hou[b][f][r] += v;
    }
    for (b = 0; b < 4; b++)
    {
        if (b != 0)
        {
            printf("####################\n");
        }
        for (f = 0; f < 3; f++)
        {
            for (r = 0; r < 10; r++)
            {
                printf(" %d", hou[b][f][r]);
            }
            printf("\n");
        }
    }
}


Measured memory_bytes: 2672
import qualified Data.ByteString.Char8 as BC
import Data.Maybe

readIntsLine :: IO [Int]
readIntsLine = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

solve :: [Int] -> Int
solve [a1, a2] = gcd a1 a2
solve (a1:a2:as) = solve $ gcd a1 a2 : as

main :: IO ()
main = do
  getLine
  as <- readIntsLine
  print $ solve as

Measured memory_bytes: 19836
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9+7;

int main(){
	
	string s; cin>>s;
	if(s.substr(0,4)<"2019"){
		cout <<"Heisei" <<endl;
	}
	else if(s.substr(0,4)>"2019"){
		cout <<"TBD"<<endl;
	}
	else if(s.substr(5,2)<="04"){
		cout <<"Heisei" <<endl;
	}
	else cout <<"TBD"<<endl;
	
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#define shosu(x) fixed<<setprecision(x)
using namespace std;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,P> pip;
typedef long long ll;
const int inf=(1<<31)-1;
const double pi=acos(-1);

int n;
ll ans=1;

int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		ans*=i;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 1156
#include<cstdio>
#include<iostream>
using namespace std;
int main(){
    int n;
    int gx,gy,kx,ky;
    while(1){
        int fie[18][18]={0},fieko[18][18]={0};
        fie[1][0]=1;
        scanf("%d%d",&gx,&gy);
        if(gx==0,gy==0)
            break;
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            scanf("%d%d",&kx,&ky);
            fieko[ky][kx]=1;
        }
        for(int i=1;i<=gy;i++){
            for(int j=1;j<=gx;j++){
                if(fieko[i][j]==1)
                    continue;
                else{
                    fie[i][j]=fie[i][j-1]+fie[i-1][j];
                    
                    /*
                    for(int k=0;k<=gy;k++){
                        for(int l=0;l<=gx;l++){
                            printf("%d ",fie[k][l]);
                        }
                        puts("");
                    }
                    puts("");
                    */

                }
            }
        }
        printf("%d\n",fie[gy][gx]);
    }
    return 0;
}

Measured memory_bytes: 1188
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf = 10**9

def f():
    n,a = list(map(int, input().split()))
    x = list(map(int, input().split()))
    x.sort()
    b = [(a-_) for _ in x if _ < a]
    c = [0 for _ in x if _ == a]
    d = [(_-a) for _ in x if _ > a]
    m = 50*50
    ba = [0]*(m+1)
    ba[0] = 1
    for bi in b:
        for j in range(m-bi,-1,-1):
            ba[j+bi] += ba[j]
    da = [0]*(m+1)
    da[0] = 1
    for di in d:
        for j in range(m-di,-1,-1):
            da[j+di] += da[j]
    r = -1
    for i in range(m+1):
        r += ba[i] * da[i]
    cl = len(c)
    cr = 2**cl - 1
    return r * (cr+1) + cr

print(f())


Measured memory_bytes: 8480
num = int(input())
A = []
for i in range(num):
    order = list(map(int, input().split()))
    if order[0] == 0:
        A.append(order[1])
    if order[0] == 1:
        print(A[order[1]])
    if order[0] == 2:
        del A[-1:]


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

using namespace std;

int main(){
        string str; cin >> str;
        int m; cin >> m;
        string str1,str2;
        int n;
        while(str != "-"){
                for (int i = 0;i < m; i++){
                        cin >> n;
                        str1 = str.substr(0,n);
                        str2 = str.substr(n);
                        str = str2 + str1;
                }   
                cout << str<< endl;    
                cin >> str;
                cin >> m;

        }   
        return 0;
}

Measured memory_bytes: 3188
var readable = process.stdin;
readable.resume();
readable.setEncoding( 'utf-8' );
readable.on( 'data', function( chunk ) {
  var data = chunk.split( ' ' );
  var a = parseInt( data[0] );
  var b = parseInt( data[1] );
  var c = parseInt( data[2] );
  if( a < b && b < c ) {
    console.log( 'Yes' );
  } else {
    console.log( 'No' );
  }
} )

Measured memory_bytes: 7644
#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() {
    string s;
    cin >> s;
    bool flag=false;
    rep(i,s.size()-1){
        if(s.at(i)=='A'&&s.at(i+1)=='C'){
            flag=true;
        }
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
}


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

int main(){
    int x,a,b;
    cin>>x>>a>>b;
    for (int i=1; i<=100; i++) {
        if (x-a<b*i) {
            cout<<x-a-b*(i-1)<<endl;
            return 0;
        }else if((x-a)==(b*i)){
            cout<<(x-a-b*i)<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10,size=1<<20;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

int n,m;

int main() {
	qr(n); qr(m); 
	int t=m+(m&1),tt=t+1;
	for(int i=1;i<t;i++) pr1(i),pr2(t--);
	t=2*m+1;
	for(int i=tt;i<t;i++) pr1(i),pr2(t--);
	return 0;
}



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

int main(){
  int memo[51] = {0};
  for(int i = 0; i < 10; i++)
    for(int j = 0; j < 10; j++)
      memo[i + j]++;
  int n;
  while(cin >> n){
    int res = 0;
    for(int i = 0; i <= n; i++)
      res += memo[i] * memo[n - i];
    cout << res << endl;
  }
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(),x.end();
#define rall(x) x.rbegin(),x.rend();
#define ld long double
#define pll pair < long long , long long >
#define endl "\n"
using namespace std;

int main()
{
    ll h, n;
    cin >> h >> n;
    ll sum = 0;
    while(n--)
    {
        int b;
        cin >>b;
        sum+=b;
    }
    if(sum>=h)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main{
	public static void main(String args[]) throws Exception{
		Scanner cin= new Scanner(System.in);
	while(true){
		int n= cin.nextInt();
		int x= cin.nextInt();
		int count= 0;
		
		if( n==0 && x==0 ){
			break;
		}
		else{
			int i,j,k;
			for(i=1;i<n-1;i++){
			for(j=i+1;j<n;j++){
			for(k=j+1;k<n+1;k++){
				if( i+j+k==x ){
					count++;
					break;
				}
			}
			}
			}
			System.out.println(count);
		}
	}
	}
}

Measured memory_bytes: 19916
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Dhanin Gupta
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        BGoldenCoins solver = new BGoldenCoins();
        solver.solve(1, in, out);
        out.close();
    }

    static class BGoldenCoins {
        public void solve(int testNumber, InputReader in, PrintWriter w) {

            long x = in.nextLong();
            long hap = 0;

            long fh = x / 500;
            hap += fh * 1000;
            x -= fh * 500;

            long fr = x / 5;
            hap += fr * 5;

            w.println(hap);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();

            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }

                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;

            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



Measured memory_bytes: 21460
a=int(input())
b=[]
for _ in range(a):
    b.append(input())
if len(b)!=len(set(b)):
    print('No')
    exit()
for i in range(a-1):
    if b[i][-1]!=b[i+1][0]:
        print('No')
        exit()
print('Yes')

Measured memory_bytes: 9184
import sys
input = sys.stdin.readline
H,W,N = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(N)]
from collections import defaultdict
dic = defaultdict(lambda: 0)
for y,x in AB:
    for dx in range(-1,2):
        for dy in range(-1,2):
            nx,ny = x+dx,y+dy
            if not 1 <= nx <= W: continue
            if not 1 <= ny <= H: continue
            dic[(nx,ny)] += 1

ans = [0] * 10
for (x,y),c in dic.items():
    if x==1 or x==W or y==1 or y==H: continue
    ans[c] += 1
s = sum(ans)
ans[0] = (W-2)*(H-2)-s

print(*ans, sep='\n')

Measured memory_bytes: 177868
/*
  A - AtCoder *** Contest
  Contest 049
  Rakesh Kumar --> 03/08/2020
 */

#include <bits/stdc++.h>

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

    char c = ' ';
    std::cin >> c;
    if (c == 'a' ||
        c == 'e' ||
        c == 'i' ||
        c == 'o' ||
        c == 'u')
        std::cout << "vowel" << std::endl;
    else
        std::cout << "consonant" << std::endl;

    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <stack>
#include <math.h>
#include <map>
#define Z class
#define ln cout<<'\n'
#define ll long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
//ASCII a=97, A=65
// int H[N]; rep(i,N) scanf("%d", &H[i]);
// int max_x = *std::max_element(x.begin(), x.end());
// int min_y = *std::min_element(y.begin(), y.end());
using namespace std;
template<class T> inline bool chmax(T& a, T b){ if(a < b) { a=b; return 1; }return 0;}
template<class T> inline bool chmin(T& a, T b){ if(a > b) { a=b; return 1; }return 0;}
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
const long long INF = 1LL << 60;

int main(){
    char a,b; cin >> a >> b;
    if(a==b) pr('H');
    else pr('D');
}


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

using namespace std;

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= 50000; ++i) {
    int ans = i * 1.08;
    if (ans == n) {
      cout << i << endl;
      return 0;
    }
  }
  cout << ":(" << endl;
  return 0;
}



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

using namespace std;

int a, b;
char str [11];
int stack[100];
int stackLength;

void push(int i) {
	stack[stackLength] = i;
	stackLength++;
}
int pop() {
	stackLength--;
	return stack[stackLength]; 
	// no need to actually delete, make the algo little fast
}

//stackoverflow.com/questions/16826422/c-most-efficient-way-to-convert-string-to-int-faster-than-atoi
int fast_atoi( const char * str ) {
    int val = 0;
    while( *str )
        val = val*10 + (*str++ - '0');

    return val;
}

int main() {
	stackLength = 0;

	while(scanf("%s", str) != EOF)
		if (str[0] == '+') {
			a = pop();
			b = pop();
			push(a+b);

		}
		else if (str[0] == '-') {
			b = pop();
			a = pop();
			push(a-b);

		}
		else if (str[0] == '*') {
			a = pop();
			b = pop();
			push(a*b);
		}
		else
			push(fast_atoi(str));

	cout << pop() << endl;

	return 0;
}


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

long long n;
vector<long long> a;

long long solve();

int main() {
  cin >> n;
  a.resize(n);
  for (int i = 0; i < n; ++i) cin >> a[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  long long bit = 0, sum = a[0] + a[1], tmp = 0;
  vector<int> id;
  for (int i = 2; i < n; ++i) bit ^= a[i];
  if ((sum ^ bit) & 1) return -1;
  for (int i = 0; i < 50; ++i)
    if (bit >> i & 1) {
      sum -= 1LL << i;
      id.push_back(i);
    }
  if (sum < 0) return -1;
  for (int i = 1; i < 50; ++i) {
    if ((sum >> i & 1) && (bit >> (i - 1) & 1)) return -1;
    if (sum >> i & 1) tmp += 1LL << (i - 1);
  }
  if (tmp > a[0]) return -1;
  reverse(id.begin(), id.end());
  for (auto x : id)
    if ((1LL << x) + tmp < a[0]) tmp += 1LL << x;
  if (tmp == 0) return -1;
  return a[0] - tmp;
}


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

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
typedef long long ll;
typedef pair<int, int> point;

const int MAXN = 2e5 + 5;

int n;
int pref[MAXN];
int a[MAXN];
ll sol;

ll sum(int x, int y){
    if(x) return pref[y] - pref[x - 1];
    return pref[y];
}

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

    cin >> n;
    REP(i, n)
        cin >> a[i];

    int cut1, cut2, cut3;
    cut1 = cut2 = cut3 = 0;
    ll sum1, sum2, sum3, sum4;
    sum1 = sum2 = sum3 = sum4 = 0;

    REP(i, n)
        sum4 += a[i];


    sol = (ll)1e15;

    while(cut2 < n){

        while(cut1 < cut2){
            ll newSum1 = sum1 + a[cut1];
            ll newSum2 = sum2 - a[cut1];

            if(abs(newSum1 - newSum2) < abs(sum1 - sum2)){
                cut1 ++;
                sum1 = newSum1;
                sum2 = newSum2;
            }
            else
                break;
        }

        while(cut3 < n){
            ll newSum1 = sum3 + a[cut3];
            ll newSum2 = sum4 - a[cut3];

            if(abs(newSum1 - newSum2) < abs(sum3 - sum4)){
                cut3 ++;
                sum3 = newSum1;
                sum4 = newSum2;
            }
            else
                break;
        }

        ll newSol = max( max(sum1, sum2), max(sum3, sum4) ) - min( min(sum1, sum2), min(sum3, sum4) );
        sol = min(sol, newSol);

        sum2 += a[cut2];
        sum3 -= a[cut2];
        cut2 ++;
    }

    cout << sol;
}


Measured memory_bytes: 1024
import copy
H, W, K = map(int,input().split())
c = [list(input()) for __ in range(H)]
#c[0][1] = '*'
#print(c[0][1])

ans = 0
for bit in range(1<<(H+W)):
  #初期化
  row = 0
  c_new = copy.deepcopy(c)
  #ビットシフト
  while bit:
    a = bit%2
    #print('a',a)
    #print('row',row)
    if(a):
      if row < H:
        for i in range(W):
            c_new[row][i] = '.'
      else:
        for j in range(H):
            c_new[j][row-H] = '.'
    row += 1
    bit = bit>>1
  #print(c_new)
  #カウント
  count = 0
  for i in range(H):
    for j in range(W):
      if c_new[i][j] == '#':
        count+=1
  #print(count)
  if count == K:
    ans+=1

    

print(ans)
#print(2>>1)

Measured memory_bytes: 9356
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
S = list(input())
f = True
if not N&1:
    n = N//2
    for i in range(n):
        if S[i]!=S[i+n]:
            f = False
else:
    print('No')
    exit()
if f:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#include<algorithm>
#include<functional>
#include<queue>
using namespace std;
typedef pair<int,int>P;
const int N=100;

int vertex[N];
vector<vector<int> >edge(N);
vector<P> v(N);

//ツ陳クツ点xツつゥツづァツ陳クツ点yツづ鳴行ツつュツ本ツ青板づ個古つ青板づーツ仰づ淞づゥ
void F(int x,int y,int n,double(&dp)[N])
{
	int i,j,k;
	fill(dp,dp+N,0.);
	dp[x]=1;
	vector<P>::iterator ite1,ite2;
	ite1=lower_bound(v.begin(),v.end(),P(vertex[x],0));
	ite2=lower_bound(v.begin(),v.end(),P(vertex[y]+1,-1));
	for(;ite1!=ite2;++ite1)
	{
		j=ite1->second;
		for(k=0;k<edge[j].size();++k)dp[edge[j][k]]+=dp[j];
	}
}
int main()
{
	int n,m,p,x,y,w,i,dist[N][N],X=0x3f3f3f3f;
	while(scanf("%d%d%d",&n,&m,&p),n)
	{
		memset(dist,X,sizeof(dist));
		memset(vertex,X,sizeof(vertex));
		for(i=0;i<n;++i)edge[i].clear();
		while(m--)
		{
			scanf("%d%d%d",&x,&y,&w);
			dist[y][x]=dist[x][y]=w;
		}
		priority_queue<P,vector<P>,greater<P> >q;
		q.push(P(0,0));
		while(!q.empty())
		{
			P p(q.top());q.pop();
			if(vertex[p.second]<=p.first)continue;
			vertex[p.second]=p.first;
			for(i=0;i<n;++i)if((w=dist[p.second][i])!=X)q.push(P(p.first+w,i));
		}
		bool flag[N]={};
		q.push(P(0,n-1));
		while(!q.empty())
		{
			P p(q.top());q.pop();
			for(i=0;i<n;++i)
				if(w=dist[i][p.second],vertex[i]+w==vertex[p.second])
				{
					edge[i].push_back(p.second);
					if(!flag[i])
					{
						q.push(P(0,i));
						flag[i]=1;
					}
				}
		}
		double dp[N];
		for(i=0;i<n;++i)v[i]=P(vertex[i],i);
		for(i=n;i<N;++i)v[i]=P(X,X);
		sort(v.begin(),v.end());
		F(0,n-1,n,dp);
		while(p--)
		{
			scanf("%d",&x);
			if(x!=n-1&&edge[x].empty())printf("%.9f\n",0.);
			else
			{
				double dp2[N]={},dp3[N]={};
				F(x,n-1,n,dp2);
				F(0,x,n,dp3);
				printf("%.9f\n",dp2[n-1]*dp3[x]/dp[n-1]);
			}
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>

int main(void)
{

	int d,n,m;
	double mean;

	scanf("%d %d %d",&n,&m,&d);

	if (d==0) {
		mean = (double)1 / n * (m-1);
	}
	else {
		mean = (2 - ((double)2 * d / n)) / n * (m-1);
	}
	
	printf("%.10f\n",mean);

	
	return 0;
}



Measured memory_bytes: 128
#include<algorithm>
#include<vector>
#include<list>
#include<iostream>
#include<utility>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<iterator>
#include<map>
#include<limits>
#include<iomanip>
#include<ctime>
#include<cmath>
 
const int INF=2147483647;
const long long MOD=1e9+7;
 
using namespace std;

int n;

int main(){
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>n;
    
    vector<long long> vi(n);
    for(int i=0; i<n; i++){
        cin>>vi[i];
    }
    sort(vi.begin(),vi.end());
    vector<long long> sums(n,0);
    for(int i=1; i<n; i++){
        sums[i]=sums[i-1]+vi[i-1];
    }
    int ans=1;
    vector<bool> canMake(n,false);
    canMake[n-1]=true;
    for(int i=n-2; i>=0 && canMake[i+1]; i--){
        if(2*(sums[i]+vi[i])>=vi[i+1]){
            ans++;
            canMake[i]=true;
        }
    }
    cout<<ans;
    
    
    
    return 0;
    
    
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int cnt[N];
int main()
{
	int n, ans;
	scanf("%d", &n);
	scanf("%s", s + 1);
	for(int i = 1; i <= n; i++)
		if(s[i] == 'R')
			cnt[i] = cnt[i - 1] + 1;
		else
			cnt[i] = cnt[i - 1];
	ans = cnt[n] - cnt[cnt[n]];
	printf("%d",ans); 
	return 0;
}

Measured memory_bytes: 4744