akhauriyash/Code-Regression huggingface dataset:
stack = input().split()
temp  =  []
num=0
for loop in stack:
    a = loop
    if a is "+":
        num = temp.pop() + temp.pop()
        temp.append(num)
    elif a is "-":
        b=temp.pop()
        c=temp.pop()
        num = c-b
        temp.append(num)
    elif a is "*":
        num = temp.pop() * temp.pop()
        temp.append(num)
    else:
        temp .append(int(a))

print(temp[0])

Measured memory_bytes: 5600
def popcnt(x):
    return bin(x).count("1")

def main():
    N = int(input())
    Xs = input()
    X = int(Xs, 2)
    d = popcnt(X)

    lut = [0] * N
    for i in range(1, N):
        Xi = i % popcnt(i)
        lut[i] = lut[Xi] + 1

    dp = d+1
    dm = d-1
    mp = X % dp
    mm = X % dm if dm else 0
    # print(lut)
    # print(format(X, 'b'))
    
    ans = []
    for i in range(N):
        mask = 1 << (N-i-1)
        Xi = X ^ mask
        _ans = 0
        if Xs[i] == '1':
            if dm:
                m = (mm - pow(2, N-i-1, dm)) % dm
                _ans = lut[m] + 1
            # m = (mm - mask) % dm
        else:
            # m = (mp + mask) % dp
            m = (mp + pow(2, N-i-1, dp)) % dp
            _ans = lut[m] + 1
        ans.append(_ans)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Measured memory_bytes: 117072
#include<cstdio>
#include<algorithm>
using namespace std;
int main(void)
{
	int a,b,c,d,x=0,y=0,z=0;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	x=a-b;
	y=b-c;
	z=a-c;
	if(x<0) x*=-1;
	if(y<0) y*=-1;
	if(z<0) z*=-1;
	if(x<=d&&y<=d) printf("Yes\n");
	else if(z<=d) printf("Yes\n");
	else printf("No\n");
	return 0;
}


Measured memory_bytes: 1652
// https://atcoder.jp/contests/abc117/tasks/abc117_c

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))

int main() {
    int n, m, tmp;
    vector<int> v, w;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> tmp;
        v.push_back(tmp);
    }
    sort(v.begin(), v.end());

    // 座標の差分を計算
    for (int i = 1; i < m; i++) {
        w.push_back(v[i] - v[i - 1]);
    }

    sort(w.begin(), w.end());

    int sum = 0, wsize = w.size();
    for (int i = 0; i < wsize - (n - 1); i++) {
        sum += w[i];
    }

    cout << sum << endl;

    return 0;
}


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

int main(){
  int N;
  char s[64];
  int i,j,k;
  int t;
  int line[3];
  int map[10][10];
  long long int res[10];

  while(1){
    fgets(s,32,stdin);
    sscanf(s,"%d",&N);
    if(N==0)break;
    for(i=0;i<10;i++){
      for(j=0;j<10;j++){
        map[i][j]=i==j?0:1000000000;
      }
    }
    for(i=0;i<N;i++){
      fgets(s,32,stdin);
      sscanf(s,"%d %d %d",&line[0],&line[1],&line[2]);
      map[line[0]][line[1]]=line[2];
      map[line[1]][line[0]]=line[2];
    }
    for(k=0;k<10;k++){
      for(i=0;i<10;i++){
        for(j=0;j<10;j++){
          if(map[i][j]>map[i][k]+map[k][j]){
            map[i][j]=map[i][k]+map[k][j];
            map[j][i]=map[i][k]+map[k][j];
          }
        }
      }
    }
    for(i=0;i<10;i++){
      res[i]=0;
      for(j=0;j<10;j++){
        res[i]+=map[i][j];
      }
    }
    i=0;
    for(j=1;j<10;j++){
      if(res[i]>res[j])i=j;
    }
    printf("%d %lld\n",i,res[i]%1000000000);
  }
  return 0;
}

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

int dp[100001];
vector<int> to[100001];

int lp(int v) {
  if (dp[v] != -1) return dp[v];
  if (to[v].size() == 0) return 0;
  for (int u : to[v]) dp[v] = max(dp[v], lp(u) + 1);
  return dp[v];
}

int main() {
  int n, m;
  cin >> n >> m;
  rep(i, m) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    to[x].push_back(y);
  }
  rep(i, n) dp[i] = -1;
  int ans = 0;
  rep(i, n) ans = max(ans, lp(i));
  cout << ans << endl;
  return 0;
}

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

#define ll long long
#define fr first
#define sc second
#define ii pair < ll, ll >

const int N = (int)5e3 + 7;
const ll inf = (ll)1e18 + 7;

ii p[N];
ll dp[N];

bool comp (const ii &a, const ii &b) {
    return a.fr + a.sc < b.fr + b.sc;
}

main() {
    int n; scanf ("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf ("%lld %lld", &p[i].fr, &p[i].sc);
    }
    sort(p, p + n, comp);
    for (int i = 0; i <= n; i++) {
        dp[i] = inf;
    }
    dp[0] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i; j >= 0; j--) {
            if (p[i].fr >= dp[j]) {
                dp[j + 1] = min(dp[j + 1], dp[j] + p[i].sc);
            }
        }
    }
    int m = n;
    while (dp[m] == inf) m--;
    printf ("%d", m);
}


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

