akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

//制約のことを考えられていないような気がする                                                                                                                                     
int top, S[1000];

void push(int x){
  /* topを加算してから                                                                                                                                                           
     その値に挿入 */
  S[++top] = x;
}

int pop(){
  top--;
  /* topが指していた要素を返す */
  return S[top + 1];
  //ここ普通逆じゃないの？                                                                                                                                                       
  //returnしちゃったらtopの値変えられなかったわ笑                                                                                                                                
}

int main(){
  int a, b;
  top = 0;
  char s[100];
  while( scanf("%s", s) != EOF){
    if( s[0] == '+'){
      a = pop();
      b = pop();
      push(a + b);
    }else if( s[0] == '-' ){
      b = pop();
      a = pop();
      push(a - b);
    }else if( s[0] == '*' ){
      a = pop();
      b = pop();
      push( a * b );
    }else{
      push(atoi(s));
    }
}

  printf("%d\n", pop());

  return 0;
}




Measured memory_bytes: 2108
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

int main(void){
    vector<int> a;
    int n;
    map<int,int> dict;

    // input 
    cin >> n;
    for (int i=0;i<n;i++){
        int v;
        cin >> v;
        a.push_back(v); 
    }

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

    // 
    for (int i=0;i<a.size();i++){
        dict[i%2]+=a[i];
    }
    cout << dict[0] - dict[1];
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
using P = pair<ll, ll>;
int main(){
    ll L;
    cin >> L;
    if(L == 2){
        cout << 2 << " " << 2 << endl;
        cout << 1 << " " << 2 << " " << 1 << endl;
        cout << 1 << " " << 2 << " " << 0 << endl;
        return 0;
    }
    L--;
    ll dig = 0;
    ll cpy = L;
    while(cpy){
        dig++;
        cpy /= 2;
    }
    vector<P> v[dig];
    for(ll i = 0; i < dig - 1; i++){
        v[i].push_back(P(i + 1, 1 << (max<ll>(0, dig - i - 2))));
        if(dig - i - 2 >= 0) v[i].push_back(P(i + 1, 0));
    }
    ll po = 0;
    ll num = (1 << (dig - 1));
    for(ll i = dig - 2; i >= 0; i--){
        bool f = (L & (1 << i));
        num += f * (1 << i);
        if(!f) continue;
        v[0].push_back(P(dig - i - 1, (num ^ (1 << i))));
    }
    v[0].push_back(P(dig - 1, L));
    ll e = 0;
    for(ll i = 0; i < dig; i++) e += v[i].size();
    cout << dig << " " << e << endl;
    for(ll i = 0; i < dig; i++) for(auto j : v[i]) cout << i + 1 << " " << j.first + 1 << " " << j.second << endl;
    return 0;
}


Measured memory_bytes: 256
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String S = sc.next();
		long K = sc.nextLong();
		String[] s = S.split("");
		String ans = "1";
		if(K <= 100) {
			for(int i = 0; i < K; i++) {
				if(!s[i].equals("1")) {
					ans = s[i];
					break;
				}
			}
		}
		else {
			for(int i = 0; i < s.length; i++) {
				if(!s[i].equals("1")) {
					ans = s[i];
					break;
				}
			}
		}
		System.out.println(ans);
	}

}


Measured memory_bytes: 25172
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;

int main()
{
    int a,b,cns;
    while(scanf("%d%d",&a,&b) != EOF)
    {
        cns = a/b;
        if(a%b) cns++;
        printf("%d\n",cns);
    }
    return 0;
}


Measured memory_bytes: 128
///////////////////////Loading Payloads.......////////////////////////////
#include<bits/stdc++.h>
#define f(i,a,b) for(int i = a; i < b; i++)
#define fd(i,a,b) for(int i = a; i > b;i--)
#define ll long long
#define fl(i,a,b) for(ll i = a; i < b; i++)
#define VI vector<int>
#define VP vector<pair<int,int>>
#define VS vector<string>
#define VL vector<long long>
#define VC vector<char>
#define VF vector<float>
#define PB push_back
#define F first
#define S second
#define fa(i,skill) for(auto i : skill)
#define fr(i,skill) for(VI :: reverse_iterator i = skill.rbegin(); i != skill.rend(); i++)
#define PI pair<int,int>
#define mi map<int,int>
#define mci map<char,int>
#define all(x) x.begin(),x.end()
using namespace std;

///////////////////////Engine Check.......////////////////////////////
void edit(VI &skill,int n)
{
    f(i,0,n)
        {
            int x;
            cin >> x;
            skill.PB(x);
        }	
}

void achilles()
{
	string s;cin >> s;
	int x = s.size();
	if(s[x-1]=='s')
	{
		cout << s << "es" << "\n";
		return;
	}
	cout << s << "s" << "\n";
}
///////////////////////3....2....1...Ignition////////////////////////////

int main()
{
	ios :: sync_with_stdio(0);
	cin.tie(0);
	/*int t;cin >> t;
	while(t--)*/
    achilles();
    return 0;
}

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

