akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
		String n=scan.nextLine();
		if(n.contains("9")) {
			System.out.println("Yes");
		}
		else {
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 35656
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;

  int Ain[N];

  for(int i = 0; i < N; i++){
      cin >> Ain[i];
  }
  
    bool judge = true;



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

      if(Ain[i] % 2 == 0){
          if(Ain[i] % 3 != 0 && Ain[i] % 5 !=0){       
            judge = false;
          }
      }
  }

  if(judge){
      cout << "APPROVED" << endl;
  }else
  {
      cout << "DENIED" << endl;
  }
  
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
	int n,m,direct,st,s,in;
	int t,sum[11111],x,y,map[111][111];
	while(~scanf("%d %d",&n,&m))
	{
		direct=0;
		st=1;x=y=1;s=0;
		in=0;
		scanf("%d",&t);
		memset(map,0,sizeof(map));
		for(int i=1;i<=t;i++)
		{
			scanf("%d",&sum[i]);
			s+=sum[i]; 
		}
		while(1)
		{
			while(!sum[st])st++;
			sum[st]--;
			map[x][y]=st;
			in++;
			if(in>=s)break;
			if(direct==0)
			{
				if(y+1>m||map[x][y+1])
				{
					direct=1;
					x++;
				}
				else
				{
					y++;
				}
			}
			else if(direct==1)
			{
				if(x+1>n||map[x+1][y])
				{
					direct=2;
					y--;
				}
				else
				{
					x++;
				}
			}
			else if(direct==2)
			{
				if(y-1<1||map[x][y-1])
				{
					direct=3;
					x--;
				}
				else
				{
					y--;
				}
			}
			else
			{
				if(x-1<1||map[x-1][y])
				{
					direct=0;
					y++;
				}
				else
				{
					x--;
				}
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				if(j>1)printf(" ");
				printf("%d",map[i][j]);
			}
			puts("");
		}
	}
	
} 

Measured memory_bytes: 384
#include<iostream>
#include<vector>
typedef long long ll;

using namespace std;

int main()
{
    int N;  cin >> N;
    ll ans=0;
    vector<int> v(N+1,0);
    for(ll i=1; i<=N; i++){
        for(ll j=1; j<=N/i; j++)   v[i*j]++;
    }
    for(ll i=1; i<=N; i++) ans += i*v[i];
    cout << ans;
}

Measured memory_bytes: 42316
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
#define max 100005
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;


