akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <utility>
#include <set>
#include <algorithm>
#define llint long long
#define mod 1000000007

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

llint n, Q;
vector<E> vec;
multiset<llint> S;

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

  cin >> n >> Q;
	llint s, t, x;
	for(int i = 1; i <= n; i++){
		cin >> s >> t >> x;
		t--;
		s-=x, t -= x;
		vec.push_back(E(P(s, 0LL), x));
		vec.push_back(E(P(t, 2LL), x));
	}
	for(int i = 1; i <= Q; i++){
		cin >> x;
		vec.push_back(E(P(x, 1LL), 0LL));
	}
	sort(vec.begin(), vec.end());

	for(int i = 0; i < vec.size(); i++){
		llint t = vec[i].first.second;
		if(t == 0) S.insert(vec[i].second);
		if(t == 2) S.erase(S.lower_bound(vec[i].second));
		if(t == 1){
			if(S.size() == 0) cout << -1 << endl;
			else cout << *S.begin() << endl;
		}
	}

  return 0;
}


Measured memory_bytes: 26984
def BubbleTrump(C, N):
    i = 0
    while i < N:
        j = N - 1
        while j > i:
            if int(C[j][1]) < int(C[j-1][1]):
                c = C[j]
                C[j] = C[j - 1]
                C[j - 1] = c
            j -= 1
        i += 1
    return C

def SelectionTrump(C, N):
    i = 0
    while i < N:
        minj = i
        j = i
        while j < N:
            if int(C[j][1]) < int(C[minj][1]):
                minj = j
            j += 1
        if minj != i:
            c = C[i]
            C[i] = C[minj]
            C[minj] = c
        i += 1
    return C

n = int(input())
C = list(map(str, input().split(' ')))
ans = ''
Cb = BubbleTrump(C.copy(), n)
ans += ' '.join(map(str, Cb)) + '\nStable\n'
Cs = SelectionTrump(C.copy(), n)
q = 0
f = 1
while q < n:
    if Cb[q] != Cs[q]:
        f = 0
    q += 1
ans += ' '.join(map(str, Cs)) + '\n'
if f == 0:
    ans += 'Not stable'
else:
    ans += 'Stable'
print(ans)


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

int main() {
  
  int N;
  cin >> N;
  
  vector<int> p(N);
  for ( int i = 0; i < N; i++){
    cin >> p.at(i);
  }
  
  int count = 0;
  
  
  for ( int i = 1; i < N - 1; i++){
    if ( ((p.at(i-1) < p.at(i)) && (p.at(i) < p.at(i+1))) || ((p.at(i-1) > p.at(i)) && (p.at(i) > p.at(i+1))) ){
      count++;
    }
  }
  
  cout << count << endl;
       
}

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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	int ans=0;
	for(int i=1;i<=n;i+=2){
		int a=i,cnt=1;
		for(int j=2;j<=n;++j){
			if(a%j==0)++cnt;
		}
		if(cnt==8)++ans;
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#define INF 1000000000000000LL
using namespace std;
struct edge {int to; long long int cost; };
int main()
{
	int n, m, l, r;
	long long int d, x[100000];
	scanf("%d %d", &n, &m);
	vector<edge> v[100000];
	for(int i=0; i<m; i++){
		scanf("%d %d %lld", &l, &r, &d);
		l--;
		r--;
		edge e;
		e.to=r, e.cost=d;
		v[l].push_back(e);
		e.to=l, e.cost=-d;
		v[r].push_back(e);
	}
	queue<int> que;
	set<int> st;
	for(int i=0; i<n; i++){
		x[i]=INF;
		st.insert(i);
	}
	while(!st.empty()){
		auto itr=st.begin();
		int n0=*itr;
		que.push(n0);
		x[n0]=0;
		while(!que.empty()){
			int k=que.front();
			que.pop();
			if(st.find(k)==st.end()) continue;
			st.erase(k);
			for(int i=0; i<v[k].size(); i++){
				edge e=v[k][i];
				if(x[e.to]==INF){
					x[e.to]=x[k]+e.cost;
				}else if(x[e.to]!=x[k]+e.cost){
                  printf("%s\n", "No");
					return 0;
				}
				que.push(e.to);
			}
		}
	}
	printf("%s\n", "Yes");
	return 0;
}

Measured memory_bytes: 18432
#include <bits/stdc++.h>
const int INF=1e9;
const int MOD=998244353;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int pw(int n,int k){
  int res=1;
  while(k){
    if(k&1)res*=n;res%=MOD;
    n*=n;n%=MOD;
    k>>=1;
  }
  return res;
}
std::vector<int> Factorial(1e6),Finverse(1e6);
void Cinit(){
  Factorial[0]=1;
  for(int i=1;i<1e6;i++)Factorial[i]=Factorial[i-1]*i%MOD;
  for(int i=0;i<1e6;i++)Finverse[i]=pw(Factorial[i],MOD-2);
}
int nCk(int n,int k){
  if(n<k)return 1;
  if(k<0)return 0;
  int res=Factorial[n];
  res*=Finverse[k];res%=MOD;
  res*=Finverse[n-k];res%=MOD;
  return res;
}
int m(int a){
  a%=MOD;a+=MOD;a%=MOD;
  return a;
}
//main
signed main(){
  int K,N;cin>>K>>N;
  Cinit();
  std::vector<int> oused(2*K,0),eused(2*K,0);
  oused[0]=nCk(N+K-1,K-1);
  eused[1]=m(nCk(N+K-3,K-2)+nCk(N+K-2,K-2));
  for(int i=2;i<=2*K;i++){
    int sz;
    int n=i/2;
    if(i&1){
      sz=min(n,K-n);
      if(oused[sz]){cout<<oused[sz]<<endl;continue;}
      int res=0;
      int ares=0;
      for(int a=0;a<=sz-1;a++){
        int waku=N-a-2;
        int dame=2*(sz-1)-a;
        int saku=K-dame-1;
        if(waku<0||saku<0)continue;
        ares=nCk(waku+saku,saku);
        ares*=nCk(sz-1,a);ares%=MOD;
        ares*=pw(2,a);ares%=MOD;
        res+=ares;res%=MOD;
      }
      oused[sz]=m(oused[sz-1]-res);
      cout<<oused[sz]<<endl;
    }
    else{
      sz=min(n,K-n+1);
      if(eused[sz]){cout<<eused[sz]<<endl;continue;}
      int res=0;
      int ares=0;
      for(int a=1;a<=sz-1;a++){
        int waku=N-a-2;
        int dame=2*(sz-1)-1-(a-1);
        int saku=K-dame-1;
        //cout<<waku<<" "<<saku<<endl;
        if(waku<0||saku<0)continue;
        ares=nCk(waku+saku,saku);
        ares*=nCk(sz-1-1,a-1);ares%=MOD;
        ares*=pw(2,a-1);ares%=MOD;
        res+=ares;res%=MOD;
      }
      for(int a=0;a<=sz-1-1;a++){
        int waku=N-a-2;
        int dame=2*(sz-1)-1-a;
        int saku=K-dame-1;
        //cout<<waku<<" "<<saku<<endl;
        if(waku<0||saku<0)continue;
        ares=nCk(waku+saku,saku);
        ares*=nCk(sz-1-1,a);ares%=MOD;
        ares*=pw(2,a);ares%=MOD;
        res+=ares;res%=MOD;
      }
      //cout<<i<<" "<<res<<endl;
      eused[sz]=m(eused[sz-1]-res);
      cout<<eused[sz]<<endl;
    }
  }
}


Measured memory_bytes: 16000
import java.util.*;
import java.awt.geom.*;
import java.io.*;

public class Main{
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();
			int s = sc.nextInt();
			int w = sc.nextInt();
			int q = sc.nextInt();
			if((n|s|w|q) == 0) break;
			int [] a = create(s, w, n);
			int ans = 0;
			if(q == 2 || q == 5){
				int count = 0;
				for(int i = 0; i < n; i++){
					if(a[i] != 0){
						count++;
					}
					if(a[i] % q == 0){
						ans += count;
					}
				}
			}
			else{
				HashMap<Long, Integer> freq = new HashMap<Long, Integer>();
				freq.put(0L, 1);
				long now = 0, digitUp = 1;
				for(int i = n - 1; i >= 0; i--){
					now = (a[i] * digitUp + now) % q;
					digitUp = (digitUp * 10) % q;
					if(a[i] != 0 && freq.containsKey(now)){
						ans += freq.get(now);
					}
					if(freq.containsKey(now)){
						freq.put(now, freq.get(now) + 1);
					}
					else{
						freq.put(now, 1);
					}
				}
			}
			System.out.println(ans);
		}
	}

	private int[] create(int s, int w, int n) {
		int [] a = new int[n];
		int g = s;
		for(int i = 0; i < n; i++){
			a[i] = (g / 7) % 10;
			if(g % 2 == 0){
				g = (g / 2);
			}
			else{
				g = (g / 2) ^ w;
			}
		}
		return a;
	}

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

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