int main(){
    int a, b, c;
    cin>>a>>b>>c;
    int k;
    cin>>k;
    while(k--){
        if(a>=b){
            b*=2;
        }
        else if(b>=c){
            c*=2;
        }
        else{
            break;
        }
    }
    if(a<b && b<c){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}


Measured memory_bytes: 3592
a=gets.to_i
b=gets.to_i
c=gets.to_i
d=gets.to_i
e=gets.to_i
p=[]
p[0]=(a%10 !=0) ? 10-a%10 : 0
p[1]=(b%10 !=0) ? 10-b%10 : 0
p[2]=(c%10 !=0) ? 10-c%10 : 0
p[3]=(d%10 !=0) ? 10-d%10 : 0
p[4]=(e%10 !=0) ? 10-e%10 : 0

p.sort!
sum = p[0]+p[1]+p[2]+p[3]
puts (a+b+c+d+e)+sum

Measured memory_bytes: 1788
#include<stdio.h>
int main(void){

    int i,y=700;
    char s[3];

    scanf("%c %c %c",&s[0],&s[1],&s[2]);

    if(s[0]=='o')y=y+100;
    if(s[1]=='o')y=y+100;
    if(s[2]=='o')y=y+100;
   

    printf("%d",y);

}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<cstring>

using namespace std;

int main(){
  int n, k, a[200009], check[200009];
  memset(check, 0, sizeof(check));
  vector<int> v;
  map<int, int> m;
  cin >> n >> k;
  for(int i=0;i<n;i++){
    cin >> a[i];
    m[a[i]]++;
  }
  for(int i=0;i<n;i++){
    if(check[a[i]]==0){
      check[a[i]]=1;
      v.push_back(m[a[i]]);
    }
  }
  sort(v.begin(), v.end());
  int cnt=0;
  for(int i=0;v.size()-i>k;i++){
    cnt+=v[i];
  }
  cout << cnt << endl;
}

Measured memory_bytes: 12284
/*
	Author - Arten
*/

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define ll long long
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main(){
	IOS;
	int a, p;
	cin >> a >> p;
	a = a * 3;
	p = p + a;
	p = p / 2;
	cout << p << endl;


	return 0;
}


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

int Point(char T, int R, int S, int P){
    switch(T){
        case 'r':
            return P;
        case 's':
            return R;
        case 'p':
            return S;
    }
}

int main() {
    int N, K, R, S, P, sum;
    string T;
    cin>>N>>K>>R>>S>>P>>T;
    sum = 0;
    bool isWon = true;
    string A(K, 'a');
    T = T + A;
    REP(i, 0, K){
        int j = 0;
        while(i + K * j < N){
            if(T[i+K*j] != T[i+K*(j+1)] || !isWon){
                sum += Point(T[i+K*j], R, S, P);
                if(!isWon){   
                    isWon = !isWon;
                }
            }else{
                isWon = !isWon;
            }
            j++;
        }
    }
    cout << sum << endl;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MAX=100005;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define REPM(i, mp) for (auto i = mp.begin(); i != mp.end(); ++i)
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#define dbgmint(n,arr) rep(i,n){cerr<<arr[i].x<<" ";}cerr<<endl;
#define out(a) cout<<a<<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

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

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);

    ll n;
    cin>>n;

    Vec t(n);
    Vec a(n);
    rep(i,n){
        cin>>t[i]>>a[i];
    }
    ll x = t[0]; ll y = a[0];
    REP(i,1,n){
        ll k = max((x+t[i]-1)/t[i],(y+a[i]-1)/a[i]);
        x = t[i]*k;
        y = a[i]*k;
//        dbg(x);
//        dbg(y);
    }

    ll ans=x+y;
    cout<<ans<<endl;
    return  0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ; 
typedef long long ll ;
ll n , m ; 
string a , b ; 
map < ll , char > s ; 
map < ll , bool > is ;
int main ()
{
	cin >> n >> m >> a >> b ;
	ll p = ( n * m ) / ( __gcd ( n , m ) ) ;
	for ( ll i = 0 ; i < n ; i ++ ){
		s [ ( i * ( p / n ) ) + 1 ] = a[i] ;
		is [( i * ( p / n ) ) + 1] = 1 ; 
	}
	for ( ll i = 0 ; i < m ; i ++ )
		if ( is [ ( i * ( p / m ) ) + 1 ] and s [ ( i * ( p / m ) ) + 1 ] != b[i] ) 
			return cout << -1 , 0 ;
	cout << p ; 
}

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

#define EPS (1e-7)
#define INF (1e10)
#define PI (acos(-1))

int main() {
    //cout.precision(11);
    int a, b, c;
    cin >> a >> b >> c;
    cout <<  min(b/a, c) << endl;
    return 0;
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
for i in range(N, 0, -1):
    B[i] = sum(B[x] for x in range(i, N+1, i)) % 2 != A[i-1]
print(sum(B))
print(*[i for i, v in enumerate(B) if v])

Measured memory_bytes: 17632
/*
 ▓█████▄  ▄████▄  ▓██   ██▓ ██▓███   ██░ ██ ▓█████  ██▀███
▒██▀ ██▌▒██▀ ▀█   ▒██  ██▒▓██░  ██▒▓██░ ██▒▓█   ▀ ▓██ ▒ ██▒
 ░██   █▌▒▓█    ▄   ▒██ ██░▓██░ ██▓▒▒██▀▀██░▒███   ▓██ ░▄█ ▒
 ░▓█▄   ▌▒▓▓▄ ▄██▒  ░ ▐██▓░▒██▄█▓▒ ▒░▓█ ░██ ▒▓█  ▄ ▒██▀▀█▄
 ░▒████▓ ▒ ▓███▀ ░  ░ ██▒▓░▒██▒ ░  ░░▓█▒░██▓░▒████▒░██▓ ▒██▒
  ▒▒▓  ▒ ░ ░▒ ▒  ░   ██▒▒▒ ▒▓▒░ ░  ░ ▒ ░░▒░▒░░ ▒░ ░░ ▒▓ ░▒▓░
  ░ ▒  ▒   ░  ▒    ▓██ ░▒░ ░▒ ░      ▒ ░▒░ ░ ░ ░  ░  ░▒ ░ ▒░
  ░ ░  ░ ░         ▒ ▒ ░░  ░░        ░  ░░ ░   ░     ░░   ░
    ░    ░ ░       ░ ░               ░  ░  ░   ░  ░   ░
  ░      ░         ░ ░
*/
//focus less on how much problem you should solve within a fixed time and focus more on getting the problem solved and
//learning something from it
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define rep(i,a,b) for(ll i=a; i<b; i++)
#define per(i,a,b) for(ll i=a; i>=b; i--)
#define ll long long int
#define ld long double
#define vi vector<ll>
#define vii vector <pair<ll,ll> >
#define sedes set <ll, greater <ll> >
#define seasc set <ll>
#define pb push_back
#define mkp make_pair
#define ff first
#define ss second
#define MOD 1000000007
#define prec(n) fixed<<setprecision(n)
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int> >
#define umap unordered_map<ll, ll>
#define map map<ll, ll>
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define mems(a, i) memset(a, i, sizeof(a))
#define endl '\n'
#define all(v) v.begin(),v.end()
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define deba(a) cout << #a << " " <<a << endl;
int main()
{
	fast;
#ifndef ONLINE_JUDGE
	freopen("D:\\input.txt", "r", stdin);
	freopen("D:\\output.txt", "w", stdout);
#endif
	int t = 1;
	// cin >> t;
	while (t--)
	{
		string s, ss;
		s += 'x';
		cin >> ss;
		s += ss;
		ll i = 1, j = 1, n = s.length();
		ll a[n + 1] = {0}, odd = 0, eve = 0;
		while (j < n)
		{
			//L-part
			if (s[j] == 'R' and s[j + 1] == 'L')
				i = j;
			if (j % 2 == 0)
				eve++;
			else odd++;
			//new component or last component
			if ((s[j] == 'L' and s[j + 1] == 'R') or (j == n - 1))
			{
				if (i % 2 == 0)
					a[i] = eve, a[i + 1] = odd;
				else
					a[i] = odd, a[i + 1] = eve;
				odd = 0, eve = 0;
				i = j + 1;
			}
			j++;
		}

		rep(i, 1, n)
		cout << a[i] << " ";

	}
	return 0;
}

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

#define ll long long
#define ld long double
#define ar array
#define pb push_back
#define FOR(i, a, b) for (int i=(a); i<(b); i++)

const int d4i[4]={-1, 0, 1, 0}, d4j[4]={0, 1, 0, -1};
const int d8i[8]={-1, -1, 0, 1, 1, 1, 0, -1}, d8j[8]={0, 1, 1, 1, 0, -1, -1, -1};

// void solve(string s,string t){
//     if(s.substr(t)){
//         return 
//     }
//     else{
//         return 1+ solve(s, )
//     }
// }


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

    string s,t;
    cin>>s;
    cin>>t;
    int c=s.length()-t.length();
    int mx=INT_MAX;
    FOR(i,0,c+1){
        int cnt=0;
        FOR(j,0,t.length()){
            if(s[i+j]!=t[j]){
                cnt++;
            }
        }
        mx=min(mx,cnt);
    }
    cout<<mx;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;

struct st {
	ll l, r;
	ll x, d;
};

bool operator<(const st& a, const st& b) {
	return a.l < b.l;
}

int n;
ll k;
ll a[120000];
int b[120000];
set<st> ss;

int main() {
	scanf("%d%lld", &n, &k);
	ll ans = 0;
	for (int i = 0; i < n; ++i) {
		scanf("%lld%d", a + i, b + i);
		a[i] *= 2;
		ans += a[i];
		if (a[i] > k && b[i] == 1) {
			cout << -1 << "\n";
			return 0;
		}
		if (b[i] == 2)
			a[i] %= k;
	}
	ss.insert({0, k, 0, 0});
	ll cur = 0;
	for (int i = 0; i < n; ++i) {
		ll d = a[i];
		ll nx = cur + d;
		if (nx > k)
			nx -= k;
		if (b[i] == 1) {
			if (cur < nx) {
				auto it = ss.lower_bound({cur, 0, 0, 0});
				while (it->r < nx)
					ss.erase(it++);
				st x1 = *it;
				st x2 = *it;
				ss.erase(it);
				x1.l = cur;
				x1.r = nx;
				x2.l = nx;
				x1.d = 1;
				x1.x = x2.x + x2.d * (x2.r - nx);
				ss.insert(x1);
				if (x2.l != x2.r)
					ss.insert(x2);
			}
			else {
				auto it = ss.lower_bound({cur, 0, 0, 0});
				while (it != ss.end())
					ss.erase(it++);
				it = ss.begin();
				while (it->r < nx)
					ss.erase(it++);
				st x1 = *it;
				st x2 = *it;
				ss.erase(it);
				x1.l = 0;
				x1.r = nx;
				x2.l = nx;
				x1.d = 1;
				x1.x = x2.x + x2.d * (x2.r - nx);
				ss.insert(x1);
				if (x2.l != x2.r)
					ss.insert(x2);
				x2.l = cur;
				x2.r = k;
				x2.d = 1;
				x2.x = x1.x + x1.d * x1.r;
				ss.insert(x2);
			}
			cur = (cur + a[i]) % k;
		}
		else {
			cur += a[i];
			cur %= k;
			auto it = ss.lower_bound({cur, 0, 0, 0});
			if (it == ss.begin())
				continue;
			--it;
			if (it->r <= cur)
				continue;
			st x1 = *it;
			st x2 = *it;
			ss.erase(it);
			x2.l = cur;
			x1.x = x2.x + x2.d * (x2.r - cur);
			x1.r = cur;
			ss.insert(x1);
			ss.insert(x2);
		}
	}
	ll mn = ss.begin()->x;
	for (auto x: ss)
		mn = min(mn, x.x);
	cout << ans + mn << "\n";
	return 0;
}




Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
int md=1000000007;
int main()
{
   int n,m,flage=0;
   cin>>n>>m;
   char dp[n][m];
   int graph[n+1][m+1];
   for(int i=0;i<n;i++)
   {
      for(int j=0;j<m;j++)
      {
           cin>>dp[i][j];
           graph[i][j]=0;
      }
   }
   
   if(n==1)
   {
       for(int i=0;i<m;i++)
       {
           if(dp[0][i]=='.')
            graph[0][i]=1;
            else
            {
               flage=1;
               break;
            }
       }
   }
   else if(m==1 && flage==0)
   {
       for(int i=0;i<n;i++)
       {
           if(dp[i][0]=='.')
             graph[i][0]=1;
             else
             {
                 flage=1;
                 break;
             }
       }
   }
   else if(flage==0)
   {
       graph[0][0]=1;
       for(int i=0;i<n;i++)
       {
           for(int j=0;j<m;j++)
           {
               if(dp[i][j]=='#')
                   continue;
                   
               if(dp[i-1][j]=='.' && i>=1)
                   graph[i][j]=(graph[i][j]%md+graph[i-1][j]%md)%md;
                   
                   if(dp[i][j-1]=='.' && j>=1)
                      graph[i][j]=(graph[i][j]%md+graph[i][j-1]%md)%md;
           }
       }
   }
   
   if(dp[n-1][m-1]=='.' && flage==0)
      cout<<graph[n-1][m-1]%md<<"\n";
      else
        cout<<"0"<<"\n";
   return 0;
}


Measured memory_bytes: 5120
while True:
    (H,W) = [int(i) for i in input().split()]
    if H == W == 0:
        break

    for hc in range(H):
        for wc in range(W):
            if(hc + wc) % 2 == 0:
                print('#',end='')
            else:
                print('.',end='')
        print()
    print()

Measured memory_bytes: 6808
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
using namespace std;

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


int main(){
  char b;
  char ans;
  cin >> b;
  if(b == 'A') ans = 'T';
  else if(b == 'T') ans ='A';
  else if(b == 'C') ans = 'G';
  else ans = 'C';

  cout << ans << endl;

}


Measured memory_bytes: 256
r, c = gets.split.map(&:to_i)
sheet = Array.new(r) { Array.new(c)}
0.upto(r-1) do |i|
  arr = gets.split.map(&:to_i)
  0.upto(c-1) do |j|
    sheet[i][j] = arr[j]
    sheet[i].push(sheet[i].inject(:+)) if j == (c-1)
 end
end
0.upto(r-1) do |i|
  puts sheet[i].join(" ")
end
final = sheet.transpose.map { |n| n.inject(:+) }
puts final.join(" ")



Measured memory_bytes: 7148
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> vvl;
typedef vector<vector<int>> vvi;
typedef vector<vector<char>> vvec;
typedef vector<vector<bool>> vveb;
typedef vector<vector<string>> vves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pb push_back
#define pp pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
//const int64 INF = 1LL << 58;
#define dame { puts("-1"); return 0;}
#define YES { cout << "YES" << endl; return 0; }
#define NO { cout << "NO" << endl; return 0; }
#define Yes { cout << "Yes" << endl; return 0; }
#define No { cout << "No" << endl; return 0; }
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 (a>b) { a=b; return 1; } return 0; }
int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
  	
  	int n,r;
  	cin >> n >> r;
  	if(n>=10){cout << r << endl;}
  	else{int ans =r + 100*(10-n);cout << ans << endl;}
  	return 0;
}

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

