akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)1e9 + 7;


//---------------------------------------------------------------
template<int MOD> struct ModInt { int x;
    explicit operator bool() const { return !!x; }
    ModInt(int v = 0) : x(v % MOD) { if (x < 0) x += MOD; }
    ModInt(long long v) : x(v % MOD) { if (x < 0) x += MOD; }
    ModInt &operator+=(const ModInt &r) { if ((x += r.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(const ModInt &r) { if ((x += MOD - r.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(const ModInt &r) { x = 1LL * x * r.x % MOD; return *this; }
    ModInt &operator/=(const ModInt &r) { return *this *= r.inv(); }
    ModInt operator-() const { return x ? ModInt(MOD - x) : ModInt(x); }
    ModInt operator+(const ModInt &r) const { return ModInt(*this) += r; }
    ModInt operator-(const ModInt &r) const { return ModInt(*this) -= r; }
    ModInt operator*(const ModInt &r) const { return ModInt(*this) *= r; }
    ModInt operator/(const ModInt &r) const { return ModInt(*this) /= r; }
    ModInt inv() const { long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); }
        return ModInt(u); } // x.pow(MOD-2)
    ModInt pow(long long k) const { ModInt r(1), a(x);
        while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
    bool operator==(const ModInt r) const { return x == r.x; }
    bool operator!=(const ModInt r) const { return x != r.x; }
    bool operator< (const ModInt r) const { return x <  r.x; }
    friend ostream& operator<<(ostream &os, const ModInt<MOD>& a) { return os << a.x; }
    friend istream& operator>>(istream &is, ModInt<MOD>& a) { return is >> a.x; }
};
template<typename T, int SZ> struct Comb { vector<T> _fac, _ifac, _inv;
    Comb() : _fac(SZ + 1), _ifac(SZ + 1), _inv(SZ + 1) {
        _fac[0] = _ifac[SZ] = _inv[0] = 1;
        for (int i = 1; i <= SZ; i++) _fac[i] = _fac[i - 1] * i;
        _ifac[SZ] /= _fac[SZ];
        for (int i = SZ - 1; i >= 0; i--) _ifac[i] = _ifac[i + 1] * (i + 1);
        for (int i = 1; i <= SZ; i++) _inv[i] = _ifac[i] * _fac[i - 1]; }
    T inv(int n) { return n < 0 ? T(0) : _inv[n]; }
    T fac(int n) { return n < 0 ? T(0) : _fac[n]; }
    T ifac(int n) { return n < 0 ? T(0) : _ifac[n]; }
    T P(int a, int b) { return (b < 0 || a < b) ? T(0) : _fac[a] * _ifac[a - b]; }
    T C(int a, int b) { return b < 0 ? T(0) : P(a, b) * _ifac[b]; }
    T H(int n, int k) { if (n < 0 || k < 0) return T(0);
        return k == 0 ? T(0) : C(n + k - 1, k); }
    T S(int n, int k) { T r = 0;
        for (int i = 0; i <= k; i++) {
            T t = C(k, i) * T(i).pow(n); r += ((k - i) & 1 ? -t : t);
        }
        return r * _ifac[k];
    }
};
typedef ModInt<MOD> mint;
//---------------------------------------------------------------

int main() {
    Comb<mint, 250000> com;
    int n, k; cin >> n >> k;
    cout << com.S(n, k) * com.fac(k) << endl;
    return 0;
}


Measured memory_bytes: 5568
#include <iostream>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <utility>
#include <string.h>
#include <map>
#include <stack>
#include <iomanip>
#include <chrono>
#include <random>
#include <math.h>
#include <time.h>
#include <assert.h>
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define all(x) x.begin(),x.end() 
#define PII pair <ll,ll>
#define N 100005
#define MOD 1000000007
#define INF 1000000000000000000
using namespace std;

ll A[65][65];
map <string, int> m;
map <int, string> rm;
void map_possibilities()
{
	int x = 1;
	for (int i = 1; i <= 4; ++i)
	{
		for (int j = 1; j <= 4; ++j)
		{
			for (int k = 1; k <= 4; ++k)
			{
				int val = i * 100 + j * 10 + k;
				string s = to_string(val);
				m[s] = x;
				rm[x] = s;
				x++;
			}
		}
	}
}
bool valid(string s)
{
	int n = (int) s.size();
	if(s.find("132") != string::npos)
		return false;
	for (int i = 0; i < n - 1; ++i)
	{
		swap(s[i], s[i + 1]);
		if(s.find("132") != string::npos)
			return false;
		swap(s[i], s[i + 1]);
	}
	return true;
}
void calc_matrix()
{
	string s, t;
	int cnt = 0;
	for (int i = 1; i <= 64; ++i)
	{
		for (int j = 1; j <= 64; ++j)
		{
			s = rm[i], t = rm[j];
			if(s[1] != t[0] || s[2] != t[1])
				continue;
			s.push_back(t.back());
			if(valid(s))
			{
				A[j][i] = 1;
			}
		}
	}
}
void matrix_mul(ll x[][65], ll y[][65])
{
	ll c[65][65];
	memset(c, 0, sizeof(c));
	for (int i = 1; i <= 64; ++i)
	{
		for (int j = 1; j <= 64; ++j)
		{
			for (int k = 1; k <= 64; ++k)
			{
				c[i][j] += x[i][k] * y[k][j];
				c[i][j] %= MOD;
			}
		}
	}
	for (int i = 1; i <= 64; ++i)
		for (int j = 1; j <= 64; ++j)
			x[i][j] = c[i][j];
}
ll matrix_expo(ll mat[][65], int b)
{
	ll res[65][65], cnt = 0;
	memset(res, 0, sizeof(res));
	for (int i = 1; i <= 64; ++i)
	{
		res[i][i] = 1;
	}
	while(b != 0)
	{
		if(b & 1)
			matrix_mul(res, mat);
		matrix_mul(mat, mat);
		b /= 2;
	}
	for (int i = 1; i <= 64; ++i)
	{
		for (int j = 1; j <= 64; ++j)
		{
			cnt += res[i][j];
			cnt %= MOD;
		}
	}
	return cnt;
}
int main()
{
	int n;
	cin >> n;
	memset(A, 0, sizeof(A));
	map_possibilities();
	calc_matrix();
	if(n == 3)
		cout << 61;
	else
		cout << matrix_expo(A, n - 3);
}



Measured memory_bytes: 384
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x;
  cin >> x;
  int num = (x%100+4)/5;
  if (x%100+num*100 <= x)
    cout << 1 << endl;
  else
    cout << 0 << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 200005
#define inf 1000000000
using namespace std;

int n,dp[N],st[30][N*4];
char s[N];

int get(int node,int bas,int son,int x,int y,int c) {

  if(x>y) return n+1;
  if(bas>y || son<x) return n+1;
  if(bas>=x && son<=y) return st[c][node];
  int orta=(bas+son)/2;
  return min(get(node*2,bas,orta,x,y,c),get(node*2+1,orta+1,son,x,y,c));

}

void build(int node,int bas,int son,int c) {

  if(bas==son) {
    if(s[bas]=='a'+c) {
      st[c][node]=bas;
    }
    else {
      st[c][node]=n+1;
    }
    return ;
  }
  int orta=(bas+son)/2;
  build(node*2,bas,orta,c);
  build(node*2+1,orta+1,son,c);
  st[c][node]=min(st[c][node*2],st[c][node*2+1]);

}

int dfs(int now) {

  int ret=inf;
  if(now>n) return dp[now]=0;
  if(~dp[now]) return dp[now];
  for(int i=0;i<26;i++) {
    int aft=get(1,1,n,now+1,n,i);
    ret=min(ret,dfs(aft)+1);
  }
  return dp[now]=ret;

}

int main() {

  memset(dp,-1,sizeof(dp));
  scanf("%s",s+1);
  n=strlen(s+1);
  for(int i=0;i<26;i++) {
    build(1,1,n,i);
  }
  dfs(0);
  int now=0,cev=dp[0];
  while(now<=n) {
    for(int i=0;i<26;i++) {
      int aft=get(1,1,n,now+1,n,i);
      if(cev-1==dp[aft]) {
        printf("%c",i+'a');
        cev=dp[aft];
        now=aft;
        break ;
      }
    }
  }

}


Measured memory_bytes: 85248
fun main(args : Array<String>) {
    val (N, K) = readLine()!!.split(" ").map { it.toLong() }

    val places = N-K +1
    (1..K).forEach { m ->
        val double = nCk(K - 1, m - 1, 1000000007)
        if (m > places) {
            println(0)
        } else {
            println((nCk(places, m, 1000000007) * double).mod(1000000007))
        }
    }
}

//return nCk mod M (M must be prime number) O(min(k,n-k)*logM)
fun nCk(n: Long, k: Long, M: Long): Long {
    var ret: Long = 1
    val min = Math.min(k, n - k)
    for (i in 1..min) {
        ret = ret * pow(i, M - 2, M) % M
    }
    for (i in n - min + 1..n) {
        ret = ret * i % M
    }
    return ret
}

fun pow(a: Long, b: Long, M: Long): Long {
    var b = b
    var ret: Long = 1
    var tmp = a
    while (b > 0) {
        if (b and 1 == 1L) ret = ret * tmp % M
        tmp = tmp * tmp % M
        b = b shr 1
    }
    return ret
}

Measured memory_bytes: 37816
a = []
for i in range(3):
    a.append(list(map(int,input().split())))

n = int(input())
b = []
for i in range(n):
    b.append(int(input()))

# print(a)
# print(b)

for i in b:
    for j in range(3):
        for k in range(3):
            if a[j][k] == i:
                a[j][k] = 0

tmp = 0
if a[0][0] + a[1][1] + a[2][2] == 0:
    tmp = 1
if a[0][2] + a[1][1] + a[2][0] == 0:
    tmp = 1
if a[0][0] + a[0][1] + a[0][2] == 0:
    tmp = 1
if a[1][0] + a[1][1] + a[1][2] == 0:
    tmp = 1
if a[2][0] + a[2][1] + a[2][2] == 0:
    tmp = 1
if a[0][0] + a[1][0] + a[2][0] == 0:
    tmp = 1
if a[0][1] + a[1][1] + a[2][1] == 0:
    tmp = 1
if a[0][2] + a[1][2] + a[2][2] == 0:
    tmp = 1

if tmp == 1:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
const int N=6e5+5;
int n,i,j,k,id[N],oo[N];
string s,f[N];
vector<int>v[2];
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>s;for(i=0;i<n*2;++i)v[s[i]-'a'].push_back(i);
	for(i=0;i<n;++i)id[v[0][i]]=id[v[1][i]]=i,oo[v[0][i]]=v[1][i],oo[v[1][i]]=v[0][i];
	for(i=n*2-1;i>=0;--i)if(oo[i]>i){
		if(s[i]=='a'){f[i]=max("ab"+f[oo[i]+1],f[i+1]);continue;}
		f[i]="b";
		for(j=i+1,k=oo[i];j<k;++j){
			if(oo[j]>j)k=oo[j];
			if(id[j]>=id[i])f[i]=f[i]+s[j];
		}
		f[i]=f[i]+"a"+f[j+1];
		f[i]=max(f[i],f[i+1]);
	}else f[i]=f[i+1];
	cout<<f[0]<<endl;
	return 0;
}

Measured memory_bytes: 18688
url = "https://atcoder.jp//contests/abc158/tasks/abc158_c"

def main():
    A, B = list(map(int, input().split()))
    ans = -1
    for i in range(1000, 0, -1):
        if int(i * 0.08) == A and int(i * 0.1) == B:
            ans = i
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		
		int change;
		if (n % 1000 == 0) change = 0;
		else change = 1000 - (n % 1000);
		
		System.out.println(change);
		
		sc.close();
	}
	
}



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

const int N = 2e5+5;
int A[N],B[N];

int ind[N][2],sz[N];
ll pre[N];
void solve() {
    int n;
    scanf("%d",&n);
    ll Asum = 0,Bsum = 0;
    ll ret = 1e18;
    vector<pair<int,int> > v;
    for(int i=0;i<n;++i) {
        scanf("%d %d",&A[i],&B[i]);
        Asum += A[i];
        Bsum += B[i];
        v.push_back(make_pair(A[i],i));
        v.push_back(make_pair(B[i],i));
    }
    sort(v.begin(),v.end());
    ret = min(Asum,Bsum);
    for(int i=0;i<v.size();++i) {
        int id = v[i].second;
        ind[id][sz[id]++] = i+1;
        pre[i+1] = pre[i] + v[i].first;
    }

    for(int i=0;i<n;++i) {
        ll tmp = A[i] + B[i];
        vector<int> pos;
        for(int j=0;j<2;++j) {
            pos.push_back(ind[i][j]);
        }
        assert(pos.size()==2);
        if(pos[0]>pos[1]) {
            swap(pos[0],pos[1]);
        }
        int pp = -1;
        for(int j = n-2;j<=n;++j) {
            int cc = j;
            for(int k = 0;k<2;++k) {
                if(pos[k]<=j) {
                    --cc;
                }
            }
            if(cc==n-2) {
                pp = j;
                break;
            }
        }
        int rem = pp - (n-2);
        ll sum = pre[pp];
        for(int j = 0;j<rem;++j) {
            sum -= v[pos[j]-1].first;
        }
        tmp += sum;
        ret = min(ret,tmp);
    }
    printf("%lld\n", ret);
}
int main(){
   //freopen("input.txt","r",stdin);
   solve();
   return 0;
}

Measured memory_bytes: 6512
//ITNOA
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
const long long INF=1e9+10,MAX=2e5+1e4,MOD=1e9+7;
typedef long long ll;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
void OUT(long double o,int x){
	 cout<<fixed<<setprecision(x)<<o;
	 return;
}
ll a[MAX],b[200][200];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll h,w,n;
	cin>>h>>w>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	ll x=1,y=1;
	for(int i=0;i<n;i++){
		while(a[i]>0){
			if(x%2==1){
				while(a[i]>0&&y<=w){
					a[i]--;
					b[x][y]=i;
					y++;
				}
			}
			if(y==w+1){
				x++;
				y=w;
			}
			if(x%2==0){
				while(a[i]>0&&y>0){
					a[i]--;
					b[x][y]=i;
					y--;
				}
			}
			if(y==0){
				x++;
				y=1;
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++)
			cout<<b[i][j]+1<<" ";
		cout<<"\n";
	}
	return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<string>
#include<vector>

class dice{
    public:
    int num[6];
    int u, bt, r, l, f, bk;

    void turn(char seq);
    void setnum(int a, int b, int c, int d, int e, int f);
};

void dice::turn(char seq){
        int a;
        if(seq=='N'){
            a=bk;
            bk=u;
            u=f;
            f=bt;
            r=r;
            l=l;
            bt=a;
        }
        else if(seq=='S'){
            a=f;
            f=u;
            u=bk;
            bk=bt;
            r=r;
            l=l;
            bt=a;
        }
        else if(seq=='E'){
            a=r;
            r=u;
            u=l;
            l=bt;
            bt=a;
            f=f;
            bk=bk;
        }
        else if(seq=='W'){
            a=l;
            l=u;
            u=r;
            r=bt;
            bt=a;
            f=f;
            bk=bk;
        }
}

void dice::setnum(int n0, int n1, int n2, int n3, int n4, int n5){
    u=n0;
    bt=n5;
    r=n2;
    l=n3;
    f=n1;
    bk=n4;
}

int main(){
    int count=0;
    int n,num[100][6];
    
    std::string all="NSNNNENNNENNNWNNNWNNNENNN";
    
    std::cin>>n;
    std::vector<dice> dice(n);
    
    for(int i=1; i<=n; i++){
        for(int j=0; j<6; j++){
        std::cin>>num[i][j];
        }
            dice[i].setnum(num[i][0],num[i][1],num[i][2],num[i][3],num[i][4],num[i][5]);
    }
            
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            for(int k=0; k<all.size(); k++){
                dice[j].turn(all[k]);
                if(dice[i].u==dice[j].u && dice[i].bt==dice[j].bt && dice[i].r==dice[j].r && dice[i].l==dice[j].l && dice[i].f==dice[j].f && dice[i].bk==dice[j].bk){
                    count+=1;
                    break;
                }
            }
        }
    }

    if (count==0){
        std::cout<<"Yes"<<std::endl;
    }else{
        std::cout<<"No"<<std::endl;
    }
    return 0;
}


Measured memory_bytes: 3220
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>
using namespace std;

using ll = long long;
using boost::irange;

int main(){

    int n;
    cin >> n;

    string S;
    cin >> S;

    for (int i: irange(0, (int)S.size())){
        S[i] += n;
        if (S[i] > 'Z'){
            S[i] -= 26;
        }
    }

    cout << S << endl;


    return 0;
}

Measured memory_bytes: 256
#include <unordered_map>
#include <iostream>
#include <algorithm>

using namespace std;

int main(){
  unordered_map<string,int> us;
  string s;
  while(cin >> s){
    us[s]++;
  }
  string ans1;
  int times = 0;
  string ans2;
  int length = 0;
  for(auto i : us){
    if(i.second > times){
      ans1 = i.first;
      times = i.second;
    }
    if(i.first.length() > length){
      ans2 = i.first;
      length = i.first.length();
    }
  }
  cout << ans1 << ' ' << ans2 << '\n';
     
}

Measured memory_bytes: 3072
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int weightNum = sc.nextInt();

        int[] weights = new int[weightNum];
        int total = 0;
        for(int i = 0; i < weightNum; i++){
            weights[i] = sc.nextInt();
            total += weights[i];
        }

        int index = 0;
        int sum = 0;
        while(sum < total / 2){
            sum += weights[index];
            index++;
        }
        int ans = minDiff(index, weights, weightNum);
        ans = Math.min(ans,minDiff(index-1, weights, weightNum));
        System.out.println(ans);
    }

    public static int minDiff(int index, int[] weights, int weightNum){
        int ans = 0;
        for(int i = 0; i < index; i++){
            ans += weights[i];
        }
        for(int i = index; i < weightNum; i++){
            ans -= weights[i];
        }
        return Math.abs(ans);
    }

}


