akhauriyash/Code-Regression huggingface dataset:
// clang-format off
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define rep1(i,n) for(ll i=1, i##_len=(n); i<=i##_len; ++i)
#define rrep(i,n) for(ll i=n-1; i>=0; --i)
#define rrep1(i,n) for(ll i=n; i>0; --i)
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort(all(x))
#define SORT_DESC(x) sort((x).rbegin(),(x).rend())
#define pb push_back
#define mp make_pair
#define coutl cout<<fixed<<setprecision(10)
#define ANS(ans) cout<<ans<<endl
#define END(ans) ANS(ans); return
const ll LINF = (1LL << 62) - 1;
const int INF = (1 << 30) - 1;
template<class T>inline bool chmax(T &a, const T &b){if (a<b){a=b;return 1;}return 0;}
template<class T>inline bool chmin(T &a, const T &b){if (b<a){a=b;return 1;}return 0;}
// clang-format on

void solve(long long N, long long W, std::vector<long long> w, std::vector<long long> v) {
  vector<vector<ll>> dp(N + 1, vector<ll>(W + 1));
  rep(i, N) rep(sum_w, W + 1) {
    if (sum_w - w[i] >= 0) {
      chmax(dp[i + 1][sum_w], dp[i][sum_w - w[i]] + v[i]);
    }
    chmax(dp[i + 1][sum_w], dp[i][sum_w]);
  }
  ANS(dp[N][W]);
}

// clang-format off
int main() {
  long long N;
  scanf("%lld",&N);
  long long W;
  scanf("%lld",&W);
  std::vector<long long> w(N);
  std::vector<long long> v(N);
  for(int i = 0 ; i < N ; i++){
    scanf("%lld",&w[i]);
    scanf("%lld",&v[i]);
  }
  solve(N, W, std::move(w), std::move(v));
  return 0;
}


Measured memory_bytes: 80256
#include<stdio.h>
#include<string.h>
int main()
{
    char S[105];
    int i,length=0,k;

    scanf("%d",&k);
    scanf("%s",&S);


        for(i=0;S[i]!='\0';i++)
        {
            length++;
        }


    if((length==k)||(length<k))
    {
        printf("%s\n",S);
    }
    if(length>k)
    {
        for(i=0;i<k;i++)
        {
            printf("%c",S[i]);
        }
        printf("...\n");
    }
    return 0;
}


Measured memory_bytes: 2088
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
 
#define NL '\n'
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define sz(x) x.size()
#define pi  acos(-1.0)
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define all(x) (x).begin(), (x).end()
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define fastIO() ios_base::sync_with_stdio(0),cin.tie(NULL)
 
template<class T>void read(T &x){int q=1;char ch;x=0;for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar()); 
if(ch == '-')ch=getchar(),q =-1;for(;'0'<=ch&&ch<='9';ch=getchar()) x=x*10 + ch-'0'; x*=q;} template<class T>  
void write(T x){if(x<0)putchar('-'),write(-x);else if(x<10)putchar(x+'0');else write(x/10),putchar(x%10+'0');}

#define faye_valentine 
void dbg(){cerr<<NL;}template<typename H,typename... T> void dbg(H h,T... t){cerr<<' '<<h;dbg(t... );}
#ifdef  faye_valentine
#define debug(...) cerr<<"("<<#__VA_ARGS__<<"):",dbg(__VA_ARGS__)
#else
#define debug(...) 
#endif
 
 
 
void absinthe(){
    int x, y; read(x); read(y);
    int k = (y - 2*x) / 2;
    if(4*k + (x-k)*2 == y && k <= x && k > -1) puts("Yes");
    else puts("No");
}
 
int main(){
    int Tx = 1; //read(Tx);  
    //fastIO(); cin >> Tx;
    while(Tx--) absinthe();
}

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

n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)

x = 0
y = 0
for i in range(len(a)):
    if i % 2 == 0:
        x += a[i]
    else:
        y += a[i]

print(x-y)


Measured memory_bytes: 9072
#!/usr/bin/env python3
import sys
import math
import itertools

def solve(N: int, x: "List[int]", y: "List[int]"):
    sum = 0
    kumi = list(itertools.permutations(range(N), N))
    for item in kumi:
        for i in range(N-1):
            a = item[i]
            b = item[i+1]
            hoge = math.sqrt((x[a]-x[b])**2 + (y[a]-y[b])**2)
            sum += hoge
    print(sum/len(kumi))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)

if __name__ == '__main__':
    main()


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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
#define REP(i,n) for(ll i = 0;i < (ll)n;i++)
#define REPD(i,n) for(ll i = (ll)n - 1;i >= 0;i--)
#define ALL(x) (x).begin(),(x).end()
#define FILLl(n,first_dimension_size,value) fill((ll*)n,(ll*)(n+first_dimension_size),value)
#define FILL(n,first_dimension_size,value) fill((int*)n,(int*)(n+first_dimension_size),value)
#define INF (1 << 29)
#define MOD 1000000007
//int dx[4] = {1,0,0,-1};
//int dy[4] = {0,1,-1,0};

