akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
const int mod=998244353;
const int INF=0x3f3f3f3f;
ll quick(ll a,ll b)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
			ret=ret*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ret;
}
ll inv(ll a){return quick(a,mod-2);}
const int maxn=5e5+7;
void getfail(char *t,int *fail)
{
    int len = strlen(t);
    int j = 0, k = fail[0] = -1;
    while (j < len)
    {
        while (k != -1 && t[j] != t[k])
            k = fail[k];
        fail[++j] = ++k;
    }
}
bool isloop(int *fail,int i)
{
	return fail[i]*2>=i&&i%(i-fail[i])==0;
}
char t2[maxn];
char t[maxn];
int fail[maxn];
int f2[maxn];
int main()
{
	scanf("%s",t);
	getfail(t,fail);
	int len=strlen(t);
	if(!isloop(fail,len))
		puts("1\n1");
	else if(len-fail[len]==1)
		printf("%d\n%d\n",len,1);
	else{
		int ans=0;
		for(int i=0;i<len;i++)
			t2[i]=t[len-1-i];
		t2[len]='\0';
		getfail(t2,f2);
		for(int i=1;i<len;i++)
		{
			if(!isloop(fail,i)&&!isloop(f2,len-i))
				 ans++;
		}
		printf("%d\n%d\n",2,ans);
	}

}


Measured memory_bytes: 5120
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define in(a)                       ll a; cin>>a;
#define in2(a,b)                    ll a,b; cin>>a>>b;
#define in3(a,b,c)                  ll a,b,c; cin>>a>>b>>c;
#define in4(a,b,c,d)                ll a,b,c,d; cin>>a>>b>>c>>d;
#define in5(a,b,c,d,e)              ll a,b,c,d,e; cin>>a>>b>>c>>d>>e;
#define lelo(b)                     for(auto &i:b)cin>>i;
#define ff                          first
#define ss                          second
#define call(v)                     v.begin(),v.end()
#define rall(v)                     v.rbegin(),v.rend()
#define show(x)                     for(auto t:x)cout<<t<<" ";
#define pb                          push_back
#define bhar(s,v)                   memset(s,v,sizeof(s))
#define endl                        "\n"                       
#define ce(x)                       cout<<x<<"\n";
#define nl                          cout<<endl;
#define jaldi                       ios_base::sync_with_stdio(false);cin.tie(NULL);
#define dekh_lo                     ce("dekh_lo");
#define sz(x)                       (ll)x.size()
#define re                          return

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> vi;

const ll mod=1e9+7;
const ll N=4e5+5;

/*


*/

void solve(){
	in(n);
	vi a(n); lelo(a);
	vi dp(n+1,0);
	for(ll i=0;i<n;i++){
		dp[i+1]=(dp[i]+a[i])%mod;
	}
	ll ans=0;
	for(ll i=0;i<n;i++){
		ll sum=(dp[n]-dp[i+1]+mod)%mod;
		sum=(sum*a[i])%mod;
		ans=(ans+sum)%mod;
	}
	ce(ans%mod);
}

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

/*


*/

  

Measured memory_bytes: 6420
//#include<bits\stdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 2000000000
#define inf 10000000000000000ll
#define ldb long double
#define pb push_back
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE ll i=p;i<=n;++i)
#define go(x) for(ll i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE ll i=n;i>=p;--i)
#define pii pair<ll,ll> 
#define mk make_pair
#define RE register
#define P 1000000007
#define S second
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ull unsigned long long
#define S second
#define F first
#define l(p) t[p].l
#define r(p) t[p].r
#define sum(p) t[p].sum
#define tag(p) t[p].tag
#define zz p<<1
#define yy p<<1|1
#define mod 1000000007
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
{
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
}
inline ll read()
{
    RE ll x=0,f=1;char ch=getc();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();}
    return x*f;
}
const ll MAXN=100010;
ll n;
ll s1,s2,s3,ans;
char a[MAXN];
signed main()
{
	//freopen("1.in","r",stdin);
	gt(n);gc(a);
	rep(1,n,i)
	{
		if(a[i]=='R')++s1;
		if(a[i]=='G')++s2;
		if(a[i]=='B')++s3;
	}
	ans=s1*s2*s3;
	for(ll i=1;i<=n;++i)
	{
		for(ll j=i+1;j<=n;++j)
		{
			if(a[i]==a[j])continue;
			ll k=j-i+j;
			if(k>n)continue;
			if(a[i]==a[k]||a[j]==a[k])continue;
			--ans;
		}
	}
	putl(ans);
	return 0;
}


Measured memory_bytes: 3824
#include <iostream>
using namespace std;
int main()
{
    int A,B;
    cin >> A >> B;
    if(A>=1&&A<=13&&B>=1&&B<=13)
    {
    if(A==1||B==1)
    {
        if(A==1&&B>1) cout << "Alice";
        else if(A>1&&B==1) cout << "Bob";
        else cout << "Draw";
    }
    else if(A>B) cout << "Alice";
    else if (A<B) cout << "Bob";
    else cout << "Draw";
    return 0;
    }
    else return 0;
}

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

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

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <utility>
#include <vector>
#include <algorithm>
#define llint long long 
#define mod 1000000007

using namespace std;
typedef pair<llint, llint> P;