Measured memory_bytes: 98356
#include <bits/stdc++.h>
using std::cerr;using std::cin;using std::cout;using std::abs;using std::min;using std::max;using std::swap;using std::map;using std::unordered_map;using std::unordered_set;using std::bitset;using std::pair;using std::set;using std::string;using std::vector;using std::sort;using ll=long long;using uint=unsigned int;using pii=pair<int,int>;using pll=pair<ll,ll>;using ull = unsigned long long;using ld=long double;template<typename T>void _(const char*s,T h){cerr<<s<<" = "<<h<<"\n";}template<typename T,typename...Ts>void _(const char*s,T h,Ts...t){int b=0;while(((b+=*s=='(')-=*s==')')!=0||*s!=',')cerr<<*s++;cerr<<" = "<<h<<",";_(s+1,t...);}// break continue pop_back 998244353
#define int ll
#define pii pll
#define f first
#define s second
#define pb emplace_back
#define forn(i,n) for(int i=0;i<(n);++i)
#define sqr(x) ((x)*(x))
struct init{init(){cin.tie(0);std::iostream::sync_with_stdio(0);cout<<std::fixed<<std::setprecision(10);cerr<<std::fixed<<std::setprecision(5);}~init(){
#ifdef LOCAL
#define dbg(...) _(#__VA_ARGS__,__VA_ARGS__)
cerr<<"Time elapsed: "<<(double)clock()/CLOCKS_PER_SEC<<"s.\n";
#else
#define dbg(...) 
#endif
}}init;template<typename T,typename U>void upx(T&x,U y){if(x<y)x=y;}template<typename T,typename U>void upn(T&x,U y){if(x>y)x=y;}
const int N=2019,M=1e9+7;
int a[N];

int32_t main(){

    int n,k;
    cin>>n>>k;
    int ans=0;
    forn(i,n){
        cin>>a[i];
        forn(j,i){
            if(a[i]>a[j]){
                ans+=((k-1)*k)/2;
            }else if(a[i]<a[j]){
                ans+=(k*(k+1))/2;
            }
            ans%=M;
        }
    }
    cout<<ans<<'\n';

    return 0;
}


Measured memory_bytes: 256
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast static int fastline = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debugg cout<<"debugged\n";
#define setpr(xval) cout<<fixed<<setprecision(12)<<xval<<endl;
#define minval -2e9
#define maxval 2e9
long double PI =3.14159265358979323846;
 
const ll M=1e9+7;
const ll inf=1e18;
const ll ms=2e5+5;
fast;
ll n,k;
void solve()
{
   cin>>n;
   map<ll,ll>mp;
   while(mp[n]!=1)
   {
       mp[n]=1;
       if(n%2)
        n=3*n+1;
        else
            n/=2;
        k++;
        //cout<<n<<endl;
   }
   cout<<k+1<<endl;
}

