akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1000000007;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX*/                      int gcd(ll a,ll b){return b?gcd(b,a%b):a;}
/*"lcm"   MIN*/                      int lcm(ll a,ll b){return a*b/gcd(a,b);}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int main(){
    int n;
    cin >> n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        cin >> a.at(i);
    }
    sort(a.begin(),a.end());
    ll ans = 0;
    for(int i=0;i<n;i++){
        int d=a.at(i);
        for(int j=i+1;j<n;j++){
            int dd = a.at(j);
            int now = d+dd;
             int ok = -1,ng=n;
             while(ng-ok>1){
                 int mid = (ok+ng)/2;
                 if(a.at(mid)<now)ok=mid;
                 else ng = mid;
             }
            if(j+1>ok)continue;
           // cout << ok<<endl;;//ikade,
            //cout << j+1<<endl;//izyou.
            int che = ok-j;
            ans+=che;
    }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < (n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < (n); ++(i))
using namespace std;
template <class T>
void setmax(T &a, T const &b) {
    if (a < b) a = b;
}

template <class T>
void setmin(T &a, T const &b) {
    if (a > b) a = b;
}

template <typename T, typename X>
auto vectors(T a, X x) { return vector<T>(x, a); }

template <typename T, typename X, typename Y, typename... Zs>
auto vectors(T a, X x, Y y, Zs... zs) {
    auto cont = vectors(a, y, zs...);
    return vector<decltype(cont)>(x, cont);
}

int main() {
    int N;
    cin >> N;
    long long T, A;
    cin >> T >> A;
    --N;
    while (N--) {
        long long t, a;
        cin >> t >> a;

        long long n = max((T + t - 1) / t, (A + a - 1) / a);
        T = n * t, A = n * a;
    }
    cout << T + A << endl;
    return 0;
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair < int, int >
#define pll pair < ll, ll >
#define pb push_back
#define maxn 100005
using namespace std;

int main()
{
    int k;

    cin >> k;

    int gcd = 0;

    for(int i = 1; i <= k; i++){
        for(int j = 1; j <= k; j++){
            for(int l = 1; l <= k; l++) gcd += __gcd(i, __gcd(j, l));
        }
    }

    cout << gcd << endl;

    return 0;
}


Measured memory_bytes: 3644
h, w, a, b = map(int, input().split())
l = [[0 for j in range(w)] for i in range(h)]
for i in range(b):
    for j in range(a):
        l[i][j] = 1
for i in range(b, h):
    for j in range(a, w):
        l[i][j] = 1
for i in l:
    print(*i, sep="")

Measured memory_bytes: 14196
//include
//--------------------------------------------------
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<string>
#include<cstring>
#include<ctime>
#include<cassert>

using namespace std;

//conversion
//--------------------------------------------------
inline int toInt(const string &s){
    int v;istringstream sin(s);sin>>v;
    return v;
}
template<class T> inline string toString(T x){
    ostringstream sout;sout<<x;
    return sout.str();
}

//math
//--------------------------------------------------
template<class T> inline T sqr(T x){return x*x;}

//typedef
//--------------------------------------------------
typedef vector<int>VI;
typedef vector<VI>VVI;
typedef vector<string>VS;
typedef pair<int,int>PII;
typedef long long LL;

//container util
//--------------------------------------------------
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin())i=(c).begin();i!=(c).end();i++)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

//constant
//--------------------------------------------------
const int INF=1e9+7;
const int dx[]={0,-1,0,1};
const int dy[]={-1,0,1,0};

//clear memory
//--------------------------------------------------
#define CLR(a) memset((a),0,sizeof(a))

//end-----------------------------------------------

struct UF{
    int N;
    VI par,sz,cost;
    void init(int n,int *c){
        N=n;
        par.resize(N);
        sz.resize(N,1);
        cost.resize(N);
        for(int i=0;i<N;i++){
            par[i]=i;
            cost[i]=c[i];
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[y]>sz[x])swap(x,y);
        par[y]=x;
        sz[x]+=sz[y];
        cost[x]=min(cost[x],cost[y]);
    }
};

int N;
string a[5000];int b[5000];
int main(){
    map<string,int>mp;
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>a[i]>>b[i];
        if(mp.find(a[i])==mp.end()){
            int s=mp.size();
            mp[a[i]]=s;
        }
    }


    UF uf;uf.init(N,b);

    int M;cin>>M;
    while(M--){
        string x,y;
        cin>>x>>y;
        uf.unite(mp[x],mp[y]);
    }

    int ans=0;
    for(int i=0;i<N;i++){
        if(uf.find(i)==i){
            ans+=uf.cost[i]*uf.sz[i];
        }
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 1900
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int n,x;
int main() {
	//freopen("a.inp", "r", stdin);
	// freopen("a.out", "w", stdout);
	scanf("%d", &n);
	int Min = 100000;
	int Max = 0;
	for(int i=0;i<n;i++) {
		scanf("%d", &x);
		Min = min(Min,x);
		Max = max(Max,x);
	}	
	printf("%d",Max - Min);
	return 0;
}

Measured memory_bytes: 256
def merge(s):
    correct_s = []
    s.sort(key = lambda x:(x[2],x[0]))
    min_max = [s[0][0],s[0][1]]
    for i in range(1,len(s)):
        if s[i][2] == s[i-1][2] and s[i][0] == min_max[1]:
            min_max[1] = s[i][1]   
        else:
            correct_s.append([min_max[0],min_max[1],s[i-1][2]])
            min_max[0],min_max[1] = s[i][0],s[i][1]
    else:
        correct_s.append([min_max[0],min_max[1],s[len(s)-1][2]])

    return correct_s
        
        
    
import heapq
N,C = list(map(int,input().split()))
data = []
av = []
for i in range(N):
    data.append(list(map(int,input().split())))
    


s = merge(data)
s.sort()


for i in range(len(s)):
    if i == 0:
        heapq.heappush(av,s[i][1])
    elif s[i][0] <= av[0]:
        heapq.heappush(av,s[i][1])
    else:
        heapq.heappop(av)
        heapq.heappush(av,s[i][1])

print(len(av))

Measured memory_bytes: 35608
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
 
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int A = sc.nextInt();
    int B = sc.nextInt();
    int C = sc.nextInt();
    int X = sc.nextInt();
    int Y = sc.nextInt();
    int costOp1 = A * X + B * Y;
    int Same = Math.min(X, Y);
    int costOp2 = Same * 2 * C + A * (X - Same) + B * (Y - Same);
    int Max = Math.max(X, Y);
    int costOp3 = Max * 2 * C;
    int Best = Math.min(costOp1, costOp2);
    Best = Math.min(Best, costOp3);
    System.out.println(Best);
  }
}


