akhauriyash/Code-Regression huggingface dataset:
def main():
    num = int(input())
    data = list(map(int, input().split()))

    l, c, r = 1, 2, 3
    P = sum(data[:l])
    Q = sum(data[l:c])
    R = sum(data[c:r])
    S = sum(data[r:])

    ans = max(P, Q, R, S) - min(P, Q, R, S)

    while c <= num-2:
        while True:
            if abs(P-Q) < abs((P+data[l])-(Q-data[l])):
                break

            if l == c-1:
                break

            P += data[l]
            Q -= data[l]
            l += 1

        while True:
            if abs(R-S) < abs((R+data[r])-(S-data[r])):
                break
            if r == num-1:
                break

            R += data[r]
            S -= data[r]
            r += 1

        ans = min(max(P,Q,R,S)- min(P,Q,R,S), ans)

        # centerについて調整
        Q += data[c]
        R -= data[c]
        c += 1

    print(ans)

if __name__ == '__main__':
    main()


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

int main() {
int n,k,a;
cout << fixed << setprecision(10);
cin>>n>>k;
double b[n];
double counter=0;
double counter1=0;
for(int i=0;i<n;i++){
cin>>b[i];
b[i]=(b[i]+1)/2;}
for(int i=0;i<k;i++){
counter+=b[i];}
counter1=counter;
for(int i=0;i<n-k;i++){
counter=counter+b[i+k]-b[i];
counter1=max(counter,counter1);}
cout<<counter1<<endl;}


Measured memory_bytes: 1792
(defun princ-list (lst)
  (princ (car lst))
  (if (cdr lst) (progn (princ " ") (princ-list (cdr lst)))))
(let* ((n (read))
       (m (read))
       (lst nil))
  (setf lst (loop :for k :from (- m (1- n)) :upto (+ m (1- n)) :collect k))
  (princ-list lst))

Measured memory_bytes: 11880
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define UP(a,b,c) for(ll (a)=(b);(a)<(c);(a)++)
#define UU(a,b,c) for(ll (a)=(b);(a)<=(c);(a)++)
#define DN(a,b,c) for(ll (a)=(b);(a)>(c);(a)--)
#define DU(a,b,c) for(ll (a)=(b);(a)>=(c);(a)--)

ll n, x, m;
ll flag[100005] = {0}, at[100005] = {0};

void reset()
{
	UU(i,0,1e5) flag[i] = -1;
	UU(i,0,1e5) at[i] = -1;
}

void input()
{
	cin>>n>>x>>m;
}

void solve()
{
	ll ans = 0, now = x % m, step = 0, i = 1;
	
	while(i <= n && flag[now] == -1)
	{
		ans += now;
		
		flag[now] = ans;
		at[now] = step;
		
		now *= now;
		now %= m;
		i++;
		step++;
	}
	
	ll life = n - i + 1;
	ll cost = ans - flag[now] + now;
	if(i != n)
	{
		ll need = step - at[now];
		ll mul = life / need;
		
		ans += cost * mul;
		life %= need;
	}
	
	while(life--)
	{
		ans += now;
		now *= now;
		now %= m;
	}
	
	cout<<ans<<endl;
}

void LetsRock()
{
	solve();
}
	
int main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	
		reset();
		input();
		LetsRock();
	
	return 0;
}


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

int main()
{
	int N, K;
	cin >> N >> K;
	int x[N];
	int distance = 0;

	for (int i = 0; i < N; i++)
	{
		cin >> x[i];
		distance += 2 * min(x[i], K - x[i]);
	}
	cout << distance << '\n';
	return (0);
}


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

s = input()
s=s[::-1] #文字列の反転
words = ["maerd", "remaerd", "esare", "resare"]
while len(s) > 4:
    if s[:5] == words[0]:
        s = s[5:]
        continue
    elif s[:7] == words[1]:
        s = s[7:]
        continue
    elif s[:5] == words[2]:
        s = s[5:]
        continue
    elif s[:6] == words[3]:
        s = s[6:]
        continue
    else:
        break
if len(s) > 0:
    print('NO')
else:
    print('YES')


Measured memory_bytes: 3188
#include <iostream>
using namespace std;
int main(){
	int a,b;
	cin>> a >>b;
	if(a > b){
		cout<< "a > b" <<endl;
	}else if(a < b){
		cout<< "a < b" <<endl;
	}else{
		cout<< "a == b" <<endl;

	}
}

Measured memory_bytes: 1160
n = int(input())
restaurants = {}
cities = []
for i in range(n):
    s, p = input().split()
    p = int(p)
    if s not in cities:
        cities.append(s)
    if s not in restaurants.keys():
        restaurants[s] = []
    restaurants[s].append([p, i+1])

cities.sort()
for city in cities:
    restaurants[city] = sorted(restaurants[city], key=lambda x:x[0], reverse=True)
    for res in restaurants[city]:
        print(res[1])

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner stdIn = new Scanner(System.in);
		int n = stdIn.nextInt();
		int p[] = new int[n];
		int ans = 0;
		for(int i = 0; i < n; i++){
			p[i] = stdIn.nextInt();
		}
		for(int i = 0; i < n - 2; i++){
			if(p[i] < p[i+1] && p[i+1] < p[i+2] || p[i] > p[i+1] && p[i+1] > p[i+2]){
				ans++;
			}
		}
		System.out.println(ans);
		stdIn.close();
	}
}

Measured memory_bytes: 35580
#include <bits/stdc++.h>
#define SIZE 300005
#define MOD 1000000007LL
#define INF 1 << 29
#define LLINF 1LL << 60
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)
#define SET(a,c) memset(a,c,sizeof a)
#define BIT(i,j) ((i)>>(j))&1
#define ALL(o) (o).begin(), (o).end()
#define ERASE(o) (o).erase(unique((o).begin(),(o).end()), (o).end())
#define SQ(x) ((x)*(x))
using namespace std;
typedef long long ll;
typedef pair<ll,ll> Pll;
typedef pair<int, int> Pii;
typedef pair<double, double> Pdd;
typedef complex<double> dcomplex;
template<typename T> inline void priv(vector<T>a){REP(i,a.size()){cerr<<a[i]<<((i==a.size()-1)?"\n":" ");}}
ll gcd(ll a,ll b){int c=max(a,b);int d=min(a,b);return c==0||d==0?c:gcd(c%d,d);}
ll lcm(ll a,ll b){return a==0||b==0?0:a*b/gcd(a,b);}
ll fact(ll a){ll b=1;FOR(i,1,a)b*=i;return b;}

