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

class Main{
    static int num = 0, n, sum = 0;
    static LinkedList<Integer> index;
    static int[] box;
    public static void main(String[] args){
	BufferedReader sc=new BufferedReader(new InputStreamReader(System.in));
	try {
	    n = Integer.valueOf(sc.readLine());
	    String inp = new StringBuffer(sc.readLine()).reverse().toString();
	    int m = Integer.valueOf(sc.readLine());
	    String[] st = sc.readLine().split(" ");
	    box = new int[m];
	    for(int i=0; i<m; i++)
		box[i] = Integer.valueOf(st[i]);
	    int start = -1;
	    index = new LinkedList<Integer>();
	    for(int i=0; i<n; i++)
		if(inp.charAt(i)=='*')
		    index.add(i);
		else
		    if(i%2==0)
			sum+=(int)(inp.charAt(i)-'0');
		    else{
			int t = 2*(int)(inp.charAt(i)-'0');
			sum+=t/10+t%10;
		    }
	    solve();
	    System.out.println(num);
	}catch(Exception e){
	    System.out.println("Error");
	}
    }
    static void solve(){
	if(index.size()==0){
	    if(sum%10==0)
		num++;
	    return;
	}
	
	for(int u: box){
	    int zz, t = index.poll();
	    if(t%2==0)
		zz = u;
	    else
		zz = (2*u)/10+(2*u)%10;
	    sum+=zz;
	    solve();
	    sum-=zz;
	    index.offerFirst(t);
	}
    }
}

Measured memory_bytes: 151308
#include<stdio.h>

int main(){
	int n,ab=0,a=0,b=0,o=0;
	char kata[3]={'O','O','O'};
	while(0<=scanf("%d,%s",&n,kata)){
		if(kata[0]=='A' && kata[1]=='B'){
			++ab;
		}else if(kata[0]=='A'){
			++a;
		}else if(kata[0]=='B'){
			++b;
		}else{
			++o;
		}
		kata[2]='O';
	}
	
	printf("%d\n%d\n%d\n%d\n",a,b,ab,o);
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define stop exit(0)
#define pb push_back
#define skip continue
#define ll long long
long long a,b,c,d=0,e=0,i,f=0,g=0,j,k=0,l=0,r,z,m,p,df[101];
string t,x,q,s;
//double ;
vector<ll>v,u,w,dv[101];
//vector<string>;
map<string,ll>n;
set<ll>y;
void dfs(ll x){
    df[x]=1;
    for(ll i=0;i<dv[x].size();i++){
        if(df[dv[x][i]]==0){
            df[dv[x][i]]=1;
            dfs(dv[x][i]);
        }
    }
}
int main(){
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    cin>>a>>b>>c>>d;
    cout<<max(max(a*c,a*d),max(b*c,b*d));
}

Measured memory_bytes: 3640
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N (200)

struct edge{
	int to;
	int dis;
};

int n, m;
vector<edge>e[N];



int main(void){
	int k;
	int x, y;
	long long z;
	long long s, ans;
	int a[30];
	f(i, 30)a[i] = 0;
	scanf("%d", &n);
	k = 0;
	f(i, 30){
		if (n % 2 == 1){
			a[i] = 1;
			k = i + 1;
		}
		else a[i] = 0;
		n = n / 2;
	}
	k--;
	a[k] = 0;
	x = 1;
	f(i, k){
		e[i].push_back({ i + 1, 0 });
		e[i].push_back({ i + 1, x });
		x = x * 2;
		if (a[k-i-1] == 1){
			e[0].push_back({ i + 1, x});
			x++;
		}
	}
	x = 0;
	f(i, 20){
		x += e[i].size();
	}
	printf("%d %d\n", k + 1, x);
	f(i, 20){
		f(j, e[i].size()){
			printf("%d %d %d\n", i + 1, (e[i][j].to) + 1, e[i][j].dis);
		}
	}




	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int x[3];
  int s=300;
  scanf("%d %d %d",&x[0],&x[1],&x[2]);
  for(int i=0;i<3;i++){
    for(int j=i+1;j<3;j++){
      if (s>x[i]+x[j]){
        s=x[i]+x[j];
      }
  	}
  }
  printf("%d",s);
}


Measured memory_bytes: 128
from functools import reduce
import operator
product = lambda it: reduce(operator.mul,it,1)

N = input()
K = int(input())

comb = lambda n, k: product(range(n-k+1,n+1))//product(range(1,k+1))

def rec(i, k):
    if k == 0:
        return 1
    if len(N) < k + i:
        return 0
    return (max(0,int(N[i])-1)*(9**(k-1))*comb(len(N)-i-1, k-1) +
            (rec(i+1,k) if N[i] == '0' else rec(i+1,k-1) + (9**k)*comb(len(N)-i-1, k)))

print(rec(0,K))

Measured memory_bytes: 3700
#include <stdio.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int main(void){
	int N;
	cin >> N;
	int a[N];
	long long ans[N-1];
	long long x=0;
	long long y=0;
	for(int i=0; i<N; i++){
		cin >> a[i];
		y += a[i];
	}
	for(int i=0; i<N-1; i++){
		x += a[i];
		y -= a[i];
		ans[i] = abs(x-y);
	}
	sort(ans, ans+N-1);
	cout << ans[0] << endl;
	return 0;
}

Measured memory_bytes: 2560
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(final String[] args) {
        final Scanner scanner = new Scanner(System.in);
        final int n = scanner.nextInt();
        final int t = scanner.nextInt();

        int min = Integer.MAX_VALUE;
        int maxDiff = -1;
        final List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            final int a = scanner.nextInt();
            min = Math.min(min, a);
            maxDiff = Math.max(maxDiff, a - min);
            list.add(a);
        }

        final Set<Integer> set = new HashSet<>(list);
        int counter = 0;
        for (final int value : list) {
            set.remove(value);
            if (set.contains(value + maxDiff)) {
                counter++;
            }
        }
        System.out.println(counter);
    }
}


