akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#define INT long long
using namespace std;

int n, p[60][30], c;
string s[60];
char ans[60];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i = 0 ; i < n ; i++ )
    {
        cin>>s[i];
        for(int j = 0 ; j < s[i].size() ; j++ )
            p[i][s[i][j]-'a']++;
    }
    while( 1 )
    {
        int mx = 0, id = -1;
        for(int j = 0 ; j < 26 ; j++ )
        {
            int mn = 100;
            for(int i = 0 ; i < n ; i++ )
            {
                if( mn > p[i][j] ) mn = p[i][j];
            }
            if( mx < mn ) mx = mn, id = j;
        }
        if( id == -1 ) break;
        for(int i = 0 ; i < mx ; i++ ) ans[c++] = (char)(id+'a');
        for(int i = 0 ; i < n ; i++ ) p[i][id] = 0;
    }
    sort(ans, ans+c);
    for(int i = 0 ; i < c ; i++ ) cout<<ans[i];
    cout<<endl;
    return 0;
}


Measured memory_bytes: 256
def main():
    n=int(input())
    x = [int(i) for i in input().split()]
    x_t = tuple(x)
    x.sort()
    l = x[int((len(x)/2 - 1))]
    u = x[int((len(x)/2))]
    for i in range(len(x_t)):
        if (x_t[i]<=l):
            print(u)
        else:
            print(l)
            
main()

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