llint n;
llint a[100005];
llint p[100005];
llint l, r;

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	make_fact();
	
	cin >> n;
	for(int i = 1; i <= n+1; i++) cin >> a[i];
	for(int i = 1; i <= n+1; i++){
		if(p[a[i]]){
			l = p[a[i]], r = i;
			break;
		}
		p[a[i]] = i;
	}
	
	for(int i = 1; i <= n+1; i++){
		llint ans = comb(n+1, i);
		if(n-r+l >= i-1) ans += mod - comb(n-r+l, i-1), ans %= mod;
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define rREP(i,m,n) for(ll i = (m); i >= (n); i--)
#define ALL(c) (c).begin(), (c).end()
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout<<endl;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    bool flag = true;
    int n, m;
    cin >> n >> m;
    int ary[n];
    rep(i,n) ary[i]=-1;
    rep(i,m)
    {
        int s,c;
        cin >> s >> c;
        s--;
        if (s>=n)
        {
            flag = false;
            break;
        }

        if (ary[s]!=-1 && ary[s]!=c)
        {
            flag = false;
            break;
        }
        ary[s] = c;
    }
    if (n!=1 && ary[0]==0)
    {
        flag = false;
    }
    rep(i,n) if (ary[i]==-1) ary[i]=0;
    if (n!=1 && ary[0]==0) ary[0] = 1;

    if (flag)
    {
        rep(i,n)
        {
            cout << ary[i];
                /* code */
        } 
        cout << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    
    
}




Measured memory_bytes: 384
#!venv/bin/python
 
import math
import numpy as np
import random
import copy
import statistics 
import bisect
import heapq
from collections import defaultdict 
import time
import sys
from pprint import pprint


N, K = [ int(x) for x in input().split() ]

if K==1:
    print(0)
else:
    print(N-K)


Measured memory_bytes: 24852
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define rep(i, a, b) for (int (i) = (a); (i) <= (b); (i)++)
#define per(i, a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, sum) memset(a, sum, sizeof(a))
#define lowbit(x) (x & -x)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define enter cout << endl
#define siz(x) ((int)x.size())
typedef long long ll ;
typedef unsigned long long ull ;
typedef vector <int> vi ;
typedef pair <int, int> pii ;
typedef map <int, int> mii ;
typedef map <string, int> msi ;
const int N = 100010 ;
const int INF = 0x3f3f3f3f ;
const int iinf = 1 << 30 ;
const ll linf = 1e15 ;
const int MOD = 1000000007 ;
void print(int x) { cout << x << endl ; exit(0) ; }
void PRINT(string x) { cout << x << endl ; exit(0) ; }
void douout(double x){ printf("%lf\n", x + 0.0000000001) ; }

int n ;
ll W, c ;
ll w[N], v[N], dp[N] ;

signed main(){
	scanf("%d%lld", &n, &W) ;
	for (int i = 1; i <= n; i++) scanf("%lld%lld", &w[i], &v[i]) ; // weight ans value
	for (int i = 1; i <= n; i++) c += v[i] ;
	for (int i = 0; i <= c; i++) dp[i] = linf ;
	dp[0] = 0 ;
	for (int i = 1; i <= n; i++)
	for (int j = c; j >= v[i]; j--)
	dp[j] = min(dp[j], dp[j - v[i]] + w[i]) ;
	for (ll i = c; i >= 0; i--)
	if (dp[i] <= W) {
		printf("%lld\n", i) ;
		break ;
	}
	return 0 ;
}

/*
写代码时请注意：
	1.ll？数组大小，边界？数据范围？
	2.精度？
	3.特判？
	4.至少做一些
思考提醒：
	1.最大值最小->二分？
	2.可以贪心么？不行dp可以么
	3.可以优化么
	4.维护区间用什么数据结构？
	5.统计方案是用dp？模了么？
*/


Measured memory_bytes: 1024
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

public class Main {
	
	Scanner sc = new Scanner(System.in);
	public void run() {
		while(sc.hasNext()){
			int n = sc.nextInt();
			int m = sc.nextInt();
			if(n == 0 && m == 0) break;
			calc(n, m);
		}
	}
	public void calc(int n, int m){
		int[] list = new int[11];
		for(int i = 0; i < n; i++){
			int d = sc.nextInt();
			int p = sc.nextInt();
			list[p] = list[p] + d;
		}
		for(int i = 10; i > 0; i--){
			if(m == 0) break;
			else if(list[i] <= m){
				m = m - list[i];
				list[i] = 0;
			}
			else{
				list[i] = list[i] - m;
				break;
			}
		}
		int sum = 0;
		for(int i = 0; i < 11; i++){
			sum = sum + list[i] * i;
		}
		System.out.println(sum);
	}

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

Measured memory_bytes: 65324
#include <cstdio>
#define bi(x) (1<<x-1)
#define ll long long
#define rep(i,j,k) for (i=j;i<=k;i++)
using namespace std;
const int N=15,mod=1e9+7;
int f[1<<N],e[N+5],w[N+2][1<<N],g[N+2][1<<N];
int n,m,i,j,k,x,p,u,v,sn,s,ans,ok[1<<N];
int main()
{
//	freopen("dag.in","r",stdin);
//	freopen("dag.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,1,m)
	{
		scanf("%d%d",&u,&v);
		e[u]|=bi(v);
	}
	sn=(1<<n)-1;
	rep(i,1,n)
	{
		w[i][0]=g[i][0]=1;
		rep(j,1,sn)
		{
			p=j&-j;
			if (!(e[i]&p)) w[i][j]=w[i][j^p];
			else w[i][j]=w[i][j^p]<<1;
			g[i][j]=w[i][j]-1;
		}
	}
	f[0]=1;
	rep(i,0,sn) if (!(i&1)==!(i&2)) ok[i]=1;
	rep(i,1,sn)
	if (ok[i])
	{
		for (j=i;j;j=j-1&i)
			if (ok[j])
			{
				k=i^j;
				s=f[k];
				rep(x,1,n)
					if (k&bi(x))
						s=(ll)s*g[x][j]%mod;
				rep(x,1,n)
					if (j&bi(x))
						s=(ll)s*w[x][k]%mod;
				f[i]=(f[i]+s)%mod;
			}
	}
	ans=1;
	rep(i,1,m) ans=(ll)ans*2%mod;
	printf("%d\n",(ans+mod-f[sn])%mod);
	return 0;
}

Measured memory_bytes: 4480
m,k=map(int,input().split())
if pow(2,m) <= k:
	print(-1)
	exit()

if m==0:
	if k==0:
		print(0,0)
	else:
		print(-1)
	exit()

if m==1:
	if k==0:
		print(0,0,1,1)
	else:
		print(-1)
	exit()
b=[]
c=[]
for i in range(pow(2,m)):
	if i!=k:
		b.append(i)
	if pow(2,m)-1-i!=k:
		c.append(pow(2,m)-1-i)

ans = " ".join([str(x) for x in b])
ans += " "
ans+=str(k)
ans += " "
ans += " ".join([str(x) for x in c])
ans += " "
ans+=str(k)

print(ans)

Measured memory_bytes: 93284
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int days = sc.nextInt();
		int cnt = sc.nextInt();

		int needDays = 0;

		for(int i = 0; i < cnt; i++) {
			needDays += sc.nextInt();
		}

		if(days < needDays) {
			System.out.println(-1);
		} else {
			System.out.println(days - needDays);
		}
	}
}