Measured memory_bytes: 62632
local read = setmetatable({}, {__index = function(t, k) local a = {} for i=1,#k do table.insert(a, '*'..string.sub(k, i, i)) end local r = io.read local u = table.unpack or unpack return function() return r(u(a)) end end})
read.N = function(N) local t={} for i=1,N do t[i]=read.n() end return t end
string.totable = function(s) local t={} local u=string.sub for i=1,#s do t[i] = u(s, i, i) end return t end
string.split = function(s) local t={} for w in string.gmatch(s, "[^%s]+") do table.insert(t, w) end return (table.unpack or unpack)(t) end
local function array(dimensi0n, default_val) assert(type(default_val) ~= 'table') local n=dimensi0n local m={}if default_val~=nil then m[1]={__index=function()return default_val end}end for i=2,n do m[i]={__index=function(p, k)local c=setmetatable({},m[i-1])rawset(p,k,c)return c end}end return setmetatable({},m[n])end
local function tostringxx(o, depth) depth = depth or 0 if depth > 10 then return "<too deep!>" end if o == _G then return "<_G>" end local indent0 = (" "):rep((depth) * 2) local indent1 = (" "):rep((depth+1) * 2) local indent2= (" "):rep((depth+2) * 2) if type(o) == 'table' then local keys = {} local types = {} for k in pairs(o) do types[type(k)] = true table.insert(keys, k) end local types_count = 0 local lasttype for k in pairs(types) do types_count = types_count + 1 lasttype = k end if types_count == 1 and (lasttype == 'string' or lasttype == 'number') then table.sort(keys) end local inside = {} for i=1,#keys do local k = keys[i] local v = o[k] if type(k) == 'string' then k = string.format('%q', k) end table.insert(inside, indent1 .. '['..tostring(k)..'] = ' .. tostringxx(v, depth + 1)) end return '{\n' .. table.concat(inside, ',\n') .. '\n' .. indent0 .. '}' else if type(o) == 'string' then o = string.format('%q', o) end return tostring(o) end end
local function richtraceback() local x = 2 while true do local info = debug.getinfo(x) if not info then break end local fname = '<' .. info.short_src .. ":" .. info.linedefined .. ">" if info.name then fname = info.name end print(info.short_src .. ":" .. info.currentline .. ": in " .. ("%q"):format(fname)) print(" LOCALS:") local p = 1 while true do local name, val = debug.getlocal(x,p) if not name then break end print(" " .. name .. ": " .. tostringxx(val, 3)) p = p + 1 end print(" UPVALUES:") for p=1,info.nups do local name, val = debug.getupvalue(info.func,p) if not name then break end print(" " .. name .. ": " .. tostringxx(val, 3)) end x = x + 1 end end
local function myassert(b) if not b then richtraceback() error("assertion failed") end end 
--
local N = read.n()
local A = {}
for i=1,N do
    A[i] = read.n()
end
table.sort(A, function(a,b)return a>b end)
local comfortableness = 0
local j
for i=1,N do
    local c = 0
    if i == 1 then
        j = 1
    elseif i == 2 then
        c = A[j]
        j = j + 1
    elseif i % 2 == 1 then
        c = A[j]
    else
        c = A[j]
        j = j + 1
    end
    comfortableness = comfortableness + c
end
print(comfortableness)

Measured memory_bytes: 21864
#include <bits/stdc++.h>
using namespace std;
const int MAX_H = 200;
const int MAX_W = 10;
const int MOD = 1e9+7;
template<int mod> struct ModInt {
    int x;
    ModInt() : x(0) {}
    ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
    ModInt &operator+=(const ModInt &p) { if((x += p.x) >= mod) x -= mod; return *this; }
    ModInt &operator-=(const ModInt &p) { if((x += mod-p.x) >= mod) x -= mod; return *this; }
    ModInt &operator*=(const ModInt &p) { x = (int)(1LL*x*p.x%mod); return *this; }
    ModInt &operator/=(const ModInt &p) { *this *= p.inverse(); return *this; }
    ModInt operator-() const { return ModInt(-x); }
    ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
    ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
    ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
    ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
    bool operator==(const ModInt &p) const { return x == p.x; }
    bool operator!=(const ModInt &p) const { return x != p.x; }
    ModInt inverse() const{
        int a = x, b = mod, u = 1, v = 0, t;
        while(b > 0) { t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
        return ModInt(u);
    }
    ModInt pow(int e){
        long long a = 1, p = x;
        while(e > 0) {
            if(e%2 == 0) {p = (p*p) % mod; e /= 2;}
            else {a = (a*p) % mod; e--;}
        }
        return ModInt(a);
    }
    friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
        return os << p.x;
    }
    friend istream &operator>>(istream &is, ModInt<mod> &a) {
        long long x;
        is >> x;
        a = ModInt<mod>(x);
        return (is);
    }
};

int main() {
    int h, w, k;
    cin >> h >> w >> k;
    ModInt<MOD> dp[MAX_H][MAX_W]; dp[0][0] = 1;
    for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) {
        for (int s = 0; s < (1<<w-1); s++) {
            bool ok = true;
            for (int k = 0; k < w-2; k++) {
                if ((s&(1<<k)) && (s&(1<<(k+1)))) ok = false;
            }
            if (ok == true) {
                if (j > 0 && (s&(1<<(j-1)))) dp[i+1][j-1] += dp[i][j];
                else if (j < w-1 && (s&(1<<j))) dp[i+1][j+1] += dp[i][j];
                else dp[i+1][j] += dp[i][j];
            }
        }
    }
    
    cout << dp[h][k-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <cstring>
#include <functional>
#include <iostream>
#include <iomanip>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <regex>
#include <vector>

#define fix(n)          cout<<fixed<<setprecision(n)
#define rep(i,n)        for (int i = 0; i < (n); ++i)
#define all(a)          (a).begin(), (a).end()
#define sort(a)         sort(all(a))
#define uniq(a)         sort(a);(a).erase(unique(all(a), (a).end())
#define reverse(a)      reverse(all(a))
#define ctos(c)         string(1, (c))
#define out(d)          cout << (d)
#define outl(d)         std::cout<<(d)<<"\n"
#define YES()           cout << "YES" << endl
#define NO()            cout << "NO" << endl
#define Yes()           cout << "Yes" << endl
#define No()            cout << "No" << endl
#define ceil(x, y)      ((x + y - 1) / (y))
#define debug(x)        cerr << #x << ": " << (x) << '\n'
#define debug2(x, y)    cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v)          for (size_t _ = 0; _ < v.size(); ++_){ cerr << #v << "[" << _ << "] : " << v[_] << '\n'; }
#define pb              push_back
#define fst             first
#define int             long long

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll,ll>;

const ll MOD = 1000000007; // 10^9 + 7
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};

void solve() {
  ll n, k; cin >> n >> k;
  vector<ll> x(n); rep(i, n) cin >> x[i];

  ll ans = __LONG_LONG_MAX__;
  for (int li = 0; li <= n - k; li++) {
    ll ri = li + k - 1;
    ans = min({
      ans,
      abs(x[li]) + abs(x[ri] - x[li]),
      abs(x[ri]) + abs(x[li] - x[ri]),
    });
  }
  outl(ans);
}

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  srand((unsigned)time(NULL));
  fix(12);

  solve();
}


Measured memory_bytes: 1024
from itertools import *

n, m, x = map(int, input().split())
c = []
a = []
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])

