akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i, n) for (ll i = 0; i < n; i++)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define fi first
#define se second

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;
}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i];if(i<len-1) s<<" ";
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){
	int len=d.size();
	rep(i,len){
		s<<d[i]<<endl;
	}
	return s;
}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){
	s<<"{ ";
	for(auto itr=v.begin();itr!=v.end();++itr) {
		if (itr!=v.begin()) {s<< ", ";}
		s<<(*itr);
	}
	s<<" }";
	return s;
}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){
	s<<"{"<<endl;
	for(auto itr=m.begin();itr!=m.end();++itr){
		s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;
	}
	s<<"}"<<endl;
	return s;
}

const ll mod=1e9+7;
const ll inf=1e15;
const int INF=1e9;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	vector<vector<int>> a(n,vector<int>(n-1));
	int V=n*(n-1)/2;
	rep(i,n){
		rep(j,n-1){
			cin>>a[i][j];
			a[i][j]--;
		}
	}
	map<Pi,int> id;
	int now=0;
	rep(i,n){
		FOR(j,i+1,n){
			id[Pi(i,j)]=now;
			id[Pi(j,i)]=now;
			now++;
		}
	}
	vector<vector<int>> g(V);
	rep(i,n){
		rep(j,n-2){
			int nid=id[Pi(i,a[i][j])];
			int neid=id[Pi(i,a[i][j+1])];
			g[nid].push_back(neid);
		}
	}
	vector<int> dp(V,-1);
	vector<bool> used(V,false);
	function<int(int)> dfs=[&](int v){
		if(used[v]){
			if(dp[v]!=-1) return dp[v];
			else return INF;
		}
		used[v]=true;
		int ret=0;
		for(auto itr:g[v]){
			chmax(ret,dfs(itr)+1);
		}
		return dp[v]=ret;
	};
	int ans=0;
	rep(i,V){
		if(!used[i]) chmax(ans,dfs(i)+1);
	}
	if(ans<INF) cout<<ans<<endl;
	else cout<<-1<<endl;
}

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

using namespace std;

const int N = int(3e5);
int pref[N];

int main(){
	int n;

	scanf("%d", &n);

	for(int i = 1 ; i <= n ; i++){
		char c;

		scanf("\n%c", &c);

		pref[i] = (c == '#');
		
		pref[i] += pref[i - 1];
	}

	int best = 1e9;

	for(int i = 0 ; i <= n ; i++){
		int twhite = pref[i];
		int tblack = (n - i) - (pref[n] - pref[i]);
		
		best = min(best, twhite + tblack);
	}

	printf("%d\n", best);

	return 0;
}

Measured memory_bytes: 1024
//1. 絶対値を外したい
//2. 各赤ちゃんの向きを決め打つ（後ろ向きにハイハイできると考えて整合性を取る）
//3. 活発度が大きい赤ちゃんから順に、端っこから割り当てる貪欲
//4. 赤ちゃんの向きをRRRLLLLLのように決め打つのは最適とは限らない <- 向きの組み合わせが非自明
//5. 3.において活発度最大の赤ちゃんは, 左端か右端に割り当てられる
//6. つまり、活発度の大きい赤ちゃんから「→」or「←」に割り当てていけば、残った場所が区間になる
//7. 区間DPができますね。O(N^2)

#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#define int long long
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef pair<int, int> P;

int n;
P pa[2000];
int dp[2000][2000];

//[l, r]
int dfs(int l, int r, int dep) {
	if (dep == n) return 0;
	if (dp[l][r] != -1) return dp[l][r];
	int res1 = pa[dep].first * abs(pa[dep].second - l) + dfs(l + 1, r, dep + 1);
	int res2 = pa[dep].first * abs(pa[dep].second - r) + dfs(l, r - 1, dep + 1);
	return dp[l][r] = max(res1, res2);
}

signed main() {
	int i, j;
	
	cin >> n;
	rep(i, n) { cin >> pa[i].first; pa[i].second = i; }
	sort(pa, pa + n, greater<P>());
	rep(i, n) { rep(j, n) { dp[i][j] = -1; } }
	
	int ans = dfs(0, n - 1, 0);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 35016
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		try(Scanner scan = new Scanner(System.in)){

			int N = scan.nextInt();
			int W = scan.nextInt();
			int[]w = new int[N];
			int[]v = new int[N];
			for(int i = 0;i<N;i++) {
				w[i] = scan.nextInt();
				v[i] = scan.nextInt();
			}

			long[][]dp = new long[N][W+1];

			long goukei = 0;


			for(int i = 0;i<=W;i++) {
				if(i-w[0]>=0) {
					dp[0][i] = v[0];
				}
			}

			for(int z = 0;z<=W;z++) {
				for(int i = 1;i<N;i++) {
					if(z-w[i]>=0) {
						dp[i][z] = Math.max(dp[i-1][z-w[i]]+v[i], dp[i-1][z]);
					}else {
						dp[i][z] = dp[i-1][z];
				}
			}
			}

			/*
			for(int i = 0;i<=W;i++) {
				for(int j = 0;j<N;j++) {
					System.out.print(dp[j][i]+" ");
				}
				System.out.println();
			}
			*/


			System.out.println(dp[N-1][W]);


		}


	}


}


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