int main(){
	int N;
	cin >> N;
	vector<string> S(N);
	for(auto &i:S)cin >> i;
	sort(S.begin(),S.end());
	
	int m=0,c=1;
	for(int i=0;i<N;i++){
		if(i<N-1 && S[i]==S[i+1])c++;
		else{
			m=max(m,c);
			c=1;
		}
	}
	
	for(int i=0;i<N;i++){
		if(i<N-1 && S[i]==S[i+1])c++;
		else{
			if(c==m)cout << S[i] << endl;
			c=1;
		}
	}
	
	return 0;
}

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

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

int main() {
    int n,l;cin>>n>>l;
    string s[n];
    rep(i,n)cin>>s[i];
    sort(s,s+n);
    rep(i,n)cout<<s[i];
    
    cout<<endl;
	return 0;
}

Measured memory_bytes: 3624
import java.util.Scanner;
public class Main{
	public static void main(String[]args){
		Scanner sc=new Scanner(System.in);
		for(int i=0;i>-1;i++){
			int num=sc.nextInt();
			if(num==0){
				break;
			}else{
			int ave=0;
			int max=0;
			int min=1000;
			int sum=0;
				int[] score =new int[num];
				//Input scores
				for(int j=0;j<num;j++){
					score[j]=sc.nextInt();
					if(j==0){
						max=score[0];
						min=score[0];
					}
					sum+=score[j];
					if(score[j]>max){
						max=score[j];
					}else if(score[j]<min){
						min=score[j];
					}
					ave=(sum-max-min)/(num-2);

				}
				System.out.println(ave);
				}
		}
	}
}

Measured memory_bytes: 20940
#include<bits/stdc++.h>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
typedef struct exam
{
    ll l, u, b;
    exam(ll x, ll y, ll z)
    {
        b = x;
        l = y;
        u = z;
    }
}Exam;

ll n, x;
bool Compare(Exam const &ls, Exam const &rs) { 
    return (ls.u*(x-ls.b) + ls.l*ls.b) > (rs.u*(x-rs.b) + rs.l*rs.b);
}
ll val[100005] = {};
vector<Exam> e;
ll B = 0;
ll get_val(ll a)
{
    if(a != 0)
        return val[a] - val[a-1];
    return val[a];
}
bool perform(ll rem)
{
    int i;
    ll use;
    ll q = (rem/x);
    ll r = rem%x;
    ll A = ninf;
    ll temp = 0;
    if(q>0) temp = val[q-1];
    A = temp;
    if(r!=0)
    {
        FOR0(i, n)
        {
            ll cur = temp;
            if(i <= q-1) 
            {
                cur -= get_val(i);
                cur += get_val(q);
            }
            if( r > e[i].b)
                cur += e[i].u*(r - e[i].b) + e[i].b*e[i].l;
            else
                cur += r*e[i].l;
            A = MAX2(A, cur);
        }
    }
    if(A >= B) return true;
    return false;
}
int main()
{
    she_told_me_dont_worry
    cin>>n>>x;
    ll i;
    FOR0(i, n)
    {
        ll b, l, u;
        cin>>b>>l>>u;
        e.push_back(exam(b, l, u));
    }
    sort(e.begin(), e.end(), Compare);

    ll hi = 0;
    FOR0(i, n)
    {
        val[i] += e[i].l*e[i].b + (x - e[i].b)*e[i].u;
        if(i!=0) val[i] += val[i-1];
        B += e[i].l*e[i].b;
        hi += x;
    }
    //FOR0(i, n) cout<<e[i].b<<" "<<e[i].l<<" "<<e[i].u<<endl;
    ll lo = 0;
    while(hi > lo)
    {
        //cout<<lo<<" "<<hi<<endl;
        ll mid = (hi+lo)>>1;
        if(perform(mid))
            hi = mid;
        else
            lo = mid+1;
    }
    cout<<lo;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 4980
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

int main() {
	int n;
	scanf ("%d", &n);
	vector < int > a (3);
	vector < int > dp (3);
	for (int i = 0; i < n; i++) {
		vector < int > dp_new (3);
		scanf ("%d %d %d", &a[0], &a[1], &a[2]);
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 3; k++) {
				if (j != k) {
					dp_new[j] = max (dp_new[j], dp[k] + a[j]);
				}
			}
		}
		dp = dp_new;
	}
	printf ("%d\n", max ({dp[0], dp[1], dp[2]}));
	return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>


typedef long long LL;
using namespace std;
 