res = 10**9
for s in product([0, 1], repeat = n):
    u = [0 for i in range(m)]
    cost = 0
    for i, b in enumerate(s):
        if b == 0: continue
        cost += c[i]
        for j in range(m):
            u[j] += a[i][j]
    if min(u) >= x:
        res = min(res, cost)
      
if res == 10**9: res = -1
print(res)

Measured memory_bytes: 69036
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=[-int(input()) for i in range(N)]
    dp=[INF]*(N+2)
    dp[0]=-INF
    for i in range(N):
        dp[bisect_right(dp,A[i])]=A[i]
    for i in range(N+2):
        if dp[i]==INF:
            print(i-1)
            exit()

if __name__ == '__main__':
    main()


Measured memory_bytes: 45788
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
#define _GLIBCXX_DEBUG
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define pii pair<long long,long long>
#define ppii pair<long long,pair<long long,long long>>
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mod 1000000007
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef vector<vector<long long>> vii;
typedef long long lint;
typedef long long ll;
lint qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
lint qp(int a, ll b, int mo) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
lint gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
long long INF = 1e14;
const int MAX_N = 1 << 17;
const int cf = 100010;
///////////////////////////////////////////////////////////////////////////////

int main(void) {
	int x,a;cin>>x>>a;
  	(x < a) ? cout << 0 << endl : cout << 10 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <climits>
using namespace std;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    long long N, M;
    cin >> N >> M;
    long long ans = 0;
    if(2*N > M){
        cout << M / 2 << endl;
        return 0;
    }

    ans += N;
    M -= 2*N;
    ans += M / 4;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
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 ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}
ll XY[200000], tmp[200000];
void pakuri_sort(int N, ll A[]) {
	const int b = 8;
	rep(k, 4) {
		int kazu[1 << b] = {}, kazu2[1 << b] = {};
		rep(i, N) kazu[A[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu[i + 1] += kazu[i];
		for (int i = N - 1; i >= 0; i--) tmp[--kazu[A[i] >> k * b & ((1 << b) - 1)]] = A[i];
		k++;
		rep(i, N) kazu2[tmp[i] >> k * b & ((1 << b) - 1)]++;
		rep(i, (1 << b) - 1) kazu2[i + 1] += kazu2[i];
		for (int i = N - 1; i >= 0; i--) A[--kazu2[tmp[i] >> k * b & ((1 << b) - 1)]] = tmp[i];
	}
}
int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	int N = getint();
	int saidai = 0;
	int saishou2 = 1e9;
	rep(i, N) {
		int x = getint();
		int y = getint();
		if (x > y) swap(x, y);
		chmax(saidai, y);
		chmin(saishou2, y);
		XY[i] = ((ll)y << 32) + x;
	}
	pakuri_sort(N, XY);
	int m = (1 << 31) - 1;
	int saishou = XY[0] & m;
	int saidai2 = XY[N - 1] & m;
	ll kotae = 1ll * (saidai - saishou2) * (saidai2 - saishou);


	int saishou3 = 1e9;
	ll haba = saidai - saishou;
	rep(i, N) {
		int x = XY[i] & m;
		int y = XY[i] >> 32;
		if (saishou3 < x) break;
		chmin(kotae, haba * (saidai2 - x));
		chmin(saishou3, y);
		chmax(saidai2, y);
	}
	chmin(kotae, haba* (saidai2 - saishou3));
	printf("%lld", kotae);

	Would you please return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<55)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)

//dp[i][j],i1回飛ばしたか? 2回飛ばしたか?
lli dp[3][200200];
bool vis[3][200200];

lli n;
vector<lli> a;