int main() {
	int n, out = 1;
	cin >> n;

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

	for(int i = 1; i < n; i++) {
		for(int j = 0; j < i; j++) {
			if(h[j] > h[i]) {
				break;
			}
			if(j == i - 1) {
				out++;
			}
		}
	}

	cout << out << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long ll;
using namespace std;
int n;
int main(void){
    int n;
    string s;cin>>n>>s;
    int dp[n+1][n+1];//sの
    rep(i,n+1){
        rep(j,n+1){
            dp[i][j]=0;
        }
    }
    rep(i,n){
        rep(j,n){
            int ni=i+1,nj=j+1;
            if(s[i]==s[j]){
                dp[ni][nj]=dp[i][j]+1;
            }else{
                dp[ni][nj]=0;
            }
        }
    }
    int res=0;
    rep(i,n+1){
        rep(j,n+1){
            if(i-dp[i][j]<j)continue;
            res=max(res,dp[i][j]);
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 97920
import itertools   # accumulate, compress, permutations(nPr), combinations(nCr)
import bisect      # bisect_left(insert位置), bisect_right(slice用)
# import math        # factorical（階乗) # hypot(距離)
# import heapq
# from fractions import gcd # Python3.5以前 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # Python3.6以降
# --------------------------------------------------------------

n  = int(input())
bo = list(map(int,input().split()))
 
cnt = 0
bo.sort()
 
for a in range(n-1):
    for b in range(a+1,n):
        cnt += bisect.bisect_left(bo, bo[a]+bo[b]) - (b+1)

print(cnt)

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

const int MOD = 1e9+7;

typedef long long ll;

int main(){
  int n; cin >> n;
  int a[n+1],  table[n+1];
  memset(table, 0, sizeof(table));

  for(int i=1; i<=n; i++) {
    cin >> a[i];
    table[a[i]]++;
  }

  bool flag = true;
  ll ans = 1;

  for(int i=0; i<=n; i++){
    if(i==0) {
      flag &= (table[i]==1 && n%2==1) || (table[i]==0 && n%2==0);
    }
    else if(i%2){
      flag &= (table[i]==2 && n%2==0) || (table[i]==0 && n%2==1);
      if(n%2==0)(ans *= 2) %= MOD;
    }
    else{
      flag &= (table[i]==2 && n%2==1) || (table[i]==0 && n%2==0);
      if(n%2==1)(ans *= 2) %= MOD;
    }
  }

  cout << (flag?ans: 0) << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)
#define rrep(i,n) for(int i=1;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define maxs(a, b) a = max(a, b)
#define mins(a, b) a = min(a, b)
using namespace std;
typedef long long ll;
typedef pair<double, int> P;
const ll linf = (1ll << 61);
const int inf = 1001001001;
const int mod = 1000000007;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a;
	string b;
	cin >> a >> b;
	ll ans = a;
	ll k = (b[0] - '0') * 100 + (b[2] - '0') * 10 + (b[3] - '0');
	cout << ll(ans * k / 100) << endl;
	return 0;
}


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

int N, K;
int L[15], R[15];
long long imos[202020];
long long now = 1;

int main()
{
    cin >> N >> K;
    for (int i = 0; i < K; i++)
    {
        cin >> L[i] >> R[i];
    }

    for (int i = 1; i <= N; i++)
    {
        now += imos[i];
        now %= 998244353LL;
        for (int j = 0; j < K; j++)
        {
            if (i + L[j] < 202020)
            {
                imos[i + L[j]] += now;
            }
            if (i + R[j] + 1 < 202020)
            {
                imos[i + R[j] + 1] -= now;
            }
        }
        if (i == N)
        {
            while (imos[N] < 0LL)
            {
                imos[N] += 998244353LL;
            }
            cout << imos[N] % 998244353LL << endl;
        }
    }
}

Measured memory_bytes: 5108
#include<bits/stdc++.h>
#define ll long long int
#define vec vector<ll>
#define mat vector<vec>

using namespace std;

const ll mod=1000000007;
const ll inf=LONG_LONG_MAX;
ll dx4[4]={1,0,-1,0};
ll dy4[4]={0,-1,0,1};
ll dx8[8]={1,0,-1,1,-1,1,0,-1};
ll dy8[8]={1,1,1,0,0,-1,-1,-1};

ll dist(vec a,vec b){
  return abs(a[0]-b[0])+abs(a[1]-b[1]);
}

int main(){

  ll h,w,d;
  cin >> h >> w >> d;

  mat l(h*w+1);
  for(ll i=0;i<h;i++){
    for(ll j=0;j<w;j++){
      ll a;
      cin >> a;
      l[a]={i,j};
    }
  }

  //cout << 5 << endl;



  vector<vector<ll>> s(d+1,vec(h*w/d+10,0));
  for(ll i=1;i<=d;i++){
    for(ll j=0;i+d*(j+1)<=h*w;j++){
      s[i][j+1]=s[i][j]+dist(l[i+d*j],l[i+d*(j+1)]);
    }
  }

  ll q;
  cin >> q;

  vec ans;

  //cout << 5 << endl;

  for(ll i=0;i<q;i++){
    ll u,v;
    cin >> u >> v;
    ll y=u%d;
    if(y==0)y=d;
    ll x=(u-y)/d;
    ll z=(v-y)/d;
    ans.push_back(s[y][z]-s[y][x]);
    //cout << s[y][z] << " " << s[y][z] << endl;
  }

  for(ll i=0;i<ans.size();i++)cout << ans[i] << endl;

  //for(ll i=0;i<6;i++)cout << s[2][i] << endl;

}

Measured memory_bytes: 19716
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
ll fact(ll x, ll k, ll p) {//最大値、個数、あまり
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
short ctos(char a) {
	return (int)(a - '0');
}
#define int long long
const long long Inf = 4523372036854775807;
const int inf = 15000000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	int a, b;
	cin >> a >> b;
	if (a + b == 15) cout << "+" << endl;
	else if (a*b == 15)cout << "*" << endl;
	else cout << "x\n";
}

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

//頂点は0からN-1
struct UnionFind {
    //par[i]はiの親
    //親のときは木のサイズの-1倍
    vector<int> par;

    //すべてが根として初期化
    //ここの書き方がわからない
    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = -1;
    }
    
    // 木の根
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    // 木の併合
    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[ry] += par[rx];
        par[rx] = ry;
    }
    
    // x, yが属する木が同じか判定
    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    long long V,E;
    cin >> V >> E;
    UnionFind tree(V);
    int x[100005], y[100005];
    for(int i=0; i<E; i++){
        int p,q;
        cin >> p >> q;
        x[E-i-1] = p-1;
        y[E-i-1] = q-1;
    }
    long long s[100005];
    s[0]=V*(V-1)/2;
    for(int i=0; i<E; i++){
        int rx = tree.root(x[i]);
        int ry = tree.root(y[i]);
        if(rx == ry){
            s[i+1] = s[i];
        } else{
            long long sx =  tree.par[rx];
            long long sy =  tree.par[ry];
            s[i+1] = s[i] - sx*sy;
            tree.unite(rx,ry);
        }        
    }
    for(int i=0; i<E; i++) cout << s[E-1-i] << endl;
}

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

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  int cur = 1;
  int ans = 0;
  while (cur < b) {
    cur -= 1;
    cur += a;
    ans++;
  }
  cout << ans << endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;
typedef long long ll;
const int MAX_N=110000;
int dp[MAX_N];
int main(){
    int N;
    cin>>N;
    for(int i=0;i<MAX_N;i++){
        dp[i]=N;
    }
    dp[0]=0;
    for(int n=0;n<N;n++){
        for(int pow6=1;n+pow6<=N;pow6*=6){
            dp[n+pow6]=min(dp[n+pow6],dp[n]+1);
        }
        for(int pow9=1;n+pow9<=N;pow9*=9){
            dp[n+pow9]=min(dp[n+pow9],dp[n]+1);
        }
    }
    cout<<dp[N]<<endl;
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define show1d(v) rep(i,v.size())cout<<" "<<v[i];cout<<endl<<endl;
#define show2d(v) rep(i,v.size()){rep(j,v[i].size())cout<<" "<<v[i][j];cout<<endl;}cout<<endl;
using namespace std;
typedef long long ll;
typedef int Def;
typedef pair<Def,Def>pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<string> vs;
Def inf=1000000019;
int main(){
	int n,m;
	cin>>n>>m;
	int co=0;
	rep(i,m){
		int a;cin>>a;
		if(a>m)co++;
	}
	cout<<co<<endl;
}







Measured memory_bytes: 3100
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<iostream>
#include<map>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
vector <tuple<int,int,int>>relation;
int n;
long long ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            ans+=j;
    printf("%lld",ans);
    
}

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

int main(){
      int A,B;cin >> A >> B;

      if(A % 3 == 0 || B % 3 == 0 || (A+B) % 3 == 0){
            cout << "Possible" << endl;
      }else{
            cout << "Impossible" << endl;
      }
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>
#include<list>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n,ll mod = MOD){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%mod;
        }
        x = (x*x)%mod;
        n >>= 1;
    }
    return ret;
}

ll mygcd(ll a,ll b){
    if(b == 0)return a;
    return mygcd(b,a%b);
}