int main()
{
 // freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    //int t;cin>>t;while(t--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <memory.h>
#include <queue>
#include <string.h>
#include <set>
using namespace std;

#define N 100005
#define M 20
#define mod 1000000007

int x[N],dp[N][M];
int jumpCity(int stCity,int day) {
  int curCity = stCity;
  for(int i=0;i<M;++i) {
    if(day&(1<<i)) {
      curCity = dp[curCity][i];
    }
  }
  return curCity;
}
void solve() {
  int n;scanf("%d ", &n);
  for(int i=1;i<=n;++i) {
    scanf("%d ", &x[i]);
  }
  int L;scanf("%d ", &L);
  for(int i=0;i<M;++i) {
    dp[n+1][i] = n+1;
    dp[n][i] =n+1;
  }
  int lastCity = n;
  int dist = x[n] - x[n-1];
  for(int i=n-1;i>=1;--i) {
    while(dist>L) {
      dist -= x[lastCity] - x[lastCity-1];
      --lastCity;
    }
    dp[i][0] = lastCity;
    for(int j=1;j<M;++j) {
      dp[i][j] = dp[dp[i][j-1]][j-1];
    }
    dist += x[i] - x[i-1];
  }
  int q;scanf("%d ", &q);
  while(q--) {
    int a,b;scanf("%d %d ", &a,&b);
    if(a>b) {
      swap(a,b);
    }
    int l = 1,r = n,mid;
    while(l<r) {
      mid = (l+r)/2;
      int arrived = jumpCity(a,mid);
      if(b<=arrived) {
        r = mid;
      } else {
        l = mid+1;
      }
    }
    printf("%d\n", l);
  }
}

int main() {
  //freopen("input.txt","r",stdin);
  solve();
  return 0;
}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fr(i, n) for (int i = 0; i < (int)n; i++)
#define frab(i, a, b) for (int i = a; i < b; i++)

using namespace std;

typedef long long ll;
typedef long double ld;

const ll INF = 2e8 + 10;
const ld PI = acos(-1);
const ld EPS = 1e-9;
const ll MOD = 1e9 + 7;
const int M = 1003;
const int N = 1e6 + 10;



int main() {
    //freopen("a.in", "r", stdin);
    int n;
    cin >> n;
    ll s = 0;
    fr(i, n) {
        int l, r;
        cin >> l >> r;
        s += (r - l + 1);
    }
    cout << s;
}


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

int	main(void)
{
  	int	N;
  	int	K;
  	int	A[200001];
  	int	B[200001];
	int	num;
  	int	i;
  	int	max;
  	int	tmp;
  
  	num = scanf("%d %d\n", &K, &N);
  	if (num != 2)
      	return (0);

  	for (i=0; i<N; i++)
  	{
      	num = scanf("%d", &A[i]);
  	}

  	for (i=0; i<N; i++)
    {
      	B[i] = A[(i+1) % N] - A[i % N];
      	if (B[i] < 0)
      	{
          	B[i] = B[i] + K;
      	}
    }

  	max = 0;
  	tmp = 0;
  	for (i=0; i<N; i++)
    {
      	if (max < B[i])
        {
          	max = B[i];
      		tmp = i;
        }
    }
  
  	printf("%d", K - max);
  	return (0);
}

Measured memory_bytes: 1664
#include <iostream>
#include <fstream>
#include <queue>
#include <list>
//#define LOCAL
using namespace std;
typedef long long ll;
const int mx=1e3+10;
list<ll>l[mx];
int main() {
#ifdef LOCAL
ifstream fin("1.txt");
streambuf*p;
p=cin.rdbuf(fin.rdbuf());
#endif // LOCAL
ll n, q;
cin>>n>>q;
for(ll i=1;i<=q;i++){
    ll t, sub, value, sub2;
    cin>>t;
    switch(t){
        case 0: cin>>sub>>value;
            l[sub].push_back(value);
            break;
        case 1: cin>>sub;
            for(list<ll>::iterator it=l[sub].begin();it!=l[sub].end();it++){
                if(l[sub].begin()==it) printf("%lld", *it);
                else printf(" %lld", *it);
            }
            puts("");
            break;
        case 2: cin>>sub>>sub2;
            l[sub2].splice(l[sub2].end(), l[sub]);
            l[sub].clear();
            break;
    }


}

#ifdef LOCAL
fin.close();
#endif // LOCAL
}




Measured memory_bytes: 18764
n,T[101],M[101][4][4];int D(d,a,b){
if(d==n+1)return 1;
if(T[d])return T[d]!=a||T[d]!=b?D(d+1,T[d],a):0;
int i=1,s=0;
for(;i<=3;i++)if(i!=a||i!=b){
	if(!M[d+1][i][a])M[d+1][i][a]=D(d+1,i,a)%10000;
	s+=M[d+1][i][a];
}
return s;}
main(k,x,y){for(scanf("%d%d",&n,&k);k;k--)scanf("%d%d",&x,&y),T[x]=y;printf("%d\n",D(1,0,0)%10000);exit(0);}

Measured memory_bytes: 604
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#include<set>
#include<map>
#include<unordered_map>
#include<stack>
#include<queue>
#include<string>
#include<cmath>
#include<climits>
using namespace std;

int main() {
    int n, W;
    cin>>n>>W;
    vector<int> w(n),v(n);
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    vector<vector<long long>> dp(W+1, vector<long long> (n+1,0));
    for(int i=1;i<=W;i++) {
        for(int j=1;j<=n;j++) {
            if(i<w[j-1])
                dp[i][j] = dp[i][j-1];
            else 
                dp[i][j] = max(dp[i][j-1], v[j-1]+dp[i-w[j-1]][j-1]);
        }
    }
    cout<<dp[W][n];
}


Measured memory_bytes: 85196
#define _USE_MATH_DEFINES
#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define MT make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define RT return
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;

void solve() {
    int N;
    cin >> N;
    rep(i, N - 1) {
        FOR(j, i + 1, N) {
            int x = i ^ j;
            int res = 1;
            while (!(x & 1)) {
                res++;
                x >>= 1;
            }
            cout << res << (j != N - 1 ? ' ' : '\n');
        }
    }
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}

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

int main(){
    string s;
    cin >> s;
    int count = 0;
    int r = 0,l = s.length()-1;
    for(int i = 0; i<s.length()/2;i++){
    if(s[r] != s[l]) count++;
    r++;l--;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <set>
#include <utility>
#define mem(a,b) memset(a,b,sizeof(a))
#define inf 0x3f3f3f3f
#define IO ios::sync_with_stdio(false);
#define ll long long
#define pb push_back
using namespace std;
const double PI=acos(-1.0);
const int N=2e6+10;
const ll mod=1e9+7;
ll a[N];
map<ll,ll>mpl;
map<ll,ll>mpr;
void sovle()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        mpl[i-a[i]]++;
        mpr[i+a[i]]++;
    }
    ll ans=0;
    for(int i=0;i<n;i++)
    {
        int cur1=mpr[i-a[i]];
        int cur2=mpl[i+a[i]];
        ans+=cur1+cur2;
    }
    ans/=2;
    cout<<ans<<endl;
}
int main()
{
//    int t;
//    cin>>t;
//    while(t--)
//    {
        sovle();
//    }
    return 0;
}


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

using namespace std;

int main(){
	
	int N, K;

	cin >> N >> K;

	bool taboo[10] = {};

	for(int i = 0; i < K; i++){
		int num;
		cin >> num;
		taboo[num] = true;
	}

	int ans;

	for(int i = N; i < 1000000; i++){
		int num = i;
		bool flag = true;
		while(num > 0){
			if(taboo[num % 10]){
				flag = false;
				break;
			}
			num /= 10;
		}
		if(flag){
			ans = i;
			break;
		}
	}

	cout << ans << endl;
	
	return 0;
}



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

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

    int *v = new int[n];
    int *cost = new int[n];

    for(int i = 0; i < n; i++)
        cin >> v[i];

    cost[0] = 0;
    cost[1] = abs(v[1] - v[0]) + cost[0];
    for(int i = 2; i < n; i++)
        cost[i] = min((abs(v[i]-v[i-1])+cost[i-1]),(abs(v[i]-v[i-2])+cost[i-2]));

    cout << cost[n-1];

    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define debug(x) cerr << #x << " " << x << '\n'
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
const int INF = 0x3f3f3f3f, N = 2e5 + 5;
const ll LINF = 1e18 + 5;

int main()
{
 	ios::sync_with_stdio(false);
 	cin.tie(0);
 	int x, y;
 	cin >> x >> y;
 	int ans = 0;
 	if(x==1) ans += 300000;
 	else if(x==2) ans += 200000;
 	else if(x==3) ans += 100000;
 	if(y==1) ans += 300000;
 	else if(y==2) ans += 200000;
 	else if(y==3) ans += 100000;
 	if(x==1&&y==1) ans += 400000;
 	cout << ans;
	return 0;
}


Measured memory_bytes: 256
/* 他の方の提出を参考に */
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

typedef std::uint64_t u64;
typedef std::int64_t  i64;
typedef std::uint32_t u32;
typedef std::int32_t  i32;

using namespace std;

#define swap(a, b)    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while(0)
#define repd(i, a, b) for(typeof(b) i = a; i < (b); ++i)
#define rep(i, n)     repd(i, 0, n)
#define dump(x)       cerr << #x << " = " << (x) << endl
#define debug(x)      cerr << "L" << __LINE__ << ": " << #x << " = " << (x) << endl

int main(int argc, const char* argv[]) {
  u64 n, k, a[100000];
  u64 bits[40] = {0};
  cin >> n >> k;
  
  rep(i, n) {
    cin >> a[i];
    rep(j, 40) {
      u64 msk = 0x0000008000000000 >> j;
      if((a[i] & msk) != 0) {
        ++bits[j];
      }
    }
  }
  
  u64 x = 0;
  rep(i, 40) {
    if( (bits[i] <= n / 2) && (x | (0x0000008000000000 >> i)) <= k ) {
      x |= 0x0000008000000000 >> i;
    }
  }
  
  u64 ret = 0;
  rep(i, n) {
    ret += (x ^ a[i]);
  }
  
  cout << ret << endl;
  
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll r;
    cin >> r;
    cout << setprecision(15) << pi * r * 2 << endl;
}  

Measured memory_bytes: 3772
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int h=sc.nextInt(),w=sc.nextInt(),k=sc.nextInt(),ans=0,sum=0;
    char[][] ch=new char[h][w];
    for(int i=0;i<h;i++){
      ch[i]=sc.next().toCharArray();
      for(int j=0;j<w;j++){
        if(ch[i][j]=='#'){
          ans++;
          
        }
      }
    }
    for(int i=0;i<(Math.pow(2,h+w));i++){
      int f=ans;
      char[][] fch=new char[h][w];
      for(int x=0;x<h;x++){
        for(int y=0;y<w;y++){
          fch[x][y]=ch[x][y];
        }
      }
      for(int j=0;j<(h+w);j++){
        if((1&i>>j)==1){
          if(j<h){
            for(int l=0;l<w;l++){
              if(fch[j][l]=='#'){
                fch[j][l]='.';
                f--;
              }
            }
          }else{
            for(int l=0;l<h;l++){
              if(fch[l][j-h]=='#'){
                fch[l][j-h]='.';
                f--;
              }
            }
          }
        }
      }
      if(f==k){
        sum++;
      }
    }
    System.out.println(sum);
  }
}