void read(int &v) {
    int k = 0, l = 1;
    char ch;
    ch = getchar();
    while (ch > '9' || ch < '0') {
        if (ch == '-')
            l = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') k = k * 10 + ch - '0', ch = getchar();
    v = l * k;
}

void print(int v) {
    if (v < 0)
        putchar('-'), v = -v;
    if (v > 9)
        print(v / 10);
    putchar(v % 10 + '0');
}

int max(int a, int b) {
        return a > b ? a : b;
}

int min(int a, int b) {
        return a < b ? a : b;
}

static int a;

int main() {
        read(a);
        print(3 * a * a);
        return 0;
}

Measured memory_bytes: 256
S = input()
T = input()

ns = len(S)
nt = len(T)
idx = []

for i in range(ns - nt + 1):
    for j in range(nt):
        if S[i+j] != T[j] and S[i+j] != '?':
            break
    else:
        idx.append(i)

if idx != []:
    ans = []
    for i in idx:
        s = S[:i] + T + S[i+nt:]
        ans.append(s.replace('?', 'a'))
    ans.sort()
    print(ans[0])
else:
    print('UNRESTORABLE')


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

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

typedef long long ll;
//ll const MOD = 998244353;
ll const MOD = 1e9+7;
int const inf = 1e9;
ll const INF = 1e18;

inline void ios_(){cin.tie(0); ios::sync_with_stdio(false);}
template<typename T> int size(const T& a){return (int)a.size();}
template<typename T> T Div(T a, T b){return (a + b - 1) / b;}
template<typename T> bool chmin(T& a, const T& b){if(a > b){a = b; return true;} return false;}
template<typename T> bool chmax(T& a, const T& b){if(a < b){a = b; return true;} return false;}



signed main(){
    ll a, b, c, d;
    cin >> a >> b >> c >> d;

    ll cnt_c = b / c - a / c + (a%c == 0 ? 1 : 0);
    ll cnt_d = b / d - a / d + (a%d == 0 ? 1 : 0);
    ll e = c * d / __gcd(c, d);
    ll cnt_e = b / e - a / e + (a%e == 0 ? 1 : 0);

    cout << b - a + 1 - cnt_c - cnt_d + cnt_e << endl;

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){
  int k, a[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  scanf("%d",&k);
  
  printf("%d",a[k-1]);
  
  return 0;
}

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

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

	vector<long long> a(N), b(N), c(N);
	for (int i = 0; i < N; i++) cin >> a[i];
    for (int i = 0; i < N; i++) cin >> b[i];
    for (int i = 0; i < N; i++) cin >> c[i];
    
	sort(a.begin(), a.end());
	sort(c.begin(), c.end());


	long long ans = 0;
	for (int j = 0; j < N; j++) {
		long long i = lower_bound(a.begin(),a.end(), b[j]) - a.begin();
		long long k = c.end() - upper_bound(c.begin(), c.end(), b[j]);
		ans += i * k;
	}

	cout << ans << endl;
}

Measured memory_bytes: 2688
#include<cstdio>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<map>
#include<set>
#include<limits>
#include<bitset>
#include<array>
#include<numeric>
#include<iomanip>

using namespace std;
typedef long long int ll;

int n,m;
int mn=0;

int main(){
    scanf("%d %d",&n,&m);
    vector<int> a(n);
    for(int i=0;i<n;i++)scanf("%d",&a[i]);
    a.push_back(0);
    sort(a.begin(),a.end());
    for(int i=0;i<n-m+1;i++){
        if(a[i+m]>=0 and a[i]<=0){
            if(mn)mn=min(mn,min(a[i+m]*2-a[i],a[i+m]-a[i]*2));
            else mn=min(a[i+m]*2-a[i],a[i+m]-a[i]*2);
        }
    }
    printf("%d\n",mn);
    
}

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

X = list(map(int, input().split()))
ans = 1000000000000000000
before = 0
after = sum(X)
X = X[:-1]
for i in X:
    before += i
    after -= i
    num = abs(before - after)
    ans  = min(ans, num)
print(ans)

Measured memory_bytes: 24800
#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

int main() {
  string s;
  cin >> s;
  int y = stoi(s.substr(0, 4));
  int m = stoi(s.substr(5, 2));
  int d = stoi(s.substr(8, 2));
  if (y < 2019) {
    cout << "Heisei" << endl;

  } else {
    if (m > 4) {
      cout << "TBD" << endl;
    } else {
      cout << "Heisei" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 760
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
  long long int a, v, b, w, t;
  cin>>a>>v>>b>>w>>t;
  long long int A,B;
  if(a<=b){
  A=a+v*t;
  B=b+w*t;
    if(A>=B){
      cout<<"YES"<<endl;
  }else{
      cout<<"NO"<<endl;
  }
  }else{
    A=a-v*t;
    B=b-w*t;
      if(A<=B){
      cout<<"YES"<<endl;
  }else{
      cout<<"NO"<<endl;
  }
  }
}


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

using namespace std;

int main(){
  int n;
  cin >> n;
  int vv[15][15];
  for(int i=0;i<15;i++){
      for(int j=0;j<15;j++){
          vv[i][j]=0;
      }
  }
  for(int i=0;i<n;i++){
      int t=i+1;
      string s=to_string(t);
      int m=s.size();
      int r=1;
      for(int j=0;j<m-1;j++){
          r*=10;
      }
      int p=t/r;
      t%=10;
      int q=t;
      vv[p][q]++;
      //cout << vv[p][q] << endl;
  }
  
  long long ans=0;
  for(int i=0;i<9;i++){
      for(int j=0;j<9;j++){
          ans+=vv[i+1][j+1]*vv[j+1][i+1];
      }
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#define MOD 1000000007
#define LL long long
using namespace std;
int n, x, y, z;
int ff, sum;
int dp[60][1<<18];
LL d;
LL f(int b,int k)
{
	LL ans=1;
	int base=b;
	while(k)
	{
		if(k&1)
		{
			ans=(ans*base)%MOD;
		}
		base=base*base%MOD;
		k>>=1;
	}
	return ans%MOD;
}
int main()
{
	cin>>n>>x>>y>>z;
	ff=1<<x+y+z-1;
	ff=ff|(1<<y+z-1);
	ff=ff|(1<<z-1);
	sum=(1<<(x+y+z))-1;
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	LL ans=1;
	for(int i=1;i<=n;i++)
	{
		ans*=10;
		ans%=MOD;
		for(int j=0;j<=sum;j++)
		{
			if(dp[i-1][j]==0) continue;
			for(int k=1;k<=10;k++)
			{
				int s=(j<<k)|(1<<(k-1));
				s&=sum;
				if((s&ff)!=ff)
				{
					dp[i][s]=(dp[i-1][j]+dp[i][s])%MOD;
				}
			}
		}
	}
	for(int i=0;i<=sum;i++)
	{
		ans=(ans-dp[n][i]+MOD)%MOD;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 61696
import numpy as np

n = int(input())
l = np.array(list(map(int, input().split())))

m = np.mean(l)
 
dif = abs(l - m)

mini = dif[0]
ans = 0

for i in range(n):
    if dif[i] < mini:
        mini = dif[i]
        ans = i
print(ans)

Measured memory_bytes: 22432
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] strs = br.readLine().split(" ");
    int A = Integer.parseInt(strs[0]);
    int B = Integer.parseInt(strs[1]);
    
    if (B % A == 0) {
      System.out.println(A + B);
    } else {
      System.out.println(B - A);
    }
  }
}

Measured memory_bytes: 22612
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using boost::multiprecision::cpp_int;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;

const ll INF = LLONG_MAX;
const ll MOD = 1e9+7;

// https://math.nakaken88.com/textbook/cp-binary-exponentiation-and-recursive-function/
ll modPow(ll a, ll n, int P) {
  if (n == 1) return a % P;
  if (n % 2 == 1) return (a * modPow(a, n - 1, P)) % P;
  ll t = modPow(a, n / 2, P);
  return (t * t) % P;
}

int main() {
    // input, ready
    int N;
    cin >> N;
    map<string,int> ans;
    for (int i=0; i<N; i++) {
        string S;
        cin >> S;
        ans[S]++;
    }
    // resolve

    // output
    cout << ans.size() << endl;

    return 0;
}


Measured memory_bytes: 19224
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long N = sc.nextLong();
		long A = sc.nextLong();
		long B = sc.nextLong();
		long x = N/(A+B);
		long y = N % (A+B);
		System.out.println(x * A + Math.min(A, y));

	}

}

Measured memory_bytes: 23508
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    char S[4];
    scanf("%s",S);
    
    if(S[0]=='S' && S[1]=='U')
    {
        printf("7\n");
    }
    else if(S[0]=='S' && S[1]=='A')
    {
        printf("1\n");
    }
    else if(S[0]=='M')
    {
        printf("6\n");
    }
    else if(S[0]=='T' && S[1]=='U')
    {
        printf("5\n");
    }
    else if(S[0]=='W')
    {
        printf("4\n");
    }
    else if(S[0]=='T' && S[1]=='H')
    {
        printf("3\n");
    }
    else
    {
        printf("2\n");
    }
}


Measured memory_bytes: 256
for e in iter(input,'0 0'):
 r=int(e.split()[0])
 d=[int(''.join(x),2)for x in zip(*[input().split()for _ in[0]*r])]
 a=0
 b=1<<r
 f=[1]*b
 for m in range(b):
  if f[m]:
   f[~m]=0
   t=0
   for s in d:
    c=bin(m^s).count('1')
    t+=c if c>r//2 else r-c
   if a<t:a=t
 print(a)


Measured memory_bytes: 6904
def main():
    _ = input()
    w = list(map(int, input().split()))

    ans = float("inf")
    for i in range(1, len(w)):
        s1 = sum(w[:i])
        s2 = sum(w[i:])
        # print(s1, s2)
        ans = min(ans, abs(s1-s2))
    print(ans)


if __name__ == '__main__':
    main()

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

int main() {
  int N,X,Y;
  cin>>N>>X;
  Y=X/1000;
  int a=0;
  for(int i=0;i<N+1;i++){
    for(int j=0;j<N+1-i;j++){
      if(i*10+j*5+N-i-j==Y){
        cout<<i<<" "<<j<<" "<<N-i-j<<endl;
        a=1;
        break;
      }
      if(a)break;
    }
    if(a)break;
  }
  if(a==0)cout<<-1<<" "<<-1<<" "<<-1<<endl;
}


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

using namespace std;

#define ll long long
int m = 1000000007;

ll bin_pow(int a, int pow) {
    if (pow == 1) return a % m;
    if (pow % 2 == 0) {
        ll tmp = bin_pow(a, pow / 2) % m;
        return tmp * tmp % m;
    }
    return (a % m) * (bin_pow(a, pow - 1) % m) % m;
}

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

    unordered_set<int> correct;

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

    cout << (n * 500 >= m ? "Yes" : "No");

    return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}