Measured memory_bytes: 46532
#include<iostream>
using namespace std;
int main(){
int n;
int samp[10000];
cin>>n;
for(int i=0;i<n;i++){
cin>>samp[i];
}

int pri[10000+1]={};
int i=2;
while(i<=10000){
if(pri[i]==0){
if(10000/i>=2){
for(int j=2;j<=10000/i;j++){
pri[j*i]=1;
}
}
}
i++;
}
int sum=0;
int sampflag[10000]={};
for(int j=2;j<=10000;j++){
if(pri[j]==0){
for(int k=0;k<n;k++){
if(samp[k]%j==0 && samp[k]/j>1)sampflag[k]=1;
}
}

}
for(int j=0;j<n;j++){
sum+=sampflag[j];
}
cout<<n-sum<<endl;
}



Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll; typedef long double ld;
const int INF32 = 1e9+10;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, K; cin >> N >> K;
  ll x[100010];
  for (int i = 0; i < N; i++) {
    cin >> x[i];
  }
  ll ans = INF32;
  /*for (int i = 0; i < N-(K-1); i++) {
    ll t;
    if (x[i+(K-1)] < 0)
      t = abs(x[i]);
    else if (x[i] >= 0)
      t = x[i+(K-1)];
    else {
      t = min(abs(x[i]), x[i+(K-1)])*2 + max(abs(x[i]), x[i+(K-1)]);
    }
    c = min(c, t);
  }
  cout << c << endl;*/
  for (int i = 0; i < N-(K-1); i++) {
    ll l = i; ll r = i+K-1;
    ll cost = min(abs(x[l]),abs(x[r]))+abs(x[r]-x[l]);
    //cout << cost << '\n';
    ans = min(ans, cost);
  }
  cout << ans << '\n';
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <complex>
#include <cctype>
#include <cassert>
#include <sstream>
#include <ctime>

using namespace std;

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

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> P;

const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS  = 1e-10;

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	
	if (b - a == c - b) puts("YES");
	else puts("NO");
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[200007],sum=0,cur=0,ans=1e16;
int main(){
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<n;i++){
        cur+=a[i];
        ans=min(ans,abs(sum-cur*2));
    }
    cout<<ans;
}


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

#define pb push_back
#define int long long
#define sz size()

using namespace std;

const int N = 1e5 + 1;
const int inf = 1e9 + 7;

int n, w, mx;
int a[1000], b[1000], ans[N];

bool dp[N * 2];

main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>> n>> w;
    dp[0] = 1;
    for(int  i = 1; i <= n; i++){
        cin>> a[i]>> b[i];
        for(int j = N; j >= 0; j--){
            if(dp[j] == 1){
                if(dp[j + b[i]] == 0)ans[j + b[i]] = inf;
                dp[j + b[i]] = 1;
                ans[j + b[i]] = min(ans[j + b[i]], ans[j] + a[i]);
                if(ans[j + b[i]] <= w)mx = max(mx, j + b[i]);
            }
        }
    }
    cout<< mx;
}


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