ll twoPow(ll shiftNum){
    return (1LL << (shiftNum - 1));
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    ll t1,t2;
    cin >> t1 >> t2;

    ll a1,a2;
    cin >> a1 >> a2;

    ll b1,b2;
    cin >> b1 >> b2;

    if(t1*a1 + t2*a2 == t1*b1 + t2*b2){
        cout << "infinity" << endl;
        return 0;
    }

    if(a1 < b1){
        swap(a1,b1);
        swap(a2,b2);
    }

    if(t1*a1 + t2*a2 > t1*b1 + t2*b2){
        cout << 0 << endl;
        return 0;
    }

    ll y = t1*a1 - t1*b1;
    ll x = t1*b1 + t2*b2 - t1*a1 - t2*a2;

    if(y%x == 0){
        cout << 2*(y/x) << endl;
    }else{
        cout << 2*(y/x) + 1 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
n, total = map(int, input().split())
x, y, z = -1, -1, -1

for i in range(n+1):
    if i*10000 + (n-i)*1000 > total:
        break
    if i*10000 + (n-i)*5000 < total:
        continue
    for j in range(n+1-i):
        if i*10000 + j*5000 + (n-i-j)*1000 == total:
            x, y, z = i, j, (n-i-j)
            break
    else:
        continue
    break

print("{} {} {}".format(x, y, z))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using st = string;
using P = pair<int, int>;
#define mrep(i, m, n) for(int i = m; i < n; i++)
#define rep(i, n) mrep(i, 0, n)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define INF 1e4
#define sz(x) x.size()

int main() {
    st s, t;
    cin >> s >> t;
    int sz_s = sz(s);
    int sz_t = sz(t);
    int ans = sz_t;
    rep(i, sz_s - sz_t + 1){
        int cnt = 0;
        rep(j, sz_t){
            if(t.at(j) != s.at(i + j)) cnt++;
        }
        chmin(ans, cnt);
    }
    /*rep(i, sz_t){
        rep(j, sz_s){
            if(s.at(j) == t.at(i)){
                int cnt = 0;
                rep(k, sz_t){
                    if(j - i + k < 0 || j - i + k >= sz_s) break;
                    if(t.at(k) != s.at(j - i + k)){
                        cnt++;
                    }      
                }
                chmin(ans, cnt);
            }
        }     
    }*/
    cout << ans << endl;
    return 0;
}

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

typedef long long  LL;
const int N=300010,mo=998244353;
int n,a,b,fac[N],ifac[N],ans;
LL k;

int qpow(int a,int b)
{
	int x=a;  a=1;
	while (b)
		{
			if (b&1)  a=1LL*a*x%mo;
			x=1LL*x*x%mo,b>>=1;
		}
	return a;
}

int C(int n,int m){return 1LL*fac[n]*ifac[m]%mo*ifac[n-m]%mo;}

void work()
{
	scanf("%d %d %d %lld",&n,&a,&b,&k),fac[0]=1;
	for (int i=1; i<=n; i++)  fac[i]=1LL*fac[i-1]*i%mo;
	ifac[n]=qpow(fac[n],mo-2);
	for (int i=n; i; i--)  ifac[i-1]=1LL*ifac[i]*i%mo;
	for (int i=0,j; i<=n; i++)
		if ((k-1LL*a*i)%b==0)
			{
				j=(k-1LL*a*i)/b;
				if ((0<=j)&&(j<=n))
					ans=(ans+1LL*C(n,i)*C(n,j))%mo;
			}
	printf("%d",ans);
}

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


Measured memory_bytes: 2560
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

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

    void run() {

        int n = sc.nextInt();
        int d = sc.nextInt();
        int x = sc.nextInt();

        int cnt = (n % d == 0) ? n / d : n / d + 1;

        System.out.println(cnt * x);

    }


}



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

using namespace std;

typedef long long ll;

ll a,b,c;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>a>>b>>c;
	if(a+b+1>=c) cout<<b+c;
	else cout<<a+2*b+1;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
xyh = [list(map(int, input().split())) for _ in range(n)]
xyh.sort(key=lambda x: x[2], reverse=True)
#print(xyh)
for cx in range(101):
    for cy in range(101):
        c = (cx, cy)
        count = 0
        H = 0
        for x, y, h in xyh:
            if count == 0:
                H = h+abs(x-cx)+abs(y-cy)
                count = 1
            else:
                if h != max(H-abs(x-cx)-abs(y-cy), 0):
                    break
        else:
            ans = [cx, cy, H]
            print(*ans)


Measured memory_bytes: 42096
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
N = int(input())
a = list(map(int,input().split()))
b = [0]*N
b0 = a[0]
b1 = a[0]
for i in range(1,N):
    c = a[i]
    if i % 2 == 0:
        b0 += c
        b1 -= c
    else:
        b0 -= c
        b1 += c
b[0] = b0
b[1] = b1
for i in range(2,N):
    b[i] = b[i-2] - 2*a[i-2]+2*a[i-1]
print(*b)

Measured memory_bytes: 24080
def answer_143b_2(): 
    n = int(input())
    dl = list(map(int,input().split()))

    ans = 0

    #[1,2,3,4,5]としたとき、iは一番左からチェックするとして、
    # iに対するjの組み合わせはi+1からリストの最後までの組み合わせが存在する。
    for i in range(n):
        for j in range(i + 1, n):
            ans += dl[i] * dl[j]

    print(ans)
    
if __name__ == '__main__':
    answer_143b_2()

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

int N;
int di[100];

void adddiv(int x){
  if(x==1) return;
  int t=2;
  while(x>1){
    if(x%t==0){
      di[t]++;
      x/=t;
    }else{
      t++;
    }
  }
  return;
}

int main(){
  cin >> N;
  for(int i=0; i<100; i++) di[i]=0;
  for(int i=1; i<=N; i++) adddiv(i);
  
  //約数75=3*5*5
  //2+4+4 or 4+14 or 2+24 or 74
  
  int result=0;
  
  int d2=0,d4=0,d14=0,d24=0,d74=0;
  for(int i=0; i<100; i++){
    if(di[i]>=74) d74++;
    if(di[i]>=24) d24++;
    if(di[i]>=14) d14++;
    if(di[i]>=4) d4++;
    if(di[i]>=2) d2++;
  }
  
  if(d74>=1){
    result+=d74;
  }
  if(d24>=1){
    result+=(d24*(d2-1));
  }
  if(d14>=1){
    result+=(d14*(d4-1));
  }
  if(d4>=2){
    result+=(d4*(d4-1)/2*(d2-2));
  }
  
  cout << result << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int i,j,k,n,buc[15],cake[15];
double box,list[11][11],goal,leng[2];
char sp;

int main(){
	for(i=3;i<=10;i++){
		for(j=3;j<=10;j++){
			list[i][j]=i+j-sqrt((double)((i+j)*(i+j)-(i-j)*(i-j)));
		}
	}

	while(scanf("%lf",&box)!=EOF){
		n=0;goal=0;
		for(i=0;i<11;i++)buc[i]=0;
		while(1){
			scanf("%c",&sp);
			if(sp=='\n')break;
			
			scanf("%d",&k);
			buc[k]++;
			goal+=k*2;
			n++;
		}
		goal-=box;
		
		if(goal<=0){printf("OK\n");continue;}
		for(i=3,j=0;i<11 && j<n;i++){for(;buc[i]>0;j++,buc[i]--)cake[j]=i;}

		leng[0]=0;leng[1]=0;
		for(k=1,i=0,j=0;k<n;k++){
			leng[0]+=list[cake[i]][cake[n-j-1]];
			leng[1]+=list[cake[j]][cake[n-i-1]];
			if(i<=j)i=j+1;else{j++;i--;}
		}

		if(leng[0]>=goal || leng[1]>=goal)printf("OK\n"); else printf("NA\n");

	}
	return 0;
}

Measured memory_bytes: 612
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {


	public static void main(String[] args) throws IOException {
		BufferedReader bf = null;
		bf = new BufferedReader(new InputStreamReader(System.in));
		long ans = 0,sum = 0,temp;
		int n;
		long[] a;
		String str;
		String[] s;
		str = bf.readLine();
		n = Integer.parseInt(str);
		str = bf.readLine();
		s = str.split(" ");
		a = new long[n];
		for(int i = 0;i < n;++i) {
			a[i] = Long.parseLong(s[i]);
			sum += a[i];
		}
		for(int i = 0;i < n-1;++i) {
			sum -= a[i];
			temp = sum%1000000007;
			ans = (ans + a[i]*temp)%1000000007;
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 61776
#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <math.h>
#include <stdio.h>
#include <functional>
#include <string>
#include <cstdlib>
#include <numeric>
#include <cstdbool>
#include <map> 
#include<set>
#include<queue>

typedef long long ll;


#define rep(i,n) for(ll i=0;i<n;i++)
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; }

const long long INF = 1000000000000000;
const ll inf = -1e18;
typedef pair<ll, ll> P;
ll ma = 1000000000 + 7;
ll mx = 1000003;
ll h, w, n,m,k; string s,t;
char maze[60][60];
int dis[101][101]; int graph[52][52]; bool vis[52];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
ll gcd(ll x, ll y) {
	if (x % y == 0) return y;
	return gcd(y, x % y);

}
ll lcm(ll a,ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
void comb(vector<vector <ll> >& v) {
	for (ll i = 0; i < v.size(); i++) {
		v[i][0] = 1;
		v[i][i] = 1;
	}
	for (ll k = 1; k < v.size(); k++) {
		for (int j = 1; j < k; j++) {
			v[k][j] = (v[k - 1][j - 1] + v[k - 1][j]);
		}
	}
}

int main() {
	cin >> n;
	vector<ll> a(n);
	rep(i, n) {
		cin >> a[i];
	}
	ll res = 0;
	for (ll i = 1; i <= n - 2; i++) {
		if (max(a[i], a[i - 1]) == min(a[i], a[i + 1]) || max(a[i], a[i + 1]) == min(a[i], a[i - 1])) {
			res++;
		}
	}
	cout << res << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define exrep(i, a, b) for(long long i = a; i <= b; i++)
#define rep(i,n)for(long long i=0;i<(long long)(n);i++)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vector<ll> > vvl;
typedef vector<vector<P> > vvp;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
const ll MOD=1e9+7;
const ll INF=1e18;
const int MAX=510000;
const double pi=acos(-1);
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false); 
  
  string s;
  cin >> s;
  int n=s.size();
  vector<int>vec(3);
  rep(i,n){
    vec[s[i]-'a']++;
  }
  sort(all(vec));
  if(vec[0]+1<vec[2])cout << "NO" << endl;
  else cout << "YES" << endl;
  return 0;     
}


Measured memory_bytes: 512
#include "bits/stdc++.h"
using namespace std;

int main(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  int l=0;
  int r=1;
  long long int ans=0;
  int np=0;
  int j=0;

  for(int i=0;i<n;i++){
    while(j<n&&(np&a[j])==0){
      np^=a[j];
      j++;
    }
    ans+=j-i;
    np^=a[i];
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define pr pair<int, int>
#define x first
#define y second
using namespace std;

template<typename T>
void read(T& n){
	char ch; int sign = 1;
	while (!isdigit(ch = getchar())) if (ch == '-') sign = -1;
	n = ch - '0';
	while (isdigit(ch = getchar())) n = n * 10 + ch - '0';
	n *= sign;
}
typedef long long ll;
const int INF = 1e9 + 7;
const int N = 222222;
int n;
int nxt[N][26], f[N];
char s[N];

int main(){
	scanf("%s", s + 1); n = strlen(s + 1);
	rep(i, 0, 25) nxt[n+1][i] = n + 1;
	per(i, n, 1) rep(c, 0, 25)
		nxt[i][c] = s[i] - 'a' == c ? i : nxt[i+1][c];
	rep(i, 1, n + 1) f[i] = INF;
	per(i, n, 1) rep(c, 0, 25)
		f[i] = min(f[i], f[nxt[i][c]+1] + 1);
	int pos = 1;
	while(pos <= n){
		rep(c, 0, 25) if (f[pos] == f[nxt[pos][c]+1] + 1){
			putchar(c + 'a'); pos = nxt[pos][c] + 1; break;
		}
	}
	puts("");
	return 0;
}

Measured memory_bytes: 22656
N=int(input())
import math
a=0
for i in range(1,int(math.sqrt(N-1))+1):
  if (N-1)%i==0:
    a+=2
    i+=1
  else:
    i+=1
a-=1

if int(math.sqrt(N-1))==math.sqrt(N-1):
  a-=1
for i in range(2,int(math.sqrt(N))+1):
  if N%i==0:
    t=N
    while t%i==0:
      t=t/i
    if t%i==1:
      a+=1
      i+=1
    else:
      i+=1
a+=1
print(a)
               


Measured memory_bytes: 9168
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static String Y = "Yes";
	public static String N = "No";
	public static long MOD = (long) (Math.pow(10, 9) + 7);
	public static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = ni();

		long kosuu[] = new long[100001];

		long sum = 0;

		for (int i = 0; i < n; i++) {
			int num = ni();
			kosuu[num]++;

			sum += num;
		}

		int q = ni(); // 操作回数

		for (int i = 0; i < q; i++) {
			int b = ni();
			int c = ni();

			long b_bef = kosuu[b];
			kosuu[b] = 0;
			sum -= (long) b * b_bef;

			long c_bef = kosuu[c];
			kosuu[c] += b_bef;
			sum += (long) c * b_bef;

			out(sum);

		}

	}

	/*
	 * 以下メソッド集
	 */
	static int[] sort(int[] n) {
		Arrays.sort(n);
		return n;
	}

	static long[] sort(long[] n) {
		Arrays.sort(n);
		return n;
	}

	static int ketasuu(int n) {
		String str = "" + n;
		return str.length();
	}

	static int account(String str) {
		String target = "AC";
		int count = 0;
		int len = str.length();
		for (int i = 0; i < len - 1; i++) {
			if (target.equals(str.substring(i, i + target.length()))) {
				count++;
			}
		}
		return count;
	}

	static int ni() {
		return sc.nextInt();
	}

	static long nl() {
		return sc.nextLong();
	}

	static double nd() {
		return sc.nextDouble();
	}

	static String n() {
		return sc.next();
	}

	static char[] nc() {
		return sc.next().toCharArray();
	}

	static int kaijo(int n) {
		if (n == 0 || n == 1) {
			return 1;
		} else {
			return n * kaijo(n - 1);
		}
	}

	static int fib(int n) {
		return (n == 1 || n == 0) ? n : fib(n - 2) + fib(n - 1);
	}

	static long lcm(long m, long n) {

		return m * n / gcd(m, n);
	}

	static int lcm(int m, int n) {

		return m * n / gcd(m, n);
	}

	static long gcd(long a, long b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	static void out(String info) {
		System.out.println(info);
	}

	static void out(int info) {
		System.out.println(info);
	}

	static void out(double info) {
		System.out.println(info);
	}

	static void out(long info) {
		System.out.println(info);
	}

	static void out(char info) {
		System.out.println(info);
	}

	static void out(Object obj) {
		System.out.println(obj.toString());
	}

	static void outn(String info) {
		System.out.print(info);
	}

	static void outn(int info) {
		System.out.print(info);
	}

	static void outn(double info) {
		System.out.print(info);
	}

	static void outn(long info) {
		System.out.print(info);
	}

	static void outn(char info) {
		System.out.print(info);
	}

	static double max(double d, double e) {
		return Math.max(d, e);
	}

	static long max(long a, long b) {
		return Math.max(a, b);
	}

	static double min(double d, double e) {
		return Math.min(d, e);
	}

	static int min(int a, int b) {
		return (int) Math.min(a, b);
	}
}

class XY {
	int h;
	int c;

	XY(int h, int c) {
		this.h = h;
		this.c = c;
	}
}


Measured memory_bytes: 64808
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); ++i)
#define fi first
#define se second
#define INF 1000000009
#define lINF 1000000000000000009
typedef long long ll;

int main(){
  string s;
  cin>>s;
  int n=s.size();
  if(n%2==1){
    cout<<"No"<<endl;
    return(0);
  }
  for(int i=0;i<n;i++){
    if(i%2==0){
      if(s[i]!='h'){
        cout<<"No"<<endl;
        return(0);
      }
    }
    else{
      if(s[i]!='i'){
        cout<<"No"<<endl;
        return(0);
      }
    }
  }
  cout<<"Yes"<<endl;
  return(0);
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#define rep(i, n) for (int i = 1; i <= (n); i++)
#define int long long
#define INF 1e9 + 7
#define cae cout << ans << endl;
#define cye cout << "Yes" << endl;
#define cne cout << "No" << endl;
#define r0 return 0;
using namespace std;
typedef pair<int,int>P;
typedef long long ll;
signed main() {
    int n;
    int ans = 0;
    cin >> n;
    rep(i, n) {
        if (i % 3 != 0 && i % 5 != 0) {
            ans += i;
        }
    }
    cae
    r0
}

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

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

    int amari = a % b;

    while(1){
        a = a % b;
        //printf("a %d\n", a);
        if(a == c){
            break;
        }
        a = (a + amari) % b;
        if(a == amari ){
            break;
        }
    }

    if(a == c){
        printf("YES\n");
    }
    else{
        printf("NO\n");
    }

    return 0;
}

Measured memory_bytes: 256
A = int(input())
flag = False
for i in range(1,10):
  if flag:
    break;
  for j in range(1,10):
    if i*j == A:
      flag = True
    else:
      flag = False
    if flag:
      break;
if flag:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 2940
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef node* Node;
#define NIL NULL

node array[500000];
int size=0;

Node root = NIL;
 
Node treeMinimum(Node x){
  while(x->left!=NIL)x=x->left;
  return x;
}
 
Node treeSearch(Node u, int k){
  Node i=u;
  while(i!=NIL){
    if(i->key==k)return i;
    else if(i->key<k)i=i->right;
    else i=i->left;     
  }
  return NIL;
}
 
Node treeSuccessor(Node x){
  if(x->right!=NIL)return treeMinimum(x->right);
  Node y=x->parent;
  while(y!=NIL&&x==y->right){
    x=y;
    y=y->parent;
  }
  return y;
}
 
void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  if(z->left==NIL||z->right==NIL)y=z;
  else y=treeSuccessor(z);
   
  if(y->left!=NIL)x=y->left;
  else x=y->right;
 
  if(x!=NIL)x->parent=y->parent;
   
  if(y->parent==NIL)root=x;
  else if(y==y->parent->left)y->parent->left=x;
  else y->parent->right=x;
 
  if(y!=z)z->key=y->key;
   
  //free(y);
}
 
void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = &array[size++];
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x!=NIL){
    y=x;
    if(z->key<x->key)x=x->left;
    else x=x->right;
  }
  z->parent=y;
  if(y==NIL)root=z;
  else if(z->key<y->key)y->left=z;
  else y->right=z;   
}