class P
{
public:
  double x,y;
  P(){};P(double x,double y):x(x),y(y){};
  P operator+(const P&q){P t;t.x=x+q.x;t.y=y+q.y;return t;}
  P operator+=(const P&q){x+=q.x;y+=q.y;return *this;}
  P operator-(const P&q){P t;t.x=x-q.x;t.y=y-q.y;return t;}
  P operator-=(const P&q){x-=q.x;y-=q.y;return *this;}
  template<typename T> P operator*(T d){return P(x*d,y*d);}
  template<typename T> P operator*=(T d){x*=d;y*=d;return *this;}
  template<typename T> P operator/(T d){return P(x/d,y/d);}
  template<typename T> P operator/=(T d){x/=d;y/=d;return *this;}
  bool operator<(const P&q){return (x!=q.x)?(x<q.x):(y<q.y);}
  bool operator>(const P&q){return (x!=q.x)?(x>q.x):(y>q.y);}
  double norm(void){return sqrt(x*x+y*y);}
  double arg(void){return acos(x/this->norm())*P(1,0).sign(*this);}
  P nvec(){return P(y,-x);}
  P rotate(double t){double c=cos(t),s=sin(t);return P(c*x-s*y,s*x+c*y);}
  P reverseX(void){return P(-x,y);}
  P reverseY(void){return P(x,-y);}
  P unit(void){return (*this).norm()==0?P(0,0):(*this)/(*this).norm();}
  P floor(void){return P((int)x,(int)y);}
  double dot(const P&q){return x*q.x+y*q.y;}
  double det(const P&q){return x*q.y-y*q.x;}
  int sign(const P&q){double d = (*this).det(q); return (d>0)-(d<0);}
  static bool on_seg(P p1,P p2,P q){return (p1-q).det(p2-q)==0&&(p1-q).dot(p2-q)<=0;}
  static P intersection(P p1,P p2,P q1,P q2){return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));}
};


int main()
{
  double x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
  P p1 = P(x1,y1);
  P p2 = P(x2,y2);
  P nv = (p1-p2).nvec();
  int q; cin >> q;
  REP(i,q)
  {
    double x,y; cin>>x>>y;
    P p = P(x,y);
    P ans = p + (P::intersection(p1,p2,p,p+nv)-p)*2;
    printf("%.10lf %.10lf\n",ans.x,ans.y);
  }
  return 0;
}

Measured memory_bytes: 3204
n = int(input())

list = [[[0] * 10 for i in range(3)] for i in range(4)]

for i in range(n):
    b, f, r, v = map(int, input().split())

    list[b-1][f-1][r-1] += v

for b in range(4):
    for f in range(3):
        print("", ' '.join(map(str, list[b][f])))
    if b < 3:
        print("####################")


Measured memory_bytes: 5608
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<ll, int> P;

int main()
{
	int n, q;
  cin>>n>>q;
  ll a[200001], b[200001];
  for(int i=1; i<=2*n; i++){
    cin>>a[i];
  }
  for(int i=1; i<=2*n; i++){
    cin>>b[i];
  }
  multiset<ll> st;
  ll ans=a[1]+a[2*n];
  int ct0=0, ct1=0;
  for(int i=2; i<2*n; i++){
    if(b[i]>a[i]){
      ct1++;
    }else if(b[i]==a[i]){
      ct0++;
    }
    st.insert(abs(b[i]-a[i]));
    ans+=max(a[i], b[i]);
  }
  for(int i=0; i<q; i++){
    int p; ll x, y;
    cin>>p>>x>>y;
    if(p==1 || p==2*n){
      ans=ans-a[p]+x;
      a[p]=x; b[p]=y;
    }else{
      if(b[p]>a[p]){
        ct1--;
      }else if(b[p]==a[p]){
        ct0--;
      }
      st.erase(st.lower_bound(abs(b[p]-a[p])));
      ans=ans-max(a[p], b[p])+max(x, y);
      a[p]=x; b[p]=y;
      st.insert(abs(y-x));
      if(y>x){
        ct1++;
      }else if(y==x){
        ct0++;
      }
    }
    if(ct0>0 || ct1%2==0){
      cout<<ans<<endl;
    }else{
      cout<<ans-*(st.begin())<<endl;
    }
  }
	return 0;
}

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

int main() {
	int n;
	std::cin >> n;
	std::vector<int> d(n, -1);
	std::vector<int> dtmp(n, -1);
	std::vector<std::vector<int>> vec(n);
	for (int i = 0; i < n; i++) {
		int u, k;
		std::cin >> u >> k;
		while (k--) {
			int a;
			std::cin >> a;
			vec[i].push_back(a - 1);
		}
	}

	dtmp[0] = 0;
	for (int i = 0; i < n; i++) {
		d = dtmp;
		for (int idx = 0; idx < n; idx++) {
			if (d[idx] >= 0) {
				for (int j = 0; j < vec[idx].size(); j++) {
					if (dtmp[vec[idx][j]] == -1) {
						dtmp[vec[idx][j]] = i + 1;
					}
				}
			}
		}
	}

	for (int i = 0; i < n; i++) {
		std::cout << i + 1 << " " << d[i] << std::endl;
	}
}


Measured memory_bytes: 3176
#include<cstdio>
#include<algorithm>
using namespace std;
int solve(int n,int k){
	while(n%k){
		int v=n%k,d=n/k+1;
		n-=d*(v/d+(v%d!=0));
	}
	return n/k;
}
int main(){
	int t,n,k,ans=0;
	scanf("%d",&t);
	while(t--)scanf("%d%d",&n,&k),ans^=solve(n,k);
	puts(ans?"Takahashi":"Aoki");
	return 0;
}


Measured memory_bytes: 128
N=int(input())
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<p:
            l=x
        else:
            r=x
    ans+=tmp-l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<m:
            l=x
        else:
            r=x
    ans+=tmp-l