int main () {
    int W1, W2 = 0, H1, H2 = 0, N;
    cin >> W1 >> H1 >> N;
    vector<int> x(N), y(N), a(N);
    for (int i = 0; i < N; i++) {
        cin >> x.at(i) >> y.at(i) >> a.at(i);
    }

    for (int i = 0; i < N; i++) {
        if (a.at(i) == 1) {
            W2 = max(x.at(i), W2);
        }
        else if (a.at(i) == 2) {
            W1 = min(x.at(i), W1);
        }
        else if (a.at(i) == 3) {
            H2 = max(y.at(i), H2);
        }
        else if (a.at(i) == 4) {
            H1 = min(y.at(i), H1);
        }
    }
    cout << max(0, W1 - W2) * max(0, H1- H2) << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define LL long long
#define REP(i,n) for(int i=0;i<(n);++i)
#define PER(i,n) for(int i=n-1;i>=0;--i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define foreach(i, n) for(auto &i:(n))
#define PII pair<int,int>
#define PLI pair<long long, int>
#define PLL pair<long long, long long>
#define MOD ((LL)1e9+7) 
#define INF ((LL)1e9+7)
#define INFLL ((LL)1e18)
#define ALL(x) (x).begin(),(x).end()
#define BIT(x) (1LL << (x))
using namespace std;
template<class t, class u> bool chmax(t &a, u b){if(a<b){a=b;return true;}return false;}
template<class t, class u> bool chmin(t &a, u b){if(a>b){a=b;return true;}return false;}

LL modpow(LL x, LL b){
	LL res = 1;
	while(b){
		if(b&1)res = res * x % MOD;
		x = x * x % MOD;
		b>>=1;
	}
	return res;
}

LL modinv(LL x){
	return modpow(x, MOD-2);
}

int main(){
	int N;
	cin >> N;
	vector<vector<int>> vs(N, vector<int>(N-1));
	vector<int> pos(N, 0);
	foreach(i, vs){
		foreach(j, i){
			cin >> j;
			--j;
		}
	}
	int ans = 0;
	auto check = [&](){
		foreach(i, pos)if(i!=N-1)return false;
		return true;
	};

	int sum = 0;
	vector<int> next;
	REP(i, N)next.push_back(i);

	while(sum < N * (N-1)){
		++ans;
		vector<bool> used(N, false);
		vector<int> nnext;
		bool flag = false;
		foreach(i, next){
			if(pos[i]==N-1)continue;
			if(used[i])continue;
			int d = vs[i][pos[i]];
			if(pos[d]==N-1)continue;
			if(used[d])continue;
			if(i == vs[d][pos[d]]){
				nnext.push_back(i);
				nnext.push_back(d);
				used[i] = used[d] = true;
				++pos[i];
				++pos[d];
				flag = true;
				sum += 2;
			}
		}
		if(!flag){
			cout << -1 << endl;
			return 0;
		}
		next = nnext;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 4224
#include<iostream>
#include<string>
#include<sstream>
#include<cctype>
#include<cstdlib>
#include<map>
using namespace std;
#define REP(i, j) for(int i = 0; i < j; i++)

map<char, int> alpha_to_num;
map<int, char> num_to_alpha;

int solve(string s){
    int ret = 0;
    REP(i, s.length()){
        if(isdigit(s[i])) continue;
        if(i == 0 || isalpha(s[i - 1])) ret += alpha_to_num[s[i]];
        else ret += (alpha_to_num[s[i]] * (s[i - 1] - '0'));
    }
    return ret;
}

void disp(int n){
    stringstream ss;
    for(int i = 1000; i > 0; i /= 10){
        int now = n / i;
        if(now == 0) continue;

        if(now == 1) ss <<num_to_alpha[i];
        else ss <<now <<num_to_alpha[i];
        n -= (now * i);
    }
    cout <<ss.str() <<endl;
}

int main(){
    alpha_to_num['m'] = 1000;
    alpha_to_num['c'] = 100;
    alpha_to_num['x'] = 10;
    alpha_to_num['i'] = 1;
    num_to_alpha[1000] = 'm';
    num_to_alpha[100] = 'c';
    num_to_alpha[10] = 'x';
    num_to_alpha[1] = 'i';
    int n; cin >>n;
    REP(z, n){
        string a, b; cin >>a >>b;
        disp(solve(a) + solve(b));
    }
    return 0;
}

Measured memory_bytes: 1224
#define DEBUG 1

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <complex>
#include <tuple>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <functional>
#include <random>
#include <chrono>
#include <cctype>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
using namespace std;
#define maxs(x, y) (x = max(x, y))
#define mins(x, y) (x = min(x, y))
using ll = long long;
class mint
{
public:
  static ll MOD;
  ll x;
  mint() : x(0) {}
  mint(ll x) : x(x % MOD) {}
  mint operator-() const { return x ? MOD - x : 0; }
  mint &operator+=(const mint &a)
  {
    if ((x += a.x) >= MOD)
    {
      x -= MOD;
    }
    return *this;
  }
  mint &operator-=(const mint &a) { return *this += -a; }
  mint &operator*=(const mint &a)
  {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint &operator/=(const mint &a)
  {
    mint b{a};
    return *this *= b.power(MOD - 2);
  }
  mint operator+(const mint &a) const { return mint(*this) += a; }
  mint operator-(const mint &a) const { return mint(*this) -= a; }
  mint operator*(const mint &a) const { return mint(*this) *= a; }
  mint operator/(const mint &a) const { return mint(*this) /= a; }
  bool operator<(const mint &a) const { return x < a.x; }
  bool operator==(const mint &a) const { return x == a.x; }
  const mint power(ll N)
  {
    if (N == 0)
    {
      return 1;
    }
    else if (N % 2 == 1)
    {
      return *this * power(N - 1);
    }
    else
    {
      mint half = power(N / 2);
      return half * half;
    }
  }
};
ll mint::MOD = 1e9 + 7;
istream &operator>>(istream &stream, mint &a) { return stream >> a.x; }
ostream &operator<<(ostream &stream, const mint &a) { return stream << a.x; }
class combination
{
public:
  vector<mint> inv, fact, factinv;
  static int MAX_SIZE;
  combination() : inv(MAX_SIZE), fact(MAX_SIZE), factinv(MAX_SIZE)
  {
    inv[1] = 1;
    for (auto i = 2; i < MAX_SIZE; i++)
    {
      inv[i] = (-inv[mint::MOD % i]) * (mint::MOD / i);
    }
    fact[0] = factinv[0] = 1;
    for (auto i = 1; i < MAX_SIZE; i++)
    {
      fact[i] = mint(i) * fact[i - 1];
      factinv[i] = inv[i] * factinv[i - 1];
    }
  }
  mint operator()(int n, int k)
  {
    if (n >= 0 && k >= 0 && n - k >= 0)
    {
      return fact[n] * factinv[k] * factinv[n - k];
    }
    return 0;
  }
};
int combination::MAX_SIZE = 1e6 + 10;
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
// constexpr double epsilon = 1e-10;
// constexpr ll infty = 1000000000000000LL;
// constexpr int dx[4] = {1, 0, -1, 0};
// constexpr int dy[4] = {0, 1, 0, -1};
void Yes()
{
  cout << "Yes" << endl;
  exit(0);
}
void No()
{
  cout << "No" << endl;
  exit(0);
}

int main()
{
  int N;
  cin >> N;
  vector<int> A(N);
  for (auto i = 0; i < N; i++)
  {
    cin >> A[i];
  }
  deque<int> D;
  for (auto i = 0; i < N; i++)
  {
    int p = lower_bound(D.begin(), D.end(), A[i]) - D.begin();
    if (p == 0)
    {
      D.push_front(A[i]);
    }
    else
    {
      D[p - 1] = A[i];
    }
  }
  cout << D.size() << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using namespace std;
 
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileio freopen("in.in", "r", stdin),freopen("out.out", "w", stdout);
#define ll long long int
#define FF first
#define SS second
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d\n",x)
#define plld(x) printf("%lld\n",x)
#define pss printf
#define MOD 1000000007
#define INF 1e18
#define eps 0.00001
#define endl '\n'
#define debug(n1) cout<<n1<<endl
string s;
 
int main() {
cin>>s;
bool y=0;
for(int i=0;i<s.length()-1;i++)
{
	if(s[i]=='A'&&s[i+1]=='C')y=1;
}
if(y)
	pss("Yes\n");
else
	pss("No\n");



	return 0;
           } 

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<string>

using namespace std;

int main(void) {
	string s;

	cin >> s;

	int num = 0;

	int half = (s.size() + 1) / 2;

	for (int i = half-1; i >= 0; i--)
	{

		//printf("half=%d,i=%d\n", half, i);
		if (equal(s.begin(), s.begin() + i, s.begin()+i, s.begin() + (2*i))) {
			num = i * 2;
			break;
		}
	}

	cout << num << "\n";

	

	return 0;
}

Measured memory_bytes: 256
#![allow(unused_imports)]

//input
use proconio::input;
use proconio::marker::{Bytes, Chars};
//use std::io::Read;

//collections
//use std::collections::BTreeMap;
//use std::collections::BTreeSet;
//use std::collections::HashMap;
//use std::collections::HashSet;
//use std::collections::VecDeque;
//use std::collections::BinaryHeap;

//use std::cmp::*;

fn main() {
    input! {
        a: char,
    }

    //tabで移動
    if a.is_lowercase() {
        println!("a");
    } else {
        println!("A");
    }
}


Measured memory_bytes: 2060
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define int long long
using namespace std;
int f(int k) {
	int r = 0;
	for (int i = k - (k % 4); i <= k; i++) r = r ^ i;
	return r;
}
signed main() {
	int a, b; cin >> a >> b;
	int c = f(b) ^ f(a - 1);
	cout << c << endl;
}

Measured memory_bytes: 256
import itertools

N = int(input())
City = [list(map(int,input().split())) for i in range(N)]

Permutations = (list(itertools.permutations(City)))

def route(l):
    Ans=[]
    for i in range(len(l)-1):
        L = ((l[i+1][0]-l[i][0])**2+(l[i+1][1]-l[i][1])**2)**.5
        Ans.append(L)
    return sum(Ans)

Length_list=[]

for i in Permutations:
    Length_list.append(route(i))



print(sum(Length_list)/len(Length_list))

Measured memory_bytes: 10228
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
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 int inf = 1001001001;

int main() {
    int n,k;
    cin >> n >> k;
    vector<int> v(n);
    rep(i,n) cin >> v[i];
    int ans = 0;
    rep(i,min(k,n)+1) {
        int rem = k-i;
        rep(le,i+1) {
            int ri = i-le;
            vector<int> pick;
            rep(j,le) {
                pick.pb(v[j]);
            }
            rep(j,ri) {
                pick.pb(v[n-1-j]);
            }
            sort(all(pick));
            int sum = 0;
            for(int j : pick) sum += j;
            int now = 0;
            rep(j,rem) {
                if(now >= pick.size()) break;
                if(pick[now] < 0) {
                    sum -= pick[now];
                    now++;
                } else break;
            }
            chmax(ans,sum);
        }
    }
    cout << ans << endl;
}

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

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)

using ll = long long;
using ld = long double;
ll INF = LLONG_MAX;

using vi = vector<int>;
using vll = vector<ll>;
using pii = pair<int, int>;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.first,", ",x.second,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void print() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void print(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); print(ts...); 
	}
}

using namespace output;

int main() {
    // ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int N, K; cin >> N >> K;
	vi arr (N);
	F0R(i, N) cin >> arr[i];

	vi temp (N);
	set<pii> cover;

	F0R(i, K) {
		vi old = arr;
		// one op
		priority_queue<pii> cover;
		R0F(j, N) {
			cover.push({j - arr[j], j});
			while (cover.size() > 0 && cover.top() > (pii) {j, N}) cover.pop();
			temp[j] = cover.size();
		}
		priority_queue<pii, vector<pii>, greater<pii>> other;
		F0R(j, N) {
			while (other.size() > 0 && other.top() < (pii) {j, 0}) other.pop();
			int ilum = other.size() + temp[j];
			other.push({j + arr[j], j});
			arr[j] = ilum;
		}
		bool done = true;
		for (int x : arr) if (x != N) done = false;
		if (done) break;
	}
	for (int x : arr) cout << x << " ";
	cout << endl;
}

Measured memory_bytes: 10804
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;

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

    if((S[0]==S[1])&&(S[1]==S[2])&&(S[2]==S[3])){
        cout << "No" << endl;
        return 0;
    }

    if (S[0] != S[1])
    {
        if (((S[0] == S[2]) && (S[1] == S[3])) || ((S[0] == S[3]) && (S[1] == S[2])))
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }
    else
    {
        if (S[2] == S[3])
        {
            cout << "Yes" << endl;
        }
        else
        {
            cout << "No" << endl;
        }
    }

    return 0;
}

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

using namespace std;

int p[10000];
int r[10000];

int findSet(int x) {
	int y = x;
	while (y != p[y]) {
		y = p[y];
	}
	while (x != p[x]) {
		int temp = p[x];
		p[x] = y;
		x = temp;
	}
	return y;
}

bool same(int x, int y) {
	return findSet(x) == findSet(y);
}

void link(int x, int y) {
	if (r[x] > r[y]) {
		p[y] = x;
		return;
	}
	if (r[x] < r[y]) {
		p[x] = y;
		return;
	}
	p[y] = x;
	r[x]++;
}

void unite(int x, int y) {
	link(findSet(x), findSet(y));
}




int main() {
	int n, q;
	int com;
	int x, y;

	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		p[i] = i;
		r[i] = 0;
	}

	for (int i = 0; i < q; i++) {
		cin >> com >> x >> y;
		if (com == 0) {
			unite(x, y);
			continue;
		}
		if (com == 1) {
			cout << (same(x, y) ? 1 : 0) << endl;
			continue;
		}
	}

	return 0;
}

