akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstring>
using namespace std;
struct SAComp{
	const int h,*g;
	SAComp(const int h, const int* g) : h(h), g(g) {}
	bool operator()(const int a, const int b){
		return a == b ? false : g[a] != g[b] ? g[a] < g[b] : g[a+h] < g[b+h];
	}
};
vector<int> buildSA(string &t){
	int n=t.size();
	int g[n],b[n];
	vector<int>suff(n);
	for(int i=0;i<n;i++)suff[i]=i,g[i]=t[i];
	b[0]=b[n-1]=0;
	sort(suff.begin(),suff.end(),SAComp(0,g));
	for(int h=1;b[n-1]!=n-1;h<<=1){
		SAComp comp(h,g);
		sort(suff.begin(),suff.end(),comp);
		for(int i=0;i<n-1;i++)b[i+1]=b[i]+comp(suff[i],suff[i+1]);
		for(int i=0;i<n;i++)g[suff[i]]=b[i];
	}
	return suff;
}
int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin>>s;
	s+='$';
	int n=s.size();
	vector<int>suff=buildSA(s);
	vector<pair<char,int>>sorted(n);
	for(int i=0;i<n;i++)sorted[i]={s[(suff[i]-1+n)%n],i};
	sort(sorted.begin(),sorted.end());

	//int T;
	//for(cin>>T;T--;){
		string q;
		cin>>q;
		int start=0,stop=n,idx=q.size()-1;
		for(;idx>=0;idx--){
			pair<char,int> ql={q[idx],start},qr={q[idx],stop};
			start=lower_bound(sorted.begin(),sorted.end(),ql)-sorted.begin();
			stop=lower_bound(sorted.begin(),sorted.end(),qr)-sorted.begin();
			if(start==stop)break;
		}
		if(idx<0){
			{vector<int>v;for(;start<stop;start++)v.push_back(suff[start]);sort(v.begin(),v.end());for(auto &e:v)printf("%d\n",e);}
			//puts("1");
		}else{
			//puts("0");
		}
	//}
}

Measured memory_bytes: 28408
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
template <typename T> bool chmax(T &u, const T z) { if (u < z) {u = z; return true;} else return false; }
template <typename T> bool chmin(T &u, const T z) { if (u > z) {u = z; return true;} else return false; }
#define ll  long long 
const ll INF=1LL<<60;
const ll MOD=1000000007;
#define rep(i, n)        for(ll i=0; i<(ll)(n); ++i)
ll dp[2001];
int main(){
    ll a;cin>>a;
    dp[1]=0;
    dp[2]=0;
    dp[3]=1;
    dp[4]=1;
    if(a<=4)cout<<dp[a];
    else{for(ll i=5;i<=a;i++){
        dp[i]=dp[i-2]+dp[i-3]+dp[i-4];
        dp[i]%=MOD;
    }
    cout<<dp[a];
}}


Measured memory_bytes: 3532
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define MOD 1000000007
using Graph = vector<vector<int>>;

int main (){
  int a,b;
  cin>>a>>b;
  cout<<a*b;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define _abs(x)((x) < 0 ? (x) * -1 : (x))
#define _max(x, y)(max(0, max((x), (y))))
#define _min(x, y)(max(0, min((x), (y))))

static const ll MOD = 1e9 + 7;

int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    //freopen("debug.txt", "w", stderr);

    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b, c, d, e, f;

    cin >> a >> b >> c >> d >> e >> f;

    vector<long> sugars, waters;
    long sugar, water;
    double per, maxPer = 0.0;

    int i, j, len, lenJ;

    for (i = 0; i <= f; i += a * 100) {
        for (j = 0; j <= f; j += b * 100) {
            if (i + j <= f) waters.push_back(i + j);
        }
    }

    for (i = 0; i <= f; i += c) {
        for (j = 0; j <= f; j += d) {
            if (i + j <= f) sugars.push_back(i + j);
        }
    }

    len = waters.size();
    lenJ = sugars.size();
    for (i = 0; i < len; i++) {
        for (j = 0; j < lenJ; j++) {
            if (waters[i] + sugars[j] <= f) {
                per = (double)sugars[j] / (double)(waters[i] + sugars[j]);

                if ((100 + e) * sugars[j] <= (waters[i] + sugars[j]) * e && maxPer <= per) {
                    water = waters[i];
                    sugar = sugars[j];
                    maxPer = per;
                }
            }
        }
    }

    cout << water + sugar << " " << sugar << '\n';

    return 0;
}


Measured memory_bytes: 2420
#include <iostream>
using namespace std;
void ABC90(void);
void ABC91(void);
void ABC92(void);
void ABC93(void);
void ABC94(void);
void ABC95(void);
void ABC96(void);
void ABC97(void);
void ABC98(void);
void ABC99(void);

int main(void){
    ABC90();
}