print(ans//2)

Measured memory_bytes: 121652
#define _USE_MATH_DEFINES
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <clocale>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i, s, n) for(int i = (s), i##_len=(n); i < i##_len; ++i)
#define FORS(i, s, n) for(int i = (s), i##_len=(n); i <= i##_len; ++i)
#define VFOR(i, s, n) for(int i = (s); i < (n); ++i)
#define VFORS(i, s, n) for(int i = (s); i <= (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) FORS(i, 0, n)
#define VREP(i, n) VFOR(i, 0, n)
#define VREPS(i, n) VFORS(i, 0, n)
#define RFOR(i, s, n) for(int i = (s), i##_len=(n); i >= i##_len; --i)
#define RFORS(i, s, n) for(int i = (s), i##_len=(n); i > i##_len; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREPS(i, n) RFORS(i, n, 0)
#define ALL(v) (v).begin(), (v).end()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v), greater<decltype(v[0])>())
#define SZ(x) ((int)(x).size())
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define BIT(n) (1LL<<(n))
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())

using ll = long long;
using ull = unsigned long long;
using Pi_i = pair<int, int>;
using VB = vector<bool>;
using VC = vector<char>;
using VD = vector<double>;
using VI = vector<int>;
using VLL = vector<ll>;
using VS = vector<string>;
using VSH = vector<short>;
using VULL = vector<ull>;

const int MOD = 1000000007;
const int INF = 1000000000;
const int NIL = -1;

template<class T, class S>
bool chmax(T &a, const S &b){
    if(a < b){
        a = b; return true;
    }
    return false;
}
template<class T, class S>
bool chmin(T &a, const S &b){
    if(b < a){
        a = b; return true;
    }
    return false;
}


int main(){
    int n, m; cin >> n;
    VI a(n);
    REP(i, n) cin >> a[i];
    cin >> m;
    VI b(m);
    REP(i, m) cin >> b[i];
    VI res;
    set_union(ALL(a), ALL(b), inserter(res, res.end()));
    REP(i, res.size()){
        cout << res[i] << "\n";
    }
    return 0;
}



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

const ULL M = 998244353;

struct RQ {
 using RQV = ULL;
 struct RQRV{ ULL b,c; };
 static RQV Zero(){ return 0; }
 static RQRV RZero(){ return { 1,0 }; }
 // addition
 static RQV f(RQV a,RQV b){ return (a+b) % M; }
 // update function
 static void uf(RQV& a,RQV b){ a = b; }
 // effect of range queries n-sized
 static void ef(RQV& a,RQRV b,int n){ a = (b.b*a + b.c*n) % M; }
 // range query update
 static void ruf(RQRV& a,RQRV b){
  a.b = (a.b * b.b) % M; 
  a.c = (a.c * b.b + b.c) % M;
 }
 // comparation
 static bool cmp(RQV l,RQV r){ return l<=r; }
 struct Node{
  RQV v; RQRV r;
 };
 int N;
 vector<Node> V;

 void init(int n){
  N=1; while (N<n) N*=2;
  V.assign(N*2,{Zero(),RZero()});
 }

 void spread(int i,int z){
  if (z!=1) {
   ef(V[i*2].v,V[i].r,z/2);
   ruf(V[i*2].r,V[i].r);
   ef(V[i*2+1].v,V[i].r,z/2);
   ruf(V[i*2+1].r,V[i].r);
  }
  V[i].r = RZero();
 }

 void upd(int p,RQV v){
  for(int d=N; d>=1; d/=2) spread(p/d,d);
  p+=N; uf(V[p].v,v);
  int z=1;
  while(p!=1){
   p/=2; z*=2;
   V[p].v = f(V[p*2].v,V[p*2+1].v);
   ef(V[p].v,V[p].r,z);
  }
 }

 void updr(int l,int r,RQRV v,int a=0,int b=0,int i=-1){
  if(i==-1){ a=0; b=N; i=1; }
  spread(i,b-a);
  if(r<=a || b<=l) return;
  if(l<=a && b<=r){
   ruf(V[i].r,v);
   ef(V[i].v,V[i].r,b-a);
   return;
  }
  updr(l,r,v,a,(a+b)/2,i*2);
  updr(l,r,v,(a+b)/2,b,i*2+1);
  V[i].v = f(V[i*2].v,V[i*2+1].v);
  ef(V[i].v,V[i].r,b-a);
 }

 RQV query(int l,int r,int a=0,int b=0,int i=-1){
  if(i==-1){ a=0; b=N; i=1; }
  if(r<=a || b<=l) return Zero();
  if(l<=a && b<=r) return V[i].v;
  RQV q1 = query(l,r,a,(a+b)/2,i*2);
  RQV q2 = query(l,r,(a+b)/2,b,i*2+1);
  q1 = f(q1,q2);
  ef(q1,V[i].r,min(r,b)-max(l,a));
  return q1;
 }

 int find(int l,RQV v,int a=0,int b=0,int i=-1){
  static RQV x;
  if(i==-1){ a=0; b=N; i=1; x=Zero(); }
  spread(i,b-a);
  if(b<=l) return N;
  if(l<=a && !cmp(v,f(x,V[i].v))){ x=f(x,V[i].v); return N; }
  if(b-a==1) return a;
  int q1 = find(l,v,a,(a+b)/2,i*2);
  if(q1!=N) return q1;
  return find(l,v,(a+b)/2,b,i*2+1);
 }
};

int N,Q;
RQ G;

int main(){
 scanf("%d%d",&N,&Q);
 G.init(N);
 rep(i,N){
  int a; scanf("%d",&a);
  G.upd(i,a);
 }
 rep(q,Q){
  int c; scanf("%d",&c);
  if(c==0){
   int l,r,b,c; scanf("%d%d%d%d",&l,&r,&b,&c);
   G.updr(l,r,{(ULL)b,(ULL)c});
  }
  if(c==1){
   int l,r; scanf("%d%d",&l,&r);
   printf("%llu\n",G.query(l,r));
  }
 }
 
 return 0;
}


Measured memory_bytes: 27816
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<iomanip>
#include<set>

using namespace std;