Measured memory_bytes: 35844
#!/usr/bin/python3
# -*- coding: utf-8 -*-

S = int(input())

# YYMM: XX01~XX12
# MMYY: 01YY~12YY
yymm = 0
mmyy = 0

if S % 100 <= 12 and S % 100 != 0:
    yymm = 1
if S // 100 <= 12 and S // 100 != 0:
    mmyy = 1

if yymm == 1 and mmyy == 1:
    print('AMBIGUOUS')
elif yymm == 1 and mmyy != 1:
    print('YYMM')
elif yymm != 1 and mmyy == 1:
    print('MMYY')
else:
    print('NA')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)

using namespace std;

const int N=1e5+100;
int n,a[N],p,d;

int main(){
	scanf("%d",&n);
	rep (i,1,n) scanf("%d",&a[i]);
	sort(a+1,a+1+n,greater<int>());
	rep (i,1,n) if (a[i]>=i) p=i; else break;
	rep (i,p+1,n) if (a[i]==p) d++; else break;
	if (((a[p]-p)&1)||(d&1)) puts("First"); else puts("Second");
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int N,M;
cin >> N >> M;
vector<pair<int,int>> vec(M);
for (int i = 0;i < M;i++) {
    cin >> vec.at(i).first >> vec.at(i).second;
}
map<int,int> mati;
for (int i = 0;i < N;i++) {
    mati[i] = 0;
    for (int j = 0;j < M;j++) {
       if (vec.at(j).first == i+1) mati[i] += 1;
        if (vec.at(j).second == i+1) mati[i] += 1;
    }
}
for (int i = 0;i < N;i++) {
    cout << mati.at(i) << endl;
}
return 0;
}


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

using namespace std;

struct P {
	int id, score;
	P(int id, int score) : id(id), score(score) { }
};

bool operator <(const P &p1, const P &p2) {
	if (p1.score == p2.score) return p1.id > p2.id;
	return p1.score < p2.score;
}
bool operator >(const P &p1, const P &p2) {
	if (p1.score == p2.score) return p1.id < p2.id;
	return p1.score > p2.score;
}

struct Data {
	int d, t, x;
	Data(int d, int t, int x) : d(d), t(t), x(x) { }
};

bool compare(const Data &d1, const Data &d2) {
	return d1.t < d2.t;
}

int main() {
	vector<Data> v;

	int N, R, L; cin >> N >> R >> L;
	for (int i = 0; i < R; ++i) {
		int d, t, x; cin >> d >> t >> x;
		v.push_back( Data(d-1, t, x) );
	}
	sort( v.begin(), v.end(), compare );

	priority_queue<P> Q;
	for (int i = 0; i < N; ++i) {
		Q.push( P(i, 0) );
	}

	vector<int> score(N, 0);
	vector<int> broadTime(N, 0);

	int bt = 0;
	int maxNo = 0;
	for (int i = 0; i < v.size(); ++i) {
		int t = v[i].t;
		int pos = v[i].d; // テ」ツδ?」ツδシテ」ツδ?ァツ閉ェテ・ツ渉キ
		int x = v[i].x; // テ・ツ環?ァツつケ or テヲツクツ崚ァツつケ テ・ツ按?

		P top = Q.top();

		// テ・ツ環?ァツョツ?
		broadTime[top.id] += t - bt;
		score[pos] += x;
		if (x > 0) { // テ・ツ環?ァツつケ
			if (pos != top.id) {
				P newData = P(pos, score[pos]);
				Q.push( newData );
//				cout << ":" << newData.id << " " << newData.score << endl;
			}
		}

		while ( 1 ) {
			P Top = Q.top();
			if (Top.score == score[Top.id] ) break;

			Q.pop();
			Q.push( P(Top.id, score[Top.id]) );
		}
/*
		queue<P> Q2;
		while ( !Q.empty() ) {
			P data = Q.top(); Q.pop(); Q2.push(data);
			cout << ":" << data.id << " " << data.score << endl;
		}
		while ( !Q2.empty() ) {
			P data = Q2.front(); Q2.pop(); Q.push(data);
		}
		cout << endl;
*/
//		cout << Q.top().score << endl;

//		cout << ":" << top.id << endl;

		bt = t;
	}
	broadTime[Q.top().id] += L - bt;

	int ansNo = 0, ansT = -1;
	for (int i = 0; i < broadTime.size(); ++i) {
		if (broadTime[i] > ansT) {
			ansT = broadTime[i];
			ansNo = i;
		}
//		cout << ":" << broadTime[i] << endl;
	}
	cout << (ansNo + 1) << endl;

	for (int i = 0; i < score.size(); ++i) {
//		cout << score[i] << endl;
	}
}

Measured memory_bytes: 19712
N = int(input())
Hs = [int(x) for x in input().split()]

# 右端から見て, 単調減少/同じにできればいい.
# 右端から見て, 右側より大きければ1つ減らす.
# その上で比較していく. もし単調減少/同じにできなければ'No'を返す.

prev = 'init'
is_yes = True
for i in range(N):
    current = Hs[N-1-i]
    if prev == 'init':
        prev = current
        continue
    elif prev >= current:
        prev = current
    elif prev == current - 1:
        prev = current - 1
    else:
        is_yes = False