long long n, a, ans, x[100], w[5000][100];
int main(){
	cin >> n >> a;
	w[0][0] = 1;
	for(int i = 0; i < n; i++){
		cin >> x[i];
		for(int j = 1; (j*a-x[i]) <= 3000; j++){
			if(j*a-x[i] >= 0) ans += w[j*a-x[i]][j-1];
		}
		for(int j = 100; j >= 1; j--){
			for(int k = 3000; k >= x[i]; k--){
				w[k][j] += w[k-x[i]][j-1];
			}
		}
	}
	cout << ans;
}

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

int main(){
	int a, b, c;
	cin >> a >> b >> c;
	for(int i = 0; i <= b; i++){
		if(i * a % b == c){
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}


Measured memory_bytes: 256
S = list(str(input()))
 
if S[0] != "A":
  print("WA")
else:
  l = len(S)
  c = 0
  x = 0
  for i in range(2,l-1):
    if S[i] == "C":
      c += 1
      x = i
  if c !=1:
    print("WA")
  else:
    del S[x]
    del S[0]
    c = 0
    for i in S:
      if i.isupper():
        c += 1
    if c == 0:
      print("AC")
    else:
      print("WA")

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		int n_middle = n/2;
		boolean flag = true;
		String[] a = new String[n];
		String str;
		str = s.next();
		// 変数strの長さ分回す
		for (int i = 0; i < str.length(); i++) {
		    // 配列に順番に格納する
		    a[i] = String.valueOf(str.charAt(i));
		}

		if(n_middle == 0 || str.length() % 2 != 0) {
			flag = false;
		}else
		{
		for(int i=0; i<n_middle; i++) {
			if(!a[i].equals(a[n_middle+i])) {
				flag = false;
			}
		}
		}


		if(flag == true) {
			System.out.print("Yes");
		}else {
			System.out.print("No");
		}

	}
}