int main()
{
	int d,g;
	cin >> d >> g;
	vector<int> p(d),c(d);
	long long ans=0;
	for(int i=0;i<d;i++)
	{
		cin >> p[i] >> c[i];
		ans+=(i+1)*100*p[i]+c[i];
	}

	
	for(int i=0;i<(1<<d);i++)
	{
		long long tmp=0;
		long long cnt=0;
		vector<bool> used(d,false);
		for(int j=0;j<d;j++)
		{
			if((i&(1<<j))!=0)
			{
				cnt+=p[j];
				tmp+=(j+1)*100*p[j]+c[j];
				used[j]=true;
			}
		}
		if(tmp<g)
		{
			for(int j=d-1;j>=0;j--)
			{
				if(used[j]!=true)
				{
					for(int k=1;k<=p[j];k++)
					{
						tmp+=(j+1)*100;
						cnt++;
						if(tmp>=g)break;
					}
					break;
				}
			}
		}
		if(tmp>=g)
		{
			if(ans>cnt)ans=cnt;

		}


	}


	cout << ans << endl;



}

Measured memory_bytes: 256
def main():
    n,a,b = map(int,input().split())
    x = [int(x_) for x_ in input().split()]
    now = x[0]
    ans = 0
    for i in range(1,n):
        if (x[i]-now)*a<=b:
            ans += (x[i]-now)*a
        else:
            ans += b
        now = x[i]
    print(ans)
if __name__ == "__main__":
    main()

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


int main(){
  int A, B;
  cin >> A >> B;
  
  if(A>12){
    cout << B << endl;
  }else if(6<=A&&A<=12){
    cout << (int)B/2 << endl;
  }else{
    cout << 0 << endl;
  }
  
 return 0;

}

Measured memory_bytes: 3536
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
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; }
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//for(auto p:mp)(mapの探索)
//printf("%.10f\n",なんちゃら)

int g[15][15];
const int INF = 1001001001;
const int dx[4] = { -1,0,1,0 };
const int dy[4] = { 0,-1,0,1 };

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int bingo[3][3];
bool flag[3][3];
int cnt[2][105];
int h, w;
int choco[1010][1010];

int main() {
	ll n, m, INF = 1e9 + 7;
	cin >> n >> m;
	vector<ll>a(m), dp(n + 2);
	vector<bool>flag(n + 2, true);
	rep(i, m) {
		cin >> a[i];
		flag[a[i] + 1] = false;
	}
	dp[1] = 1;
	dp[0] = 0;
	for (int i = 2;i <= n+1;++i) {
		if (flag[i])dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] = dp[i] % INF;
	}
	cout << dp[n + 1] << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	unsigned long long int i, j;
	unsigned int n, a_max = 0;
	unsigned int a[4000];

	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}

	for (i = 0; i < n; i++)
	{
		a_max += a[i] - 1;
	}

	printf("%d", a_max);

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	std::string str;
	int okada[200003];
	int a = 0,b = 0, c=0,k = 0,x=0,y=0,z=0,r=1;
	std::cin >> a >> b >> c >> k;
	for (int i = 0; i < k; i++) {
		r = r * 2;
	}
	x = a *r+ b + c;
	y = a + b *r+ c;
	z = a + b + c * r;
	std::cout << std::max(x, std::max(y, z)) << std::endl;
}


Measured memory_bytes: 256
#include<stdio.h>

void print_array(int *array, int num){
    for(int i = 0; i < num; i++){
        printf("%d", array[i]);
        if(i != num-1) printf(" ");
    }
    printf("\n");
}

int main(void){
    int i = 0, j = 0, temp, num;
    int array[100];

    scanf("%d", &num);
    while(i < num && scanf("%d", &array[i++]) == 1);

    print_array(array, num);
    for(i = 1; i < num; i++){
        temp = array[i];
        for(j = i - 1; j >= 0 && array[j] > temp; j--){
            array[j+1] = array[j];
        }
        array[j+1] = temp;
        print_array(array, num);
    }
    
    return 0;
}


Measured memory_bytes: 2084
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <stdio.h>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	if (a == b) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
// typedef
using ll  = long long;
using str = string;
using PL  = pair<ll, ll>;
using P   = pair<int, int>;
using VL  = vector<ll>;
using VI  = vector<int>;
using VS  = vector<str>;
using VP  = vector<P>;
using VPL = vector<PL>;
using VVL = vector<VL>;
using VVI = vector<VI>;

// const num
const ll INF         = 1e18 + 18;
const ll MAX         = 100005;
const ll MOD         = 1000000007;
const long double PI = acosl(-1.0);

// loop
#define REP(i, a, b) for(ll(i) = (a); (i) < (b); (i)++)
#define RREP(i, a, b) for(ll(i) = (a); (i) >= (b); (i)--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, n, 0)

// YesNo
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
// All
#define ALL(v) v.begin(), v.end()
#define deduplicate(v) (v).erase(unique(ALL(d)), (v).end())

int main(void) {
	int n;
	int ans = 0;
	int l[110];
	cin >> n;
	rep(i, n) {
		cin >> l[i];
	}
	if(n < 3) {
		cout << 0 << endl;
		exit(0);
	}
	REP(i, 0, n) {
		REP(j, i + 1, n) {
			REP(k, j + 1, n) {
				int a = l[i];
				int b = l[j];
				int c = l[k];
				if(a == b || b == c || c == a) {
					continue;
				}
				if(a + b > c && b + c > a && c + a > b) {
					ans++;
				}
			}
		}
	}

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

Measured memory_bytes: 3616
<?php
    $line = readline();
    readline_add_history($line);
    $inputs = explode(" ", $line);
    $a = intval($inputs[0]);
    $b = intval($inputs[1]);
    $c = intval($inputs[2]);
    if (($a < $b) && ($b < $c)) {
    echo "Yes";
    } else {
    echo "No";
    }
?>

Measured memory_bytes: 6544
n = input()

for i in range(2 ** 3):
    ops = ["+"] * 3
    for j in range(3):
        if ((i >> j) & 1):
            ops[j] = "-"

    f = ""
    for pn, po in zip(n, ops + [""]):
        f += (pn + po)
    if eval(f) == 7:
        print(f + "=7")
        break

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

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

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

    int d = 0, max_value = 0;
    for (int i = 0; i < N; i++)
    {
        int x;
        cin >> x;
        d = gcd(d, x);
        max_value = max(max_value, x);
    }

    cout << (K <= max_value && K % d == 0 ? "POSSIBLE" : "IMPOSSIBLE") << endl;
}


Measured memory_bytes: 256
using System;

