akhauriyash/Code-Regression huggingface dataset:
#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 1e17
#define ninf -1e17
#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.
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;
ll dp[200005];
ll h[200005];
ll a[200005];
ll st[800005] = {};
ll n;
ll left(ll p)
{
    return (p<<1);
}
ll right(ll p)
{
    return (p<<1) + 1;
}
void update(ll p, ll l, ll r, ll pos, ll val)
{
    if(l>pos||r<pos)
        return;
    if(l==r)
    {
        st[p] = val;
        return;
    }
    ll mid = (l+r)/2;
    update(left(p), l, mid, pos, val);
    update(right(p), mid+1, r, pos, val);
    st[p] = MAX2(st[left(p)], st[right(p)]);
    return;
}
ll query(ll p, ll l, ll r, ll i, ll j)
{
    if(i>r||j<l)
        return ninf;
    if(l>=i&&r<=j)
        return st[p];
    ll mid = (l+r)/2;
    ll lv = query(left(p), l, mid, i, j);
    ll rv = query(right(p), mid+1, r, i, j);
    ll rev = MAX2(lv, rv);
    return rev;
}
int main()
{
    she_told_me_dont_worry
    cin>>n;
    int i;
    FOR0(i, n) cin>>h[i];
    FOR0(i, n) cin>>a[i];
    ll ans = 0;
    FORD(i, n-1, 0)
    {
        ll cur = a[i]; 
        if(h[i]!=n)
            cur += query(1, 1, n, h[i]+1, n);
        ans = MAX2(ans, cur);
        update(1, 1, n, h[i], cur);
    }
    cout<<ans;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 10496
n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)

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

int main(void)
{
	int n;
	int dx,dy;
	int x,y;
	int max,max_x,max_y;
	int d;

	int i1,i2;

	
	
	
	

	cin >> n;

	for(i1=0; i1<n; i1++){
		x = 0;
		y = 0;
		max = 0;
		max_x = 0;
		max_y = 0;


		while(1){

			cin >> dx >> dy;
			if(dx==0 && dy==0)break;

			x += dx;
			y += dy;
			d = x*x + y*y;

			if( max <= d){
				if( max == d){
					if (max_x < x){
						max = d;
						max_x = x;
						max_y = y;
					}
				}
				else {
					max = d;
					max_x = x;
					max_y = y;
				}
			}

		}

		cout << max_x << " " << max_y << endl;
	}


	return 0;
}

Measured memory_bytes: 1160
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=1e9+7;

int main(){

	ll x, y;
	cin >> x >> y;
	if(x==y || x%y==0){
		cout << -1 << endl;
	} else {
		for(int i=1; ; i++){
			if(x*i%y!=0){
				cout << x*i << endl;
				return 0;
			}
		}
	}


	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define V vector
#define VI vector<int>
#define VVI vector<vector<int>>

using namespace std;

int main(void){
    long N,ans=0,cnt=0;
    cin>>N;
    vector<string> s(N);
    rep(i,N){
        cin>>s[i];
        sort(s[i].begin(),s[i].end());
    }
    sort(s.begin(),s.end());
    for(int i=1;i<N;i++){
        if(s[i-1]==s[i]){
            cnt+=1;
            ans+=cnt;
        }
        else{
            cnt=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 7296
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<int> p(n);
	int ans = 0;

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

	for (int i = 1; i < n - 1; i++) {
		if ((p[i - 1] < p[i] && p[i] < p[i + 1]) || (p[i - 1] > p[i] && p[i] > p[i + 1])) {
			ans++;
		}
	}

	printf("%d", ans);

	return 0;
}

Measured memory_bytes: 256
n = int(input())
d = list(map(int, input().split(' ')))
d = sorted(d)
mid = n//2-1
if d[mid] == d[mid+1]:
  ans = 0
else:
  start = d[mid] +1
  end = d[mid+1] 
  ans = end - start + 1
print(ans)

Measured memory_bytes: 14428
// Allocation
#include<iostream>

using namespace std;

const int MAX_N = 100000;
const int MAX_Wi = 10000;

typedef long long llong;

int n, k;
llong T[MAX_N];

// 最大積載量 P の k 台のトラックで何個の荷物を積めるかを調べる関数
int check(llong P)
{
    // 積載されている荷物の数
    int i = 0;

    for(int j = 0; j < k; j++)
    {
        // トラックに積載されている荷物の重量
        llong s = 0;

        while( s + T[i] <= P )
        {
            s += T[i];
            i++;

            if( i == n )
            {
                return n;
            }
        }
    }

    return i;
}

// 2分探索を用いて、検索を実施する関数
int solve()
{
    llong left = 0;
    // ( 荷物の個数　) * ( 1個あたりの最大重量 )
    llong right = MAX_N * MAX_Wi;
    llong mid;

    while( right - left > 1 )
    {
        mid = ( left + right ) / 2;
        // 最大積載量を決めて、何個の荷物が積めるかを確認する
        int v = check(mid);

        if( v >= n )
        {
        	// 最大積載量の最小値を検索するため、右側を移動する
            right = mid;
        }
        else
        {
        	// 最大積載量が少なかったので、左側を移動する
            left = mid;
        }
    }

    return right;
}

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

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

    llong ans = solve();

    cout << ans << '\n';
}



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

int main(){

  int e, cpy;

  while(cin >> e && e){

    int m = INT_MAX;

    for(int i = 0; i*i <= e; i++){
      for(int j = 0; j*j*j <= e; j++){
	cpy = e - i*i - j*j*j;
	if(e == i*i + j*j*j + cpy && cpy >= 0){
	    m = min(m,i+j+cpy);
	}
      }
    }
    cout << m << endl;

  }

 
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);



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

  REP(i, 50000){
    double ans = 1;
    ans = i * 1.08;
    ans = (int)ans;
    if(n == ans){
      cout << i << endl;
      return 0;
    }
  }

  cout << ":(" << endl;
  return 0;
}


Measured memory_bytes: 3604
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())