void inorder(Node u){
  if(u==NIL)return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

void preorder(Node u){
  if(u==NIL)return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n,x;
  char str[20];
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%s", str);
    if(str[0]=='f'){
      scanf("%d",&x);
      Node t=treeSearch(root,x);
      if (t!=NIL) printf("yes\n");
      else printf("no\n");
    }else if(str[0]=='i'){
      scanf("%d",&x);
      insert(x);
    }else if(str[0]=='p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }else if(str[0]=='d'){
      scanf("%d",&x);
      treeDelete(treeSearch(root,x));
    }
  }

  return 0;
}



Measured memory_bytes: 15072
import sys
from collections import deque
n = int(input())
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
c_ls = [int(i) for i in sys.stdin.readline().split()]
c_ls.sort(reverse=True)
costs = [0 for i in range(n)]
que = deque([0])
already = {0}
i = 0
while len(que) > 0:
    cur = que.popleft()
    costs[cur] = c_ls[i]
    i += 1
    for _next in graph[cur]:
        if _next not in already:
            que.append(_next)
            already.add(_next)
print(sum(c_ls[1:]))
print(" ".join([str(i) for i in costs]))

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

int main(void){
    ll n, a, b;
    cin>>n>>a>>b;
    ll idx=n%(a+b);
    if(idx<=a) cout<<n/(a+b)*a+idx<<endl;
    else cout<<n/(a+b)*a+a<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <bitset>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <regex>
#include <iomanip>
#include <climits>
#include <utility>
#include <queue>
using namespace std;
using ll = long long int;
using dd = long double;
const ll MOD = 1e9 + 7;
const dd PI = 3.1415926435;

ll gcd(ll a, ll b)
{
    if (a % b == 0)
    {
        return b;
    }
    return gcd(b, a % b);
}

ll fact(ll n)
{
    if (n == 0)
    {
        return 1;
    }
    if (n == 1)
    {
        return 1;
    }
    return n * fact(n - 1) % MOD;
}

ll pow_fast(ll n, ll k)
{
    if (k == 0)
    {
        return 1;
    }
    if (k == 1)
    {
        return n;
    }

    if (k % 2 == 0)
    {
        ll tmp = pow_fast(n, k / 2LL);
        return tmp * tmp % MOD;
    }
    else
    {
        ll tmp = pow_fast(n, k / 2LL);
        tmp *= tmp;
        tmp %= MOD;
        return tmp * n % MOD;
    }
}

map<ll, ll> sosuu(ll n)
{
    map<ll, ll> res;
    for (ll i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            res[i] += 1;
            n /= i;
        }
    }
    if (n != 1)
    {
        res[n] += 1;
    }
    return res;
}