int main() {
  int a, b;
  cin >> a >> b;
  if (a <= 8 && b <= 8) cout << "Yay!" << endl;
  else cout << ":(" << endl;
  return 0;
}

Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define itrfor(itr,A) for(auto itr = A.begin(); itr !=A.end();itr++)
typedef int64_t llong;
char moji[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
char moji2[26]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
char moji3[10]={'0','1','2','3','4','5','6','7','8','9'};
#define Sort(a) sort(a.begin(),a.end());
#define Reverse(a) reverse(a.begin(),a.end());
#define ld PRId64
#define n_MAX int(1e5)





int main(){
    int n;
    cin >> n;
    llong A,B;
    cin >> A >> B;
    
    llong tai[n_MAX + 5];
    REP(i,n) scanf("%ld",&tai[i]);
    llong left = -1;
    llong right = 1e9;
    llong mid,kijun,cnt;
    while(left + 1 < right){
        mid=(left + right) /2;
        kijun= B * mid;
        cnt=0;
        REP(i,n){
            cnt += max((tai[i] - kijun)/(A-B),llong(0));
            if( (tai[i] - kijun)%(A-B)!=0 and tai[i] - kijun >0) cnt +=1;
        }
        if(cnt > mid) left = mid;
        else right = mid;
    }
    cout << right << endl;

}



Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
import sys

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
F=map(int, sys.stdin.readline().split())
A.sort(reverse=True)
F.sort()

max_ans=10**12

def check(temp_ans):
    if temp_ans<0:
        return False
    k=0
    for a,f in zip(A,F):
        if a*f<=temp_ans: continue
        aa=temp_ans/f
        k+=(a-aa)
        if K<k:
            return False
    else:
        return True

h=max_ans
l=-1

while h-l!=1:
    m=(h+l)/2
    if check(m):
        h=m
    else:
        l=m

print h

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

using namespace std;

const int N = 105;
const int K = 1e5 + 5;
const int mod = 1e9 + 7;
int cld[N];
int dp[N][K];

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

    for (int i = 1; i <= n; i ++) cin >> cld[i];

    dp[0][0] = 1;

    for (int i = 1; i <= n; i++) dp[i][0] = 1;
    for (int j = 1; j <= k; j++) dp[0][j] = 0;

    for (int i = 1; i <= n; i++) {
        int sums[k + 1];
        sums[0] = 1;
        for (int j = 1; j <= k; j++) {
            sums[j] = (dp[i - 1][j] + sums[j - 1]) % mod;

            int tmp = sums[j];
            int unreachable = j - cld[i] - 1;

            if (unreachable >= 0) tmp = (tmp - sums[unreachable] + mod) % mod;

            dp[i][j] = tmp;
        }
    }

    cout << dp[n][k];
    return 0;
}



Measured memory_bytes: 43372
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	if(n-(n&-n)==0){printf("No");return 0;}
	printf("Yes\n");
		
	if(n==3)
	{
		printf("1 2\n2 3\n3 4\n4 5\n5 6\n");
		return 0;
	}
	printf("1 2\n2 3\n3 %d\n%d %d\n%d %d\n",n+1,n+1,n+2,n+2,n+3);
	for(int i=4;i+1<=n;i+=2)
	{
		printf("%d %d\n%d %d\n",n+1,i,i,i+n+1);
		printf("%d %d\n%d %d\n",n+1,i+1,i+1,i+n);
	}
	if(n%2==0)
	{
		int k=n&-n;
		int x=n^k^1;
		if(k!=2)
			printf("%d %d\n%d %d\n",k,n,x,n+n);
		else
			printf("%d %d\n%d %d\n",n+2,n,x,n+n);
	}
	return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e9;

#define MAX_V 200

ll d[MAX_V][MAX_V];
int V, M, R;
int r[8];
void warshall_floyd() {
	rep(k, 0, V) rep(i, 0, V) rep(j, 0, V) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

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

	cin >> V >> M >> R;
	rep(i, 0, R) {
		cin >> r[i];
		r[i]--;
	}
	rep(i, 0, V) rep(j, 0, V) {
		if(i == j) d[i][j] = 0;
		else d[i][j] = INF;
	}

	rep(i, 0, M) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		d[a][b] = c;
		d[b][a] = c;
	}

	warshall_floyd();

	vector<int> v(R);
	rep(i, 0, R) v[i] = r[i];
	vsort(v);
	ll res = INF;
	do {
		ll tmp = 0;
		rep(i, 1, R) tmp += d[v[i - 1]][v[i]];
		res = min(tmp, res);
	} while(next_permutation(v.begin(), v.end()));

	cout << res << endl;
}



Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define pb push_back
#define N 100010
#define MOD 1000000007
#define fn(i,n) for(int i=0;i<n;i+=1)
#define rep(i,l,r) for(int i=l;i<=r;i+=1)
#define INF 100000000000000
#define pii pair<int,int>
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

signed main()
{
    
    speed
    int l;cin>>l;
    cout<<setprecision(12)<<fixed<<(l*l*l*1.0)/(27.0)<<endl;
    
    


    return 0;
}


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

struct city {
    int id;
    int prefecture;
    int birth;
    string number;
};

bool id_cmp(const struct city& l, const struct city& r) { return l.id < r.id; }
bool birth_cmp(const struct city& l, const struct city& r) {
    return l.birth < r.birth;
}

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

    vector<city> cities(M);
    for (int i = 0; i < M; i++) {
        int prefecture, birth;
        cin >> prefecture >> birth;
        cities[i].id = i;
        cities[i].prefecture = prefecture;
        cities[i].birth = birth;
    }
    sort(cities.begin(), cities.end(), birth_cmp);
    vector<int> p(N, 0);

    for (int i = 0; i < M; i++) {
        int pr = cities[i].prefecture;
        int q = p[pr - 1] + 1;
        p[pr - 1]++;
        std::ostringstream sout;
        sout << setfill('0') << setw(6) << pr;
        sout << setfill('0') << setw(6) << q;
        cities[i].number = sout.str();
    }

    sort(cities.begin(), cities.end(), id_cmp);

    for (int i = 0; i < M; i++) {
        cout << cities[i].number << endl;
    }

    return 0;
}


Measured memory_bytes: 8284
//
//  main.cpp
//  AC
//
//  Created by makinofuya on 2019/07/08.
//  Copyright © 2019 makinofuya. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <math.h>
#include <map>

typedef long long ll;
using namespace std;
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define out(s) cout << s << endl