Measured memory_bytes: 1236
/*
*/
#include<iostream>
#include<queue>
using namespace std;

int main()
{
  int A,B,C;
  cin >> A >> B >> C;
  string ans = "No";
  if (A == B && B == C) {
  }
  else if (A == B || B == C || A ==C) {
    ans = "Yes";
  }
  cout << ans;

  return 0;

}

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

using namespace std;

int main(){
	string s;
	int k;
	cin>>s>>k;
	priority_queue<char, vector<char>, greater<char>> head;
	map<char,bool> check;

	for(auto a:s){
		if(!check.count(a)){
			check[a]=true;
			head.push(a);
		}
	}

	set<string> hoge;

	for(int i=0;!head.empty() && i<5;i++){
		char H=head.top();
		head.pop();

		for(int j=0;j<s.size();j++){
			if(s.at(j)==H){
				for(int k=j;k<s.size() && k-j<5;k++){
					string sub=s.substr(j,k-j+1);
					hoge.insert(sub);
				}
			}
		}

		if(hoge.size()>=5) break;
	}

	auto it=hoge.begin();

	for(int i=1;i<k;i++) it++;

	cout<<*it<<endl;

	return 0;
}


Measured memory_bytes: 256
def selectionSort(A, N):
    cnt = 0
    for i in range(N):
        minj = i
        for j in range(i, N):
            if A[j] < A[minj]:
                minj = j
        if i != minj:
           cnt += 1
           tmp = A[i]
           A[i] = A[minj]
           A[minj] = tmp
    print(*A)
    print(cnt)
    
