akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
// #include <numeric> // gcdとかlcmとか C++17から
#include <time.h> // time_t timer; time(&timer); でtimerに現在時刻が代入される．
#include <unistd.h> // sleep関数．引数は秒単位．
using namespace std;

typedef long long ll;


// sortの仕方
// 	■ string s の場合
// 	昇順: sort(s.begin(), s.end())
// 	降順: sort(s.rbegin(), s.rend())
//
// 	■ ll a[N] の場合
// 	昇順: sort(a, a+N)
// 	降順: 不明

// vector の使い方
// 宣言：
// vector<int> v;
// vector<int> v(N);
// 初期化:
// vector<int> v(10, 5); 要素数10，全ての要素の値5．
// vector<int> v = {1, 2, 3};
// 代入：
// v[0] = 3;
// sort:
// sort(v.begin(), v.end());
//

// int alph2int(char character) {
//     int x = character - 'a';
//     return x;
// }

ll my_gcd(ll a, ll b){
	return (b==0) ? a : my_gcd(b, a%b);
}

ll my_lcm(ll a, ll b){
	return a*b / my_gcd(a,b);
}

ll factorial(ll a){
	ll ans = 1;
	for(ll i=a; i>0; i--){
		ans *= i;
	}
	return ans;
}

ll pow(ll a, ll b) {
	ll a_powered = 1;
	for (int i=0; i<b; i++) {
		a_powered *= a;
	}
	return a_powered;
}


int main(int argc, char *argv[]){
    int N; cin >> N;
    vector<int> V(N),C(N);

    for(int i=0; i<N; i++){
        cin >> V[i];
    }
    for(int i=0; i<N; i++){
        cin >> C[i];
    }

    int ans = 0;
    for(int i=0; i<N; i++){
        if(V[i]-C[i]>0){
            ans += V[i] - C[i];
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 764
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#define rep(i, n) for(int i = 0; i < n; i ++)
#define COUNT(i, n) for(int i = 1; i <= n; i ++)
#define ITER(c) __typeof((c).begin())
#define each(c, it) for(ITER(c) it =(c).begin(); it!=(c).end(); it++)
#define ALL(c) c.begin(), c.end()
#define mp make_pair
#define pb push_back
#define MEMSET(v, h) memset((v), h, sizeof(v))
 
using namespace std; 

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<string> vs;

const int INF = 1 << 24;
const double EPS = 1e-5;

int main(void){
    double x;
    for(int q; cin >> q, x = q / 2., ~q; printf("%.6f\n", x)) 
        while(!(fabs(pow(x, 3) - q) < EPS * q))
            x = x - (pow(x, 3) - q) / (3 * pow(x, 2));
 
    return 0;
}

Measured memory_bytes: 1192
#include <vector>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <ctime>
#include <map>
#include <set>
#include <chrono>
#include <queue>
#include <string>
#include <cassert>
#include <bitset>
#include <stack> 
#include <unordered_set>

#define INFLL 2000000000000000000
#define INF 2000000000
#define MOD 1000000007
#define BASE 77747
#define PI acos(-1.0)
#define MAXLEN 29

using namespace std;

typedef pair <int, int> pii;
typedef long long ll;
typedef vector <ll> vll;

int h, w, n;
pair <int, int> arr[100006];
ll f[200001];
ll dp[100006];

ll modPow(ll num, ll p) {
	ll ans = 1;
	while (p) {
		if (p & 1) {
			ans *= num;
			ans %= MOD;
		}
		num *= num;
		num %= MOD;
		p >>= 1;
	}
	return ans;
}

ll c(ll N, ll K) {
	if (K > N) return 0;
	if (K < 0 || N < 0) return 0;
	return (f[N] * modPow(f[N - K], MOD - 2) % MOD) * modPow(f[K], MOD - 2) % MOD;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d %d %d", &h, &w, &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &arr[i].first, &arr[i].second);
		arr[i].first--;
		arr[i].second--;
	}
	arr[n] = make_pair(0, 0);
	arr[n + 1] = make_pair(h - 1, w - 1);
	n += 2;
	f[0] = 1;
	for (int i = 1; i <= h + w; i++) f[i] = f[i - 1] * i % MOD;
	sort(arr, arr + n);
	dp[0] = 1;
	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 1; j--) {
			if (arr[i].first >= arr[j].first &&
				arr[i].second >= arr[j].second) {
					dp[i] += (c(arr[i].first - arr[j].first + 
						arr[i].second - arr[j].second, arr[i].first - arr[j].first) *
						dp[j]) % MOD;
				}
		}
		dp[i] = (c(arr[i].first + arr[i].second, arr[i].first) - 
			dp[i]) % MOD;
		if (dp[i] < 0) {
			dp[i] += MOD;
		}
	}
	cout << dp[n - 1] << endl;
	return 0;
}

Measured memory_bytes: 1920
#include <iostream>
#include <cmath>
#include <string>

using namespace std;

int main()
{
	int a,b,c,d;cin >> a >> b >> c >> d;
	while(a || c)
	{
		c -= b;
		if(c <= 0)
		{
			puts("Yes");
			return 0;
		}
		a -= d;
		if(a <= 0)
		{
			puts("No");
			return 0;
		}
	}
    return 0;
}


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

int main() {
  
  int a;
  int b;
  int c;
  int k;
  
  cin >> a >> b >> c >> k;
  
  if(a >= k) {
    cout << k*1 << endl;
  }
  
  if(a<k && a+b>=k) {
    cout << a*1 + (k-a)*0 << endl;
  }
  
  if(a+b<k && a+b+c>=k) {
    cout << a*1 + (k-a)*0 + (k-a-b)*(-1) << endl;
  }
  
}


Measured memory_bytes: 3632
# -*- coding: utf-8 -*-
N = int(input())
H_list = list(map(int, input().split()))



for i in reversed(range(len(H_list))):
    if i == 0:
        print("Yes")
    elif H_list[i] - H_list[i - 1] == -1:
        H_list[i - 1] -= 1
    elif H_list[i] - H_list[i - 1] < -1:
        print("No")
        break
    else:
        continue