if is_yes:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 14396
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
    ll N;
    cin >> N;
    int a[N];
    bool no1 = true;
    for(int i = 0; i < N; i++){
        cin >> a[i];
        if(a[i] == 1) no1 = false;
    }
    if(no1){
        cout << -1 << "\n";
        return 0;
    }
    
    int ans = 0, num = 1;
    for(int i = 0; i < N; i++){
        if(a[i] == num){
            num++;
        }else{
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 1024
N=int(input())
A=list(map(int,input().split()))

c=0
money=1000
stock=0


while c<N:
    if c==N-1:  #final
        money+=A[c]*stock
        stock=0
    elif A[c]<A[c+1] and stock==0:  #buy
        stock+=money//A[c]
        money-=A[c]*stock
    elif A[c]>A[c+1]:  #sell
        money+=A[c]*stock
        stock=0
    
    #print(c,money,stock)
    c+=1
    
    
#例外：買わないほうが得
D=sorted(A,reverse=True)
if A==D:
    print(1000)
else:
    print(money)

Measured memory_bytes: 9204
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
const int N=1e5+100;
int a[N];
main()
{

int n,k;
scanf("%d",&n);
scanf("%d",&k);
for(int i=0;i<n;i++)
    scanf("%d",a+i);
sort(a,a+n);
int sum=0;
for(int i=0;i<k;i++)
    sum+=a[i];

    printf("%d",sum);
}


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

int main()
{
	unsigned long long a[100] = { 1 }, temp = 0;
	long long x = 0, y = 1, t = 0;

	cin >> a[0] >> a[1];
	
	if (a[0] < a[1]) {
		temp = a[0];
		a[0] = a[1];
		a[1] = temp;
	}

	a[2] = a[0] % a[1];

	int i = 2;

	for (i = 2; a[i] != 0; i++)
		a[i + 1] = a[i - 1] % a[i];

	for (int j = 0; j < i - 2; j++) {
		t = x;
		x = y;
		y = t - (a[i - j - 3] / a[i - j - 2]) * y;
	}

	while (abs(x - (long long) (a[1] / a[i - 1])) + abs(y + (long long)(a[0] / a[i - 1])) <= abs(x) + abs(y)) {
		x = x - a[1] / a[i - 1];
		y = y + a[0] / a[i - 1];
	}

	while (abs(x + (long long)(a[1] / a[i - 1])) + abs(y - (long long)(a[0] / a[i - 1])) < abs(x) + abs(y)) {
		x = x + a[1] / a[i - 1];
		y = y - a[0] / a[i - 1];
	}

	if (temp > 0) {
		temp = x;
		x = y;
		y = temp;
	}

	cout << x << " " << y << endl;

	return 0;
}

Measured memory_bytes: 3104
/* created   : 2019-11-09 21:04:30
 * accepted  : 2019-11-10 09:52:03
 * author    : landcold7
 */
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mt make_tuple
#ifndef LOCAL
#define trace(...)
#endif
typedef long long ll;
typedef pair<ll, int> PII;

struct node {
  int to;
  int cost;
};

const int N = 1e5 + 7;
const ll INF = 1e18;
vector<node> g[N];
int n;
int m;

template <class T>
vector<T> dijkstra(int src) {
  vector<T> dist(n, INF);
  priority_queue<PII, vector<PII>, greater<PII>> q;
  dist[src] = 0;
  q.push({0, src});
  while (!q.empty()) {
    auto tp = q.top();
    q.pop();
    T d = tp.first;
    int u = tp.second;
    if (d > dist[u]) {
    // Very important lines of code here
      continue;
    }
    for (auto e : g[tp.second]) {
      if (dist[u] + e.cost < dist[e.to]) {
        dist[e.to] = dist[u] + e.cost;
        q.push(PII{dist[e.to], e.to});
      }
    }
  }
  return dist;
}

void solve() {
  cin >> n >> m;
  for (int i = 0; i < n - 1; i++) {
    g[i + 1].push_back(node{i, 0});
  }
  for (int i = 0; i < m; i++) {
    int u, v, c; cin >> u >> v >> c;
    u--, v--;
    g[u].push_back(node{v, c});
  }
  vector<ll> dist = dijkstra<ll>(0);
  cout << (dist[n - 1] == INF ? -1 : dist[n - 1]) << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}


Measured memory_bytes: 8568
//
//  main.cpp
//  sandbox
//
//  Created by 田村雄太 on 2017/09/16.
//  Copyright © 2017年 田村雄太. All rights reserved.
//

#include <iostream>
#include <utility>


using namespace std;

pair<int,int> getans(){
    
    int A,B,C,D,E,F;
    cin>>A>>B>>C>>D>>E>>F;
    double nodo = 0;
    std::pair<int,int> ans = make_pair(100 * A, 0);
    for(int i = 0 ; A * i <= F; i = i +  100){
        for(int j = 0 ; A * i + B * j <= F; j = j + 100){
            if(i == 0 && i == j){
                continue;
            }
            for(int k = 0 ; A * i + B * j + C * k <= F; k++){
                for(int l = 0 ; A * i + B * j + C * k + D * l <= F; l++){
                    if ( C * k + D * l > (A * i + B * j) * E/100 ){
                        break;
                    }
                    const double nodok = 100.0 * ( C * k + D * l ) /
                    (A * i + B * j + C * k + D * l);
                    if(nodok > nodo){
                        nodo = nodok;
                        ans = make_pair(A * i + B * j + C * k + D * l,
                                        C * k + D * l);
                        if(C * k + D * l == (A * i + B * j) * E/100){
                            return ans;
                        }
                    }
                }
            }
        }
    }
    return ans;
}



int main(int argc, const char * argv[]) {
    
    const pair<int,int> ans = getans();
    cout<<ans.first<<" "<<ans.second<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll mod = 1e9 + 7;
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};

int main() {
  char a;
  cin >> a;
  if (int(a) > 90) {
    cout << "a" << endl;
  } else {
    cout << "A" << endl;
  }

  return 0;
}



Measured memory_bytes: 3616
#include <iostream>

int main(){
  int a, b, k;
  std::cin >> a >> b >> k;
  for(int i = 0; i < k; i++){
    if(i % 2 == 0){
      a = a - (a % 2);
      b += a / 2;
      a = a / 2;
    }
    else{
      b = b - (b % 2);
      a += b / 2;
      b = b / 2;
    }
  }
  std::cout << a << " " << b << std::endl;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(x) x.begin(), x.end()

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long long ll;

template <typename T> void max_self(T& a, T b){
  a = max(a,b);
}

template <typename T> void min_self(T& a, T b){
  a = min(a,b);
}

void solve(){	
  int n;cin>>n;
  vi v(n);
  for(int i=0;i<n;++i) cin>>v[i];
  vi ans(n);
  for(int i=1;i<n;++i) ans[0] = ans[0]^v[i];
  for(int i=1;i<n;++i){
      ans[i] = ans[i-1]^v[i]^v[i-1];
  }
  for(int i=0;i<n;++i){
    if(i == n-1)
      cout<<ans[i]<<endl;
    else
      cout<<ans[i]<<" ";
  }
}

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  //int t; cin >> t;
  //while(t--) solve();
  //
  solve();
  return 0;
}


Measured memory_bytes: 4732
#include<stdio.h>
#include<string.h>
#include <stdlib.h>
#include <math.h>
#define MAX 100

#define M 1000000
#define L 12

char H[M][L];

int gC(char ch){
  int ct;
  if(ch=='A'){
    ct = 1;
  }
  else if(ch=='C'){
    ct = 2;
  }
  else if(ch=='G'){
    ct = 3;
  }
  else if(ch=='T'){
    ct = 4;
  }
  return ct;
}

long long gK(char str[]){
  
  long long sum = 0, p = 1, i;
  
  for(i=0;i<strlen(str);i++){
    
    sum += p*(gC(str[i]));
    
    p *= 5;
    
  }
  return sum;
}

int A(int key)
{
  return key%M;
}

int B(int key)
{
  return 1+key%(M-1);
}

int find(char str[])
{
  long long sum;
  int i,j;

  sum = gK(str);

  for(i=0;;i++){
    
    j = (A(sum)+i*B(sum))%M;
    
    if(strcmp(H[j],str)==0) return 1;
    
    else if(strlen(H[j])==0) return 0;
  }
}  

int insert(char str[]){
  long long sum;
  int i,h;

  sum = gK(str);
  
  for(i=0;;i++){
    
    h = (A(sum)+i*B(sum))%M;
    
    if(strcmp(H[h],str)==0) return 1;
    
    else if(strlen(H[h])==0){
      
      strcpy(H[h],str);
      
      return 0;
    }
  }
}

int main(){
  int i,n;
  char str[L],c[9];
  
  for(i=0;i<M;i++) H[i][0] = '\0';
    
  scanf("%d",&n);
    
  for(i=0;i<n;i++){
    
    scanf("%s%s",c,str);
    
    if(c[0]=='i') insert(str);
    
    else{
      
      if(find(str)==1) printf("yes\n");
      
      else printf("no\n");
    }
  }

  return 0;
}  





Measured memory_bytes: 13452
import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		
		int[] ar = {sc.nextInt(), sc.nextInt(), sc.nextInt()};
		Arrays.sort(ar);
		System.out.println(ar[0]+" "+ar[1]+" "+ar[2]);
		
	}
}


