akhauriyash/Code-Regression huggingface dataset:
//Acknowledgement:  Xiaoyu Han, for his "brute-force" proposal

#include <cstdio>
#include <algorithm>
#include <cstdlib>

using std::max;  using std::abs;
using std::min;

const int MAXN=105;

int N,cx,cy,ch=0,c_point,min_abs;                     //c_point: calculable point
int x[MAXN],y[MAXN],h[MAXN];

int main()
{
    scanf("%d",&N);
    for (int i=1;i<=N;++i)
        scanf("%d%d%d",&x[i],&y[i],&h[i]);
    for (cx=0;cx<=100&&ch<=0;++cx)
    {
        for (cy=0;cy<=100&&ch<=0;++cy)
        {
            min_abs=MAXN<<1;
            for (c_point=1;c_point<=N&&h[c_point]==0;++c_point);
            if (c_point==N+1)
            {
                for (int i=1;i<=N;++i)
                    min_abs=min(min_abs,abs(x[i]-cx)+abs(y[i]-cy));
                if (min_abs==1) ch=1;
            }
            else
            {
                ch=h[c_point]+abs(x[c_point]-cx)+abs(y[c_point]-cy);
                int i;
                for (i=1;i<=N&&h[i]==max(ch-abs(x[i]-cx)-abs(y[i]-cy),0);++i);
                if (i<=N) ch=0;
            }
        }
    }
    printf("%d %d %d",--cx,--cy,ch);

    return 0;
}


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

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

    int res;
    if (c <= a) {
        if (d <= a) res = 0;
        else if (b <= d) res = b - a;
        else res = d - a; 
    } else if (b <= c) res = 0;
    else {
        if (b <= d) res = b - c;
        else res = d - c;
    }

    cout << res << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

N, A, B = [int(i) for i in input().split()]

all_sum = 0
for i in range(1, N+1):

    i_sum =sum(list(map(int, str(i))))
    if A <= i_sum and i_sum <= B:
        all_sum += i
print (all_sum)


Measured memory_bytes: 3064
#include <iostream>


int main(void)
{
	using namespace std;
	int a,b;
	cin >> a;
	cin >> b;
	if(a < b)      cout << "a < b" << endl;
	else if(a > b) cout << "a > b" << endl;
	else	       cout << "a == b" << endl;

	return 0;

}

Measured memory_bytes: 3120
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            if L[i] != L[j] and L[j] != L[k]:
                if L[i] + L[j] > L[k]:
                    ans += 1
if N < 3:
    ans = 0
print(ans)

Measured memory_bytes: 9188
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;i++)
using namespace std;

int main(){
	string s;
	while(cin>>s){
	string buf="";
	rep(i,s.size()){
		if(s[i]=='@'){
			rep(j,s[i+1]-48)buf+=s[i+2];
			i+=2;
		}
		else buf+=s[i];
		
	}
	cout<<buf<<endl;
}
	return 0;
}

Measured memory_bytes: 3212
#データ入力
data = input()
data = data.split(" ")

n_large = int(data[0])
t_large = int(data[1])

data = input()
data = data.split(" ")
ts = []
for d in data:
    ts.append(int(d))

#計算
ts.sort()

total = ts[0]
for i in range(1, len(ts)):
    buf = ts[i] - ts[i - 1]
    if buf > t_large:
        total += t_large
    else:
        total += buf

total += t_large

print(total)

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define orep(i, n) for(int i = 1; i < (int)(n); ++i)
#define rrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;

int main() {
    int n;
    string s;
    cin >> n >> s;
    string ans = "Yes";
    rep(i, n / 2) {
        if (s[i] != s[n / 2 + i]) ans = "No";
    }

    if(n%2) ans = "No";
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_set>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef unordered_set<ll> uset;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=0;i<=n;i++)
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("unroll-loops")
#pragma gcc target("avx2,see4")
ll n;
void dfs(string s){
	if(s.size()==n){
		cout<<s<<endl;
		return;
	}
	char ma='a';
	rep(i,s.size())chmax(ma,s[i]);
	ma++;
	for(char z='a';z<=ma;z++){
		dfs(s+z);
	}
}
int main(){
	cin>>n;
	dfs("a");
}


Measured memory_bytes: 1536
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
	    String N = sc.next();
	    
	    if (N.contains("9")){
	    	System.out.println("Yes");
	    }else {
	    	System.out.println("No");
	    }
	}
}

Measured memory_bytes: 22740
package main

import (
	"fmt"
)