lli func(lli left,lli now){
    if(DEBUG)cout<<"left="<<left<<"now="<<now<<endl;
    if(now>=n){
        if(left>0)return -INF;
        else return 0;
    }
    if(vis[left][now])return dp[left][now];
    vis[left][now]=true;
    lli rtn = -INF;
    rtn = max(rtn,a[now]+func(left,now+2));
    if(left>0)rtn = max(rtn,func(left-1,now+1));

    return dp[left][now] = rtn;
}

int main(){
    // cout << fixed << setprecision(5);
    cin>>n;
    a.resize(n);
    REP(i,0,n)cin>>a[i];

    REP(i,0,3)REP(j,0,200200)dp[i][j]= (-INF);

    if(n==2){
        cout<<max(a[0],a[1])<<endl;
        return 0;
    }
    if(n==3){
        cout<<max({a[0],a[1],a[2]})<<endl;
        return 0;
    }

    lli left;
    if(n%2==0)left=1;
    else left=2;

    cout<<func(left,0)<<endl;
    return 0;
}


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

ll GCD(ll x, ll y) {
    return x ? GCD(y%x, x) : y;
}

int main() {
    ll N;
    cin >> N;
    vector<ll> a(N);
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        ans += a[i];
        ans --;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#17:27
n = int(input())
k = int((2*n)**.5)
if k*(k+1)//2 != n:
  print('No')
  exit()
ans = [[x for x in range(k)]]
now = k
for j in range(k):
  tmp = []
  for i in range(j+1):
    tmp.append(ans[i][j])
  for i in range(j+1,k):
    tmp.append(now)
    now += 1
  ans.append(tmp)
print('Yes')
print(k+1)
for x in ans:
  print(k,' '.join(list(map(lambda y:str(y+1),x))))

Measured memory_bytes: 44508
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define memreset(a) memset(a,0,sizeof(a))
#define testcase(t) int t;cin>>t;while(t--)
#define forstl(i,v) for(auto &i: v)
#define forn(i,e) for(int i = 0; i < e; i++)
#define forsn(i,s,e) for(int i = s; i < e; i++)
#define rforn(i,s) for(int i = s; i >= 0; i--)
#define rforsn(i,s,e) for(int i = s; i >= e; i--)
#define leadzero(a) __builtin_clz(a) // count leading zeroes
#define trailzero(a) __builtin_ctz(a) // count trailing zeroes
#define bitcount(a) __builtin_popcount(a) // count set bits (add ll)
#define ln endl
#define dbg(x) cerr<<#x<<" = "<<x<<endl
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" & "<<#y<<" = "<<y<<endl;
#define dbgstl32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it<<ln;} cerr<<endl
#define dbgstlp32(v) cerr<<#v<<" = \n"; { int c=0; forstl(it,v) \
cerr<<"    Term "<< ++c <<" = "<<it.fi<<" , "<<it.se<<ln;} cerr<<endl
#define dbgarr(v,s,e) cerr<<#v<<" = "; forsn(i,s,e) cerr<<v[i]<<", "; cerr<<endl
#define inp freopen("input.txt", "r", stdin)
#define outp freopen("output.txt", "w", stdout)
#define dbgm(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); \
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
typedef long long int  ll;
typedef long double  ld;
typedef pair<ll,ll> p64;
typedef pair<int,int> p32;
typedef vector<ll> v64;
typedef vector<int> v32; 
typedef vector<v32> vv32;
typedef vector<v64> vv64;
typedef vector<p32> vp32;
typedef vector<vp32> vvp32;
typedef map<int,int> m32;
const int LIM = 2e5+5, MOD = 1e9+7, EPS = 1e-9;
int t,n,m,k,x,y;
int main(){
	fastio;
	string a,b;
	cin>>a>>b;
	n = a.length();
	m = b.length();
	int lcs[n][m];
	forn(i,n){
		forn(j,m){
			lcs[i][j] = 0;
		}
	}
	forn(i,n){
		forn(j,m){
			if(a[i]==b[j]){
				if(i>0 && j>0) lcs[i][j] = 1+lcs[i-1][j-1];
				else lcs[i][j] = 1;
			}
			else if(i==0 && j==0) lcs[i][j] = 0;
			else if(i==0) lcs[i][j] = lcs[i][j-1];
			else if(j==0) lcs[i][j] = lcs[i-1][j];
			else lcs[i][j] = max(lcs[i-1][j],lcs[i][j-1]);
		}
	}
	vector<char> v;
	int i = n-1,j = m-1;
//	cout<<lcs[i][j]<<ln;
	while(i>=0 && j>=0){
		if(a[i]==b[j]){
			v.pb(a[i]);
			i--;
			j--;
		}
		else{
			if(i==0){
				j--;
			}
			else if(j==0){
				i--;
			}
			else if(lcs[i-1][j]>lcs[i][j-1]){
				i--;
			}
			else{
				j--;
			}
		}
	}
	reverse(v.begin(),v.end());
	forstl(r,v) cout<<r;
	cout<<ln;
	return 0;
}

Measured memory_bytes: 35456
#include "bits/stdc++.h"
using namespace std;

long long N, M;
int di[3] = { 1, 2, 3 }, dj[3] = { 1, -1, 0 };
vector<long long> INV;

void init() {
	INV.resize(N + 1);
	INV[1] = 1;
	for (int i = 2; i <= N; i++) {
		INV[i] = M - (INV[M % i] * (M / i)) % M;
	}
}