Measured memory_bytes: 26396
# -*- coding: utf-8 -*-
n,m=map(int,input().split())

m_lst=[-1]
for i in range(m):
    m_lst.append(int(input()))
m_lst.append(n+1)
d_lst=[]
for i in range(len(m_lst)-1):
    d_lst.append(m_lst[i+1]-m_lst[i]-1)
def f(length):
    d=length-1
    if d==-1:
        return 0
    elif d==0:
        return 1
    elif d == 1:
        return 1
    elif d == 2:
        return 2
    else:
        last_two=1
        last_one=2
        last=0
        for i in range(d-2):
            last=last_two+last_one
            last_two=last_one
            last_one=last
        return last

output =1 
for d in d_lst:
    output*=f(d)
print(output%1000000007)


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    EACH(x,vec) is >> x;
    return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
    REP(i,vec.size()) {
        if (i) os << " ";
        os << vec[i];
    }
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
    REP(i,vec.size()) {
        if (i) os << endl;
        os << vec[i];
    }
    return os;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    string s; cin >> s;
    int n = s.size();
    vector<string> cand = {"dream", "dreamer", "erase", "eraser"};
    vector<bool> dp(n+1, false);
    dp[0] = true;
    REP(i, n) {
        if (!dp[i]) continue;
        EACH(str, cand) {
            if (i + str.size() <= n && s.substr(i, str.size()) == str) {
                dp[i+str.size()] = true;
            }
        }
    }
    if (dp[n]) cout << "YES" << endl;
    else cout << "NO" << endl;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main(void){
    int H,W;
    while(1){
        cin>>H>>W;
        if(H==0&&W==0)break;
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cout<<"#";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3064
lis_1=[1,3,5,7,8,10,12]
lis_2=[4,6,9,11]
lis_3=[2]
x,y=map(int,input().split())
print("Yes" if (x in lis_1 and y in lis_1) else "Yes" if (x in lis_2 and y in lis_2) else "Yes" if (x in lis_3 and y in lis_3) else "No")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
/*
    s.find_by_order(k) ---> returns iterator to the element at index(from 0) k
    s.order_of_key(val) ---> number of elements that are strictly smaller than the given value
*/
typedef long long int ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<long long int> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<long long int>> vvl;
typedef pair<int, int> pii;
typedef pair<long long int, long long int> pll;
typedef vector<pair<int, int>> vii;
typedef vector<pair<long long int, long long int>> vll;
#define fast() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define test() long long int tc; cin >> tc; cin.ignore(); while(tc--) 
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define MOD 1000000007
#define SMOD 998244353
#define pq priority_queue
#define all(x) x.begin(),x.end()
#define SP(x) setprecision(x)
#define sp " "
#define inp(a) ll a;cin>>a;cin.ignore()
#define inps(a,b) ll a,b;cin>>a>>b;cin.ignore()
#define out(a) cout<<SP(20)<<a<<'\n'
#define outs(a,b) cout<<SP(20)<<a<<" "<<b<<'\n'
#define ins insert
#define er erase
#define lb lower_bound
#define ub upper_bound
#define printclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define inpa(a,n) ll a[n]; for(int i=0; i<n; i++){cin>>a[i];}
#define inpv(a,n) vl a; for(int i=0; i<n; i++){inp(x);a.pb(x);}
#define outa(a,n) for(int i=0;i<n;i++){cout<<a[i]<<" ";}cout<<'\n';
#define outv(v) for(auto i:v){cout<<i<<" ";}cout<<'\n';
set<char> vow = {'a','e','i','o','u','A','E','I','O','U'};
ll xpow(ll n, ll m){if(m==0){return 1;}else{ll x = xpow(n, m/2);if(m&1){return x*x*n;}else{return x*x;}}}
ll xmod(ll a, ll m){return (((a%m)+m)%m);}
ll xmodpow(ll n, ll m, ll y){if(m==0){return 1;}else{ll x = xmodpow(n, m/2, y);if(m&1){return xmod((xmod((xmod(x,y)*xmod(x,y)),y)*xmod(n,y)),y);}else{return xmod((xmod(x,y)*xmod(x,y)),y);}}}
 
int main() {
	fast();
 
    /*NA – JEONG – MO – SA – JI – MI – DA – CHAE – TZU*/
    
    inp(n);
    map <ll, ll> m;
    bool check = 0;
    for(int i=0; i<n; i++){
        inp(x);
        m[x]++;
        if(m[x]==2){
            check = 1;
        }
    }
    if(check){
        out("NO");
    }
    else{
        out("YES");
    }
}

Measured memory_bytes: 12800
#include <set>
#include <vector>
#include <cstdio>
#include <assert.h>
using namespace std;
typedef long long ll;
inline ll read() {
    char ch = getchar(); ll x = 0;
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9') x = x*10+ch-'0', ch = getchar();
    return x;
}


const ll INF = 2e13 + 5;
const int N = 1e5+5;

struct seg {
    int l, r;
    ll v;

    seg() {}
    seg(int a, int b, ll c): l(a), r(b), v(c) {}
    bool operator <(const seg &b) const {
        return l < b.l;
    }
};

set <seg> s;
set <seg>:: iterator it;
seg del[N], ins[N];

int t1, t2;
void work() {
    ll y = read(), x = read();
    it = s.upper_bound(seg(y, 0, 0)), --it;
    if(y+1 <= it->r) ins[++t1] = (seg(y+1, it->r, it->v));
    del[++t2] = (*it);

    int nl = it->l, nr = y; ll nv = it->v;
    for(--it; 1LL*(nr-nl+1)*(it->v-nv) < x && it != s.begin();) {
        x -= 1LL*(nr-nl+1)*(it->v-nv);
        del[++t2] = (*it);
        nl = it->l, nv = it->v, --it;
    }

    nv += x / (nr-nl+1);
    x  %= (nr-nl+1), nl = it->r+x+1;
    if(nl <= nr) ins[++t1] = (seg(nl, nr, nv));
    if(it->r < nl-1) ins[++t1] = (seg(it->r+1, nl-1, nv+1));

    for(int i = 1; i <= t2; ++i) s.erase(del[i]);
    for(int i = 1; i <= t1; ++i) s.insert(ins[i]);
    t1 = t2 = 0;
}


int n, q;
int main() {
    n = read(), q = read();

    s.insert(seg(0, 0, INF));
    s.insert(seg(1, n, 0));

    while(q--) work();
    for(it = s.begin(), ++it; it != s.end(); ++it)
        for(int j = it->l; j <= it->r; ++j)
            printf("%lld\n", it->v);
    return 0;
}


Measured memory_bytes: 7680
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i=0; i<(n); ++i)
using ll = long long;
using P = pair<int, int>;
 
int main() {
  P x, y;
  cin >> x.first >> x.second >> y.first >> y.second;

  int i = 0;
  while (x.first > 0 && y.first > 0) {
    if (i % 2 == 0) {
      y.first -= x.second;
    } else {
      x.first -= y.second;
    }
    i++;
  }
  if (x.first <= 0) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define REP(i,s,l) for(lli i=s;i<l;i++)
#define DEBUG 0
#define INF (1LL<<50)
#define MOD 1000000007

lli g[2][3];

signed main(){

	lli n;
	cin>>n;

	REP(i,0,2)REP(j,0,3)cin>>g[i][j];

	/*残りのどんぐりが何個あるとき*/
	/*AからBにでどんぐりを増やしつつBからAにどんぐりを増やすマン*/

	vector<lli> dp(n+1);
	REP(i,0,n+1)dp[i]=i;
	for(lli i=0;i<3;i++){
		lli F = g[0][i], T = g[1][i];
		for(lli m=0;m+F<=n;m++){
			dp[m+F] = max(dp[m+F],dp[m]+T);
		}
	}
	n = dp[n];

	dp.resize(n+1);
	REP(i,0,n+1)dp[i]=i;

	for(lli i=0;i<3;i++){
		lli F = g[1][i], T = g[0][i];
		for(lli m=0;m+F<=n;m++){
			dp[m+F] = max(dp[m+F],dp[m]+T);
		}
	}

	cout<<dp[n]<<endl;

	return 0;
}

Measured memory_bytes: 195584
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 30;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N, L;

void solve() {
	cin >> N >> L;
	int sum = L * N + (N - 1) * N / 2;
	int absv = inf;
	int ans = -inf;

	rep(i, 1, N + 1) {
		int b = sum - (L + i - 1);
		if(abs(sum - b) < absv) {
			absv = abs(sum - b);
			ans = b;
		}
	}
	cout << ans << "\n";
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

vector<ll> dijkstra(vector<vector<pair<int, ll> > > const & g, int root) {
    vector<ll> dist(g.size(), LLONG_MAX);
    priority_queue<pair<ll, int> > que;
    dist[root] = 0;
    que.emplace(- dist[root], root);
    while (not que.empty()) {
        ll dist_i; int i; tie(dist_i, i) = que.top(); que.pop();
        if (dist[i] < - dist_i) continue;
        for (auto it : g[i]) {
            int j; ll cost; tie(j, cost) = it;
            if (- dist_i + cost < dist[j]) {
                dist[j] = - dist_i + cost;
                que.emplace(dist_i - cost, j);
            }
        }
    }
    return dist;
}

constexpr int mod = 1e9 + 7;
ll sq(ll x) { return x * x % mod; }

vector<int> count_path(vector<vector<pair<int, ll> > > const & g, int root, vector<ll> const & dist) {
    vector<int> cnt(g.size());
    vector<int> order(g.size());  // ascending by dist
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) { return dist[i] < dist[j]; });
    for (int i : order) {
        if (i == root) {
            cnt[i] = 1;
        } else {
            ll acc = 0;
            for (auto edge : g[i]) {
                int j; ll d; tie(j, d) = edge;
                if (dist[j] + d != dist[i]) continue;
                acc += cnt[j];
            }
            cnt[i] = acc % mod;
        }
    }
    return cnt;
}

int main() {
    // input
    int n, m; scanf("%d%d", &n, &m);
    int s, t; scanf("%d%d", &s, &t);
    -- s; -- t;

    vector<vector<pair<int, ll> > > g(n);
    REP (i, m) {
        int u, v, d; scanf("%d%d%d", &u, &v, &d);
        -- u; -- v;
        g[u].emplace_back(v, d);
        g[v].emplace_back(u, d);
    }

    // solve
    vector<ll> dist_from_s = dijkstra(g, s);
    vector<ll> dist_to_t   = dijkstra(g, t);
    vector<int> count_from_s = count_path(g, s, dist_from_s);
    vector<int> count_to_t   = count_path(g, t, dist_to_t);
    auto used = [&](int i) { return dist_from_s[i] + dist_to_t[i] == dist_from_s[t]; };

    ll complement = 0;
    REP (i, n) {
        if (not used(i)) continue;
        if (dist_from_s[i] == dist_to_t[i]) {
            complement += sq(count_from_s[i]) * sq(count_to_t[i]) % mod;
        }
        for (auto edge : g[i]) {
            int j; ll dist; tie(j, dist) = edge;
            if (dist_from_s[i] + dist != dist_from_s[j]) continue;
            if (not used(j)) continue;
            if (dist_from_s[i] < dist_from_s[t] / 2.0 and dist_to_t[j] < dist_from_s[t] / 2.0) {
                complement += sq(count_from_s[i]) * sq(count_to_t[j]) % mod;
            }
        }
    }
    complement %= mod;
    int result = (sq(count_from_s[t]) - complement + mod) % mod;

    // output
    printf("%d\n", result);
    return 0;
}


Measured memory_bytes: 17236
from bisect import bisect
N = int(input())
S = [input() for _ in range(N)]

def count(s):
    n = len(s)
    n1 = 0
    n2 = 0
    for i in range(n):
        if s[i]=='(':
            n2 += 1
        else:
            if n2 > 0:
                n2 -= 1
            else:
                n1 += 1
    return n1,n2

l1 = []
l2 = []
m1 = 0
m2 = 0
for i in range(N):
    n1,n2 = count(S[i])
    if n1+n2==0:
        continue
    if n1 == 0:
        m1 += n2
        continue
    if n2 == 0:
        m2 += n1
        continue
    if n2-n1>=0:
        l1.append([n1,n2])
    else:
        l2.append([n1,n2])

ans = 'Yes'
l1.sort()
for i in range(len(l1)):
    n1,n2 = l1[i]
    if m1 < n1:
        ans = 'No'
        break
    m1 += n2-n1

l2.sort(key=lambda x:x[1])
for i in range(len(l2)):
    n1,n2 = l2[i]
    if m2 < n2:
        ans = 'No'
        break
    m2 += n1-n2

if m1!=m2:
    ans = 'No'

print(ans)



Measured memory_bytes: 183876
N,M = map(int,input().split())
A = []
for i in range(M):
    p,y = map(int,input().split())
    A.append([p,y,i])
A.sort(key=lambda x:(x[0],x[1]))
ans = ["" for i in range(M)]
p = -1
y = 1
for a in A:
    if p!=a[0]:
        y = 1
        p = a[0]
    b = "0"*(6-len(str(a[0])))+str(a[0])+"0"*(6-len(str(y)))+str(y)
    ans[a[2]] = b
    y+=1
for i in ans:
    print(i)

Measured memory_bytes: 32028
#include <iostream>
using namespace std;
int dp[100000],s[100000];
int main(void){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
    }
    dp[1]=abs(s[1]-s[0]);
    for(int i=2;i<n;i++){
        dp[i]=min(abs(s[i]-s[i-2])+dp[i-2],abs(s[i]-s[i-1])+dp[i-1]);
    }
    cout<<dp[n-1]<<endl;
}


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

