akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

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

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

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  string t, p;
  cin >> t >> p;

  int ts = t.size();
  int ps = p.size();
  vector<int> a(ps+1);
  int j = a[0] = -1;
  rep(i,ps) {
    while (j >= 0 && p[i] != p[j]) j = a[j];
    ++j;
    if (p[i+1] == p[j])
      a[i+1] = a[j];
    else 
      a[i+1] = j;
  }

  vector<int> ans;
  int pi = 0;
  rep(ti,ts) {
    while (pi > -1 && p[pi] != t[ti])
      pi = a[pi];
    pi++;
    if (pi >= ps) {
      ans.push_back(ti - pi + 1);
      pi = a[pi];
    }
  }

  for (auto a : ans) cout << a << endl;

  return 0;
}



Measured memory_bytes: 8456
#include <stdio.h>
#include <cmath>
using namespace std;
int main(){
  int n, i;
  scanf("%d", &n);
  int x[n], y[n];
  for (i=0; i<n; i++) {
    scanf("%d", &x[i]);
  }
  for (i=0; i<n; i++) {
    scanf("%d", &y[i]);
  }

  double p1, p2, p3, pmax=abs(x[0]-y[0]);
  for (i=0; i<n; i++) {
    p1+=abs(x[i]-y[i]);
  }
  for (i=0; i<n; i++) {
    p2+=pow(x[i]-y[i], 2);
  }
  p2=pow(p2, 1/2.0);
  for (i=0; i<n; i++) {
    p3+=pow(abs(x[i]-y[i]), 3);
  }
  p3=pow(p3, 1/3.0);
  for (i=0; i<n; i++) {
    if (pmax<abs(x[i]-y[i])) pmax=abs(x[i]-y[i]);
  }
  
  printf("%lf\n", p1);
  printf("%lf\n", p2);
  printf("%lf\n", p3);
  printf("%lf\n", pmax);
}


Measured memory_bytes: 2932
n,k = map(int,input().split())
x = tuple(map(int, input().split()))

for i,v in enumerate(x):
    if v == 1:
        r = i
a,b = divmod(r,k-1)
if b > 0:
    a += 1
r = a * (k-1)

l = n-r-1
if l > 0:
    c,d = divmod(l, k-1)
    if d > 0:
        c += 1
    a += c

print(a)

Measured memory_bytes: 14008
n = int(input())
li = []
for i in range(n):
    a,b = map(int,input().split())
    tmp = [a+b,a,b]
    li.append(tmp)
li.sort(reverse=True)
x_sum = 0
y_sum = 0
for i,l in enumerate(li):
    if i%2 == 0:
        x_sum += l[1]
    else:
        y_sum += l[2]
print(x_sum-y_sum)
#print(li)

Measured memory_bytes: 23260
#pypyは内包表記使わない
def main():
    import sys
    #input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations
    #from itertools import accumulate, product
    from bisect import bisect_left,bisect_right
    from math import floor, ceil
    #from operator import itemgetter

    #mod = 1000000007

    N, M = map(int, input().split())
    if N==1 and M==1:
        print(1)
    elif N==1 or M==1:
        print(max(N, M)-2)
    else:
        print(N*M - ((N+M)*2 - 4))



if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <stdio.h>
#include <stdlib.h>
int main(){
  int X,Y;
  scanf("%d %d",&X,&Y);
  if(Y%2==1){
    printf("No");
    return 0;
  }
  if(Y-2*X>=0 && 4*X-Y>=0) printf("Yes");
  else printf("No");
  return 0;
}

Measured memory_bytes: 1736
N = 4
N2 = 16
mdt = Array.new(N2){Array.new(N2){0}}

N2.times{|i|
  N2.times{|j|
    mdt[i][j] = ((i / N) - (j / N)).abs + ((i % N) - (j % N)).abs
  }
}

dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
mat = Array.new(N2)
space = 0
md = nil
steps = 0;

N.times{|i|
  mat[N*i], mat[N*i+1], mat[N*i+2], mat[N*i+3] = gets.split.map(&:to_i)
}

pre_space = mat.index(0)
ini_md = 0
N2.times{|i|
  ini_md += mdt[i][mat[i]-1] unless i == pre_space
}

path = []
criteria = ini_md
tx = 0
ty = 0
mdt_diff = 0
loop do
  break if criteria >= 50;
  space = pre_space
  md = ini_md
  steps = 0
  path[0] = 4
  pre_direc = 0
  while steps >= 0 && md > 0 do
    sx = space / N
    sy = space % N

    direc = pre_direc-1
    loop do
      direc += 1
      break if direc == 4
      next if path[steps] ^ direc == 2
      tx = sx + dx[direc]
      ty = sy + dy[direc]
      next if tx < 0 || ty < 0 || tx == N || ty == N
      mdt_diff = mdt[sx*N+sy][mat[tx*N+ty]-1] - mdt[tx*N+ty][mat[tx*N+ty]-1]
      next if steps + 1 + md + mdt_diff > criteria
      break
    end
    if direc < 4 then
      mat[sx*N+sy], mat[tx*N+ty] = mat[tx*N+ty], mat[sx*N+sy]
      space = tx*N+ty
      md += mdt_diff
      steps += 1
      path[steps] = direc
      pre_direc = 0
    else
      direc = path[steps] ^ 2
      pre_direc = path[steps] + 1
      steps -= 1
      if steps >= 0 then
        rev_space = space + N * dx[direc] + dy[direc]
        md += mdt[space][mat[rev_space]-1] - mdt[rev_space][mat[rev_space]-1]
        mat[space], mat[rev_space] = mat[rev_space], mat[space]
        space = rev_space
      end
    end
  end
  break if steps >= 0
  criteria += 2;
end

puts steps

Measured memory_bytes: 8832
#include<bits/stdc++.h>
#define ll long 
#define pii pair<int,int>
#define F first
#define S second
#define MP make_pair
#define pss pair<string,string>
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
using namespace std;
const int N=2e3+5;
const ll mod=1e9+7;
int n,m,x[N],y[N];
ll dp[N][N];