int main(){
    ll x;
    cin>>x;
    for(int a=-119;a<=120;a++){
        for(int b=-119;b<=120;b++){
            if(a>b){
                ll result=pow(a,5)-pow(b,5);
                if(x==result){
                    cout<<a<<" "<<b<<endl;
                    return 0;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 3972
while True:
  N,Q = map(int, raw_input().split())
  if N==Q==0: break
  schedule = [0] * 101
  for _ in xrange(N):
    ipt = map(int, raw_input().split())
    for i in xrange(1, ipt[0]+1):
      schedule[ipt[i]] += 1
  bestday = 0
  bestnum = 0
  for i in xrange(1, 101):
    if bestnum < schedule[i]:
      bestday = i
      bestnum = schedule[i]
  if bestnum < Q:
    bestday = 0
  print bestday

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

int main() {
  int a, b,c;
  int k;
  
 
  cin >> a >> b >> c;
  cin >> k;
  int count =0;
  
  for(int i=0; b<=a; i++){
    b *= 2;
    count++;
  }
  int cou =0;
  for(int i=0; c<=b; i++){
    c *= 2;
    cou++;
  }
  
  if((cou + count)>k){
    cout << "No" << endl;
  } else  if(a<b && b<c){
    cout << "Yes" <<endl;
  }
    
    
}


Measured memory_bytes: 3560
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>
#include <cmath>
#include <utility> // pair make_pair
#include <algorithm>
#include <functional>
#include <iomanip>
#include <climits> // LLONG_MAX, LLONG_MIN, INT_MIN, INT_MAX
#include <assert.h>

#define m0(x) memset(x,0,sizeof(x))
#define m1(x) memset(x,63,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))
#define ll long long
//#define int ll
#define INF INT_MAX/10
#define MOD 1000000007

using namespace std;
using Pi = pair<int, int>;
using Graph = vector<vector<int> >;
using WeightGraph = vector<vector<Pi> >;

int Input[100100];

int main() {
  string A[4] = { "Christmas Eve", "Christmas", "Christmas Eve Eve Eve", "Christmas Eve Eve"};
  int x; cin >> x;
  cout << A[x%4] << endl;
}


Measured memory_bytes: 256
//#include<atcoder/all>
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<string>
#include<utility>
#include<vector>

using namespace std;
//using namespace atcoder;

#define ll long long
#define pal pair<ll,ll>
#define pad pair<double,double>
#define PB push_back
#define MP make_pair
#define F first
#define S second

const ll MOD = 1e9+7;
const ll INF = 1e18;
const double EPS = 1e-8;

template<typename T,typename U>
bool chmax(T& max, const U& x){
	if(max<x){
		max = x;
		return true;
	}
	return false;
}

template<typename T,typename U>
bool chmin(T& min, const U& x){
	if(min>x){
		min = x;
		return true;
	}
	return false;
}

vector<ll> deta(100001,0);

int main(){
	ll n,x,m;
    bool f=false;
	cin >> n >> x >> m;
	vector<ll> loop(m,0);
	ll ls,le,lsize;
	ll tmp=x;
	for(ll i=1;i<=n;i++){
		if(i>1)tmp= (tmp*tmp);
		tmp %=m;
		if(deta[tmp]!=0){
			ls=deta[tmp];
			le=i-1;
			lsize=le-ls+1;
			break;
		}else{
			deta[tmp]=i;
			loop[i]=loop[i-1]+tmp;
		}
		if(i==n) f=true;
	}
	if(f){
		cout << loop[n] << endl;
	}else{
		ll sho = (n-ls+1)/lsize;
		ll amari=(n-ls+1)%lsize;
		cout << loop[ls-1]+(loop[le]-loop[ls-1])*sho+loop[amari+ls-1]-loop[ls-1] << endl;
	}
}

Measured memory_bytes: 4768
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define US unordered_set
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
typedef vector<vector<ll>> Graph;

int main(){
  int N,T; cin>>N>>T;
  vi A(N); REP(i,N) cin>>A[i];
  vi B(N);
  B[N-1]=A[N-1];
  for(ll i=N-2;i>=0;i--) B[i]=max(A[i],B[i+1]);
  vi C(N);
  REP(i,N) C[i]=B[i]-A[i];
  ll ma=C[0]; for(ll i:C) ma=max(ma,i);
  ll cnt=0;
  for(ll i:C) if(i==ma) cnt++;
  cout<<cnt<<endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n; i >= 0; i--)
#define reprr(i, m, n) for (ll i = m; i < n; i++)
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
using Graph = vector<vector<pair<ll, ll>>>;


int main()
{
    ll N; cin >> N;
    Graph G(N);
    rep(i, N-1) {
        ll a, b, c; cin >> a >> b >> c;
        a--, b--;
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    ll Q, K; cin >> Q >> K; K--;
    vll X(Q), Y(Q);
    rep(i, Q) {
        cin >> X[i] >> Y[i]; X[i]--, Y[i]--;
    }

    queue<ll> que;
    que.push(K);
    vll dist(N, -1);
    dist[K] = 0;

    while (que.size()) {
        ll node = que.front(); que.pop();

        for (auto e : G[node]) {
            if (dist[e.first] > 0 || e.first == node) continue;
            dist[e.first] = dist[node] + e.second;
            que.push(e.first);
        }
    }

    rep(i, Q) {
        cout << dist[X[i]] + dist[Y[i]] << endl;
    }

    return 0;
}

Measured memory_bytes: 11648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "
#define N 100010
int main(){
    int n,m;cin>>n>>m;
    int h[N],ma[N]={0};
    rep1(i,n)cin>>h[i];
    rep(i,m){
        int a,b;cin>>a>>b;
        ma[a] = max(ma[a], h[b]);
        ma[b] = max(ma[b], h[a]);
    }
    int ans=0;
    rep1(i,n){
        if(h[i]>ma[i])ans++;
    }
    co(ans);
}


Measured memory_bytes: 4404
import sys
input = sys.stdin.readline
n,y=map(int,input().split())
y//=1000
for i in range(n+1):
    for j in range(n-i+1):
        if 9*i+4*j==y-n:
            print(i,j,n-i-j)
            exit()
print(-1,-1,-1)


Measured memory_bytes: 40556
import sys
import collections
from collections import Counter
from collections import deque
from collections import defaultdict
import itertools
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from itertools import takewhile
from itertools import compress
import functools
from functools import reduce
import math
####from math import gcd
####from math import inf
from math import ceil
from math import floor
##from math import log10
##from math import log2
##from math import log
from math import factorial
import re
from functools import lru_cache

# @lru_cache(maxsize=1000)

# MOD = 10 ** 9 + 7

# N = int(input())
# A = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]

# N, K = [int(x) for x in input().split()]
# A = [int(x) for x in input().split()]


S = input()

a = S[0] + S[1]
b = S[2] + S[3]

a = int(a)
b = int(b)

isYYMM = False
isMMYY = False

if 1 <= b and b <= 12:
    isYYMM = True

if 1 <= a and a <= 12:
    isMMYY = True

# if a >= 13 and (b == 0 or b >= 13):
#     isYYMM = False
#     isMMYY = False



ans = ""
if isYYMM == True and isMMYY == True:
    ans = "AMBIGUOUS"
elif isYYMM == True:
    ans = "YYMM"
elif isMMYY == True:
    ans = "MMYY"
else:
    ans = "NA"

print(ans)


Measured memory_bytes: 38384
#define lp(i,n) for(int i=0;i<n;i++)
#define pau system("pause")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    int x,y,z,tmp;
    cin>>x>>y>>z;
    printf("%d %d %d",z,x,y);
}


Measured memory_bytes: 256
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N, K, C = map(int, input().split())
    S = input()[:-1]

    Q = []
    for i in range(N):
        if S[i] == "o":
            Q.append(i+1)

    forward = []
    day = 0
    cnt = 0
    for q in Q:
        if day < q:
            forward.append(q)
            day = q + C
            cnt += 1
        if cnt == K:
            break
    
    back = []
    day = INF
    cnt = 0
    for q in reversed(Q):
        if q + C < day:
            back.append(q)
            day = q
            cnt += 1
        if cnt == K:
            break
    back.reverse()
    
    for i in range(len(forward)):
        if forward[i] == back[i]:
            print(forward[i])
        


if __name__ == '__main__':
    main()

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, a[100000], ma, ans;

int main() {
	cin >> n;
	inc(i, n) { cin >> a[i]; }
	
	inc(i, n) {
		if(i == 0) { ma = 1; ans += a[i] - 1; }
		else {
			if(a[i] > ma) {
				if(a[i] == ma + 1) { ma++; }
				else {
					ans += (a[i] - 1) / (ma + 1);
				}
			}
		}
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int n,m;
map<int,int> cnt;
main() {
    int i,x;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&x), cnt[x]++;
    scanf("%d",&m);
    for(i=1;i<=m;i++) {
        scanf("%d",&x);
        if(cnt[x]==0) {
            printf("NO");
            return 0;
        }
        cnt[x]--;
    }
    printf("YES");
}


Measured memory_bytes: 9600
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt();
        }

        long[][][] dp = new long[3][N+5][2];
        dp[0][0][0] = 1000;
        dp[0][0][1] = 0;
        dp[1][0][0] = 1000;
        dp[1][0][1] = 0;
        dp[2][0][0] = 1000;
        dp[2][0][1] = 0;
        for (int j = 1; j <= N; j++) {
            int price = A[j-1];
            for (int i = 0; i < 3; i++) {
                long maxValue = 0;
                for (int k = 0; k < 3; k++) {
                    long money  = dp[k][j-1][0];
                    long stock = dp[k][j-1][1];
                    if (i == 0) {
                        long buyNum = money/price;
                        money -= buyNum*price;
                        stock += buyNum;
                    } else if (i == 1) {
                        money += stock*price;
                        stock = 0;
                    } else {
                        // nop
                    }
                    long value = money + stock*price;
                    if (value >= maxValue) {
                        maxValue = value;
                        dp[i][j][0] = money;
                        dp[i][j][1] = stock;
                    }
                }
            }
        }

        long ans = 0;
        for (int i = 0; i < 3; i++) {
            ans = Math.max(ans, dp[i][N][0]);
        }

        System.out.println(ans);
    }
}


Measured memory_bytes: 35920
#include<iostream>

using namespace std;

int main()
{
	long long int a;
	long long int b;
	long long int check = 1;
	long long int k=1;
	cin >> a;

	for (int i = 1; i <= a/2+1; i++)
	{
		//cout << i;
		b = i*i;
		if (b > a)
		{
			check = i - 1;
			k = check*check;
			break;

		}
	}

	cout << k;
	return 0;
}


Measured memory_bytes: 256
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

S = list(input().rstrip())
N = len(S)
FIN_L = N*2-1

def calc(lst, idx):
    if idx == N:
        return sum(list(map(int, ''.join(lst).split('+'))))
    else:
        return calc(lst+['',S[idx]], idx+1) + calc(lst+['+',S[idx]], idx+1)

def main():
    """ main """
    print(calc(S[:1],1))

if __name__ == '__main__':
    main()

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

int main() {
  int N;  cin >> N;
  vector<double> vec(N);
 
  for (int i = 0; i < N; i++) 
    cin >> vec.at(i);
  
  double x = 0.0;
  for (int i = 0; i < N; i++)
    x += 1.0 / vec.at(i);
  
  cout << 1.0 / x  << endl;
}


Measured memory_bytes: 256
import sys

n, k = map(int, input().split())
ara = [0]
ara += list(map(int, input().split()))

now = 1
vis = []
taken = [0]*(n+1)

while taken[now] == 0:
    vis.append(now)
    taken[now] = 1
    now = ara[now]

cycleLen = len(vis) - vis.index(now)

if k < vis.index(now):
    print(vis[k])
    sys.exit()

k -= vis.index(now)
k %= cycleLen

print(vis[k + vis.index(now)])

Measured memory_bytes: 32268
import math

s = input()
q = int(input())
reverse_flag = 0
head = ""
tail = ""

for i in range(q):
  query = input().split(" ")
  if(len(query) == 1):
    reverse_flag += 1
  else:
    if((reverse_flag + int(query[1])) % 2 == 0):
      tail += query[2]
    else:
      head = query[2] + head

ans_str = head + s + tail

if(reverse_flag % 2 == 1): print(ans_str[::-1])
else: print(ans_str)


Measured memory_bytes: 4596
H, N = list(map(int,input().split()))
A = []
B = []
for i in range(N):
    in1, in2 = list(map(int,input().split()))
    A.append(in1)
    B.append(in2)
    
# dp[i]: モンスターの体力がiのときの最適値
INF = 10 ** 9 + 7
dp = [INF for _ in range(H + 1)]
dp[0] = 0

for i in range(1, H + 1):
    for j in range(N):
        dp[i] = min(dp[i], dp[max(0, i - A[j])] + B[j])
        
print(dp[H])

Measured memory_bytes: 42988
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ll long long

ll Max, Min, gap;
int N, M;
vector<pair<pair<int, int>, int> > q;
vector<pair<int, int> > g[100101];
int parent[100101], dp[20][100101], p[100101], h[100101];
ll depth[100101];
vector<bool> visited(100101);

int Find(int n)
{
	if (n == parent[n]) return n;
	return parent[n] = Find(parent[n]);
}

void Union(int l, int r, int d)
{
	int pl = l, pr = r;
	l = Find(l); r = Find(r);
	if (l == r)
	{
		q.push_back({ {pl, pr}, d });
		return;
	}

	parent[l] = r;
	g[pl].push_back({ pr, d });
	g[pr].push_back({ pl, -d });
}

void DFS(int n, int prev)
{
	Max = max(Max, depth[n]);
	Min = min(Min, depth[n]);
	visited[n] = true;

	for (int i = 0; i < g[n].size(); i++)
	{
		int next = g[n][i].first, cost = g[n][i].second;
		if (next == prev) continue;

		p[next] = n;
		depth[next] = depth[n] + cost;
		h[next] = h[n] + 1;
		DFS(next, n);
	}
}

int LCA(int a, int b) //LCA를 잘못 구했다.
{
	if (h[a] != h[b])
	{
		if (h[a] < h[b]) swap(a, b);
		int diff = h[a] - h[b];
		for (int i = 0; diff; i++)
		{
			if (diff % 2) a = dp[i][a];
			diff /= 2;
		}
	}

	if (a == b) return a;

	for (int i = 19; i >= 0; i--)
		if (dp[i][a] != dp[i][b])
		{
			a = dp[i][a];
			b = dp[i][b];
		}
	return p[a];
}

int main()
{
	for (int i = 0; i < 100101; i++)
		parent[i] = i;

	scanf("%d %d", &N, &M);
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		Union(a, b, c);
	}

	//컴포넌트가 하나가 아닐 수도 있다.
	//항상 같은 컴포넌트의 정점끼리만 쿼리가 들어온다.
	for (int i = 1; i <= N; i++)
	{
		if (!visited[i])
		{
			Max = 0;
			Min = 0;

			depth[i] = 0;
			h[i] = 0;
			DFS(i, 0);

			gap = max(gap, Max - Min);
		}
	}

	//잊은 것 : [0, 10^9] 범위니까 트리의 최장 경로 검사가 필요
	//이 문제에서는 트리의 특수성 때문에 간단하게 검사할 수 있다.
	//컴포넌트가 여러 개면 컴포넌트끼리 따로 처리해 줘야 한다.
	if (gap > 1'000'000'000LL)
		return !printf("No");

	for (int i = 1; i <= N; i++)
		dp[0][i] = p[i];

	for (int i = 1; i < 20; i++)
		for (int j = 1; j <= N; j++)
			dp[i][j] = dp[i - 1][dp[i - 1][j]];

	for (int i = 0; i < q.size(); i++)
	{
		int l = q[i].first.first, r = q[i].first.second, d = q[i].second;
		int lca = LCA(l, r);
		if (abs(depth[l] - depth[r]) != (ll)d)
			return !printf("No");
	}

	printf("Yes");
	return 0;
}

Measured memory_bytes: 21504
#include <bits/stdc++.h>
#define GET_REP(_1, _2, _3, NAME, ...) NAME
#define rep(...) GET_REP(__VA_ARGS__, irep, _rep)(__VA_ARGS__)
#define rep1(...) GET_REP(__VA_ARGS__, irep1, _rep1)(__VA_ARGS__)
#define _rep(i, n) irep (i, 0, n)
#define _rep1(i, n) irep1(i, 1, n)
#define irep(i, a, n) for (int i = a; i < (int)(n); ++i)
#define irep1(i, a, n) for (int i = a; i <= (int)(n); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep1(i, n) for (int i = (int)(n); i >= 1; --i)
#define allrep(X, x) for (auto &&X : x)
#define all(x) begin(x), end(x)
#define debug(x) cout << #x " => " << (x) << endl
#ifdef LOCAL
  #include "../../Lib/cout_container.hpp"
#endif
using lint = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr double EPS = 1e-9;
using namespace std;
namespace { struct INIT { INIT() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(15); } } INIT; }

int main(void) {
  lint n, a, b;
  cin >> n >> a >> b;
  if ((a & 1) == (b & 1)) {
    cout << (b - a) / 2 << endl;
  } else {
    lint mini = min(a - 1, n - b);
    cout << (b - a) / 2 + mini + 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <tuple>
#include <vector>

using ll = int64_t;
using namespace std;

ll fastExp(ll base, ll exp, ll modulo) {
  ll result = 1;
  ll be = base;
  while (exp > 0) {
    if (exp & 1) {
      result = (result * be) % modulo;
    }
    be = (be * be) % modulo;
    exp >>= 1;
  }
  return result;
}

tuple<vector<ll>, vector<ll>> makeFactorials(ll n, ll modulo) {
  vector<ll> a(n + 1, 0);
  vector<ll> a_inv(n + 1, 0);
  ll k = a[0] = a_inv[0] = 1;
  for (ll i = 1; i <= n; i++) {
    k = (k * i) % modulo;
    a[i] = k;
    a_inv[i] = fastExp(k, modulo - 2, modulo);
  }
  return {a, a_inv};
}

ll solve(ll k, const string& s, int debug = 0) {
  ll modulo = 1000'000'000 + 7;  // Prime < 2^32
  ll l = 26;                     // Alphabets
  ll m = s.size();               // > 0
  ll n = k + m;
  auto [f, f_inv] = makeFactorials(n, modulo);
  auto ADD = [&](ll x, ll y) { return (x + y) % modulo; };
  auto MUL = [&](ll x, ll y) { return (x * y) % modulo; };
  auto EXP = [&](ll x, ll y) { return fastExp(x, y, modulo); };
#define COMB(N, K) MUL(f[(N)], MUL(f_inv[(K)], f_inv[(N) - (K)]))

  if (debug) {
    for (int i = 0; i <= n; i++) {
      printf("%d: %ld %ld %ld\n", i, f[i], f_inv[i], MUL(f[i], f_inv[i]));
    }
  }

  ll result = 0;
  for (int i = m; i <= n; i++) {
    ll c = COMB(i - 1, m - 1);
    ll d = EXP(l - 1, i - m);
    ll e = EXP(l, n - i);
    ll cde = MUL(c, MUL(d, e));
    result = ADD(result, cde);
  }
  return result;
}

void _main(istream& istr, ostream& ostr) {
  ll k;
  istr >> k;
  string s;
  istr >> s;
  ostr << solve(k, s) << endl;
}

int main() {
  _main(cin, cout);
  return 0;
}


Measured memory_bytes: 66348
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <iomanip>
using namespace std;
#define INF 1e9
#define PI acos(-1)
typedef long long ll;
typedef pair<int, int> p_ii;

int main() {
	int h, w;
	ll ans = 0;
	cin >> h >> w;

	vector<int> cost(10, INF);//1からの最小コスト
	cost[1] = 0;

	vector<vector<int>> c(10, vector<int>(10,INF));
	vector<vector<int>> a(h, vector<int>(w,-1));

	for (int i = 0; i < 10; i++)for (int j = 0; j < 10; j++)cin >> c[i][j];
	for (int i = 0; i < h; i++)for (int j = 0; j < w; j++)cin >> a[i][j];

	priority_queue<p_ii, vector<p_ii>, greater<p_ii>> que;
	que.push(p_ii(0, 1));

	while (!que.empty()) {
		p_ii p = que.top(); que.pop();
		int v = p.second;
		if (cost[v] < p.first)continue;

		for (int i = 0; i < c[v].size(); i++) {
			if (i == v)continue;
			if (cost[i] > cost[v] + c[i][v]) {
				cost[i] = cost[v] + c[i][v];
				que.push(p_ii(cost[i], i));
			}
		}
	}

	for (int i = 0; i < h; i++)for (int j = 0; j < w; j++) {
		if (a[i][j] == -1)continue;
		ans += cost[a[i][j]];
	}

	cout << ans << endl;


	return 0;
}

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

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

    int ans = 0;
    for (int i = 1; i < S.size(); i++) {
        if (S[i] == S[i - 1]) {
            ans++;
            if (S[i] == '0') {
                S[i] = '1';
            } else {
                S[i] = '0';
            }
        }
    }

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

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

using namespace std;
typedef long long ll;

int N, M;
int P[100000], Y[100000];
vector<int> yd[100001];
int main()
{
    //  scanf("%d%d", &N, &M);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
        scanf("%d%d ", &P[i], &Y[i]), yd[P[i]].push_back(Y[i]);
    for (int i = 0; i < N; i++)
        sort(yd[i + 1].begin(), yd[i + 1].end());
    for (int i = 0; i < M; i++)
        printf("%012lld\n", ll(P[i]) * 1000000 + int(lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin()) + 1);
}

Measured memory_bytes: 7808
/*
 * a.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

/* typedef */

/* global variables */

/* subroutines */

/* main */

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

  printf("%d %d %.5lf\n", a / b, a % b, (double)a / b);
  return 0;
}

Measured memory_bytes: 1192
#include <functional>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    vector<int> a(N + 1), b(N + 1);
    for (int i = 1; i <= N; ++i) a[i] = b[i] = N;

    ll black = ll(N - 2) * (N - 2);

    int H = N, W = N;

    while (Q--) {
        int t, x;
        cin >> t >> x;
        if (t == 1) {
            if (x < W) {
                for (int i = x; i < W; ++i) {
                    b[i] = H;
                }
                W = x;
            }
            black -= b[x] - 2;

        } else {
            if (x < H) {
                for (int i = x; i < H; ++i) {
                    a[i] = W;
                }
                H = x;
            }
            black -= a[x] - 2;
        }
    }
    cout << black << endl;
    
    return 0;
}

Measured memory_bytes: 4824
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <algorithm>
using namespace std;

double calc (double w,double s){
    return s * 100 / (w + s);
}

int main(void){
    long long A,B,C,D,E,F;
    cin >> A >> B >> C >> D >> E >> F;
    vector<long long> water;
    vector<long long> suger;
    long long a = A;
    long long b = B;
    long long c = C;
    double rate = (double)E / 100;
    long long d = D;
    long long f = F / 100;
    A = A * 100;
    B = B * 100;
    double con = -1.0;
    for(long long i = 0;i <= f;i += a){
        for(long long j = 0;j <= f;j += b){
            if(i + j <= f && i + j != 0){
                water.push_back(i * 100 + j * 100);
            }
        }
    }
    for(long long i = 0;i < F;i += c){
        for(long long j = 0;j < F;j += d){
            if(i + j <= F){
                suger.push_back(i + j);
            }
        }
    }
    long long ans_g,ans_s;
    ans_g = 0;
    ans_s = 0;
    for(long long i = 0;i < water.size();i++){
        for(long long j = 0;j < suger.size();j++){
            if(con <= calc((double)water[i],(double)suger[j]) && water[i] + suger[j] <= F && (double)suger[j] <= rate * (double)water[i]){
                con = calc((double)water[i],(double)suger[j]);
                ans_g = water[i] + suger[j];
                ans_s = suger[j];
            }
        }
    }
    cout << ans_g << " " << ans_s << endl;
    return 0;
}


Measured memory_bytes: 2420
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<cstdlib>
using namespace std;
typedef long long ll;
int main()
{
    int h1,h2,m1,m2,k;
    cin>>h1>>m1>>h2>>m2>>k;
    int h=h2-h1;
    int m=m2-m1;
    int t=h*60+m;
    cout<<t-k<<endl;
    return 0;
}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define call(var) cout<<#var<<"="<<var<<endl;
using ll=long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using Graph = vector<vi>;
using P = pair<int,int>;
const int MOD=(int)1e9+7;
const int INF=(int)1e9;
const ll LINF=(ll)1e18;
template<class t,class u> void chmax(t&a,u b){if(a<b)a=b;}
template<class t,class u> void chmin(t&a,u b){if(b<a)a=b;}

int main(){
    int n;
    cin >> n;
    map<int,int> mp;
    rep(i,n){
        int a;cin >> a;
        mp[a]++;
    }
    ll ans = 0;
    for(auto t : mp){
        if(t.first<t.second) ans += t.second - t.first;
        else if(t.first>t.second) ans += t.second;
    }
    cout << ans << endl;
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
typedef long long LL;
typedef pair<int, int> PII;

int n;
vector<PII> g[100000];
int sz[100000];

void calcSizes(int v, int par) {
    sz[v] = 1;
    for (PII to : g[v]) if (to.first != par) {
        calcSizes(to.first, v);
        sz[v] += sz[to.first];
    }
}

LL sum;
int cnt;

void dfs(int v, LL dist, int par) {
    sum += dist;
    ++cnt;
    for (PII to : g[v]) if (to.first != par) {
        dfs(to.first, dist + to.second, v);
    }
}

LL solve(int st) {
    int mxcnt = -1;
    int mxind = -1;
    sum = 0;
    for (PII to : g[st]) {
        cnt = 0;
        dfs(to.first, to.second, st);
        if (cnt > mxcnt) {
            mxcnt = cnt;
            mxind = to.first;
        }
    }
    sum *= 2;
    if (mxcnt > n - 1 - mxcnt) {
        assert(mxcnt == n - mxcnt);
        for (PII to : g[st]) if (to.first == mxind) {
            sum -= to.second;
        }
    } else {
        int mn = int(1e9);
        for (PII to : g[st]) {
            mn = min(mn, to.second);
        }
        sum -= mn;
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    forn(i, n - 1) {
        int from, to, w;
        scanf("%d%d%d", &from, &to, &w), --from, --to;
        g[from].pb(mp(to, w));
        g[to].pb(mp(from, w));
    }
    int v = -1;
    forn(i, n) if ((int)g[i].size() == 1) {
        v = i;
        break;
    }
    assert(v != -1);
    int par = -1;
    int v2 = -1;
    calcSizes(v, -1);
    while (true) {
        bool done = true;
        for (PII to : g[v]) if (to.first != par && sz[to.first] * 2 >= n) {
            if (sz[to.first] * 2 == n) {
                v2 = to.first;
            } else {
                par = v;
                v = to.first;
                done = false;
                break;
            }
        }
        if (done) {
            break;
        }
    }
    LL ans = solve(v);
    if (v2 != -1) {
        ans = max(ans, solve(v2));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 12416
#define __USE_MINGW_ANSI_STDIO
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long ll;
typedef long long ull;
typedef pair<int, int> ii;

#define all(v)		((v).begin()), ((v).end())
#define sz(v)		((int)((v).size()))
#define endl		"\n"
#define fx(n)		fixed<<setprecision(n)
#define mk			make_pair	

void file()
{
#ifndef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("input.txt", "r", stdin);
#endif
#ifdef ONLINE_JUDGE
	freopen("output.txt", "w", stdout);
	freopen("pyramid.in", "r", stdin);
#endif
}
const double pi = 2 * acos(0.0);
const ll oo = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int nn = 5e3 + 15;
int dx[8] = { -1, 0, 0, 1, 1, -1, 1, -1 };
int dy[8] = { 0, -1, 1, 0, 1, -1, -1, 1 };


int main()
{
	//file();
	ios::sync_with_stdio(NULL);
	cout.tie(NULL);
	cin.tie(NULL);
	set<int> st;
	for (int i = 0; i < 3; i++)
	{
		int x;
		cin >> x;
		st.insert(x);
	}
	cout << sz(st) << endl;
	return 0;
}

Measured memory_bytes: 256
#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 main() {
    int H, W, K;
    cin >> H >> W >> K;
    vector<string> c(H);
    for (int i = 0; i < H; i++)
    {
        cin >> c[i];
    }

    int ans = 0;
    for (int bitx = 0; bitx < (1 << H); bitx++)
    {
        for (int bity = 0; bity < (1 << W); bity++)
        {
            int temp = 0;
            for (int x = 0; x < H; x++)
            {
                if (bitx & (1<<x)) continue;
                for (int y = 0; y < W; y++)
                {

                    if (bity & (1<<y)) continue;
                    if (c[x][y] == '#')
                    {
                        temp++;
                    }
                    
                }
                
            }
            if (temp == K)
            {
                ans++;
            }
            
        }
        
    }
    cout << ans << endl;
    
  return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;

#define int long long

#define left __left__

const int N=70+10;

const int A=520;

const int MOD=1000000007;

int n,k;

char s[N];

int C[A][A];

void prework()
{
	int i,j;
	for(i=0;i<A;++i)
	{
		C[i][0]=1;
		for(j=1;j<=i;++j)
			if((C[i][j]=C[i-1][j-1]+C[i-1][j])>=MOD)
				C[i][j]-=MOD;
	}
}

int ans;

int B[N],ed,left;

bool valid()
{
	if(!ed)
		return false;
	int i,j=1,jj=1,c=0;
	for(i=1;i<=k&&(j<=ed||B[jj]>1||c);++i)
	{
		if(j<=ed&&s[i]=='r')
			++j;
		else if(jj<j&&B[jj]>1&&s[i]=='b')
			c+=B[jj++]-2;
		else if(c)
			--c;
	}
	return !(j<=ed||B[jj]>1||c);
}

void update()
{
	int i,j,res(1),em(0);
	for(i=1;i<=ed;i=j+1)
	{
		for(j=i;B[j+1]==B[i];++j);
		res=res*C[j][i-1]%MOD;
		em+=(j-i+1)*((B[i]<<1)-1);
	}
	em+=ed+1;
	res=res*C[em-1+left][em-1]%MOD;
	if((ans+=res)>=MOD)
		ans-=MOD;
}

void dfs(int lim)
{
	if(left<0)
		return;
	if(valid())
		update();
	if(ed)
		--left;
	++ed;--left;
	dfs(B[ed]=1);
	++left;
	for(int i=2;i<=lim;++i)
	{
		left-=(i<<1)-3;
		dfs(B[ed]=i);
		left+=(i<<1)-3;
	}
	B[ed--]=0;
	if(ed)
		++left;
}

signed main()
{
	scanf("%lld%lld%s",&n,&k,s+1);
	prework();
	left=n;dfs(233);
	printf("%lld",(ans+1)%MOD);
	return 0;
}


Measured memory_bytes: 2304
import java.util.Scanner;

public class Main {

	
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			char[] s = (cin.next()+"     ").toCharArray();
			int cnt1=0,cnt2=0;
			for(int i = 0;i<s.length-4;i++){
				if(s[i]=='I'&&s[i+1]=='O'&&s[i+2]=='I'){
					cnt2++;
				}
				if(s[i]=='J'&&s[i+1]=='O'&&s[i+2]=='I'){
					cnt1++;
				}
			}
			System.out.println(cnt1);
			System.out.println(cnt2);
		}

	}

}

Measured memory_bytes: 12000
#include<iostream>
using namespace std;
int a[100];
int bubbleSort(int a[],int n)
{
	int sum=0;
   bool flag=1;
	for(int i=0;flag;i++)
	{
		flag=0;
		for(int j=n-1;j>=i-1;j--)
		{
			if(a[j]<a[j-1])
			{
				flag=1;
				swap(a[j],a[j-1]);
				sum++;
			}
		}
	}
	return sum;
}

int main()
{
	int n,sw;
	cin>>n;
	for(int i=0;i<n;i++)
	cin>>a[i];
	sw=bubbleSort(a,n);
	for(int i=0;i<n;i++)
	{
		if(i) cout<<" ";
		cout<<a[i];
	}
	cout<<endl;
	cout<<sw<<endl;
	return 0;
}


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

using namespace std;
using ll = long long int;

int main()
{
    ll A, B, C, K;
    cin >> A >> B >> C >> K;

    ll ans = 0;

    if(K % 2 == 0)
    {
        ans = A - B;
    }
    else
    {
        ans = B - A;
    }

  
    cout << (abs(ans) > 1e18 ? "Unfair" : to_string(ans)) << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
#define ull unsigned long long int
#define ll long long int
#define MAX 1000000007
//1e9+7
#define pll pair<ll,ll>
#define pii pair<int,int>
#define IO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FO ifstream fin("a.in");ofstream fout("a.out");
#define TEST ll t;cin>>t;while(t--)
#define all(x) (x).begin(),(x).end()
#define mset0(x) memset((x), 0, sizeof((x)));
#define mset1(x) memset((x), -1, sizeof((x)));

bool prime[10000];
void era(){
    memset(prime,true,sizeof prime);
    for(ll p=2;p*p<=10000;p++){
        if(prime[p]){
            for(ll q=p*p;q<=10000;q+=p){
                prime[q]=false;
            }
        }
    }

    return;
}
bool is_prime(ll x){
    if(x==1) return(false);
    if(x==2 || x==3) return(true);
    if(x%2==0) return(false);
    if(x%3==0) return(false);
    for(ll p=5;p*p<=x;p++){
        if(x%p==0) return(false);
    }
    return(true);
}
ll fac[200001],finv[200001];
ll power(ll a,ll b){
    a%=MAX;
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%MAX;
        b/=2;
        a=(a*a)%MAX;
    }
    return(ans%MAX);
}
ll inverse(ll a){
    return((power(a,MAX-2))%MAX);
}
ll ncr(ll n, ll r){
    ll p1=finv[n-r];
    ll p2=finv[r];

    return((((fac[n]*p1)%MAX)*p2)%MAX);


}
bool solve(ll n,ll arr[]){
    ll sum=0;
    for(ll i=0;i<n;i++){
        sum+=arr[i];
        if(sum<=0) return(false);
    }
    sum=0;
    for(ll i=n-1;i>=0;i--){
        sum+=arr[i];
        if(sum<=0) return(false);
    }
    return(true);
}
struct Node{
    ll l,r,w;
}arr[5001];

string cmp(string a,string b){
    if(a.size()>b.size()) return(a);
    if(b.size()>a.size()) return(b);
    int n=a.size();
    for(int i=0;i<n;i++){
        if(a[i]==b[i]) continue;
        if((a[i]-'0')>(b[i]-'0')) return(a);
        else return(b);
    }
    return(a);
}

int main(){
    IO
    ll n,k;
    cin>>n>>k;
    ll w[k+1];
    memset(w,0,sizeof w);
    for(ll gcd=k;gcd>=1;gcd--){
        ll a=k/gcd;
        ll a_b=power(a,n);
       // cout<<a_b<<endl;
        w[gcd]=a_b;
        for(ll mul=2*gcd;mul<=k;mul+=gcd){
            w[gcd]-=w[mul];
            if(w[gcd]<0) w[mul]+=MAX;


        }
    }
    ll sum=0;
   // for(ll i=1;i<=k;i++) cout<<w[i]<<" ";
   // cout<<endl;
    for(ll i=1;i<=k;i++){
        sum+=(i*w[i])%MAX;
        sum%=MAX;
    }
    cout<<sum%MAX;
    return(0);
}


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

#define NDEBUG
#include <cassert>

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))

#define INTSPACE 12
char _buf[INTSPACE*1000000 + 3];

int loadint() {
    if (fgets(_buf, INTSPACE+3, stdin)==NULL) return 0;
    return atoi(_buf);
}

int loadvec(vector<int>& v, int N=-1) {
    if (N == -1) {
        N = loadint();
        if (N==0) return 0;
    }
    int bufsize = INTSPACE*N + 3;
    if (fgets(_buf, bufsize, stdin)==NULL) return 0;
    v.resize(N);

    int i=0;
    bool last = false;
    for (char *p=&_buf[0]; ;) {
        char *q = p;
        while (*q > ' ') ++q;
        if (*q == 0x0D || *q == 0x0A) last = true;
        *q = 0;
        v[i++] = atoi(p);
        if (last || i == N) break;
        p = q+1;
    }
    return i;
}


#define MAX_SUM 4000000

ll solve(int N, vi& a) {
    sort(ALL(a));
    int max_sum = accumulate(ALL(a), 0);
    int half = max_sum / 2, odd = max_sum % 2;

    vector<bitset<MAX_SUM+1>> dp(2);
    dp[0].set(0, true);
    rep(i,N){
        int i0 = i%2, i1 = 1-i0;
        dp[i1] = dp[i0] << a[i];
        dp[i1] |= dp[i0];
    }
    if (odd) half++;
    for (int i=half; i<=MAX_SUM; ++i) {
        if (dp[N%2].test(i)) return i;
    }
    return -1;
}

int main() {
    vi a;
    int N = loadvec(a);
    cout << solve(N,a) << endl;
    return 0;
}


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

int main() {
  int n,k;
  cin >> n >> k;
  vector<int> vec(n);
  for(int i=0;i<n;i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(),vec.end());
  long long int ans = 0;
  for(int i=0;i<n-k;i++){
    ans += vec.at(i);
  }
  cout << ans << endl;
}

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

int main() {
    int N,A;
    int x[50];
    cin >> N >> A;
    for(int i=0; i<N; ++i) {
        int tmp; cin >> tmp;
        x[i] = tmp - A;
    }
    long long dp[50][4901] = {0};
    dp[0][2450] = 1;
    dp[0][x[0] + 2450] += 1;
    for(int i=1; i<N; ++i) {
        for(int j=0; j<=4900; ++j) {
            dp[i][j] = dp[i-1][j];
            if(j-x[i] >= 0 && j-x[i] <= 4900) dp[i][j] += dp[i-1][j - x[i]];
        }
    }
    cout << dp[N-1][2450] - 1 << endl;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<int>>;
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25
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; }

int main() {
    int n;
    cin >> n;
    vector<vector<ll>> a(n, vector<ll>(3));
    rep(i, n){
        rep(j, 3){
            cin >> a[i][j];
        }
    }
    vector<vector<ll>> dp(n+1, vector<ll>(3, 0));
    rep(i, n){
        rep(j, 3){
            rep(k, 3){
                if(j == k) continue;
                chmax(dp[i+1][k], dp[i][j] + a[i][k]);
            }
        }
    }
    cout << *max_element(dp[n].begin(), dp[n].end()) << endl;
}




Measured memory_bytes: 11136
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
        return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

ll gcd(ll a, ll b) {
        if (b == 0) {
                return a;
        } else {
                return gcd(b, a % b);
        }
}

template<typename Iter>
ll lcm_v(Iter first, Iter end) {
        if (first == end) {
                return 1;
        } else {
                ll rest = lcm_v(next(first), end), g = gcd(*first, rest);
                return g * (*first / g) * (rest / g);
        }
}

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

        vector<ll> a(n);
        REP(i, n) {
                cin >> a[i];
                a[i] >>= 1;
        }

        ll l = lcm_v(a.cbegin(), a.cend());

        REP(i, n) {
                if (l / a[i] % 2 == 0) {
                        cout << 0 << endl;
                        return 0;
                }
        }

        cout << (m / l + 1) / 2 << endl;

        return 0;
}


Measured memory_bytes: 2560
def main():
    x = int(input())

    if 400 <= x <= 599:
        print(8)
    elif 600 <= x <= 799:
        print(7)
    elif 800 <= x <= 999:
        print(6)
    elif 1000 <= x <= 1199:
        print(5)
    elif 1200 <= x <= 1399:
        print(4)
    elif 1400 <= x <= 1599:
        print(3)
    elif 1600 <= x <= 1799:
        print(2)
    elif 1800 <= x <= 1999:
        print(1)

if __name__ == '__main__':
    main()


Measured memory_bytes: 9180
#include<stdio.h>
#include<string.h>
int main(){
    long int n, a=0, b=0, c=0, d=0;
    char s[100000][4];
    scanf("%ld", &n);
    for(int i=0; i<n; i++){
        scanf("%s", s[i]);
    }
    for(int i=0; i<n; i++){
        if(strcmp(s[i],"AC") == 0) a++;
        if(strcmp(s[i],"WA") == 0) b++;
        if(strcmp(s[i],"TLE") == 0) c++;
        if(strcmp(s[i],"RE") == 0) d++;
    }
    printf("AC x %ld\n", a);
    printf("WA x %ld\n", b);
    printf("TLE x %ld\n", c);
    printf("RE x %ld\n", d);
    return 0;
}


Measured memory_bytes: 2120
#include<bits/stdc++.h>
#include<iostream>
#include<stdio.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
//using namespace __gnu_pbds;
using namespace std;

#define ordered_set tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll  long long
#define mod 998244353
#define ve vector
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define mxe(v) *max_element(v.begin(),v.end())
#define mne(v) *min_element(v.begin(),v.end())
#define all(v) v.begin(),v.end()
#define FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int inf=1e9+5;


ll power(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1LL)
			res=(res*a)%c;
		a=(a*a)%c;
		b/=2;
	}
	return res;
}