int main(){
    int w,h,n;cin >> w >> h >> n;
    vector<int>x(n),y(n),a(n);
    rep(i,n)cin >> x[i] >> y[i] >> a[i];
    int w_l=0,w_r=w,h_u=h,h_s=0;
    rep(i,n){
        if(a[i]==1 ){
            if(w_l<x[i])w_l=x[i];
        }
        if(a[i]==2){
            if(w_r>x[i])w_r=x[i];
        }
        if(a[i]==3 ){
            if(h_s<y[i])h_s=y[i];
        }
        if(a[i]==4 ){
            if(h_u>y[i])h_u=y[i];
        }
    }
    w=(w_r-w_l);
    h=(h_u-h_s);
    if(w<0)w=0;
    if(h<0)h=0;
    
    cout << w*h << endl;
    return 0;
}


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

using namespace std;

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

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

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

    int N;
    cin >> N;

    int A[10000];
    FOR(i, N) cin >> A[i];

    int c = 0;
    FOR(i, N) {
        while (A[i] != 0 and A[i] % 2 == 0) {
            c++;
            A[i] /= 2;
        }
    }
    cout << c;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

#define rep(i, b) for(int i = 0; i < b; i++)
#define repi(i, a, b) for(int i = a; i < b; i++)

using namespace std;

int main(){
    int w;
    int i = 0, j = 0;
    int g[128][128];
    while(cin >> w){
        g[i][j++] = w;
        char c = cin.get();
        if(c == '\n'){
            i++;
            j = 0;
        }
    }
    int dp[128][128] = {0};
    dp[0][0] = g[0][0];
    repi(a,1,i+1)rep(b,a+1){
        if(a < i/2 + 1){
            if(!b) dp[a][b] = dp[a-1][b] + g[a][b];
            else if(b == a) dp[a][b] = dp[a-1][b-1] + g[a][b];
            else dp[a][b] = max(dp[a-1][b],dp[a-1][b-1]) + g[a][b];
        }else{
            dp[a][b] = max(dp[a-1][b],dp[a-1][b+1]) + g[a][b];
        }
    }
    cout << dp[i][0] << endl;
}

Measured memory_bytes: 1284
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdlib>

using namespace std;
//DP用
template<class T> inline bool chmin(T& a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
const long long INF = 1LL << 60;

int main() {
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a,a+n);
    for(int i = 0; i < n; i++) {
        if(a[i-1] == a[i] && i > 0) {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  string s;
  cin >> s;
  int ans = 0,count=0;
  rep(i,s.size()){
    if(s[i]=='A'||s[i]=='T'||s[i]=='G'||s[i]=='C'){
        count++;
    }else{
        ans=max(ans,count);
        count=0;
    }
  }
  ans=max(ans,count);
  count=0;
  cout << ans << endl;
}
  

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

const int mod = 998244353;

int dp[3001][3001], pre[3001][3001], a[3001];

int mul(int a, int b) { return 1LL * a * b % mod; }
void add_self(int& a, int b) { a += b; if(a >= mod) a -= mod; }

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

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

	for(int i = 0; i < n; i++) {
		pre[i][a[i]] = dp[i][a[i]] = i+1;
	}

	for(int w = 1; w <= s; w++) {
		for(int i = 1; i < n; i++) {
			add_self(pre[i][w], pre[i-1][w]);
		}
	}

	for(int w = 1; w <= s; w++) {
		for(int i = 0; i < n; i++) {
			if(w <= a[i] || i == 0) continue;
			add_self(dp[i][w], pre[i-1][w-a[i]]);
	//		for(int j = 0; j < i; j++) {
	//			add_self(dp[i][w], dp[j][w-a[i]]);
	//		}
		}
		for(int i = 0; i < n; i++) {
			pre[i][w] = i > 0 ? pre[i-1][w] : 0;
			add_self(pre[i][w], dp[i][w]);
		}
	}

	int ans = 0;
	for(int i = 0; i < n; i++) {
		add_self(ans, mul(n - i, dp[i][s]));
	}

	cout << ans << endl;
}


Measured memory_bytes: 70656
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <map>
#include <set>
#include <stdlib.h>
#include <ctype.h>
#include <stack>
using namespace std;
#define ull unsigned long long
#define ll long long
const int maxn=1e5+5;
int pre[maxn];
ll num[maxn];
int findRoot(int u){
	if(u==pre[u]) return u;
	else return pre[u]=findRoot(pre[u]);
}
struct Edge{
	int u,v;
	Edge(int u,int v):u(u),v(v){}
};
vector<Edge> edges;
vector<ll> ans;
int n,m;
int main(void){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i){
		int u,v;scanf("%d%d",&u,&v);
		edges.push_back(Edge(u,v));
	}
	for(int i=1;i<=n;++i){
		pre[i]=i,num[i]=1;
	}
	ll last=n*(n-1)/2,cur;
	ans.push_back(last);
	for(int i=edges.size()-1;i>=0;--i){
		int x=findRoot(edges[i].u),y=findRoot(edges[i].v);
		if(x!=y){
			cur=last-num[x]*num[y];
			pre[x]=y,num[y]+=num[x];
		}
		else cur=last;
		ans.push_back(cur);last=cur;
	}
	ll b=ans[ans.size()-1];					
	for(int i=ans.size()-2;i>=0;--i)
		printf("%lld\n",ans[i]-b);
	return 0;
}

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

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

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

int main() {

	int n, m;
	cin >> n >> m;
	
	int L = -1e9;
	int R = 1e9;

	for (int i = 0; i < m; i++) {
		int l, r; 
		cin >> l >> r;
		L = max(L, l);
		R = min(R, r);
	}

	int ans = 0;

	if (L <= R) {
		ans = R - L + 1;
	}

	cout << ans << endl;
}


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

int main() {

	double W, H;
	double x, y;
	cin >> W >> H >> x >> y;

	double S = W * H / 2;
	int jdg = 0;
	if (x == W / 2.0 && y == H / 2.0) {
		jdg = 1;
	}

	cout << fixed;
	cout << setprecision(10) << S << " " << jdg << endl;

	return 0;
}



Measured memory_bytes: 256
# Problem https://atcoder.jp/contests/abc081/tasks/abc081_a
# Ruby 3rd Try
s1,s2,s3 = gets.chomp('\n').split('')
answer = 0
if s1 == '1'
    answer +=  1