int main()
{
	cin>>n>>m;
	for(ll i=1;i<=n;i++)cin>>x[i];
	for(ll i=1;i<=m;i++)cin>>y[i];
	for(ll i=0;i<N;i++)dp[i][0]=dp[0][i]=1;
	for(ll i=1;i<=n;i++)
	{
		for(ll j=1;j<=m;j++)
		{
			dp[i][j]=((dp[i-1][j]+dp[i][j-1])%mod-dp[i-1][j-1]+mod)%mod;//继承 
			if(x[i]==y[j])
				dp[i][j]=(dp[i][j]+dp[i-1][j-1])%mod;
		}
	}
	cout<<dp[n][m]<<endl;
	return 0;
}

Measured memory_bytes: 31616
#include<iostream>
#include<vector>
#include<string>
#include<map>
#include<set>
using namespace std;

int main()
{
    long long int a, b, c, d, ans;
    cin>>a>>b>>c>>d;
    ans = a*c;
    if(ans<a*d)
    {
        ans = a*d;
    }
    if(ans<b*c)
    {
        ans = b*c;
    }
    if(ans<b*d)
    {
        ans = b*d;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
 cin >>N ;
  vector<int>a(N);
  int sum = 0;
for (int i = 0; i < N ; i++) {
  cin >> a[i];
    sum += a[i];
}
  int mini = sum; 
  int prefix_sum = 0;
  for (int i = 0; i < N; ++i) { 
    cin >> a[i]; 
    prefix_sum += a[i]; 
    mini = min(mini, abs(prefix_sum - (sum - prefix_sum))); 
  }
cout << mini << endl;
 return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
XYZ = []
for _ in range(M):
    x,y,z = map(int, input().split())
    XYZ.append((x,y,z))
    
pairs = XYZ[:]
known = [False] * (N)

pairs = sorted(pairs)

# UnionFindの元
class UnionFind:
    def __init__(self, n):
        # n : ノード数（ノード番号は0始まり）
        self.par = [i for i in range(n)] # 各ノードの親
        self.rank = [0] * n              # 各木の高さ
        
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
        
    def is_group(self, x, y):
        return self.find(x) == self.find(y)
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

# UnionFindでグループ化
def create_union(edges, v_num):
    # edges: 辺
    # v_num: ノード数
    u = UnionFind(v_num)
    for x,y in edges:
        u.union(x,y)
        
    return [u.find(x) for x in range(v_num)]
     
    
edges = [(x,y) for x,y,z in pairs]

parents = create_union(edges, N+1)
union = set()
for p in parents:
    union.add(p)
union_num = len(union) -1
print(union_num)




Measured memory_bytes: 40760
#include<iostream>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;

int main(){
    int n;
    int S[1000];
    double sum = 0;
    double std = 0;
    double deviate = 0;
    while(1) {
        cin >> n;
        if (n == 0) break;
        for(int i = 0; i < n;i++) cin >> S[i];
        for(int i = 0; i < n; i++) {
            sum += S[i]; 
        }
        for (int i = 0; i < n; i++) {
            deviate += (S[i] - sum/n) * (S[i] - sum/n);  
        }
        
        printf("%lf\n",sqrt(deviate/n));
        sum = 0;
        std = 0;
        deviate = 0;    
    }
    
   
    return 0;
}

Measured memory_bytes: 1192
A,B,C,D=map(int,raw_input().split())

# 1..c
def F(c,x):
    if c<1:return 0
    return c-(c/x)

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
L=lcm(C,D)        
print(F(B,C)-F(A-1,C)+F(B,D)-F(A-1,D) - F(B,L)+F(A-1,L))


Measured memory_bytes: 2568
// Problem : A - ∴ (Therefore)
// Contest : AtCoder - AtCoder Beginner Contest 168
// URL : https://atcoder.jp/contests/abc168/tasks/abc168_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
#define int long long
#define fastio                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0);
#define sz(a) int((a).size())
#define pb push_back
#define mp make_pair
#define db1(x) cout << #x << "=" << x << endl
#define db2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z)                                                       \
  cout << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z \
       << endl
#define dbp(x) \
  cout << #x << "= {" << (x.first) << ", " << (x.second) << "}" << endl;
#define dbv(v)                         \
  {                                    \
    cout << #v << " : ";               \
    for (auto x : v) cout << x << ' '; \
    cout << endl;                      \
  }
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define rep2(i, a, b) for (int i = a; i >= b; i--)
#define die(x) return cout << x << '\n', 0;

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int32_t main() {
  fastio;
  //  freopen("input.txt", "r", stdin);
  //  freopen("output.txt", "w", stdout);
  int testcases;
  testcases = 1;
  // cin>>testcases;

  while (testcases--) {
    int n;
    cin >> n;
    n = n % 10;
    if (n == 2 || n == 4 || n == 5 || n == 7 || n == 9) die("hon");
    if (n == 3) die("bon");
    die("pon");
  }

  return 0;
}


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

const int MOD = 1000000007;

//long long
using ll = long long;

//出力系
#define print(x) cout << x << endl
#define yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define no cout << "No" << endl
#define NO cout << "NO" << endl
 
// begin() end()
#define all(x) (x).begin(),(x).end()

//for
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

//最大公約数（ll）
ll gcd(ll x, ll y) { return y ? gcd(y,x%y) : x;}

//素因数分解？
vector<pair<ll, int>>factorize(ll n){
  vector<pair<ll, int>> res;
  for(ll i = 2; i * i <= n; ++i){
    if(n % i) continue;
    res.emplace_back(i, 0);
    while(n % i == 0){
      n /= i;
      res.back().second++;
    }
  }
if(n != 1) res.emplace_back(n, 1);
return res;
}




int main() {
 string S;
 cin >> S;

 vector<string>inputs = { "dream", "dreamer", "erase", "eraser"};
 reverse(all(S));
 REP(i, 4) reverse(all(inputs.at(i)));


 int pos = 0;
 while(true){
   bool update = false;
   REP(i, inputs.size()){
     if(S.substr(pos, inputs.at(i).size()) == inputs.at(i)){
       update = true;
       pos += inputs.at(i).size();
       break;
     }
   }
 if(!update) break;
 
 }

if(pos == S.size()) YES;
else NO;


}

Measured memory_bytes: 512
import numpy as np

N, T = map(int, input().split())
ABs = [tuple(map(int, input().split())) for _ in range(N)]

dp = np.zeros((N+1, 2, T), np.int64)
for i, (A, B) in enumerate(ABs):
    dp[i+1] = dp[i]
    dp[i+1, 1] = np.maximum(dp[i, 0] + B, dp[i+1, 1])
    dp[i+1, :, A:] = np.maximum(dp[i, :, :-A] + B, dp[i+1, :, A:])

print(np.max(dp[N]))

Measured memory_bytes: 167736
//
// Created by yamunaku on 2019/07/20.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vector<int>> mti;
typedef vector<ll> vl;
typedef vector<vector<ll>> mtl;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<int> l(n+1,0),r(n+1,0);
    rep(i,n){
        l[i+1]=max(l[i],a[i]);
    }
    per(i,n){
        r[i]=max(r[i+1],a[i]);
    }
    rep(i,n){
        cout << max(l[i],r[i+1]) << endl;
    }
    return 0;
}


Measured memory_bytes: 3968
#include <iostream>
using namespace std;
using ll = long long;

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

    ll X[N], Y[N];
    for (int i = 0; i < N; ++i) {
        cin >> X[i] >> Y[i];
    }

    // 可能性判定: X + Yのparityが全部一致していればOK
    // 負数の除算はタブーなので2^35を足している
    int parity = (X[0] + Y[0] + (1LL << 35)) % 2;
    for (int i = 1; i < N; ++i) {
        if ((X[i] + Y[i] + (1LL << 35)) % 2 != parity) {
            cout << -1 << endl;
            return 0;
        }
    }

    // 偶数の場合は最後にLをくっつけることにして奇数に変換する
    if (parity == 0) {
        for (int i = 0; i < N; ++i) {
            ++X[i];
        }
    }

    // 実際は2^kか-2^kを選択だが,
    // 下駄として2^35-1を足すことで, 0か2^(K+1)を選択するように変更
    // さらに2で割ることで, 0か2^kを選択するように
    cout << 36 - parity << endl;
    for (int k = 0; k < 35; ++k) {
        cout << (1LL << k) << " ";
    }
    if (parity == 0) cout << 1;
    cout << endl;

    // (X, Y) -> (X - Y, X + Y)に変換
    // さらに2^35-1だけ下駄を履かせ, 2で割る
    for (int i = 0; i < N; ++i) {
        ll tmp = X[i];
        X[i] -= Y[i];
        Y[i] += tmp;

        X[i] += (1LL << 35) - 1;
        X[i] /= 2;
        Y[i] += (1LL << 35) - 1;
        Y[i] /= 2;
    }

    // 後はX, Yをそれぞれ2進変換
    // 各指示に対応する変化
    // L -> -X, -Y  R -> +X, +Y
    // U -> -X, +Y  D -> +X, -Y
    string order = "LDUR";
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < 35; ++k) {
            int kind = 0;
            if ((X[i] >> k) & 1) kind += 1;
            if ((Y[i] >> k) & 1) kind += 2;
            cout << order[kind];
        }
        if (parity == 0) cout << "L";
        cout << endl;
    }
    return 0;
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(t, x) t ipt; cin >> ipt; x.push_back(ipt);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
ll n, cnt, ans, tmp, sum, a, b, c, d, k, m, h, w, q, x, y;
string s, t;