pub fn gcd(x: i64, y: i64) -> i64 {
    if y == 0 {
        x.abs()
    } else {
        gcd(y, x % y)
    }
}

fn solve() {
    input! {
        s: chars,
    }
    let mut ans = 0;
    let mut sum = 0;
    for i in s.iter(){
        match *i {
            'A'|'T'|'C'|'G' => sum += 1,
            _ => sum = 0,
        }
        ans = max(ans, sum);
    }
    println!("{}", ans);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include<bits/stdc++.h>
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()
 
template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

int mod_pow(int x,int y,int m=mod){
	x%=m;
	int res=1;
	while(y>0){
		if(y&1)(res*=x)%=m;
		(x*=x)%=m;
		y>>=1;
	}
	return res;
}
vector<int>perm,inv;
void init_perm(){
	int x=1e6+1;perm.resize(x);inv.resize(x);
	perm[0]=1;
	REP(i,x+1)perm[i]=perm[i-1]*i%mod;
	inv[x]=mod_pow(perm[x],mod-2);
	for(int i=x-1;i>=0;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}
int nCk(int x,int y){
	if(x<y)return 0;
	return perm[x]*inv[x-y]%mod*inv[y]%mod;
}

signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	init_perm();
	int N;cin>>N;
	int ans=0;
	REP(i,N){
		if(3*i>N)break;
		int p=N-3*i;
		ans+=nCk(p+i-1,i-1);
		ans%=mod;
	}
	cout<<ans<<"\n";
}

Measured memory_bytes: 18748
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define VIZ {printf("digraph G{\n"); for(int i=1;i<=n;i++) for es(i,e) printf("%d->%d;\n",i,vb[e]); puts("}");}
#ifdef LOCAL
#define TIMER cerr<<clock()<<"ms\n"
#else
#define TIMER
#endif
#define SZ 666666
int h,w;
char mat[233][233];
#define IMP {puts("Impossible"); return 0;}
int main()
{
	scanf("%d%d",&h,&w);
	int r=1;
	for(int i=1;i<=h;i++)
	{
		scanf("%s",mat[i]+1);
		int qwq=r;
		if(mat[i][r]!='#') IMP
		for(int j=r;j<=w;j++)
		{
			if(mat[i][j]!='#') break;
			qwq=j;
		}
		for(int j=1;j<=w;j++)
		{
			bool a=(mat[i][j]=='#'),
			b=r<=j&&j<=qwq;
			if(a!=b) IMP 
		}
		r=qwq;
	}
	puts("Possible");
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main(){
    LL n;
    cin >> n;
    vector<LL> a(n);
    LL x;
    cin >> x;
    LL sum = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
    }
    sort(a.begin(), a.end());
    if(sum == x){
        cout << n << '\n';
        return 0;
    }
    LL ans = 0;
    for(int i = 0; i < n-1; i++){
        if(x >= a[i]){
            x -= a[i];
            ans++;
        }
    }
    cout << ans << '\n';
}

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

int main() {
  string s;
  cin >> s;
  int a = s.size();
  if(a==2) cout << s << endl;
  else {
    reverse(s.begin(), s.end());
    cout << s << endl;
  }
  return 0;
}


Measured memory_bytes: 3600
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <set>

using namespace std;

#define N_MAX 110

void solv()
{
	int N; scanf("%d", &N);
	char S[N_MAX]; scanf("%s", S);

	if (1 == N % 2){
		printf("No");
		return;
	}

	for (int i = 0; i < N / 2; i++){
		if (S[i] != S[N / 2 + i]){
			printf("No");
			return;
		}
	}

	printf("Yes");

	return;
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);

	solv();

	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
long long n,a[41]={2};
int main()
{
    scanf("%lld",&n);
    for(int i=0;i<=n;i++)a[i]=a[i-1]*2+2;
    printf("%lld\n",a[n]);
    return 0;
}

Measured memory_bytes: 256
function main(input) {
  input=input.trim();
  const a = parseInt(input.split(" ")[0], 10);
  const b = parseInt(input.split(" ")[1], 10);
  const c = parseInt(input.split(" ")[2], 10);
  if(a!=b&&a!=c){
    console.log(a);
  }else if(b!=a&&b!=c){
    console.log(b);
  }else{
    console.log(c);
  }
  
}

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



Measured memory_bytes: 7372
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int Trie[100010][2], tz, leaf[100010];
int n;
char buf[100010];
ll L;

ll dfs(int x, int dep = 0) {
	if(leaf[x]) return 0;
	ll res = 0;
	rep(u, 2) {
		int nxt = Trie[x][u];
		if(nxt == 0) {
			ll tl = L - dep;
			res ^= (tl & -tl);
		}
		else res ^= dfs(nxt, dep + 1);
	}
	return res;
}

void solve() {
	scanf("%d%lld", &n, &L);
	rep(i, n) {
		scanf("%s", buf);
		int now = 0;
		for(int j=0;buf[j];j++) {
			int c = buf[j] - '0';
			if(Trie[now][c] == 0) Trie[now][c] = ++tz;
			now = Trie[now][c];
		}
		leaf[now] = 1;
	}
	printf("%s\n", dfs(0) == 0 ? "Bob" : "Alice");
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}




Measured memory_bytes: 5760
using namespace std;

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <climits>
#include <bitset>
#define all(x) (x).begin(),(x).end()

void solve(){

}
int main(){
    int N;
    vector<int> p;
    cin >> N;
    int x;
    for (int i = 0; i < N; i++){
        cin >> x;
        p.push_back(x);
    }
    sort(all(p));
    int sum = 0;
    for (int i = 0; i < N; i++){
        if (i == N-1){
            sum += p[i]/2;
        } else {
            sum += p[i];
        }
    }
    cout << sum << endl;





    return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public final class Main {

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = Integer.parseInt(in.nextLine());
        int[] arr = new int[n];
        final Map<Integer, Integer> count = new HashMap<>();
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
            count.merge(arr[i], 1, Integer::sum);
        }
        in.nextLine();
        arr = Arrays.stream(arr).distinct().sorted().toArray();

        long res = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    if (arr[i] + arr[j] > arr[k]) {
                        res += count.get(arr[i]) * count.get(arr[j]) * count.get(arr[k]);
                    }
                }
            }
        }
        System.out.println(res);
    }
}