#define ld long double
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define nl cout << endl
#define pii pair <ll, ll>
#define pb push_back
#define mp make_pair
#define y1 abacaba
#define fn "abc"
#define sz(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define Need_For_Speed ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define __lcm(a, b) (a * b) / __gcd(a, b)

using namespace std;

const long long MXN = 1e5 + 1;
const long long MOD = 1e9 + 7;

int a[22][22];

int dp[(1 << 21) + 28];

int main () {

    Need_For_Speed
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a[i][j];
        }
    }
    dp[0] = 1;
    for (int mask = 0; mask < (1 << n); mask++) {
        int x = __builtin_popcount(mask);
        for (int j = 1; j <= n; j++) {
            if (a[x + 1][j] && !((mask >> (j - 1)) & 1)) {
                (dp[mask | (1 << (j - 1))] += dp[mask]) %= MOD;

            }
        }
    }
    cout << dp[(1 << n) - 1];
    return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
#define MAX (ll)(1e5 + 7)
#define INF (ll)(1e18)
#define MOD (ll)(998244353)

using namespace std;
using ll = long long;
using cd = complex<double>;

const int x = sqrt (3 * MAX);
int v[3 * MAX], w[3 * MAX], dp[x][MAX];
int main () {
	int n, q;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> v[i] >> w[i];
	}
	int x = sqrt (n);
	for (int i = 0; i <= x; i++) {
		for (int j = 0; j < MAX; j++) {
			dp[i][j] = -MOD;
		}
	}
	dp[0][0] = 0;
	for (int i = 1; i <= x; i++) {
		for (int j = 0; j < MAX; j++) {
			dp[i][j] = max (dp[i / 2][j], dp[i][j]);
			if (j) {
				dp[i][j] = max (dp[i][j], dp[i][j - 1]);
			}
			if (j - w[i] >= 0) {
				dp[i][j] = max (dp[i / 2][j - w[i]] + v[i], dp[i][j]);
			}
		}
	}
	cin >> q;	
	for (int i = 0; i < q; i++) {
		int vv, l;
		cin >> vv >> l;
		vector<int> ve;
		while (vv > x) {
			ve.push_back (vv);
			vv = vv / 2;
		}
		int y = (1 << ve.size ()), ma = 0;
		for (int i = 0; i < y; i++) {
			int ww = 0, lx = 0;
			for (int j = 0; j < ve.size (); j++) {
				if ((i >> j) & 1) {
					ww += w[ve[j]], lx += v[ve[j]];
				}
			}
			if (ww <= l) {
				ma = max (lx + dp[vv][l - ww], ma);
			}
		}
		cout << ma << "\n";
	}
}