int main(){

  int n,x;
  cin >> n >> x;
  vector<int> l(n);
  REP(i,n)cin >> l[i];
  ll res = 1,now = 0;
  for(int i = 0;i < n;i++){
    now += l[i];
    if(now > x)break;
    res++;
  }
  cout << res << endl;

  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
int main(){
    map<int,int>M;
    vector<pair<int,int> >V;
    int a,b;
    while(scanf("%d,%d",&a,&b),a||b){
        V.push_back(make_pair(b,a));
    }
    sort(V.begin(),V.end());
    reverse(V.begin(),V.end());
    int buf=100,cnt=0;
    for(int i=0;i<V.size();i++){
        if(buf>V[i].first){
            buf=V[i].first;
            cnt++;
        }
        M[buf]=cnt;
    }
    int n;
    while(cin>>n){
        int p;
        for(int j=0;j<V.size();j++){
            if(V[j].second==n){
                p=j;
                break;
            }
        }
        cout<<M[V[p].first]<<endl;
    }


}

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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j

int lbidx(vector<int> x, int y) {
  auto itr = lower_bound(x.begin(), x.end(), y);
  int idx = itr - x.begin();
  return idx;
};

int upidx(vector<int> x, int y) {
  auto itr = upper_bound(x.begin(), x.end(), y);
  int idx = itr - x.begin();
  return idx;
}

int main() {
  int N;
  cin >> N;
  vector<int> H(N);
  rep(i, 0, N) {
    cin >> H[i];
  }
  vector<vector<int>> block(100, vector<int> (100, 0));

  rep(i, 0, N) {
    int h = H[i];
    rep(j, 0, h) {
      block[j][i] = 1;
    }
  }
  int ans = 0;
  rep(i, 0, 100) {
    vector<int> row = block[i];
    rep(j, 0, row.size()) {
      int cell = row[j];
      if (j == 0) {
        if (cell == 1) {
          ans++;
        }
      } else {
        if (cell == 1 && row[j - 1] == 0) {
          ans++;
        }
      }
    }
  }
  cout << ans << endl;
};


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>
#include <unordered_map>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
static ull tenq = 1000000000;
static ull mod = tenq + 7;

using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<ll> as = {N / 1000, (N / 100) % 10, (N / 10) % 10, N % 10};

  for (auto i = 0; i < 8; i++) {
    string res_str = "";
    res_str += to_string(as[0]);
    ll res = as[0];
    for (auto j = 0; j < 3; j++) {
      if ((i >> j) & 1) {
        res_str += "+" + to_string(as[j+1]);
        res += as[j+1];
      } else {
        res_str += "-" + to_string(as[j+1]);
        res -= as[j+1];
      }
    }
    if (res == 7) {
      cout << res_str << "=7" << endl;
      return 0;
    }
  }

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using lint = long;
using llint = long long;
using namespace std;

void drawRect(int H, int W) {
    rep(h, H) {
        rep(w, W) cout << "#";
        cout << endl;
    }
}

int main() {
    fastIO;
    int H, W;
    while (cin >> H >> W) {
        if (H == 0 && W == 0)
            break;

        drawRect(H, W);
        cout << endl;
    }
}



Measured memory_bytes: 3124
#include <stdio.h>
#include<string.h>
int main(void) {
	// your code goes here
long int n,i,count,n1;


scanf("%ld",&n);
n1=(n%2==0)?n/2:(n-1)/2;
n-=n1;
printf("%ld",n1*n);

return 0;
}



Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr int INF = 1e9+1;


int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  set<int> odd;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (i % 2 == 0) odd.insert(a[i]); 
  }
  sort(a.begin(), a.end());
  int res = 0;
  for (int i = 0; i < n; i++) {
    if (i % 2 != 0 && odd.count(a[i])) res++; 
  }
  cout << res << endl;
  return 0;
} 

Measured memory_bytes: 2944
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    A=lmis()
    A.sort()
    q = deque()
    q.append(A.pop())
    ans = 0
    while A:
        s = q.popleft()
        ans += s
        ns = A.pop()
        q.append(ns)
        q.append(ns)
    print(ans)









main()



Measured memory_bytes: 32300
import sys
readline = sys.stdin.buffer.readline

n,m = map(int,readline().split())
lst1 = list(map(int,readline().split()))
ans = 0
for i in range(1,n):
    if lst1[i-1]+lst1[i] > m:
        res = max(0,m-lst1[i-1])
        ans += lst1[i]-res
        lst1[i] = res

if lst1[0]+lst1[1] > m:
    ans += lst1[0]-m

print(ans)


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

int main() {
    long long N;
    cin >> N;
    string res = "";
    while (N) {
        --N;
        res += (char)('a' + (N % 26));
        N /= 26;
    }
    reverse(res.begin(), res.end());
    cout << res << endl;
}

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

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

    bool ok = true;
    for (int i = 0; i < S.size(); i++)
    {
        if (i % 2 == 0 && S[i] == 'L')
        {
            ok = false;
            break;
        }

        else if (i % 2 == 1 && S[i] == 'R')
        {
            ok = false;
            break;
        }
    }

    if (ok)
    {
        cout << "Yes" << endl;
    }

    else
    {
        cout << "No" << endl;
    }
    

    return 0;
}