public class Hello
{
    public static void Main()
    {
        string[] line = Console.ReadLine().Trim().Split(' ');
        var n = long.Parse(line[0]);
        var k = long.Parse(line[1]);
        if (n == k) { Console.WriteLine(1); goto end; }
        line = Console.ReadLine().Trim().Split(' ');
        var a = Array.ConvertAll(line, long.Parse);
        var min = 9999999999L; var mini = 0L;
        for (long i = 0; i < n; i++)
        {
            if (a[i] < min) { mini = i;  min = a[i]; }
        }
        var r1 = n - k;
        var r2 = k - 1;
        var r3 = (r1 + r2 - 1) / r2 + 1;
        Console.WriteLine(r3);

        end:;
    }
}

Measured memory_bytes: 19296
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 100000000000000000
#define EPS 1e-9
#define PI  acos(-1)
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fi first
#define se second
#define pb push_back
#define re return
#define br break

//----***入出力***---
void print() { std::cout << "\n"; }
template <class T>void print(const T &x) {std::cout << x<<"\n";}
template <class T, class... Args>void print(const T &x, const Args &... args) {std::cout << x << " ";print(args...);}
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;

signed main(){
  int N;cin>>N;
  vector<int> A(N),B(N);
  int a=0,b=0,sum_;
  REP(i,0,N){cin>>A[i];a+=A[i];}
  REP(i,0,N){cin>>B[i];b+=B[i];}
  sum_=b-a;
  if(sum_<0){
    print("No");
    re 0;
  }
  int ans=0;
  REP(i,0,N){
   if(B[i]>A[i]){
      ans+=(B[i]-A[i]+1)/2;
    }
  }
  if(ans<=sum_)print("Yes");
  else print("No");
}


Measured memory_bytes: 384
# include <stdio.h>
# include <string.h>

 int main () {
 char str [222];
 scanf ("%s", str ) ;
 int n= strlen (str ) ;
 for (int i=n -2; i; i -=2) {
 if( strncmp (str , str +i/2 , i/2) ==0) {
 printf ("%d\n" ,i) ;
 return 0;
 }
 }
 return 0;
}


Measured memory_bytes: 128
while n = gets.to_i do
  break if n.zero?
  tile = Array.new(n).map!{Array.new(n)}
  tile[y=n/2+1][x=n/2]=1
  2.upto(n*n){|i|
  if tile[y=(y+1)%n][x=(x+1)%n].nil?
   tile[y][x]=i
  else
    loop{
      x=(x+n-1)%n
      y=(y+1)%n
    if tile[y][x].nil?
      tile[y][x] = i
      break
    end
    }
  end
  }
  tile.each{|ary|
    ary.each{|num|
      printf("%4d",num)
    }
    puts
  }
end

Measured memory_bytes: 2388
function main(input){
  input = input.split('\n');
  const N = Number(input[0]);
  const list = input[1].split(' ').map(Number);

  let sum = 0;
  for(let i=0; i<N; i++){
    for(let j=i+1; j<N; j++){
      for(let k=j+1; k<N; k++){
        const a = list[i];
        const b = list[j];
        const c = list[k];
        if(a!=b &&  b!=c && c!=a){
          if(
              ((a+b) > c)
            && ((b+c) > a)
            && ((c+a) > b)
          ){
            sum++;
          }
        }
      }
    }
  }

  console.log(sum);

}
main(require('fs').readFileSync('/dev/stdin', 'utf8').trim());


Measured memory_bytes: 32432
N, T = map(int, input().split())
L = [int(i) for i in input().split()]
x = 0

for i in range(N-1):
    if L[i+1] - L[i] >= T:
        x += T
    else:
        x += L[i+1] - L[i]
else:
    x += T
    print(x)


Measured memory_bytes: 25196
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[3*n];
        for (int i = 0; i < 3 * n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (long) a[3*n - 2 - 2 * i];
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 61976
import java.util.*;

public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int a;
        int x=0;
        
		for(int i = 0 ; i < n; i++){
			a = sc.nextInt();
            if(a % 2 == 0){
            	if(a % 3 == 0 || a % 5 == 0)
            	    continue;
                else{
                    x = 9;
                    break;
                }
    		}
		}
        if( x == 9)
    		System.out.println("DENIED");
		else
    		System.out.println("APPROVED");
    }
}

Measured memory_bytes: 23764
#include<cstdio>
#include<algorithm>
using namespace std;
void dfs(int j,int sum);
bool memo[2001];
int a[2001];
int n;
int main(){

  int m,b;
  scanf("%d",&n);
  for(int i = 1;i <= n;i++) scanf("%d",&a[i]);

  fill(memo,memo+2001,0);
  dfs(0,0);
  
  scanf("%d",&m);
  for(int i = 0;i < m;i++){
    scanf("%d",&b);
    if(memo[b] == 1) printf("yes\n");
    else printf("no\n");
  }
  return (0);
}

void dfs(int j,int sum){
  if(memo[sum] != 1) memo[sum]++;
  if(j <= n){
    dfs(j+1,sum+a[j]);
    dfs(j+1,sum);
  }
}

Measured memory_bytes: 2700
n = int(input())
mx = n//3
ans = 0
mod = 10**9+7
import math
def combinations_count(n, r): #組み合わせ(nCr)
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
for i in range(1,mx+1):
    if i == 1:
        ans += 1
    else:
        ans += combinations_count(n-2*i-1,i-1) % mod
print(ans%mod)

Measured memory_bytes: 9192
#include <bits/stdc++.h>
using namespace std;
const int maxx = 2e5 + 7;
int n;
int a[maxx];
int p[maxx];

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) p[i] = 0;
	for(int i = 1; i <= n; i++) p[a[i]] = p[a[i] - 1] + 1;
	//for(int i = 1; i <= n; i++) cout << p[a[i]] << endl;
	int ans = 0;
	for(int i = 1; i <= n; i++) ans = max(ans, p[i]);
	cout << n - ans << endl;
}

Measured memory_bytes: 1792
n=int(input())
a=[]
for i in range(n):
	a.append(int(input()))