Measured memory_bytes: 46436
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;cin >> a >> b >> c;
    if((a==b&&a!=c)||(b==c&&b!=a)||(c==a&&c!=b)){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

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

int main(void){
   vector<vector<string> > a(3,vector<string>(3));
   for(int i=0;i<3;i++){
       for (int j = 0; j< 3; j++)
       {
           cin >> a[i][j];
       }  
   }
   int n;
   cin >> n;
   vector<string> b(n);
   for(int i=0;i<n;i++){
       cin >> b[i];
   }
    vector<bool> c(9,false);
    for(int i=0;i<3;i++){
       for (int j = 0; j< 3; j++)
       {
           for(int k=0;k<n;k++){
               if (b[k] == a[i][j]) {
                   c[3*i+j] = true;
               }
           }
       }  
   }
   if(c[0] && c[1] && c[2] || c[3] && c[4] && c[5] || c[6] && c[7] && c[8] || 
   c[0] && c[3] && c[6] || c[1] && c[4] && c[7] || c[2] && c[5] && c[8] ||
   c[0] && c[4] && c[8] || c[2] && c[4] && c[6]) cout << "Yes" << endl;
   else cout << "No" << endl;
}


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

#define pb  push_back
#define ll  long long
#define INF 0x3f3f3f3f
#define pii pair<int, int>
#define ull unsigned long long int

const int t = 100005;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    ll dp[2][t], w;
    int p[105], v[105];
    int n;
    
    cin >> n >> w;
    for (int i = 1; i <= n; i++)
        cin >> p[i] >> v[i];
    
    for (int i = 0; i < t; i++)
        dp[0][i] = dp[1][i] = (ll) 1e18;
    dp[0][0] = 0LL;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= t - 5; j++) {
            ll passa = dp[(i - 1) & 1][j];
            if (j - v[i] < 0) {
                dp[i & 1][j] = passa;
                continue;
            }
            ll pega = dp[(i - 1) & 1][j - v[i]] + p[i];
            dp[i & 1][j] = min(pega, passa);
        }
    }

    int ans = 0;
    for (int i = 0; i < t; i++) {
        if (dp[n & 1][i] <= w)
            ans = max(ans, i);
    }
    cout << ans << "\n";
    
    //cerr << "\n" << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
    return 0;
}

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