Measured memory_bytes: 21844
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<utility>
#include<cctype>
using namespace std;

int main(void)
{
  int a,b;
  cin>>a>>b;
  int n=1;
  if(b==100){
    b++;
  }
  for(int i=0;i<a;i++){
    n*=100;
  }
  n*=b;
  cout<<n<<endl;
  return 0;
}


Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define mp make_pair
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pii pair<ll,ll>
#define pb push_back
#define F first
#define S second
#define mi map<ll,ll>
#define mii map<pii,ll>
const ll N=(1e7+1);//mod=998244353;
ll n,m,k;//
ll a[N],dp[N];
string s;
ll l=(1e7+2);
int main(){
	int n;cin>>n;int ans[n],gcd1[n],gcd2[n],a[n];
	for(int i=0;i<n;i++)cin>>a[i];
	gcd1[0]=a[0];
	for(int i=1;i<n;i++){
		gcd1[i]=__gcd(gcd1[i-1],a[i]);
	}
	gcd2[n-1]=a[n-1];
	for(int i=n-2;i>=0;i--){
		gcd2[i]=__gcd(gcd2[i+1],a[i]);
	}
	ans[0]=gcd2[1];ans[n-1]=gcd1[n-2];
	for(int i=1;i<n-1;i++){
		ans[i]=__gcd(gcd1[i-1],gcd2[i+1]);
	}
	int temp=ans[0];
	for(int i=0;i<n;i++){
		temp=max(temp,ans[i]);
	}
	cout<<temp<<endl;
}
/*
2
5 2
3 6 4 7 2
5 3
3 -5 6 3 10


*/


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

int main() {
    int N;
    std::cin >> N;
    std::vector<int> v(N);
    for (auto& e : v) std::cin >> e;

    int Q;
    std::cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int k;
        std::cin >> k;
        std::cout << (std::lower_bound(v.begin(), v.end(), k) - v.begin()) << " "
                  << (std::upper_bound(v.begin(), v.end(), k) - v.begin()) << std::endl;
    }
}


Measured memory_bytes: 3092
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
int main(void){
    
    int n;
    cin >> n;

    int sum = 0;
    for(int i=1; i<=n; i++) {
        sum += i;
    }
    
    cout << sum << endl;

    return 0;
}


Measured memory_bytes: 256
N = int(input())
S = input()

R = []

for i in range(len(S)):
    if (ord(S[i]) + N) <= 90:
        R.append(chr((ord(S[i]) + N)))
    else:
        R.append(chr((ord(S[i]) + N - 26)))

print("".join(R))


Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>
#include <set>

using ll = long long;
using namespace std;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

const ll MOD = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
const double INF3 = 900000000000000;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()


struct edge { ll to, cap, rev; };

vector<edge>g[101000];
bool used[101000] = { 0 };