def resolve():
    K = int(input())
    s = input()
    ls = len(s) - 1
    mod = 10**9+7

    N = ls + K

    N1 = N + 1
    fact = [1] * N1
    inv = [1] * N1

    for i in range(2, N1):
        fact[i] = fact[i-1] * i % mod

    inv[N] = pow(fact[N], mod-2, mod)
    for i in range(N-1, 1, -1):
        inv[i] = inv[i+1]*(i+1) % mod

    def cmb(a, b):
        return fact[a] * inv[b] % mod * inv[a-b] % mod

    ans = 0
    p25 = 1
    p26 = pow(26, K, mod)
    p26inv = 576923081 #pow(26,  mod-2, mod)
    for i in range(K+1):
        ans = (ans + cmb(ls+i, ls) * p25 % mod * p26 % mod) % mod
        p25 = p25 * 25 % mod
        p26 = p26 * p26inv % mod
    print(ans)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 101888
def i():
	return int(input())
def i2():
	return map(int,input().split())
def s():
	return str(input())
def l():
	return list(input())
def intl():
	return list(int(k) for k in input().split())

n = i()
s,t = map(str,input().split())

for i in range(n):
	print(s[i], end="")
	print(t[i], end="")

Measured memory_bytes: 9096
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int n;
vector<int> g[maxn];
int dep[maxn];
int len, id;
bool SG[maxn];
void dfs(int x) {
	if (dep[x] > len) len = dep[x], id = x;
	for (int i = 0; i < g[x].size(); i++) {
		if (!dep[g[x][i]]) {
			dep[g[x][i]] = dep[x] + 1;
			dfs(g[x][i]);
		}
	}
}
int main() {
	scanf("%d", &n);
	memset(dep, 0, sizeof(dep));
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dep[1] = 1;
	dfs(1);
	memset(dep, 0, sizeof(dep));
	dep[id] = 1;
	dfs(id);
	SG[1] = 1; SG[2] = 0;
	for (int i = 3; i <= n; i++) {
		SG[i] = !(SG[i - 1] & SG[i - 2]);
		//printf("%d ", SG[i]);
	}
	//puts("");
	if (SG[len]) printf("First\n");
	else printf("Second\n");
	return 0;
}

Measured memory_bytes: 21504
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), a = sc.nextInt(), b = sc.nextInt();
        System.out.println(Math.min(n * a, b));
    }


    void debug(Object...os) {
        System.err.println(Arrays.deepToString(os));
    }

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


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

using ll = long long;

template<long long mod>
class modint{
private:
  long long num;
  long long extgcd(long long a, long long b, long long&x, long long&y)const {
    long long d = a;
    if(b != 0){d = extgcd(b, a%b, y, x);  y -= (a/b) * x;}
    else{x = 1; y = 0;}
    return d;
  }
  long long modinverse()const{
    long long x, y;
    extgcd(num, mod, x, y);
    return (mod + x%mod)%mod;
  }
public:
  modint():num(0){}
  modint(const long long x):num((x < 0?(x+mod):x)%mod ){}
  friend modint operator+(const modint&a, const modint&b)
  {    return modint(a.num + b.num);  }
  friend modint operator-(const modint&a, const modint&b)
  {    return modint(a.num - b.num);  }
  friend modint operator*(const modint&a, const modint&b)
  {    return modint(a.num * b.num);  }
  friend modint operator/(const modint&a, const modint&b)
  {    return modint(a*b.modinverse());  }
  friend ostream& operator<<(ostream&os, const modint&a){
    os << a.num;
    return os;
  }
};


int main(){
  const ll mod = (1e+9)+7;
    
  ll n, k;cin >> n >> k;

  ll l = n - k;
  vector<modint<mod>>red(l + 1, l + 1);
  for(ll i = 1; i < l + 1; ++i)
    red[i] = (((red[i - 1] * (l+1-i)))) / (i+1);
  vector<modint<mod>>blue(k,1);
  for(ll i = 1; i < k; ++i)
    blue[i] = (((blue[i - 1] * (k-i)))) / i;
  for(ll i = 0; i < k; ++i){
    //   debug(red[i]);
    //    debug(blue[i]);
    if(i < l + 1)
      cout << (red[i] * blue[i]) << endl;
    else
      cout << 0 << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);};};
const int MOD = 1000000007;
const int INF = INT_MAX;
const ll LLINF = 1LL<<62;





int main(void) {

    // int n;
    // cin>>n;
    // bool ch=false;
    // for(int i=1;i<10;i++){
    //     for(int j=1;j<10;j++){
    //         if(i*j==n)ch=true;
    //     }
    // }
    // if(ch)fin("Yes");
    // else fin("No");
    int a,b;
    cin>>a>>b;
    if(a<10&&b<10)cout<<a*b<<endl;
    else fin(-1);

}



Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
using namespace std;
#define MOD 1000000007
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec; typedef pair<int, int> pi;
int dd[] = { 0, 1, 0, -1, 0 };


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

	int r = 0, l = 0;
	int a = 0, b = 0;
	int m = 0;
	for (int i = 0; i < N; i++)
	{
		if (S[i] == '(')
		{
			l++;
		}
		else
		{
			r++;
		}
		m = min(m, l - r);
	}
	//cout << m << endl;
	for (int i = 0; i < -m; i++)
	{
		cout << '(';
	}
	cout << S;
	for (int i = 0; i < (l-r)-m; i++)
	{
		cout << ')';
	}
	cout << endl;;
	return 0;
}