int main() {
	cin >> N >> M;
	N *= 3;
	init();
	vector<vector<long long> > DP(N + 1, vector<long long>(N * 2 + 1, 0));
	DP[0][N] = 1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j <= N * 2; j++) {
			for (int k = 0; k < 3; k++) {
				int ni = i + di[k], nj = j + dj[k];
				if (0 <= ni && ni <= N && 0 <= nj && nj <= N * 2) {
					DP[ni][nj] += (DP[i][j] * INV[ni]) % M;
					DP[ni][nj] %= M;
				}
			}
		}
	}
	long long ANS = 0;
	for (int i = N; i <= N * 2; i++) {
		ANS += DP[N][i];
		ANS %= M;
	}
	for (int i = 1; i <= N; i++) {
		ANS *= i;
		ANS %= M;
	}
	cout << ANS << endl;
}

Measured memory_bytes: 565248
n,k = map(int,input().split())
h = [int(input()) for i in range(n)]
h.sort()
d = h[n-1]-h[0]
for i in range(n-k+1):
    if h[i+k-1] - h[i] < d:
        d = h[i+k-1] - h[i]
print(d)


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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define INTMAX 1000000000
using namespace std;
typedef long long ll;

int n,m;
int a[3000], b[3000];
bool graph[3000][3000];
vector <bool> visited(100,false);

int dfs(int src){
  visited[src] = true;
  rep(i,1,n+1){
    if(graph[src][i]&&!visited[i])dfs(i);//深さ優先探索で到達判定
  }
}

int main(){
  cin >> n >> m;
  rep(i,0,m){
    cin >> a[i] >> b[i];
    graph[a[i]][b[i]]=true;
    graph[b[i]][a[i]]=true;
  }
  int ans =0;
  rep(i,0,m){
    graph[a[i]][b[i]] = false;
    graph[b[i]][a[i]] = false;
    dfs(1);

    bool bridge=false;
    rep(i,1,n+1) if(visited[i]==false) bridge=true;
    if(bridge)ans+=1;

    graph[a[i]][b[i]] = true;
    graph[b[i]][a[i]] = true;
    rep(i,1,n+1) visited[i]=false;

  }
  cout << ans << endl;

}


Measured memory_bytes: 384
//author-abhijit dey
 //Welcome to my code. btw I hate coding 😉
#include <bits/stdc++.h>
using namespace std;
#define     ff first
#define     ss second
#define     pb push_back
#define     mp make_pair
#define     INF 1000000005
#define     MOD 1000000000
#define     ninf -1000000000
#define     all(c) c.begin(), c.end()
#define     tinput long long int t;cin>>t;
#define     mem(a,x) memset(a,x,sizeof a)
#define     for0(i,n) for(long long int i=0;i<n;i++)
#define     pi 3.141592653589793238462643383279502884
#define     fori(i,a,n) for(long long int i=a;i<n;i++)
#define     forxy(i,x,y) for(int i=x;i<=y;i++)
#define     rfor(i,n) for(long long int i=n-1;i>=0;i--)
#define     ainput for(int i=0; i<n; i++) cin>>a[i];
#define     fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

typedef     long long int ll;
typedef     vector<long long int>vll;
typedef     vector<vector<int> >vvll;
typedef     pair<long long int,long long int>pr;
typedef     vector<pair<long long int,long long int> >vp;

inline long long  min2(long long  a, long long  b)  {return (a)<(b)?(a):(b);}
inline long long  max2(long long  a, long long  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  min3(long long  a, long long  b, long long  c)    {return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std::chrono;
ll N;
vll dp(100000+1,-1);
ll mincost(ll a[],ll ind)
{
    if(ind==N)return 0;

    if(dp[ind]!=-1)return dp[ind];

    ll left=abs(a[ind]-a[ind+1])+mincost(a,ind+1);

    ll right=INT_MAX;
    if(ind+2<=N)
    right=abs(a[ind]-a[ind+2])+mincost(a,ind+2);

    dp[ind]=min(left,right);

    return dp[ind];
}
void process()
{
    cin>>N;
    ll a[N+1];for(ll i=1;i<=N;i++)cin>>a[i];
    cout<<mincost(a,1);
}
int main()
{
    fastio;
    //tinput;
    //while(t--)
        process();
}

Measured memory_bytes: 8064
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i=0;i<=m;i++)
     for(int j=0;j<=m;j++)
      for(int k=0;k<=m,i+j+k<=m;k++)
       {
            if(i+j+k==m && i*1000+j*5000+k*10000==n)
            {
                printf("%d %d %d",k,j,i);
                return 0;   
            }
       }
    printf("-1 -1 -1");
    return 0;
}

Measured memory_bytes: 384
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i < (int)(n); i++)
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

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

int main()
{
	long long A, B;

	cin >> A >> B;	
	cout << A * B / gcd(A, B);

	return 0;
}

Measured memory_bytes: 256
x =int(input())
total =0
count =0
for i in range(x):
    if 500*i ==x:
        count =i*1000
        break
    elif 500*i > x:
        total =abs(500*(i-1) -x)
        count =(i-1) *1000
        # print(count)
        break
if total ==0:
    print(count)
else:
    for i in range(x):
        if 5*i ==total:
            count +=i*5
            break
        elif 5*i >total:
            count +=(i-1)*5
            break
    print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <map>

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i++)
#define PI 3.141592653589

using namespace std;

int gcd(int a, int b){return (a % b)? gcd(b, a % b) : b;}
int lcm(int a, int b){return a * b / gcd(a, b);}

void solve_A(){
    string s;
    cin >> s;
    if(s[0] != s[1] || s[1] != s[2]) cout  << "Yes";
    else cout << "No";

}
void solve_B(){
    int n, a, b;
    cin >> n >> a >> b;

    int tmp = n / (a+b);
    int ans = tmp * a;
    if(n - (a+b) * tmp < a) ans += n - (a+b) * tmp;
    else ans += a;

    cout << ans;
}