Measured memory_bytes: 256
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <random>
#include <cmath>
#include <chrono>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
using LL = long long;
#define eps 1e-8
#define fi first
#define se second
#define eb emplace_back
#define close std::ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define FOR(i, x, y) for (LL i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (LL i = (x), _##i = (y); i > _##i; --i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define CASET int ___T; cin>>___T; for(int __CS=1;__CS<=___T;__CS++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
mt19937 dlsrand(random_device{}());
mt19937 mrand(std::chrono::system_clock::now().time_since_epoch().count()); 
int rnd(int x) { return mrand() % x;}
LL bin(LL x, LL n, LL MOD) {LL ret = MOD != 1;for (x %= MOD; n; n >>= 1, x = x * x % MOD)if (n & 1) ret = ret * x % MOD;return ret;}
inline LL get_inv(LL x, LL p) { return bin(x, p - 2, p); }
const double PI = acos(-1.0);
constexpr int maxn = 1e6+10;
constexpr int INF = 0x3f3f3f3f;
constexpr ll linf = 0x3f3f3f3f3f3f3f3f;
constexpr int mod = 1e9+7;
void add(int &a,int b) {a+=b; if(a>=mod) a-=mod;}
void dec(int &a,int b) {a-=b; if(a<0) a+=mod;}
int k , n , a[maxn];
int main()
{
    close;
    cin >> k >> n;
    for(int i = 1; i<=n; i++){
        cin >> a[i];
    }
    int mx = a[1]+k-a[n];
    for(int i = 2; i <= n; i++){
        mx = max(mx,a[i]-a[i-1]);
    }
    cout << k - mx ;
    
    
}

Measured memory_bytes: 1152
for(r=".IVXLCDM",k=n=s=0,j=require("fs").readFileSync("/dev/stdin","utf8");p=n,i=j[k];k++)i=='\n'?(console.log(s),n=s=0):s+=(n=Math.pow(10,~~((n=r.indexOf(i))/2))/(2-(n%2))),n>p?s-=p*2:0

Measured memory_bytes: 8696
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>

using namespace std;

int gcd(int a, int b) {
    if (a < b) {
        int t = a;
        a = b;
        b = t;
    }
    int r = -1;
    while (r != 0) {
        r = a % b;
        a = b;
        b = r;
    }

    return a;    //b には r=0 の値が入るため、a を返す
}

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

    int A[N];
    int maxA = 1;
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        if (maxA < A[i])
            maxA = A[i];
    }

    if (maxA < K) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }

    for (int i = 0; i < N; ++i) {
        if (A[i] == K) {
            cout << "POSSIBLE" << endl;
            return 0;
        }
    }

    if (N == 1) {
        cout << "IMPOSSIBLE" << endl;
        return 0;
    }

    int gcda = gcd(A[0], A[1]);
    for (int i = 2; i < N; ++i) {
        gcda = gcd(gcda, A[i]);
    }

    if (K % gcda == 0) {
        cout << "POSSIBLE" << endl;
    } else {
        cout << "IMPOSSIBLE" << endl;
    }

}

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

#define FOR(a, b, c) for(int a = b; a <= c; ++a)
#define FORW(a, b, c) for(int a = b; a >= c; --a)
#define fi first
#define se second
#define pb push_back
//#define int long long

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 2e2 + 100;
const int oo = 1e8;
const int mod = 1e9 + 7;

int n, m;
int dp[N][N];
bool visit[N][N], color[N][N];

void upd(int &x, int y) { x = min(x, y); }
void solve(int x0, int y0, int x, int y, int id)    {
    visit[x][y] = 1;
    upd(dp[x0][y0], dp[x - 1][y] + id);
    upd(dp[x0][y0], dp[x][y - 1] + id);
    if(x > 1 && color[x - 1][y] == id && !visit[x - 1][y]) solve(x0, y0, x - 1, y, id);
    if(y > 1 && color[x][y - 1] == id && !visit[x][y - 1]) solve(x0, y0, x, y - 1, id);
    //visit[x][y] = 0;
}

signed main()  {
//    freopen("test.inp", "r", stdin);
//    freopen("test.out", "w", stdout);
    //ios_base::sync_with_stdio(false); cout.tie(0);
    scanf("%d%d", &n, &m);
    FOR(i, 1, n)    FOR(j, 1, m)    {
        char x; scanf(" %c", &x);
        if(x == '#') color[i][j] = 1;
    }
    FOR(i, 0, n) FOR(j, 0, m) dp[i][j] = oo;
    dp[0][1] = dp[1][0] = 0;
    FOR(i, 1, n) FOR(j, 1, m)   {
        solve(i, j, i, j, color[i][j]);
        FOR(i1, 1, i) FOR(j1, 1, j) visit[i1][j1] = 0;
        //cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
    }
    printf("%d", dp[n][m]);
}


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

int main(){
  long long n, a, b, c, d, e;
  cin >> n >> a >> b >> c >> d >> e;
  
  long long minMove = min({a, b, c, d, e});
  long long ans = ((n+minMove-1)/minMove)+4;
  
  cout << ans << endl;
}

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