main(){
  int n, k;
  cin >> n >> k;
  vector<pair<int,int>> p(n);
  rep(i,n){
    int a, b;
    cin >> a >> b;
    p[i]=make_pair(a,b);
  }
  sort(p.begin(),p.end());
  int ans;
  ll tmp=0;
  rep(i,n){
    tmp += p[i].second;
    if(tmp >= k){
      ans=p[i].first;
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 4816
#include <iostream>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MN = 1e5 + 5, LN = 20;
int N, W;
ll dp[MN];

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> N >> W;
    for (int i = 1, w, v; i <= N; i++) {
        cin >> w >> v;
        for (int j = W; j >= w; j--)
            dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[W] << '\n';
    return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k;
    cin>>n>>k;
    ll h[n];
    for(ll i=0;i<n;i++)
        cin>>h[i];
    ll dp[n];
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    for(ll i=2;i<n;i++)
    {
        ll mini=max((ll)0,i-k);
        dp[i]= 1e18;
        for(ll j=mini;j<i;j++)
        {
            dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]));
        }
    }
    cout<<dp[n-1];
}

Measured memory_bytes: 1792
import java.util.Scanner;
 
public class Main{
  public static void main(String args[]){ 
    Scanner scan = new Scanner(System.in);
    String str = scan.next();
   
    String last = str.replaceAll("hi", "");
    if(last.length() == 0) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
   }
}

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def gcd(n,m):
    if m == 0:
        return n
    else:
        return gcd(m,n%m)
a,b = LI()
g = gcd(a,b)
ans = a*b//g
print(ans)