Measured memory_bytes: 23380
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 10000000
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}

func max(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v > ret {
			ret = v
		}
	}
	return ret
}

func min(nums ...int) int {
	ret := nums[0]
	for _, v := range nums {
		if v < ret {
			ret = v
		}
	}
	return ret
}

func main() {
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, initialBufSize), maxBufSize)
	defer wt.Flush()

	n := nextInt()
	c := []byte(next())

	l, r := make([]int, n), make([]int, n)
	if c[0] == 'W' {
		l[0] = 1
	}
	for i := 1; i < n; i++ {
		if c[i] == 'W' {
			l[i] = l[i-1] + 1
		} else {
			l[i] = l[i-1]
		}
	}
	if c[n-1] == 'R' {
		r[n-1] = 1
	}
	for i := n - 2; i >= 0; i-- {
		if c[i] == 'R' {
			r[i] = r[i+1] + 1
		} else {
			r[i] = r[i+1]
		}
	}

	ans := min(l[n-1], r[0])
	for i := 0; i < n-1; i++ {
		ans = min(ans, max(l[i], r[i+1]))
	}
	puts(ans)
}


Measured memory_bytes: 6040
#include <bits/stdc++.h>
using namespace std;
 
#define MOD 1000000007
#define INF  2000000000
//#define int ll
#define ll long long
#define ld long double
#define vi vector<int>
#define pa pair<int, int>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
 