end
if s2 == '1'
    answer += 1
end
if s3 == '1'
    answer += 1
end
puts(answer)

Measured memory_bytes: 1788
def abc_exp(a,b,c):
	print(str(a) + ' ' + str(b) + ' ' + str(c) )
	
def exchange(a,b,remain):
	while True:
		if remain >= 4 and a - 4 >= 0:
			b = b + 8
			a = a - 4
			remain = remain - 4
		else: 
			break
	return a,b
	

N,Y = map(int,input().split())

a = int(Y/10000)
b = int((Y - a * 10000)/5000)
c = int((Y - a * 10000 - b * 5000)/1000)

max_bills = int(Y/1000)

if (max_bills < N) or (N < a + b + c):
	print('-1 -1 -1')
	
elif (N == max_bills):
	print('0 0 ' + str(max_bills))
	
elif (N == a + b + c):
	abc_exp(a,b,c)

else:
	remain = N - a - b - c
	a = a - (remain % 4)
	b = b + 2 * (remain % 4)
	
	a , b = exchange(a,b,remain)
	remain = N - a - b - c
	if b - remain/4 >= 0:
		b = b - int(remain / 4)
		c = c + int(remain / 4) * 5
		abc_exp(a,b,c)
	
	else:
		print('-1 -1 -1')


Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
using namespace std;

char s[100010];

int main(void){
    scanf("%s", s);

    int ans = 0;
    for(int i = 0; s[i] != '\0'; i++){
        int s_ = (i%2)?'0':'1';
        if(s[i] == s_){
            ans++;
        }
    }

    printf("%d\n", min(ans, (int)strlen(s)-ans));
}


Measured memory_bytes: 888
// ※※※ 解答不能 ※※※
// https://img.atcoder.jp/keyence2020/editorial.pdf
#include <bits/stdc++.h>
using namespace std;
#define repex(i, a, b, c) for(int i = a; i < b; i += c)
#define repx(i, a, b) repex(i, a, b, 1)
#define rep(i, n) repx(i, 0, n)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define a first
#define b second
#define pb push_back

int main(){
    
    // 1. 入力情報.
    int N;
    scanf("%d", &N);
    vector<pair<int, int>> v;
    rep(i, N){
        int x, l;
        scanf("%d %d", &x, &l);
        v.pb({x + l, x - l});
    }
    
    // sort.
    sort(v.begin(), v.end());
    
    // 3. 残せるロボットの個数は？
    int ans = 0, cur = -1e10;
    rep(i, N){
        if(cur <= v[i].b) ans++, cur = v[i].a;
    }
    
    // 4. 出力.
    printf("%d\n", ans);
    return 0;
    
}

Measured memory_bytes: 1400
//https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_a
#include <bits/stdc++.h>
#if LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
template<class T>bool chmax(T &a, const T &b) {if (a<b) { a=b; return 1; } return 0;}
template<class T>bool chmin(T &a, const T &b) {if (b<a) { a=b; return 1; } return 0;}
int main() {
    ll N;
    cin>>N;
    ll ans=0;
    FOR(i,1,N+1){
        ll j=N-i;
        if(i==j)continue;
        if(i>j)break;
        ++ans;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
    int N;
    scanf("%d", &N);
    if(scanf("%d", &N) == EOF) exit(1);

    int i;
    char A[5];
    int AC,WA,TLE,RE;
    AC = 0;
    WA = 0;
    TLE = 0;
    RE = 0;

    for(i=0;i<N;i++){
        if(fgets(A, sizeof(A), stdin)==NULL){ exit(1);}

        if (strcmp(A, "AC\n") ==0){ AC++; }
        else if (strcmp(A, "WA\n") ==0){ WA++; }
        else if (strcmp(A, "TLE\n") ==0){ TLE++;}
        else {RE ++;}
    }

    printf("AC x %d\n",AC);
    printf("WA x %d\n",WA);
    printf("TLE x %d\n",TLE);
    printf("RE x %d\n",RE);
    return 0;
}

Measured memory_bytes: 1772
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

table = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = [table[i] for i in A]

# ちょうどi本のマッチ棒を使って、条件を満たす整数を作るときの最大桁数
INF = float('inf')
dp = [-INF] * (N + 1)
dp[0] = 0
cost = set(a)

for i in range(1, N + 1):
    for j in cost:
        if i - j >= 0 and dp[i] < dp[i - j] + 1:
            dp[i] = dp[i - j] + 1

answer = []
for i in A:
    x = table[i]
    while N - x >= 0 and dp[N] == dp[N - x] + 1:
        answer.append(i)
        N -= x

print(''.join(map(str, answer)))

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

using namespace std;

int main() {

	int n;
	cin >> n;

	vector<double> x(n, 0);
	vector<double> y(n, 0);

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

	double p1 = 0, p2 = 0, p3 = 0, pii = 0;;
	for (int i = 0; i < n; i++) {
		p1 += abs(x[i] - y[i]);
		p2 += (x[i] - y[i])*(x[i] - y[i]);
		p3 += (abs(x[i] - y[i]))*(abs(x[i] - y[i]))*(abs(x[i] - y[i]));
		pii = max(pii, abs(x[i] - y[i]));
	}

	cout << fixed << setprecision(9) << p1 << endl;
	cout << fixed << setprecision(9) << sqrt(p2) << endl;
	cout << fixed << setprecision(9) << pow(p3, (1 / (double)3)) << endl;
	cout << fixed << setprecision(9) << pii << endl;

}


Measured memory_bytes: 3472
import sys
import math

M=int(input())
ans=0
a=[list(map(int,input().split())) for i in range(M)]
b=[0 for i in range(M)]

for i in range(M):
    ans+=a[i][1]-1
    b[i]=a[i][0]*a[i][1]
    while b[i]>=10:
        ans+=b[i]//10
        b[i]=b[i]//10+b[i]%10


ans+=M-1
x=sum(b)
while x>=10:
    ans+=x//10
    x=x//10+x%10
print(int(ans))

Measured memory_bytes: 47148
#include <bits/stdc++.h>
using namespace std;
#define fin(ans) cout << ans << endl

int main(void) {
  long long int A, B, K;
  cin >> A >> B >> K;
  
  if (A <= K) {
    if (B >= K - A) {
      cout << "0 " << B - K + A << endl;
      return 0;
    } else {
      cout << "0 " << "0 " << endl;
      return 0;
    }
  } else {
    cout << A - K << " " << B << endl;
    return 0;
  }
  return 0;
}


Measured memory_bytes: 256
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

void pakuri_sort(int N, int A[]) {
	const int b = 8;
	int tmp[200001];
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}

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


	int N = getint(), M = getint();
	int A[100001];
	A[0] = 0;
	rep1(i, N) {
		int a = getint();
		A[i] = (A[i - 1] + a) % M;
	}
	pakuri_sort(N, A + 1);

	//数だけでええんか
	int mae = -1;
	int k = 0;
	ll kotae = 0;
	rep(i, N + 1) {
		if (mae != A[i]) k = 0;
		kotae += k++;
		mae = A[i];
	}
	printf("%lld", kotae);

	Would you please return 0;
}

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