int main() {
    cin >> n >> d >> x;
    sum = 0;
    NREP() {
        cin >> a;
        cnt = 1;
        while (cnt <= d) {
            sum++;
            cnt += a;
        }
    }
    MSG(x + sum)
}


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

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

    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
        a[i]--;
    }

    std::vector<bool> is_pushd(n, false);

    int ptr = 0;
    int count = 0;
    while (1) {
        count++;
        if (a[ptr] == 1) {
            std::cout << count << std::endl;
            return 0;
        }

        if (is_pushd[ptr] == true) {
            std::cout << -1 << std::endl;
            return 0;
        }
        is_pushd[ptr] = true;
        ptr = a[ptr];
    }
}


Measured memory_bytes: 640
#include <iostream>

using namespace std;

int main()
{
    int n , count ;
    string s ;
    cin >> n >> s ;
    int sz = s.size();

    count = 0;
    for (int i = 0 ; i < sz ; i++){

        if(s[i]== 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
                count++;

        }

    }
        cout << count << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<string>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<climits>
#include<set>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
using namespace std;
typedef pair<int, int> pii;
typedef long long int ll;
typedef pair<ll, ll> pll;
int dx[4] = { 1,0,0,-1 };
int dy[4] = { 0,1,-1,0 };
#define MOD 1000000007
#define ARRAY_MAX 100005

//const int INF = 1e9 + 7;


int main() {

	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}

	ll res = 0;

	for (int digit = 28; digit >= 0; digit--)
	{
		int bekihigh = 1 << (digit + 1);
		int bekilow = 1 << (digit);
		for (int i = 0; i < n; i++)
		{
			a[i] %= bekihigh;//2^(k+1)の余りを取る
			b[i] %= bekihigh;
		}
		sort(b.begin(), b.end());

		ll num = 0;
		for (int i = 0; i < n; i++)
		{
			num += (lower_bound(b.begin(), b.end(), 2 * bekilow - a[i]) - lower_bound(b.begin(), b.end(), bekilow - a[i])) + (lower_bound(b.begin(), b.end(), 4 * bekilow - a[i]) - lower_bound(b.begin(), b.end(), 3 * bekilow - a[i]));
		}
		if (num & 1) {
			res += bekilow;
		}
	}
	cout << res << endl;


	return 0;
}


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

dic = {}

for _ in range(N):
    a = input()
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1

m = max(dic.values())
l = [k for k in dic if dic[k] == m]
l.sort()
for s in l:
    print(s)

Measured memory_bytes: 35420
#include <iostream>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;

int main(){
    int n;  cin >> n;
    int ans = 0;
    rep(i, n){
        int a;  cin >> a;
        ans += a-1;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc *bufio.Scanner = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}()

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}
func nextString() string {
	sc.Scan()
	return sc.Text()
}