Measured memory_bytes: 38384
#include <iostream>
using namespace std;
signed main() {
	int n, m, x[123];
	cin >> n; for (int i = 0; i < n; i++)cin >> x[i]; cin >> m;
	x[n] = 2020;
	for (int i = 0; i < m; i++) {
		int p; cin >> p;
		p--;
		x[p] = min(x[p] + 1, x[p + 1] - 1);
	}
	for (int i = 0; i < n; i++)cout << x[i] << endl;
}


Measured memory_bytes: 3076
inp = require('fs').readFileSync('/dev/stdin', 'utf8').split('\n')
N = inp.shift() * 1
l = inp.shift().split(' ')
T = l.shift() * 1
A = l.shift() * 1
l = inp.shift().split(' ')
min = 10000
j = 0
for(i=0; i<N; i++) {
    abs = Math.abs(A - (T - (l[i] * 1) * 0.006))
    if (min > abs) {
        min = abs
        j = i
    }
}
console.log(j+1)

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

const int N = (int) 1e5;
int a[N], n;

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> a[i];
    long long res = 0;
    for (int i = 0; i < n; ++i) {
        res += a[i] / 2;
        if (a[i] % 2 != 0 && a[i + 1] > 0) {
            --a[i + 1];
            ++res;
        }
    }
    cout << res << endl;
    return 0;
}


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

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

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

int main(){
  ll n, x;
  cin >> n >> x;

  vector<ll> city(n);
  rep(i,n){
    cin >> city.at(i);
    city.at(i)-=x;
    if(city.at(i)<0) city.at(i)*=-1;
  }

  ll ans=city.at(0);
  rep(i,n){
    if(city.at(i)!=0) ans = gcd(ans, city.at(i));
  }

  cout << ans;
}

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

int main() {
  int N;
  cin >> N;
  vector<int> data(N);
  for(int i = 0; i < N; i++){
    cin >> data.at(i);
    data.at(i)--;
  }
  int now = 0;
  int c = 0;
  for(int i = 0; i < N; i++){
    if(now == 1){
      cout << c << endl;
      break;
    }
    now = data[now];
    c++;
    if( c >= N){
      cout << -1 << endl;
    }
  }
  
}

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

using namespace std;

class DisjointSet {
    public:
        vector<int> rank, p;
        
        DisjointSet() {}
        DisjointSet(int size){
            rank.resize(size, 0);
            p.resize(size, 0);
            for(int i = 0; i < size; i++) makeSet(i);
        }
        
        void makeSet(int x){
            p[x] = x;
            rank[x] = 0;
        }
        
        bool same(int x, int y){
            return findSet(x) == findSet(y);
        }
        
        int findSet(int x){
            if(x != p[x]){
                p[x] = findSet(p[x]);
            }
            
            return p[x];
        }
        
        void unite(int x, int y){
            link(findSet(x), findSet(y));
        }
        
        void link(int x, int y){
            if(rank[x] > rank[y]){
                p[y] = x;
            } else {
                p[x] = y;
                if(rank[x] == rank[y]){
                    rank[y]++;
                }
            }
        }
};


int main(void){
    // Your code here!
    int n, q, com, x, y;
    cin >> n >> q;
    DisjointSet ds = DisjointSet(n);
    for(int i = 0; i < q; i++){
        cin >> com >> x >> y;
        if(com==0) ds.unite(x, y);
        else if(com==1){
            if(ds.same(x, y)) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
    
    return 0;
}



Measured memory_bytes: 3172
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FORR(i, a, b) for (int i = b - 1; i >= a; --i)
#define SORT(v) sort(v.begin(), v.end())
#define SORTR(v) sort(v.rbegin(), v.rend())
#define REV(v) reverse(v.begin(), v.end())
#define ITER(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define LB(v, x) (lower_bound(v.begin(), v.end(), x) - v.begin())
#define UB(v, x) (upper_bound(v.begin(), v.end(), x) - v.begin())
#define SZ(v) (int)v.size()
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

    int N;
    cin >> N;
    vector<ll> A(N + 1);
    REP(i, N) {
        cin >> A[i];
    }
    ll m = 1000, k = 0;
    REP(i, N) {
        if (k == 0) {
            while (i < N && A[i] >= A[i + 1]) {
                ++i;
            }
            if (i == N) {
                break;
            }
            k = m / A[i];
            m -= k * A[i];
        } else {
            while (i < N && A[i] <= A[i + 1]) {
                ++i;
            }
            m += A[i] * k;
            k = 0;
        }
    }
    cout << m << endl;

    return 0;
}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#define rep(i,N) for (int i = 0; i < (N); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
int main(void){
  int n;
  cin >> n;

  cout << ceil(n / 2.0) << endl;
}


Measured memory_bytes: 3764
#!/usr/bin/env python
"""AtCoder Beginner Contest 173: A - Payment
https://atcoder.jp/contests/abc173/tasks/abc173_a
"""

import math


def main():
    N = int(input())
    print(math.ceil(N / 1000) * 1000 - N)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9172
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<math.h>
#include<queue>
#include<stack>
#include<ctime>
#include<set>
using namespace std ;

int n , m ;
priority_queue < int > q ;

void input ( ) {
    scanf ( "%d%d" , &n , &m ) ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        int x ;
        scanf ( "%d" , &x ) , q.push ( x ) ;
    }
}