n = int(input())
a = list(map(int, input().split()))

selectionSort(a, n)


Measured memory_bytes: 5604
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,n1,n2) for(int i=n1;i<n2;i++)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef pair<int,int> Pi;
typedef long long int ll;
const int INF=(ll)(1<<30)-1;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)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 dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};

template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int n;
vector<bool> s;

int main(){
	cin>>n;
	string t1,t2;
	cin>>t1;
	cin>>t2;
	int k=0;
	while(k<n){
		if(t1[k]==t1[k+1]){
			s.push_back(1);
			k+=2;
		}else{
			s.push_back(0);
			k++;
		}
	}
	ll ans=s[0]?6:3;
	for(int i=1;i<s.size();i++){
		if(s[i-1]&&s[i]){
			ans*=3;
		}else if(s[i-1]&&!s[i]){
			ans*=1;
		}else{
			ans*=2;
		}
		ans%=(ll)MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#define INF (long)1e9
#define MAX_N 10000000
const int MOD = 1e9 + 7;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
using namespace std;
typedef long long ll;
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	int t, d, l;
	while(cin >> t >> d >> l, t | d | l)
	{
		int cnt = 0;
		int b = -MAX_N;
		for(int i = 0; i < t; i++)
		{
			int x;
			cin >> x;
			if(i + 1 == t)
				continue;
			if(x >= l){
				b = i;
			}
			cnt += i - b<d;
		}
		cout << cnt << endl;
	}
	return 0;
}





Measured memory_bytes: 3008
#include <iostream>

using namespace std;

int N;
long long int A[100005], B[100005];

int main(void) {

	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i];
	}

	long long int count = 0;

	for (int i = N; i >= 1; i--) {
		long long int tmp = A[i] + count;

		if (tmp%B[i] != 0) { count += B[i] - (tmp%B[i]); }
	}

	cout << count << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace io{
	const int l=1<<20;
	char buf[l],*s,*t;
	inline char gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			return s==t?EOF:*s++;
		}
		return *s++;
	}
	char c;
	template<class IT>inline void gi(IT &x){
		x=0;c=gc();while(c<'0'||c>'9')c=gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=gc();}
	}
};
using io::gi;
template<class IT>inline void _int(      IT &a,      IT &b  ){if(a>b)swap(a,b);}
template<class IT>inline void cmin(      IT &a,const IT &b=0){if(a>b)a=b;}
template<class IT>inline void cmax(      IT &a,const IT &b=0){if(a<b)a=b;}
template<class IT>inline IT   _min(const IT &a,const IT &b=0){return a>b? b:a;}
template<class IT>inline IT   _max(const IT &a,const IT &b=0){return a<b? b:a;}
template<class IT>inline IT   _abs(const IT &a              ){return a<0?-a:a;}

const int N=200005;

struct qwq{
	int a,b;
	inline qwq(){}
	inline qwq(int a,int b):a(a),b(b){}
	inline bool operator<(const qwq &x)const{return a<x.a;}
};
int f[N];ll a[N];
int main(){
//	freopen("a.in","r",stdin);
//	freopen("a.out","w",stdout);
	int n,i;ll k,l=0ll,r=1000000000000ll,m,s,t;
	scanf("%d%lld",&n,&k);
	for(i=1;i<=n;++i)scanf("%lld",&a[i]);
	for(i=1;i<=n;++i)scanf("%d"  ,&f[i]);
	sort(a+1,a+n+1);
	sort(f+1,f+n+1);
	reverse(f+1,f+n+1);
	while(l<=r){
		m=(l+r)>>1;t=0ll;
		for(i=1;i<=n;++i)t+=_max(a[i]-m/f[i]);
		if(t<=k)r=(s=m)-1ll;else l=m+1ll;
	}
	printf("%lld",s);
	return 0;
}