Measured memory_bytes: 14252
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

x,n = iim()
p = set(iil())
for i in range(100):
    if x-i not in p:
        print(x-i)
        exit()
    elif x+i not in p:
        print(x+i)
        exit()


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

using VS = vector<string>;    using LL = long long;
using VI = vector<int>;       using VVI = vector<VI>;
using PII = pair<int, int>;   using PLL = pair<LL, LL>;
using VL = vector<LL>;        using VVL = vector<VL>;

#define ALL(a)  begin((a)),end((a))
#define RALL(a) (a).rbegin(), (a).rend()
#define SZ(a) int((a).size())
#define SORT(c) sort(ALL((c)))
#define RSORT(c) sort(RALL((c)))
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)
#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)
//#pragma GCC optimize ("-O3") 
#ifdef YANG33
#include "mydebug.hpp"
#else
#define DD(x) 
#endif
const int INF = 1e9;                          const LL LINF = 1e16;
const LL MOD = 1000000007;                    const double PI = acos(-1.0);
int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };

/* -----  __MAKE_TIME__  Problem: __PROBLEM__ / Link: __CONTEST_URL__  ----- */
/* ------問題------



-----問題ここまで----- */
/* -----解説等-----



----解説ここまで---- */



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

	LL N; cin >> N;
	VL a(N);
	FOR(i, 0, N) {
		cin >> a[i];
	}

	deque<LL>d;
	FOR(i, 0, N) {
		if (i % 2 == N % 2) {
			d.push_back(a[i]);
		}
		else {
			d.push_front(a[i]);
		}
	}
	for (auto it : d) {
		cout << it << " ";
	}cout << endl;

	return 0;
}


Measured memory_bytes: 5376
#include<bits/stdc++.h>
using namespace std;
int i,i0,n,m,k,pre[200005];
char s[200005];
int main()
{
    scanf("%d %s",&n,s);
    for(i=0;i<n;i++)pre[i]=pre[i-1]+(s[i]=='#');
    m=n-pre[n-1];
    for(i=0;i<n;i++)m=min(m,pre[i]+n-1-i-(pre[n-1]-pre[i]));
    printf("%d\n",m);
    return 0;
}

Measured memory_bytes: 1280
N,K = map(int, input().split())
XY = [ [int(j) for j in input().split()] for _ in range(N)]

xlst = []
ylst = []

for x,y in XY:
    x += 10**9 + 1
    y += 10**9 + 1
    xlst.append(x)
    ylst.append(y)

xset = sorted(list(set(xlst)))
yset = sorted(list(set(ylst)))

# print(xset, yset)

S = [ [0]*(N+1) for _ in range(N+1)]

for x,y in zip(xlst,ylst):
    x=xset.index(x)+1
    y=yset.index(y)+1
    S[y][x] = 1

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


ans = float("inf")
for i in range(N):
    for j in range(N):
        for k in range(N):
            for ll in range(N):

                left     = xlst[i]
                right    = xlst[j]
                top      = ylst[k]
                bottom   = ylst[ll]

                if right <= left: continue
                if bottom <= top: continue

                left = xset.index(left)+1
                right = xset.index(right)+1
                top = yset.index(top)+1
                bottom=yset.index(bottom)+1


                cnt = 0
                cnt += S[bottom][right]
                # print(cnt)
                cnt += S[top-1][left-1]
                # print(cnt)
                cnt -= S[top-1][right]
                # print(cnt)
                cnt -= S[bottom][left-1]
                # print(cnt)
                if cnt >= K:
                    left = xset[left    -1 ]
                    right = xset[right  -1 ]
                    top = yset[top      -1 ]
                    bottom = yset[bottom-1 ]
                    rect_area = (right-left)*(bottom-top)
                    ans = min(ans, rect_area)
                
print(ans)


                


Measured memory_bytes: 46552
#include<stdio.h>
int main(){
	char a,b,c;
	scanf("%c%c%c",&a,&b,&c);
	if(a==b && a!=c && b!=c){
		printf("Yes");
	}
	if(a==c && a!=b && b!=c){
		printf("Yes");
	}
	if(b==c && a!=b && a!=c){
		printf("Yes");
	}
	else if(a==b && a==c && b==c){
		printf("No");
	}
		return 0;	
}

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

pair<int, int> keta_num(int x);

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

    pair<int, int> p;
    int k;
    map<pair<int, int>, int> freq;
    int64_t ans = 0;

    for (k=1; k<=N; k++){

        p = keta_num(k);
        freq[p]++;
    }

    for (k=1; k<=N; k++){

        p = keta_num(k);
        
        pair<int, int> q(p.second, p.first);
        ans += freq[q];
    }

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

pair<int, int> keta_num(int x){
    
    int last = x%10;
    int first = 0;

    while(x){
        first = x;
        x /= 10;
    }
        
    return pair<int, int> (first, last);
}

Measured memory_bytes: 256
n = gets.to_i

h = {"M" => 0, "A" => 0, "R" => 0, "C" => 0, "H" => 0}
n.times do 
    s = gets[0]
    h[s] += 1 if h[s]
end

ans = 0
h.values.combination(3) do |arr|
    ans += arr.inject(:*)
end

puts ans


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

using namespace std;
int n,S[1000000];
bool cmp(const int a,const int b){
    return a>b;
}


bool mcmp(int t){
    if(t==1) return true;
    int tt = t/2;
    for(int i=0;i<tt;++i){
        if(S[i]<=S[i+tt]) return false;
    }
    return mcmp(t/2);
}