int main()
{
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N + 1);
    for (ll i = 0; i < N; i++)
    {
        cin >> A[i];
    }

    vector<ll> imos(N + 1);
    for (ll _ = 0; _ < min(1000LL, K); _++)
    {
        for (ll i = 0; i < N; i++)
        {
            imos[i] = 0;
        }

        for (ll i = 0; i < N; i++)
        {
            imos[max(0LL, i - (A[i]))] += 1;
            imos[min(N, i + (A[i]) + 1)] -= 1;
        }
        for (ll i = 0; i <= N; i++)
        {
            if (0 < i)
            {
                imos[i] += imos[i - 1];
            }
            A[i] = imos[i];
        }
    }

    for (ll i = 0; i < N; i++)
    {
        cout << imos[i] << " ";
    }
    cout << endl;
}


Measured memory_bytes: 6428
a,b = map(int, input().split(' '))


def gcd(a, b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a


def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)

print(int(lcm(a,b)))

Measured memory_bytes: 3068
c = list(list(map(int, input().split())) for i in range(3))

d = [0, 1, 2, 0, 1]
x = c[0][0] + c[1][1] + c[2][2]
ok = True
for i in range(3):
    a = c[d[i]][0] + c[d[i+1]][1] + c[d[i+2]][2]
    b = c[d[i]][2] + c[d[i+1]][1] + c[d[i+2]][0]

    if x != a or x != b:
        ok = False