Measured memory_bytes: 38360
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0549
#include<vector>
#include<iostream>
#include<cmath>
using namespace std;
//宿場町はn個　m日間
int n, m, pos = 0, a;
long long ans = 0;
long long t[100000];
int main()
{
	cin >> n >> m;
	t[0] = 0;
	//累積和
	for (int i = 1; i < n; i++)
	{
		cin >> t[i];
		t[i] += t[i - 1];
	}
	pos = 0;
	for (int i = 0; i < m; i++)
	{
		cin >> a;
		ans += abs(t[pos] - t[pos + a]);
		ans %= 100000;
		pos += a;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3860
import qualified Data.ByteString.Char8 as C
import qualified Data.Vector.Unboxed as V

main = C.interact $ put . sol . get

get = V.unfoldr (C.readInt . C.dropWhile (<'0'))

put = C.pack . unwords . map show . V.toList

sol v = V.generate n ((u V.!) . f)
  where
  n = V.head v
  u = V.tail v
  f i = abs (2*i-n) - if i<(n+1) `div` 2 then 1 else 0

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

int main()
{
	int Table[128][128], RSum[128], CSum[128];
	int R, C;
	cin >> R >> C;
	for(int i = 0; i < R; ++i)
	{
		for(int j = 0; j < C; ++j)
		{
			cin >> Table[i][j];
			CSum[j] = 0;
		}
		RSum[i] = 0;
	}
	
	for(int i = 0; i < R; ++i)
	{
		for(int j = 0; j < C; ++j)
		{
			cout << Table[i][j] << " ";
			RSum[i] += Table[i][j];
			CSum[j] += Table[i][j];
		}
		cout << RSum[i] << endl;
	}
	
	int sum = 0;
	for(int i = 0; i < C; ++i)
	{
		cout << CSum[i] << " ";
		sum += CSum[i];
	}
	cout << sum << endl;

    return 0;
}



Measured memory_bytes: 3120
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
##############################

N, M = map(int, input().split())
AB = []
for i in range(N):
    a, b = map(int, input().split())
    AB.append([a, b])

AB.sort()

ans = 0
for (yen, num) in AB:
    if num <= M:
        ans += (yen * num)
        M -= num
    else:
        ans += (yen * M)
        print(ans)
        exit()

print(ans)

Measured memory_bytes: 20072
#%%
n = int(input())
s = list(input())
num2alpha = lambda c: chr(c+65)
alpha2num = lambda c: num2alpha((ord(c) - ord('A')+ n)%26)

for i in range(len(s)):
    s[i] = alpha2num(s[i])
print(''.join(s))

#%%







# %%


Measured memory_bytes: 3316
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
int digit(int x) {
	int cnt = 0;
	while (x > 0) {
		cnt += x % 10;
		x /= 10;
	}
	return cnt;
}

signed main() {
	int n;
	cin >> n;
	int sum = 0;
	rep(i, n) {
		int a;
		cin >> a;
		sum += a;
	}
	cout << sum - (1 + n) * n / 2 << endl;

	return 0;
}



Measured memory_bytes: 3120
import java.util.Scanner;


class Main{

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int[][] A = new int [3][N+1];
		int count  =0 ;
		int ans = 0;

		for(int i = 1;i < 3;i++){
			for(int j = 1;j < N+1;j++){
				A[i][j] = scan.nextInt();
			}
		}
		

		for(int i= 1;i < N+1;i++){

			int x = 1;
			count=0;
			while(x <= i){
				count += A[1][x];
				x++;
			}
			x--;
			while(x <= N ){
				count += A[2][x];
				x++;
			}
			ans = Math.max(ans, count);
		}

		System.out.println(ans);

	}

	static int count(int a,int b,int c,int X){
		if(X == a*500+b*100+c*50){
			return 1;
		}else{
			return 0;
		}
	}


}
class Pair implements Comparable{
	int from;
	int end;

	public Pair(int a,int b) {
		this.from = a;
		this.end = b;

	}
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}



Measured memory_bytes: 23764
#include <iostream>
#include <stack>
#define int long long
using namespace std;
stack<int>s[1010];
int n, q, t, x;
signed main() {
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		cin >> n >> t;
		if (!n) {
			cin >> x;
			s[t].push(x);
		}
		else if (n == 1 && s[t].size()) cout << s[t].top() << endl;
		else if(s[t].size())s[t].pop();
	}
}