Measured memory_bytes: 205684
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

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

class State
{
public:
	int lx,ly,rx,ry,c,f;
	State(int lx, int ly, int rx, int ry, int c, int f)
		:lx(lx),ly(ly),rx(rx),ry(ry),c(c),f(f)
	{}

	bool operator<(const State& s) const
	{
		return c>s.c;
	}
};

bool v[30][60][30][60][2];

int main()
{
	int W,H;
	char f[80][80];
	while(cin >> W >> H, (W||H))
	{
		memset(v,0,sizeof(v));

		priority_queue<State> q;
		for(int i=0; i<H; i++)
		for(int j=0; j<W; j++)
		{
			cin >> f[j][i];
			if(f[j][i]=='S')
			{
				for(int k=0; k<2; k++)
					q.push(State(j,i,j,i,0,k));
			}
		}

		bool g=false;
		while(!q.empty())
		{
			State s=q.top(); q.pop();
			if(f[s.lx][s.ly]=='T' || f[s.rx][s.ry]=='T')
			{
				g=true;
				cout << s.c << endl;
				break;
			}

			if(v[s.lx][s.ly][s.rx][s.ry][s.f]) continue;
			v[s.lx][s.ly][s.rx][s.ry][s.f]=1;

			for(int i=0; i<9; i++)
			{
				if(s.f==0)
				{
					int tlx=s.rx-dx[i], tly=s.ry+dy[i];
					int tf=(s.f+1)%2;
					if(tlx<0||tly<0||tlx>=W||tly>=H) continue;
					if(f[tlx][tly]=='X') continue;
					if(v[tlx][tly][s.rx][s.ry][tf]) continue;

					int tc=s.c;
					if(isdigit(f[tlx][tly])) tc+=f[tlx][tly]-'0';

					q.push(State(tlx,tly,s.rx,s.ry,tc,tf));
				}
				if(s.f==1)
				{
					int tlx=s.lx+dx[i], tly=s.ly+dy[i];
					int tf=(s.f+1)%2;
					if(tlx<0||tly<0||tlx>=W||tly>=H) continue;
					if(f[tlx][tly]=='X') continue;
					if(v[s.lx][s.ly][tlx][tly][tf]) continue;

					int tc=s.c;
					if(isdigit(f[tlx][tly])) tc+=f[tlx][tly]-'0';

					q.push(State(s.rx,s.ry,tlx,tly,tc,tf));
				}
			}

		}

		if(!g) cout << -1 << endl;
		
	}

}