int main(int argc, char const *argv[]) {
    string s;
    cin >> s;

    if (s == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (s == "Cloudy") {
        cout << "Rainy" << endl;
    } else {
        cout << "Sunny" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
using i64 = int64_t;
using f80 = __float80;
static const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
#define _overload3(_1,_2,_3,name,...) name
#define repi(i,start,end) for(i64 i=(start);i<(end);++i)
#define _rep(i,n) repi(i,0,n)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define rrep(i,start,end) for(i64 i=(start);i>end;--i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define v(T) vector<T>
#define vv(T) v(v(T))
typedef v(i64) vi;
typedef v(vi) vvi;
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;}
template<typename T> ostream &operator<<(ostream &os, const vector< T > &v){
  rep(i,v.size()) os << v[i] << (i + 1 != v.size() ? " " : "");
  return os;
}
template<typename T> istream &operator>>(istream &is, vector< T > &v){
  for(T &in : v) is >> in;
  return is;
}

void Main()
{
  i64 N, M, X;
  cin >> N >> M >> X;
  vi A(M);
  cin >> A;

  i64 l = 0, r = 0;
  for(auto &p : A){
    if(p < X) l++;
    else r++;
  }
  cout << min(l, r) << "\n";
}

int main()
{
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  Main();
}

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

std::vector<int> a[100000], b[100000], group;
int n, m, k, x, y, tmp, cnt, ans[100001], lbl[100001];
bool done[100001];
std::queue<int> idx;

void solve() {
    std::cin >> n >> m >> k;
    for (int i=0; i<m; ++i) {
        std::cin >> x >> y;
        a[x].push_back(y);
        a[y].push_back(x);
    }

    cnt = 0;
    for (int i=0; i<100001; ++i) {
        done[i] = 0;
        ans[i] = 0;
    }
    for (int i=1; i<n+1; ++i) {
        group.clear();
        if (done[i] == true)
            continue;
        done[i] = true;
        group.push_back(i);
        for (int p : a[i]) {
            idx.push(p);
            done[p] = true;
            group.push_back(p);
        }
        while (!idx.empty()) {
            tmp = idx.front();
            idx.pop();
            for (int p : a[tmp]) {
                if (done[p] == true)
                    continue;
                idx.push(p);
                done[p] = true;
                group.push_back(p);
            }
        }
        for (int s : group) {
            ans[s] = group.size();
            lbl[s] = cnt;
        }
        ++cnt;
    }

    for (int i=0; i<k; ++i) {
        std::cin >> x >> y;
        if (lbl[x] == lbl[y]) {
            b[x].push_back(y);
            b[y].push_back(x);
        }
    }

    for (int i=1; i<n+1; ++i)
        std::cout << ans[i] - a[i].size() - b[i].size() - 1 << " ";
    std::cout << std::endl;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    solve();
    return 0;
}


Measured memory_bytes: 15576
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var N = int.Parse(Console.ReadLine());

        var array = Console.ReadLine().Split(' ');
        var list = new List<int>();
        var ans = new List<int>();
        var boxItems = new int[N];
        foreach(var n in array)
        {
            list.Add(int.Parse(n));
        }

        for(var n = list.Count; n > 0; n--)
        {
            var itemNum = 0;
            var count = 2;
            var m = n;
            var finish = false;
            while (!finish)
            {
                if(m <= list.Count)
                {
                    if(boxItems[m - 1] == 1)
                    {
                        itemNum += 1;
                    }
                    m = n * count;
                    count++;
                }
                else
                {
                    finish = true;
                }
            }

            if (list[n - 1] == 0)
            {
                if (itemNum % 2 != 0)
                {
                    ans.Add(n);
                    boxItems[n - 1] = 1;
                }
            }
            else
            {
                if (itemNum % 2 == 0)
                {
                    ans.Add(n);
                    boxItems[n - 1] = 1;
                }
            }
        }
        Console.WriteLine(ans.Count);
        if(ans.Count > 0)
        {
            Console.WriteLine(string.Join(" ", ans)); 
        }
        Console.ReadLine();
    }

}



Measured memory_bytes: 36440
/*
 * Author : Andrew J
*/
#include <bits/stdc++.h>
using namespace std;
#define rall(x) x.rbegin() , x.rend()
#define all(x) x.begin() , x.end()
#define fi first
#define se second
#define pb push_back
using ll = long long;
using ii = pair <int , int>;
void in(int &x);
// const int N = ;
#define singleCase
// #define multipleCase
stack <char> stk;
string s;
int n;

void work() {
   cin >> s;
   n = s.length();
   int sol = 0;
   for (int i = 0 ; i < n ; i++) {
      if (stk.size()) {
         int cur = stk.top();
         if (cur == 'S' && s[i] == 'T') {
            stk.pop();
            continue;
         }
      }
      stk.push(s[i]);
   }
   printf("%lu\n" , stk.size());
   return;
}