#define INIT ios::sync_with_stdio(false);cin.tie(0);
#define VAR(type, ...)type __VA_ARGS__;MACRO_VAR_Scan(__VA_ARGS__);
template<typename T> void MACRO_VAR_Scan(T& t) { cin >> t; }
template<typename First, typename...Rest>void MACRO_VAR_Scan(First& first, Rest&...rest) { cin >> first; MACRO_VAR_Scan(rest...); }
#define VEC(type, c, n) vector<type> c(n);for(auto& i:c)cin>>i;
#define MAT(type, c, m, n) vector<vector<type>> c(m, vector<type>(n));for(auto& r:c)for(auto& i:r)cin>>i;
 
#define BR cout << "\n";
#define SP cout << " ";
#define ENDL cout<<endl;
#define OUT(d) cout<<(d);
#define OUTL(d) cout<<(d); BR;
#define YES OUTL("YES")
#define Yes OUTL("Yes")
#define NO OUTL("NO")
#define No OUTL("No")
#define RET return 0;
#define SUM(a, n) accumulate(a, a+n, 0)
#define VSUM(v) accumulate(ALL(v), 0);
 
#define REP(i, n) for(int i=0;i<(n);i++)
#define RREP(i, n) for(int i=n-1;i>=0;--i)
#define FOR(i, m, n) for(int i = m;i < n; i++)
#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define AREP(a, n) for(auto (a):(n))
#define ALL(a) (a).begin(),(a).end()
#define IN(n, a, b) ((a)<=(n)&&(n)<(b))