Measured memory_bytes: 8008
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    const K = parseInt(arg[0].split(" ")[1]);
    
    const A = arg[1].split(" ").map(n=>parseInt(n));
    
    const ball = [...Array(N)].fill(0);
    
    for(let i=0; i<N; i++) {
        ball[A[i]-1]++;
    }
    
    ball.sort((a,b)=>b-a);
    
    const temp = ball.filter(n=>n!==0); 
    
    // console.log(ball)
    
    if(temp.length <= K) {
        console.log(0);
    } else {
        console.log(temp.slice(K).reduce((m,n)=>m+n));
    }
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

int main(){
  int s = 0;
  int s_1, s_2, s_3 = 0;
  cin >> s;
  s_1 = s % 2;
  s_2 = (s-s_1)/10 % 2;
  s_3 = (s-s_1-s_2*10)/100 % 2;
  cout << s_1 + s_2 + s_3 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fi first
#define pii pair<int,int>
#define se second
using namespace std;
void solve()
{
    int n;
    cin>>n;
    int x=0;
    while(x<n){
        x+=1000;
    }
    cout<<x-n;
}
int32_t main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    t=1;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 3648
#include <iostream>

using namespace std;

using ll = long long;

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()

typedef pair<int, int> P;

const int MOD = (int) 1e9 + 7;

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	string s;
	cin >> s;
	
	int minT = s.length() + 1;
	REP(i, s.length() - 1) {
		if (s[i] != s[i + 1]) {
			minT = min(minT, max(i + 1, (int) (s.length() - i - 1)));
		}
	}
	
	if (minT == s.length() + 1) cout << s.length() << endl;
	else cout << minT << endl;
	
	return 0;
}

Measured memory_bytes: 512
for _ in range(int(input())):
    p,q=map(int,input().split())
    c=0
    for i in range(143):
        for j in range(143):
            if (i>0 or j>0)and(j*p+i*q)%(j*j+i*i)==0 and (j*q-i*p)%(j*j+i*i)==0:c+=1
    print('P' if c<5 else 'C')

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int n;
  cin>>n;
  vector<ll> h(n);
  rep (i, n) {
    cin>>h.at(i);
  }
  int ans=0;
  int memo=0;
  rep (i, n-1) {
    if(h.at(i)>=h.at(i+1)) {
      memo++;
      ans=max(memo, ans);
    }
    else {
      memo=0;
    }
  }
  cout<<ans<<endl;
  
}

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