Measured memory_bytes: 256
s = input()
l = []
ans = 7
for i in range(4):
    l.append(s[i])

for i in range(1 << 3):
    op = []
    for j in range(3):
        if i & (1 << j):
            op.append('+')
        else:
            op.append('-')

    tmp = str(l[0])
    for k in range(3):
        tmp += op[k]
        tmp += str(l[k+1])

    if eval(tmp) == ans:
        tmp += '=7'
        print(tmp)
        exit()


Measured memory_bytes: 3064
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <ctime>
#include <memory.h>
#include <bitset>
#include <climits>
#include <iomanip>

#define F first
#define S second
#define endl "\n"
#define pb push_back
#define mp make_pair
#define bs 1000000007
#define pi 3.141592653589793
#define y1 kjdfshnvoavaofobiopj
#define ends yryrqayrehojoborolo
using namespace std;

string st, ts;

int main(){
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);

cin>>st;
for(int i = 0; i < st.size(); i++)
{
    if(st[i] == ',')
        ts += ' ';
    else
        ts += st[i];
}
cout<<ts<<endl;

return 0;}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define se second
#define fi first
#define pb push_back
#define cn cout<<"\n"
#define rep(i,a,b) for(int i = a; i < b; i++)
#define repr(i,a,b) for(int i = a; i >= b; i--)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()

#define _ ios::sync_with_stdio(0); cin.tie(0);

#define vi vector<int>
#define ii pair<int,int>
#define vii vector<ii>
#define ll long long
#define vll vector<ll>
#define flush fflush(stdout)

const int INF = 1e8;
const ll MOD = 1e9 + 7;

using namespace std;

int main(){
	_

	int t = 1, a, b , c;

	// cin>>t;

	rep(nc, 0, t){
		cin>>a>>b>>c;

		cout<<(c/a) * b; cn;
	}

	return 0;
}

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

int main() {
	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2;
	int x3, y3, x4, y4;
	x3 = x2 - (y2 - y1);
	y3 = y2 + (x2 - x1);
	x4 = x1 - (y2 - y1);
	y4 = y1 + (x2 - x1);

	printf("%d %d %d %d\n", x3, y3, x4, y4);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main(void){
    int n;
    scanf("%d",&n);
    char str[n][11],strc[11];
    int ary[n][2],i,j,judge[2],memo;
    for(i=0;i<n;i++){
        scanf("%s %d",&str[i][0],&ary[i][0]);
        ary[i][1]=i+1;
    }
    for(i=0;i<n-1;i++){
        strcpy(strc,&str[i][0]);
        judge[0]=ary[i][0];
        judge[1]=ary[i][1];
        memo=i;
        for(j=i+1;j<n;j++){
            if(strcmp(strc,&str[j][0])>0){
                strcpy(strc,&str[j][0]);
                judge[0]=ary[j][0];
                judge[1]=ary[j][1];
                memo=j;
            }else if(strcmp(strc,&str[j][0])==0&&judge[0]<ary[j][0]){
                strcpy(strc,&str[j][0]);
                judge[0]=ary[j][0];
                judge[1]=ary[j][1];
                memo=j;
            }
        }
        strcpy(&str[memo][0],&str[i][0]);
        ary[memo][0]=ary[i][0];
        ary[memo][1]=ary[i][1];
        strcpy(&str[i][0],strc);
        ary[i][0]=judge[0];
        ary[i][1]=judge[1];
        printf("%d\n",ary[i][1]);
    }
    printf("%d\n",ary[i][1]);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(25);

  ll n;
  cin >> n;
  vector<ll> a(n + 1);
  rep(i, n + 1) cin >> a[i];

  ll ans = 0, res = 1;
  vector<ll> asum = a;
  repr(i, n - 1) asum[i] += asum[i + 1];
  rep(i, n + 1) {
    if (res < a[i]) {
      cout << -1 << '\n';
      return 0;
    }
    ans += res;
    res -= a[i];
    res *= 2;
    if (i != n) chmin(res, asum[i + 1]);
    //cout << res << '\n';
  }
  cout << ans << '\n';




  
  return 0;
}

Measured memory_bytes: 4780
use proconio::{fastout, input, marker::*};

#[fastout]
fn main() {
    input! {
        k: usize,
        n: usize,
        a: [usize; n],
    }
    let mut ans = 0;
    let mut max = 0;
    let mut dp = a.clone();
    dp.push(k + dp[0]);

    for i in 1..dp.len() {
        let m = dp[i] - dp[i - 1];
        ans += m;
        max = std::cmp::max(m, max);
    }

    println!("{}", ans - max);

}


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

int main() {
	int w, a, b; cin >> w >> a >> b;

	int num = max(a + w, b + w) - min(a, b);
	if (num <= w * 2) cout << 0 << endl;
	else cout << num - w * 2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<vector>
using namespace std;
vector<int> digit;
int n, k;
int aa(int ex,int val,bool first) {
	if (ex == 0) return val;
	if (first) {
		int ret = aa(ex / 10, val, true);
		if (ret >= n) return ret;
	}
	for (int next:digit) {
		int ret = aa(ex / 10, val + next * ex, false);
		if (ret >= n) return ret;
	}
	return val;
}
int main() {
	scanf("%d%d", &n, &k);
	int i;
	bool use[10];
	for (i = 0; i < 10; i++) use[i] = true;
	for (i = 0; i < k; i++) {
		int a;
		scanf("%d", &a);
		use[a] = false;
	}
	for (i = 0; i < 10; i++) if (use[i]) digit.push_back(i);
	printf("%d",aa(10000,0,1));
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

int MOD=1e9+7;
ll INF=1e18;

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

int main(){
    int n; cin>>n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin>>a[i];

    ll sum=0;
    for(int i=0; i<n; i++){
        sum+=a[i]/2;
        a[i]=(a[i]%2==0?0:1);
        if(i+1<n && a[i] && a[i+1]){
            a[i]--, a[i+1]--;
            sum++;
        }
    }
    cout << sum << endl;
}

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


int main()
{
	string s;
	cin>>s;
	for(int i=0;i<3;i++)
	{
		if(s[i]=='1')cout<<"9";
		else if(s[i]=='9')cout<<"1";
		else cout<<s[i];
	}
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int a, b;
    scanf("%d%d", &a, &b);
    if (a == 1)
        a = 14;
    if (b == 1)
        b = 14;
    if (a > b)
        printf("Alice\n");
    else if (b > a)
        printf("Bob\n");
    else
        printf("Draw\n");
}

Measured memory_bytes: 128
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($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)*}
    };
}