signed main(){ INIT;
    VAR(int, n);
    VEC(int, a, n);
    ll s=0, t=0, b=0;
    REP(i, n){
        b += a[i];
        if(i%2 && b<=0) s+= abs(b)+1, b=1;
        if(!(i%2) && b>=0) s+= b+1, b=-1;
    }
    b=0;
    REP(i, n){
        b += a[i];
        if(!(i%2) && b<=0) t+= abs(b)+1, b=1;
        if(i%2 && b>=0) t+= b+1, b=-1;
    }
    OUTL(min(s,t));
RET;}

Measured memory_bytes: 640
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<set>
using namespace std;
int b[30];
int n;
int solve(int i,int m){
	if(m==0)
		return 1;
	if(i>=n)
		return 0;
	int res;
	if(m-b[i]>=0)
		res=solve(i+1,m)||solve(i+1,m-b[i]);
	else
		res=solve(i+1,m);
	return res;
}
int main()
{
	ios::sync_with_stdio(false);
	int m;
	while(cin>>n){
		for(int i=0;i<n;i++){
			cin>>b[i];
		}
		cin>>m;
		int te;
		for(int i=0;i<m;i++){
			cin>>te;
			if(solve(0,te))
				cout<<"yes"<<endl;
			else
				cout<<"no"<<endl;
		}
	}
	
	
	return 0;
}



Measured memory_bytes: 3124
class NormalInput {
  input: string[];
  pointer: number;
  constructor(raw: string) {
    this.input = raw.split(/ |\n/);
    this.pointer = 0;
  }
  int = (): number => {
    const ret = parseInt(this.input[this.pointer], 10);
    this.pointer++;
    return ret;
  };
  str = (): string => {
    const ret = this.input[this.pointer];
    this.pointer++;
    return ret;
  };
  strs = (length: number): string[] => {
    let ret: string[] = [];
    for (let i = 0; i < length; i++) {
      ret.push(this.str());
    }
    return ret;
  };
  ints = (length: number): number[] => {
    let ret: number[] = [];
    for (let i = 0; i < length; i++) {
      ret.push(this.int());
    }
    return ret;
  };
}
function rep(n: number) {
  let a = [];
  for (let i = 0; i < n; i++) a.push(i);
  return a;
}
function Main({ int, str, strs, ints }: NormalInput) {
  const N = int();
  const A = ints(N);
  const count = [];
  A.forEach(a => {
    if (!count[a]) count[a] = 0;
    count[a] = count[a] + 1;
  });
  let sum = 0;
  count.forEach(i => {
    if (i) {
      sum += (i * (i - 1)) / 2;
    }
  });
  // rep(count.length).forEach(i => console.log(i, count[i]));
  // console.log(sum);
  rep(N).forEach(i => {
    let x = count[A[i]];
    console.log(sum - (x * (x - 1)) / 2 + ((x - 1) * (x - 2)) / 2);
  });
}

//DO NOT EDIT
Main(new NormalInput(require("fs").readFileSync("/dev/stdin", "utf8")));


Measured memory_bytes: 70500
def resolve():
    N = int(input())

    Q = [[] for _ in range(N)]
    for i in range(N):
        pp, ss = input().split()
        Q[i] = [i + 1, pp, - int(ss)]

    Q.sort(key=lambda x: (x[1], x[2]))

    for QQ in Q:
        print(QQ[0])