using lint = long long;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<int> tree(n<<1);
    for (int i = 0; i < n; ++i) {
    	char c;
    	cin >> c;
    	tree[i+n] = 1 << (c - 'a');
    }
    for (int i = n-1; i; --i) 
    	tree[i] = tree[i<<1] | tree[i<<1|1];
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
    	int op;
    	cin >> op;
    	if (op == 1) {
    		int pos; char c;
    		cin >> pos >> c;
    		--pos;
    		tree[pos+n] = 1 << (c - 'a');
    		for (int j = (pos+n)/2; j; j >>= 1)
    			tree[j] = tree[j<<1] | tree[j<<1|1];
    	}
    	else {
    		int l, r;
    		cin >> l >> r;
    		--l, --r;
    		int result = 0;
    		for (l += n-1, r += n+1; l^r^1; l >>= 1, r >>= 1) {
    			if (~l&1) result |= tree[l^1];
    			if (r&1) result |= tree[r^1];
    		}
    		cout << __builtin_popcount(result) << '\n';
    	}
    }
}

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

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

	while (A > 0) {
		A -= D;
		C -= B;
		if (C <= 0) {
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;
}

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;

int main() {
  ll N, M;
  cin >> N >> M;
  vector<vector<ll>> vv(M, vector<ll>(2));
  vector<ll> v(N);
  for(ll i = 0LL; i < N; i++) {
    cin >> v.at(i);
  }
  ll cnt = 0;
  for(ll i = 0; i < M; i++) {
    cin >> vv.at(i).at(1) >> vv.at(i).at(0);
  }
  vector<ll> va;
  sort(vv.begin(), vv.end());
  reverse(vv.begin(), vv.end());
  sort(v.begin(), v.end());
  for(ll i = 0; i < M; i++) {
    for(ll j = 0; j < vv.at(i).at(1); j++) {
      va.push_back(vv.at(i).at(0));
      if (va.size() >= N) break;
    }
  }
  ll i = 0LL;
  while(i < N && i < va.size() && va.at(i)>v.at(i)) {
    v.at(i) = va.at(i);
    i++;
  }
  ll ans = 0LL;
  for(ll j = 0; j < N; j++) {
    ans += v.at(j);
  }
  cout << ans << endl;
}


Measured memory_bytes: 8692
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <list>
#include <ctime>
#include <sstream>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <cassert>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define FOR(x, b, e) for(int x=(b); x<=(e); ++x)
#define FORD(x, b, e) for(int x=((int)(b))-1; x>=(e); --x)
#define REP(x, n) for(int x=0; x<(n); ++x)
#define ALL(c) c.begin(),c.end()
#define sz(x) ((int)((x).size()))
#define pb push_back
#define st first
#define nd second
#define mp(x,y) make_pair(x,y)
typedef short int sint;

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it) {
	*this << ((it != d.b) ? ", " : "") << *it;
  }
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

int main() {
	ios_base::sync_with_stdio(false);

	int n,m;
	cin >> n >> m;
	int sum = 0;
	REP(i, m) {
		int x;
		cin >> x;
		sum += x;
	}
	if (sum > n) {
		cout << -1 << endl;
	} else {
		cout << n - sum << endl;
	}
}

Measured memory_bytes: 3656
N, X = map(int, input().split())

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン(ただしレベル0バーガー参照時には+1)
        return 0 + (n == 0)

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ
    elif x == 2 + thick[n - 1]:
        return patti[n - 1] + 1

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    elif 2 + thick[n - 1] < x <= 2 * thick[n - 1] + 2:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガー + 最後のバン
    elif x == 2 * thick[n - 1] + 3:
        return 2 * patti[n - 1] + 1


print(solve(N, X))


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
typedef vector<vec> mat;
const int MAX_N=200000;
int bit[MAX_N+1]={0},n;
int sum(int i){
    int s=0;
    while(i>0){
        s+=bit[i];
        i-=i&-i;
    }
    return s;
}
void add(int i,int x){
    while(i<=n){
        bit[i]+=x;
        i+=i&-i;
    }
}
int search(int k){
    ll ok=200000,ng=-1;
    while(abs(ok-ng)>1){
        ll mid=(ok+ng)/2;
        if(sum(mid)>=k) ok=mid;
        else ng=mid;
    }
    return ok;
}
int main(){
    int q,Q[200001][3];
    cin>>q;
    n=MAX_N;
    vector<P> A;
    vec B(200001,-1),C(200001);
    rep(i,q){
        int c,a,b;
        cin>>c;
        Q[i][0]=c;
        if(c==1) cin>>a>>b,Q[i][1]=a,Q[i][2]=b,A.push_back(P(a,i));
    }
    sort(all(A));
    rep(i,A.size()) B[A[i].second]=i+1;
    rep(i,B.size()) if(B[i]!=-1) C[B[i]]=i;
    ll ans=0,x,c=0;
    rep(i,q){
        if(Q[i][0]==1){
            c++;
            if(c==1) ;
            else if(c%2==0) ans+=abs(Q[i][1]-Q[C[search(c/2)]][1]);
            else{
                int a=Q[C[search(c/2)]][1],b=Q[C[search(c/2+1)]][1];
                if(Q[i][1]<a) ans+=abs(Q[i][1]-a);
                if(b<Q[i][1]) ans+=abs(Q[i][1]-b);
            }
            add(B[i],1);
            x=Q[C[search((c+1)/2)]][1];
            ans+=Q[i][2];
        }
        else{
            cout<<x<<" "<<ans<<"\n";
        }
    }
}

Measured memory_bytes: 10480
import std.stdio, std.algorithm, std.conv, std.array, std.string;

void main()
{
    auto nab = readln.split.to!(long[]);
    auto n = nab[0];
    auto a = nab[1];
    auto b = nab[2];

    auto hs = new long[n];
    foreach (i; 0..n) {
        hs[i] = readln.chomp.to!long;
    }

    auto d = a - b;

    bool check(long n) {
        auto nn = n;
        foreach (h; hs) {
            h -= b * n;
            if (h <= 0) {
                continue;
            } else if (h <= d * nn) {
                nn -= (h + d - 1) / d;
            } else {
                return false;
            }
        }
        return true;
    }

    auto min = 0;
    auto max = 10^^9;
    while (min + 1 != max) {
        auto piv = (min + max) / 2;
        if (check(piv)) {
            max = piv;
        } else {
            min = piv;
        }
    }
    writeln(max);
}

Measured memory_bytes: 3708
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr long long MOD = 1000000000 + 7;
constexpr long long INF = 100000000000000;
const double PI = acos(-1);

string s = "RYGB";