#[allow(unused_macros)]
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)*}
    };

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

#[allow(unused_macros)]
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:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      m: usize,
      aa: [usize; m],
    }
    let sum: usize = aa.iter().sum();
    if sum > n {
        puts!("{}\n", -1);
    } else {
        puts!("{}\n", n-sum);
    }
}


Measured memory_bytes: 2192
def mod2(num):
    return num % 2

def solve():
    # 標準入力
    N, M = list(map(int, input().split()))  # N: スイッチの数， M: 電球の数
    k = [0] * M  # 電球iにつながっているスイッチの数
    s = [[0] for _ in range(M)]  # 電球iにつながっているスイッチの番号
    for i in range(M):
        tmp = list(map(int, input().split()))
        k[i] = tmp[0]
        s[i] = tmp[1::]
    p = list(map(int, input().split()))

    # スイッチの状態を総当たり
    count = 0
    for switch_state in range(2**N):
        p_tmp = [0] * M
        iter_num = format(switch_state, '0'+str(N)+'b')
        # 電球ごとに条件をチェック, i: i番目の電球，s_i: i番目の電球に接続しているスイッチのリスト
        for i, s_i in enumerate(s):
            # 電球iに接続しているスイッチs_i_jがon/offかチェック
            for s_i_j in s_i:
                if (iter_num[s_i_j-1] == '1'):
                    p_tmp[i] += 1
        if(p == list(map(mod2, p_tmp))):
            count += 1
    print(count)

if __name__ == "__main__":
    solve()

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

#define mp make_pair
#define pb push_back

#define int int64_t
#define ld long double

const int MOD = 1e9+7;
const int N = 1e6+5;

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

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

    cout<<max({dp[n-1][0], dp[n-1][1], dp[n-1][2]});

    return 0;
}

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

bool ms(int n) {
	return n % 7 == 1 || n % 7 == 6;
}