func main() {
	var r int
	var g int
	var b int
	fmt.Scan(&r)
	fmt.Scan(&g)
	fmt.Scan(&b)
	sum := 100*r + 10*g + b
	if sum%4 == 0 {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>

void run(void){
  int n,k;
  scanf("%d%d",&n,&k);
  int *dp=(int *)calloc(k+1,sizeof(int));
  int a[100];
  int i;
  for(i=0;i<n;i++) scanf("%d",a+i);
  for(i=1;i<=k;i++){
    int win=0;
    for(int j=0;j<n;j++){
      if(i-a[j]>=0 && dp[i-a[j]]==0){
	win=1;
      }
    }
    dp[i]=win;
  }
  puts(dp[k]?"First":"Second");
}

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

Measured memory_bytes: 512
N, x = map(int, input().split())

if x in [1, 2*N-1]:
  print('No')
else:
  print('Yes')
  if N == 2:
    print(*range(1, 4), sep='\n')
  else:
    ans = [0] * (2*N - 1)
    s = set(range(1, 2*N))
    if x >= N:
      ans[N-2] = x - 1; s.discard(x-1)
      ans[N-1] = x; s.discard(x)
      ans[N] = x + 1; s.discard(x+1)
      ans[N+1] = x - 2; s.discard(x-2)
    else:
      ans[N-2] = x + 1; s.discard(x+1)
      ans[N-1] = x; s.discard(x)
      ans[N] = x - 1; s.discard(x-1)
      ans[N+1] = x + 2; s.discard(x+2)
    for i in range(2*N-1):
      if ans[i]:
        continue
      ans[i] = s.pop()
    print(*ans, sep='\n')

Measured memory_bytes: 23856
from collections import deque

h,w = map(int, input().split())
n = int(input())
al = list(map(int, input().split()))

q = deque([])
for i,a in enumerate(al):
    c = i+1
    for j in range(a):
        q.append(c)

ans = [ [0]*w for _ in range(h)]
for hi in range(h):
    if hi%2 == 0:
        for wi in range(w):
            c = q.popleft()
            ans[hi][wi] = c
    else:
        for wi in range(w-1,-1,-1):
            c = q.popleft()
            ans[hi][wi] = c

    
for a in ans:
    print(*a)

Measured memory_bytes: 75080
#include <bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  if(n%2==1){
    cout<<"0\n";
    return 0;
  }
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
sort(a.begin(),a.end());
  cout<<a[n/2]-a[n/2-1]<<endl;
  return 0;
}

Measured memory_bytes: 3756
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <string>
#include <set>
#include <bitset>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <map>
#include <cstdlib>
#include <stack>
#include <chrono>
#include <random>

using namespace std;
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;
template <class T>
using Vvec = vector<vector<T> >;
using Graph = Vvec<int>;

template <class T>
void debug(T& v)
{
    for(auto& x: v) cout << x << " ";
    cout << endl;
}

ll calc(Vvec<ll>& s, vector<int>& c, int D, vector<int>& ans){
    vector<ll> l(26, -1);
    ll ret = 0;
    for(int i=0; i<D; i++){
        l[ans[i]] = i;
        ret += s[i][ans[i]];
        for(int j=0; j<26; j++) ret -= (ll)c[j] * (i-l[j]);
    }
    return ret;
}

int main()
{
    chrono::system_clock::time_point start, tmp;
    start = std::chrono::system_clock::now();

    int seed = 1;
    mt19937 mt(seed);

    int D;
    cin >> D;
    vector<int> c(26);
    Vvec<ll> s(D, vector<ll>(26));
    for(auto& x: c) cin >> x;
    for(auto& v: s){
        for(auto& x: v) cin >> x;
    }

    vector<int> l(26), ans(D);
    for(int i=0; i<D; i++){
        int m = 0;
        ll t = -1e18;
        for(int j=0; j<26; j++){
            ll t1 = s[i][j] + (ll)(D-i)*c[j]*(i-l[j]+1);
            // ll t1 = s[i][j];
            if(t < t1){
                m = j;
                t = t1;
            }
        }
        ans[i] = m;
        l[m] = i;
    }

    ll S = calc(s, c, D, ans);

    tmp = std::chrono::system_clock::now();
    double elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(tmp-start).count();
    uniform_int_distribution<> rnd(0, D-1);

    while(elapsed < 1500){
        int i = rnd(mt);
        int j = rnd(mt);
        if(i != j && abs(i-j) < (int)((1500-elapsed)/50) + 1){
            swap(ans[i], ans[j]);
            ll S1 = calc(s, c, D, ans);
            if(S < S1) S = S1;
            else swap(ans[i], ans[j]);
        }
        tmp = std::chrono::system_clock::now();
        elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(tmp-start).count();
    }

    for(auto& x: ans) cout << x+1 << "\n";
}

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

using namespace std;

int main() {
  vector<int> vs(3);
  cin >> vs[0] >> vs[1] >> vs[2];
  sort(vs.begin(), vs.end());
  if(vs[1] - vs[0] == vs[2] - vs[1]) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
}

Measured memory_bytes: 256
#include<string>
#include<iostream>
#include <algorithm>
#include<vector>
#include<functional>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <numeric>
#include <math.h>
#define ll long long
#define rep(i,n) for(ll i=0;i<(ll)n;i++)
using namespace std;



int main() {
    ll A, B, C, K, ans;
    cin >> A >> B >> C >> K;
    if (K <= A)ans = K;
    else if (K > A && K <= A + B) ans = A;
    else if (K > A + B && K <= A + B + C) ans = A - (K - (A + B));
    else if (K > A + B + C) ans = A - C;
    cout << ans << endl;
    return 0;

}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
//using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
int main(){
  int D; std::cin >> D;
  int c[26];
  int last[26]={};
  REP(i,26){
    std::cin >> c[i];
    last[i]=-1;
  }
  int s[D][26];
  REP(d,D){
    REP(j,26){
      std::cin >> s[d][j];
    }
  }
  int t[D];
  REP(d,D){
    std::cin >> t[d];
    t[d]--;
  }


  int v=0;
  REP(d,D){
    v+=s[d][t[d]];
    last[t[d]]=d;
    REP(i,26){
      v-=c[i]*(d-last[i]);
    }
    std::cout << v << '\n';
  }
	return 0;
}


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