int main()
{
    scanf("%d",&n);
    int t = 1;for(int i=0;i<n;++i)t*=2;
    multiset<int> ss;
    for(int i=0;i<t;++i){scanf("%d",S+i);ss.insert(S[i]);}
    sort(S,S+t,cmp);
    bool yes = true;
    vector<int> bg;bg.push_back(S[0]);
    ss.erase(ss.find(S[0]));
    while(!ss.empty()&&yes){
        for(int i=0,st=bg.size();i<st;++i){
            auto pos = ss.lower_bound(bg[i]);
            if(pos==ss.begin()){
                yes = false;break;
            }
            bg.push_back(*(--pos));
            ss.erase(pos);
        }
    }
    if(yes) printf("Yes\n");
    else printf("No\n");

    return 0;
}


Measured memory_bytes: 14716
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	for (int i = 1; ; i++) {
		int x; cin >> x;
		if (x == 0) break;
		cout << "Case " << i << ": " << x << endl;
	}
}

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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    if(a == b && a != c){
        cout << "Yes" << endl;
    }else if(b == c && b != a){
        cout << "Yes" << endl;
    }else if(a == c && a != b){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a[51];
    cin >> n;
    for(int i = 0; i < n;i++){
        cin >> a[i];
    }
    long long sum = 0; 
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            sum+=a[i]*a[j];
        }
    }
    cout << sum << endl;
    return 0;
}


Measured memory_bytes: 256
//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define ct count
#define ep empty
#define _for(i,a,b) for(int i = (a);i<(b);++i)
#define _rfor(i,a,b) for(int i = (a);i>(b);--i)
#define _sfor(p,st) for(auto &p:st)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9+7;
const double eps = 1e-6;
const double pi = acos(-1.0);
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll qpow(ll x, ll y) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans *= x; x *= x; }return ans; }
ll qpow(ll x, ll y, int MOD) { ll ans = 1; for (; y > 0; y >>= 1) { if (y & 1)ans = ans*x%MOD; x = x*x%MOD; }return ans; }
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    ll X=x;
    x=y; y=X-a/b*y;
}
ll inv(ll x, int mod = MOD) { return qpow(x, mod - 2,mod); }
ll m_m(ll a){ return (a%MOD+MOD)%MOD; }

int a[200005];
int n,k;
int check(int x){
    ll sum = 0;
    _for(i,0,n){
        sum+=a[i]/x;
        if(a[i]%x==0)--sum;
    }
    return sum>k;
}
signed main() {
    //ifstream cin("E:\\acm dream\\in.in");
	//ofstream cout("E:\\acm dream\\out.out");
	FIO;
    #ifdef err
	double be = clock();
    #endif

    cin>>n>>k;
    int l=1,r=0;
    int ans;
    _for(i,0,n){cin>>a[i];r=max(r,a[i]);}
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))l=mid+1;
        else r=mid-1;
    }
    cout<<l;

    #ifdef err
	double en = clock();
    cout<<"time: "<<fixed<<setprecision(8)<<en-be;
    #endif
	return 0;
}

Measured memory_bytes: 4324
using System;

namespace ABC078C
{
  class Program
  {
    static void Main(string[] args)
    {
      string[] bufs = Console.ReadLine().Split(' ');
      int N = int.Parse(bufs[0]);
      int M = int.Parse(bufs[1]);

      int time = M * 1900 + (N - M) * 100;
      int res = time;

      for (int i = 0; i < M; i++) {
        res <<= 1;
      }

      Console.WriteLine(res);
    }
  }
}


Measured memory_bytes: 11092
#include <stdio.h>
#include <ctype.h>

int idx;
char formula[1024];

int addsub(int idx);

int number(int idx)
{
    int res = 0;
    if (formula[idx] == '('){
        res = addsub(idx + 1);
    }
    else {
        while (isdigit(formula[idx])){
            res = res * 10 + formula[idx] - '0';
            ++idx;
        }
    }
#ifdef DEBUG
    printf("   %d\n", res);
#endif
    return res;
}

int muldiv(int idx)
{
    int res = number(idx);
    int brackets = 0;
    while (1){
        if (formula[idx] == '*' && !brackets){
            res *= number(idx + 1);
#ifdef DEBUG
            printf("  %d\n", res);
#endif
        }
        else if (formula[idx] == '/' && !brackets){
            res /= number(idx + 1);
#ifdef DEBUG
            printf("  %d\n", res);
#endif
        }
        else if (formula[idx] == '('){
            ++brackets;
        }
        else if (formula[idx] == ')'){
            if (!brackets){
                break;
            }
            --brackets;
        }
        else if (!isdigit(formula[idx]) && !brackets){
            break;
        }
        ++idx;
    }
#ifdef DEBUG
    printf("  %d\n", res);
#endif
    return res;
}

int addsub(int idx)
{
    int res = muldiv(idx);
    int brackets = 0;
    while (1){
        if (formula[idx] == '+' && !brackets){
            res += muldiv(idx + 1);
#ifdef DEBUG
            printf("  %d\n", res);
#endif
        }
        else if (formula[idx] == '-' && !brackets){
            res -= muldiv(idx + 1);
#ifdef DEBUG
            printf("  %d\n", res);
#endif
        }
        else if (formula[idx] == '('){
            ++brackets;
        }
        else if (formula[idx] == ')'){
            if (!brackets){
                break;
            }
            --brackets;
        }
        else if (formula[idx] == '='){
            break;
        }
        ++idx;
    }
#ifdef DEBUG
    printf(" %d\n", res);
#endif
    return res;
}

int main(void)
{
    int n;

    scanf("%d", &n);
    while (n--){
        scanf("%s", formula);
        printf("%d\n", addsub(0));
    }

    return 0;
}

Measured memory_bytes: 596
import sys
read = sys.stdin.readline
n, d = map(int, read().split())
d2 = pow(d,2)
ans = 0
for _ in range(n):
    x,y = map(int, read().split())
    if pow(x,2)+pow(y,2)<=d2:
        ans += 1
print(ans)

Measured memory_bytes: 9036
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#define int long long
#define REP(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define MOD 1000000007

using namespace std;