void ABC90(){
    string a,b,c;
    cin>>a>>b>>c;
    cout<<a[0]<<b[1]<<c[2]<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<cmath>
#define LL long long 
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
LL x[100005],ans[100005],k[100005],bc[100005],ass[100005];
int main()
{
	LL n=read();
	for(LL i=1;i<=n;i++) x[ans[i]=k[i]=i]=read();
	LL m=read(),lun=read();
	for(LL i=1;i<=m;i++) 
	{
		LL a=read();
		swap(k[a],k[a+1]);
	}
	while(lun)
	{
		if(lun&1)
		{
			for(LL i=1;i<=n;i++) bc[i]=ans[k[i]];
			for(LL i=1;i<=n;i++) ans[i]=bc[i];
		}
		for(LL i=1;i<=n;i++) bc[i]=k[k[i]];
		for(LL i=1;i<=n;i++) k[i]=bc[i];
		lun>>=1;
	}
	for(LL i=1;i<=n;i++) ass[i]=x[ans[i]]-x[ans[i]-1];
	double s=0;
	for(LL i=1;i<=n;i++) {s+=ass[i];printf("%.1lf\n",s);}
	return 0;
}


Measured memory_bytes: 7088
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define mfill(x,y) memset(x,y,sizeof(x))
#define all(v) v.begin(), v.end()
#define in(x,y,h,w) if(0<=x&&x<h&&0<=y&&y<w)
#define y0 y12345
#define y1 y54321

#ifdef LOCAL
#define debug(...) fprintf(stderr,__VA_ARGS__)
#else
#define debug(...) 42
#endif

using ul = unsigned long;
using ll = long long;
using P = pair<int, int>;
using vint = vector<int>;using vvint = vector<vector<int>>;
using vll = vector<ll>;using vvll = vector<vector<ll>>;
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(a>b){a=b;return 1;}return 0;}
template <class T>void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
	v.assign(a, vector<T>(b, t));
}
template <class T>T gcd(T &a, T &b){if(a<b){swap(a,b);} T r = a%b; while(r!=0){a=b;b=r;r=a%b;} return b;}

vint dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};
vint dx8 = {-1, -1, -1, 0, 1, 1, 1, 0}, dy8 = {-1, 0, 1, 1, 1, 0, -1, -1};

int main() {
	cin.tie(0);
   	ios::sync_with_stdio(false);
	debug("debug test\n");
   	int n,m;
	cin>>n;
	if(n%2==0){
		cout << 0.5000000 << endl;
	}else{
		cout <<((double)(n+1)/2)/n << endl;
	}
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(),(a).end()
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
const int INF=1e9;
const int mod=100000;
int dp[2][3010][50];
int n,m,s;
int main(){
  while(1){
    cin>>n>>m>>s;
    if(n==0&&m==0&&s==0)break;
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1;
    for(int i=1;i<=m;i++){
      REP(j,3010)REP(k,50)dp[i&1][j][k]=dp[(i-1)&1][j][k];
      for(int j=0;j+i<=s;j++){
        for(int k=0;k<n*n;k++){
          if(dp[(i-1)&1][j][k]>=1){
          }
          dp[i&1][j+i][k+1]+=dp[(i-1)&1][j][k];
          dp[i&1][j+i][k+1]%=mod;
        }
      }
    }
    cout<<dp[m&1][s][n*n]%mod<<endl;
  }
}

Measured memory_bytes: 2344
#include<stdio.h>
#define N 1000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,A[N][N],color[N],d[N],f[N],time;
void visit(int r)
{
  int v;
  color[r]=GRAY;
  d[r]=++time;
  for(v=0;v<n;v++)
    {
      if(A[r][v]==0)
	{
	  continue;
	}
      if(color[v]==WHITE)
	{
	  visit(v);
	}
    }
  color[r]=BLACK;
  f[r]=++time;
}
  
void dfs()
{
  int u;
  for(u=0;u<n;u++)
    {
      color[u]=WHITE;
      time=0;
    }
      for(u=0;u<n;u++)
	{
	  if(color[u]==WHITE)
	    {
	      visit(u);
	    }
	}
      for(u=0;u<n;u++)
	{
	  printf("%d %d %d\n",u+1,d[u],f[u]);
	}
}


int main()
{
  int i,j,u,k,v;
  scanf("%d",&n);
  for(i=1;i<=n;i++)
    {
      for(j=1;j<=n;j++)
	{
	  A[i][j]=0;
	}
    }
  for(i=1;i<=n;i++)
    {
      scanf("%d%d",&u,&k);
      u--;
      for(j=1;j<=k;j++)
      {
	scanf("%d",&v);
	v--;
	A[u][v]=1;
      }
    }
  dfs();
	    

  return 0;
}



Measured memory_bytes: 2128
n = int(input())
d_inp = [input() for i in range(n)]
can = False
d = []
for i in range(n):
    d.append(list(map(int, d_inp[i].split())))
ct = 0
cx = 0
cy = 0
for i in range(n):
    dt = d[i][0]-ct
    dx = d[i][1]-cx
    dy = d[i][2]-cy
    if dx+dy > dt:
        break
    if (dx+dy) % 2 != dt % 2:
        break
    ct += dt
    cx += dx
    cy += dy
else:
    can = True
if can == True:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 34460
#include <stdio.h>

int S(int n) {
	int asumikana = 0;
	if (n < 0) return S(-n);
	while (n > 0) {
		asumikana += n % 10;
		n /= 10;
	}
	return asumikana;
}

int main(void) {
	int N;
	if (scanf("%d", &N) != 1) return 1;
	puts(N % S(N) == 0 ? "Yes" : "No");
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
 
 
void solve(){
    int n;
    cin>>n;

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

    vector<vector<ll>> dp(n, vector<ll>(3));
    dp[0][0]=a[0];
    dp[0][1]=b[0];
    dp[0][2]=c[0];

    for(int i=1;i<n;i++){
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+a[i];
        dp[i][1]=max(dp[i-1][0],dp[i-1][2])+b[i];
        dp[i][2]=max(dp[i-1][0],dp[i-1][1])+c[i];
    }

    ll res=0;
    for(auto x: dp.back())res=max(res,x);

    cout<<res<<endl;
}


int main()
{   
    // int n;
    // cin>>n;

    // while(n--)
    solve();

    return 0;
}

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

#define DEBUG 0 // change 0 -> 1 if we need debug.
// insert #if<tab> by my emacs. #if DEBUG == 1 ... #end

typedef long long ll;

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

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

int n;
string S[60];
int cnt[60][26];
int mini[26];

int main () {
  cin >> n;
  for (auto i = 0; i < n; ++i) {
    cin >> S[i];
  }
  fill(&cnt[0][0], &cnt[0][0]+60*26, 0);
  for (auto i = 0; i < n; ++i) {
    for (auto x : S[i]) {
      cnt[i][x - 'a']++;
    }
  }
  fill(mini, mini+26, 100);
  for (auto i = 0; i < 26; ++i) {
    for (auto j = 0; j < n; ++j) {
      mini[i] = min(mini[i], cnt[j][i]);
    }
  }
  string ans = "";
  for (auto i = 0; i < 26; ++i) {
    string t{'a' + i};
    for (auto j = 0; j < mini[i]; ++j) {
      ans += t;
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
import numpy as np
from itertools import combinations as comb


def main():
    n, d = map(int, input().split())
    xs = [list(map(int, input().split())) for _ in range(n)]
    xs_combs = list(comb(xs, 2))
    ans = 0
    for xs_comb in xs_combs:
        xs_comb = np.array(xs_comb)
        dist = np.linalg.norm(xs_comb[0]-xs_comb[1])
        if int(dist) == dist:
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< pii >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; cin >> x;
#define int2(x, y) Int(x); Int(y);
#define int3(x, y, z) Int(x); int2(y, z);
#define in(x, a, b) ((a) <= (x) && (x) < (b))
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second
#define Decimal fixed << setprecision(10)

//int dxy[5] = {0, 1, 0, -1, 0};
// cmd

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

    int2(n, k);
    vector<int> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i];
    }
    
    sort(all(data));
    int ret = 0;
    rep(i, k) ret += data[i];
    cout << ret << endl;

    return 0;
}


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

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

    int h,w,k; cin>>h>>w>>k;
    int sx,sy,tx,ty; cin>>sx>>sy>>tx>>ty;
    sx--,sy--,tx--,ty--;
    vector<string> grd(h);
    for(auto &r: grd) cin>>r;
    const int inf=1e7;
    vector dist(h,vector<int>(w,inf));
    const int dx[4]={1,0,-1,0};
    const int dy[4]={0,1,0,-1};
    queue<pair<int,int>> qu;
    qu.emplace(sx,sy);
    dist[sx][sy]=0;
    while(!qu.empty())
    {
        auto [nox,noy]=qu.front();
        qu.pop();
        for(int i=0; i<4; i++)
        {
            int tox=nox;
            int toy=noy;
            for(int j=1; j<=k; j++)
            {
                tox+=dx[i];
                toy+=dy[i];
                if(tox<0 or toy<0 or tox>=h or toy>=w) break;
                if(grd[tox][toy]=='@' or dist[tox][toy]<=dist[nox][noy]) break;
                if(dist[tox][toy]==inf)
                {
                    qu.emplace(tox,toy);
                    dist[tox][toy]=dist[nox][noy]+1;
                }
            }
        }
    }
    if(dist[tx][ty]!=inf) cout << dist[tx][ty] << "\n";
    else cout << -1 << "\n";
}


Measured memory_bytes: 12160
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())