int main() {
   #ifdef multipleCase
      int nQ; in(nQ);
      while (nQ--)
         work();
   #endif
   #ifdef singleCase
      work();
   #endif
   return 0;
}

void in(int &x) {
	bool neg = false;
	register int c;
	x = 0;
	c = getchar();
	if(c == '-') {
		neg = true;
		c = getchar();
	}
	for (; c > 47 && c < 58; c = getchar())
	  x = (x << 1) + (x << 3) + c - 48;
	if (neg) x *= -1;
}


Measured memory_bytes: 3788
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 
 using namespace std;
 
 int arr[10000+5];
 
 int main()
 {
   int n;
   while(cin>>n&&n)
   {
     for(int i=0;i<n;i++) cin>>arr[i];
     sort(arr,arr+n);
     long long int sum=0;
     long long int sum2=0;
     for(int i=0;i<n-1;i++)
     {
       sum2+=arr[i];
       sum+=sum2;        
     }
     cout<<sum<<endl;
   }
   //while(1);
   return 0;
 }

 

Measured memory_bytes: 3104
import java.util.*;

public class Main{
    
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int A = sc.nextInt();
        int B = sc.nextInt();
        sc.close();

        int sum = 0;
        for(int i = 1; i <= N; i++){
            if(keta(i)>=A && keta(i)<=B)
                sum += i;
        }
        System.out.println(sum);
   }

    static int keta(int n){
        int sum = 0;
        while(n != 0){
            sum += (n%10);
            n /= 10;
        }
        return sum;
    }
}