func build(n int, l, r string) string {
	result := make([]rune, n*2)
	ll := []rune(l)
	rr := []rune(r)
	for i := 0; i < n; i++ {
		ii := i * 2
		result[ii] = ll[i]
		result[ii+1] = rr[i]
	}
	return string(result)
}

func main() {
	n := nextInt()
	s, t := nextString(), nextString()
	r := build(n, s, t)

	fmt.Println(r)
}


Measured memory_bytes: 640
/*
ID: rajiv
TASK: test
LANG: C++14
*/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<queue>
#include<stack>
#include<iomanip>
#include<sstream>
#include<iterator>
#include<random>
#include<chrono>

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ONLINE_JUDGE

using namespace std;

#define deb(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) { cout << '\n';}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << '[' << *it << " = " << a << "]  ";
    err(++it, args...);
}
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
int rnd(int a, int b){ // including a and b
	return a+(rng()%(b-a+1));
}
#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sortr(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb push_back
#define endl '\n'

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<lli, lli> tii;
typedef tuple<lli, lli, lli> tiii;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

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

void solve(){
	int n; cin>>n;
	lli ans=1,x;
	bool f=false, z=false;
	lli k=3e18,h=1e18;
	rep(i,n){
		cin>>x;
		if(x==0) z=true;
		if(z) continue;
		//deb(x, ans, (k/ans), (x<=(k/ans)), x*ans)
		if(x<=(k/ans)){
			if(x*ans>h){
				f=true;
			}else{
				ans=ans*x;
			}		
		}else{
			f=true;
		}	
	}
	//deb("final", (ans>1e18))
	if(z) cout<<"0"<<endl;
	else if(f) cout<<"-1"<<endl;
	else cout<<ans<<endl;	
}

int main(){
	fast_io
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	freopen("test.out", "w", stdout);
	#endif 
	int tc=1;
	//cin>>tc;
	while(tc--){solve();}
	return 0;
}

/*
31
3
101 9901 999999000001

3
101 9901 999999000001


;
[x = 101]  [ans = 1]  [(3e18/ans) = 3e+18]  [(x<=(3e18/ans)) = 1]  [x*ans = 101]
[x = 9901]  [ans = 101]  [(3e18/ans) = 2.9703e+16]  [(x<=(3e18/ans)) = 1]  [x*ans = 1000001]
[x = 999999000001]  [ans = 1000001]  [(3e18/ans) = 3e+12]  [(x<=(3e18/ans)) = 1]  [x*ans = 1000000000000000001]
["final" = final]  [(ans>1e18) = 0]
1 000 000 000 000 000 001
[Program finished]

*/

Measured memory_bytes: 3652
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
ans=0
for i in range(n):
    if b[i]<=a[i]: ans+=b[i]
    elif b[i]>a[i]+a[i+1]:
        ans+=a[i]+a[i+1]
        a[i+1]=0
    else:
        ans+=b[i]
        a[i+1]=a[i+1]+a[i]-b[i]
print(ans)

Measured memory_bytes: 81892
#include<stdio.h>
int main(){
  int w,h,i,j,k,x,y,nx,ny,min,m,han,a;
  char g;
  int Y[9]={2,1,1,0,0,0,-1,-1,-2};
  int X[9]={1,1,2,1,2,3,1,2,1};
  int c[2][62][32],f[2][62][32],d[62][32];
  while(scanf("%d %d",&w,&h),w||h){
    int ans=2100000000;
    for(i=0;i<h;i++){
      for(j=0;j<w;j++){
	c[0][i][j]=c[1][i][j]=200000000;
	f[0][i][j]=f[1][i][j]=0;
	scanf(" %c",&g);
	if     (g=='S')d[i][j]=c[0][i][j]=c[1][i][j]=0;
	else if(g=='T')d[i][j]=-1;
	else if(g=='X')d[i][j]=100000000;
	else           d[i][j]=g-'0';
	if(g=='X'||g=='T')f[0][i][j]=f[1][i][j]=2;
      }
    }
    while(han=1){
      min=2100000000;
      for(i=0;i<h;i++){
	for(j=0;j<w;j++){
	  for(k=0;k<2;k++){
	    if(f[k][i][j])continue;
	    han=0;
	    if(min>c[k][i][j]){
	      y=i;
	      x=j;
	      m=a=1-k;
	      min=c[k][i][j];
	    }
	  }
	}
      }
      if(han)break;//printf("%d %d\n",y,x);
      if(m==0)m--;
      for(i=0;i<9;i++){
	ny=y+Y[i];
	nx=x+X[i]*m;
	if(nx<0||w<=nx||ny<0||h<=ny)continue;
	if(d[ny][nx]==-1){//printf("d%d %d\n",y,x);
	  if(ans>c[1-a][y][x])ans=c[1-a][y][x];
	  continue;
	}
	if(c[a][ny][nx]>c[1-a][y][x]+d[ny][nx]){
	   c[a][ny][nx]=c[1-a][y][x]+d[ny][nx];
	}
      }
      f[1-a][y][x]=1;
    }
    /*for(k=0;k<2;k++){
      for(i=0;i<h;i++){
	for(j=0;j<w;j++)printf("%10d",c[k][i][j]);
	printf("\n");
      }
      printf("\n");
      }//*/
    if(ans>100000000)printf("-1\n");
    else              printf("%d\n",ans);
  }
  return 0;
}

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

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}


struct Corr {
    ll y;
    ll x;
    ll depth;
};

ll H, W;  // 迷路の縦，横
ll s_y, s_x, g_y, g_x;  // スタート，ゴールの座標
ll y, x, depth;  // キューから取り出した座標
vector<string> maze;  // 座標を受け取る配列
queue<Corr> q;

vector<ll> y_vec = {0, 0, -1, +1};  // 進む方向の簡便化，テクニックとして覚えておく．
vector<ll> x_vec = {-1, +1, 0, 0};  // ループで回すことで上下左右に移動できるようになっている