def floor_sum(n,m,a,b):  # sum((A*i+B)//M for i in range(N))
    res = 0
    res += (a//m)*n*(n-1)//2 + (b//m)*n
    a %= m
    b %= m
    y_max = (a*n+b)//m
    if y_max == 0:
        return res
    x_max = m*y_max-b
    res += (n+(-x_max)//a)*y_max
    res += floor_sum(y_max,a,m,(x_max+a-1)//a*a-x_max)
    return res


T = I()
for i in range(T):
    n,m,a,b = MI()
    print(floor_sum(n,m,a,b))


Measured memory_bytes: 78220
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000000
#define endl '\n'
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

int n,m;
vector<P> a;
int num[9]={2,5,5,4,5,6,3,7,6};
int dp[10010];

signed main(){
    cin>>n>>m;
    a.resize(m);
    rep(i,m){
        cin>>a.at(i).F;
        a.at(i).S=num[a.at(i).F-1];
    }
    fill(dp+1,dp+10010,-INF);
    rep(i,n){
        rep(j,m){
            if(i+1-a.at(j).S>=0){
                chmax(dp[i+1], dp[i+1-a.at(j).S]+1);
            }
        }
    }
    int match=n;
    while(match>0){
        int tmp=-1;
        rep(i,m){
            if(match-a.at(i).S>=0 and dp[match-a.at(i).S]==dp[match]-1){
                chmax(tmp, a.at(i).F);
            }
        }
        cout<<tmp;
        match-=num[tmp-1];
    }
    cout<<endl;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int n;
char s[MAXN];
map<pair<string,string>,int>cnt;
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%d",&n);
    scanf("%s",s);
    reverse(s+n,s+2*n);
    for(int i=0;i<(1<<n);i++){
		string a,b;
		for(int j=0;j<n;j++){
			if(i>>j&1)
				a+=s[j];
			else
				b+=s[j];
		}
		cnt[mp(a,b)]++;
	}
	ll ans=0;
	for(int i=0;i<(1<<n);i++){
		string a,b;
		for(int j=0;j<n;j++){
			if(i>>j&1)
				a+=s[n+j];
			else
				b+=s[n+j];
		}
		ans+=cnt[mp(a,b)];
	}
	printf("%lld\n",ans);
	return 0;
}
 

Measured memory_bytes: 91904
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 105
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 100005;
const int MOD = 1000000007;

int main(){
    int n;
    cin>>n;
    int sum=0;
    int m=0;
    REP(i,n){
        int a;
        cin>>a;
        sum+=a;
        m=max(m,a);
    }
    OUT(sum-m/2);
    return 0;
}

Measured memory_bytes: 256
#include "stdio.h"
#include <vector>
#include <queue>
#include <set>

using namespace std;

int x[10];

int main()
{
while(1)
{
int n,k;
scanf("%d",&n);
scanf("%d",&k);
if(n == 0 && k == 0)
{
break;
}
for(int i = 0; i < n; i++)
{
scanf("%d",&x[i]);
}

int w = 1;
for(int i = 0; i < k; i++)
{
w *= n;
}

set<int> sw;
for(int i = 0; i < w; i++)
{
priority_queue<int> q1;
vector<int> q2;
int s = i;
for(int i = 0; i < k; i++)
{
int l = s % n;
q1.push(l);
q2.push_back(l);
s /= n;
}

int flgw = 0;
int mae = -1;
for(int ii = 0; ii < k; ii++)
{
if(mae == q1.top())
{
flgw = 1;
break;
}
mae = q1.top();
q1.pop();
}
if(flgw == 1)
{
continue;
}

int g = 0;
for(int ii = 0; ii < k; ii++)
{
if(x[q2[ii]] < 10)
{
g = g * 10 + x[q2[ii]];
}
else
{
g = g * 100 + x[q2[ii]];
}
}
sw.insert(g);
}

printf("%d\n",sw.size());
}
return 0;
}

Measured memory_bytes: 1176
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

//constexpr int inf = 2147483647;
//constexpr int64_t inf64 = 9223372036854775807;
//constexpr int mod = 1e9+7;

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

  int n, m;
  cin >> n >> m;

  cout << n*(n-1)/2 + m*(m-1)/2 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define c(P)        cout<<P<<"\n"
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define mii         map<pii,ll>
#define F           first
#define S           second
#define sz(a)       (ll)(a.size())
#define mem(a,val)  memset(a,val,sizeof(a))
#define fr(i,x,n)   for(ll i=x;i<n;i++)
#define frr(i,x,n)  for(ll i=n-1;i>=x;i--)
using namespace std;


const ll N   =  500005;
const ll mod = 1e9 + 7;



void solve(){

  ll x=0,y=0,c=0,ans=0;
  ll n,m,k;
  cin>>n >> m;
  
  ll a[n];
  for (ll i = 0; i < n; ++i)
  {
  cin>>a[i];
  c+=a[i];
  }
  for (ll i = 0; i < n; ++i){
      
   
  if(a[i]* 4* m >= c){
   // c(i);
    ans++;
  }
  }
  if(ans>=m){
    c("Yes");
  }
  else c("No");

}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<string>
#define FIO ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define mod (ll)(1e9+7)
#define nax (ll)(1e6)
#define INFL LLONG_MAX
#define NINFL LLONG_MIN
#define INF INT_MAX
#define disp(a,n,arr) for(int i=a;i<(ll)n;i++) cout << arr[i] << " "; cout << "\n";
#define check cout << "Working\n";
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vpl vector<pl>
#define vpi vector<pi>
#define vb vector<bool>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

int main() {
	FIO;
	int t = 1;
	//cin >> t;
	while (t--) {
		ll n;
		ll x = 1000;
		cin >> n;
		while(n > x){
			x += 1000;
		}
		cout << x - n << "\n";
	}


	return 0;
}


Measured memory_bytes: 3648
/**
 * @author: shashankchdhry
 * @made:   2020-03-31 10:54:14 
**/
#include <bits/stdc++.h>

using namespace std;

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

    vector<string> arr(3);
    cin >> arr[0] >> arr[1] >> arr[2];

    vector<pair<int, int>> count{
        {0,arr[0].length()}, 
        {0,arr[1].length()}, 
        {0,arr[2].length()}};

    int crrnt = 0;
    while (count[crrnt].first != count[crrnt].second)
    {
        int temp = arr[crrnt][count[crrnt].first] - 'a';
        count[crrnt].first++;
        crrnt = temp;
    }

    char ans = toupper(crrnt+'a');
    cout << ans << "\n";

    return 0;
}

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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cerr << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cerr << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int a; cin >> a;
  long double b; cin >> b;
  int ans = a * b;
  cout << ans;
  cout << "\n";
  return 0;
}
/***** MAIN *****/


Measured memory_bytes: 3680
import sys
if sys.version_info < (3, 5):
    from fractions import gcd
else:
    from math import gcd

def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    return int(a * b // gcd(a, b))

def solve():
    n = int(input())
    tl = [int(input()) for _ in range(n)]
    ans = tl[0]
    for elem in tl[1:]:
        ans = lcm(ans, elem)
    print(ans)
 
if __name__=="__main__":
    solve()

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

#define INF INT_MAX
#define MOD 1000000007
#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()

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

using namespace std;

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

    ll n;
    cin >> n;
    vector<ll> h(n),dp(n,INF);
    REP(i,n)cin >> h[i];
    dp[0] = 0;
    dp[1] = abs(h[0] - h[1]);
    for(ll i = 2;i < n;i++){
        ll prev_1 = abs(h[i] - h[i-1]) + dp[i-1];
        ll prev_2 = abs(h[i] - h[i-2]) + dp[i-2];
        dp[i] = min(prev_1,prev_2);
    }
    cout << dp[n-1] << endl;

    return 0;
}    

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
#define MOD 1e9+7

int main(){
    int n,m;
    cin >> n >> m;
    vector<string> a(n),b(m);
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];
    for(int i=0;i<=n-m;i++){
        for(int j=0;j<=n-m;j++){
            bool flag=true;
            for(int k=0;k<m;k++){
                for(int l=0;l<m;l++){
                    if(a[i+k][j+l]==b[k][l]) continue;
                    flag=false;
                    break;
                }
            }
            if(flag){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 3564
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
#define abs(a) (a>0?a:(-(a)))
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
char s[10050];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	for (int i=1;i<=n;i++){
		if (i%2&&(s[i]!='R'&&s[i]!='U'&&s[i]!='D')) return printf("No\n"),0;
		if (i%2==0&&(s[i]!='L'&&s[i]!='U'&&s[i]!='D')) return printf("No\n"),0;
	}
	printf("Yes\n");
	return 0;
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>

using namespace std;

namespace {

class Dice {
 public:
  Dice(const int* face) {
    copy(face, face + 6, face_);
  }

  void west() {
    const int t = face_[0];
    const int t2 = face_[3];
    face_[0] = face_[2];
    face_[2] = face_[5];
    face_[3] = t;
    face_[5] = t2;
  }

  void east() {
    const int t = face_[0];
    const int t2 = face_[2];
    face_[0] = face_[3];
    face_[2] = t;
    face_[3] = face_[5];
    face_[5] = t2;
  }

  void north() {
    const int t = face_[0];
    const int t2 = face_[4];
    face_[0] = face_[1];
    face_[1] = face_[5];
    face_[4] = t;
    face_[5] = t2;
  }

  void south() {
    const int t = face_[0];
    const int t2 = face_[1];
    face_[0] = face_[4];
    face_[1] = t;
    face_[4] = face_[5];
    face_[5] = t2;
  }

  int top() const { return face_[0]; }

 private:
  int face_[6];
};

}  // namespace

int main() {
  string ops;
  int face[6];
  for (int i = 0; i < 6; ++i) {
    cin >> face[i];
  }
  cin >> ops;

  Dice d(face);
  for (auto op : ops) {
    switch (op) {
      case 'W':
        d.west();
        break;
      case 'E':
        d.east();
        break;
      case 'N':
        d.north();
        break;
      case 'S':
        d.south();
        break;
    }
  }
  cout << d.top() << endl;

  return 0;
}

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

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define MIN(a) *min_element(all(a))
#define MAX(a) *max_element(all(a))
#define SUM(a, b) accumulate(all(a), b)
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define RREP(i, n) for(int (i)=(n)-1; (i)>=0; (i)--)
#define FOR(i, m, n) for(int (i)=(m); (i)<(n); i++)
#define FORR(i, m, n) for(int (i)=(n)-1; (i)>=(m); i--)
#define ios() cin.tie(0), ios::sync_with_stdio(false)
#define debug(x) cerr << #x << " = " << x << endl
//#define int long long

typedef long long ll;
typedef unsigned long long ull;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
ll const INF = 1e18;

template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}

//Graph in adjcency list (weighted)
class Graph{
public:
    int N;
    vector<vector<pair<int,ll>>> adjlist;
    vector<ll> depth;

    Graph(int n) : N(n), adjlist(n), depth(n, -1){}

    void setEdge(int a, int b, ll c){
        adjlist[a].push_back(make_pair(b, c));
    }

    void dfs(int p, int v, ll dist){
        static vector<bool> check(N, false);
        if(check[v]){
            return;
        }
        check[v] = true;
        depth[v] = dist;
        for(auto i : adjlist[v]){
            if(i.first == p){
                continue;
            }
            dfs(v, i.first, dist + i.second);
        }
    }

    void dijkstra(int start){
        depth[start] = 0;

        auto fn = [](pair<int,ll> a, pair<int, ll> b){return a.second > b.second;};
        priority_queue<pair<int,ll>, vector<pair<int,ll>>, decltype(fn)> que(fn);

        for(auto i : adjlist[start]) que.push(i);

        while(!que.empty()){
            auto v = que.top().first;
            auto d = que.top().second;
            que.pop();

            if(depth[v] >= 0) continue;
            else depth[v] = d;
            
            for(auto i : adjlist[v]){
                if(depth[i.first] == -1){
                    que.push(make_pair(i.first, i.second + d));
                }
            }
        }
    }
};


signed main(){
    int n, m, start, goal;
    cin >> n >> m >> start >> goal;
    start--;
    goal--;

    Graph GY(n), GS(n);

    REP(i, m){
        int u, v;
        ll a, b;
        cin >> u >> v >> a >> b;
        u--;
        v--;
        GY.setEdge(u, v, a);
        GY.setEdge(v, u, a);
        GS.setEdge(u, v, b);
        GS.setEdge(v, u, b);
    }

    GY.dijkstra(start);
    GS.dijkstra(goal);

    vector<ll> cost(n+1);
    cost[n] = INF;

    RREP(i, n){
        cost[i] = min(cost[i+1], GY.depth[i] + GS.depth[i]);
    }

    REP(i, n){
        cout << (ll)1e15 - cost[i] << '\n';
    }

    return 0;
}


Measured memory_bytes: 19000
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>
#include <iomanip>
#include <random>


#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout << fixed << setprecision(20);

	int as[3][3];
	FOR_LT(i, 0, 3) {
		FOR_LT(j, 0, 3) {
			cin >> as[i][j];
		}
	}

	bool bs[3][3] = {};
	int n; cin >> n;
	FOR_LT(i, 0, n) {
		int b; cin >> b;
		FOR_LT(j, 0, 3) {
			FOR_LT(k, 0, 3) {
				if (as[j][k] == b) bs[j][k] = true;
			}
		}
	}

	bool is_ok = false;
	FOR_LT(i, 0, 3) {
		bool s = true;
		FOR_LT(j, 0, 3) {
			if (!bs[i][j]) {
				s = false;
				break;
			}
		}
		if (s) is_ok = true;
	}
	FOR_LT(i, 0, 3) {
		bool s = true;
		FOR_LT(j, 0, 3) {
			if (!bs[j][i]) {
				s = false;
				break;
			}
		}
		if (s) is_ok = true;
	}

	if (bs[0][0] && bs[1][1] && bs[2][2]) is_ok = true;
	if (bs[0][2] && bs[1][1] && bs[2][0]) is_ok = true;

	if (is_ok) cout << "Yes" << endl;
	else cout << "No" << endl;
	

	return 0;
}

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

int main() {
    int n;
    cin >> n;
    int k = n % 10;
    
    if (k == 3) {
        cout << "bon" << endl;
    } else if (k == 0 || k == 1 || k == 6 || k == 8) {
        cout << "pon" << endl;
    } else {
        cout << "hon" << endl;
    }
}

Measured memory_bytes: 3676
#include <iostream>
#include <cstdio>
using namespace std;
const int MAX_V = 15;
const int MAX_E = 50;
const int INF = 100000000;
int V, E;
int d[MAX_V][MAX_V];  //各町間の通勤時間
int main(int argc, const char * argv[])
{
    while (true) {
        scanf("%d", &E);  //道の数
        if (E == 0) break;
        V = 0;
        //d[][]の初期化
        for (int i = 0; i < MAX_V; i++) {
            for (int j = 0; j < MAX_V; j++) d[i][j] = INF;
        }
        
        for (int i = 0; i < E; i++) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            V = max(V,max(a,b));  //0~最大の番号までが町の番号
            d[a][b] = min(d[a][b], c);
            d[b][a] = d[a][b];
        }
        
        for (int i = 0; i <= V; i++) d[i][i] = 0;
        
        for (int k = 0; k <= V; k++) {
            for (int i = 0; i <= V; i++) {
                for (int j = 0; j <= V; j++) {
                    d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
                }
            }
        }
        
        int town = 0;  //とりあえず、0にセット
        int dist = 0;
        for (int i = 0; i <= V; i++) dist += d[0][i];
        for (int i = 1; i <= V; i++) {
            int total = 0;
            for (int j = 0; j <= V; j++) {
                total += d[i][j];
            }
            if (total < dist) {
                town = i;
                dist = total;
            }
        }
        printf("%d %d\n", town, dist);
    }
    return 0;
}

Measured memory_bytes: 1188
/**
 *    author:  tourist
 *    created: 23.09.2017 14:52:20       
**/
#include <bits/stdc++.h>

using namespace std;

int main() {
  string s; cin >> s; cout << (s.substr(0, 4) == "YAKI" ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
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


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


	int N, Q;
	cin >> N >> Q;
	int A[100000];
	rep(i, N) cin >> A[i];
	sort(A, A + N);

	ll S[100001] = {};
	ll S1[100001] = {};
	ll S2[100001] = {};
	rep(i, N) {
		S[i + 1] = S[i] + A[i];
		S1[i + 1] = S1[i];
		S2[i + 1] = S2[i];
		if (i % 2 == 0) S1[i + 1] += A[i];
		else S2[i + 1] += A[i];
	}

	rep(i, Q) {
		int X;
		cin >> X;

		int L = X;
		int R = 1e9;
		while (L < R) {
			int H = (L + R + 1) / 2;
			int kari = X - (H - X);
			int a = lower_bound(A, A + N, kari) - A;
			int b = upper_bound(A, A + N, H) - A;
			if (b - a <= N - b) L = H;
			else R = H - 1;
		}

		int b = upper_bound(A, A + N, L) - A;


		ll kotae = 0;
		kotae += S[N] - S[b];

		int kari = N - (N - b) * 2;
		if (kari > 0 && N % 2) kotae += S1[kari];
		else if (kari > 0 && N % 2 == 0) kotae += S2[kari];

		co(kotae);
	}

	Would you please return 0;
}

Measured memory_bytes: 4480
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
int n,a[N],maxn,nmax;
int read(){
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
int main(){
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=n;i++){
		if(a[i]>maxn) maxn=a[i];
		else if(a[i]>nmax) nmax=a[i];
	}
	for(int i=1;i<=n;i++){
		if(a[i]==maxn) printf("%d\n",nmax);
		else printf("%d\n",maxn);
	}
	return 0;
}


Measured memory_bytes: 2432
#include <iostream>
#include <random>
#include <chrono>
#include <algorithm>
#include <map>
#include <cstring>

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
using namespace std;
typedef long long ll;
const ll MOD = (ll)1e9 + 7;
const int N = 1e2+5, inf = 1e9+5;
ll add(ll x, ll y) { x += y; if (x >= MOD) return x - MOD; return x; }
ll sub(ll x, ll y) { x -= y; if (x < 0) return x + MOD; return x; }
ll mult(ll x, ll y) { return (x * y) % MOD; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll weights[N], values[N];
ll dp[N][N*1000];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    ll n, W; cin >> n >> W;
    rep (i, 0, n) {
        cin >> weights[i];
        cin >> values[i];
    }

    std::fill(&dp[0][0], &dp[0][0] + sizeof(dp) / sizeof(dp[0][0]), inf);
    int ans = 0;
    for (int i = 0; i < n; ++i)
        for (int v = 0; v <= N*1000; ++v) {
            if (i > 0) {
                dp[i][v] = dp[i - 1][v];
                if (v - values[i] >= 0)
                    dp[i][v] = min(dp[i][v], dp[i - 1][v - values[i]] + weights[i]);
            }
            if (values[i] == v)
                dp[i][v] = min(dp[i][v], weights[i]);
            if (dp[i][v] <= W)
                ans = v;
        }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 86400
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
typedef complex<ld> Point;
const ll INF = mod * mod;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
const ld eps = 1e-6;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;

int n;

void solve() {
	vector<P> v(n);
	rep(i, n) {
		cin >> v[i].first >> v[i].second;
	}
	sort(v.begin(),v.end());
	int sum = 0;
	rep(i, n - 1) {
		sum += v[i].first;
	}
	int dif = max(0, v[n - 1].first-sum);
	if (dif == 0) {
		int ans = sum + v[n - 1].first;
		rep(i, n) {
			ans += v[i].second;
		}
		cout << ans << endl; return;
	}
	bitset<1001> b; b[0] = 1;
	rep(i, n) {
		if (i == n - 1)continue;
		int z = v[i].second;
		b |= (b << z);
	}
	int ans = 2 * v[n - 1].first;
	rep(i, n) {
		ans += v[i].second;
	}
	int dec = 0;
	rep(i, dif + 1)if (b[i])dec = i;
	//cout << "hello " << dec << endl;
	cout << ans - dec << endl;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	while (cin >>n,n) {
		solve();
	}
	//stop
	return 0;
}


Measured memory_bytes: 3152
N, A, B = map(int, input().split())

if A > B:
    ans = 0
elif N == 1 and A != B:
    ans = 0
elif N <= 2:
    ans = 1
else:
    mn = A * (N-1) + B
    mx = A + B * (N-1)
    ans = mx - mn + 1
print(ans)


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

#define REP(i,n) for(long long i=0;i<(n);i++)

int main() {
  int a, b, c, d, e, k;
  cin >> a >> b >> c >> d >> e >> k;
  if(e - a <= k) {
    cout << "Yay!" << endl;
  } else {
    cout << ":(" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;

ll n,ans;
ll a[20];

void dfs(int u,ll sum,ll now){
    //printf("###%d %lld %lld\n",u,sum,now);
    if(u==a[0]+1){
        //printf("%lld\n",sum+now);
        ans+=sum+now;
        return;
    }
    dfs(u+1,sum,now*10ll+a[u]);
    dfs(u+1,sum+now,a[u]);
}

int main(){
    scanf("%lld",&n);
    while(n){
        a[++a[0]]=n%10;
        n/=10ll;
    }
    reverse(a+1,a+a[0]+1);
    /*for(int i=1;i<=a[0];i++) printf("%d ",a[i]);
    puts("");*/
    dfs(2,0,a[1]);
    printf("%lld",ans);
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
int main(void) {
	double x1, x2, x3, px, y1, y2, y3, py, r;
	int n, i;
	
	scanf("%d", &n);
	for(i = 1; i <= n; i++){
		scanf("%lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3);
		px = ((y1-y3)*(x2*x2-x1*x1+y2*y2-y1*y1)-(y1-y2)*(x3*x3-x1*x1+y3*y3-y1*y1)) / (-2*(x1-x2)*(y1-y3)+2*(x1-x3)*(y1-y2));
		py = ((x1-x3)*(x2*x2-x1*x1+y2*y2-y1*y1)-(x1-x2)*(x3*x3-x1*x1+y3*y3-y1*y1)) / (-2*(x1-x3)*(y1-y2)+2*(x1-x2)*(y1-y3));
		r = sqrt((px - x1) * (px - x1) + (py - y1) * (py - y1));
		printf("%.3lf %.3lf %.3lf\n", px, py, r);
	}
	return 0;
}

Measured memory_bytes: 664
#include <stdio.h>

int main(void) {

  int n,k;
  scanf("%d %d", &n, &k);
  int a[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
  }
  int answer = (n-1+k-2)/(k-1);
  printf("%d\n", answer);

  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <array>
#include <tuple>
#include <string>
#include <algorithm>
#include <functional> // greater など
#include <cmath>      // abs など
#include <numeric>    // accumulate, gcd など
#include <cassert>    // assert
#include <stdexcept>
#include <bitset>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (a); i < (int)(b); i++)
typedef long long ll;

//////////////// //////////////// //////////////// //////////////// ////////////////
//////////////// //////////////// //////////////// //////////////// ////////////////

// constexpr inline ll mod = 1'000'000'007;
// constexpr int max_n = 200'000 + 5;

int main()
{
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(15); // 浮動小数の表示の精度

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

    return 0;
}


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

vector<long long>vp;

long long dp[410][410];
long long dpp(int i,int j)

{
  if(i>j)
  return 0;
  if(j==i)
  return 0;

  if(dp[i][j]!=-1)
  return dp[i][j];

 long long ans=1e20;
  for(int x=i;x<j;x++)
  {
    ans=min(ans,vp[j]-vp[i-1]+dpp(i,x)+dpp(x+1,j));
  }

return dp[i][j]=ans;
}
int main()
{

    memset(dp,-1,sizeof dp);
    int n;
    cin>>n;
    long long sum=0;
    vp.push_back(0);
    for(int i=1;i<=n;i++)
    {
      int a;
      cin>>a;
      sum+=a;
      vp.push_back(sum);

    }
    cout <<dpp(1,n);
}






Measured memory_bytes: 1536
N=int(input())
A=list(input())
B=list(input())
C=list(input())
a=0
for i in range(N):
    if A[i]!=B[i] and B[i]!=C[i] and C[i]!=A[i]:
        a+=2
    elif A[i]==B[i] and B[i]==C[i]:
        a+=0
    else:
        a+=1
print(a)

Measured memory_bytes: 9136
<?php

fscanf(STDIN, "%d %d %d", $a, $b, $c);

$daily = 0;
$min_login = 0;

while ($c > 0) {
    $daily++;
    if ($daily == 7) {
        $c -= $b;
        $daily = 0;
    }
    
    $c -= $a;
    $min_login++;
}

echo $min_login."\n";
?>


Measured memory_bytes: 9192
#include <iostream>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
long long a[200010],f[200010],k,ans;
int n;
bool cmp(int a,int b)
{
	return a>b;
}
bool check(long long x)
{
	long long tot=0;
	for (int i=1;i<=n;++i)
		if (f[i]*a[i]>x) tot+=ceil((f[i]*a[i]-x)/(double)f[i]);
	if (tot<=k) return 1;else return 0;
}
void search(long long l,long long r)
{
	if (l>r) return;
	long long mid=(l+r)>>1;
	if (check(mid))
	{
		ans=mid;
		search(l,mid-1);
	}
	else search(mid+1,r);
}
int main()
{
	long long max=0;
	cin>>n>>k;
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=n;++i) scanf("%d",&f[i]);
	sort(a+1,a+n+1);sort(f+1,f+n+1,cmp);
	for (int i=1;i<=n;++i) if (f[i]*a[i]>max) max=f[i]*a[i];
	search(0,max);
	cout<<ans<<endl;
 	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ce continue
#define Rep(i,a,b) for(int i=a;i<=b;i++)
#define rep1(i,n) Rep(i,1,n)
#define rep(i,n) Rep(i,0,n-1)
int n,a[2222],sum;
int q,w,mid;
int main(){
	cin>>n;
	rep(i,n)
		cin>>a[i];
	sort(a,a+n);
	rep(i,n){
		Rep(j,i+1,n-1){
			q=j;
			w=n;
			while(q+1<w){
				mid=(q+w)/2;
				if(a[mid]<a[i]+a[j])
					q=mid;
				else
					w=mid;
			}
			sum=sum+w-j-1;
		}
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        String t = scanner.next();

        ArrayList<String> aL = new ArrayList<>();

        for (int i = 0; i <= s.length() - t.length(); i++) {
            aL.add(s.substring(i, i + t.length()));
        }

        int ir = 0;

        for (String a : aL) {
            int c = 0;
            for (int i = 0; i < t.length(); i++) {
                if (a.charAt(i) == t.charAt(i)) {
                    c += 1;
                    if (ir > c) {
                      continue;
                    }
                }
                if (ir < c) {
                  ir = c;
                }
            }
        }

        System.out.println(t.length() - ir);
    }
}


Measured memory_bytes: 36416
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <numeric>

using namespace std;

#define int long long
typedef long double ld;
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define vpii vector<pii>
#define vb vector<bool>
#define vbb vector<vb>
#define vs vector<string>
#define pb push_back
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define in(a, x) for (int i = x; i < (a).size(); ++i) cin >> (a)[i]
#define out(a) for (auto qwe : a) cout << qwe << " "

const int INF = 1e9;
const int INF64 = 1e18;
const int MOD = 1e9 + 7;
const int MOD9 = 1e9 + 9;
const int MOD3 = 998244353;
const int P = 37;

const int mxn = 200000;

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

    int n, k;
    cin >> n >> k;

    vi a(n + 1);
    in(a, 1);

    vii dp(n + 1, vi(k + 1, 0));
    vii p(n + 1, vi(k + 1, 0));

    dp[0][k] = 1;
    p[0][k] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= k; ++j) {
            dp[i][j] = p[i - 1][min(k, j + a[i])] - (j > 0 ? p[i - 1][j - 1] : 0) + MOD;
            dp[i][j] %= MOD;

            if (j > 0)
                p[i][j] = p[i][j - 1];
            p[i][j] += dp[i][j];
            p[i][j] %= MOD;
        }
    }

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


Measured memory_bytes: 159088
#include <stdio.h>

int main(void)
{
	int x1,x2,a;
	scanf("%d %d",&x1,&x2);
	if(0<=x1 && x2<=100){
		if(x1<x2){
			a=x2-x1;
			printf("%d\n",a);
		}
		else{
			a=x1-x2;
			printf("%d\n",a);
		}
	}
	else{
		printf("error\n");
	}
	return 0;
}


Measured memory_bytes: 2116
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> L(N);
  int S = 0;
  for(int i=0;i<N;++i){
    cin >> L.at(i);
  }
  sort(L.begin(),L.end());
  for(int i=0;i<N-2;++i){
    for(int j=i+1;j<N-1;++j){
      for(int k=j+1;k<N;++k){
      if(L.at(k)<L.at(i)+L.at(j)){
        ++S;
       }
      }
    }
  }
   cout<<S<<endl;
}

Measured memory_bytes: 256