using namespace std;
#define int long long
const int MOD = 1000000007;

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, K;
	cin >> N >> K;
	vector<int> A(N);
	int res = 0;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	int INF = (int)1 << 60;
	int u = INF;
	int d = -INF;
	while (u - d > 1) {
		int m = (u + d) / 2;
		int c = 0;
		for (int i = 0; i < N; i++) {
			if (A[i] * A[i] <= m) c--;
			if (A[i] < 0) {
				int mn = (m / A[i]) - 5;
				while (mn * A[i] > m) mn++;
				int pos = lower_bound(A.begin(), A.end(), mn) - A.begin();
				//cerr << m << " " << A[i] << " " << mn <<  " " << pos << endl;
				c += N - pos;
			} else if (A[i] > 0) {
				int mx = (m / A[i]) + 5;
				while (mx * A[i] > m) mx--;
				int pos = upper_bound(A.begin(), A.end(), mx) - A.begin();
				//cerr << m << " " << A[i] << " " << mx <<  " " << pos << endl;
				c += pos;
			} else {
				if (m >= 0) {
					c += N;
				}
			}
		}
		//cerr << m << " " << c << endl;
		c /= 2;
		if (c >= K) {
			u = m;
		} else {
			d = m;
		}
	}
	cout << u << endl;
}

Measured memory_bytes: 1792
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod
def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 in a:
            a[2] += 1
        else:
            a[2] = 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f in a:
                a[f] += 1
            else:
                a[f] = 1
            n //= f
        else:
            f += 2
    if n != 1:
        if n in a:
            a[n] += 1
        else:
            a[n] = 1
    return a
def main():
    N, M = map(int, input().split())
    d = prime_factorize(M)
    MOD = 10**9 + 7
    c = cmbs(MOD)
    r = 1
    for i in d:
        r *= c.cmb(N+d[i]-1, N-1)
    r %= MOD
    print(r)
main()


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

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

int N,M;

string S;
const int mod=1000000007;
int to[3333];
int sum[3333];

int dp[3333][3333];

signed main(){
    cin>>N>>M;
    cin>>S;
    rep(i,N)sum[i+1]=sum[i]+(S[i]=='1');
    rep(i,N)to[i+1]=i+1;
    rep(i,M){
        int l,r;
        cin>>l>>r;
        chmax(to[l],r);
    }
    for(int i=1;i<N;i++)chmax(to[i],to[i-1]);
    dp[0][0]=1;
    for(int i=0;i<N;i++){
        for(int j=max(i-(to[i]-sum[to[i]]),0ll);j<=min(i,sum[to[i]]);j++){
            if(to[i+1]-sum[to[i+1]]>=i-j+1)dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod;
            if(sum[to[i+1]]>=j+1)dp[i+1][j+1]=(dp[i+1][j+1]+dp[i][j])%mod;
        }
    }
    cout<<dp[N][sum[N]]<<endl;
    return 0;
}


Measured memory_bytes: 12928
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int N,M;cin>>N>>M;
    priority_queue<int> que;
    REP(i,N){
        int a;cin>>a;
        que.push(a);
    }
    REP(i,M){
        int d=que.top();
        d/=2;
        que.pop();
        que.push(d);
    }
    int ans=0;
    while(que.size()){
        ans+=que.top();
        que.pop();
    }
    cout<<ans<<endl;
}

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

using namespace std;

int main()
{
  int m, n;
  while(cin >> m >> n, m) {
    vector<bool> isbor(8000000, true);
    for(int i = m; i < 8000000; i++) {
      if(!isbor[i]) continue;
      if(n-- == 0) {
	cout << i << endl;
	break;
      }
      for(int j = i+i; j < 8000000; j+=i) isbor[j] = false;
    }
  }
  return 0;
}

Measured memory_bytes: 4048
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 1000000000000000000;

struct Edge {int to; ll cost;};

int main() {
    int N_, M;
    cin >> N_ >> M;
    int N = 1;
    while (N < N_) N <<= 1;
    vector<vector<Edge>> G(5 * N - 2 + 2 * M);
    for (int i = 0; i < N - 1; ++i) {
        G[i].push_back(Edge{2 * i + 1, 0});
        G[i].push_back(Edge{2 * i + 2, 0});
    }
    for (int i = N - 1; i < 2 * N - 1; ++i) {
        G[i].push_back(Edge{i + 3 * N - 1, 0});
    }
    for (int i = 2 * N - 1; i < 3 * N - 2; ++i) {
        G[2 * i - 2 * N + 2].push_back(Edge{i, 0});
        G[2 * i - 2 * N + 3].push_back(Edge{i, 0});
    }
    for (int i = 3 * N - 2; i < 4 * N - 2; ++i) {
        G[i + N].push_back(Edge{i, 0});
    }
    rep(i, M) {
        int L, R;
        ll C;
        cin >> L >> R >> C;
        --L;
        vector<int> S;
        L += N - 1;
        R += N - 1;
        while (R - L) {
            if (!(L & 1)) {
                S.push_back(L);
                ++L;
            }
            if (!(R & 1)) {
                --R;
                S.push_back(R);
            }
            L = (L - 1) >> 1;
            R = (R - 1) >> 1;
        }
        for (int x : S) {
            G[x + 2 * N - 1].push_back(Edge{5 * N - 2 + i * 2, 0});
            G[5 * N - 1 + i * 2].push_back(Edge{x, 0});
        }
        G[5 * N - 2 + i * 2].push_back(Edge{5 * N - 1 + i * 2, C});
    }
    vector<ll> dist(5 * N - 2 + 2 * M, INF);
    vector<int> used(5 * N - 2 + 2 * M, 0);
    priority_queue<pair<ll, int>> pq;
    dist[4 * N - 2] = 0;
    pq.push(pair<ll, int>{0, 4 * N - 2});
    while (!pq.empty()) {
        int v = pq.top().second;
        pq.pop();
        for (auto e : G[v]) {
            ll alt = dist[v] + e.cost;
            if (alt < dist[e.to]) {
                dist[e.to] = alt;
                pq.push(pair<ll, int>{-alt, e.to});
            }
        }
        used[v] = 1;
    }
    if (dist[4 * N + N_ - 3] == INF) cout << -1 << "\n";
    else cout << dist[4 * N + N_ - 3] << "\n";
    return 0;
}