int main() {
	vector<bool> a(300000, true);
	for (int i = 2; i < 300000; i++) {
		if (a[i]) {
			for (int j = 2 * i; j < 300000; j += i) {
				a[j] = a[j] && !(j % i) && !ms(j / i);
			}
		}
	}
	int n;
	while (cin >> n, n > 1) {
		set<int> s;
		for (int i = 2; i <= n; i++) {
			if (a[i] && !(n % i) && ms(n / i)) {
				s.insert(i);
			}
		}
		cout << n << ":";
		for (auto it = begin(s); it != end(s); it++) {
			cout << " " << *it;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3092
H,W = gets.split.map(&:to_i)
C = (0..9).map{ gets.split.map(&:to_i) }

costs = (0..9).map{ 1000*1000 }
costs[1] = 0
queue = [1]
while f = queue.shift
  (0..9).each{ |t|
    next if f == t
    c = C[t][f]
    next if costs[f] + c >= costs[t]
    costs[t] = costs[f] + c
    queue.push(t)
  }
end

#p costs

puts (0...H).map{ 
  gets.split.map(&:to_i).map{ |a| a >= 0 ? costs[a] : 0 }.inject(:+)
}.inject(:+)

Measured memory_bytes: 3964
list1= input().split(" ")
list2= input().split(" ")
X=int(list1[0])
N=int(list1[1])
plus_abs =1000
minus_abs=1000
result=0

for i in range(100):
    plus_abs=X+i
    minus_abs=X-i

    for j in range(N):
        if plus_abs == int(list2[j]):
           plus_abs=1000


    for k in range(N):
        if minus_abs == int(list2[k]):
            minus_abs=1000

    if plus_abs !=1000 or minus_abs!=1000:
        if plus_abs >= minus_abs:
            result = minus_abs
        else:
            result = plus_abs

        print(result)
        break


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

int main(){
    int n, a ,b, pass = 0, abr = 0;
    cin >> n >> a >> b;
    string s; cin >> s;

    rep(i,n){
        int flag = 0;
        switch (s[i]){
        case 'a':
            if(pass < a + b){
                pass++;
                flag = 1;
            }
            break;
        case 'b':
            if(pass < a + b && abr < b){
                pass++;
                abr++;
                flag = 1;
            }
            break;
        }
        
        cout << (flag ? "Yes" : "No") << endl;
    }
}

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

using namespace std;

int main() {
    int N, M;
    cin >> N >> M;
    
    
    vector<vector<int> > s(M, vector<int>());
    for(int i=0; i<M; i++) {
        int k;
        cin >> k;
        for(int j=0; j<k; j++) {
            int ss;
            cin >> ss;
            s[i].push_back(ss);
        }
    }
    
    int p[M];
    for(int i=0; i<M; i++) {
        cin >> p[i];
    }
    
    long long int ans=0;
    bool flag=true;
    for(int bit=0; bit<(1<<N); bit++) {
        flag=true;
        for(int i=0; i<M; i++) {
            int count=0;
            for(int j=0; j<s[i].size(); j++) {
                if(1 & bit>>(s[i][j]-1)) {
                    count++;
                }
            }
            if(count%2==p[i]) continue;
            else {
                flag=false;
                break;
            }
        }
        if(flag) {
            ans++;
        }
    }
    
    cout << ans << endl;

    return 0;
    
}

Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
vector<int> G[105];
int N;
long long V[105];
long long C[105][105];
long long F[105][105];
int T[105];
bool viz[105];
int S=0,D=104;
int stq,drq;
int Q[105];
bool BFS(int S,int D)
{
    memset(viz,0,sizeof(viz));
    viz[S]=1;
    Q[stq=drq=1]=S;
    while(stq<=drq)
    {
        int nod=Q[stq++];
        if(nod==D)continue;
        for(auto it:G[nod])
        {
            if(!viz[it]&&F[nod][it]<C[nod][it])
            {
                T[it]=nod;
                viz[it]=1;
                Q[++drq]=it;
            }
        }
    }
    return viz[D];
}
long long flux(int S,int D)
{
    long long maxflow=0;
    while(BFS(S,D))
    {
        for(auto it:G[D])
        {
            if(F[it][D]==C[it][D])continue;
            long long fmin=1LL<<60;
            for(int nod=D;nod!=S;nod=T[nod])
            {
                fmin=min(fmin,C[T[nod]][nod]-F[T[nod]][nod]);
            }
            if(!fmin)continue;
            maxflow+=fmin;
            for(int nod=D;nod!=S;nod=T[nod])
            {
                F[T[nod]][nod]+=fmin;
                F[nod][T[nod]]-=fmin;
            }
        }
    }
    return maxflow;
}
long long rez=0;
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>V[i];
        if(V[i]>=0)
        {
            rez+=V[i];
            C[i][D]=V[i];
            G[i].push_back(D);
            G[D].push_back(i);
        }
        else
        {
            C[S][i]=-V[i];
            G[S].push_back(i);
            G[i].push_back(S);
        }
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=i*2;j<=N;j+=i)
        {
            C[i][j]=1LL<<50;
            G[i].push_back(j);
            G[j].push_back(i);
        }
    }
    rez-=flux(S,D);
    cout<<rez;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
string st;
int n,m,i,j,l,r,mid,ans;
bool check(int x)
{
	if (x>=st.length()) return 0; 
	char c='2';
	for (i=1;i<=x;i++)
	{
		if (st.length()-x<=i)
		{
			if (c=='2') c=st[i];
			if (c!=st[i]) return 0;
		}
	}
	return 1;
}
int main()
{
	cin>>st;
	st=" "+st;
	l=0;r=st.length()+1;
	while (l<r)
	{
		mid=(l+r)/2;
		if (check(mid))
		{
			l=mid+1;
			ans=mid;
		}
		else r=mid;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 512
N, M = map(int, raw_input().split())
red = set([1])
num = [1 for i in xrange(N+1)]
for i in xrange(M):
    x, y = map(int, raw_input().split())
    num[x] -= 1
    num[y] += 1
    if x in red:
        red.add(y)
        if num[x] == 0:
            red.remove(x)
print len(red)


Measured memory_bytes: 31132
H,W = list(map(int,input().split()))
a = [list(input()) for i in range(H)]
H_new = H
b = []
for h in range(H):
	judge = True
	for w in range(W):
		#print(h,w)
		if a[h][w] != ".":
			judge = False
	if judge:
		H_new -= 1
	else:
		b.append(a[h])
c = []
W_new = W
for w in range(W):
	judge = True
	for h in range(H_new):
		if b[h][w] != ".":
			judge = False
	if judge:
		W_new -= 1
	else:
		b_new = []
		for h in range(H_new):
			b_new.append(b[h][w])
		c.append(b_new)

for h in range(H_new):
	for w in range(W_new):
		print(c[w][h],end = "")
	print("")


Measured memory_bytes: 4596
#include <stdio.h>

typedef struct {
	int key, id;
} data;

void merge_sort(data x[], int n)
{
	static data y[100001] = {};
	if (n <= 1) return;
	merge_sort(&(x[0]), n/2);
	merge_sort(&(x[n/2]), (n+1)/2);
	
	int i, p, q;
	for (i = 0, p = 0, q = n/2; i < n; i++) {
		if (p >= n/2) y[i] = x[q++];
		else if (q >= n) y[i] = x[p++];
		else y[i] = (x[p].key < x[q].key)? x[p++]: x[q++];
	}
	for (i = 0; i < n; i++) x[i] = y[i];
}

int main()
{
	int i, N;
	data d[100001];
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		scanf("%d", &(d[i].key));
		d[i].id = i + 1;
	}
	merge_sort(d, N);
	
	int j, k, min[100001], count[100001], v[100001];
	for (i = N - 1, k = 0; i >= 0; i--) {
		v[k] = d[i].key;
		for (j = i - 1; j >= 0 && d[j].key == v[k]; j--);
		count[k] = i - j;
		for (min[k] = d[i].id; i > j; i--) if (d[i].id < min[k]) min[k] = d[i].id;
		i++;
		k++;
	}
	min[k] = 1;
	count[k] = 0;
	v[k] = 0;
	
	long long ans[100001] = {};
	for (i = 0; i < k; i++) {
		ans[min[i]] += (long long)(v[i] - v[i+1]) * count[i];
		min[i+1] = (min[i] < min[i+1])? min[i]: min[i+1];
		count[i+1] += count[i];
	}
	
	for (i = 1; i <= N; i++) printf("%lld\n", ans[i]);
	fflush(stdout);
	return 0;
}


Measured memory_bytes: 5232
#include <bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){
    string str;
    int n;
    cin>>n;
    cin>>str;
    int i=0,j=str.length()-1,ans=0;
    while(i<j){
        if(str[i]=='R' && str[j]=='W'){
            i++;
            j--;
        }
        else if(str[i]=='R' && str[j]!='W')
           i++;
        else if(str[i]!='R' && str[j]=='W')
          j--;
        else{
            swap(str[i],str[j]);
            i++;
            j--;
            ans++;
        }
        
    }
    cout<<ans<<endl;
   
}


Measured memory_bytes: 3732
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <utility>
#include <functional>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <fstream>
using namespace std;
inline int toInt(string s) { int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string toStr(T x) { ostringstream sout; sout << x; return sout.str();}
typedef vector<int> vi;
typedef vector<vi>  vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
const double EPS = 1e-12;
const double PI = acos(-1.0);
const int INF = INT_MAX/10;

#include <complex>
typedef complex<double> P;
typedef vector<P> vP;
typedef vector<double> vd;

#define EQ(x,y) (abs((x)-(y))<EPS)

double dot(P a, P b) {
	return (a.real()*b.real() + a.imag()*b.imag());
}

double cross(P a, P b) {
	return (a.real()*b.imag() - a.imag()*b.real());
}

double distance_ls_p(P a, P b, P c) {
	if(dot(b-a, c-a) < -EPS) return abs(c-a);
	if(dot(a-b, c-b) < -EPS) return abs(c-b);
	return abs(cross(b-a, c-a)) / abs(b-a);
}

P rotate(P t, P p, double r) {
	double ta = cos(r)*(t.real()-p.real())-sin(r)*(t.imag()-p.imag())+p.real();
	double tb = sin(r)*(t.real()-p.real())-cos(r)*(t.imag()-p.imag())+p.imag();
	return P(ta, tb);
}

double to_radian(double degree) {
	return degree*PI/180.0;
}

P intersection_l(P a1, P a2, P b1, P b2) {
	P a = a2 - a1;
	P b = b2 - b1;
	return a1 + a * cross(b, b1-a1) / cross(b, a);
}

double area(P a, P b, P c) {
	return abs(cross(c-a, b-a)*0.5);
}

int main() {
	int n;
	cin >> n;
	REP(_, n) {
		double x1, y1, x2, y2, x3, y3;
		cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;

		P A(x1, y1), B(x2, y2), C(x3, y3);
		P mAB((x1+x2)/2, (y1+y2)/2), mBC((x2+x3)/2, (y2+y3)/2);
		P nAB = rotate(B, mAB, to_radian(90));
		P nBC = rotate(C, mBC, to_radian(90));

		P p = intersection_l(mAB, nAB, mBC, nBC);
		double r = abs(A-p);

		printf("%.3f %.3f %.3f\n", p.real(), p.imag(), r);
	}

	return 0;
}

Measured memory_bytes: 1260
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <cmath>
#include <tuple>
#include <cstdio>
#include <bitset>
#include <sstream>
#include <iterator>
#include <numeric>
#include <map>
#include <cstring>

using namespace std;

#define DEBUG_ //!!提出時にコメントアウト!!
#ifdef DEBUG_
	#define dump(x)  cerr << #x << " = " << (x) << endl;
#else
	#define dump(x)  ; //何もしない文
#endif

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(x) ((int)(x).size()) //unsignedのサイズをint型に変換
#define pb push_back

typedef long long LL; 
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

template <typename T>
std::string printVector(const std::vector<T> &data)
{
    std::stringstream ss;
    std::ostream_iterator<T> out_it(ss, ", ");
    ss << "[";
    std::copy(data.begin(), data.end() - 1, out_it);
    ss << data.back() << "]";
    return ss.str();
}

const int MOD = 1e9+7;
const LL LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);	
    LL Q,H,S,D; cin >> Q >> H >> S >> D;
    LL N; cin >> N;
    vector<LL> k(4);

    k[0] = S;
    k[1] = H * 2;
    k[2] = H + Q * 2;
    k[3] = Q * 4;

    LL lmin = *min_element(k.begin(), k.end());
    LL l2min = min(lmin * 2, D);

    LL ans;

    if(N % 2 == 0)
    {
        ans = N / 2 * l2min;
    }
    else
    {
        ans = (N - 1) / 2 * l2min + lmin;
    }
    cout << ans << endl;




}


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