Measured memory_bytes: 2688
package main

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

func nextInt(sc *bufio.Scanner) int {
	sc.Scan()
	n, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return n
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanLines)
	n := nextInt(sc)

	sc.Scan()
	s := strings.Split(sc.Text(), " ")

	for i := n; i >= 0; i-- {
		if i == 1 {
			fmt.Printf("%s", s[i-1])
			break
		}
		fmt.Printf("%s ", s[i-1])
	}
	fmt.Println("")
}



Measured memory_bytes: 1100
n=int(input())
a=list(map(int,input().split()))
b=[0]*(n)
ans=0
for i in range(1,n):
    b[i]=(a[i-1]+b[i-1])%1000000007
for i in range(1,n):
    ans+=(b[i]*a[i])%1000000007
print(ans%1000000007)


Measured memory_bytes: 94168
#include <stdio.h>
#define MAX 10000000
int ham[MAX + 1];

int main(){
  int m, n, i, j, k;

  for(i = 1; i <= MAX; i *= 2)
    for(j = i; j <= MAX; j *= 3)
      for(k = j; k <= MAX; k *= 5)
	ham[k] = 1;

  for(i = 1; i <= MAX; i++) 
    ham[i] += ham[i - 1];

  while(scanf("%d", &m) && m){
    scanf("%d", &n);
    printf("%d\n", ham[n] - ham[m - 1]);
  }

  return 0;
}

Measured memory_bytes: 39660
def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def r_sort(a) a.sort{|a,b|b<=>a} end

def ser(k)
  que = [[k,0]]
  while(que.size != 0)
    now = que.shift
    next if @used[now[0]]
    @memo[now[0]] = now[1]
    @used[now[0]] = true
    $link[now[0]].each do |nex, c|
      que.push([nex,c+now[1]])
    end
  end
end

$n = inp[0]
$link = na2($n+1,0)
($n-1).times do
  a,b,c = inp
  $link[a].push([b,c])
  $link[b].push([a,c])
end
q, k = inp
@memo = na($n+1,nil)
@used = na($n+1,false)
ser(k)
q.times do
  a,b = inp
  p @memo[a] + @memo[b]
end

Measured memory_bytes: 59316
#ifdef _MSC_VER
#define _CRT_SECURE_NO_WARNINGS
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

#define _USE_MATH_DEFINES

#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_map>
#include <stack>
#include <list>
#include <math.h>
#include <map>
#include <iomanip>
#include <functional>
#include <string>
#include <algorithm>
#include <queue>
#include <random>
#include <set>

using namespace std;

template<class T> ostream& operator<<(ostream& os, const vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) os << *i << (i == end(v) - 1 ? "" : " "); return os;
}
template<class T> istream& operator>>(istream& is, vector<T>& v) {
	for (auto i = begin(v); i != end(v); i++) is >> *i; return is;
}

#define MOD 1000000007
#define inf 2000000000

long long nearest_wsum(long long x, int sum)
{
	long long orig_x = x;
	vector<int> vec;
	int curr_sum = 0;
	while (x > 0)
	{
		vec.push_back(x % 10);
		curr_sum += x % 10;
		x /= 10;
	}

	while (vec.size() < 17)
		vec.push_back(0);

	if (curr_sum == sum)
		return orig_x;
	if (curr_sum < sum)
	{
		sum -= curr_sum;
		for (int j = 0; sum > 0 && j < vec.size(); j++)
		{
			int ava = 9 - vec[j];
			int inc = min(sum, ava);
			vec[j] += inc;
			sum -= inc;
		}
	}
	else
	{
		int acc = 0;
		for (int j = 0; j < vec.size(); j++)
		{
			if (vec[j] != 9 && acc > (curr_sum - sum))
			{
				curr_sum -= acc;
				vec[j]++; curr_sum++;

				for (int k = 0; curr_sum < sum && k < vec.size(); k++)
				{
					int ava = min(9, sum - curr_sum);
					vec[k] = ava;
					curr_sum += ava;
				}

				break;
			}
			acc += vec[j];
			vec[j] = 0;
		}
	}

	long long resp = 0;
	for (int j = vec.size() - 1; j >= 0; j--)
	{
		resp *= 10LL;
		resp += vec[j];
	}

	return resp;
}

int main() {

#if defined(_DEBUG) 
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int k;
	cin >> k;


	cout << 1 << "\n";
	long long prev_num = 1;

	for (int j = 2; j <= k; j++)
	{
		pair<long long, long long> best_pair = { nearest_wsum(prev_num + 1LL, 1), 1LL };
		for (long long denom = 2; denom <= 135; denom++)
		{
			pair<long long, long long> candidate = { nearest_wsum(prev_num + 1LL, denom), denom };
			if (candidate.first * best_pair.second < best_pair.first * candidate.second)
			{
				best_pair = candidate;
			}
		}

		cout << best_pair.first << "\n";
		prev_num = best_pair.first;
	}

	return 0;
}


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

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()

#define endl "\n"

void use_cio() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

template <class L, class R>
ostream &operator<<(ostream &os, pair<L, R> P) {
  return os << "(" << P.first << "," << P.second << ")";
}
template <class T>
ostream &operator<<(ostream &os, vector<T> V) {
  os << "[";
  for (auto x : V) os << x << ", ";
  return os << "]";
}

//--------------------------------------------------//

int main() {
  use_cio();
  string s;
  cin >> s;
  rep(i, s.size() - 1) {
    if (s[i] == s[i + 1]) return !(cout << "Bad\n");
  }
  cout << "Good";
}