resolve()

Measured memory_bytes: 3060
#include "bits/stdc++.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
#define int ll
typedef pair<int,int> pii;
#define fi first
#define se second
#define Sort(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/4
#define INTINF INT_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T &a, T b){if(a < b){a = b;return true;}return false;}
template<class T> inline bool chmin(T &a, T b){if(a > b){a = b;return true;}return false;}
/*----------------------------------------------------------------*/
// const int MOD = 998244353;
const int MOD = 1000000007;


/*----------------------------------------------------------------*/
signed main(){
	
	int k;
	cin >> k;
	int x = 7;
	for(int i = 1;i <= 2000000;i++){
		if(x%k == 0){
			cout << i << endl;
			return 0;
		}
		x = (10*x+7)%k;
	}
	cout << -1 << endl;

	return 0;
}
/*----------------------------------------------------------------*/

// g++ -std=gnu++17 code1.cpp
// sudo pip3 install --upgrade online-judge-tools
// rm -r -f test;oj dl https://code-festival-2017-qualb.contest.atcoder.jp/tasks/code_festival_2017_qualb_b
// rm -r -f test;oj dl https://atcoder.jp/contests/abc174/tasks/abc174_b

Measured memory_bytes: 3644
n = int(input())
goal = list(map(int,input().split()))
now = [0]*n
ans = 0

while goal != now:
    x = 0
    for i in range(n):
        if x == 0 and now[i] != goal[i]:
            x = 1
            now[i] += 1
        elif x == 1 and now[i] != goal[i]:
            now[i] += 1
        elif x == 1 and now[i] == goal[i]:
            break
    ans += 1

print(ans)


Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define BUF_SIZE 30

int get_int(void) {
  int num;
#ifdef BUF_SIZE
  char line[BUF_SIZE];
  if(!fgets(line, BUF_SIZE, stdin)) return 0;
  sscanf(line, "%d", &num);
#else
#error
#endif
  return num;
}


// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(int *arr, int size) {
#ifdef BUF_SIZE
    char line[BUF_SIZE];
    char *tmpbuf = line;
    int i;
    if(!fgets(line, BUF_SIZE, stdin)) return -1;
    for(i = 0; i < size; i++) {
        char *tmp = strtok(tmpbuf, " ");
        arr[i] = strtol(tmp, NULL, 10);
        tmpbuf = NULL;
    }
#else
#error
#endif
    return 0;
}

#define NUM_MAX 8
char used[NUM_MAX];
int p[NUM_MAX];
int idx = 0;

int perm1(int *arr, int pos, int size, int *comp, int *ans) {
    int i;
    if(pos == size) {
        // main func
        int flag = 1;
        idx++;
        for(i = 0; i < size; i++) {
            if(arr[p[i]] == comp[i]) continue;
            flag = 0; break;
        }
        if(flag) *ans = idx;
        return flag;
    }

    for(i = 0; i < size; i++) {
        if(used[i]) continue;
        used[i] = 1;
        p[pos] = i;
        int res = perm1(arr, pos+1, size, comp, ans);
        // cannot early return because used and p are global variables
        //if(res) return 1;
        used[i] = 0;
    }
    return 0;
}

int perm(int *comp, int size) {
    int ans = 0;
    idx = 0;
    int arr[NUM_MAX] = {1,2,3,4,5,6,7,8};
    // arr, 0, size (+ in: comp, out: ans)
    perm1(arr, 0, size, comp, &ans);
    return ans;
}

int main(void) {
    int size = get_int();
    int pidx, qidx;

    int ps[NUM_MAX];
    int qs[NUM_MAX];
    fget_array(ps, size);
    fget_array(qs, size);

    pidx = perm(ps, size);
    qidx = perm(qs, size);
#ifdef DEBUG
    printf("%d %d\n", pidx, qidx);
#endif

    int ans = pidx>qidx ? pidx-qidx : qidx-pidx;
    printf("%d\n", ans);

    return 0;
}

Measured memory_bytes: 128
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		List<Integer> sales = new ArrayList<>();
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		
		for(int i = 0;i<a;i++){
			int x = sc.nextInt();
			if(x == 0){
				sales.add(sc.nextInt());
			}else if(x == 1){
				System.out.println(sales.get(sc.nextInt()));
			}else{
				sales.remove(sales.size()-1);
			}
		}
		
	}
}



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

#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define ALL(x) x.begin(),x.end()
#define EPS (1e-8)
#define equals(a,b) (fabs((a)-(b))<EPS)

using namespace std;

typedef long long ll;
const int IINF = INT_MAX;
const ll LLINF = LLONG_MAX;

bool LT(double a,double b) { return !equals(a,b) && a < b; }
bool LTE(double a,double b) { return equals(a,b) || a < b; }

void compute() {

}

ll arr[200123][26];
int main() {
  string s;
  cin >> s;
  long long cnt = 1;
  rep(i,(int)s.size()) ++arr[i][s[i]-'a'];
  rep(i,26) {
    for(int j=(int)s.size()-1;j>=0;--j) {
      arr[j][i] += arr[j+1][i];
    }
  }
  rep(i,(int)s.size()) {
    rep(j,26) if( (s[i]-'a') != j ) cnt += ( arr[i][j] );
  }
  cout << cnt << endl;
  compute();
  return 0;
}


Measured memory_bytes: 41220
import Data.IORef
import Control.Monad

main :: IO()
main = do
        n <- readLn
        x <- readLn
        y <- readLn
        print =<< solve (y - x) (min x y) n

solve :: Int -> Int -> Int -> IO Int
solve a b n = do
                a' <- newIORef a
                b' <- newIORef b
                solve' a' b' n 2
    where solve' x' y' n m | n == m    = readIORef x'
                           | otherwise = do
                              z <- readLn
                              x <- readIORef x'
                              y <- readIORef y'
                              when (z - y > x) $ writeIORef x' (z - y)
                              when (z < y) $ writeIORef y' z
                              solve' x' y' n (m + 1)

Measured memory_bytes: 4400
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  string s;
  cin >> s;
  s[3] = '8';
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <math.h>
#include <algorithm>

using namespace std;