a.sort()
ans1=ans2=0
p=q=a[n//2]
if n%2==0:
	for i in range(n//2-1):
		ans1+=abs(p-a[i])
		p=a[i]
		ans1+=abs(p-a[-i-1])
		p=a[-i-1]
	ans1+=abs(p-a[n//2-1])
	print(ans1)
else:
	for i in range(n//2):
		ans1+=abs(p-a[i])
		p=a[i]
		ans1+=abs(p-a[-i-1])
		p=a[-i-1]
		ans2+=abs(q-a[-i-1])
		q=a[-i-1]
		ans2+=abs(q-a[i])
		q=a[i]
	print(max(ans1,ans2))




Measured memory_bytes: 7512
#include <bits/stdc++.h>
using namespace std;
int main(){
    long n; cin>>n;
    vector<vector<long>> tree(n+1);
    for(int i=0;i<n-1;i++){
        long a,b; cin>>a>>b;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    vector<long> df(n+1,0),ds(n+1,0);
    queue<long> q;
    q.push(1);
    while(!q.empty()){
        long t=q.front(); q.pop();
        for(auto x:tree[t]){
            if(x!=1&&df[x]==0){
                df[x]=df[t]+1;
                q.push(x);
            }
        }
    }
    q.push(n);
    while(!q.empty()){
        long t=q.front(); q.pop();
        for(auto x:tree[t]){
            if(x!=n&&ds[x]==0){
                ds[x]=ds[t]+1;
                q.push(x);
            }
        }
    }
    long sum=0;
    for(int i=1;i<=n;i++)
        sum+=df[i]<=ds[i]?1:-1;
    if(sum>0)
        cout<<"Fennec";
    else
        cout<<"Snuke";
}

Measured memory_bytes: 7936
while(n=gets.to_i)>0
a=[b=[x=0,0]]
p=a*n
n.times{w=0;m=gets
n.times{|j|h,w=p[j][0]+1,w+1;m[j]==?*&&h=w=0
a[j]=[h,s=[h,w,p[j-1][1]+1].min]
x<s&&x=s}
p,a=a,[b]}
p x
end

Measured memory_bytes: 6116
#include <bits/stdc++.h>
using namespace std;
int main() {
  int sx,sy,tx,ty;
  cin >> sx >> sy >> tx >> ty;
  int xx = tx - sx;
  int yy = ty - sy;
  string rz = "";
  string lz = "";
  for (int i = 0; i < xx; i++) {
  rz += "R";
  lz += "L";
}
string dz = "";
string uz = "";
for (int i = 0; i < yy; i++) {
  dz += "D";
  uz += "U";
}

string firs = uz + rz + dz + lz;
string secon = "D" + rz + "R" + uz + "ULUL" + lz + dz + "DR";

cout << firs + secon << endl;
  return 0;
}

Measured memory_bytes: 256
#include <vector>

using namespace std;

using u16 = unsigned short int;
using uint = unsigned int;

class bitVector {
public:
    uint length, cnum, bnum;
    // bit列の長さ、chunk数、chunk毎のblock数

    static int cw, bw;
    // chunkの幅、blockの幅 今回は256, 32

    vector<uint> bit;
    vector<uint> chunk;
    vector<vector<u16>> blocks;


    explicit bitVector(int N) : length(N) {
        cnum = (length + cw - 1) / cw;
        // length / cwを切り上げたものが必要なchunkの個数
        bnum = cw / bw;

        bit.assign(cnum * bnum, 0);
        chunk.assign(cnum + 1, 0);
        // +1は先頭の0が入っているやつの分
        blocks.assign(cnum, vector<u16>(bnum + 1, 0));
        // こっちの+1も同じく
    }

    // pos桁目をbに変える
    void set(int pos, int b) {
        int bpos = pos / bw;
        // bit内でposが存在するblockの番号
        int offset = pos % bw;
        // そのblock内でのposのindex

        if (b == 0) {
            bit[bpos] &= ~(1 << offset);
        } else if (b == 1) {
            bit[bpos] |= (1 << offset);
        }
    }

    // pos桁目のbitを返す
    int access(int pos) const {
        // assert(pos < length);

        int bpos = pos / bw;
        int offset = pos % bw;
        return bit[bpos] >> offset & 1;
    }

    uint popCount(uint num) const {
        // __builtin_popcountが使えなければ黒魔術
        return __builtin_popcount(num);
    }

    // chunkとblocksを適切に埋める
    void build() {
        chunk[0] = 0;
        for (int i = 0; i < cnum; ++i) {
            blocks[i][0] = 0;
            for (int j = 0; j < bnum; ++j) {
                blocks[i][j + 1] = blocks[i][j] + popCount(bit[i * bnum + j]);
            }
            chunk[i + 1] = chunk[i] + blocks[i][bnum];
        }
    }

    // [0, pos)にあるkindの数を返す
    int rank(int pos, int kind) const {
        // assert(kind <= 1);
        if (kind == 0) {
            return pos - rank1(pos);
        } else {
            return rank1(pos);
        }
    }

    // [0, pos)にある1の数を返す
    int rank1(int pos) const {
        int cpos = pos / cw;
        int bpos = pos % cw / bw;
        int offset = pos % bw;

        uint masked = (bit[cpos * bnum + bpos]) & ((1 << offset) - 1);
        return chunk[cpos] + blocks[cpos][bpos] + popCount(masked);
    }

    // rank(idx, kind)=numなる最小のidxを返す
    // そもそもkindがnum個なかったら-1を返す
    int select(int num, int kind) const {
        if (num == 0) return 0;
        if (rank(length, kind) < num) return -1;

        int ok = length, ng = 0;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (rank(mid, kind) >= num) {
                ok = num;
            } else {
                ng = num;
            }
        }

        return ok;
    }
};

int bitVector::cw = 1024;
int bitVector::bw = 32;


#include <iostream>
#include <string>

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

    bitVector bv(N);

    for (int i = 0; i < N; ++i) {
        bv.set(i, S[i] == 'W' ? 1 : 0);
    }

    bv.build();
    int ans = N;

    for (int i = 1; i <= N; ++i) {
        int turn = bv.rank(i - 1, 1) + (bv.rank(N, 0) - bv.rank(i, 0));
        ans = min(ans, turn);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 900
#include <stdio.h>
#include <math.h>

int hantei(int);

int main(){
int num[10000], i, kosuu, x;
int M=0;

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

for(i=0; i<kosuu; i++){

  if(num[i]==2){
    M++;
    continue;
  }
  else if(num[i]<2||num[i]%2==0){
    continue;
  }
  x=hantei(num[i]);
  if(x==1) M++;
}
printf("%d\n", M);
return 0;
}

int hantei(int x)
{
  int y=3;

  while(y<=sqrt(x)){
    if(x%y==0) return 0;

    y+=2;
  }
  return 1;
}

Measured memory_bytes: 628
#include <iostream>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  while(a>0&&c>0){
    c -= b;
    if(c<=0){
      break;
    }
    a -= d;
  }
  if(a>0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3632
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll extgcd(ll a,ll b,ll& x,ll& y){
	ll d=a;
	if(b){
		d=extgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	else x=1,y=0;
	return d;
}

ll n;
vl a;

int main(){
	cin>>n;
	if(n==1){
		cout<<1<<endl;
		return 0;
	}
	n*=2;
	ll N=n;
	for(ll i=2;i*i<=n;i++) if(n%i==0){
		ll t=1;
		while(n%i==0) n/=i,t*=i;
		a.push_back(t);
	}
	if(n>1) a.push_back(n);
	ll m=a.size(),res=INF;
	for(int i=0;i<1<<m;i++){
		ll p=1;
		for(int j=0;j<m;j++) if(i&1<<j) p*=a[j];
		ll q=N/p,x,y;
		extgcd(p,q,x,y);
		x*=-1;
		if(x>0){
//			if(p>INF/x+2) continue;
			res=min(res,p*x);
		}
	}
	cout<<res<<endl;
}

Measured memory_bytes: 3540
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define f first
#define sc second
void solve() {
    char a;
    cin >> a;
    if (a >= 'a' && a <= 'z') cout << "a\n";
    else cout << "A\n";
    return;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    solve();
}


Measured memory_bytes: 3580
function main(input){
  const a = input.trim().split('');
  let count = 0;
  for(let i=0; i<3; i++){
    if(a[i]=='1'){
      count++;
    }
  }
  console.log(count);
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 29508
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file 
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional> // for less 
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Debug_array(a,n) for (ll i=(0); i<(n); i++) cout<<a[i]<<" "
#define Foe(i,s,e) for (ll i=(s); i<=(e); i++)
#define Fod(i,s,e) for (ll i=(s)-1; i>=(e); i--)
#define Mod 1000000007
#define pii pair<ll,ll>
#define fi first
#define se second
#define endl "\n"
#define mp make_pair
#define big_prime 15486277
#define bigger_prime 179424697
#define biggest_prime 32416188691
//#define random_shuffle(indices.begin(), indices.end());
//std::random_device rd;
//std::mt19937 g(rd());
//std::shuffle(v.begin(), v.end(), g);
using namespace __gnu_pbds; 
using namespace std;

typedef long long ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; 

#define MAX 100000
ll n,x;
ll b[MAX];
pii a[MAX];
pii sum[MAX];
ll prefix[MAX];
ll req;
ll get_r(ll i,ll r){
	if(r<=b[i]) return a[i].fi*r;
	else return a[i].fi*b[i]+a[i].se*(r-b[i]);
}

bool check(ll k){
	ll r = k%x;
	ll q = k/x;
	ll ans = 0;
	For(i,0,n){ 
		ll temp = 0;
		if(i>=q) temp = prefix[q-1]+get_r(sum[i].se,r);
		else{
			temp = prefix[q]-sum[i].fi+get_r(sum[i].se,r);
		} 
		ans = max(ans,temp);
	}
	return (ans>=req);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin>>n>>x;
	For(i,0,n){
		cin>>b[i]>>a[i].fi>>a[i].se;
		sum[i].fi = (a[i].fi*b[i]+a[i].se*(x-b[i]));
		sum[i].se = i;
		req += (a[i].fi*b[i]);
	}
	sort(sum,sum+n,greater<pii>());
	prefix[0]=sum[0].fi;
	For(i,1,n) prefix[i]=prefix[i-1]+sum[i].fi;

	ll start=0,end=x*n;
	ll ans = x*n;
	while(start<=end){
		ll mid = (start+end)/2;
		if(check(mid)){
			ans = mid;
			end = mid-1;
		}else{
			start = mid+1;
		}
	}

	cout<<ans<<endl;








	
}

Measured memory_bytes: 4992
#include <cstdio>
#include <cstdint>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <unordered_map>

int main()
{
    int x, y;
    std::cin >> x >> y;

    std::cout << (x + y/2) << std::endl;

    return 0;
}

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

#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define all(v) (v).begin(),(v).end()
#define pb push_back

typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef vector<pint> vpint;


int main(){
    string a;
    int counter0=0,counter1=0;
    cin>>a;
    rep(i,a.length()){
        if(a[i]=='0')counter0+=1;
        else counter1+=1;
    }
    cout<<min(counter0,counter1)*2<<endl;


    return 0;
}

Measured memory_bytes: 512
n,p = map(int,input().split())
l = list(map(int,input().split()))
l1 = []
for i in l:
  if i%2==0:
    l1.append(0)
  else:
    l1.append(1)
    


a = l1.count(1)
b = l1.count(0)
if a!=0:
  cou = (2**(b))*(2**(a-1))
  print(cou)
else:
  if p%2==0:
    print(2**b)
  else:
    print(0)

Measured memory_bytes: 3064
#include <stdio.h>
#define SIZE 10

/* prototype declaration */
void init();
void operation();
void push(int data);
int pop();

int s[SIZE];
int sp;

int main(int argc, const char *argv[])
{
	init();
	operation();
	return 0;
}

void init()
{
	int i;
	sp = 0;
	for(i=0; i<SIZE; i++) s[i] = 0;
}

void operation()
{
	int car;
	while(scanf("%d", &car) != EOF){
		if(car) push(car);
		else printf("%d\n",pop());
	}
}

void push(int data)
{
	s[sp++] = data;
}

int pop()
{
	return s[--sp];	
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define fi first
#define se second
#define REP(i, a, b) for (int i = (a); i <= (b); ++i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define endl '\n'
#define mp make_pair
#define pb push_back
#define pf push_front
#define ins insert
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define SZ(x) ((int)(x).size())
#define unmap unordered_map
#define pq priority_queue
#define lb lower_bound //first pos >= val
#define ub upper_bound // first pos > val
#define bp __builtin_popcount
#define debug(a) cout << a << endl
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;
typedef pair <ll, ld> pld;
typedef pair <ll, pll> pllp;
typedef pair <pll, ll> ppll;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <pll> vpll;
typedef vector <pii> vpii;
typedef string BigNum;

const ll maxN = 1e18;
const ll minN = -1e18;
const ll MOD = 1e9 + 7;
const ll MOD1 = 998244353;
const int baseHash = 331;
const int bigNumLength = 5000;
const ld PI = acos(-1);

//Remember limit for IT, etc..., and +1 in limit of any array
const ll limit = 2e5 + 5;
const ll limit1 = 1e6 + 5;
const ll limit2 = 1e3 + 5;
//If TLE let's use int instead of ll because it's as slow as your WPM :)))

/*----IMPORTANT THINGS----*/
pll dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
/*------------------------*/

ll n;
ll a[limit], b[limit], c[limit];
ll f[limit][4];

void solveProblem() {
    f[1][1] = a[1], f[1][2] = b[1], f[1][3] = c[1];

    REP(i, 2, n) {
        f[i][1] = max(f[i - 1][2], f[i - 1][3]) + a[i];
        f[i][2] = max(f[i - 1][1], f[i - 1][3]) + b[i];
        f[i][3] = max(f[i - 1][1], f[i - 1][2]) + c[i];
        //cout << f[i][1] << " " << f[i][2] << " " << f[i][3] << endl;
    }

    cout << max(f[n][1], max(f[n][2], f[n][3])) << endl;
}

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

void readInput() {
    cin >> n;
    REP(i, 1, n) cin >> a[i] >> b[i] >> c[i];
}

int main() {
    fastInput();
    readInput();
    solveProblem();
}



Measured memory_bytes: 9060
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

template <size_t T>
bool nextBitset(bitset<T> &bs, int digit)
{
    if(bs.none())
        return false;
    bitset<T> x, y, z;
    x = bs.to_ulong() & (~(bs.to_ulong()) + 1ULL);
    y = bs.to_ulong() + x.to_ulong() + 0ULL;
    z = bs & ~y;
    if(bs[digit-1] && bs == z)
        return false;
    bs = ((z.to_ulong() / x.to_ulong()) >> 1) + 0ULL;
    bs |= y;
    return true;
}

pair<int, int> hitBlow(const string& s, const string& t)
{
    pair<int, int> ret(0, 0);
    for(int i=0; i<4; ++i){
        if(s[i] == t[i])
            ++ ret.first;
        else if(t.find(s[i]) != string::npos)
            ++ ret.second;
    }
    return ret;
}

int main()
{
    for(;;){
        int n;
        cin >> n;
        if(n == 0)
            return 0;

        vector<string> digit(n);
        vector<pair<int, int> > a(n);
        for(int i=0; i<n; ++i)
            cin >> digit[i] >> a[i].first >> a[i].second;

        vector<string> t;
        bitset<10> bs((1<<4)-1);
        do{
            string s;
            for(int i=0; i<10; ++i){
                if(bs[i])
                    s += '0' + i;
            }
            do{
                bool ok = true;
                for(int i=0; i<n; ++i){
                    if(hitBlow(s, digit[i]) != a[i])
                        ok = false;
                }
                if(ok)
                    t.push_back(s);
            }while(next_permutation(s.begin(), s.end()));
        }while(nextBitset(bs, 10));

        if(t.size() == 1){
            cout << t[0] << endl;
            continue;
        }

        string ret = "????";
        bs = bitset<10>((1<<4)-1);
        do{
            string s;
            for(int i=0; i<10; ++i){
                if(bs[i])
                    s += '0' + i;
            }
            do{
                set<pair<int, int> > p;
                for(unsigned i=0; i<t.size(); ++i)
                    p.insert(hitBlow(s, t[i]));
                if(p.size() == t.size())
                    ret = min(ret, s);
            }while(next_permutation(s.begin(), s.end()));
        }while(nextBitset(bs, 10));

        cout << ret << endl;
    }
}

Measured memory_bytes: 1300
#include <algorithm>
#include <iterator>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <utility>
#include <string>
#include <vector>
#include <limits>
#include <queue>
#include <cmath>
#include <map>
#include <set>

using namespace std;

using ll = long long;

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

    vector<ll> v(n);

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

    vector<vector<ll> > dp(n + 1, vector<ll>(n + 1));

    for(int len = 1; len < n + 1; ++len) {
        for(int left = 0; left + len < n + 1; ++left) {
            int right = left + len;

            if((right - left) % 2 == n % 2) {
                dp[left][right] = max(v[left] + dp[left + 1][right],
                                      dp[left][right - 1] + v[right - 1]);
            } else {
                dp[left][right] = min(-v[left] + dp[left + 1][right],
                                      dp[left][right - 1] - v[right - 1]);
            }
        }
    }

    /*
    for(int i = 0; i < n + 1; ++i) {
        copy(dp[i].begin(), dp[i].end(), ostream_iterator<ll>(cout, " "));
        cout << endl;
    }
    */

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

    return 0;
}


Measured memory_bytes: 70784
from collections import defaultdict
import heapq
N,M,S = map(int,input().split())
E=[list(map(int,input().split())) for _ in range(M)]

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

A_max=max([a for _,_,a,_ in E])*N

D=defaultdict(lambda :[])

for u,v,a,b in E:
    u-=1;v-=1
    for from_a in range(A_max+1):
        if from_a-a<0:
            continue
        from_state_u=(u,from_a)
        to_state_v=(v,from_a-a)
        D[from_state_u].append((b,to_state_v))

        from_state_v=(v,from_a)
        to_state_u=(u,from_a-a)
        D[from_state_v].append((b,to_state_u))

for n,[c,d] in enumerate(C):
    for a in range(A_max+1):
        a_after=min(A_max,a+c)
        from_state=(n,a)
        to_state=(n,a_after)
        D[from_state].append((d,to_state))


start=(0,min(A_max,S))
Q=[(0,start)]

Dist=defaultdict(lambda :float('inf'))

Dist[start]=0

while Q:
    q = heapq.heappop(Q)
    cur_time,cur_state=q
    if Dist[cur_state]<cur_time:
        continue
    for cost,next_state in D[cur_state]:
        next_time = cost+cur_time

        if Dist[next_state]>next_time:
            Dist[next_state]=next_time
            heapq.heappush(Q,(next_time,next_state))

for dest in range(1,N):
    ans=float("inf")
    for a in range(A_max+1):
        state=(dest,a)
        ans=min(ans,Dist[state])
    print(ans)


Measured memory_bytes: 175220