print('Yes' if ok else 'No')


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

using namespace std;

const int N = 8e5 + 5;
const int P = 200003;
const double PI = acos( -1.0 );
int _w;

struct Complex {
  double x , y;
  Complex( double x = 0 , double y = 0 ):
    x( x ) , y( y ) {}
  Complex operator + ( const Complex & rhs ) const {
    return Complex( x + rhs.x , y + rhs.y );
  }
  Complex operator - ( const Complex & rhs ) const {
    return Complex( x - rhs.x , y - rhs.y );
  }
  Complex operator * ( const Complex & rhs ) const {
    return Complex( x * rhs.x - y * rhs.y , x * rhs.y + y * rhs.x );
  }
} _wn[N] , f[N] , g[N];

int _r[N] , _now;
inline void _init( int n ) {
  if( _now == n ) return;
  _now = n; int l = 0; while( ( 1 << l ) < n ) ++l;
  --l; for( int i = 0 ; i < n ; ++i ) {
    _r[i] = ( _r[i >> 1] >> 1 ) | ( (i&1) << l );
    _wn[i] = Complex( cos( (2 * PI / n) * i ) , sin( (2 * PI / n) * i ) ); 
  }
}

void DFT( Complex * f , int n ) {
  static Complex x; _init( n );
  for( int i = 1 ; i < n ; ++i ) if( i < _r[i] ) swap( f[i] , f[_r[i]] );
  for( int mid = 1 , tk = n / 2 ; mid < n ; mid <<= 1 , tk >>= 1 ) 
    for( int i = 0 ; i < n ; i += ( mid << 1 ) ) 
      for( int j = 0 ; j < mid ; ++j ) {
        x = f[i + j + mid] * _wn[tk * j];
        f[i + j + mid] = f[i + j] - x;
        f[i + j] = f[i + j] + x;
      }
}