Measured memory_bytes: 5048
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int mod = 1000000007;
#define ll long long

int main()
{
	string S; cin >> S;
	if (S.size() == 2) cout << S << endl;
	else {
		for (int i = 2; i >= 0; i--) {
			cout << S[i];
		}
		cout << endl;
	}
}

Measured memory_bytes: 256
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();;
        String c = sc.next();
        if (a.charAt(a.length() - 1) == b.charAt(0) && b.charAt(b.length() - 1) == c.charAt(0)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

Measured memory_bytes: 21844
#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <numeric>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

long long mod_pow(long long x, long long n) {
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fast_input() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main(void) {
    long long A, B, C, D; cin >> A >> B >> C >> D;
    long long LCM = lcm(C, D);
    cout << (B-A+1) - ((B/C + B/D - B/LCM) - ((A-1)/C + (A-1)/D - (A-1)/LCM)) << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

import sys
import math


debug = False

def log(text):
    if debug:
        print(text)

def parse_input(lines_as_string = None):

    global debug
    lines = []
    if lines_as_string is None:
        debug = False
        # for line in sys.stdin:
        #     lines.append(line)
        lines.append(input())
        lines.append(input())
    else:
        debug = True
        lines = [e for e in lines_as_string.split("\n")][1:-1]


    n = int(lines[0])
    p = [int(e) for e in lines[1].split(' ')]

    return (n, p)


def solve(n, p):


    result = [] 
    current_min = 200000 + 1
    current_min_index = None
    for i in range(n):

        if current_min < p[i]:
            pass
        else:
           current_min = p[i]
           current_min_index = i

        done = False
        for j in range(current_min_index, i+1):
            if p[i] <= p[j]:
                if j == i:
                    done = True
            else:
                break
        if done:
            result.append(i)


    return len(result)


def main():
    # 出力
    result = solve(*parse_input())
    if isinstance(result, list):
        print("%d %d" % (result[0], result[1]))
    else:
        print("%s" % result, sep='')

if __name__ == '__main__':

    main()

Measured memory_bytes: 26004
N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
cnt = 0


for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if (L[i] < L[j] + L[k]) and (L[i] != L[j] != L[k]):
                cnt += 1


print(cnt)



Measured memory_bytes: 9180
#!/usr/bin/env python3


def solv(n, m, a, s):
    a = sorted(a)
    s = sorted(s, key=lambda x: -x[1])
    i = 0
    sum0 = 0
    for (b, c) in s:
        if (i+b) < n and a[i+b] < c:
            sum0 += b*c
            i += b
        else:
            for _ in range(b):
                if i >= n:
                    return sum0
                elif c <= a[i]:
                    return sum0 + sum(a[i:])
                sum0 += c
                i += 1
    if i >= n:
        return sum0
    return sum0 + sum(a[i:])


if __name__ == '__main__':

    n, m = map(int, input().split())
    a = map(int, input().split())
    s = []
    for _ in range(m):
        b, c = map(int, input().split())
        s.append((b, c))

    ans = solv(n, m, a, s)

    print(ans)


Measured memory_bytes: 27736
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits>
#include <sstream>
#include <fstream>
#include <climits>
#include <map>
#include <numeric>
#include <functional>
#include <utility>

using namespace std;

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

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


Measured memory_bytes: 256
///A man can't be always right.
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#define endl '\n'
#define ll long long
#define pb push_back
#define ppb pop_back
#define pi 3.14159265358979323846264338327950288419716939937510
#define RUN_FAST ios::sync_with_stdio(false);
#define sz 200010
using namespace std;

int main()
{
    RUN_FAST;
    int a;
    cin >> a;
    cout << a+(a*a)+(a*a*a) << endl;
    return 0;

}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
ll MOD = 1000000007;
//ll INF = 21474836470000000;
ll INF = 100000000000000000;
long double EPS = 1e-11;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<ll>>;

ll modpow(ll a,ll n,ll m){//modpow(a,n,m) := a ^ n (mod m)
  ll res = 1;
  while(n > 0){
    if(n & 1)res = res * a % m;
    a = a * a % m;
    n >>= 1;
  }
  return res;
}

int main(){
    ll N;
    cin >> N;
    vector<ll> A(N),B(1000010,0);
    rep(i,N){
        cin >> A[i];
        ll n = A[i];
        for(ll j = 2;j * j <= A[i];j++){
            ll cnt = 0;
            while(n % j == 0){
                cnt++;
                n /= j;
            }
            B[j] = max(B[j],cnt);
            
        }
        if(n > 1){
            B[n] = max(B[n],(ll)1);
        }
    }
    ll lcm = 1;
    rep(i,1000010){
        lcm *= modpow(i,B[i],MOD);
        lcm %= MOD;
    }
    ll ans = 0;
    rep(i,N){
        ans += lcm * modpow(A[i],MOD-2,MOD);
        ans %= MOD;
    }
    cout << ans << endl;
}



Measured memory_bytes: 8192
#include <stdio.h>

int main (int argc,char **argv)
{
	int a,b;
	int k;
	scanf("%d%d",&a,&b); 
	k = a + b;

	if ((k % 3 == 0)|| (a % 3 == 0) || (b % 3 == 0))
	{
		printf("Possible\n");
	} 

	else
	{
		printf("Impossible\n");
	}

	return 0;
}

Measured memory_bytes: 128
M, D = map(int, input().split())

ans = 0
for m in range(1, M+1):
    for d in range(1, D+1):
        d1 = d % 10
        d10 = (d - d1) // 10
        if d1 < 2 or d10 < 2:
            continue
        if m == d1 * d10:
            ans += 1

print(ans)



Measured memory_bytes: 39024
def is_palin(s):
    return s == s[::-1]

S = input().strip()
N = len(S)


s1 = S[0:(N-1)//2]
s2 = S[(N+3)//2-1:]

if is_palin(S) and is_palin(s1) and is_palin(s2):
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3060
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>

using namespace std;
typedef long long ll;
#define INF int(1e9)
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define REPONE(i, n) for(int i = 1; i <= (int)(n); i++)
#define EACH(i, mp) for(auto i:mp)
#define FOR(i, m, n) for(int i = m;i < n;i++)


const int MAX_N = (int) 1e5;
int n, a[MAX_N];
int a_max = 0, a_medi = 0;

void solve() {
    int res = INF;
    int ans = 0;
    REP(i, n) {
        if (a[i] != a_max && res > abs(a_medi - a[i])) {
            ans = a[i];
            res = abs(a_medi - a[i]);
        }
    }
    printf("%d %d", a_max, ans);
}

int main() {
    cin >> n;
    REP(i, n) {
        cin >> a[i];
        a_max = max(a[i], a_max);
    }
    a_medi = a_max / 2;
    solve();
    return 0;
}

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

int main(){
	int n ; cin >> n ;
	vector<int> v(n) ;
	for(int i=0;i<n;i++) cin >> v.at(i) ;
	vector<int> c(n) ;
	for(int i=0;i<n;i++) cin >> c.at(i) ;
	int ans = 0 ;
	for(int i=0;i<n;i++) if(v.at(i)>c.at(i)) ans += v.at(i)-c.at(i) ;
	cout << ans << endl ;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#pragma warning(disable: 4996)
int H, W, a[2009][2009], b[2009][2009], minv = (1 << 30), maxv = -(1 << 30), ans = (1 << 30);
bool solve(int p) {
	int L = 0, R = 0;
	for (int i = 0; i < H; i++) {
		int l = 0, r = W;
		for (int j = 0; j < W; j++) {
			if (a[i][j] > minv + p) { r = j; break; }
		}
		for (int j = W - 1; j >= 0; j--) {
			if (a[i][j] < maxv - p) { l = j + 1; break; }
		}
		if (r < L || l > r)return false;
		L = max(L, l); R = r;
	}
	return true;
}
int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) { for (int j = 0; j < W; j++) { scanf("%d", &a[i][j]); minv = min(minv, a[i][j]); maxv = max(maxv, a[i][j]); } }
	for (int i = 0; i < 4; i++) {
		int L = 0, R = maxv - minv + 1, M, res = (1 << 30);
		for (int j = 0; j < 35; j++) {
			M = (L + R) / 2;
			if (solve(M) == true) { res = min(res, M); R = M; }
			else { L = M; }
		}
		ans = min(ans, res);
		for (int j = 0; j < H; j++) {
			for (int k = 0; k < W; k++) {
				b[W - 1 - k][j] = a[j][k];
			}
		}
		swap(H, W);
		for (int j = 0; j < H; j++) { for (int k = 0; k < W; k++)a[j][k] = b[j][k]; }
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 34636
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define frst first
#define sec second
#define fast cin.tie(0) , ios_base :: sync_with_stdio(0)
#define db double
#define mod 1000000007
void online_judge()
{
#ifndef ONLINE_JUDGE
	freopen("Input.txt", "r", stdin);
	freopen("Output.txt", "w", stdout);
#endif
}


ll lpp(string s)
{
	string rev = s;
	reverse(rev.begin() , rev.end());
	s = s + '#' + rev;
	////cout << s << " ";
	vector<ll> z(s.size() , 0);
	ll l = 0 , r = 0;
	for (int i = 1; i < s.size(); ++i)
	{
		if (i > r) {
			l = r = i;
			while (s[r] == s[r - l]) {
				r++;
			}
			z[i] = (r - l);
			r--;
		}
		else {
			if (z[i - l] + i <= r)z[i] = z[i - l];
			else {
				l = i;
				while (s[r] == s[r - l])r++;
				z[i] = (r - l);
				r--;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < s.size(); ++i)
	{
		if (z[i] + i == s.size()) {
			ans = max(ans , z[i]);
		}
	}
	return ans;
}

string binary(ll n)
{
	string s;
	while (n) {
		if ((n & 1))s += '1';
		else s += '0';
		n >>= 1;
	}
	reverse(s.begin() , s.end());
	return s;
}

bool pos(vector<ll> &v , ll val , ll painters)
{
	ll cur = 0;
	ll k = 1;
	for (int i = 0; i < v.size(); ++i)
	{
		if (v[i] > val)return 0;
		if (cur + v[i] <= val)cur += v[i];
		else {
			k++;
			cur = v[i];
		}
	}
	cout << k << endl;
	return (k <= painters);
}

class node {
	node* next;
	node* random;
	ll val;
	node(ll x)
	{
		next = random = NULL;
		val = x;
	}
};

ll dp[101][101][1001];

ll cal(ll a[] , ll cur , ll n , ll sum , ll c , ll tot)
{
	if (n == 0)
	{
		///cout << cur << " " << sum << " " << c << endl;
		if (cur == tot / 2)return abs((sum - c) - c);
		return 1e8;
	}
	if (dp[n][cur][c] != 1e8) {
		///cout << dp[n][cur][c] << " ";
		return dp[n][cur][c];
	}
	///cout << dp[n][cur][c] << " ";
	dp[n][cur][c] = cal(a , cur , n - 1 , sum , c , tot);
	dp[n][cur][c] = min(dp[n][cur][c] ,
	                    cal(a , cur + 1 , n - 1 , sum, c + a[n - 1] , tot));
	//cout << ans << endl;
	return dp[n][cur][c];
}


void go() {
	ll n;
	cin >> n;
	ll a[n];
	for (int i = 0; i < n; ++i)cin >> a[i];
	ll dp[n];
	//memset(dp , 0, sizeof dp);
	for (int i = 0; i < n; ++i)dp[i] = 1e8;
	dp[0] = 0;
	for (int i = 1; i < n; ++i)
	{
		dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]) , (i >= 2) ? dp[i - 2] + abs(a[i - 2] - a[i]) : (ll)1e8);
	}
	cout << dp[n - 1];
}


int main() {
	fast;
	//online_judge();
	go();
}


Measured memory_bytes: 1792
#include<string>
#include<iostream>
#include<vector>
#include<algorithm>

#define int long long
using namespace std;

int N, A[101010], B[101010];
int C[101010];


signed main()
{
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		cin >> B[i];
		C[i] = A[i] - B[i];
	}
	sort(C, C + N);
	
	int MIN=0;
	int n = 0;
	for (int i = 0; i<N; i++) {
		if (C[i] < 0) {
			MIN -= C[i];
			if (i == N - 1) {
				cout << "-1" << endl;
				return 0;
			}
		}
		else {
			n = i;
			break;
		}
	}
	int m;
	m = n;
	for (int i = N - 1; i >= m-1; i--) {
		if (MIN > 0) {
			MIN -= C[i];
			if (i == m - 1) {
				cout << "-1" << endl;
				return 0;
			}
		}
		else {
			n += N - 1 - i;
			break;
			
		}
	}
	cout << n << endl;



    return 0;
}



Measured memory_bytes: 2560
A = []
for i in range(3):
    Ai = [int(x) for x in input().split()]
    A.append(Ai)
    
N = int(input())

for i in range(N):
    bi = int(input())
    
    for j in range(3):
        if bi in A[j]:
            A[j][A[j].index(bi)] = 0
            
judge = False
for i in range(3):
    if A[i] == [0, 0, 0]:
        judge = True
    if A[0][i] == A[1][i] == A[2][i] == 0:
        judge = True
if A[0][0] == A[1][1] == A[2][2] == 0 or A[0][2] == A[1][1] == A[2][0] == 0:
    judge = True
    
if judge == True:
    print('Yes')
else:
    print('No')

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

int n, m;
int memo3[16] = {0,      1,      3,       9,
                 27,     81,     243,     729,
                 2187,   6561,   19683,   59049,
                 177147, 531441, 1594323, 4782969};
bool memo[15000000] = {0};
int from[4] = {0, 1, 1, 2};
int to[4] = {1, 0, 2, 1};
struct dish {
  vector<int> v[3];
  int now;
};
dish first;

int solve();
int calc3(dish x);

int main() {
  int a, x;
  while(1) {
    cin >> n >> m;
    if(n + m == 0) break;
    for(int i = 0; i < 3; ++i) {
      cin >> x;
      for(int j = 0; j < x; ++j) {
        cin >> a;
        first.v[i].push_back(a);
      }
    }
    first.now = 0;
    memo[calc3(first)] = 1;
    cout << solve() << endl;
    for(int i = 0; i < 3; ++i)
      first.v[i].erase(first.v[i].begin(),
                       first.v[i].end());
    for(int i = 0; i < 15000000; ++i) memo[i] = 0;
  }
  return 0;
}

int solve() {
  dish now = first, next;
  bool end = 0;
  int ans = -1;
  queue<dish> qu;
  qu.push(first);
  while(qu.size() > 0 && now.now <= m && !end) {
    now = qu.front();
    qu.pop();
    if(now.v[0].size() == n || now.v[2].size() == n) {
      ans = now.now;
      end = 1;
      break;
    }
    for(int i = 0; i < 4; ++i) {
      int f = from[i], t = to[i];
      next = now;
      if(next.v[f].size() != 0 &&
         (next.v[t].size() == 0 ||
          next.v[f][next.v[f].size() - 1] >
              next.v[t][next.v[t].size() - 1])) {
        int x = next.v[f][next.v[f].size() - 1], y;
        next.v[f].pop_back();
        next.v[t].push_back(x);
        ++next.now;
        y = calc3(next);
        if(memo[y] == 0) {
          qu.push(next);
          memo[y] = 1;
        }
      }
    }
  }
  return ans;
}
int calc3(dish x) {
  int ans = 0;
  for(int i = 0; i < 3; ++i) {
    for(int j = 0; j < x.v[i].size(); ++j)
      ans += i * memo3[x.v[i][j]];
  }
  return ans;
}


Measured memory_bytes: 17652
#define _CRT_SECURE_NO_WARNINGS
#include"bits/stdc++.h"
#ifdef _DEBUG
#define DBG(n) n
#else
#define DBG(n)
#endif
#define INF          1e9
#define INFLL        1e18
#define EPS          1e-9
#define MOD          1000000007
#define REP(i,n)     for(ll i=0,i##_len=(n);i<i##_len;++i)
#define REP1(i,n)    for(ll i=1,i##_len=(n);i<=i##_len;++i)
#define REPR(i,n)    for(ll i=(n)-1;i>=0;--i)
#define REPR1(i,n)   for(ll i=(n);i>0;--i)
#define REPC(i,obj)  for(auto i:obj)
#define ALL(obj)     (obj).begin(),(obj).end()
#define SETP(n)      cout<<fixed<<setprecision(n)
#define VV(T,h,w)    move(vector<vector<T>>(h,move(vector<T>(w))))
#define VVI(T,h,w,i) move(vector<vector<T>>(h,move(vector<T>(w,i))))
using namespace std;
using ll = long long;
template<typename T = ll>inline T in() { T ret; cin >> ret; return ret; }

int main()
{
	string s, t, u; cin >> s >> t >> u;
	cout << (char)(s[0] - 'a' + 'A') << (char)(t[0] - 'a' + 'A') << (char)(u[0] - 'a' + 'A') << endl;
}

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

#define WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 101

int n, M[MAX][MAX] = {0};
int color[MAX] = {0}, d[MAX] = {0}, f[MAX] = {0}, tt;
int nt[MAX];

int S[MAX] = {0};
int top = 0;

void initialise();
int isEmpty();
int isFull();
void push(int x);
int pop();
int isTop();

void initialise() {
	top = 0;
	return;
}

int isEmpty() {
	return top == 0;
}

int isFull() {
	return top >= MAX - 1;
}

void push(int x) {
	if (isFull()) {
		printf("over flow\n");
		exit(1);
	}
	top++;
	S[top] = x;
}

int pop() {
	if (isEmpty()) {
		printf("under flow\n");
		exit(1);
	}
	top--;
	return S[top+1];
}

int isTop() {
	return S[top];
}

int next(int u) {
	int v;
	for (v = nt[u]; v < n; v++) {
		nt[u] = v + 1;
		if (M[u][v]) return v;
	}
	return -1;
}

void dfs_visit(int r) {
	int i;
	for (i = 0; i < n; ++i) nt[i] = 0;
	
	initialise();
	push(r);
	color[r] = GRAY;
	d[r] = ++tt;

	while (!isEmpty()) {
		int u = isTop();
		int v = next(u);
		if ( v != -1) {
			if ( color[v] == WHITE) {
				color[v] = GRAY;
				d[v] = ++tt;
				push(v);
			}
		} else {
			pop();
			color[u] = BLACK;
			f[u] = ++tt;
		}
	}
}

void dfs() {
	int i;

	for (i = 0; i < n; ++i) {
		if ( color[i] == WHITE ) dfs_visit(i);
	}

	for (i = 0; i < n; ++i) {
		printf("%d %d %d\n", i + 1, d[i], f[i]);
	}
	
	tt = 0;
}

int main() {
	int i, j, u, k, v;

	scanf("%d", &n);

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

	dfs();
	
	return 0;
}

Measured memory_bytes: 636
#include "bits/stdc++.h"
#include <unordered_set>

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)
#define REP3(i, x, n) for(decltype(x) i = (x); i <= (n); i++)
#define RREP(i, n) for (decltype(n) i = (n) - 1;i >= 0; i--)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

#define LL long long int
#define LD long double

#define INF 1000000000
#define PI 3.14159265358979

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

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

typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<LL> vll;
//==============================================
int n;
vi A;

bool solve(int i, int m) {
	if (m == 0) return true;
	if (i >= n) return false;

	return (solve(i + 1, m) || solve(i + 1, m - A[i]));
}

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

	cin >> n; A.resize(n);
	REP(i, n) cin >> A[i];

	int q, m;
	cin >> q;
	REP(i, q) {
		cin >> m;
		cout << (solve(0, m) ? "yes" : "no") << "\n";
	}
	return 0;
}

Measured memory_bytes: 3228
<?php

$numbers = preg_split("/[\s,]+/", rtrim(fgets(STDIN)));
$wareki = $numbers[0];
$y = intval($numbers[1]);
$m = intval($numbers[2]);
$d = intval($numbers[3]);

while($wareki != '#'){
    if($y < 31) {
        print 'HEISEI' . ' ' . $y . ' ' .$m . ' ' .$d . "\n";
    } else if($y == 31){
        if ($m <= 4){
            print 'HEISEI' . ' ' . $y . ' ' .$m . ' ' .$d . "\n";
        } else {
            print '?' . ' ' . ($y - 30) . ' ' .$m . ' ' .$d . "\n";
        }
    } else {
        print '?' . ' ' . ($y - 30) . ' ' .$m . ' ' .$d . "\n";
    }

    $numbers = preg_split("/[\s,]+/", rtrim(fgets(STDIN)));
    $wareki = $numbers[0];
    if ($wareki != '#') {
        $y = intval($numbers[1]);
        $m = intval($numbers[2]);
        $d = intval($numbers[3]);
    }
}


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

using namespace std;
int main() {
	int n, m;
	while (cin >> n >> m && n) {
		vector<int> line(n);
		for (int i = 0; i < n; ++i) {
			cin >> line[i];
		}
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				if (i == j)continue;
				int sum = line[i] + line[j];
				if (sum > m)continue;
				ans = max(ans, sum);
			}
		}
		if (ans == 0) {
			cout << "NONE" << endl;
			continue;
		}
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 3016
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<numeric>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b));i>=((int)(a));i--)
typedef long long ll;
typedef pair<ll, ll> mp;
//LLONG_MIN

int main(void){
	int N,M,x,y,z;
	vector<int> v[1010];
	vector<int> c[1010];
	scanf("%d%d",&N,&M);
	rep(i,M){
		scanf("%d%d%d",&x,&y,&z);
		v[x].push_back(y);
		c[x].push_back(z);
	}
	ll s1[1010],s2[1010],t;
	reg(i,1,N)s2[i]=-(1e14+10);
	s2[1]=0;
	reg(cnt,1,3*N+2){
		reg(i,1,N)s1[i]=s2[i];
		reg(i,1,N){
			rep(j,v[i].size()){
				if(s2[v[i][j]]<s1[i]+c[i][j])s2[v[i][j]]=s1[i]+c[i][j];
			}
		}
		if(cnt==N-1)t=s2[N];
	}
	if(s2[N]>t){
		printf("inf\n");
	}else{
		printf("%lld\n",s2[N]);	
	}
	return 0;
}

Measured memory_bytes: 384