void solve()
{   
   int n;
int ac=0,wa=0,tle=0,re=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
     string s;
        cin>>s;
        if(s=="AC")ac++;
        else if(s=="WA")wa++;
            else if(s=="RE")re++;
            else tle++;
    }
    cout<<"AC x "<<ac<<endl;
     cout<<"WA x "<<wa<<endl;
     cout<<"TLE x "<<tle<<endl;
     cout<<"RE x "<<re<<endl;
}

signed main()
{
//#ifndef ONLINE_JUDGE
    //  freopen("input.txt","r",stdin);
    //  freopen("output.txt","w",stdout);
//#endif
    FAST;

     int t=1;
    // cin>>t;
     while(t--)
    	solve();
    return 0;
}



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

using namespace std;

#define NMAX 100005
 
int N;
int path[NMAX];
int L[NMAX];


int compute(){
	L[0] = path[0];
	int length = 1;
	for (int i = 1; i < N; ++i)
	{
		if (path[i] > L[length-1])
		{
			L[length] = path[i];
			length++;
		} else {
			*lower_bound(L, L + length, path[i]) = path[i];
		}
	}
	return length;
}


int main(){
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> path[i];
	}
	cout << compute() << endl;
}

Measured memory_bytes: 1940
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>

using namespace std;
#define int long long int
const int INF = 1001001001001001LL;

int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

signed main(){
    
    while(1){

    int n; cin >> n;
    if(!n) break;
    vector<int> p(n);
    vector<int> t(n);
    t[0] = 0;
    int sum = 0;
    for(int i = 0; i < n; i++){
        cin >> p[i];
        sum += p[i];
    }
    for(int i = 1; i < n; i++) cin >> t[i];
    

    sort(t.begin(), t.end());
    for(int i = 1; i < n; i++) t[i] += t[i - 1];

    int ans = 0;
    for(int k = 0; k <= n - 1; k++){
        
        // k := 使うジョイントの本数
        int val = n - k;
        int len = t[n - 1] - t[n - 1 - k] + sum;
        ans = max(ans, val * len);
    }

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



Measured memory_bytes: 3944