Measured memory_bytes: 119932
#include "bits/stdc++.h"
#include <set>

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()
#define int long long
#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second
#define mod 1000000007
#define INF 10e10
template <typename T>

void print(T x)
{
	std::cout << x << " ";
}
template <typename T>

void println(T x)
{
	std::cout << x << "\n";
}

signed main(void) {
	int n;
	cin >> n;
	if (n == 1) {
		print("Hello World");
	}
	else {
		int a,b;
		cin >> a >> b;
		print(a + b);
	}
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

const int N = 5010;
const ll INF = 1e18;
ll dp[N][N];

int main() {
    int n;
    cin >> n;
    vector<PL> a(n);
    REP(i,n){
        cin >> a[i].first >> a[i].second;
        a[i].first += a[i].second;
    }
    sort(ALL(a));
    VL h(n), p(n);
    REP(i,n){
        h[i] = a[i].first - a[i].second;
        p[i] = a[i].second;

        // cout << h[i] << " " << p[i] << endl;
    }

    REP(i,n+1) REP(j,n+1) dp[i][j] = INF;

    dp[0][0] = 0;
    REP(i,n) REP(j,n){
        dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        if (dp[i][j] <= h[i]) dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j] + p[i]);
    }

    int ans = 0;
    REP(i,n+1) if (dp[n][i] < INF) ans = i;
    cout << ans << endl;


    return 0;
}





Measured memory_bytes: 196224
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
constexpr ll mod=1e9+7;

int main()
{
  int k,s,ans=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) ans++;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

#include <bits/stdc++.h>

#define F first
#define S second
#define _sz(x) (int)x.size()
#define pb push_back

#define error(x) cout << #x << " = " << x << endl

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

const int N = 1e5 + 20;
int n, m;
bool vis[N];
vector <int> g[N];

int x, y;

vector <int> v1, v2;

void dfs (int v, vector <int> &vec)
{
	vis[v] = 1;
	vec.pb(v);

	for (int u : g[v])
		if (!vis[u])
		{
			dfs(u, vec);
			return;
		}
}

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

	cin >> n >> m;
	for (int i = 0, u, v; i < m; i++)
	{
		cin >> u >> v;
		u--, v--;

		if (!i) x = u, y = v;

		g[u].pb(v);
		g[v].pb(u);
	}

	vis[x] = vis[y] = 1;

	dfs(x, v1);
	dfs(y, v2);

	reverse(v1.begin(), v1.end());

	cout << _sz(v1) + _sz(v2) << '\n';
	for (int x : v1) cout << x + 1 << ' ';
	for (int x : v2) cout << x + 1 << ' ';
	cout << '\n';
}


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

using namespace std;

int main()
{
	int n;
	cin >> n;
	int ans=0;
	vector<int> v(n);
	vector<int> c(n);
	for(int i=0;i<n;i++)
	{
		cin >> v[i];
	}
	for(int i=0;i<n;i++)
	{
		cin >> c[i];
	}

	for(int i=0;i<n;i++)
	{
		ans+=max(0,v[i]-c[i]);
	}
	cout << ans << endl;
}

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

int main(void){
	int64 D, L;
	cin >> D >> L;
	cout << D/L+D%L << endl;
}



Measured memory_bytes: 3096
function main(arg) {
    let [x,k,d]= arg.split(" ").map(Number)

    d *= x > 0 ? 1 : -1
    let t = parseInt(x/d)
    let a = x - t*d
    k = k - t
    if(t > k) {
        console.log(Math.abs(x-(k+t)*d))
    } else {
        console.log(k%2 ? Math.abs(a-d) : Math.abs(a))
    }
    
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 29564
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,s,n) for(int i = s; i < (int)(n); i++)

int main() {
  int k,t;
  cin >> k >> t;
  vector<int>a(t);
  rep(i,0,t) cin >> a[i];
  sort(a.begin(),a.end());
  if(a[t-1] <= (k+1)/2){
    cout << 0 << endl;
    return 0;
  }
  cout << (a[t-1]-(k+1)/2)*2-1 << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n, a[200005], fre[200005];
int main(int argc, char const *argv[])
{
	cin >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> a[i];
		fre[a[i]] ++;
	}
	long long ans = 0;
	for (int i = 1; i <= n; ++i)
	{
		ans = (ans + (fre[i] * (fre[i] - 1)) / 2);
	}
	for (int i = 1; i <= n; ++i)
	{
		cout << ans - fre[a[i]] + 1 << '\n';
	}
	return 0;
}

Measured memory_bytes: 4736
package main

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

func scanInt(scanner *bufio.Scanner) (i int) {
	if scanner.Scan() {
		bs := scanner.Bytes()
		for _, b := range bs {
			i = i*10 + int(b-'0')
		}
	}
	return
}

func copyMap(m map[int]int) map[int]int {
	m2 := make(map[int]int)
	for k, v := range m {
		m2[k] = v
	}
	return m2
}