int main(){

      string S;
      bool a=0;
      cin >> S;
      
      if(S[0] == S[1]){
            if(S[0] != S[2] && S[2] == S[3]){
                  a = 1;
            }
      }else if(S[0] == S[2]){
            if(S[0] != S[1] && S[1] == S[3]){
                  a = 1;
            }
      }else if(S[0] == S[3]){
            if(S[0] != S[1] && S[1] == S[2]){
                  a=1;
            }
      }

      if(a == 1){
            cout << "Yes" << endl;
      }else{
            cout << "No" << endl;
      }
}


Measured memory_bytes: 256
#include<stdio.h>
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <math.h>

/*
	入力例：
	3
	1 1 3
*/

int main(){
	long lN;
	scanf("%ld", &lN);
	printf("%ld\n",lN + lN * lN + lN * lN * lN);
 return 0;
}

Measured memory_bytes: 1732
import itertools, bisect
from fractions import Fraction
from math import factorial


def comb(n, r):
    return factorial(n) // (factorial(r) * factorial(n - r))


N, A, B = map(int, input().split())
V = sorted(list(map(int, input().split())), reverse=True)

Ave = [Fraction(a, i) for i, a in enumerate(itertools.accumulate(V), 1)]
max_num = max(Ave[A - 1:B])
max_indices = [i for i, v in enumerate(Ave) if A <= i + 1 <= B and v == max_num]