int main() {
	int h, w, d;
	cin >> h >> w >> d;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			int x = i - j;
			int y = i + j;
			cout << s[(y + 114514 * d) % (2 * d) / d * 2 + (x + 114514 * d) % (2 * d) / d];
		}
		cout << endl;
	}
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define fi first
#define se second
#define vll vector<ll>
#define pii pair<ll,ll>
#define vvll vector< vector<ll> >
#define pb push_back
#define sz(v) (ll)(v).size()
#define inf 1e18
#define md 1000000007
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define tel(a){cout<<a<<"\n";}
#define tell(a,b){cout<<a<<" | "<<b<<"\n";}
#define telll(a,b,c){cout<<a<<" | "<<b<<" | "<<c<<"\n";}
#define teln(v,n){cout<<"v- ";rep(o,0,n)cout<<v[o]<<" ";cout<<"\n";}
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define M 300010
ll ex(ll a,ll b,ll c){ll ans=1;while(b){if(b&1)ans=(ans*a)%c;a=(a*a)%c,b/=2;}return ans;}

// ll dp[M];
ll f(ll n){
	if(!n)return 0;
	// if(dp[n]!=-1)return dp[n];
	ll x=__builtin_popcount(n);
	return 1+f(n%x);
}
int main(){
    IOS;
     
    // memset(dp,-1,sizeof(dp));
 	ll n;cin>>n;
    string s;
    cin>>s;
    ll cnt=0;
    rep(i,0,n)if(s[i]=='1')cnt++;
    ll t[2]={0},temp;
    rep(i,0,n){
    	if(s[i]!='1')continue;
    	if(cnt>1)t[0]+=ex(2,n-1-i,cnt-1);
    	t[1]+=ex(2,n-1-i,cnt+1);
    } 
    rep(i,0,n){
    	if(s[i]=='1'){
    		if(cnt==1){cout<<"0\n";continue;}
    		temp=t[0]-ex(2,n-1-i,cnt-1),(temp+=(cnt-1))%=(cnt-1);
    		cout<<f(temp)+1<<"\n";
    	}
    	else {
    		temp=t[1]+ex(2,n-1-i,cnt+1),(temp)%=(cnt+1);
    		cout<<f(temp)+1<<"\n";
    	}
    }
    return 0;
}


Measured memory_bytes: 3764
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	public static boolean possible(List<Integer> w, int n, int k, int P) {
		int current = 0;
		k--; // ???????????£???????????????????????°
		for (int c : w) {
			if (current + c > P) {
				if (k > 0) {
					k--;
					if (c <= P)
						current = c;
					else 
						return false; 
				} else {
					return false;
				}
			} else {
				current += c;
			}
		}
		return true;
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader br = new BufferedReader(new FileReader("in1.txt"));
		// BufferedReader br = new BufferedReader(new FileReader("in2.txt"));
		String[] line = br.readLine().split(" ");
		int n = Integer.parseInt(line[0]);
		int k = Integer.parseInt(line[1]);
		List<Integer> w = new ArrayList<Integer>();
		for (int i = 0; i < n; i++)
			w.add(Integer.parseInt(br.readLine()));
		
		// O(kn^2)?????¢?????´??????????????????????????????...????????????(?????¶)
		// ????????????????????????O(kn)?????????????§£?????????????????????????????????...
		// List<List<Integer>> P = new ArrayList<List<Integer>>();
		// List<Integer> P0 = new ArrayList<Integer>();
		// P0.add(w.get(0));
		// for (int j = 1; j < n; j++)
		// 	P0.add(P0.get(j - 1) + w.get(j));
		// P.add(P0);
		// for (int i = 1; i < k; i++) {
		// 	List<Integer> Pk = new ArrayList<Integer>();
		// 	for (int j = 0; j < n; j++) {
		// 		int min = P.get(i - 1).get(j);
		// 		int sum = 0;
		// 		for (int l = 0; l < j; l++) {  // j??????????????????????????????l+1???????????????
		// 			sum += w.get(j - l);
		// 			if (min < sum)
		// 				break;
		// 			min = Math.max(P.get(i - 1).get(j - l - 1), sum);
		// 		}
		// 		Pk.add(min);
		// 	}
		// 	P.add(Pk);
		// }
		// System.out.println(P.get(k - 1).get(n - 1));
		
		// ??????P????????????????????????????????????????????????????????????????????¨???????°????
		// ???????????¨??????2?????¢?´¢??§?????£?????????O(nlnP)??§???????????????
		// System.out.println(possible(w, n, k, 6));
		// l????????????u???????????????
		int u = 1000000000, l = 1;
		int sum = 0;
		for (int c : w)
			sum += c;
		u = sum + 1; l = sum / w.size();
		while (u - l > 1) {
			int mid = (u + l) / 2 - 1;
			if (possible(w, n, k, mid))
				u = mid + 1;
			else
				l = mid + 1;
		}
		System.out.println(l);
	}
}

Measured memory_bytes: 31340
N,R=input().split()
N=int(N)
R=int(R)
if (R>4111)or(R<0):
  None
if 1<=N<=9:
  R_internal=R+100*(10-N)
  print(R_internal)
elif N>=10:
  R_internal=R
  print(R_internal)
else:
  None

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
#define pii pair<int, int>
#define int int64_t
#define re(s) reverse((s).begin(), (s).end())
#define setout(n, x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10);
const long long mod = 1e9 + 7;

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

   int n, cnt = 0, ans = 0;
   string s[10010], v;
   cin >> n;
   vector<int> x(n);

   rep(i, n)
   {
      cin >> s[i];
      cin >> x[i];
   }

   cin >> v;
   bool a = false;

   rep(i, n)
   {
      if (a)
         cnt += x[i];
      if (s[i] == v)
         a = true;
   }

   cout << cnt << '\n';
}