// Note:
// dp[i][j] == dp[i*(a*n+1)+j]
func countWays(a, n int, x []int) int {
	rowSize := a*n+1
	dp := make([]map[int]int, rowSize*n)

	for i := 0; i < n; i++ {
		dp[i*rowSize] /* dp[i][0] */ = map[int]int{0: 1}
	}

	if x[0] < rowSize {
		dp[x[0]] /* dp[0][x[0]] */ = map[int]int{1: 1}
	}

	for i := 1; i < n; i++ {
		for j := 0; j < rowSize; j++ {
			dp[i*rowSize+j] /* dp[i][j] */ = copyMap(dp[(i-1)*rowSize+j] /* dp[i-1][j] */)
			if j < x[i] {
				continue
			}
			for k, v := range dp[(i-1)*rowSize+j-x[i]] /* dp[i-1][j-x[i]] */ {
				dp[i*rowSize+j][k+1] /* dp[i][j][k+1] */ += v
			}
		}
	}

	ways := 0
	for i := 1; i <= n; i++ {
		ways += dp[(n-1)*rowSize+a*i][i] /* dp[n-1][a*i][i] */
	}

	return ways
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	n := scanInt(scanner) // 1 <= n <= 50
	a := scanInt(scanner) // 1 <= a <= 50
	x := make([]int, n)
	for i := 0; i < n; i++ {
		x[i] = scanInt(scanner)
	}
	fmt.Println(countWays(a, n, x))
}


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

using namespace std;