Measured memory_bytes: 256
fn main() {
  fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
  }
  fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
  }
  fn solve(mut i: usize) -> i32 {
    let mut ans = 1;
    let mut history = [false; 1000001];
    history[i] = true;
    fn next(x: usize) -> usize {
      match x % 2 {
        0 => x / 2,
        _ => 3 * x + 1
      }
    }
    loop {
      i = next(i);
      ans += 1;
      if history[i] {
        break;
      } else {
        history[i] = true;
      }
    }
    ans
  }
  let input = read_vec::<usize>();
  println!("{}", solve(input[0]));
}



Measured memory_bytes: 5244
#include <bits/stdc++.h>
using namespace std;
string s, t,ans;
int dp[3009][3009],x,y;
int main() {
    cin >> s >> t;
    for (int i = 0; i < s.size(); i++) {
        for (int j = 0; j < t.size(); j++) {
            if (s[i] == t[j]) dp[i + 1][j + 1] = dp[i][j] + 1;
            dp[i + 1][j + 1] = max(dp[i + 1][j], max(dp[i][j + 1], dp[i + 1][j + 1]) );
        }
    }
    ans="",x = s.size(),y = t.size();
    while (x > 0 && y > 0) {
        if (dp[x][y] == dp[x - 1][y]) x--;
        else if (dp[x][y] == dp[x][y - 1]) y--;
        else {
            ans = s[x - 1] + ans;
            x--;
            y--;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 35584
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		sc.close();
		int a = 0;
		while(N>0) {
			a++;
			N=N/K;
		}
		System.out.println(a);
	}

}

Measured memory_bytes: 23124
//  Created by Vignesh Manoharan

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <cstring>
#include <cassert>

using namespace std;

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

const int INF = 1000000000;
const ll LINF = 1e17;
const double PI =3.141592653589793238;
#pragma unused(INF,PI,LINF)
#define F(i,a,n) for(int i=(a);i<(n);i++)

template<typename T,typename TT> ostream& operator<<(ostream &s,pair<T,TT> t) {return s<<"("<<t.first<<","<<t.second<<")";}
template<typename T> ostream& operator<<(ostream &s,vector<T> t){
    for(int i=0;i<(t).size();i++)s<<t[i]<<((i<(t).size()-1)?" ":"");return s; }
template<typename T> ostream& operator<<(ostream &s,set<T> t){for(T x:t) s<<x<<" ";return s; }
template<typename T> istream& operator>>(istream &s,vector<T> &t){
    for(int _i=0;_i<t.size();_i++) s>>t[_i];return s; }

#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()

const int maxn=100010;
ll a[maxn],tree[4*maxn];
ll merge(ll t1,ll t2){
    return min(t1,t2);
}
void build(int v,int l,int r){
    // call v=1,l=0,r=n-1
    if(l==r){
        tree[v]=a[l];
    } else {
        int mid=(l+r)/2;
        build(2*v,l,mid);
        build(2*v+1,mid+1,r);
        tree[v]=merge(tree[2*v],tree[2*v+1]);
    }
}
ll query(int v,int l,int r,int ql,int qr){
    // call v=1,l=0,r=n-1 to query from ql to qr(included)
    if(ql>qr)
        return (1ll<<31)-1; // check this for 'identity' value
    if(l==ql && r==qr)
        return tree[v];
    int mid=(l+r)/2;
    return merge(query(2*v,l,mid,ql,min(qr,mid)),
                 query(2*v+1,mid+1,r,max(ql,mid+1),qr));
}
void update(int v,int l,int r,int idx,int val){
    // call v=1,l=0,r=n-1 to update idx to val
    if(l==r){
        // may want to update a
        tree[v]=val;
    } else {
        int mid=(l+r)/2;
        if(idx<=mid) update(2*v,l,mid,idx,val);
        else update(2*v+1,mid+1,r,idx,val);
        tree[v]=merge(tree[2*v],tree[2*v+1]);
    }
}

int main(int argc, const char * argv[]) {
#ifdef local_test
    //    input
    //    freopen("input","w",stdout);
    //    cout<<"1 \n 100 10 \n";
     freopen("input","r",stdin);
     freopen("output","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    F(i,0,n) a[i]=(1ll<<31)-1;
    build(1,0,n-1);
    F(i,0,m){
        int com,x,y;
        cin>>com>>x>>y;
        if(com==0){
            a[x]=y;
            update(1,0,n-1,x,y);
        } else {
            cout<<query(1,0,n-1,x,y)<<"\n";
        }
    }
}

Measured memory_bytes: 5876
#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() {
  ll a,b,c,n;
  cin >> a >> b >> n;
  c = a*(b-1);
  if(n >= b-1) cout << c/b << endl;
  else cout << (a*n)/b-a*(n/b) << endl;
}

Measured memory_bytes: 3636
#include <stdio.h> 
int main()
{ int a,b,c, temp= 0;
 scanf("%d %d %d",&a,&b,&c); 
temp=a;
 a=b; 
b=temp;
 temp=a; 
 a=c; 
c=temp ; 
printf("%d %d %d\n",a,b,c);
 return 0; 
}

Measured memory_bytes: 1724
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
    int a[3];
    cin >> a[0] >> a[1] >> a[2];
    sort(a, &a[3]);
    cout << a[0] + a[1] << endl;

    return 0;
}


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

#define F(i, a, n) for(int i=a;i<n;i++)
#define REP(i, n) F(i, 0, n)
#define REP1(i, n) for(int i=1;i<=n;i++)
#define MOD 1000000007

typedef long long ll;

const int MAX = 2e6 + 5;

int w,a,b;
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin>>w>>a>>b;
	if(b > a + w)
		cout<<b-(a+w);
	else if(b + w < a)
		cout<<a-(b+w);
	else
		cout<<0;
	return 0;
}

Measured memory_bytes: 256