void solve_C(){
    int a, b;
    cin >> a >> b;

    int num;
    int ans = 10000;
    for(num = 0; num <= 1000; num++){
        if(floor(num * 0.08) == a && floor(num * 0.10) == b){
            if(ans >= num) ans = num;
            break;
        }
    }
    if(ans == 10000) cout << -1;
    else cout << ans;
    
}

int main(void){
    solve_C();
    
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int> m;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
    int x,n; cin>>x>>n;
	for(int i=0;i<n;i++){
		int a; cin>>a; 
		m[a]=1;
	}
	for(int i=0;i<200;i++){
		if(m[x-i]==0){cout<<(x-i)<<"\n"; return 0;}
		if(m[x+i]==0){cout<<(x+i)<<"\n"; return 0;}
	}
    return 0;	
}  

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e16;
const ll mod = 1000000007;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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;
}
int ctoi(char c) {
  if (c >= '0' && c <= '9') {
    return c - '0';
  }
  return 0;
}
ll factorial(ll n) {
  if (n == 1) {
    return 1;
  }
  ll ans = factorial(n-1);
  return ans*n;
}
ll gcd(ll a, ll b) {
  if (b == 0) return a;
  return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
  return (a/gcd(a, b))*b;
}
bool is_prime(ll n) {
  for (ll i = 2; i*i <= n; i++) {
    if (n%i == 0) return false;
  }
  return n != 1;
}
ll mod_pow(ll x, ll n, ll mod) {
  if (n == 0) return 1;
  ll res = mod_pow(x*x%mod, n/2, mod);
  if (n & 1) res = res * x % mod;
  return res;
}

int main() {
  ll n;
  cin >> n;
  ll res = 0;
  rep(i, n) {
    rep(j, n) {
      rep(k, n) {
        res += gcd(gcd(i+1, j+1), k+1);
      }
    }
  }
  cout << res << endl;
}

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

int main() {
    int N,i,j,s=0;
    cin >> N;
    vector<int> d(N);

    for(i=0; i<N; i++)
        cin >> d.at(i);

    for(i=0; i<N-1; i++)
        for(j=i+1; j<N; j++)
            s += d.at(i)*d.at(j);
    
    cout << s << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
#include<cstring>
#include<string>
#include<stack>
#include<malloc.h>
#include<math.h>
using namespace std;
//#define int long long
typedef pair<int, int> pii;
typedef pair<int, char> pic;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, M;
pii vs[100100];
int c[100100];

signed main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int a, b;
        cin >> a >> b;
        vs[i] = mk(b, a);
    }
    for(int i = 0; i < M; i++){
        int a;
        cin >> a;
        c[i] = a;
    }
    sort(vs, vs + N, greater<pii>() );
    sort(c, c + M, greater<int>() );
    int ans = 0;
    int k = 0;
    for(int i = 0; i < M; i++){
        while(k < N){
            if(vs[k].second <= c[i])break;
            k++;
        }
        if(k >= N)break;
        if(vs[k].second <= c[i]){
            ans++;
            k++;
        }
    }
    cout << ans << endl;
    


    return 0;
}

/*



*/


Measured memory_bytes: 4332
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import Counter
N = int(input())
As = list(mapint())

cum = 0
for a in As:
    cum^=a
A = []
for a in As:
    ans = cum^a
    A.append(str(ans))
print(' '.join(A))

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

using namespace std;

const int MAX_N = 5e4+10, MAX_M = 30;
const int INF = (1<<29);

int main(int argc, char const *argv[])
{
	int n, m, c[MAX_M], t[MAX_N];
	cin >> n >> m;
	for (int i = 0; i < m; ++i)  cin >> c[i];

	for (int i = 0; i <= n; ++i) t[i] = INF;
	t[0] = 0;

	for (int i = 0; i < m; ++i) {
		for (int j = 0; j+c[i] <= n; ++j) {
			t[j+c[i]] = min(t[j+c[i]], t[j]+1);
		}
	}

	cout << t[n] << endl;
	return 0;
}