ll bfs(vector<vector<ll>> &path) {
    ll res = 0;
    while (!q.empty()) {
        // キューの先頭の要素を取り出す dequeue(pop)
        Corr now = q.front(); q.pop();
        y = now.y, x = now.x, depth = now.depth;

        // BFS
        for (int i = 0; i < 4; ++i) {
            Corr next = {y + y_vec[i], x + x_vec[i], depth + 1};
            if (0 <= next.y && next.y < H && 0 <= next.x && next.x < W && maze[next.y][next.x] == '.') {
                if(path[next.y][next.x]!=-1){
                    continue;
                }else{
                    res = max(res, next.depth);
                    path[next.y][next.x] = next.depth;
                    q.push(next);
                }
            }
        }
    }
    return res;
}

int main(){

    cin >> H >> W;
    rep(i,H){
        string s;
        cin >> s;
        maze.push_back(s);
    }

    ll ans = 0;
    rep(i,H){
        rep(j,W){
            if(maze[i][j]=='#'){
                continue;
            }
            vector<vector<ll>> path(H, vector<ll> (W, -1));
            path[i][j] = 0;
            Corr start = {i, j, 0};
            q.emplace(start);
            ans = max(ans, bfs(path));
        }
    }
    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 256
def root a
	return a if @p[a] == a
	return (@p[a] = root(@p[a]))
end

def isSameSet a, b
	return root(a) == root(b)
end

def unite a, b
	@p[root(a)] = root(b)
end

@fib=[1,1]
n=0
def f n
	return if n >= 1010
	@fib.push @fib[-1]+@fib[-2]
	f n+1
end
f 1

while true
	arg=gets
	break if arg == nil
	v,d=arg.split(" ").map{|e|e.to_i}
	
	@nowFib = @fib[(2..v+1)]
	@nowFib=@nowFib.map{|e|e%1001}
	@nowFib.sort!
	@p=[]
	v.times{|t|@p.push t}
	(v-1).times{|t|
		unite(t+1, t) if (@nowFib[t+1]-@nowFib[t]) < d
	}
	p @p.uniq.count
end

Measured memory_bytes: 6284
n, q = gets.strip.split.map(&:to_i)
ab = (n-1).times.map {|line| gets.strip.split.map(&:to_i) }
pq = readlines.map {|line| line.strip.split.map(&:to_i) }

graph = Array.new(n+1) { [] }
ab.each do |a, b|
  graph[a] << b
  graph[b] << a
end

tree = Array.new(n+1, 0)
pq.each do |p, x|
  tree[p] += x
end

checked = Array.new(n+1, false)
currents = [1]

until currents.empty?
  current = currents.shift
  next if checked[current]

  checked[current]=true
  graph[current].each do |cc|
    next if checked[cc]
    tree[cc] += tree[current]
  end

  graph[current].each do |cc|
    currents << cc unless checked[cc]
  end
end

puts tree[1..n].join(' ')



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

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

  ll X, Y, A, B, C;
  cin >> X >> Y >> A >> B >> C;

  vector<pair<ll, char>> vp(A+B+C);

  for (ll i = 0; i < A; i++)
  {
    ll a;
    cin >> a;
    vp.at(i) = make_pair(10e+9 - a, 'r');
  }
  for (ll i = 0; i < B; i++)
  {
    ll b;
    cin >> b;
    vp.at(A+i) = make_pair(10e+9 - b, 'g');
  }
  for (ll i = 0; i < C; i++)
  {
    ll c;
    cin >> c;
    vp.at(A+B+i) = make_pair(10e+9 - c, 't');
  }

  sort(vp.begin(), vp.end());
  ll r_cnt = 0;
  ll g_cnt = 0;
  ll t_cnt = 0;
  ll ans = 0;
  for (int i = 0; i < vp.size(); i++)
  {
    if(vp.at(i).second == 'r')
    {
      if(r_cnt == X) continue;
      else r_cnt++;
    } 
    if(vp.at(i).second == 'g')
    {
      if(g_cnt == Y) continue;
      else g_cnt++;
    } 
    if(vp.at(i).second == 't') t_cnt++;
    ans += vp.at(i).first;

    if(r_cnt + g_cnt + t_cnt == X + Y) break; 
  }

  ans = 10e+9 * (X+Y) - ans;
  cout << ans << endl;
  
  return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
int main()
{   /// Standing in the hall of fame
    ios_base::sync_with_stdio() , cin.tie(NULL) , cout.tie(NULL);
    int a , s = 0;
    for(int i = 0 ; i < 3 ; i++)
        cin >> a , s += a;
    if(s < 22)cout << "win\n";
    else      cout << "bust\n";
    return 0;
}

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

int main() {
  string s, t;
  cin >> s >> t;
  
  sort(s.begin(), s.end());
  
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  
  if(s < t){
    cout << "Yes" << endl;
  }
  else cout << "No" << endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
 
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
 
int mainC()
{
	string str;
	cin >> str;
	int n = stoi(str);
	map<string, int> strMap;
	long long m = 0;
	for (int i = 0; i < n; ++i)
	{
		cin >> str;
		sort(str.begin(), str.end());
        m += strMap[str];
		strMap[str]++;
	}
 
//	long long m = 0;
//	for (const auto& x : strMap)
//	{
//		auto k = x.second;
//		if(k > 1)
//			m += (k - 1) * k;
//	}
//	m /= 2;
	cout << m << endl;
	return 0;
 
}
 
int main()
{
	return mainC();
}

Measured memory_bytes: 11136
import sys

def solve():
    input = sys.stdin.readline
    H, W = map(int, input().split())
    if H == 1 or W == 1: print(1)
    else: 
        Ans = (H // 2 + H % 2) * (W // 2 + W % 2) + (H // 2) *  (W // 2)
        print(Ans)

    return 0

if __name__ == "__main__":
    solve()

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

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> p(N);
    for (int i = 0; i < N; i++) {
        cin >> p[i];
    }
    sort(p.begin(), p.end());

    ll output = 0;
    for (int i = 0; i < K; i++) {
        output += p[i];
    }

    cout << output << endl;

    return 0;
}


Measured memory_bytes: 3600
/**
 * File    : D.cpp
 * Author  : Kazune Takahashi
 * Created : 2018-5-5 21:10:07
 * Powered by Visual Studio Code
 */

#include <iostream>
#include <iomanip>   // << fixed << setprecision(xxx)
#include <algorithm> // do { } while ( next_permutation(A, A+xxx) ) ;
#include <vector>
#include <string> // to_string(nnn) // substr(m, n) // stoi(nnn)
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map> // if (M.find(key) != M.end()) { }
#include <set>
#include <random> // random_device rd; mt19937 mt(rd());
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;

#define DEBUG 0 // change 0 -> 1 if we need debug.

typedef long long ll;

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

// const int C = 1e6+10;
// const ll M = 1000000007;

const int MAX_SIZE = 1000010; // 10000010でもよさそう？
bool isprime[MAX_SIZE];
vector<ll> prime_num;

void init()
{
  fill(isprime, isprime + MAX_SIZE, true);
  isprime[0] = isprime[1] = false;
  for (auto i = 2; i < MAX_SIZE; i++)
  {
    if (isprime[i])
    {
      prime_num.push_back(i);
      for (auto j = 2; i * j < MAX_SIZE; j++)
      {
        isprime[i * j] = false;
      }
    }
  }
}

bool prime(long long x)
{ // 2 \leq x \leq MAX_SIZE^2
  if (x < MAX_SIZE)
  {
    return isprime[x];
  }
  for (auto e : prime_num)
  {
    if (x % e == 0)
      return false;
  }
  return true;
}

int main()
{
  init();
  int N;
  cin >> N;
  vector<ll> A;
  for (auto x : prime_num)
  {
    assert(x <= 55555);
    if (x % 5 == 1)
    {
      A.push_back(x);
      if ((int)A.size() == N)
      {
        break;
      }
    }
  }
  for (auto i = 0; i < N; i++)
  {
    cout << A[i];
    if (i < N-1)
    {
      cout << " ";
    }
    else
    {
      cout << endl;
    }
  }
}


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

# aの合計値がbの合計値を下回る場合は終了
total_a = sum(a)
total_b = sum(b)
if total_a < total_b:
  print(-1)
  exit()
  
# 数列aと数列bの差分を取得  
nums = [0]*n
for i in range(n): nums[i] = a[i] - b[i]
nums.sort()

ans = 0
m = 0
for i in range(n): # 差分がマイナスの値の合計と数を取得
  if nums[i] < 0:
    m += nums[i]
    ans += 1
  else: break

# 差分の大きい値から順にマイナス分を相殺していき、マイナスが終了した時点の変更数を回答する
for i in reversed(range(n)):
  if m >= 0:
    print(ans)
    break
  else:
    m += nums[i]
    ans += 1

Measured memory_bytes: 24200
package main
 
import (
	"bufio"
	"fmt"
	"log"
	"os"
	"strconv"
)
 
func run() {

	var N int64;
    N = nextInt();
    p := make([]int64,N);
    for i := 0 ; i < int(N) ; i++ {
        p[i] = nextInt();
    }
	solve(N, p);

}

func solve(N int64, p []int64){
	count := 0
	for i := 0; i < int(N); i++ {
		if i+1 != int(p[i]) {
			count++
		}
	}
	if count > 2 {
		Println("NO")		
	}else{
		Println("YES")
	}
}


// --- template ---
// Thanks https://gist.github.com/halllllll/853ab587fd82ee3ffe6f7fb7fb499695
 
var sc = bufio.NewScanner(os.Stdin)
var out = bufio.NewWriter(os.Stdout)
 
// Caution: You will get unexpected result if a single token is larger than this size.
const BufferSize = 64 * 1024 * 1024
 
func Print(a ...interface{}) (n int, err error) {
	return fmt.Fprint(out, a...)
}
 
func Printf(format string, a ...interface{}) (n int, err error) {
	return fmt.Fprintf(out, format, a...)
}
 
func Println(a ...interface{}) (n int, err error) {
	return fmt.Fprintln(out, a...)
}
 
func next() string {
	sc.Scan()
	return sc.Text()
}
 
func nextInt() int64 {
	a, err := strconv.ParseInt(next(),10, 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}

func nextFloat() float64 {
	a, err := strconv.ParseFloat(next(), 64)
	if err != nil {
		log.Fatal(err)
	}
	return a
}


type IntHeap []int
func (h IntHeap) Len() int           { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IntHeap) Push(x interface{}) {
	// Push and Pop use pointer receivers because they modify the slice's length,
	// not just its contents.
	*h = append(*h, x.(int))
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

/////数字と文字
// 基本クラス
type NS struct {
    Num int
    Str string
}

//////　数字と数字
// 基本クラス
type NN struct {
    Num1 int
    Num2 int
}

 
func main() {
	sc.Buffer(make([]byte, 0, BufferSize), BufferSize)
	sc.Split(bufio.ScanWords)
	run()
	out.Flush()
}



Measured memory_bytes: 2816
#include <stdio.h>
#include <stdlib.h>
#define N 500000

void maxheapify(int);

int n,arr[N+1];
int main(){
  int i,node;

  scanf("%d",&n);
  if(n>N) exit(2);
  for(i=1;i<=n;i++){
    scanf("%d",&arr[i]);
  }

  for(i=n/2;i>=1;i--){
    maxheapify(i);
  }

  for(i=1;i<=n;i++){
    printf(" %d",arr[i]);
  }
  printf("\n");
  
  
  return 0;
}

void maxheapify(int node){
  int left,right,max,temp;
  left=node*2;
  right=node*2+1;
  if(left<=n && arr[left]>arr[node]) max = left;
  else max = node;
  if(right<=n && arr[right]>arr[max]) max = right;
  
  if(max != node){
    temp=arr[node];
    arr[node]=arr[max];
    arr[max]=temp;
    maxheapify(max);
  }
}



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

int main() {
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;
    vector<int> L(Q), R(Q);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        L[i] = l; R[i] = r;
    }

    vector<int> cnt(N);
    cnt[0] = 0;
    for (int i = 1; i < N; i++) {
        cnt[i] = cnt[i - 1];
        if (S[i - 1] == 'A' && S[i] == 'C')
            cnt[i]++;
    }

    for (int i = 0; i < Q; i++)
        cout << cnt[R[i]] - cnt[L[i]] << endl;
    return 0;
}

Measured memory_bytes: 2176
#include<stdio.h>
int main(){
  int n,m,a;
  char s[50]={"kogakubu10gokan"};
  for(scanf("%d %d",&n,&m);n--;scanf("%s",s)){
    scanf("%d",&a);
    if(a<=m)continue;
    printf("%s\n",s);
    m=100;
  }
  if(m-100)printf("%s\n",s);
  return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, start, n) for (ll i = (ll)(start); i < (ll)(n); ++i)
int N, M;
void func()
{
    ll A, V, B, W, T;
    cin >> A >> V;
    cin >> B >> W;
    cin >> T;
    bool ans = false;
    if (V > W)
    {
        if (abs(B - A) <= (V - W) * T)
            ans = true;
    }
    if (ans)
        cout << "YES\n";
    else
        cout << "NO\n";
}
int main()
{
    func();
}

Measured memory_bytes: 3580
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
ll power(ll x,ll n)
{
	ll res =1;
	while(n>0)
	{
		if(n%2==1)
	res=res*x;
	x=x*x;
	n=n/2;
	}
	return res;
	
}

int main(){

ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i,x;
    int a,b;
    cin>>a>>b;
    for(i=1;i<2000;i++)
    {
    	if((8*i)/100==a&&(10*i)/100==b)
    	{
    		cout<<i;
    		return 0;
		}
	}
	cout<<-1;
	
	
}


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

import collections
c = collections.Counter(a)
m = c.most_common()
ans = 0
if len(m)<=k:
    print(0)
else:
    for i in range(k, len(m)):
        ans += m[i][1]
    print(ans)

Measured memory_bytes: 39348
// #include<iostream>
// #include<vector>
// #include<algorithm>
// #include<map>
// #include<cstring>
// #include<math.h>
// #include<bitset>
// #include<queue>
// #include<set>
// #include<iomanip>
// #include<math.h>
// #include<assert.h>
// #include<string>
// #include<cstdlib>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 1LL << 40;
const double INFD = 1e100;
const ll mod = 1000000007;
const double PI = 3.1415926535897932384626433832795028841971;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
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;
}
// ----------------------------------------------------------------------------
int dp[105][100005];
int main(){
  int N;
  cin >> N;
  vector<int> s(N);
  for(int i=0; i<N; i++){
    cin >> s[i];
  }
  for(int i=0; i<105; i++){
    for(int j=0; j<100005; j++){
      dp[i][j] = 0;
    }
  }
  dp[0][0] = 1;
  for(int i=0; i<N; i++){
    for(int j=0; j<100005; j++){
      dp[i+1][j+s[i]] += dp[i][j];
      dp[i+1][j] += dp[i][j];
    }
  }
  int ans=0;
  for(int i=0; i<100005; i++){
    if(dp[N][i]){
      if(i%10){
        ans = i;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 41216
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


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

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;
bool prime[1100100];
void mainmain(){
	int n;
	rep(i,1100100) prime[i]=true;
	rep(i,2) prime[i]=false;
	for(int i=2;i*i<1100100;i++){
		if(prime[i]){
			for(int j=i*i;j<1100100;j+=i){
				prime[j]=false;
			}
		}
	}
	while(cin>>n,n){
		int ans=prime[n-2];
		for(int i=3;i*2<=n;i+=2){
			if(prime[i]&&prime[n-i]){
				ans++;
			}
		}
		cout<<ans<<endl;
	}
}



}
main() try{
    mainmain();
}
catch(...){
}

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int L = a + b;
    int R = c + d;
    if (L > R) {
        cout << "Left" << endl;
    }
    else if (L == R) {
        cout << "Balanced" << endl;
    }
    else if (L < R) {
        cout << "Right" << endl;
    }
}

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

string dp[70][70];

string comp(string a,string b){
  while(a[0]=='0')a=a.substr(1);
  while(b[0]=='0')b=b.substr(1);
  if(a.length()<b.length()){
    return b;
  }else if(a.length()>b.length()){
    return a;
  }else{
    int i=0;
    while(i<a.length() && a[i]==b[i])i++;
    if(i==a.length())return a;
    if(a[i]>=b[i]) return a;
    else return b;
  }
}

int main(){
  int h,w;
  while(cin>>w>>h,w){
    char grid[h+1][w+1];
    for(int i=1;i<=h;i++){
      for(int j=1;j<=w;j++){
	cin>>grid[i][j];
	if(grid[i][j]<'0' || '9'<grid[i][j])
	  grid[i][j]='0'-1;
      }
    }
    for(int i=0;i<=h;i++)
      for(string s:dp[i])
	s.clear();
    string res="";
    for(int i=1;i<=h;i++){
      for(int j=1;j<=w;j++){
	if(grid[i][j]=='0'-1){
	  dp[i][j]="";
	  continue;
	}
	if(j==0){
	  dp[i][j]=dp[i-1][j]+grid[i][j];
	}else{
	  dp[i][j]=comp(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
	}
	res=comp(dp[i][j],res);
      }
    }
    // cout << "dp:" << endl;
    // for(int i=1;i<=h;i++){
    //   for(string a:dp[i]){
    // 	cout << a << " ";
    //   }
    //   cout << endl;
    // }
    cout << res << endl;
  }
  return 0;
}

Measured memory_bytes: 1384
using System;
class p
{
  static void Main()
  {
    int N = int.Parse(Console.ReadLine());
    bool result = false;
    for (int i = 1; i < 10; i++) {
      if ((N%i==0) && (N/i<10)) {
        result = true;
        break;
      }
    }
    Console.WriteLine(result ? "Yes" : "No");
  }
}

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

#define ll long long
const ll INF = 1e18;
const int N = 5e3 + 5;
const int M = 205;

int n, m;
ll a[N], b[N][M], st[4*N], lz[4*N];
vector<int> s[M];

void pushDown(int id, int l, int r){
	if(lz[id] != 0){
		st[id] += lz[id];
		if(l < r){
			lz[id << 1] += lz[id];
			lz[id << 1 | 1] += lz[id];
		}
		lz[id] = 0;
	}
}
void update(int id, int l, int r, int i, int j, ll x){
	pushDown(id, l, r);
	if(l > j || r < i || i > j){
		return;
	}
	if(l >= i & r <= j){
		lz[id] += x;
		pushDown(id, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	update(id << 1, l, mid, i, j, x);
	update(id << 1 | 1, mid + 1, r, i, j, x);
	st[id] = max(st[id << 1], st[id << 1 | 1]);
}
ll get(int id, int l, int r, int i, int j){
	pushDown(id, l, r);
	if(l > j || r < i || i > j){
		return -INF;
	}
	if(l >= i && r <= j){
		return st[id];
	}
	int mid = (l + r) >> 1;
	return max(get(id << 1, l, mid, i, j), get(id << 1 | 1, mid + 1, r, i, j));
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i < n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			cin >> b[i][j];
		}
	}
	for(int i = 1; i <= m; i++){
		s[i].push_back(n + 1);
	}
	ll ans = -INF;
	for(int i = n; i >= 1; i--){
		for(int j = 1; j <= m; j++){
			int ptr = s[j].size() - 1;
			while(s[j].size() > 1 && b[i][j] > b[s[j][ptr]][j]){
				update(1, 1, n, s[j][ptr], s[j][ptr - 1] - 1, b[i][j] - b[s[j][ptr]][j]);
				s[j].pop_back();
				ptr = s[j].size() - 1;
			}
			s[j].push_back(i);
			update(1, 1, n, i, i, b[i][j]);
		}
		update(1, 1, n, i + 1, n, -a[i]);
		ans = max(ans, get(1, 1, n, i, n));
	}
	cout << ans;
}

Measured memory_bytes: 8704
#include <bitset>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <stdio.h>
#include <math.h>

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef vector<vector<int>> vvi;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;
typedef vector<ll> vll;

typedef pair<int, int> pii;

typedef queue<int> qi;
typedef queue<string> qs;


#define rep(i, n) for(int i=0; i<(n); ++i)
#define repp(i, a, b) for(int i = (a); i <= (b); i++)
#define repm(i, a, b) for(int i = (a); i >= (b); i--)

#define all(v) v.begin(), v.end()
//sort( all(v) )　などと使える

int main(){
    ll x; cin >> x;

    ll aa, bb;
    for(ll a = 0; a < 1000; a++) for(ll b = -1000; b < 1000; b++){
        if(pow(a, 5) - pow(b, 5) == x){
            aa = a, bb = b;
            break;
        }
    }

    cout << aa << " " <<  bb << endl;
}

Measured memory_bytes: 4100
## coding: UTF-8

X = int(input())

#l = [100]

now = 100
ans = 0
for i in range(3761):
    now = int(now * 1.01)
    #print(now)
    if(now >= X):
        ans = i+1
        break
    #l.append(now)

print(ans)
#print(l)

#ans = 0
#for i in range(3761):



'''
counter = 0
while now<10**18:
    counter += 1
    now = int(now*1.01)
print(counter)
'''

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

int main()
{
    int N, s_len, t_len, com_len = 0;
    string s, t;
    cin >> N >> s >> t;

    s_len = s.length();
    t_len = t.length();

    for (int i = min(s_len, t_len); i > 0; i--)
    {
        //cout << s.substr(s_len - i) << endl;
        //cout << t.substr(0, i) << endl;
        if (s.substr(s_len - i) == t.substr(0, i))
        {
            com_len = i;
            break;
        }
    }

    cout << max(N, s_len + t_len - com_len) << endl;

    return 0;
}

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

int main(){
int W,H,N;
  cin>>W>>H>>N;
  
  vector<int>x(N),y(N),a(N);
  for(int i=0; i<N; i++){
   cin>>x[i]>>y[i]>>a[i]; }
  
  int lx=0, ux=W, ly=0, uy=H;
  for(int i=0; i<N; i++){
   if(a[i]==1){lx=max(lx, x[i]);}
   if(a[i]==2){ux=min(ux, x[i]);}
   if(a[i]==3){ly=max(ly, y[i]);}
   if(a[i]==4){uy=min(uy, y[i]);}
  }
  
  if(ux<lx){ux=lx;}
  if(uy<ly){uy=ly;}
  
  cout<<(ux-lx)*(uy-ly)<<endl;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
 
if K==N+1:
    print(1)
elif K==N:
    print(N+2)
else:
    def tousawa(shokou, makkou, kosu):
        return int((shokou+makkou)*kosu/2)
    
    ans=0
    for i in range(K,N+2):
        ans+=tousawa(N-i+1,N,i)-tousawa(0,i-1,i)+1
    print(int(ans%(10**9+7)))


Measured memory_bytes: 9108
#include <iostream>

using namespace std;


//必须自底向上的调用本函数 ，这样，每执行一次，底层的树依次会满足最大堆性质 
void maxHeapify(int *Heap,int n,int i) {
	int l = 2*i;
	int r = 2*i+1;
	int maxI = i;
	if (l <= n && Heap[maxI]<Heap[l]) {
		maxI = l;
	}
	
	if (r <= n && Heap[maxI] < Heap[r]) {
		maxI = r;
	}
	
	if (maxI != i) {
		int t = Heap[i];
		Heap[i] = Heap[maxI];
		Heap[maxI] = t; 
		maxHeapify(Heap,n,maxI);
	}
}

void maxHeap(int *Heap,int n) {
	for (int i = n / 2;i>0;i--) {
		maxHeapify(Heap,n,i);
	}
} 
int main() {
	int n;
	cin >> n;
	int *Heap = new int[n+1]; 
	for (int i=1;i<=n;i++) {
		cin >> Heap[i];
	}
	maxHeap(Heap,n);
	for (int i=1;i<=n;i++) {
		cout << " ";
		cout << Heap[i];
		if (i == n) {
			cout << endl;
		}
	}
	delete[] Heap;
	return 0;
	
}


Measured memory_bytes: 4568