int main() {
	int N;
	cin >> N;
	int x, y;
	x = N * 800;
	y = N / 15 * 200;
	cout << x - y << endl;
	return 0;
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9

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

  cout << (double)(a+b)*h/2 << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
typedef struct {
	int l, r;
} range;

int IniSize(int num) {
	// 要素数 num が収まるセグ木のサイズを返す
	int n = 1;
	while (n <= num)
		n <<= 1;
	return (n << 1) - 1;
}

void UpdateAdd(int pos, int n, vector<vector<int>>& d) {
	// 位置 pos(0-index) の値を n で更新する
	// セグ木のサイズは 2^n - 1
	int i = pos + (d.size() >> 1);
	d[i][n]++;
	while (i > 0) {
		i = (i - 1) >> 1;
		d[i][n]++;
	}
	return;
}

void UpdateSub(int pos, int n, vector<vector<int>>& d) {
	// 位置 pos(0-index) の値を n で更新する
	// セグ木のサイズは 2^n - 1
	int i = pos + (d.size() >> 1);
	d[i][n]--;
	while (i > 0) {
		i = (i - 1) >> 1;
		d[i][n]--;
	}
	return;
}

vector<int> Query(int pos, const range tag, range x, vector<vector<int>> &d) {
	if (tag.r <= x.l || x.r <= tag.l)
		return vector<int>(26, 0);
	if (tag.l <= x.l && x.r <= tag.r)
		return d[pos];
	int i;
	vector<int> a, b;
	a = Query((pos << 1) + 1, tag, { x.l, (x.l + x.r + 1) >> 1 }, d);
	b = Query((pos << 1) + 2, tag, { (x.l + x.r + 1) >> 1, x.r }, d);
	rep(i, a.size())
		a[i] += b[i];
	return a;
}

int main(void) {
	int num, i, j, m, n = 1, k, a, b, ans;
	string s, c;
	cin >> num >> s >> m;
	num = IniSize(num);
	vector<int> d;
	vector<vector<int>> st(num, vector<int>(26, 0));
	rep(i, s.size()) {
		UpdateAdd(i, s[i] - 'a', st);
	}
	rep(i, m) {
		cin >> k >> a;
		a--;
		if (k - 1) {
			cin >> b;
			d = Query(0, { a, b }, { 0, (num >> 1) + 1 }, st);
			ans = 0;
			rep(j, d.size()) {
				if (d[j])
					ans++;
			}
			cout << ans << "\n";
		}
		else {
			cin >> c;
			UpdateSub(a, s[a] - 'a', st);
			UpdateAdd(a, c[0] - 'a', st);
			s[a] = c[0];
		}
	}
	return 0;
}

Measured memory_bytes: 142084
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class Main {

	int N;
	int[] a;

	public void solve() {
		N = nextInt();
		a = new int[3 * N];
		for(int i = 0;i < 3 * N;i++){
			a[i] = nextInt();
		}

		long firstSum = 0;
		long secondSum = 0;
		PriorityQueue<Integer> minPq = new PriorityQueue<Integer>();
		PriorityQueue<Integer> maxPq = new PriorityQueue<Integer>((a,b) -> b-a);

		for(int i = 0;i < N;i++){
			minPq.add(a[i]);
			firstSum += a[i];
		}

		for(int i = 0;i < N;i++){
			maxPq.add(a[2*N+i]);
			secondSum += a[2*N+i];
		}

		long ans = Long.MIN_VALUE;

		long[] firstSums = new long[N+1];
		long[] secondSums = new long[N+1];

		firstSums[0] = firstSum;
		secondSums[N] = secondSum;

		for(int i = 0;i < N;i++){
			minPq.add(a[N+i]);
			firstSum -= minPq.poll();
			firstSum += a[N+i];

			firstSums[i+1] = firstSum;
		}

		for(int i = 0;i < N;i++){
			maxPq.add(a[3*N-N-1-i]);
			secondSum -= maxPq.poll();
			secondSum += a[3*N-N-1-i];

			secondSums[N-i-1] = secondSum;
		}

		for(int i = 0;i <= N;i++){
			ans = Math.max(ans,firstSums[i]-secondSums[i]);
		}

		out.println(ans);
	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

Measured memory_bytes: 51144
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<functional>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

const double EPS = 1e-5;

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;

vector<vector<int>> G;
vector<int> h;


int main(){
    int n,m; cin >> n >> m;
    G.resize(n);
    h.resize(n);
    rep(i,n){
        cin >> h[i];
    }
    rep(i,m){
        int a,b; cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    int ans = 0;
    rep(i,n){
        bool ok = true;
        for(int u :G[i]){
            if(h[i] <= h[u]) ok = false;
        }
        if(ok) ans++;
    }
    cout << ans << endl;
}   

Measured memory_bytes: 8784
/*
	submission # - User: herp_sy
	https://atcoder.jp/contests/
*/

import java.util.*;
import java.util.Collections; // sorting use
import java.io.*;
import static java.lang.System.*;

public class Main{
	public static void main(String[] args){
		int a,b;
		int tap = 1;
		int ans = 0;
		Scanner sc = new Scanner(System.in);

		a = sc.nextInt();
		b = sc.nextInt();
		while(tap < b){
			tap += (a - 1);
			++ans;
		}
		out.println(ans);
	}
}


Measured memory_bytes: 21712
#include <iostream>
#include <cmath>
using namespace std;
typedef long long int LLI;

int main()
{
	LLI a, b, c, x, save, sum = 0;
	cin >> a >> b >> c >> x;
	for(int i = 0; i <= a and 500*i <= x; i++)
		for(int j = 0; j <= b and 500*i + 100*j <= x; j++)
			if( ( x - 500*i - 100*j ) / 50 <= c )
				sum++;
	cout << sum;
}

Measured memory_bytes: 3592
#include<stdio.h>
int main()
{
	int a[1000];
	int j,k,n,ans,sum=0;
	scanf("%d",&n);
	for(k=1;k<=n;k++)
	scanf("%d",&a[k]);
	for(k=1;k<=n;k++)
	{
		for(j=k+1;j<=n;j++)
		{
			ans=a[k]*a[j];
			sum+=ans;
		}
	}
	printf("%d\n",sum);
}

Measured memory_bytes: 128
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AGC026_B
{
    class Program
    {
        static void Main(string[] args)
        {
            int t = int.Parse(Console.ReadLine());

            bool[] flags = new bool[t];

            for (int i = 0; i < t; ++i)
            {
                string[] strs = Console.ReadLine().Split(' ');
                long a = long.Parse(strs[0]);
                long b = long.Parse(strs[1]);
                long c = long.Parse(strs[2]);
                long d = long.Parse(strs[3]);

                flags[i] = Check(a, b, c, d);

            }

            for (int i = 0; i < t; ++i)
            {
                Console.WriteLine("{0}", flags[i] ? "Yes" : "No");
            }
        }

        static bool Check(long a, long b, long c, long d)
        {
            if (a < b) return false;

            long xMod = a % b;
            long x = a / b;

            long yMod = (a - c) % b;
            long y = (a - c) / b;

            if (x == y && yMod != 0) return false;

            long a2 = xMod + d;

            if (xMod + d < b) return false;


            long xMod2 = a2 % b;


            x = a2 / b;
            yMod = (a2 - c) % b;
            y = (a2 - c) / b;

            if (x == y && yMod != 0) return false;

            //if (xMod == xMod2) return true;



            if (d == b) return true;
            if (d < b) return false;


            long a3 = xMod2 + d;
            long xMod3 = a3 % b;

            if (xMod2 == xMod3) return true;

            long gcd = Gcd(b, d);

            long e = a3 - c;

            long f = (e / gcd) * gcd;
            long fMod = e % gcd;
            if (fMod == 0) f -= gcd;

            if (f + b > a3) return false;

            ////if (c + gcd >= b && d >= b) return true;
            //if ((c + gcd) - b + d >= b) return true;

            if (d > b) return true;


            return false;
        }

        public static long Gcd(long a, long b)
        {
            if (a < b)
            {
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            }

            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }
    }
}


Measured memory_bytes: 13268
from sys import exit
# A,B,C = [int(n) for n in input().split()]
# N = int(input())
# a = [int(input()) for _ in range(N)]
S = str(input())
# L = len(S)
cnt = 0
maxs = 0
for s in S:
    if s in ["A","G","C","T"]:
        cnt+=1
    else:
        cnt = 0
    if cnt > maxs:
        maxs = cnt
print(maxs)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
#define kragar ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
#define pb push_back
using namespace std;

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

	int k;
	cin >> k;
	string s;
	cin >> s;
	if (s.size() <= k)
		cout << s;
	else
	{
		for (ll i = 0; i < k ; i++)
			cout << s[i];
		cout << "...";
	}
}


Measured memory_bytes: 3648
#include <iostream>

using namespace std;

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

    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        cout << "#";
      }

      cout << endl;
    }
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,i,j,k,g=0,p=0;
  string s;cin>>s;
  for(i=0;i<s.size();i++){
    if(s[i]=='g') g++;
    else p++;
  }
  cout << (g-p)/2 << endl;
  return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
 
int main()
{
  char s[100];
  int n;
  scanf("%d", &n);
  scanf("%s", s);
  if(n % 2 == 1){
    printf("No\n");
    return 0;
  }
  for(int i = 0; i < n / 2; i++){
    if(s[i] != s[n / 2 + i]){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
  
  return 0;
}

Measured memory_bytes: 128
#include "bits/stdc++.h"
#define rep(i,b) for(ll i=0;i<b;i++)
#define ll long long
using namespace std;
/*--Input//////////////////////////////////////////////////*/
inline void IN(void){return;}
template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}
#define SS(T, ...)      T __VA_ARGS__; IN(__VA_ARGS__);
#define SV(type,c,n) vector<type> c(n);for(auto& i:c)cin >> i;
/*--Output/////////////////////////////////////////////////*/
inline int p(void){cout << endl; return 0;}
template<class Head> int p(Head&& head){cout << head;p();return 0;} template<class Head,class... Tail> int p(Head&& head,Tail&&... tail){cout<<head<<" ";p(forward<Tail>(tail)...);return 0;}
struct ProconInit {
    static constexpr bool AUTOFLUSH = false;
    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define vl vector<ll>
#define debug(x) cerr<<#x<<" "<<x<<'\n';
#define all(x) (x).begin(),(x).end()
#define bit(n) (1LL<<(n))
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; }
bool cmp(pair<ll,ll> a, pair<ll,ll> b) { return a.first+a.second > b.first+b.second; }

signed main() {
  string ans="";
  SS(ll,n);
  for(;;){
      if(n%26==0){
          ans+='z';
          n--;
      }
      else ans+=(char)(n%26+96);
      n-=n%26;
      n/=26;
      if(n==0)break;
  }
  reverse(ans.begin(),ans.end());
  p(ans);
}

Measured memory_bytes: 3644
#include <float.h>
#include <inttypes.h>
#include <limits.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include <math.h>
#ifdef __cplusplus
#include <bits/stdc++.h>
#endif

#define getchar getchar_unlocked
#define putchar putchar_unlocked
int32_t nextint(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); bool s=false; if(c=='-'){s=true;c=getchar_unlocked();} uint32_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
int64_t nextlong(void){ char c=getchar_unlocked(); while(c!='-'&&(c<'0'||'9'<c)) c=getchar_unlocked(); int s=0; if(c=='-'){s=1;c=getchar_unlocked();} uint64_t x=0; while('0'<=c && c<='9'){ x=x*10+c-'0'; c=getchar_unlocked(); } return s?-x:x; }
uint32_t nextstr(char *s){ char c=getchar_unlocked(); while(c==' '||c=='\n') c=getchar_unlocked(); uint32_t len=0; while(c!=' '&&c!='\n'){ *s++=c; len++; c=getchar_unlocked(); } *s='\0'; return len; }

#define P 998244353

int k[3001];

int a[3000];
int b[3001][3001];
int main(void){
	int n=nextint();
	int s=nextint();
	for(int i=0; i<n; i++){
		a[i]=nextint();
	}
	k[0]=1;
	for(int i=0; i<n; i++){
		k[i+1]=k[i]*2%P;
	}
	b[0][0]=1;
	for(int i=0; i<=n; i++){
		for(int j=0; j<=s; j++){
			b[i+1][j]+=b[i][j]*2%P;
			b[i+1][j]%=P;
			if(j+a[i]<=s){
				b[i+1][j+a[i]]+=b[i][j];
				b[i+1][j+a[i]]%=P;
			}
		}
		/*
		for(int i=0; i<=s; i++){
			printf("%d ", b[i]);
		}
		putchar(10);
		*/
	}
	printf("%d\n", b[n][s]);
}


Measured memory_bytes: 36772
def int_raw():
    return int(raw_input())

def ss_raw():
    return raw_input().split()

def ints_raw():
    return map(int,ss_raw())

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in xrange(n)]

def make2d_arr(w,h,val =INF):
    return [[val for i in xrange(w)]for i in xrange(h)]

table = {"A":"T", "C":"G", "G":"C", "T":"A" }
b = raw_input()
print table[b]




Measured memory_bytes: 2568
#include <stdio.h>

int main(void)
{

  int a, b, c;

  scanf("%d %d %d", &a, &b, &c);

  if (a == b && b == c && c == a)
    printf("No\n");
  else if(a != b && b != c && c != a)
    printf("No\n");
  else
    printf("Yes\n");

  return 0;
}


Measured memory_bytes: 128
N = input()
P_list = input().split()
# N = '5'
# P_list = '4 2 5 1 3'.split()
P_list = [int(i) for i in P_list]
length = int(N)
ans = 0 
M = []
mini =-1
for i in range(length):
    # print(min(P_list[0:i+1]))
    if P_list[i] <mini or mini <0:
        mini = P_list[i]
    if mini == P_list[i]:
        ans +=1


    # if P_list[i]==min(P_list[0:i+1]):
    #     ans +=1
    
print(ans)

Measured memory_bytes: 25768
import sys


stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()


n = ni()
ttt = na()
s = sum(ttt)
m = ni()
for i in range(m):
    p, x = na()
    p -= 1
    print(s - ttt[p] + x)





Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
map<int,int> mp;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
mp[a]++;
mp[b]++;
}
for(int i=1;i<=n;i++) cout<<mp[i]<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define in freopen("in.txt","r",stdin)
//#define out freopen("out.txt","w",stdout) 
ll n,m,k,t,l,r;
ll a,b,c,d;
char A,B,C,X,Y,Z;
ll ans,MAX,MIN,sum;
ll ax[1000000];
char str[100000];
ll dx[12];
ll bx[2000500];