int main()
{
  int N;
  cin >> N;
  vector<int> A(N,0);
  for (int i=0;i<N;i++) cin >> A[i];
  sort(A.begin(), A.end());
  int maxa = A[N-1];
  int mina = A[0];
  vector<pair<int, int>> Pans;
  for (int i=1;i<N-1;i++) {
    if (A[i] < 0) {
      Pans.push_back(make_pair(maxa, A[i]));
      maxa -= A[i];
      continue;
    }
    Pans.push_back(make_pair(mina, A[i]));
    mina -= A[i];
  }
  Pans.push_back(make_pair(maxa, mina));
  cout << maxa - mina << endl;
  for (auto& v : Pans)
  {
    printf("%d %d\n", v.first, v.second);
  }
  return 0;
}


Measured memory_bytes: 3188
S = int(input())

num = ''
def division(N):
  if N%2==0:
    return N//-2,'0'
  else:
    return (N//-2)+1,'1'
  
  
if S==0:
  print(0)
else:
  while S!=0:
    a,b = division(S)
    num += b
    S = a
  print(num[::-1])
  

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

bool exist[100005]={0};

int main(){
    int n;
    cin >> n;
    int dup = 0;
    for(int i=0;i<n;++i){
        int a;
        cin >> a;
        if(exist[a])dup++;
        exist[a] = true;
    }
    cout << n - (dup+1)/2 * 2 << endl;

    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define ft first
#define sd second
#define pb push_back
#define pob pop_back()
#define pf push_front
#define pof pop_front()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<double,double> pdd;
typedef pair<long long,long long> pll;
// scanf("%d %d %d %d",&w,&b,&d,&s); %lld
// printf("%d\n" ,points);
// const double PI=acos(-1);

int main()
{
	int n; 
	string s, ans;
	cin >> n >> s;
	ans = s[0];
	
	for(int i = 1; i<n; i++)
		if(s[i] != s[i-1]) 
			ans += s[i];
	
	cout << ans.size() << endl;
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for(int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}

const int MAX_N = 200005;
int bit[MAX_N+1];
int nn = MAX_N; //　1-index

void adds(int a, int w){
    for(int x = a; x <= nn; x += x & -x) bit[x] += w;
}
int sums(int a){ // bit[1,a]の和を返す.
    int ret = 0;
    for(int x = a; x > 0; x -= x & -x) ret += bit[x];  
    return ret;
}


int main() {
    int n, k;
    cin >> n >> k;
    int a[n+1] = {};
    srep(i,1,n+1)cin >> a[i];

    rep(loop,k){
        rep(i,MAX_N+1)bit[i] = 0;
        srep(i,1,n+1){
            int l = max(1,i-a[i]);
            int r = min(n,i+a[i]);
            adds(l,1);
            adds(r+1,-1);
        }
        ll sum = 0;
        srep(i,1,n+1){
            a[i] = sums(i);
            sum += a[i];
        }
        if(sum == (ll)n * n)break;
    }
    srep(i,1,n+1)cout << a[i] << ' ';
    cout << endl;
    return 0;
}




Measured memory_bytes: 5168
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int i, j, H, W;
    cin >> H >> W;
  
    vector<string> vec(H);

    for(i=0; i < H; i++)
        cin >> vec.at(i);
  
    for(i=0; i < H; i++){
        for(j=0; j < W; j++){

            if(vec.at(i).at(j) == '.'){
   		        char count = '0';
                if(i != 0){
                    if(j != 0)
                        if(vec.at(i-1).at(j-1) == '#')
                            count++;
                    if(vec.at(i-1).at(j) == '#')
                        count++;
                    if(j != W-1)
                        if(vec.at(i-1).at(j+1) == '#')
                            count++;
                }
        
               if(i != H-1){
                    if(j != 0)
                        if(vec.at(i+1).at(j-1) == '#')
                            count++;
                    if(vec.at(i+1).at(j) == '#')
                        count++;
                    if(j != W-1)
                        if(vec.at(i+1).at(j+1) == '#')
                            count++;
                }

                if(j != 0)
      	            if(vec.at(i).at(j-1) == '#')
                        count++;
        
                if(j != W-1)
                    if(vec.at(i).at(j+1) == '#')
                        count++;
        
            vec.at(i).at(j) = count;
            }
        }
    }
  
    for(i=0; i < H; i++)
        cout << vec.at(i) << endl;
  
}

Measured memory_bytes: 256
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;


void main() {
    auto n = readln.chomp.to!int;
    auto g = new int[][](n);
    foreach (i; 0..n) {
        auto s = readln.split.map!(to!int).array;
        auto k = s.front;
        foreach (j; 1..k+1) {
            g[i] ~= s[j];
            g[s[j]] ~= i;
        }
    }

    auto lca = new LowestCommonAncestor(g, 0);

    auto q = readln.chomp.to!int;
    while (q--) {
        auto s = readln.split.map!(to!int);
        auto x = s[0];
        auto y = s[1];
        writeln(lca.lca(x, y));
    }
}


class LowestCommonAncestor {
    import std.algorithm : swap;
    import std.conv : to;
    import std.typecons : Tuple, tuple;
    import core.bitop : bsr;

    int n, root, lgn;
    int[][] graph;
    int[] depth;
    int[][] dp;

    this(const int[][] graph, int root) {
        n = graph.length.to!int;
        this.root = root;
        this.graph = new int[][](n);
        foreach (i; 0..n) this.graph[i] = graph[i].dup;

        lgn = bsr(n) + 3;
        depth = new int[](n);
        dp = new int[][](lgn, n);

        construct;
    }

    int lca(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);

        int diff = depth[a] - depth[b];
        foreach_reverse (i; 0..lgn) if (diff & (1<<i)) a = dp[i][a];

        if (a == b) return a;

        int K = lgn;
        while (dp[0][a] != dp[0][b]) {
            foreach_reverse (k; 0..lgn) {
                if (dp[k][a] != dp[k][b]) {
                    a = dp[k][a];
                    b = dp[k][b];
                    K = k;
                }
            }
        }

        return dp[0][a];
    }

    private void construct() {
        auto stack = new Tuple!(int, int, int)[](n+10);
        int sp = 0;
        stack[0] = tuple(root, -1, 0);
        while (sp >= 0) {
            auto u = stack[sp][0];
            auto p = stack[sp][1];
            auto d = stack[sp][2];
            sp -= 1;
            dp[0][u] = p;
            depth[u] = d;
            foreach (v; graph[u]) if (v != p) stack[++sp] = tuple(v, u, d+1);
        }

        foreach (k; 0..lgn-1)
            foreach (i; 0..n)
                dp[k+1][i] = (dp[k][i] == -1) ? -1 : dp[k][dp[k][i]];
    }
}



Measured memory_bytes: 29536
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int n,m,l=-INF,r=INF,li,ri,i,ans=0;
	cin >> n >> m;
	for(i=0; i<m; ++i){
		cin >> li >> ri;
		l = max(l,li);
		r = min(r,ri);
	}
	cout << (max(r-l+1,0)) << endl;
	return 0;
}


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