Vm = [-v for v in V]
C = 0
for ind in max_indices:
    l = bisect.bisect_left(Vm, Vm[ind])
    r = bisect.bisect_right(Vm, Vm[ind])
    C += comb(r - l, ind - l + 1)
print(float(max_num))
print(C)


Measured memory_bytes: 10420
n,k=map(int, input().split())
h=list(map(int, input().split()))+[0]*2*k
dp=[10**10]*(n*10)+[10**10]*2*k
dp[0]=0
dp[1]=abs(h[0]-h[1])
for i in range(n):
    for j in range(1,k+1):
        dp[i+j] = min(dp[i+j], dp[i]+abs(h[i]-h[i+j]))
print(dp[n-1])

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A'; 

int main()
{
    while(true){
        string s; cin >> s;
        if(s == "-") break;
        int m; cin >> m;
        for(int i=0; i<m; i++){
            int h; cin >> h;
            s = s.substr(h) + s.substr(0, h);
            // cout << s << endl;
        }
        cout << s << endl;
    }
}


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

#define int long long
#define ff first
#define ss second
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x.size())
int powmod(int a,int l, int md){a%=md; int res=1;while(l){if(l&1)res=res*a%md;l/=2;a=a*a%md;}return res;}
int binpow(int a,int l){int res=1;while(l){if(l&1)res=res*a;l/=2;a=a*a;}return res;}
int invmod(int a, int md){return powmod(a,md-2,md);}
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
typedef vector<int> vi; typedef pair<int, int> ii; typedef vector< ii > vii;
#define pb push_back
int __set(int b, int i) {return b|(1LL<<i);} //set ith bit
int __unset(int b, int i) {return b&(~(1UL<<i));}
int __check(int b, int i) {return b&(1LL<<i);} //returns 0 if ith bit is 0
int mulmod(int a, int b, int md) {return (((a%md)*(b%md))%md+md)%md;}
int addmod(int a, int b, int md) {return ((a%md+b%md)%md+md)%md;}
int submod(int a, int b, int md) {return (((a%md-b%md)%md)+md)%md;}
int divmod(int a, int b, int md) {return mulmod(a, powmod(b, md-2, md), md);} //if md is prime;
const ll inf = 0xFFFFFFFFFFFFFFFL; //very large number
priority_queue<int, vector<int>, greater<int> > pq; //for min priority_queue
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int solve1(vi& a, int n) {
	int dp[n][3];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 3; j++)
			dp[i][j]=-inf;
	}
	int s=0;
	for(int i =1; i < n; i+=2) {
		s+=a[i];
	}
	dp[0][1]=a[0];
	for(int i = 2; i < n; i++) {
		if(i-3>=0) {
			dp[i][2]=max(dp[i][2],dp[i-3][1]+a[i]);
		}
		dp[i][2]=max(dp[i][2],dp[i-2][2]+a[i]);
		dp[i][1]=max(dp[i][1],dp[i-2][1]+a[i]);
	}
	return max({s,dp[n-2][1],dp[n-1][2]});
}
int solve2(vi& a, int n) {
	int dp[n][5][3];
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < 5; j++) {
			for(int k = 0; k < 3; k++)
				dp[i][j][k]=-inf;
		}
	}
	dp[0][1][0]=a[0];
	for(int i = 2; i < n; i++) {
		dp[i][1][0]=max(dp[i][1][0],dp[i-2][1][0]+a[i]);
		dp[i][2][1]=max(dp[i][2][1],dp[i-2][2][1]+a[i]);
		dp[i][2][2]=max(dp[i][2][2],dp[i-2][2][2]+a[i]);
		dp[i][3][1]=max(dp[i][3][1],dp[i-2][3][1]+a[i]);
		if(i-3>=0) {
			dp[i][2][1]=max(dp[i][2][1],dp[i-3][1][0]+a[i]);
			dp[i][2][2]=max(dp[i][2][2],dp[i-3][2][1]+a[i]);
		}
		if(i-4>=0) {
			dp[i][3][1]=max(dp[i][3][1],dp[i-4][1][0]+a[i]);
		}
	}
	int mx=-inf;
	if(n>=3) mx=dp[n-3][1][0];
	return max({mx,dp[n-1][2][2],dp[n-2][2][1],dp[n-1][3][1]});
}
signed main(void)
{
	IOS;
	int n; cin>>n;
	vi a(n);
	for(int i = 0; i < n; i++)
		cin>>a[i];
	if(n%2==0) {
		cout<<solve1(a,n)<<endl;
	} else {
		vi a1;
		for(int i  =1;i  <n; i++)
			a1.pb(a[i]);
		cout<<max(solve2(a,n),solve1(a1,n-1))<<endl;
	}
	return 0;
}

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