Measured memory_bytes: 3284
#include <bits/stdc++.h>
#define rp1(i,n) for ((i)=1;(i)<=(n);(i)++)
#define rp0(i,n) for ((i)=0;(i)<(n);(i)++)
using namespace std;
const int mod=998244353;
int n,m,t,s[1200005],ans;
void update(int x,int l,int r,int ll,int rr,int c){
	if(l==r){
		s[x]=max(s[x],c);
		return;
	}
	int mid=(l+r)/2;
	if(ll<=mid)update(x+x,l,mid,ll,rr,c);
	if(rr>mid) update(x+x+1,mid+1,r,ll,rr,c);
	s[x]=max(s[x+x],s[x+x+1]);
}
int query(int x,int l,int r,int ll,int rr){
	if(ll<=l&&r<=rr) return s[x];
	int mid=(l+r)/2,f=0;
	if(ll<=mid)f=max(f,query(x+x,l,mid,ll,rr));
	if(rr>mid) f=max(f,query(x+x+1,mid+1,r,ll,rr));
	return f;
}
int main(){
	cin>>n>>m;int i;
	rp0(i,n){
		int x;cin>>x;
		int l=max(0,x-m),r=min(300000,x+m);
		int t=query(1,0,300000,l,r)+1;
		ans=max(ans,t);
		update(1,0,300000,x,x,t);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 7736
import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

if N == 2:
    print(abs(A[0] - A[1]))
else:
    ans = INF

    x = A[0]
    y = sum(A[1:])

    for i in range(1, N-2):
        x = x + A[i]
        y = y - A[i]

        tmp = abs(x - y)
        if tmp < ans:
            ans = tmp
    print(ans)


Measured memory_bytes: 32288
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_map>

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

using namespace std;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

int main(){
    int n; cin >> n;
    string s,t; cin >> s >> t;
    for(int i=0; i<n;i++) {
        cout << s[i] << t[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)

int main()
{
	while(1)
	{
		int n;
		ll res = 0;
		ll sum = 0;
		vector<ll>con;
		
		cin >> n;
		if(n == 0) break;
		for(int i=0;i<n;i++)
		{
			ll a; cin >> a;
			sum+=a;
		}
		for(int i=0;i<n-1;i++)
		{
			ll b; cin >> b;
			con.pb(b); sum+=b;
		}
		sort(con.begin(),con.end());
		res = sum;
		
		for(int i=0;i<con.size();i++)
		{
			sum -= con[i];
			res = max(res,sum*1LL*(i+2));
		}
		
		cout << res << endl;
	}
}

Measured memory_bytes: 2132
#include <bits/stdc++.h>
#define REP(i, n) for(int i=0; i<(int)(n); ++i)
#define FOR(i, s, n) for(int i=(int)(s); i<(int)(n); ++i)
#define ALL(n) (n).begin(), (n).end()
#define pb push_back

using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> mat;

const ll MAX_V = 100000;
const ll INF = 1e9;
const ll MOD = 998244353;

bool pairCompare(const pair<ll, ll>& firstElof, const pair<ll, ll>& secondElof)
{
    return firstElof.second < secondElof.second;
}

int main(){
    int N, M; cin >> N >> M;
    vl A(N), B(M), C(M);
    vector<pair<ll, ll>> BC(M);
    REP(i, N) cin >> A[i];
    REP(i, M){
        ll b, c; cin >> b >> c;
        BC[i] = make_pair(b, c);
    }
    sort(ALL(A));
    sort(ALL(BC), pairCompare);
    // cout << BC.back().first << " " << BC.back().second << endl;
    auto iter = lower_bound(ALL(A), BC.back().second);
    int max_border = iter - A.begin();
    // cout << max_border << endl;
    int cnt = 1;
    int j = 0;
    // for(int i=max_border-1; i>=0; --i){
    REP(i, max_border){
        if (cnt > BC.size()) break;
        if (A[i] < BC[BC.size()-cnt].second){
            A[i] = BC[BC.size()-cnt].second;
            j++;
            if(BC[BC.size()-cnt].first == j){
                j = 0;
                cnt++;
            }
        }else{
            i--;
            j = 0;
            cnt++;
        }
    }
    ll sum = 0;
    REP(i, N){
        sum += A[i];
        // cout << A[i] << endl;
    }
    cout << sum << endl;
}

Measured memory_bytes: 4224
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#pragma comment(linker, "/STACK:16777216")
#pragma warning( disable : 6031)
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <numeric>
#include <algorithm>
#include <utility>
#include <bitset>
#include <cmath>
#include <sstream>
#include <functional>
#include <iomanip>
#include <limits>

#define all(a) (a).begin(),(a).end()
#define sz(a) (int)(a).size()
#define eps (1e-9)
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<double> vd;
typedef vector< vd > vvd;
typedef vector< ll > vll;
typedef vector< vll > vvll;
typedef vector< string > vs;
typedef pair< int, int > pii;
typedef vector< pii > vpii;
typedef tuple<int, int, int> tiii;
const long long mod = 1000000007;

template<typename T>
void max_self(T& a, T b)
{
	a = max(a, b);
}
template<typename T>
void add_self(T& a, T b)
{
	a += b;
	if (a >= mod)
		a -= mod;
}
template<typename T>
void sub_self(T& a, T b)
{
	a -= b;
	if (a < 0)
		a += mod;
}

// dp[i][j] - number of ways to distribute i candies to j kids

int main()
{ 
#ifdef LOCAL_MACHINE
	freopen("input.txt", "rt", stdin);
	freopen("output.txt", "wt", stdout);
#endif
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << setprecision(18) << fixed;
	int n, k;
	cin >> n >> k;
	vll dp(k + 1, 0);
	dp[0] = 1;
	for (int child = 0; child < n; child++)
	{
		int up_to;
		cin >> up_to;
		vll fake(k + 1);
		for (int used = k; used >= 0; used--)
		{
			ll tmp = dp[used];
			ll left = used + 1LL;
			ll right = min((ll)up_to, k - (ll)used) + used;
			if (left <= right)
			{
				add_self(fake[left], tmp);
				if (right < sz(fake) - 1)
					sub_self(fake[right + 1], tmp);
			}

		}
		ll cur_sum = 0;
		for (int i = 0; i < sz(fake); i++)
		{
			add_self(cur_sum, fake[i]);
			add_self(dp[i], cur_sum);
		}

	}
	cout << dp[k];
	return 0;
}

Measured memory_bytes: 1792
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)

    # N の逆元
    # N_inv = pow(N,MOD-2,MOD)

    # nCr
    # Nの階乗 * rの階乗の逆元 * n-rの階乗の逆元
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")

    # 大きな素数
    MOD = 10**9+7
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    S = input()
    T = input()
    tmp = S
    for i in range(len(S)):
        tmp = tmp[-1]+tmp[:len(S)-1]
        if tmp == T:
            print('Yes')
            return
    print('No')
if __name__ == '__main__':
    main()


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

#define ll long long
#define ull unsigned long long

using namespace std;

const ll INF = 1000000001;

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

int main() {
	ll N, X;
	cin >> N >> X;

	vector <ll> x(N+1);
	for (int ii = 0; ii < N; ++ii){
		cin >> x[ii];
	}
	x[N] = X;
	sort(x.begin(), x.end());

	vector <ll> dist(N);
	for (int ii = 0; ii < N; ++ii){
		dist[ii] = x[ii+1] - x[ii];
	}

	//全てのdistの最大公約数を求める
	ll ans = dist[0];
	for (int ii = 1; ii < N; ++ii){
		ans = gcd(ans, dist[ii]);
	}

	cout << ans << "\n";

	return 0;
}


Measured memory_bytes: 4696
import Control.Monad
import Control.Applicative
import Data.List
import Data.Array
strToInt s = (read :: String -> Int) s
f (a,_,_) = a
s (_,b,_) = b
t (_,_,c) = c

main = do
   [n,y] <- (map strToInt . words) <$> getLine
   let ansset = [(a,b,n-a-b) | a<-[0..n],b<-[0..n],a+b<=n,10000*a + 5000*b + 1000*(n-a-b) == y]
   
   if (null ansset) == True
   then putStrLn "-1 -1 -1"
   else putStrLn (show (f (head ansset)) ++" " ++ show (s (head ansset)) ++ " " ++ show (t (head ansset)) )


Measured memory_bytes: 892
#include <iostream>
  #include <string>
  #include <vector>
  #include <algorithm>
  #include <utility>
  #include <numeric>
  #include <map>
  using namespace std;
  typedef long long ll;
  #define rep(i,n) for (int i=0;i < (int)(n);i++)
  
  int main(){
   int n;
   string s;
   map<char,int> m;
   cin >> n;
   rep(i,n){
     char x;
     cin >> x;
     m[x]++;
   }
   int kind=0;
   for (auto w:m){
     kind++;
   }
   if(kind == 3) cout << "Three" << endl;
   else cout << "Four" << endl;
   
    return 0;
  }



Measured memory_bytes: 256
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    LL N;
    cin >> N;

    LL ans = 0;
    for (LL i = 1; i <= N; ++i) {
        if (i % 3 != 0 && i % 5 != 0) {
            ans += i;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#include <string>
using namespace std;
 
int main() {
  int N;
  cin >>N;
  int n=N;
  int sum=0;
  while(N>0){
    int k=N%10;
    sum+=k;
    N/=10;
  }
  if(n%sum==0){
    cout << "Yes" <<endl;
  }else{
    cout << "No" <<endl;
  }
}

Measured memory_bytes: 256
N = int(input())
V = list(map(int, input().split()))
odd, even = {}, {}
for i in range(N):
    if i % 2 == 1:
        if V[i] not in even:
            even[V[i]] = 0
        even[V[i]] += 1
    else:
        if V[i] not in odd:
            odd[V[i]] = 0
        odd[V[i]] += 1

sorted_odd = sorted(odd.items(), key=lambda x: x[1], reverse=True)
sorted_even = sorted(even.items(), key=lambda x: x[1], reverse=True)
if sorted_odd[0][0] != sorted_even[0][0]:
    print(N - sorted_even[0][1] - sorted_odd[0][1])
else:
    if len(sorted_odd) == 1 or len(sorted_even) == 1:
        print(N // 2)
    else:
        print(N - max(sorted_even[0][1] + sorted_odd[1][1], sorted_even[1][1] + sorted_odd[0][1]))

Measured memory_bytes: 20764
#include<stdio.h>

int main(void){
int i,c,N;
char S[100005]={};
scanf("%d",&N);
for(i=0;i<=N;i++){scanf("%c",&S[i]);}

i=1;
c=0;

while(i<=N){
   if(S[i]=='O'&&S[i-1]=='X'){
      c++;i+=2;
      }
      else if(S[i]=='X'&&S[i-1]=='O'){
         c++;i+=2;
         }
      else { i++; }
   }
printf("%d\n",c);
return 0;
}



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

int main() {

    std::string a, b, c; 
    int x, y; 

    std::cin >> a >> b; 
    std::cin >> x >> y; 
    std::cin >> c; 

    if (c == a) x --; 
    if (c == b) y --; 

    std::cout << x << " " << y << std::endl;

    return 0; 
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int x;
	int i = 1;
	while(1) {
		scanf("%d", &x);
		if (x == 0) {
			break;
		}
		printf("Case %d: %d\n", i, x);
		i++;
	}
	return 0;
}

Measured memory_bytes: 600
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long N = scanner.nextLong();
        long A = scanner.nextLong();
        long B = scanner.nextLong();

        long answer = 0;
        if (A >= N) {
            answer = N;
        } else if (A + B > N) {
            answer = A;
        } else {
            if (A + B != 0) {
                long numberOfBToAdd = N / (A + B);
                answer = numberOfBToAdd * A;
                long additional = N % (A + B);
                if (A != 0) {
                    if (additional >= A) {
                        answer += A;
                    } else {
                        answer += additional;
                    }
                }
            }
        }

        System.out.println(answer);
    }
}

Measured memory_bytes: 23124
public class Main {
	public static void main(String[] args) {
		long X = Long.parseLong(next());
		long Y = Long.parseLong(next());
		System.out.println(Math.abs(X - Y) <= 1 ? "Brown" : "Alice");
	}

	static int NI(){
		try {
			int c=System.in.read(),r=0;
			for(;c!='-'&&(c<'0'||'9'<c);)c=System.in.read();
			if(c=='-') return -NI();
			for(;'0'<=c&&c<='9';c=System.in.read())
				r = r * 10 + c - '0';
			return r;
		} catch (Exception e) {
			return -1;
		}
	}
	static String next() {
		try {
			StringBuilder res = new StringBuilder("");
			int c = System.in.read();
			while (Character.isWhitespace(c))
				c = System.in.read();
			do {
				res.append((char) c);
			} while (!Character.isWhitespace(c = System.in.read()));
			return res.toString();
		} catch (Exception e) {
			return null;
		}
	}
}


Measured memory_bytes: 23124