Measured memory_bytes: 21844
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#define rep(i,s,t) for(register int i=s;i<=t;++i)
#define _rep(i,s,t) for(register int i=s;i>=t;--i)
using namespace std;
const int mod=998244353;
typedef long long ll;
int n;
char s[41];
char A[41],B[41];
int b[41];
ll f[39][39],ans;
map<int,int>mp;
inline void deal(int S){
	int top=0,hh=0;
	rep(i,0,n-1)if(S>>i&1)A[++top]=s[i+1];
	_rep(i,n-1,0)if((~S)>>i&1)A[++top]=s[i+1];
	rep(i,1,n)B[i]=A[i];
	reverse(B+1,B+n+1);
	//puts(A+1);
	rep(i,1,n)hh=(hh*97ll+(A[i]-'a'+1))%mod;
	if(mp[hh])return;
	mp[hh]=1;
	//puts(B+1);
	memset(f,0,sizeof f);
	f[0][0]=1;
	rep(i,0,n+n-1)
		rep(j,0,min(i,n)){
			if(A[j+1]==s[i+1])
				f[j+1][i-j]+=f[j][i-j];
			if(B[i-j+1]==s[i+1])
				f[j][i-j+1]+=f[j][i-j];
		}
	ans+=f[n][n];
}
int main(){
	//freopen("string.in","r",stdin);
	//freopen("string.out","w",stdout);
	scanf("%d%s",&n,s+1);
	rep(i,0,(1<<n)-1)
		deal(i);
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 6400
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
typedef long long int lli;
const lli inf = 1e18;

lli bellmanford(int s, int g, vector<vector<pair<int, lli> > > &adj){
	int n = adj.size();
	vector<lli> mincost(n, inf);
	mincost[s] = 0;
	bool update = true;
	lli rem;
	for(int r=0; update; r++){
		if(r == n) rem = mincost[g];
		if(r == 2*n){
			if(rem != mincost[g]) return -1;
			break;
		}
		update = false;
		REP(i, n) REP(j, (int)adj[i].size()){
			int next = adj[i][j].first;
			lli ncost = mincost[i] + adj[i][j].second;
			if(ncost < mincost[next]){
				mincost[next] = ncost;
				update = true;
			}
		}
		if(!update) break;
	}
	return -mincost[g];
}

int main(){
	int n,m;
	cin >> n >> m;
	vector<vector<pair<int, lli> > > adj(n);
	REP(i, m){
		int a,b,c;
		cin >> a >> b >> c;
		a--; b--;
		adj[a].push_back(make_pair(b, -c));
	}
	lli ans = bellmanford(0, n-1, adj);
	if(ans == -1){
		cout << "inf" << endl;
	}else{
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 384
#include <cstdio>

int main(int argc, char const *argv[]) {
  int r,g,b;
  int n;
  scanf("%d %d %d\n", &r,&g,&b);
  n=100*r+10*g+b;
  if(n%4==0){
    printf("YES\n");
  }
  else{
    printf("NO\n");
  }
  return 0;
}


Measured memory_bytes: 128
target = 10 ** 9 + 7

N = int(input())

# 全ての整数のリスト作成
int_list = list(input().split())
int_list = [int(n) for n in int_list]

int_sum = sum(int_list)

sum_result = 0
for num in int_list:
    int_sum -= num
    sum_result += num * int_sum
print(sum_result % target)


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

using namespace std;
typedef long long ll;

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

    if( (n%(2*d+1))==0 ) cout << n/(2*d+1) << endl;
    else cout << n/(2*d+1) + 1<< endl;
    
    return 0;
}


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

int main() {
    int n;
    long long d;
    cin >> n >> d;
    int ans = 0;
    rep(i,n) {
        long long x, y;
        cin >> x >> y;
        if (x*x + y*y <= d*d) ans++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		HashSet<Integer> hs = new HashSet<Integer>();
		
		int n = Integer.parseInt(sc.next());
		int m = Integer.parseInt(sc.next());
		
		Unionfind un = new Unionfind(n+1);
		
		
		for(int i = 0 ;i < m ;i++) {
			int x = Integer.parseInt(sc.next());
			int y = Integer.parseInt(sc.next());
			int z = Integer.parseInt(sc.next());
			un.union(x, y);
		}
		
		for(int i = 1  ;i <= n ;i++) {
			if(!hs.contains(un.root(i))) {
				hs.add(un.root(i));
			}
		}
		
		int ans = hs.size();
		
		System.out.println(ans);

	}

}

class Unionfind {

	private int[] data;
	
	public Unionfind(int size) {
		this.data = new int [size];
		clear();
	}
	
	public void clear() {
		Arrays.fill(data, -1);
	}
	
	public void union(int x , int y ) {
		if((x = root(x)) != (y = root(y))) {
			if(data[y] < data[x]) {
				final int t = x;
				x = y;
				y = t;
			}
			data[x] += data[y];
			data[y] = x;
		}
	}
	
	public int root(int x) {
		if(data[x] < 0) {
			return x;
		}
		else {
			return data[x] = root(data[x]);
		}
	}
	
	public boolean same(int x, int y) {
		return root(x) == root(y);
	}
}



Measured memory_bytes: 63812
N,K,S=map(int,input().split())
A=[]
if S!=10**9:
  for i in range(K):
    A.append(S)
  for i in range(N-K):
    A.append(S+1)

  print(*A)
else:
  if N==1:
    A.append(10**9)
  else:
    for i in range(K):
      A.append(S)
    for i in range(N-K):
      A.append(S-1)
  
  print(*A)

Measured memory_bytes: 9692
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
signed main(){
  string s;
  cin >> s;
  ll aidx=-1,zidx;
  for(int i=0;i<s.size();i++){
    if(s[i]=='A'&&aidx==-1) aidx = i;
    if(s[i]=='Z')zidx = i;
  }
  cout << zidx-aidx+1;
  cout << endl;
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline

def main():
    s = input().strip()

    l = 0
    while l < len(s):
        if s[l] == "A":
            break
        l += 1
    r = len(s)-1
    while r >= 0:
        if s[r] == "Z":
            break
        r -= 1
    
    print(r-l+1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 3512
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

int INF = INT_MAX / 2;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

struct unko {
	int l, r; i_i mi;
	unko *lch, *rch;
	unko(int l, int r) : l(l), r(r) {
		if (r - l == 1) return;
		lch = new unko(l, (l + r) / 2);
		rch = new unko((l + r) / 2, r);
	}
	i_i get(int i, int j) {
		if (j <= l || r <= i) return i_i(INF, -1);
		if (i <= l && r <= j) return mi;
		return min(lch->get(i, j), rch->get(i, j));
	}
	void set(int i, int x) {
		if (i < l || r <= i) return;
		if (r - l == 1) {
			mi = i_i(x, i);
			return;
		}
		lch->set(i, x);
		rch->set(i, x);
		mi = min(lch->mi, rch->mi);
	}
};

int N, K, i = 0;
unko* z;
int ans[500001];

void f(int r, int x) {
	for (;;) {
		i_i p = z->get(0, r);
		if (p.first - x >= K) break;
		f(p.second, p.first);
	}
	z->set(r, INF);
	ans[x] = i++;
}

int main() {
	cin >> N >> K;
	z = new unko(0, N);
	for (int i = 0; i < N; i++) {
		int p; scanf("%d", &p); p--;
		z->set(p, i);
	}
	f(N, N);
	for (int i = 0; i < N; i++)
		printf("%d\n", ans[i] + 1);
}


Measured memory_bytes: 153984
#include<iostream>
#include<stdio.h>
using  namespace std;
int main () {
    int n;
    int V[101][101] = { 0 };
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int u, c;
        scanf("%d %d", &u, &c);
        for (int j = 0; j < c; j++) {
            int ux;
            scanf("%d", &ux);
            V[u][ux] = 1;
        }
    }
    
    for (int i = 1; i < n+1; i++) {
        for (int j = 1; j < n+1; j++) {
            if (j != n) {
                printf("%d ", V[i][j]);
            }
            else {
                printf("%d" , V[i][j]);
            }
        }
        printf("\n");
    }
    
    
    return 0;
}


Measured memory_bytes: 3260
def cr():
    #データの読み込み
    NK=input().split()

    n=int(NK[0])
    k=int(NK[1])


    x=list(map(int,input().split()))
    distance=[]

    for i in range(len(x)-1):
        distance.append(x[i+1]-x[i])

    distance.sort()

    if n>k:
        for i in range(k-1):
            distance.pop()

        sum=0
        for i in range(n-k):
            sum+=distance[i]

        print(sum)

    else:
        print(0)

S=int(input())


for i in range(S):
    cr()



Measured memory_bytes: 17168
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s1,s2,t,ans="~",s[51];cin>>s1>>t;
	int a=s1.size(),b=t.size(),c=0;
	int n=a-b;
	s2=s1;
	for(int i=n;i>=0;i--){
		bool flag=1;
		for(int j=0;j<b;j++){
			if(s1[i+j]!=t[j]&&s1[i+j]!='?'){
				flag=0;
				break;
			}
		}
		if(flag){
			for(int j=i;j<=i+b-1;j++)s1[j]=t[j-i];
			for(int j=0;j<a;j++){
				if(s1[j]=='?')s1[j]='a';
			}
			s[c]=s1;
			s1=s2;
			c++;
		}
	}
	for(int i=0;i<c;i++)ans=min(ans,s[i]);
	if(ans!="~")cout<<ans;
	else cout<<"UNRESTORABLE";
	return 0;
}

Measured memory_bytes: 3604
import java.io.*;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int t=1;//sc.nextInt();
		while(t-->0) {
			int n=sc.nextInt();
			int x=sc.nextInt();
			int T=sc.nextInt();
			int val=n/x+(n%x==0? 0:1);
			System.out.println(val*T);
		}

	}

}
/*class Reader{
	BufferedReader reader;
	Reader(){
		reader=new BufferedReader(new InputStreamReader(System.in));
	}
	int nextInt() throws IOException{
		String in=reader.readLine().trim();
		return Integer.parseInt(in);
	}
	long nextLong() throws IOException{
		String in=reader.readLine().trim();
		return Long.parseLong(in);
	}
	String next() throws IOException{
		return reader.readLine().trim();
	}
	String[] stringArray() throws IOException{
		return reader.readLine().trim().split("\\s+");
	}
	int[] intArray() throws IOException{
		String[] inp=this.stringArray();
		int[] arr=new int[inp.length];
		int i=0;
		for(String s:inp) {
			arr[i++]=Integer.parseInt(s);
		}
		return arr;
	}
}*/




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