using namespace std;

int main() {
    int N;
    cin >> N;
    
    string str;
    cin >> str;
    
    if(N%2!=0) {
        cout << "No" << endl;
        return 0;
    }
    
    bool flag=true;
    for(int i=0; i<N/2; i++) {
        if(str[i]!=str[i+N/2]) {
            flag=false;
            break;
        }
    }
    
    if(flag) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

    return 0;
    
}

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

using ll = long long;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  if (fopen("input.in", "r")) {
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
  }

  ll N, W;
  cin >> N >> W;
  vector<ll> w(N+1), v(N+1);
  for (ll i = 1; i <= N; i++) {
    cin >> w[i] >> v[i];
  }

  // dp[i] = min weight for subjset of sum of value exactly i

  vector<ll> dp(1e5+1, 1e10);
  dp[0] = 0;
  for (int k = 1; k <= N; k++) {
    for (int i = 1e5; i >= v[k]; i--) {
      dp[i] = min(dp[i-v[k]]+w[k], dp[i]);
    }
  }

  for (int i = 1e5; i >= 0; i--) {
    if (dp[i]<=W) { cout << i << endl; break; }
  }

  return 0;
}

Measured memory_bytes: 1024
n = int(input())
l = list(map(int, input().split()))
c = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            s = []
            s.append(l[i])
            s.append(l[j])
            s.append(l[k])
            s.sort()
            if s[0]+s[1] > s[2]:
                if len(set(s)) == 3:
                    c += 1

print(c)

Measured memory_bytes: 68520
def resolve():
    '''
    code here
    '''
    S_dash = input()[::-1]
    T = input()[::-1]

    is_flag = False

    res = ''

    for i in range(len(S_dash)):
        res = S_dash[:i]
        # print(res)
        if len(S_dash) - len(res) >= len(T):
            for j in range(len(T)):
                if S_dash[i+j] == T[j] or S_dash[i+j] == '?':
                    res += T[j]
                else:
                    # print('bk')
                    break
            else:
                is_flag = True
                break

        # print(res)

    # print(S_dash, T, res)
    # print(S_dash[len(T):])
    res = res + S_dash[len(T)+i:]
    res = res.replace('?','a')

    print(res[::-1]) if is_flag else print('UNRESTORABLE')     

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <string>
#define rep(i, n) for (int i = 0; i < n; ++i)
using ll = long long;
using namespace std;
#define P pair<int, int>
using namespace std;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    long long a,b,ans=0,mod=1e9+7,i=1;
 
    cin>>a>>b;
 
    if(a==b || abs(a-b)==1){
 
        if(a<b)
            swap(a,b);
        ans=1;
        if(a==b){
            i=2;
        }
        for(int i=1; i<=a; i++){
 
            ans*=i;
            ans%=mod;
 
            if(i==b){
                b=ans;
            }
        }
        ans = (ans*b*i)%mod;
    }
    cout<<ans<<endl;
    return 0;
}
    
  

Measured memory_bytes: 3628
s = gets.chomp.split("")
even_one = 0
odd_one = 0

(s.size).times do |tile|
    if tile % 2 == 0
        if s[tile] == "1"
            even_one += 1
        else
            odd_one += 1
        end
    else
        if s[tile] == "1"
            odd_one += 1
        else
            even_one += 1
        end
    end
end

puts [even_one, odd_one].min

Measured memory_bytes: 9468
N, K = map(int, input().split())
h = []
for i in range(N):
  h.append(int(input()))
h.sort()
mini = 1e9
for i in range(N-K+1):
  sub = h[i+K-1] - h[i]
  if(sub < mini):
    mini = sub
print(mini)


Measured memory_bytes: 7384
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int INF = 12;
int main(){
	int N;
	cin >> N;
	vector<int> D(N);
	for (int i = 0; i < N; i++){
		cin >> D[i];
	}
	vector<int> cnt(13, 0);
	cnt[0]++;
	for (int i = 0; i < N; i++){
		cnt[D[i]]++;
	}
	bool zero = false;
	if (cnt[0] >= 2 || cnt[12] >= 2){
		zero = true;
	}
	for (int i = 1; i <= 11; i++){
		if (cnt[i] >= 3){
			zero = true;
		}
	}
	if (zero){
		cout << 0 << endl;
	} else {
		int ans = 0;
		for (int i = 0; i < (1 << 11); i++){
			vector<int> t;
			for (int j = 0; j <= 12; j++){
				if (cnt[j] == 1){
					if (j == 0){
						t.push_back(0);
						t.push_back(24);
					} else if (j == 12){
						t.push_back(12);
					} else {
						if (i >> (j - 1) & 1){
							t.push_back(24 - j);
						} else {
							t.push_back(j);
						}
					}
				}
				if (cnt[j] == 2){
					t.push_back(j);
					t.push_back(24 - j);
				}
			}
			sort(t.begin(), t.end());
			int s = INF;
			int sz = t.size();
			for (int j = 0; j < sz - 1; j++){
				s = min(s, t[j + 1] - t[j]);
			}
			ans = max(ans, s);
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 3620
#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
int a[10001];
int t,n,m;
int ans,sum;
signed main()
{
	scanf("%lld",&t);
	ans=1000;
	for(int i=1;i<=t;i++)
		scanf("%lld",&a[i]);
	for(int i=1;i<t;i++) {
		sum=0;
		if(a[i]<a[i+1]) sum=ans/a[i];
		ans+=(a[i+1]-a[i])*sum;
	   }
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 3780
import java.util.Scanner;

class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    int x = (int)Math.sqrt((double)N);
    
    for(; x>1; x--){
      if(N % x == 0){
        break;
      }
    }
    
    System.out.println(x - 1 + N/x - 1);
  }
}


Measured memory_bytes: 22868