void add(ll from, ll to, ll cap) {
	g[from].push_back(edge{ to, cap, (ll)g[to].size() });
	g[to].push_back(edge{ from, (ll)0, (ll)g[from].size() - 1 });
}

ll dfs(ll v, ll t, ll f) {
	if (v == t)return f;
	used[v] = true;
	for (int i = 0;i < g[v].size();i++) {
		edge &e = g[v][i];
		if (!used[e.to] && e.cap > 0) {
			ll d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				e.cap -= d;
				g[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

ll max_flow(ll s, ll t) {
	ll flow = 0;
	for (;;) {
		fill(used, used + 100000, 0);
		ll f = dfs(s, t, INF);
		if (f == 0)return flow;
		flow += f;
		if (flow >= INF)return INF;
	}
}



int main() {
	char mp[110][110];
	int w, h;
	cin >> h >> w;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			cin >> mp[i][j];
		}
	}

	int s = 2 * h*w, t = s + 1;
	for (int i = 0;i < h;i++) {
		for (int j = 0;j < w;j++) {
			if (mp[i][j] == 'X') {
				add(s, i*w + j, INF);
				add(i*w + j, i*w + j + h*w, INF);
			}
			else add(i*w + j, i*w + j + h*w, 1);
			for (int k = 0;k < 4;k++) {
				int ni = i + dy[k], nj = j + dx[k];
				if (ni < 0 || ni >= h || nj < 0 || nj >= w)add(i*w + j + w*h, t, INF);
				else add(i*w + j + w*h, ni*w + nj, INF);
			}
		}
	}

	ll ans = max_flow(s, t);
	if (ans == INF) cout << -1 << endl;
	else cout << ans << endl;

	return 0;
}

Measured memory_bytes: 7296
#include<bits/stdc++.h>
#define N 2005
using namespace std;
const int mo=924844033;
int n,m,now,f[N],g[N],C[N][N],fc[N];
int main()
{
	int i,j,k,L;
	scanf("%d %d",&n,&m),fc[0]=1;
	for(i=1;i<N;i++)
		fc[i]=(1LL*fc[i-1]*i)%mo;
	for(i=0;i<N;i++){
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;j++)
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%mo;
	  }
	f[0]=1;
	for(i=1;i<=m;i++){
		L=(n-i)/m;
		for(j=0;j<=now;j++) g[j]=f[j],f[j]=0;
		for(j=0;j<=now;j++)
			for(k=0;k<=(L+1)/2;k++)
				f[j+k]=(f[j+k]+1LL*g[j]*C[L-k+1][k])%mo;
		now+=(L+1)/2;
		for(j=0;j<=now;j++) g[j]=f[j],f[j]=0;
		for(j=0;j<=now;j++)
			for(k=0;k<=(L+1)/2;k++)
				f[j+k]=(f[j+k]+1LL*g[j]*C[L-k+1][k])%mo;
		now+=(L+1)/2;
	  }
	for(i=0;i<=n;i++) f[i]=1LL*f[i]*fc[n-i]%mo;
	for(i=n;i>=0;i--)
		for(j=i+1;j<=n;j++)
			f[i]=(f[i]-1LL*f[j]*C[j][i]%mo+mo)%mo;
	cout<<f[0];
	return 0;
}


Measured memory_bytes: 15104
#include <stdio.h>
#include <math.h>

int main(void){
	int t,a;double b[5];
	for(t=0;t<5;t++){
		scanf("%lf",&b[t]);
	}
	b[1]=b[1]/b[3];
	b[2]=b[2]/b[4];
	if((b[1])>(b[2])){
		b[1]=ceil(b[1]);
	}
	else{
		b[1]=ceil(b[2]);
	}
	a=b[0]-b[1];
	printf("%d\n",a);
return 0;
}

Measured memory_bytes: 628
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;

#define LL long long
#define DB double
#define MAXN 300
#define Pr pair<LL,int>
#define X first
#define Y second
#define INF 1000000000
#define MOD 1000000007
#define mem(x,v) memset(x,v,sizeof(x))

LL read(){
    LL x=0,F=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')F=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*F;
}
int add(int a,int b){return (a+b>=MOD)?a+b-MOD:a+b;}
int dec(int a,int b){return (a-b<0)?a-b+MOD:a-b;}
int mul(int a,int b){return (1LL*a*b)%MOD;}
int fst_pow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=mul(res,a);
        a=mul(a,a),b>>=1;
    }return res;
}

int n,d[MAXN+5],dp[MAXN+5][MAXN+5],tot,inv2;
int fac[MAXN+5],ifac[MAXN+5],ans,xd;
void upd(int &x,int y){x=add(x,y);}

void prepare(){
    fac[0]=1;
    for(int i=1;i<=MAXN;i++)fac[i]=mul(fac[i-1],i);
    ifac[MAXN]=fst_pow(fac[MAXN],MOD-2);
    for(int i=MAXN;i>=1;i--)ifac[i-1]=mul(ifac[i],i);
}

int main(){
    prepare();
    n=read(),inv2=(MOD+1)>>1;
    for(int i=1;i<=n;i++)d[i]=read()-1;
    dp[0][0]=1;
    for(int i=1;i<=n;i++)
    if(d[i]){
        for(int j=i-1;j>=0;j--)
            for(int k=0;k<=tot;k++)
            upd(dp[j+1][k+d[i]-1],mul(d[i],dp[j][k]));
        tot+=d[i]-1;
    }
    ans=mul(mul(fac[n-1],inv2),dp[n][0]),xd=1;
    for(int i=1;i<=n;i++)xd=mul(xd,ifac[d[i]]);
    for(int i=3;i<n;i++)//**从3开始
        for(int j=1;j<=tot;j++){
            int c=mul(mul(fac[i-1],inv2),mul(fac[n-i-1],xd));
            ans=add(ans,mul(mul(c,j),dp[i][j]));
        }
    printf("%d",ans);
}


Measured memory_bytes: 3548
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	
	
	
	public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		int k = s.nextInt();
		
		int a[] = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = s.nextInt();
		}
		
		double ans = 0;
		for(int i=0;i<k;i++) {
			ans+=Math.log(a[i]);
		}
		double prev = ans;
		for(int i=k;i<n;i++) {
			ans-=Math.log(a[i-k]);
			ans+=Math.log(a[i]);
			if(ans>prev) {
				System.out.println("Yes");
			}
			else {
				System.out.println("No");
			}
			prev = ans;
		}
		
	}

}