using namespace std;

using ll = long long;

template<typename T>
map<T, int> prime_factor(T n) {
    map<T, int> res;
    for (T i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ++res[i];
            n /= i;
        }
    }
    if (n != 1) res[n] = 1;
    return res;
}

const ll MOD = 1000000007;

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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    cin >> n;
    vector<ll> a(n);
    vector< map<ll, int> > memo(n);
    map<ll, int> total;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        memo[i] = prime_factor(a[i]);
        for (auto& p : memo[i]) {
            total[p.first] = max(total[p.first], p.second);
        }
    }

    ll all_val = 1;
    for (auto& p : total) {
        (all_val *= modpow(p.first, p.second)) %= MOD;
    }

    ll ans = 0;
    for (int i = 0; i < n; ++i) {
        ll b = all_val;
        ll inv = 1;
        for (auto& p : memo[i]) {
            (inv *= modpow(p.first, total[p.first])) %= MOD;
            b = b * modpow(p.first, total[p.first] - p.second) % MOD;
        }
        (b *= modpow(inv, MOD - 2)) %= MOD;
        (ans += b) %= MOD;
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3968
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long int
#define pb push_back
#define fi first
#define se second
#define ld long double
#define vi vector<vector<ll> >
using namespace std;
const int MOD=1000000007;
const ll MAX=9187201950435737471;
const int N=1000006;
const ll INF=-1e12;
const double pi=acos(-1);



void solve(int T){
    int k;
    string s;
    cin>>k>>s;
    if(s.size()<=k)cout<<s;
    else {
        string ans="";
        for(int i=0;i<k;i++)cout<<s[i];
        cout<<"...";
    }
}

int main() {
    //fastio

    int T=1;
    //cin>>T;
    for(int i=1;i<=T;i++){
        solve(i);
    }
	return 0;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

ll waru(ll a, ll n) {
  return a % n;
}

ll gcd(ll a, ll b) {
  return (!a || !b) ? 0 : ((a % b == 0) ? b : gcd(b, a % b));
}

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

// ====================================================================

int main() {
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll bmade = (b / c + b / d - b / lcm(c, d));
  a--;
  ll amade = (a / c + a / d - a / lcm(c, d));
  cout << (b - a) - (bmade - amade) << endl;
}


Measured memory_bytes: 256
N = int(input())
P = list(map(float, input().split()))

ans = 0

DP = []
for _ in range(3000):
    DP.append([0] * 3000)
DP[0][0] = 1

for i in range(N):
    for j in range(i+1):
        DP[i+1][j] += DP[i][j] * (1-P[i])
        DP[i+1][j+1] += DP[i][j] * P[i]

ans = 0
i = N
while i > N//2:
    ans += DP[N][i]
    i -= 1

print(ans)


Measured memory_bytes: 253704
#import numpy as np
#from numpy import*
#from scipy.sparse.csgraph import shortest_path #shortest_path(csgraph=graph) # dijkstra# floyd_warshall
#from scipy.sparse import csr_matrix

from collections import* #defaultdict Counter deque appendleft
from fractions import gcd
from functools import* #reduce
from itertools import* #permutations("AB",repeat=2) combinations("AB",2) product("AB",2) groupby accumulate
from operator import mul,itemgetter
from bisect import* #bisect_left bisect_right
from heapq import* #heapify heappop heappushpop
from math import factorial,pi
from copy import deepcopy
import sys
sys.setrecursionlimit(10**8)
#input=sys.stdin.readline  #危険！基本オフにしろ！
def cmb(n, r):
    if n-r<0:
        return 0
    return factorial(n) // factorial(r) // factorial(n - r)

def main():
    n,W=map(int,input().split())
    d=defaultdict(int)
    d[0]=0
    for i in range(n):
        w,v=map(int,input().split())
        for k,j in d.copy().items():
            if k+w<=W:
                d[k+w]=max(d[k+w],j+v)
#    print(d)
    print(max(d.values()))
if __name__ == '__main__':
    main()

Measured memory_bytes: 5604
#include<bits/stdc++.h>
using namespace std;
int main()
{   char c[]={'3','5','7'};
	 int n;
	 cin>>n;
	 queue<string>q;
	 q.push("3");
	 q.push("5");
	 q.push("7");
	 int on=3,nn=0,ans=0,flag=0;
	  while(1)
    {
    	for(int i=1;i<=on;i++)
    	{
    		 string t=q.front();
    		 q.pop();
    		 for(int j=0;j<3;j++)
    		 {
    		 	string tt=t+c[j];
    		
    		 	int num3=0,num5=0,num7=0;
    		 	for(int k=0;k<tt.length();k++)
    		 	{
    		 		if(tt[k]=='3')num3++;
    		 		else if(tt[k]=='5')num5++;
    		 		else if(tt[k]=='7')num7++;
    		 		
				 }
				 
    		 	stringstream ss;
    		 	int x;
    		 	ss<<tt;
    		 	ss>>x;
    		 	q.push(tt);
    		 	nn++;
    		 	if(x<=n){
    		 		if((num3&&num5&&num7))
    		 		ans++;
				 }
				 else
				 {
				 	flag=1;
				 	break;
				 }
			 }
			 if(flag)break;
		}
		if(flag)break;
		on=nn;
		nn=0;
	}
	printf("%d",ans);
 } 

Measured memory_bytes: 4316
def countZeros(n)
  array = Array.new
  n.to_s.each_byte{|c| array << c - 48}
  numZero = 0
  array.reverse.each{|i|
    break if i != 0
    numZero += 1
  }
  return numZero 
end

loop do
  n = $stdin.gets.to_i
  break if n == 0
  sum = 1
  n.times{|i| sum = sum * (i + 1) }
  puts countZeros(sum)
end

Measured memory_bytes: 10224