void IDFT( Complex * f , int n ) {
  reverse( f + 1 , f + n ); DFT( f , n );
  for( int i = 0 ; i < n ; ++i ) 
    f[i].x /= n , f[i].y /= n;
}

int n , dat[N] , LOG[N];
long long ans[N] , res;

int main( void ) {
  for( int i = 0 , now = 1 ; i < P - 1 ; ++i ) {
    LOG[now] = i;
    now = ( now + now ) % P;
  }
  _w = scanf("%d",&n);
  for( int i = 1 ; i <= n ; ++i ) {
    _w = scanf("%d",dat+i);
    if( dat[i] == 0 ) continue;
    dat[i] = LOG[dat[i]];
    --ans[dat[i] * 2];
    f[dat[i]].x += 1;
  }
  int lim = 1;
  while( lim < P + P ) lim <<= 1;
  DFT( f , lim ); 
  for( int i = 0 ; i < lim ; ++i ) g[i] = f[i] * f[i];
  IDFT( g , lim );
  for( int i = 0 , now = 1 ; i < P + P ; ++i ) {
    ans[i] += (long long)( g[i].x + 0.5 );
    res += ( ans[i] / 2 ) * now;
    now = ( now + now ) % P;
  }
  cout << res;
  return 0;
}


Measured memory_bytes: 48352
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
const ld pi = 3.14159265358;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b; return true;}return false;}
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b; return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

ll fac[510000], finv[510000], inv[510000];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; 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;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/