using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef long int li;

int main()
{
    IOS;
    //freopen("fr.txt","r",stdin);
    char ch;
    cin>>ch;
    if(ch>='a'&&ch<='z')
        cout<<'a'<<endl;
    else cout<<'A'<<endl;

    return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
int main(){
  int l;
  cin>>l;
  int x=l;
  int d=0;
  vector<int> b;
  while(x>1){
    b.push_back(x%2);
    d++;
    x/=2;
  }
  vector<vector<int>> e;
  int p=1;
  for(int i=0;i<d;i++){
    e.push_back({i+1,i+2,0});
    e.push_back({i+1,i+2,p});
    p*=2;
  }
  int w=p;
  for(int i=d-1;i>=0;i--){
    p/=2;
    if(b.at(i)){
      e.push_back({i+1,d+1,w});
      w+=p;
    }
  }
  cout<<d+1<<' '<<e.size()<<endl;
  for(int i=0;i<e.size();i++)
    cout<<e.at(i).at(0)<<' '<<e.at(i).at(1)<<' '<<e.at(i).at(2)<<endl;
}

Measured memory_bytes: 3612
from collections import Counter
import bisect


def main():
    N = int(input())
    A = list(map(int, input().split()))
    count_list = list(Counter(A).values())
    count_list.sort()
    cumsum_count = [0] * len(count_list)
    cumsum_count[0] = count_list[0]
    for i in range(1, len(count_list)):
        cumsum_count[i] = cumsum_count[i - 1] + count_list[i]
    ans_list = [0] * N
    n_max = N
    for k in range(1, len(count_list) + 1):
        # 最大でも N // k 回まで。
        # 各カード n_max 枚まで使って k * n_max の長方形領域を全部埋め尽くせるかを調べる。
        # 埋め尽くせる最小の n_max が答え。
        n_max = min(n_max, N // k)
        s = 0
        while True:
            # n_max 枚以上あるカードは n_max 枚固定
            index = bisect.bisect_left(count_list, n_max)
            s = n_max * (len(count_list) - index)
            # それ未満のカードはそのまま全部使う
            if index > 0:
                s += cumsum_count[index - 1]
            if s >= k * n_max or n_max == 0:
                break
            n_max -= 1
        ans_list[k - 1] = n_max
    for ans in ans_list:
        print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 46364
//People only find me interesting because they can't tell whether I'm serious or not
//#include <boost/multiprecision/cpp_int.hpp> 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
#include "ext/pb_ds/tree_policy.hpp"
typedef long long int ll;
typedef double db;
typedef __int128 s128;
typedef __uint128_t u128;
typedef unsigned long long u64;
#define int long long int
#define P 1000000007
#define Q 1000000006
#define sz(a) (ll)a.size()
#define lt(a) (ll)a.length()
#define pll pair<ll,ll>
#define f(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define bac(i,a,b) for(ll i=(ll)a;i>=(ll)b;i--)
#define mll map<ll,ll>
#define umll unordered_map<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define teevra_gati ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define N 3005
#define PI 3.14159265359
#define inf LLONG_MAX
//using namespace boost::multiprecision; 
using namespace __gnu_pbds;
using namespace std;
ll dp[N][N]; 
void solve(){
    string s,t,ans="";
    cin>>s>>t;
    f(i,1,lt(s)+1){
        f(j,1,lt(t)+1){
            if(s[i-1]==t[j-1]) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
        }
    }
    ll i=lt(s),j=lt(t);
    while(i>0 && j>0){
        if(dp[i][j]==1+dp[i-1][j-1] && s[i-1]==t[j-1]){
            ans += s[i-1];
            i--;
            j--;
        }
        else if(dp[i-1][j]>=dp[i][j-1]) i--;
        else j--;
    }
    reverse(all(ans));
    cout<<ans;
}
signed main() {
    teevra_gati
    
    solve();

    return 0;
}

Measured memory_bytes: 70656
use std::io::*;
use std::str::*;
use std::collections::*;

fn main() {
    let N : i32 = read();
    let W : usize = read();
    const M : usize = 100000;
    let mut dp = vec![1 << 50; M + 1];
    dp[0] = 0;
    for i in 0..N {
        let w : usize = read();
        let v : usize = read();
        for j in (0..M+1).rev() {
            let pj = j as i32 - v as i32;
            if pj < 0 { break; }
            let pj = pj as usize;
            dp[j] = std::cmp::min(dp[j], dp[pj] + w);
        }
    }
    for i in (0..M + 1).rev() {
        if dp[i] <= W {
            println!("{}", i);
            break;
        }
    }
}

fn read<T: FromStr>() -> T {
    let cin = stdin();
    let cin = cin.lock();
    let s: String = cin 
        .bytes() // Bytes
        .map(|c| c.expect("failed reading char") as char)
        .skip_while(|c| c.is_whitespace()) // c が whitespace である限り skip
        .take_while(|c| !c.is_whitespace()) // c が whitespace でない限り要素を返す
        .collect();
    s.parse().ok().expect("failed parsing")
}


Measured memory_bytes: 4352