Measured memory_bytes: 60672
import sys
input = sys.stdin.readline

N = int(input())
imo = []
xlmin = 0
xlmax = 0
for _ in range(N):
    x,l = map(int,input().split())
    imo.append([x-l,x+l-1])
imo = sorted(imo,key = lambda x: x[1])
cnt = 1
ls = imo[0][1]
for i in range(1,N):
    if imo[i][0]<=ls:
        continue
    else:
        cnt += 1
        ls = imo[i][1]
print(cnt)


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

using namespace std;

unsigned long long gcd(unsigned long long  x, unsigned long long  y) {
  if (y == 0) return x;
  return gcd(y, x%y);
}

int main(){
  int N;
  unsigned long long T1,T2;
  cin >> N;
  vector<unsigned long long> T(N);
  for(int i=0;i<N;i++){
    cin >> T[i];
  }

  sort(T.begin(),T.end());

  T1 = T[0];
    
  for(int i=1;i<N;i++){
    T2 = T[i];
    T1 = T1*(T2/gcd(T1,T2));
  }

  cout << T1 << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
using namespace std;
#define pie 3.141592653589793238462643383279
#define int long long
#define mod 1000000007
#define INF 1145141919364364
#define all(vec) vec.begin(),vec.end()
#define P pair<int,int>
#define S second
#define F first
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
bool prime(int x) {
	for (int i = 2; i <= sqrt(x); i++) {
		if (x%i == 0)return false;
	}
	return true;
}

int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1)*x%mod;
}

int mod_pow(int x, int y, int mood) {
	int res = 1;
	while (y > 0) {
		if (y & 1)res = res * x%mood;
		x = x * x%mood;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), mod - 2, mod) % mod * mod_pow(kai(y), mod - 2, mod) % mod;
}

int n;
string s;
int dp[5010][5010];
int ans;