int main() {
  int n;
  cin>>n;
  vector<int> num(n);
  for(int i=0;i<n;i++){
    cin>>num.at(i);
  }
  int sum=0;
  int min=0;
  for(int i=0;i<n;i++){
    if(i!=0&&num.at(i)<=min){
      sum++;
      min=num.at(i);
    }
    if(i==0){
      min=num.at(i);
      sum++;
    }
  }
  cout<<sum<<endl;
}

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

int main(){
 int a, b, c;
 char op;
 c = 1;

 while(true){
  cin >> a >> op >> b;
  if(op == '?')break;
  else if(op == '+') c = a + b;
  else if(op == '-') c = a - b;
  else if(op == '*') c = a * b;
  else if(op == '/') c = a / b;
  else break;
  
  cout << c <<endl;
  
 }
}


Measured memory_bytes: 3112
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  ll N;
  cin>>N;
  string S;
  cin>>S;
  ll Q;
  cin>>Q;
  ll ans[Q];
  ll k;
  ll dnum, mnum;
  ll tmpans;
  ll dmap[N], mmap[N];
  for(ll i=0;i<Q;++i) {
    ans[i] = 0;
    cin>>k;
    dnum = 0;
    mnum = 0;
    for(ll j=0;j<N;++j) {
      dmap[j] = 0;
      mmap[j] = 0;
    }
    tmpans = 0;
    for(ll j=0;j<N;++j) {
      if(S[j]=='D') {
        dnum++;
        dmap[j]++;
      }
      if(S[j]=='M') {
        mnum++;
        mmap[j]++;
        tmpans += dnum;
      }
      if(S[j]=='C') {
        ans[i] += tmpans;
      }
      if(j-k+1>=0 && dmap[j-k+1]>0) {
        tmpans -= mnum;
        dnum--;
      }
      if(j-k+1>=0 && mmap[j-k+1]>0) {
        mnum--;
      }
    }
  }
  for(ll i=0;i<Q;++i) cout<<ans[i]<<endl;
}



Measured memory_bytes: 20024
S = input()

keyence = 'keyence'
new = S
if S.startswith(keyence) or S.endswith(keyence):
    print('YES')
    exit()
else:
    for char in S:
        if char == keyence[0]:
            new = new[1:]
            keyence = keyence[1:]
        else:
            break
if new.endswith(keyence):
    print('YES')
    exit()
print('NO')

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    private static final Scanner scn = new Scanner(System.in);
    
    public static void main(String[] args) {
        int n;
        while((n = scn.nextInt()) > 0) {
            System.out.println(aerobics(n));
        }
    }
    
    private static int aerobics(int n) {
        int count = 0;
        boolean next = true, left = false, right = false;
        for(int i = 0; i < n; i++) {
            switch(scn.next()) {
              case "lu":
                left = true;
                break;
              case "ld":
                left = false;
                break;
              case "ru":
                right = true;
                break;
              case "rd":
                right = false;
                break;
            }
            if(next == left && next == right) {
                next = !next;
                count++;
            }
        }
        return count;
    }
}

Measured memory_bytes: 37572
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
if a % 10 == 0:
  aa = 0 
else:
  aa = 10 - a % 10
  
if b % 10 == 0:
  bb = 0 
else:
  bb = 10 - b % 10

if c % 10 == 0:
  cc = 0 
else:
  cc = 10 - c % 10
  
if d % 10 == 0:
  dd = 0 
else:
  dd = 10 - d % 10
  
if e % 10 == 0:
  ee = 0 
else:
  ee = 10 - e % 10
l1 = [[a,aa],[b,bb],[c,cc],[d,dd],[e,ee]]
l2 = sorted(l1, key=lambda x:x[1])
time = 0
for i in range(4):
  time += l2[i][0] + l2[i][1]
time += l2[4][0]
print(time)

Measured memory_bytes: 3064
import copy
N , W = map(int, input().split())
item =[list(map(int, input().split())) for i in range(N)]
dp = [0] * (W+1)
dp2 = [0] * (W+1)
for i in range(N):
    w = item[i][0]
    v = item[i][1]
    for j in range(1, W+1):
        if j - w >= 0:
            dp2[j] = max(dp[j], dp[j-w] + v)
    dp = copy.copy(dp2)
print(dp[W])

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

using namespace std;

typedef long long int ll;