int main()
{
    ll i,j;
    t=1;
    //scanf("lld",&t);
    while(t--)
    {
        ll flag=0;
        scanf("%s",str);
        if(str[1]=='R') str[1]='B';
        else str[1]='R';
        printf("%s",str);
    }
	return 0;
}

Measured memory_bytes: 3840
use proconio::{input};
use std::collections::HashSet;

// #[fastout]
fn main() {
    input! {
        k: usize
    }

    let mut res = 0;
    // let mut used_pair: Vec<Vec<bool>> = vec![vec![false; k]; k];
    let mut used_pair = HashSet::<(usize, usize)>::new();

    let mut former_mod_res = 0;
    let mut mod_frag = 7 % k;
    loop {
        res += 1;
        // if used_pair[former_mod_res][mod_frag] {
        if used_pair.contains(&(former_mod_res, mod_frag)) {
            println!("-1");
            return;
        } else {
            // used_pair[former_mod_res][mod_frag] = true;
            used_pair.insert((former_mod_res, mod_frag));
        }
        former_mod_res = (former_mod_res + mod_frag) % k;
        if former_mod_res == 0 {
            println!("{}", res);
            return;
        } else {
            mod_frag = (mod_frag * 10) % k;
        }
    }
}


Measured memory_bytes: 54200
/// c.cpp

# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < __typeof(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < pll >
# define pb push_back
# define pdd pair < db , db >
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n,k;
    fi>>n>>k;
    static ll s[1 << 20];
    for (int i = 1;i <= n;++i)
        fi>>s[i],s[i] -= k;
    for (int i = 1;i <= n;++i)
        s[i] += s[i - 1];
    vl ss;
    for (int i = 0;i <= n;++i)
        ss.pb(s[i]);
    sort(ss.begin(),ss.end());
    ss.resize(unique(ss.begin(),ss.end()) - ss.begin());
    const int SZ = ss.size();
    static int t[1 << 20];
    auto U = [&](ll v)
    {
        for (int i = lower_bound(ss.begin(),ss.end(),v) - ss.begin() + 1;i <= SZ;i += i&(-i))
            ++t[i];
    };
    auto Q = [&](ll v)
    {
        int ans = 0;
        for (int i = lower_bound(ss.begin(),ss.end(),v) - ss.begin() + 1;i;i -= i&(-i))
            ans += t[i];
        return ans;
    };
    ll ans = 0;
    U(s[0]);
    for (int i = 1;i <= n;++i)
        ans += Q(s[i]),U(s[i]);
    fo << ans << '\n';
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}


Measured memory_bytes: 4720
n, m = list(map(int, input().split()))
A = [[0]*m for _ in range(n)]
B = [0]*m
for i in range(n):
  a = list(map(int, input().split()))
  for j in range(m):
    A[i][j] = a[j]
for i in range(m):
  B[i] = int(input())
for i in range(n):
  ans = 0
  for j in range(m):
    ans += A[i][j]*B[j]
  print(ans)


Measured memory_bytes: 6012
#include <iostream>

using namespace std;
int q;
struct point
{
    double x,y;
};
point vt(point a,point b)
{
    point vt;
    vt.x=b.x-a.x;
    vt.y=b.y-a.y;
    return vt;
}
void test(point a,point b)
{
    if (a.x*b.y==a.y*b.x) cout<<2<<endl;
    else if (a.x*b.x+a.y*b.y==0) cout<<1<<endl;
    else cout<<0<<endl;
}
int main()
{
    cin>>q;
    while (q--)
    {
        point p0,p1,p2,p3;
        cin>>p0.x>>p0.y>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y;
        point p01=vt(p0,p1);
        point p23=vt(p2,p3);
        test(p01,p23);
    }
    return 0;
}



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

int div_sum(int n) {
  int sum = 0;
  while ( n > 0) {
    sum += n % 10;
    n /= 10; 
  }
  return sum;
}


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

  int ans;
  int min_ans = 50;

  for (int i = 1 ; i <= n/2 ; i++) {
    ans = div_sum(i) + div_sum(n - i);
    min_ans = min(min_ans, ans);
  }

  cout << min_ans << endl;

}

Measured memory_bytes: 256
//
// Created by 13783 on 2020/4/1.
//

#include<iostream>
using namespace std;
const int N=1e5+5;
const int K=100;
int h[N];
int dp[N];
int n;
int k;
const int maxn=0x3fffffff;
void solve(){
    dp[1]=0;

    for(int i=2;i<=n;i++){
        dp[i]=maxn;
    }
    //dp[i]为跳到第i步的最小代价
    for(int i=2;i<=n;i++){
      for(int j=1;j<=k&&i>j;j++){
          dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i]);
      }
    }
    cout<<dp[n];
}
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    solve();
    return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h> 
using namespace std;
int main()
{
  	char c;
    cin>>c;
    if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')    
	{
		cout<<"vowel"<<endl;
	}  
    else 
	{
		cout<<"consonant"<<endl;
	}
    return 0;
}


Measured memory_bytes: 256
h,w=map(int,input().split())
a1=[[*input()] for _ in range(h)];a2=[i for i,j in enumerate(zip(*a1)) if j.count('.')==h]
[print(*[k for l,k in enumerate(j) if l not in a2],sep='') for j in [i for i in a1 if i.count('.')<w]]

Measured memory_bytes: 9300
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pint = pair<int, int>;
using vi = vector<int>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

template<typename T> T gcd(T a, T b) { return b ? gcd(b, a%b) : a; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

int main() {
    lint a, b, c, d;
    cin >> a >> b >> c >> d;

    lint res = b - a + 1;

    lint bpc = b / c;
    lint apc = (a-1) / c;
    lint cd = bpc - apc;
    lint bpd = b / d;
    lint apd = (a-1) / d;
    lint dd = bpd - apd;
    lint cdl = lcm(c, d);
    lint bpcd = b / cdl;
    lint apcd = (a-1) / cdl;
    lint cdd = bpcd - apcd;
    cout << res - cd - dd + cdd << endl;
    return 0;
}


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

double abst(double x, int v){
    if(x-(double)v>0)return x-(double)v;
    else return (double)v-x;
}

int main(){
    int N; cin>>N;
    vector<int>v;
    for(int i=0;i<N;i++){
        int a; cin>>a;
        v.push_back(a);
    }
    sort(v.begin(),v.end());
    cout<<v[N-1]<<" ";
    double x=v[N-1]/2.0;
    double min=abst(x,v[0]);
    int ans=v[0];
    for(int i=1;i<v.size();i++){
        if(min>abst(x,v[i])){
            min=abst(x,v[i]);
            ans=v[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 892