Measured memory_bytes: 384
#include<iostream>
#include<stdio.h>
#include<vector>
#include<ctype.h>
#include<string>
#include<cmath>
#include<string.h>
#include<sstream>
#include<limits.h>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long int ll;
typedef vector<int> vi;

//最大公約数
int gcd(int a,int b){
    return b ? gcd(b,a%b):a;
}

//最小公倍数
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

//素数判定
bool isPrime(int x){
    if(x<2)return 0;
    else if(x==2)return 1;
    if(x%2==0)return 0;
    for(int i=3;i*i<=x;i+=2){
        if(x%i==0)return 0;
    }
    return 1;
}

//桁ごとの足し算
int digsum(int n){
    int res=0;
    while(n>0){
        res+=n%10;
        n/=10;
    }
    return res;
}

//約数列挙
vector<int> enum_div(int n){
    vector<int> ret;
    for(int i=1;i*i<=n;++i){
        if(n%i==0){
            ret.push_back(i);
            if(i*i !=n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}

//累乗の計算とあまり,0で累乗そのまま出力
long long modpow(long long a,long long n,long long mod){
    if(mod==0)mod=__LONG_LONG_MAX__;
    long long res=1;
    while(n>0){
        if(n & 1)res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}

int N,X,T;
int main(){
    cin>>N>>X>>T;
    int ans=N/X*T;
    if(N%X!=0)ans+=T;
    cout<<ans<<endl;
}

Measured memory_bytes: 3624
w = gets.chomp.split(' ').map(&:to_i)
puts (w.reduce(0) {|memo, item| item == 5 ? memo + 1 : memo }) == 2 && (w.reduce(0) {|memo, item| item == 7 ? memo + 1 : memo }) == 1 ? "YES" : "NO"

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

using namespace std;

int main() {
    int K, S;
    int count = 0;

    cin >> K >> S;

    for (int x = 0; x <= K; x++) {
        for (int y = 0; y <= K; y++) {
            int z = S-x-y;
            if (z >= 0 && z <= K) count++;
        }
    }
    cout << count << endl;

    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
int N;    
    cin>>N;
char S[N+1];
char T[N+1];
       for(int i=0;i<N;i++){
           cin>>S[i];}
    cout<<endl;
       for(int i=0;i<N;i++){
           cin>>T[i];}
       for(int i=0;i<N;i++){
           cout<<S[i]<<T[i];}
    return 0;}
              
        

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define fn for(int i =0 ;i <n;i++)
#define fn1 for( int i =1;i<=n;i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define E endl
#define MOD 1000000007
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
const int N = 1e6+5;
const int INF = 1e18L;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}
int ar[N];
int dp[N];
signed main(){
	// #ifndef ONLINE_JUDGE
 // 	freopen("input.txt","r",stdin);
 // 	freopen("output.txt","w",stdout);
	// #endif
	IOS;
	int T=1;
	// cin >> T;
	while(T--){
		int n,m;
		cin >> n >> m ;
		cout << (n==m  ? "Yes ":"No");
	
	
	}
	cerr << "Time Taken : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std; 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define pp(...) "\033[94m [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define dg1(x) debug() << pp(x)
#define dg2(x,y) debug() << pp(x) pp(y)
#define dg3(x,y,z) debug() << pp(x) pp(y) pp(z)
#define dg4(w,x,y,z) debug() << pp(w) pp(x) pp(y) pp(z)
#define msg(x) debug() << x
#define int long long

signed main(){
  int n , m ;
  cin >> n >> m;
  string s;
  cin >> s;
  vector<int>pos;
  reverse(s.begin() , s.end());
  for(int i=0;i<=n;i++){
    if(s[i]=='0'){
      pos.push_back(i);
    }
  }
  pos.push_back(pos[pos.size()-1] + 1e5);
  vector<int>ans;
  int pre = pos[0];
  for(int i=1;i<pos.size();i++){
    int d = pos[i] - pre;
    if(d > m){
      int now = pos[i-1];
      if(pre == now){
        cout << -1 << '\n';
        return 0;
      }
      if(now - pre > m){
        cout << -1 << '\n';
        return 0;
      }
      ans.push_back(now - pre);
      pre = now;
    }
  }
  reverse(ans.begin() , ans.end());

  for(int i : ans) cout << i <<" ";cout << '\n';

}

Measured memory_bytes: 2676
#include <bits/stdc++.h>
#include <boost/range/algorithm.hpp>
#include <boost/range/numeric.hpp>
#include <boost/range/irange.hpp>
#include <boost/range/adaptor/indexed.hpp>

using namespace std;
using namespace boost::adaptors;
using namespace std::string_literals;
using ll = int64_t;
using vecint = vector<int>;
using vecll = vector<ll>;
using boost::irange;

constexpr ll MOD = 1000000007;

tuple<ll, ll> dfs(const vector<vecint>& g, int i, int p = -1) {
  ll a = 1, b = 1;
  for (auto&& to: g[i]) {
    if (to == p) continue;
    ll p, q;
    tie(p, q) = dfs(g, to, i);
    a *= (p + q);
    a %= MOD;
    b *= p;
    b %= MOD;
  }
  return make_tuple(a, b);
}

int main()
{
  ll n;
  cin>>n;
  vector<vecint> g(n);
  for(auto&& i:irange(0l,n-1)) {
    int x,y;
    cin>>x>>y;
    --x;--y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  ll a, b;
  tie(a, b) = dfs(g, 0);
  cout<<(a+b)%MOD<<endl;
  return 0;
}


Measured memory_bytes: 15488
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = ll(1e18)+5;


void solve(long long N, long long K, std::vector<long long> A, std::vector<long long> F){
    sort(A.begin(),A.end());
    sort(F.rbegin(),F.rend());
    ll l=-1;
    ll r = INF;
    while(l+1<r){
        ll mid = (l+r)/2;
        ll sum =0;
        for(int i=0;i<N;i++){
            sum += max(0ll, A[i]-(mid/F[i]));
        }
        if(sum>K){
            l  =mid;
        }else{
            r = mid;
        }
    }
    cout << r << endl;


}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;
    scanf("%lld",&N);
    long long K;
    scanf("%lld",&K);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    std::vector<long long> F(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&F[i]);
    }
    solve(N, K, std::move(A), std::move(F));
    return 0;
}


Measured memory_bytes: 6408
use std::io;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let iter = buf.split_whitespace();
	let mut v: Vec<T> = Vec::new();
	for i in iter {
		v.push(i.parse().ok().unwrap());
	}
	v
}

fn main() {
	let r:f64 = procon_read()[0];
	println!("{}", 2.0*r*std::f64::consts::PI);
}

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

typedef long long ll;

struct Box {
	ll str;
	ll w;
};

ll dp[5001][5001];

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

	int n; cin >> n;
	vector<Box> v(n + 1);
	for (int i = 1; i <= n; ++i) {
		cin >> v[i].str >> v[i].w;
	}

	sort(v.begin() + 1, v.end(), [] (const Box& a, const Box& b) {
		return a.str + a.w < b.str + b.w;
	});

	for (int i = 0; i < 1001; ++i)
		for (int j = 0; j < 1001; ++j)
			dp[i][j] = -1;

	dp[1][1] = v[1].w;
	for (int pref = 2; pref <= n; ++pref) {
		dp[pref][1] = min(v[pref].w, dp[pref-1][1]);
	}
	for (int pref = 2; pref <= n; ++pref) {
		if (dp[pref-1][pref-1] == -1) {
			dp[pref][pref] = -1;
		} else if (v[pref].str >= dp[pref-1][pref-1]) {
			dp[pref][pref] = dp[pref-1][pref-1] + v[pref].w;
		} else {
			dp[pref][pref] = -1;
		}
	}

	for (int pref = 3; pref <= n; ++pref) {
		for (int used = 2; used < pref; ++used) {
			if (dp[pref-1][used] == -1) {
				if (dp[pref-1][used-1] == -1) {
					dp[pref][used] = -1;
				} else if (dp[pref-1][used-1] <= v[pref].str) {
					dp[pref][used] = v[pref].w + dp[pref-1][used-1];
				} else {
					dp[pref][used] = -1;
				}
			} else {
				dp[pref][used] = dp[pref-1][used];
				if (dp[pref-1][used-1] <= v[pref].str) {
					dp[pref][used] = min(dp[pref][used], v[pref].w + dp[pref-1][used-1]);
				}
			}
		}
	}

	int ans;
	for (int used = n; used >= 1; --used) {
		for (int pref = n; pref >= used; --pref) {
			if (dp[pref][used] != -1) {
				ans = used;
				goto end;
			}
		}
	}
end:
	cout << ans << '\n';
}


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

#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define MOD 1000000007

const int MAX_M = 100000;


int main(){
  ll n;
  //string s;
  cin >> n;
  
  vector<ll> a(n-1);
  rep(i,0,n-1){
    cin >> a.at(i);
  }
  
  map<ll,ll> d{};
  rep(i,0,n-1){
    d[a.at(i)]++;
  }
  
  rep(i,0,n){
    cout << d[i+1] << endl;
  }
}

Measured memory_bytes: 17196
<?php

class Scanner
{
    private $arr = [];
    private $count = 0;
    private $pointer = 0;

    public function next()
    {
        if ($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        ++$this->pointer;

        return $result;
    }

    public function hasNext()
    {
        return $this->pointer < $this->count;
    }

    public function nextInt()
    {
        return (int) $this->next();
    }

    public function nextDouble()
    {
        return (float) $this->next();
    }
}

$sc = new Scanner();
$a = $sc->nextInt();
$b = $sc->nextInt();
$eight_percent_tax = [];
$ten_percent_tax = [];
$min_gross_price_for_eight = 10000;
$max_gross_price_for_eight = 0;
$min_gross_price_for_ten = 10000;
$max_gross_price_for_ten = 0;

for($i=1;$i<1251;$i++){
    $eight_percent_tax[] = floor($i * 0.08);
    if(floor($i*0.08) == $a){
        if($min_gross_price_for_eight == 10000){
            $min_gross_price_for_eight = $i;
            $max_gross_price_for_eight = $i;
        } else {
            $max_gross_price_for_eight = $i;
        }
    }
}

for($i=1;$i<1001;$i++){
    $ten_percent_tax[] = floor($i * 0.10);
    if(floor($i*0.10) == $b){
        if($min_gross_price_for_ten == 10000){
            $min_gross_price_for_ten = $i;
            $max_gross_price_for_ten = $i;
        } else {
            $max_gross_price_for_ten = $i;
        }
    }

}

if(($min_gross_price_for_eight == 10000) || ($min_gross_price_for_ten == 10000) || ($min_gross_price_for_eight > $max_gross_price_for_ten) || ($min_gross_price_for_ten > $max_gross_price_for_eight)){
    echo "-1".PHP_EOL;
} else {
    //重なっている場合はどちらかのminの値が採用となる
    if($min_gross_price_for_ten == $min_gross_price_for_eight){
        echo $min_gross_price_for_ten.PHP_EOL;
    } else {
        if($min_gross_price_for_ten < $min_gross_price_for_eight){
            echo $min_gross_price_for_eight.PHP_EOL;
        } else {
            echo $min_gross_price_for_ten.PHP_EOL;
        }
    }
}


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

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

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

int main(){
  // 入力
  long long N, K;
  cin >> N >> K;

  if(N <= K){
    cout << 0 << endl;
    return 0;
  }

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

  sort(enemies.begin(), enemies.end());
  //HPの高いやつから殺していく
  for(int i = 0; i < K; i++){
    enemies.pop_back();
  }
  auto sum = accumulate(enemies.begin(), enemies.end(), 0LL);

  cout << sum << endl;
}



Measured memory_bytes: 1792
//Written by Zhu Zeqi
//Come on,baby
//Hack,please
#include <iostream> 
#include <cstdio> 
#include <fstream> 
#include <algorithm> 
#include <cmath> 
#include <deque> 
#include <vector> 
#include <queue> 
#include <string> 
#include <cstring> 
#include <map> 
#include <stack> 
#include <set> 
#define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
//orz yht
using namespace std;
int n;
vector<pair<ll,int> >v;
map<ll,int>mp;
vector<pair<int,int> > ans;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++){
    	ll x;
    	cin>>x;
    	mp[x]=i;
    	v.push_back(make_pair(x,i));
	}
	sort(v.rbegin(),v.rend());
	vector<int>sz(n,1);
	vector<ll>dp(n,0);
	for(auto x : v){
		if(x.first!=v.back().first){
			if(sz[x.second]*2>=n){
				cout<<-1;
				
				return 0;
			}
			ll need=x.first-(n-2*sz[x.second]);
			if(!mp.count(need)){
				cout<<-1;
				return 0;
			}
			ll par=mp[need];
			dp[par]+=dp[x.second]+sz[x.second];
			sz[par]+=sz[x.second];
			ans.push_back(make_pair(x.second+1,par+1));
		}
	}
	if(dp[v.back().second]!=v.back().first){
		cout<<-1;
		return 0;
	}
	for(auto x : ans)
	cout<<x.first<<" "<<x.second<<endl;
	return 0;
}

Measured memory_bytes: 12144
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>


using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
template <class T> int __builtin_popcount(T n) { return n ? 1 + __builtin_popcount(n & (n - 1)) : 0; }
#endif

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define CL(arr, val) memset(arr, val, sizeof(arr))

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

template <class T> void max_swap(T& a, const T& b) { a = max(a, b); }
template <class T> void min_swap(T& a, const T& b) { a = min(a, b); }

typedef long long ll;
typedef pair<int, int> pint;

const double EPS = 1e-8;
const double PI = acos(-1.0);
const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };
bool valid_pos(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }



int n;
int x[32], y[32], r[32], c[32];
int on_mask[32];
char dp[1 << 24];
int recur(int remain)
{
	if (dp[remain] != -1)
		return dp[remain];

	int res = 0;
	for (int i = 0; i < n; ++i)
		if (remain >> i & 1 && (on_mask[i] & remain) == 0)
			for (int j = i + 1; j < n; ++j)
				if (remain >> j & 1 && c[j] == c[i] && (on_mask[j] & remain) == 0)
					max_swap(res, recur(remain ^ (1 << i | 1 << j)) + 2);

	return dp[remain] = res;					
}
bool on(int i, int j)
{
	int dx = x[i] - x[j], dy = y[i] - y[j];
	int d = r[i] + r[j];
	return dx * dx + dy * dy < d * d;
}
int main()
{
	ios::sync_with_stdio(false);

	while (cin >> n, n)
	{
		rep (i, n)
			cin >> x[i] >> y[i] >> r[i] >> c[i];

		CL(on_mask, 0);
		for (int j = 0; j < n; ++j)
			for (int i = 0; i < j; ++i)
				if (on(i, j))
					on_mask[j] |= 1 << i;

		CL(dp, -1);
		cout << recur((1 << n) - 1) << endl;
	}
}

Measured memory_bytes: 16000
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <map>
#include <numeric>
#include <functional>
#include <math.h>

using namespace std;

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

#define INF ((int)1e9)
#define INFLL ((ll)1e18)
#define MOD (1000000007LL)


int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    int A, P;
    cin >> A >> P;
    cout << (3 * A + P) / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <utility>
 
int n;
std::unordered_map<int,int> one;
std::unordered_map<int,int> two;
int main()
{
  std::cin>>n;
  for(int i=0;i<n;++i){
    int temp;
    std::cin>>temp;
    if(i%2==0)
      ++one[temp];
    else
      ++two[temp];
  }
  
  std::vector<std::pair<int,int>> data;
  for(auto& tmp:one)
    data.emplace_back(tmp.second,tmp.first);
  std::sort(data.begin(),data.end(),std::greater<std::pair<int,int>>());
  int o1=data[0].first,o2=data[1].first,o1Num=data[0].second;
  
  data.clear();
  for(auto& tmp:two)
    data.emplace_back(tmp.second,tmp.first);
  std::sort(data.begin(),data.end(),std::greater<std::pair<int,int>>());
  int t1=data[0].first,t2=data[1].first,t1Num=data[0].second;
  
  if(o1Num!=t1Num)
    std::cout<<n-o1-t1<<std::endl;
  else
    std::cout<<std::min(n-o1-t2,n-o2-t1)<<std::endl;
  return 0;
}


Measured memory_bytes: 5144