vector < int > cst = {INT_MAX, 2, 5, 5, 4, 5, 6, 3, 7, 6};

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

  int n, m;
  cin >> n >> m;
  vector < int > a(m + 1);
  for (int i = 1; i <= m; i++) {
    cin >> a[i];
  }

  sort(a.begin() + 1, a.end(), greater < int > ());

  vector < int > dp(n + 1, -1e9);
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      if (i - cst[a[j]] >= 0) dp[i] = max(dp[i], 1 + dp[i - cst[a[j]]]);
    }
  }

  while (n > 0) {
    int mx_digits = -1, num = -1;
    for (int j = 1; j <= m; j++) {
      if (n - cst[a[j]] >= 0 && dp[n - cst[a[j]]] > mx_digits) {
        mx_digits = dp[n - cst[a[j]]];
        num = a[j];
      }
    }

    cout << num;
    n -= cst[num];
  }

  cout << '\n';
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define rep2(i, x, n) for(int i = x, i##_len = (n); i < i##_len; ++i)
#define all(n) begin(n), end(n)
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vs = vector<string>;
using vc = vector<char>;
using vb = vector<bool>;
vi dir = {-1, 0, 1, 0, -1, -1, 1, 1, -1};

int main() {
  int h, n;
  cin >> h >> n;
  int sum = 0;
  rep(i, n) {
    int a;
    cin >> a;
    sum += a;
  }
  cout << (h <= sum ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#import numpy as np
import sys, math
from itertools import permutations, combinations, combinations_with_replacement
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

ll = list(combinations_with_replacement(range(1, M+1), N))
res = 0
for li in ll:
    val = 0
    for abcdi in abcd:
        a, b, c, d = abcdi
        if li[b-1] - li[a-1] == c:
            val += d
    if res < val:
        res = val
print(res)


Measured memory_bytes: 21924
#include <iostream>
#include <sstream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
using namespace std;

typedef pair <int, int> PII;
typedef vector <PII> VPII;
typedef vector <int> VI;

int dp[10][10000];

int main() {
    int m;
    while ( cin >> m && m ) {
        VPII v( m );
        for ( int i = 0; i < m; ++ i ) {
            cin >> v[i].first >> v[i].second;
        }
        for ( int i = 0; i < 10; ++ i ) {
            for ( int j = 0; j < 10000; ++ j ) {
                dp[i][j] = 0;
            }
        }
        dp[0][0] = 1;
        for ( int i = 0; i < m; ++ i ) {
            for ( int j = 0; j < 10000; ++ j ) {
                for ( int k = 0; k <= v[i].second; ++ k ) {
                    int s = j + v[i].first * k;
                    if ( s >= 10000 ) continue;
                    dp[i+1][s] += dp[i][j];
                }
            }
        }
        int g;
        cin >> g;
        for ( int i = 0; i < g; ++ i ) {
            int n;
            cin >> n;
            cout << dp[m][n] << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define YES cout<<"YES"<<"\n";
#define NO cout<<"NO"<<"\n";
#define pb push_back
#define f(i,a) for(ll i=0;i<a;i++)


int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    ll n;
    cin>>n;
    
    ll a[n];
    f(i,n)
    {
        cin>>a[i];
    }
    ll c=0;
    f(i,n)
    {
        if((i+1)%2!=0 && a[i]%2!=0)
        {
            c++;
        }
    }
    cout<<c<<endl;
    
	return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>

using namespace std;

bool kaibun(string s){
    size_t len = s.length();
    for(int i = 0; i < len/2; i++){
        if(s[i] != s[len-i-1]) return false;
    }
    return true;
}

void Kitei(int N,int K, vector<int> & v){
    int sho = N/K;
    int amari= N%K;
    v.push_back(amari);
    if(sho==0){
        return;
    }
    Kitei(sho,K,v);
}

int main(){
    int N,K =0;
    cin >> N >> K;
    vector<int> vec;
    Kitei(N,K,vec);
    cout << vec.size() <<endl;

    return 0;
}

Measured memory_bytes: 256
// ABD

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <ios>
#include <iomanip>
#include <string>
#include <numeric>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n <= 999) {
        cout << "ABC" << endl;
    } else {
        cout << "ABD" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define N 65536

int main(){
  int f,i,j,k,m;
  char l;
  int a[N],b[N],c[N];
  i = 0;
  while(1){
    scanf("%d %c %d", &j,&l,&k);
    if(0<=j && j<=20000 && 0<=k && k<=20000){
      if(l == '?'){
        break;
      }else if(l == '+'){
        a[i] = j+k;
      }else if(l == '-'){
        a[i] = j-k;
      }else if(l  =='*'){
        a[i] = j*k;
      }else if(l == '/'){
        if(k != 0){
          a[i] = j/k;
        }else{
          b[i] = 1;
        }
      }
    }else{
      c[i] = 1;
    }
    i++;
  }
  for(m=0;m<i;m++){
    if(b[m] == 1 || c[m] == 1){
      printf("Error\n");
    }else{
      printf("%d\n",a[m]);
    }
  }
  return 0;
}

Measured memory_bytes: 1036
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in);) {
			int h = sc.nextInt();
			int w = sc.nextInt();
			int k = sc.nextInt();

			char[][] masu = new char[h][w];
			for (int i = 0; i < h; i++) {
				String line = sc.next();
				for (int j = 0; j < w; j++) {
					masu[i][j] = line.charAt(j);
				}
			}

			int result = 0;

			for (int hBit = 0; hBit < (1 << h); hBit++) {
				ArrayList<Integer> hIndexes = new ArrayList<>();
				for (int i = 0; i < h; i++) {
					if ((1 & hBit >> i) == 1) {
						hIndexes.add(i);
					}
				}

				for (int wBit = 0; wBit < (1 << w); wBit++) {

					ArrayList<Integer> wIndexes = new ArrayList<>();
					for (int i = 0; i < w; i++) {
						if ((1 & wBit >> i) == 1) {
							wIndexes.add(i);
						}
					}

					//ここから処理
					int count = 0;
					for (int i = 0; i < h; i++) {
						for (int j = 0; j < w; j++) {
							if (masu[i][j] == '#' && hIndexes.contains(i) == false && wIndexes.contains(j) == false) {
								count++;
							}
						}
					}
					if (count == k) {
						result++;
					}

					//System.out.println(hBit + " " + wBit + " " + hIndexes.size() + " " + wIndexes.size() + " count:" + count );
				}
			}

			System.out.println(result);

		} catch (Exception e) {
			e.printStackTrace();
		}

	}

}

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

int N;
vector<int> A(210);

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

    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
    }

    int res = 0;

    while (true) {
        bool exit_odd = false;
        for (int i = 0; i < N; i++) {
            if (A.at(i) % 2 != 0) exit_odd = true;
        }

        if (exit_odd) break;

        for (int i = 0; i < N; i++) {
            A.at(i) /= 2;
        }
        res++;
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define mod 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll N,A,B;
  cin >> N >> A >> B;
  vector<ll> X(N);
  rep(i,N) cin >> X[i];
  ll ans=0;
  for(int i=1;i<N;i++){
    ans += min(A*(X[i]-X[i-1]),B);
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024