signed main() {
	cin >> n >> s;
	for (int j = (int)s.size()-1; j >= 0; j--) {
		for (int i = j; i >= 0; i--) {
			if (s[i] == s[j]) dp[i][j] = dp[i + 1][j + 1] + 1;
			else dp[i][j] = 0;
		}
	}
	for (int i = 0; i < (int)s.size(); i++) {
		for (int j = i; j < (int)s.size(); j++) {
			ans = max(ans, min(dp[i][j], j - i));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 194944
#include <stdio.h>

int max(int a, int b){
    return (a > b) ? a:b;
}
int main(void){
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(((a < c) && (b > c)) || ((b < c) && (a > c))){
        printf("%s\n", "Yes");
    }
    else printf("%s\n", "No");
    return 0; 
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <string>

using namespace std;
int main(int argc, const char * argv[]) {
    
    int n, m;
    cin >> n >> m;
    if (m <= n) {
        cout << 0 << endl;
    }
    else {

        vector<int> x;
        x.resize(m);
        
        for (int i=0; i<m; i++) {
            cin >> x[i];
        }
        sort(x.begin(), x.end());

        vector<int> d(m-1);
        for (int i=0; i<m-1; i++) {
            d[i] = x[i+1] - x[i];
        }
        sort(d.begin(), d.end());

        int c=0;
        for (int i=0; i<m-n; ++i) {
            c+=d[i];
        }
        cout << c << endl;
    }
    
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <unordered_set>
using namespace std;
const char* solve() {
    int n;
    cin >> n;
    unordered_set<int> us;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        if (us.find(a) != us.end()) return "NO";
        us.insert(a);
    }
    return "YES";
}
int main() {
    cout << solve() << endl;
}

Measured memory_bytes: 8520
#include <bits/stdc++.h>
using namespace std;
#define min(a,b) ((a)<(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#define REP(i,n) for(ll i=0;i<n;i++)
#define FOR(i,n1,n2) for(ll i=n1;i<n2;i++)
#define bFOR(i,n1,n2) for(ll i=n1;i>=n2;i--)
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
typedef long long int ll;
typedef pair<ll,ll> Pi;
typedef tuple<ll,ll,ll> Tu;
const int INF=(ll)(1LL<<30)-1;
const double INFd=100000000000.0;
const double PI=3.14151926535;
const ll INFl=(ll)9223372036854775807;
const int MAX=10000;
const ll MOD=(ll)1e9+7;
const ll tMOD=(ll)998244353;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a, b)*b;}
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int mdx[8]={0,1,0,-1,1,1,-1,-1},mdy[8]={-1,0,1,0,1,-1,1,-1};


template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

const int MAX_N=100100;

int par[MAX_N];
int ran[MAX_N];
int size[MAX_N];

void init(int n){
	for(int i=0;i<n;i++){
		par[i]=i;
		ran[i]=0;
		size[i]=1;
	}
}

int find(int x){
	if(par[x]==x){
		return x;
	}else{
		return par[x]=find(par[x]);
	}
}

void unite(int x,int y){
	x=find(x);
	y=find(y);
	if(x==y)return;
	
	if(ran[x]<ran[y]){
		par[x]=y;
	}else{
		par[y]=x;
		if(ran[x]==ran[y])ran[x]++;
	}
	size[x]=size[y]+size[x];
	size[y]=size[x];
}

bool same(int x,int y){
	return find(x)==find(y);
}

int n,m,k;
int ans=0;
int t[100100]={};
int main(){
    cin>>n>>m>>k;
    init(n);
    REP(i,m){
        int a,b;
        cin>>a>>b;
        a--,b--;
        unite(a,b);
        t[a]++;
        t[b]++;
    }
    REP(i,k){
        int c,d;
        cin>>c>>d;
        c--,d--;
        if(find(c)==find(d)){
            t[c]++;
            t[d]++;
        }
    }
    REP(i,n){
        cout<<size[find(i)]-t[i]-1<<" ";
    }
    cout<<endl;
    return 0;
}

Measured memory_bytes: 2432
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <ctype.h>
int main(void){
  int n,w,h,cnt=0,i;
  scanf("%d%d%d",&n,&h,&w);
  for(i=0;i<n;i++){
    int a,b;
    scanf("%d %d",&a,&b);
    if(a>=h&&b>=w) cnt++;
  }
  printf("%d\n",cnt);
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=1LL<<61;

int main() {
  ll h,w,m;
  cin >> h >> w >> m;
  vec y(m),x(m);
  map<ll,ll> cy,cx;
  for(ll i=0;i<m;i++) {
    cin >> y[i] >> x[i];
    cy[y[i]]++;
    cx[x[i]]++;
  }
  ll my=1,mx=1;
  for(auto p:cy) {
    my=max(my,p.second);
  }
  for(auto p:cx) {
    mx=max(mx,p.second);
  }
  set<ll> mylist,mxlist;
  for(auto p:cy) {
    if(my==p.second) {
      mylist.insert(p.first);
    }
  }
  for(auto p:cx) {
    if(mx==p.second) {
      mxlist.insert(p.first);
    }
  }
  ll cnt=0;
  for(ll i=0;i<m;i++) {
    if(mylist.count(y[i])&&mxlist.count(x[i])) {
      cnt++;
    }
  }
  ll ans=mx+my;
  if(cnt==mylist.size()*mxlist.size()) ans--;
  cout << ans << endl;
}


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

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;

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

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

  // dp[i][j] - No. of ways to distribute j chocolates to the first i people
  int dp[n + 1][k + 1];
  memset(dp, 0, sizeof(dp));

  dp[0][0] = 1;

  for (auto i = 1; i <= n; ++i) {
    vector<int> prefix(k + 1, 0);
    prefix[0] = dp[i - 1][0];

    for (auto m = 1; m <= k; ++m) {
      prefix[m] = (prefix[m - 1] + dp[i - 1][m]) % MOD;
    }

    for (auto j = 0; j <= k; ++j) {
      dp[i][j] =
          (prefix[j] - (j - a[i] - 1 >= 0 ? prefix[j - a[i] - 1] : 0) + MOD) %
          MOD;
    }
  }

  // dbg(dp[2][0]);
  cout << dp[n][k] << "\n";
}


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

int main() {
    int n, m;
    cin >> n;
    
    vector<string> blue(n);
    for (int i=0; i<n; i++) {
        cin >> blue.at(i);
    }
    
    cin >> m;
    vector<string> red(m);
    for (int i=0; i<m; i++) {
        cin >> red.at(i);
    }
    
    int ans = 0;
    
    for (int i=0; i<n; i++) {
        int counter = 0;
        string text = blue.at(i);
        for (int j=0; j<n; j++) {
            if (text == blue.at(j)) {
                counter++;
            }
        }
        for (int j=0; j<m; j++) {
            if (text == red.at(j)) {
                counter--;
            }
        }
        ans = max(ans, counter);
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

typedef long long ll;
const int N = 1e6 + 10, OO = 0x3f3f3f3f, mod = 1e9 + 7;

#define PI acos(-1)
#define clr(arr, val) memset(arr, val, sizeof(arr))
#define loop(i, n) for (int i = 0; i < int(n); i++)
#define rloop(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define xloop(i, a, b) for (int i = int(a); i <= int(b); i++)
#define ALL(v) ((v).begin()), ((v).end())
#define SZ(v) ((int)((v).size()))
//int dx[] = {1, 0, -1, 0};
//int dy[] = {0, 1, 0, -1}; //4 Direction
//int dx[] = {1, 1, 0, -1, -1, -1, 0, 1};
//int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; //8 direction
int dx[]={2,1,-1,-2,-2,-1,1,2};int dy[]={1,2,2,1,-1,-2,-2,-1};//Knight Direction
//int dx[6]={2,1,-1,-2,-1,1};int dy[6]={0,1,1,0,-1,-1}; //Hexagonal Direction

//-- "كلٌّ من يسعى لابد يصل .. كلٌّ من يسعى مضمون له الوصول" --//

int x , dp[6][N];

int a[] = {100,101,102,103,104,105};

bool solve(int idx , int remW){
	if(remW < 0)
		return 0;
	if(idx == 6){
		if(remW == 0)
			return 1;
		return 0;
	}
	int &ret = dp[idx][remW];
	if(~ret) return ret;
	ret = solve(idx , remW-a[idx]) | solve(idx+1 , remW-a[idx]) | solve(idx+1 , remW);
	return ret;
}


int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	
	
	scanf("%d" , &x);
	clr(dp , -1);
	if(solve(0 , x))
		puts("1");
	else 
		puts("0");
		
	//for(int idx = 0 ; idx < 6 ; ++i)
		//dp[idx][0] = 1;
	//for(int idx = 0 ; idx < 6 ; ++i){
		//for(int rem = 0 ; rem <= x ; ++rem){
			//dp[idx][rem] = dp[idx+1][rem] | dp[idx][x-rem] | dp[idx+1][x-rem];
		//}
	//}
	//if(dp[6][x])
		//puts("1");
	//else 
		//puts("0");
	
    return 0;
}




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

char area[1001][1001];
int dp[1001][1001];

int traverseArea(int x, int y, int rows, int cols) {
    if (dp[y][x] != -1) {
        return dp[y][x];
    }
    if (area[y][x] == '#' || y == rows || x==cols) {
        return dp[y][x] = 0;
    }
    if (x == cols - 1 && y == rows - 1) {
        return 1;
    }
    return dp[y][x] = traverseArea(x + 1, y, rows, cols)%1000000007 + traverseArea(x, y + 1, rows, cols)%1000000007;
}

int main() {
    int rows,cols;
    cin>>rows>>cols;
    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++){
            dp[i][j] = -1;
            cin>>area[i][j];
        }
    }
    cout<<traverseArea(0, 0, rows, cols)%1000000007<<endl;
    return 0;
}

Measured memory_bytes: 5248
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e6 + 10, M = 2e6 + 10;

inline void Read(int &x) {
	x = 0; register char cc = '\0'; int fff = 1;
	for (; cc < '0' || cc > '9'; cc = getchar())
		if (cc == '-') fff = -1;
	for (; cc >= '0' && cc <= '9'; cc = getchar())
		x = (x << 1) + (x << 3) + (cc & 15);
	x *= fff;
}

bool ischain;
int n, rt, tot, fans, deg[N], f[N], Head[N], Next[M], Adj[M];

void DFS(int x, int fat) {
	if (deg[x] > 1) {
		int t = 0;
		for (int e = Head[x]; e; e = Next[e])
			if (Adj[e] != fat) {
				DFS(Adj[e], x);
				f[x] |= f[Adj[e]];
				if (f[Adj[e]]) ++t;
			}
		if (fat) {
			if (deg[x] > 2) f[x] = 1;
			if (t < deg[x] - 2)
				fans += deg[x] - 2 - t;
		}
		else {
			if (deg[x] > 1) f[x] = 1;
			if (t < deg[x] - 1)
				fans += deg[x] - 1 - t;
		}
	}
}

int main()
{
	Read(n);
	if (n == 1) {
		printf("0\n");
		return 0;
	}
	for (int i = 1, x, y; i < n; ++i) {
		Read(x), Read(y);
		++x, ++y;
		++deg[x], ++deg[y];
		Next[++tot] = Head[x]; Head[x] = tot; Adj[tot] = y;
		Next[++tot] = Head[y]; Head[y] = tot; Adj[tot] = x;
	}
	for (int i = 1; i <= n; ++i)
		if (deg[i] > 2) {
			rt = i;
			ischain = true;
			break;
		}
	DFS(rt, 0);
	fans = max(fans, 1);
	printf("%d\n", fans);
	
	return 0;
}


Measured memory_bytes: 13824
#pragma GCC optimize (3)
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define PII pair<int,int>
#define ll long long
#define ull unsigned long long
#define INFI 2147483647
#define INFL 9223372036854775807
#define INFU 18446744073709551615
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while (ch<'0' || ch>'9') {
		if (ch == '-') f = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}
int main()
{
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	//cout.tie(0);
	int a = read(), b = read(), c = read();
	int ans = c - (a - b);
	if (ans < 0) ans = 0;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(void){
  int N;
  cin>>N;
  int p[N];
  for(int i=0;i<N;++i) p[i]=0;
  vector<int> n[3];
  for(int i=0,a,b,c;i<N;++i){
    cin>>a>>b>>c;
    n[0].push_back(a);
    n[1].push_back(b);
    n[2].push_back(c);
  }
  for(int i=0;i<3;++i){
      int a[101]={};
      for(int j=0;j<N;++j) ++a[n[i][j]];
      for(int j=0;j<N;++j) if(a[n[i][j]]<2) p[j]+=n[i][j];
  }
  for(int i=0;i<N;++i) cout<<p[i]<<endl;
  return 0;
}

Measured memory_bytes: 1224
#include<bits/stdc++.h>
#define ll long long 
#define ld long double
#define X first
#define Y second
#define pb push_back
#define max_el(x) max_element(x.begin(),x.end())-x.begin()
#define min_el(x) min_element(x.begin(),x.end())-x.begin()
#define mp make_pair
#define endl '\n'
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
// DONT USE MEMSET, USE VECTORS

bool vowel(char c){
	return (c=='a' || c=='e' || c=='i' || c=='o' || c=='u'
		 || c=='A' || c=='E' || c=='I' || c=='O' || c=='U');
}

void solve(){
	char c;
	cin>>c;
	if(vowel(c)){
		cout<<"vowel"<<endl;
	}
	else{
		cout<<"consonant"<<endl;
	}
}

int main(){
	fastread;
	int t = 1;
	// cin>>t;
	for(int i=1;i<=t;i++){
		// cout<<"Case #"<<i<<": ";
		solve();
	}
	return 0;
}


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

int tot, n, x, t, ans;

int main() {
	scanf ("%d %d %d", &n, &x, &t);
	while (tot < n) {
		tot += x;
		ans += t;
	}
	printf ("%d\n", ans);
	return 0;
}

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

using namespace std;

#define boost ios::sync_with_stdio(0);cin.tie(0);
#define debug(s) cout << #s << " = " << s << endl
#define forn(i,n) for ( int i=0 ; i < n ; i++ )
#define all(a) (a).begin(), (a).end()
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define ll long long
#define endl '\n'
#define mod 1000000007

int main()
{
    //freopen ("f.in","r",stdin);
    //freopen ("f.out","w",stdout);
    boost
    //code
    int n,k;
    cin >> n >> k;
    vector<ll> v(n);
    forn(i,n) cin >> v[i];
    vector<ll> final;
    forn(i,n){
        ll here = 0;
        for(int j=i;j<n;j++){
            here += v[j];
            final.PB(here);
        }
    }
    for(int j=42;j>=0;j--){
        ll mask = 1LL<<j;
        vector<ll> here;
        ll count = 0;
        forn(i,final.size()){
            if(final[i]&mask){
                here.PB(final[i]);
            }
        }
        if(here.size()>=k){
            swap(here,final);
        }
    }
    ll ans = 0;
    if(final.size()>=1){
        ans = final[0];
        for(int i=1;i<min(k,(int)final.size());i++) ans = ans&final[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6512
<?php
$n = trim(fgets(STDIN));
for($i = 0; $i < $n; $i++){
    $data[] = explode(" ", trim(fgets(STDIN)));
}
$maxH = 0;
for($i = 0; $i < $n; $i++){
    $maxH = max($maxH, $data[$i][2]);
}

for($x = 0; $x <= 100; $x++){
    for($y = 0; $y <= 100; $y++){
        for($h = $maxH; $h <= $maxH+100; $h++){
            foreach($data as $i => $d){
                list($X, $Y, $H) = $d;
                if($H != max(0, $h - abs($X-$x) - abs($Y-$y))){
                    break;
                }
                if($i == $n-1){
                    echo "$x $y $h";
                    exit;
                }
            }
        }
    }
}

Measured memory_bytes: 4604
function main(input) {
  input = input.split(" ");
  var n = parseInt(input[0], 10);
  var r = parseInt(input[1], 10);

  if (n > 9) {
    console.log(r);
  } else {
    console.log(r + 100 * (10 - n));
  }
  
}

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

Measured memory_bytes: 7624
use std::io::prelude::*;
use std::io::stdin;
use std::str::FromStr;

fn main() {
    let n: usize = read();
    let a: Vec<i32> = (0..n).map(|_| read()).collect();

    let mut count = 1;
    let mut ans = 0;
    let mut prev_color = a[0];

    for &a_i in a.iter().skip(1) {
        if prev_color == a_i {
            count += 1;
        } else {
            ans += count / 2;
            prev_color = a_i;
            count = 1;
        }
    }
    ans += count / 2;

    println!("{}", ans);
}

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let token: String = stdin
        .lock()
        .bytes()
        .map(|b| b.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().unwrap()
}


Measured memory_bytes: 4352