//    cout << fixed << setprecision(15);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N,M;
    cin >> N;
    vector<ll> n(N);
    rep(i,N)cin >> n[i];
    cin >> M;
    vector<ll> m(M);
    rep(i,M)cin >> m[i];
    sort(all(m));
    sort(all(n));
    ll ans = 0;
    rep(i,N - 1){
        if(n[i] != n[i + 1]){
        ll left = -1,right = M;
        while(right - left != 1){
            ll mid = (right + left) / 2;
            if(m[mid] < n[i])left = mid;
            else if(m[mid] > n[i])right = mid;
            else{
                //cout << n[i] << ":" << "atta!" << "\n";
                ans++;
                break;
            }
        }
    }
}
    ll left = -1,right = M;
    while(right - left != 1){
        ll mid = (right + left) / 2;
        if(m[mid] < n[N - 1])left = mid;
        else if(m[mid] > n[N - 1])right = mid;
        else{
            ans++;
            break;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 4044
#include<bits/stdc++.h>
using ll  = long long;
#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define erep(e,v) for(auto && e :v)
#define all(in) in.begin(), in.end()
#define MP make_pair
#define INF (sizeof(int) == 4 ? (int)1e9:(int)1e18)
#define EPS 0.0000000001
using namespace std;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return vector<decltype(inner)>(x, inner); }
template<class T> void join(T a){for(auto itr :a){if(itr != *a.begin())cout << " "; cout << itr;} }
using ld  = long double;
using pii = pair<int,int>;
using piii = pair<int,pii>;
int W,H;
int dx[]={0,0,1,-1}, dy[]={1,-1,0,0};
bool valid(int x,int y){return (0<=x&&x<W)&&(0<=y&&y<H);}
signed main(){
    int n,h,w; cin >>n >> h >> w;
    int ans = 0;
    rep(_,n){
        int a,b; cin >>a >> b;
        if(a>=h  and b >= w )ans++;
    }
    cout << ans << endl;
}




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

using namespace std;
set<int> x[26];

int main(){
    cin.exceptions(cin.failbit);
    cin.tie(0);
    cout.tie(0);
    cin.sync_with_stdio(0);
    int n, q;
    string s;
    cin >> n >> s >> q;
    for (int i = 0; i < n; ++i){
        x[s[i]-'a'].insert(i);
    }
    while (q--){
        int op;
        cin >> op;
        if (op == 1){
            int p;
            char c;
            cin >> p >> c;
            p--;
            
            x[s[p]-'a'].erase(p);
            x[c-'a'].insert(p);
            s[p] = c;
        }
        else {
            int l, r;
            int ans = 0;
            cin >> l >> r;
            l--, r--;
            for (int i = 0; i < 26; ++i){
                if (x[i].lower_bound(l) == x[i].end()) continue;
                ans += *x[i].lower_bound(l) <= r;
            }
            cout << ans << '\n';
        }
    }
    return 0;
}

Measured memory_bytes: 24348
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define np next_permutation
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
//cout << fixed << setprecision (20);   小数点以下2０桁まで
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'0'+=16;        で大文字に
//'大文字'+=32;    で小文字に
//s[i]-'0'でchar文字→int数に;
//string s = to_string(int数);
//int n = stoi(string文字列)
//実行時間制約2秒では２×10^8回くらいまで計算できる


int main() {
  int n,m;
  cin >> n>>m;
  
  vector<int> p(m);
  vector<int> q(m);  
  rep(i,m){
  cin>>p[i]>>q[i];
  }
  
  if(n==1)
  rep(i,10){
    bool ome = true;
    rep(j,m){
      if(i!=q[j]) ome = false;
    }
    if(ome) {
    cout << i << endl;
    return 0;
    }
    if(i==9) cout << -1 << endl;
  }
  
  
  if(n==2)
  for(int i=10;i<100;i++){
    bool ome = true;
    rep(j,m){
      if((p[j]==1 && i/10!=q[j])||(p[j]==2 && i%10!=q[j])) ome = false;
    }
    if(ome) {
    cout << i << endl;
    return 0;
    }
    if(i==99) cout << -1 << endl;
  }
  
  if(n==3)
  for(int i=100;i<1000;i++){
    bool ome = true;
    rep(j,m){
      if((p[j]==1 && i/100!=q[j])||(p[j]==2 && (i/10)%10!=q[j])
        ||(p[j]==3 && i%10!=q[j])) ome = false;
    }
    if(ome) {
    cout << i << endl;
    return 0;
    }
    if(i==999) cout << -1 << endl;
  } 
  
  
    
}


Measured memory_bytes: 256
#include <cstdlib>
#include <iostream>


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

  int a, b, c;
  std::cin >> a >> b >> c;

  if(c-b==b-a)
    std::cout << "YES" << std::endl;
  else
    std::cout << "NO" << std::endl;
  return EXIT_SUCCESS;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {

    public static void main(String args[]) {

        // 入力
        Scanner sc = new Scanner(System.in);
        long a = Long.parseLong(sc.next());
        long v = Long.parseLong(sc.next());
        long b = Long.parseLong(sc.next());
        long w = Long.parseLong(sc.next());
        long t = Long.parseLong(sc.next());
        sc.close();

        // 主処理
        long dist = Math.abs(a - b);
        boolean judge = false;
        if (w < v) {
            long diff = v - w;
            judge = dist - diff * t <= 0;
        }
        String result = judge ? "YES" : "NO";

        // 出力
        System.out.println(result);
    }
}


Measured memory_bytes: 35832
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

//vector string deque break continue
#define forn(i, s, f) for (int i = (int)s; i < (int)f; i++)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define fs first
#define sc second
#define pf push_front
#define pb push_back
#define pop_f pop_front
#define pop_b pop_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()

template <typename T> istream& operator>>(istream& in, vector <T>& a) {for (auto& i : a) in >> i; return in;}
template <typename T> ostream& operator<<(ostream& out, vector <T>& a)  {for (auto& i : a) out << i << " "; return out;}
template <typename T, typename U> void chkmin(T& a, U b) {if (a > b) a = b;}
template <typename T, typename U> void chkmax(T& a, U b) {if (a < b) a = b;}


int n, m, q;
vector <vector <int>> b;
vector <int> a;

long long ans = 0;

void check() {
    long long cur = 0;
    forn (i, 0, q) {
        int l = b[i][0], r = b[i][1], c = b[i][2], d = b[i][3];
        if (a[r] - a[l] == c)
            cur += d;
    }
    chkmax(ans, cur);
}

void go() {
    if (sz(a) == n) {
        check();
        return;
    }
    int lst = a.empty() ? 1 : a.back();
    forn (i, lst, m + 1) {
        a.pb(i);
        go();
        a.pop_back();
    }
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m >> q;
    b.resize(q);
    forn (i, 0, q) {
        b[i].resize(4);
        cin >> b[i];
        forn (j, 0, 2)
            b[i][j]--;
    }
    go();
    cout << ans;
    return 0;
}

Measured memory_bytes: 3648
// Sakhiya07 - Yagnik Sakhiya
 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define pb push_back
 
#define mp make_pair
#define bp __builtin_popcountll
#define MOD  1000000007
const int N = 100005;
#define FAST ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);srand(time(NULL));

void solve()
{
    ll n,d,a;
    cin >> n >> d >> a;
    pair<ll,ll> p[n];
    for(ll i=0;i<n;i++)
    {
    	cin >> p[i].ff >> p[i].ss;
    }
    sort(p,p+n);
    ll ans = 0;
    set<pair<ll,ll>> extra;
    ll have = 0;
    for(ll i=0;i<n;i++)
    {
    	ll need = ceil(p[i].ss/(ld)a);
    	while(extra.size()>0)
    	{
    		pair<ll,ll> p1 = *extra.begin();
    		if(p1.ff<p[i].ff)
    		{
    			have -= p1.ss;
    			extra.erase(extra.begin());
    		}
    		else
    		{
    			break;
    		}
    	}
    	if(have>=need)   continue;
    	else
    	{
    		ans += need - have;
    		extra.insert({p[i].ff+2*d,need - have});
    		have += (need - have);
    	}
    }
    cout<<ans;
} 

int32_t  main()
{
    FAST;
    ll t = 1;
    //  cin >> t;
    while(t--)
    {
    	solve();
    }
}


Measured memory_bytes: 9600