signed main() {
    int n;
    cin >> n;
    vector<int> a(n), b(n), c(n);
    REP(i,n) cin >> a.at(i);
    REP(i,n) cin >> b.at(i);
    REP(i,n) cin >> c.at(i);
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    sort(c.begin(),c.end());
    vector<int> b_kosu(n);
    REP(i,n) b_kosu[i] = 0;
    REP(i,n) b_kosu[i] = n - (lower_bound(c.begin(),c.end(),b[i] + 1) - c.begin());
    for(int i = n-2; i > -1; i--) b_kosu[i] += b_kosu[i+1];
    int ans = 0;
    REP(i,n) ans += b_kosu[lower_bound(b.begin(),b.end(),a[i] + 1) - b.begin()];
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long x,y,ans,sum=0;
    cin>>x>>y;
    ans=y/x;
    while(ans)
    {
        ans=ans/2;
        sum++;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define ll long long
#define BIT_FLAG_0 (1<<0) // 0000 0000 0000 0001
int gcd(int a, int b){
    if(a%b == 0){
        return b;
    }else{
    return gcd(b, a%b);
    }
}

int main(){
    int n,m;
    ll sum=0;
    cin >> n >> m;
    vector<double> a(n);
    rep(i,n){
        cin >> a[i];
        sum+=a[i];
    }
    double count=(double)sum/(4*m);
    //cout << count << endl;
    sort(a.begin(),a.end(),greater<double>());
    rep(i,m){
        if(a[i]<count){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const ll INFLL = 1001001001001001001;  // > 10^18
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    int n; cin >>n;
    vector<double> a(n); REP(i,n) cin >> a[i];

    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += ((double)1)/a[i];
    }
    
    cout << setprecision(12) << ((double)1/sum) << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long A = sc.nextLong();
        long B = sc.nextLong();


                if(A==B){
                    System.out.println(0);
                 }else if((B-A)%2 ==0){

                    System.out.println((B-A)/2);

                }else{

                    if((A-1)<(N-B)){
                        System.out.println((A+B-1)/2);
                    }else{
                        System.out.println((N*2-A-B+1)/2);
                    }
                }



            }

        }


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

int balance(int N){
    int W[N];
    int sum=0;
    for(int i=0;i<N;i++){
        cin >> W[i];
        sum+=W[i];
    }
    int S1=0,S2;
    int diff=1000;
    for(int i=0;i<N;i++){
        S1+=W[i];
        S2=sum-S1;
        int tmp_diff=abs(S1-S2);
        diff=min(diff,tmp_diff);
    }
    return diff;
}

int main(){
    int N; cin >> N;
    cout << balance(N) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
 
const LL MOD = 1000000007;
LL n, m;
 
LL fac(LL x){
	LL res = 1;
	while (x)
		res = (res * (x--)) % MOD;
	return res;
}
 
int main(){
	scanf("%lld%lld", &n, &m);
	if (n > m) swap(n, m);
	if (n <= m-2) puts("0");
	else if (n == m-1) printf("%lld\n", fac(n)*fac(m)%MOD);
	else printf("%lld\n", 2*fac(n)*fac(m)%MOD);
	return 0;
}

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

#define int long long
#define ci(m)     for(int i=0;i<m;i++)
#define cj(m)     for(int j=0;j<m;j++)
#define ck(m)     for(int k=0;k<m;k++)
#define gcd            __gcd
#define endl           "\n"
#define pb             emplace_back
#define setbits(x)     __builtin_popcountll(x)
#define zrobits(x)     __builtin_ctzll(x)
#define mod            1000000007
#define mod2           998244353
#define maxe           *max_element
#define mine           *min_element
#define inf            1e18
#define deci(x, y)      fixed<<setprecision(y)<<x
#define w(t)           int t; cin>>t; while(t--)
#define nitin          ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PI             3.141592653589793238
using namespace std;

int32_t main() {
    nitin;
    int a,b,c;
    cin>>a>>b>>c;
    int ans=min(b,c);
    b-=ans;
    c-=ans;
    ans+=ans;
    int p=min(a,c);
    a-=p;
    c-=p;
    ans+=p;
    if(c!=0)
        ans+=1;
    ans+=b;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <stack>
#include <queue>
#include <cmath>

#define rep(i,j,k) for(int i=(int)j;i<(int)k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define llrep(i,j,k) for(long long int i=j;i<(long long int)k;i++)
#define Sort(x) sort(x.begin(),x.end()); 
#define vi vector<int>
#define vvi vector<vector<int>> 
#define ll long long
int mod=1e9+7;
const int INF = 1e9;

using namespace std;


int main(void) {
	int n, m;

	while (1) {
		cin >> n >> m;
		if (n == 0 && m == 0)break;
		vector<int> v(n), vv(m);
		int suma = 0, sumb = 0;
		rep(i, 0, n) {
			cin >> v[i];
			suma += v[i];
		}
		rep(i, 0, m) {
			cin >> vv[i];
			sumb += vv[i];
		}
		Sort(v);
		Sort(vv);

		if (suma > sumb) {
			bool judge = false;
			int x = suma - sumb;
			if (x % 2 == 1) {
				cout << -1 << endl;
				continue;
			}
			rep(i, 0, n) {
				rep(j, 0, m) {
					if (x/2 == v[i] - vv[j]) {
						judge = true;
						cout << v[i] <<" "<< vv[j] << endl;
						goto AWAY;
					}
				}
			}
			if (!judge)cout << -1 << endl;
		}
		else if (suma < sumb) {
			bool judge = false;
			int x = sumb - suma;
			if (x % 2 == 1) {
				cout << -1 << endl;
				continue;
			}
			rep(i, 0, n) {
				rep(j, 0, m) {
					if (x/2 == vv[j] - v[i]) {
						judge = true;
						cout << v[i] <<" "<< vv[j] << endl;
						goto AWAY;
					}
				}
			}
			if (!judge)cout << -1 << endl;
		}
		else {
			bool judge = false;
			rep(i, 0, n) {
				rep(j, 0, m) {
					if (v[i] == vv[j]) {
						cout << v[i] <<" "<< vv[j] << endl;
						goto AWAY;
					}
				}
			}
			if (!judge)cout << -1 << endl;
		}

	AWAY:;
	}




	


	return 0;
}

Measured memory_bytes: 3008
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef std::int_fast64_t i64;
typedef std::uint_fast64_t u64;
typedef std::int_fast32_t i32;
typedef std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(std::vector<T>& vector, const typename std::vector<T>::size_type size) {
    vector.reserve(size);
    std::copy_n(std::istream_iterator<T>(std::cin), size, std::back_inserter(vector));
  }

  template <typename T, std::size_t N>
  void read(std::array<T, N>& array) {
    std::copy_n(std::istream_iterator<T>(std::cin), N, array.begin());
  }
}

#endif

// main.cpp

int main() {
  i64 date;
  std::cin >> date;

  const std::array<bool, 2> is_year_part = {
    date / 100 == 0 || date / 100 > 12,
    date % 100 == 0 || date % 100 > 12
  };
  if (is_year_part[0]) {
    if (is_year_part[1]) {
      std::cout << "NA" << std::endl;
    } else {
      std::cout << "YYMM" << std::endl;
    }
  } else {
    if (is_year_part[1]) {
      std::cout << "MMYY" << std::endl;
    } else {
      std::cout << "AMBIGUOUS" << std::endl;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;++x)
#define Red(x,y,z) for(int x=y;x>=z;--x)
using namespace std;
const int MAXN=1505;
char buf[1<<12],*p1=buf,*p2=buf,nc;int ny;
//inline char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
inline char gc(){return getchar();}
inline int read(){
	int x=0;ny=1;while(nc=gc(),(nc<48||nc>57)&&nc!=EOF)if(nc==45)ny=-1;if(nc<0)return nc;
	x=nc-48;while(nc=gc(),47<nc&&nc<58&&nc!=EOF)x=(x<<3)+(x<<1)+(nc^48);return x*ny;
}
int Sumv[MAXN][MAXN],rpos[MAXN][MAXN],Mn[2][MAXN][MAXN],Mx[2][MAXN][MAXN],n;ll ans;
char S[MAXN][MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	n=read();
	Rep(i,1,n)scanf("%s",S[i]+1);
	for(int i=n,cur=1;i>=1;i--,cur^=1)Red(j,n,1)if(S[i][j]!='#'){
		Sumv[i][j]=Sumv[i+1][j]+Sumv[i][j+1]+(S[i][j]^48),rpos[i][j]=max(max(rpos[i+1][j],rpos[i][j+1]),i);
		Mn[cur][j][i]=j;
		Rep(k,i+1,rpos[i+1][j])Mn[cur][j][k]=Mn[cur^1][j][k];
		Rep(k,max(rpos[i+1][j],i)+1,rpos[i][j+1])Mn[cur][j][k]=Mn[cur][j+1][k];
		Mx[cur][j][i]=j;
		Rep(k,i,rpos[i][j+1])Mx[cur][j][k]=Mx[cur][j+1][k];
		Rep(k,max(rpos[i][j+1],i)+1,rpos[i+1][j])Mx[cur][j][k]=Mx[cur^1][j][k];
		for(int d=i+1,r=min(rpos[i][j+1],rpos[i+1][j]);d<=r;d++){
			if(Mx[cur^1][j][d]>=Mn[cur][j+1][d])
				Sumv[i][j]-=Sumv[d][Mn[cur][j+1][d]],d=rpos[d][Mn[cur][j+1][d]];
		}ans=(ans+1ll*(Sumv[i][j]-(S[i][j]^48))*(S[i][j]^48));
	}cout<<ans<<"\n";
	return 0;
}



Measured memory_bytes: 22116
#include<bits/stdc++.h>
using namespace std; 
int main(){
	string a;
	cin>>a;
	stack<char> q;
	for(int i=0;i<a.size();i++){
		if(a[i]=='C'){
			q.push(a[i]);
		}
		if(a[i]=='F'&&q.empty()==0){
			cout<<"Yes";
			return 0;
		}
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int A,B;
char S[110][110];


signed main(){
	cin>>A>>B;
	REP(i,100){
		REP(j,50){
			S[j][i]='#';
			S[j+50][i]='.';
		}
	}
	A--,B--;
	REP(i,50){
		if(i%2)continue;
		REP(j,100){
			if(j%2==0){
				continue;
			}
			if(A>0){
				S[i][j]='.';
				A--;
			}
			if(B>0){
				S[i+51][j]='#';
				B--;
			}
		}
	}
	cout<<100<<" "<<100<<endl;
	REP(i,100){
		REP(j,100){
			cout<<S[i][j];
		}
		cout<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{

    public static void main(String[] args){
	Scanner sc = new Scanner(System.in);

	int n = sc.nextInt();
	int p = sc.nextInt();

	while(n!=0 && p!=0){
	    int[] mayor = new int[n];
	    int pp = p;
	    int winner = 0;
	    for(int i=0;;){
		if(pp!=0){
		    mayor[i]++;
		    pp--;
		    if(mayor[i]==p){winner = i; break;}
		}else if(pp==0){
		    pp = mayor[i];
		    mayor[i] = 0;
		}
		i = (i+1)%n;
	    }

	    System.out.println(winner);

	    n = sc.nextInt();
	    p = sc.nextInt();
	}
    }
}

Measured memory_bytes: 0
n = int(input())
a = list(map(int, input().split()))

print(*a)

for i in range(1, n):
	v = a[i]
	j = i - 1
	while j>=0 and a[j] > v:
		a[j+1] = a[j]
		j -= 1
	a[j+1] = v
	print(*a)


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

typedef struct node {
  struct node *parent;
  int value;
} Node;

int compar(const void *a, const void *b)
{
  return *(int*)b - *(int*)a;
}

int main()
{
  int i, j, slen, ans;
  char s[100003];
  int cc[26] = {0};
  fgets(s, 100002, stdin);
  slen = strlen(s);
  if (s[slen-1]=='\n')  s[--slen]='\0';
  for (i=0; i<slen; i++) cc[s[i]-'a']++;
  qsort(cc, 26, sizeof(int), compar);
  for (j=0; cc[j]!=0; j++);
  if (j==1) {
    printf("%d\n", slen);
    return 0;
  }

  Node *nn = (Node*)malloc(sizeof(Node)*j*2);
  int n0, m0, m1;
  n0 = 0;
  m0 = m1 = j;

  for (i=0; i<j; i++) {
    nn[i].value = cc[j-i-1];
    nn[i].parent = NULL;
  }
  Node *x, *y, *z;
  do {
    if (n0<j && (nn[m0].value==0 || nn[n0].value<nn[m0].value)) {
      x = &nn[n0++];
    } else {
      x = &nn[m0++];
    }
    if (n0<j && (nn[m0].value==0 || nn[n0].value<nn[m0].value)) {
      y = &nn[n0++];
    } else {
      y = &nn[m0++];
    }
    if (y->value==0) break;
    z = &nn[m1++];
    x->parent=z;
    y->parent=z;
    z->value=x->value+y->value;
  } while (j>=n0);

  ans=0;
  for (i=0; i<j; i++) {
    for (z = &nn[i]; z->parent; z=z->parent)
      ans += cc[j-i-1];
  }
  printf("%d\n", ans);
  return 0;
}



Measured memory_bytes: 2112
import bisect
x = int(input())
T = [0] * ((10 ** 4) + 1)
for i in range(0, (10 ** 4)+1):
    T[i] = i ** 5

for i in range(len(T)):
    index = bisect.bisect_left(T, x + T[i])
    if index == len(T):
        break
    if T[index] == x + T[i]:
        print(' '.join(map(str,[index, i])))
        exit(0)


for i in range(len(T)):
    index = bisect.bisect_left(T, x - T[i])
    if index == len(T):
        break
    if T[index] == x - T[i]:
        print(' '.join(map(str,[index, -i])))
        exit(0)

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

using namespace std;

typedef long long ll;

int main(){
  ll A,B,C,K;
  cin >> A >> B >> C;
  cin >> K;
  ll num = 0;
  while(A>=B){
    num++;
    B*=2;
  }
  while(B>=C){
    num++;
    C*=2;
  }
  if(num<=K) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 3636
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())

    """
    奇数人のときは１飛ばし、３飛ばし、５飛ばし、、、とすればよい。
    偶数人のときは１飛ばし、３飛ばし、、、で途中から偶数飛ばしに切り替えるとよい。
    （「カークマンの組み分け」を参照）
    構成問題苦手だ。。。
    """

    if N % 2 == 1:
        cnt = 0
        for l in range(1, N // 2 + 1):
            r = N - l + 1
            print("{} {}".format(l, r))
            cnt += 1
            if cnt == M: return
    else:
        cnt = 0
        for l in range(1, N // 4 + 1):
            r = N - l + 1
            print("{} {}".format(l, r))
            cnt += 1
            if cnt == M: return
        for l in range(N // 4 + 1, N // 2):
            r = N - l
            print("{} {}".format(l, r))
            cnt += 1
            if cnt == M: return

    

if __name__ == "__main__":
    main()

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

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define dump_1(x1) cerr << #x1 << ": " << x1 << endl
#define dump_2(x1, x2) \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define dump_3(x1, x2, x3)                                                \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << endl
#define dump_4(x1, x2, x3, x4)                                            \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << endl
#define dump_5(x1, x2, x3, x4, x5)                                        \
  cerr << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " \
       << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#define dump(...) \
  CHOOSE((__VA_ARGS__, dump_5, dump_4, dump_3, dump_2, dump_1, ~))(__VA_ARGS__)
#define check(s) cerr << s << endl

#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++)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define unique(v) v.erase(unique(v.begin(), v.end()), v.end());
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)

using namespace std;

using ll = long long;

vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};

const ll LINF = 2e18;
const int INF = 1e9;

void solve(ll N, ll W, std::vector<ll> w, std::vector<ll> v) {
  vector<vector<ll>> dp(N + 1, vector<ll>(W + 1, 0));

  rep(i, N) {
    FOR(j, 1, W + 1) {
      dp.at(i + 1).at(j) = dp.at(i).at(j);
      chmax(dp.at(i + 1).at(j), dp.at(i).at(j - 1));
      if (j - w.at(i) >= 0)
        chmax(dp.at(i + 1).at(j), dp.at(i).at(j - w.at(i)) + v.at(i));
    }
  }

  ll ans = 0;
  rep(j, W + 1) { chmax(ans, dp.at(N).at(j)); }
  cout << ans << endl;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  ll N;
  scanf("%lld", &N);
  ll W;
  scanf("%lld", &W);
  std::vector<ll> w(N);
  std::vector<ll> 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: 83192
#include<iostream>
#include<sstream>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<numeric>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>

#define rep(i,n) for(int i=0;i<n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define rp(i,c) rep(i,(c).size())
#define fr(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf=1<<28;
const double INF=1e12,EPS=1e-9;

int main()
{
	int b,r,g,c,s,t;
	while(cin>>b>>r>>g>>c>>s>>t,b+r+g+c+s+t){
		int ans=100-3*t+95*b+63*r+7*g+2*c+3*s;
		cout<<ans<<endl;
	}
	return 0;
}

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

#define int long long
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define rept(i,n) for(int (i)=0;(i)<=(int)(n);(i)++)
#define reps(i,s,n) for(int (i)=(s);(i)<(int)(n);(i)++)
#define repst(i,s,n) for(int (i)=(s);(i)<=(int)(n);(i)++)
#define repr(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define each(itr,v) for(auto (itr):(v))
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define mp(x,y) make_pair((x),(y))
#define fi first
#define se second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define ln '\n'
#define dbg(x) cout<<#x" = "<<(x)<<ln

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vector<int> > mat;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int inf = (int)1e9;
const ll linf = (ll)1e18;
const int mod = (int)(1e9+7);
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};
const double eps = 1e-10;

struct oreno_initializer {
	oreno_initializer() {
		cin.tie(0);
		ios::sync_with_stdio(0);
	}
} oreno_initializer;

// ━━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…
// .｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋.｡.:( ^ω^)・ﾟ＋
// ・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・‥…━━━☆・

ll x, y, gcd, lcm;

signed main() {
	cin >> x >> y;
	gcd = __gcd(x,y);
	lcm = x*y/gcd;
	if (x%y==0) cout << -1 << ln;
	else {
		reps(i,1,10000) if (x*i%y) {
				cout << x*i << ln;
				return 0;
			}
	}
}

Measured memory_bytes: 256
// J'aime
// Chemise Blanche

#include <bits/stdc++.h>
using namespace std;

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (i % 2 == 0) cout << s[i];
  }
  cout << '\n';
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3676
#include <iostream>
#include <vector>
using namespace std;
#define in(v) v; cin >> v;
#define rep(i,n) for(int i=0,_i=(n);i<_i;++i)
template<int MOD> struct MInt {
  long long val;
  constexpr MInt(long long val = 0) : val(val % MOD) { if (val < 0) val += MOD; }
  constexpr MInt operator+(const MInt& n) const { return MInt(val) += n; }
  constexpr MInt operator-(const MInt& n) const { return MInt(val) -= n; }
  constexpr MInt& operator+=(const MInt& n) { val = (val + n.val) % MOD; return *this; }
  constexpr MInt& operator-=(const MInt& n) { val = (MOD + val - n.val) % MOD; return *this; }
  friend ostream& operator<<(ostream& os, const MInt& n) { os<<n.val; return os; }
};
using mint = MInt<1000000007>;
int A[100];
mint dp[101][100001];
int main() {
  int in(N); int in(K);
  rep(i, N) cin >> A[i];

  dp[0][0] = 1;
  vector<mint> sum(K+2, 1);
  sum[0] = 0;
  rep(i, N) {
    vector<mint> sum2(K+2, 0);
    rep(j, K+1) {
      dp[i+1][j] = sum[j+1] - sum[max(0,j-A[i])];
      sum2[j+1] = sum2[j] + dp[i+1][j];
    }
    swap(sum, sum2);
  }


  cout << dp[N][K] << endl;

  return 0;
}


Measured memory_bytes: 79976
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<iomanip>

using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;
typedef vector<long long> vll;
typedef pair<long long, long long> pll;

const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int main(){
	ll H, W, K;
	cin >> H >> W >> K;
	vector<string> A;
	ll i, j, k;
	pll S;
	for (i = 0; i < H; i++){
		string row;
		cin >> row;
		for (j = 0; j < W; j++){
			if (row[j] == 'S'){
				S.first = i;
				S.second = j;
			}
		}
		A.push_back(row);
	}
	vector<vector<ll>> M;
	vll tmp(W, INF);
	for (i = 0; i < H; i++){
		M.push_back(tmp);
	}
	M[S.first][S.second] = 0;
	vector<pll> nows;
	nows.push_back(S);
	ll step = 1;
	for (k = 0; k < K; k++){
		vector<pll> nexts(0);
		while (!nows.empty()){
			pll now = nows.back();
			nows.pop_back();
			if (now.second - 1 >= 0){
				if (A[now.first][now.second - 1] != '#' && M[now.first][now.second-1]==INF){
					M[now.first][now.second - 1] = step;
					pll next(now.first, now.second - 1);
					nexts.push_back(next);
				}
			}
			if (now.second + 1 <= W - 1){
				if (A[now.first][now.second + 1] != '#' && M[now.first][now.second + 1] == INF){
					M[now.first][now.second + 1] = step;
					pll next(now.first, now.second + 1);
					nexts.push_back(next);
				}
			}			
			if (now.first - 1 >= 0){
				if (A[now.first - 1][now.second] != '#' && M[now.first - 1][now.second] == INF){
					M[now.first - 1][now.second] = step;
					pll next(now.first - 1, now.second);
					nexts.push_back(next);
				}
			}			
			if (now.first + 1 <= H - 1){
				if (A[now.first + 1][now.second] != '#' && M[now.first + 1][now.second] == INF){
					M[now.first + 1][now.second] = step;
					pll next(now.first + 1, now.second);
					nexts.push_back(next);
				}
			}
		}
		nows = nexts;
	}
	ll min_dist = H + W;
	for (i = 0; i < H; i++){
		for (j = 0; j < W; j++){
			if (M[i][j] < INF){
				min_dist = min(min_dist, min(min(i, j), min(H - i - 1, W - j - 1)));
			}
		}
	}
	if (min_dist == 0){
		cout << 1 << endl;
	}
	else{
		cout << ((min_dist - 1) / K) + 2 << endl;
	}
	return 0;
}

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

int main(){
    int n; cin >> n;
    vector<ll> lis(n);
    for(int i = 0; i < n; i++){
        cin >> lis[i];
    }
    int count = 0;
    int k = n-1;
    while(1){
        cout << lis[k] << " ";
        count++;
        k -= 2;
        if(k < 0){
            if(n % 2 == 0) k = 0;
            else k = 1;
            break;
        }
    }
    while(count != n){
        cout << lis[k] << " ";
        count++;
        k += 2;
    }
    return 0;
}

Measured memory_bytes: 3712
BIG_NUM = 10**9

n, m = map(int, input().split(" "))
c = list(map(int, input().split(" ")))

l = [BIG_NUM] * (n+1)
l[0] = 0

for c_i in c:
	for j in range(1, n+1):
		if j < c_i:
			continue
		l[j] = min(l[j-c_i]+1, l[j])

	# print(l)
print(l[n])



Measured memory_bytes: 7512
#include <bits/stdc++.h>
using namespace std;
int main(void) {
  int n,m;
  cin >> n >> m;
  vector<pair<int,int> > vp(m);
  for(int i = 0; i < m; ++i) {
    cin >> vp[i].first >> vp[i].second;
  }
  sort(vp.begin(),vp.end());
  const int INF = (1<<25);
  int bef = INF;
  int answer = 0;
  for(int i = 0; i < m; ++i) {
    int l=vp[i].first, r=vp[i].second;
    if(bef <= l) {
      ++answer;
      bef = INF;
    }
    bef = min(bef, r);
  }
  if(bef != INF) ++answer;
  cout << answer << endl;
  return 0; 
}

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

int n;
const int MAX = 2000000;

void maxHeapify(int *A,int i){
    int l = 2 * i, r = 2 * i + 1, largest;
    if(l <= n && A[l-1] > A[i-1]) largest = l;
    else largest = i;
    if(r <= n && A[r-1] > A[largest-1]) largest = r;
    if(largest != i){
        swap(A[i-1], A[largest-1]);
        maxHeapify(A, largest);
    }
}

void heapIncreaseKey(int *A, int i, int key){
    if(key < A[i-1]){
        printf("Exception: the new key is smaller than the present key.");
        return;
    }
    A[i-1] = key;
    while(i > 1 && A[i/2-1] < A[i-1]){
        swap(A[i/2-1], A[i-1]);
        i = i/2;
    }
}

void maxHeapInsert(int *A, int key){
    A[n++] = -1;
    heapIncreaseKey(A, n, key);
}

int heapExtractMax(int *A){
    if(n < 1){
        printf("Exception: Heap Under Flow");
    } else {
        int max = A[0];
        A[0] = A[--n];
        maxHeapify(A, 1);
        return max;
    }
}

int main(){
    static int A[MAX];
    n = 0;
    char str[10];
    while(scanf("%s",str)){
        if(str[0] == 'e' && str[1] == 'n') break;
        else if(str[0] == 'i'){
            int a;
            cin >> a;
            maxHeapInsert(A, a);
        } else printf("%d\n",heapExtractMax(A));
    }
}

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

signed main(){
  int N,M;cin>>N>>M;
  std::vector<int> v[N];
  for(int i=0;i<M;i++){
    int a,b;cin>>a>>b;a--;b--;
    v[a].push_back(b);
  }
  std::vector<int> dp(N);
  for(int i=0;i<N;i++)dp[i]=0;
  std::vector<int> w(N,0);
  for(int i=0;i<N;i++){
    for(int j=0;j<v[i].size();j++){
      w[v[i][j]]++;
    }
  }
  queue<int> que;
  for(int i=0;i<N;i++)if(w[i]==0)que.push(i);
  while(que.size()){
    int a=que.front();que.pop();
    for(int i=0;i<v[a].size();i++){
      dp[v[a][i]]=max(dp[v[a][i]],dp[a]+1);
      w[v[a][i]]--;
      if(w[v[a][i]]==0)que.push(v[a][i]);
    }
  }
  int ans=0;
  for(int i=0;i<N;i++)ans=max(ans,dp[i]);
  cout<<ans<<endl;
}


Measured memory_bytes: 7296
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
//long long mo = 1e9 + 7;
typedef long long ll;
typedef pair<int,int> P;

int main(){
    ll L;
    cin >> L;
    double x = L/double(3.0);

    //ll M = 0;
    //for(int i=1;i<)

    cout << setprecision(10) << (x*x*x) << endl;
    
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int m,d,ans=0;
signed main(){
    cin>>m>>d;
    for(int i=1;i<=m;i++){
        for(int j=22;j<=d;j++){
            int mul=(j/10)*(j%10);
            if(j/10==1||j%10==1)continue;
            if(i==mul){
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int a = in.nextInt();
		int b = in.nextInt();
		in.close();
		String ans = "No";
		if ((a & b & 1) == 1) {
			ans = "Yes";
		}
		System.out.println(ans);
	}
}


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

using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	int c,t,minx = 0x3f3f3f3f;
	for(int i = 0;i < n;i++){
		cin>>c>>t;
		if(t <= m){
			minx = min(minx,c);
		}
	}
	if(minx == 0x3f3f3f3f){
		cout<<"TLE";
	}else{
		cout<<minx;
	}
}

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


int MOD=1000000007;

int main(void){
    int N,K,h,c=0;
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> h;
        if(h>=K) c++;
    }
    cout << c << endl;

}


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

    int a=0,b=0,c=0,d=0;

    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;

        if(s=="AC")
        {
            a++;
        }

        if(s=="WA")
        {
            b++;
        }

        if(s=="TLE")
        {
            c++;
        }

        if(s=="RE")
        {
            d++;
        }


    }

    cout<<"AC x "<<a<<endl;
    cout<<"WA x "<<b<<endl;
    cout<<"TLE x "<<c<<endl;
    cout<<"RE x "<<d<<endl;


    return 0;
   
}


Measured memory_bytes: 3624
V = int(input())
E = int(input())
dist = [[float('inf')] * V for _ in range(V)]
for i in range(V): dist[i][i] = 0
for _ in range(E):
    a, b, c, d = map(int, input().split(','))
    dist[a-1][b-1], dist[b-1][a-1] = c, d
fr, to, money, cost = map(int, input().split(','))
for k in range(V):
    for i in range(V):
        for j in range(V):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
print(money-cost-dist[fr-1][to-1]-dist[to-1][fr-1])

Measured memory_bytes: 6760
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> v(9, 0);
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        v[min(8, a / 400)]++;
    }
    int res = 0;
    for (int i = 0; i <= 7; i++) {
        if (v[i] > 0) res++;
    }
    if (v[8] > 0) {
        cout << min(8, max(1, res)) << " " << res + v[8] << endl;
    } else {
        cout << res << " " << res << endl;
    }
}




Measured memory_bytes: 3628
import math
A, B, H, M = map(int, input().split())

ra = H*30 + 0.5*M
rb = M*6
rc = abs(ra-rb)
if rc > 180:
    rc = 360 - rc
c2 = A**2 + B**2 - 2*A*B* math.cos(math.radians(rc))
print(c2**(0.5))

Measured memory_bytes: 9508