void solve ( ) {
    while ( m -- ) {
        int x = q.top ( ) ;
        q.pop ( ) ;
        q.push ( x / 2 ) ;
    }
    long long ans = 0 ;
    while ( q.empty ( ) == false ) {
        ans += q.top ( ) ;
        q.pop ( ) ;
    }
    printf ( "%lld\n" , ans ) ;
}

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


Measured memory_bytes: 892
/**
 * Created by hiramekun at 20:53 on 2019-11-23.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) {
        if (i % 10 == 0) cout << "i=" << i << " | ";
        out << list[i] << ' ';
    }
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
ll f(ll n) {
    ll ret = 0;
    while (n > 0) ret += (n % 10), n /= 10;
    return ret;
}

void solve() {
    ll m;
    cin >> m;

    ll s = 0, n = 0;
    rep(i, m) {
        ll d, c;
        cin >> d >> c;
        s += d * c;
        n += c;
    }
    cout << n - 1 + (s - 1) / 9 << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>

#define barsik ios::sync_with_stdio(false)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair <int, int> pii;
typedef std::unordered_set <int> u_si;

using namespace std;


void solve(){
    string s;
    cin >> s;
    int cnt = 1;
    for(int i = 0; i < s.size() - 1; i++){
        if(s[i] != s[i + 1]) cnt++;
    }
    cout << cnt - 1;
}

int main(){
    barsik;
    int q = 1;
    //cin >> q;
    while(q--) solve();
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<int, int> > adj[100010];
int assigned[100010], val[100010];
bool poss = false;
void possible(int a, int v)
{
	if (assigned[a] && val[a] != v) poss = false;
	if (assigned[a]) return;
	assigned[a] = true;
	val[a] = v;
	for (auto b : adj[a]) possible(b.first, v + b.second);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		adj[a].emplace_back(b, c);
		adj[b].emplace_back(a, -c);
	}
	poss = true;
	for (int i = 0; i < n; i++)
	{
		if (!assigned[i]) possible(i, 0);
	}
	if (!poss) printf("No\n");
	else printf("Yes\n");
}


Measured memory_bytes: 11392
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#define INF 1e9+7
using namespace std;
typedef long long int ll;


int main() {

	int a[2] = { 0 };
	for (int i = 0; i < 3; i++) {
		int c;
		cin >> c;
		if (c == 5) { a[0]++;
		}
		else if(c==7){
			a[1]++;
		}
	}


	if (a[0] == 2 && a[1] == 1) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n;
  cin >> n;
  int ans = 0;
  vector<int> a(n);
  for(int i = 1; i <= n; i++) {
    int x;
    cin >> x;
    if(i % 2 != 0 && x % 2 != 0 ) {
      ans += 1;
    }

  }
  cout << ans << endl;
}


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

using namespace std;

#define ll long long

int main(){
   int n;
   cin>>n;
   int a[n];
   for(int i=0; i<n; i++){
       cin>>a[i];
   }
   sort(a,a+n);
//    for(int i=0; i<n; i++){
//        for(int j=i+1; j<n; j++){
//            if(a[i]!=a[j])
//        }
//    }
    cout<<a[n-1]-a[0]<<endl;

}

Measured memory_bytes: 256
from collections import Counter
n=int(input())
s = []
for i in range(n):
    t = list(input())
    t.sort()
    s.append(''.join(t))
c = Counter(s)
sum = 0
for i in c.values():
    sum += i*(i-1)//2
print(sum)

"""
n = int(input())
dic = {}
for i in range(n):
    s = list(input())
    s.sort()
    t = "".join(s)
    if t in dic.keys():
        dic[t] += dic[t] + 1
    elif t not in dic.keys():
        dic[t] = 0
print(sum(dic.values()))
"""

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

int main(void)
{
  int N, A, B;
  std::cin >> N >> A >> B;

  int minReader = std::max(0, A+B-N);
  int maxReader = std::min(A, B);
  
  std::cout << maxReader << " " << minReader << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define LL long long
template<class T> inline void chmax(T & a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> void print_vector(vector<T> vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << vec[i] << " ";
	}
	cout << "]" << endl;
}
template<class T> void print_pair_vector(vector<pair<T, T> > vec) {
	cout << "[ ";
	for (int i = 0; i < vec.size(); i++) {
		cout << "(" << vec[i].first << "," << vec[i].second << ") ";
	}
	cout << "]" << endl;
}

int main(void) {
	int N;
	cin >> N;
	
	vector<LL> a(3*N);
	rep(i, 3*N) cin >> a[i];
	sort(RALL(a));

	LL ans = 0;
	for (int i = 1; i < 2*N; i+=2){
		ans += a[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <string>

using namespace std;

int main(){
    int L;
    string S;

    cin >> S;

    L = S.length();
    if(S.substr(L - 1, L) == "s"){
        cout << S << "es" << endl;
    }else{
        cout << S << "s" << endl;
    }

    return 0;
}


Measured memory_bytes: 3632