akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define F first
#define S second
#define MP make_pair
#define pb push_back
#define endl '\n'

using namespace std;

typedef long long LL;
typedef pair< int, int > P;
typedef pair< LL, LL > LP;
typedef pair< int, P > iP;
typedef pair< P, P > PP;

static const int INF = INT_MAX;
static const LL LINF = LLONG_MAX;
static const int MIN = INT_MIN;
static const LL LMIN = LLONG_MIN;
static const int MOD = 1000000007;

int dx[] = {0, -1, 1, 0};
int dy[] = {-1, 0, 0, 1};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector< P > v;
    for( int i = 0; i < n; ++i ) {
        int a, b;
        cin >> a >> b;
        v.pb( MP( a, b ) );
    }

    vector< P > cp;
    for( int i = 0; i < m; ++i ) {
        int x, y;
        cin >> x >> y;
        cp.pb( MP( x, y ) );
    }

    for( int i = 0; i < v.size(); ++i ) {
        int mval = INF, mpos;
        for( int j = cp.size() - 1; j >= 0; --j ) {
            if( mval >= abs( v[i].F - cp[j].F ) + abs( v[i].S - cp[j].S ) ) {
                mval = abs( v[i].F - cp[j].F ) + abs( v[i].S - cp[j].S );
                mpos = j;
            }
        }
        cout << mpos + 1 << endl;
    }


    return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include <string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>

#define ok printf("ok\n");
#define MAX 1000000
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(g);(i)--)
#define all(a) (a).begin(),(a).end()
#define pb push_back

using namespace std;

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;

int main()
{
	int a,b,c,d;
	string s,t;
	vi v,w;
	cin >> a >> b >> c >> d;
	if(a+b < c+d)
		cout <<"Right";
	else if(a+b==c+d)
		cout <<"Balanced";
	else
		cout << "Left";
	
	return 0;
}

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

int main() {
    int N, K, cnt[MAXK + 3];

    cin >> N >> K;

    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= N; i++)
        cnt[i%K] += 1;

    LL answer = 0;
    for (int i = 0; i < K; i++) {
        if ((2 * i)%K == 0) {
            LL temp = (LL) cnt[i] * cnt[i] * cnt[i];
            answer += temp;
        }
    }

    cout << answer << endl;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

int main()
{
    int n, x = 0, mx = 0;
    string s;
    cin >> n;
    cin >> s;

    for (int i = 0; i < n; ++i) {
        if (s[i] == 'I') ++x;
        else --x;
        mx = (x > mx) ? x : mx;
    }
    cout << mx << endl;

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;

namespace A
{
    public class Node
    {
        public int left;
        public int right;
        public int value;
        public Tree tree;
    }

    public class Tree
    {
        List<Node> nodes;

        public Tree()
        {
            nodes = new List<Node>();
        }

        public void Insert(int x)
        {
            if (nodes.Count == 0) Insert(x, -1);
            else Insert(x, 0);
        }
        public bool Find(int x)
        {
            if (nodes.Count == 0) return false;
            else return Find(x, 0);
        }

        public void Preorder(int node)
        {
            Console.Write(" " + nodes[node].value);
            if (nodes[node].left != -1) Preorder(nodes[node].left);
            if (nodes[node].right != -1) Preorder(nodes[node].right);
        }
        public void Inorder(int node)
        {
            if (nodes[node].left != -1) Inorder(nodes[node].left);
            Console.Write(" " + nodes[node].value);
            if (nodes[node].right != -1) Inorder(nodes[node].right);
        }
        private void Insert(int x, int parent)
        {
            if (parent == -1) nodes.Add(NewNode(x));
            else
            {
                if (nodes[parent].value > x)
                {
                    if (nodes[parent].left == -1)
                    {
                        nodes.Add(NewNode(x));
                        nodes[parent].left = nodes.Count - 1;
                    }
                    else Insert(x, nodes[parent].left);
                }
                else
                {
                    if (nodes[parent].right == -1)
                    {
                        nodes.Add(NewNode(x));
                        nodes[parent].right = nodes.Count - 1;
                    }
                    else Insert(x, nodes[parent].right);
                }
            }
        }
        private bool Find(int x, int node)
        {
            if (node == -1) return false;
            if (nodes[node].value == x) return true;
            else
            {
                if (nodes[node].value > x) return Find(x, nodes[node].left);
                else return Find(x, nodes[node].right);
            }
        }
        private Node NewNode(int value)
        {
            return new Node() { value = value, left = -1, right = -1, tree = this };
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var tree = new Tree();
            for (int i = 0; i < n; i++)
            {
                var strs = Console.ReadLine().Split(' ');
                if (strs[0][0] == 'i') tree.Insert(int.Parse(strs[1]));
                else if (strs[0][0] == 'p')
                {
                    tree.Inorder(0); Console.WriteLine();
                    tree.Preorder(0); Console.WriteLine();
                }
                else Console.WriteLine(tree.Find(int.Parse(strs[1])) ? "yes" : "no");
            }
        }
    }
}

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

int n, dp[100005], a[100005];

int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dp[n - 1] = 0;
      dp[n - 2] = abs(a[n - 2] - a[n - 1]);
      for (int i = n - 3; i > -1; i--)
        dp[i] = min(abs(a[i + 2] - a[i]) + dp[i + 2], abs(a[i + 1] - a[i]) + dp[i + 1]);
      cout << dp[0];
      return 0;
}

Measured memory_bytes: 1024
import collections
n = int(input())
v = list(map(int,input().split()))
v1 = [v[2*i] for i in range(n//2)]
v2 = [v[2*i+1] for i in range(n//2)]
c1 = collections.Counter(v1)
c2 = collections.Counter(v2)
c1most = c1.most_common()[0]
c2most = c2.most_common()[0]
if int(c1most[0]) != int(c2most[0]):
    print(n - int(c1most[1]) - int(c2most[1]))
elif c1most[1] == n//2 and c2most[1] == n//2:
    print(n//2)
elif c1most[1] == n//2:
    print(n//2 - int(c2.most_common()[1][1]))
elif c2most[1] == n//2:
    print(n//2 - int(c1.most_common()[1][1]))
else:
    c1most2 = c1.most_common()[1]
    c2most2 = c2.most_common()[1]
    if int(c1most2[1]) >= int(c2most2[1]):
        print(n - int(c1most2[1]) - int(c2most[1]))
    else:
        print(n - int(c2most2[1]) - int(c1most[1]))

Measured memory_bytes: 19040
/*** akshaykumar99 ***/
 
#include<bits/stdc++.h> 
using namespace std;
 
const long long MOD = 998244353;
const long double PI = acos(-1);
const long long N = 2e5+1;
 
typedef long long ll;
typedef long double ld;

void test_case()
{
	ll n, x, m;
	cin >> n >> x >> m;
	if(x == 0 || m == 1)
	{
		cout << x << '\n';
		return;
	}
	ll ans = x, prev = x, curr = 0;
	vector<bool> done(m+1, 0);
	done[x] = 1;
	ll ind = 0;
	for(ll i = 2; i <= n; i++)
	{
		curr = prev * prev % m;
		if(done[curr])
		{
			ind = i;
			break;
		}
		done[curr] = 1;
		ans = curr + ans;
		prev = curr;
		if(curr == 0)
			break;
	}
	if(ind == 0 || curr == 0)
	{
		cout << ans << '\n';
		return;
	}
	ll left = n - ind + 1;
	ll z = curr;
	vector<ll> vv = {curr};
	ll sum = curr;
	while(1)
	{
		z = z * z % m;
		if(z == curr)
			break;
		sum += z;
		vv.push_back(z);
	}
	ll nn = vv.size();
	// cout << ind << ' ' << left << ' ' << nn << ' '; 
	ll tot = left / nn;
	// cout << sum * tot << ' ';
	ans = ans + sum * tot;
	left = left % nn;
	for(int i = 0; i < left; i++)
	{
		ans += vv[i];
	}
	cout << ans << '\n';
}
 
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    ll tc=1;
    // cin>>tc;
    while(tc--)
        test_case();
    return 0;
}


Measured memory_bytes: 3868
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{
	public static void main(String[] args) throws IOException {
		try (BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in))) {

			String in = br.readLine();
			String chr[] = in.split("");
			System.out.println(chr[0].equals("9")||chr[1].equals("9")?"Yes":"No");

		}
	}
}

Measured memory_bytes: 25216
#include <bits/stdc++.h>
#define MOD 1000000007LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int n;

int main(void){
	scanf("%d",&n);
	for(int x=1;x<=n;x++){
		int nx=x*108/100;
		if(nx==n){
			printf("%d\n",x);
			return 0;
		}
	}
	printf(":(\n");
	return 0;
}


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

string divide[4] = {"dream","dreamer","erase","eraser"};

int main(){
	int N; //山の数
	cin >> N;
	vector<int> H(N); //山の高さ
	for(int i = 0; i < N; i++){
		cin >> H[i]; //高さを順番に入力
	}
	//1番目の山の高さと同じかそれより高い山を数える
	int count = 0;
	int max = 0; //一番高い山の高さを入れる変数
	for(int i = 0; i < N; i++){
		if(max < H[i]){
			max = H[i];
		}
		if(max <= H[i]){
			count++;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  long long a, b, x;
  long long n, m;
  
  scanf("%lld %lld %lld", &a, &b, &x);

  printf("%lld\n", (b / x) - ((a + x - 1) / x) + 1);
  
  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

class Main{
  public static void main (String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int[] num_list = new int[n];
    for (int i = 0; i < n; i++){
      num_list[i] = sc.nextInt();
    }
    selection_sort(num_list, n);
  }

  public static void output(int[] lst, int n){
    for (int i = 0; i < n; i++){
      if (i == n - 1){
        System.out.println(lst[i]);
      }else{
        System.out.print(lst[i] + " ");
      }
    }
  }

  public static void selection_sort(int[] lst, int n){
    int count = 0;
    for (int i = 0; i < n; i++){
      int minj = i;
      for (int j = i;j < n; j++){
        if (lst[j] < lst[minj]){
          minj = j;

        }
      }
      if (minj != i){
        int tmp = lst[i];
        lst[i] = lst[minj];
        lst[minj] = tmp;  
        count ++;  
      }

    }
    output(lst, n);
    System.out.println(count);
  }
}



Measured memory_bytes: 26272
#include <stdio.h>
#include <string.h>

typedef struct Dice {
	int north,south,east,west,top,bottom;
} Dice;

typedef void (*DiceCmd)(Dice* dp);

void turn_north(Dice* dp){
	int tmp;

	tmp = dp->top;
	dp->top = dp->south;
	dp->south = dp->bottom;
	dp->bottom = dp->north;
	dp->north = tmp;
}

void turn_south(Dice* dp){
	int tmp;

	tmp = dp->top;
	dp->top = dp->north;
	dp->north = dp->bottom;
	dp->bottom = dp->south;
	dp->south = tmp;
}

void turn_east(Dice* dp){
	int tmp;

	tmp = dp->top;
	dp->top = dp->west;
	dp->west = dp->bottom;
	dp->bottom = dp->east;
	dp->east = tmp;
}

void turn_west(Dice* dp){
	int tmp;

	tmp = dp->top;
	dp->top = dp->east;
	dp->east = dp->bottom;
	dp->bottom = dp->west;
	dp->west = tmp;
}

void clockwise(Dice* dp){
	int tmp;

	tmp = dp->south;
	dp->south = dp->east;
	dp->east = dp->north;
	dp->north = dp->west;
	dp->west = tmp;
}

void anticlockwise(Dice* dp){
	int tmp;

	tmp = dp->south;
	dp->south = dp->west;
	dp->west = dp->north;
	dp->north = dp->east;
	dp->east = tmp;
}

int main(int argc, char** argv){
	Dice d;
	int q_cnt,q_top,q_south;
	DiceCmd dice_cmd[] = { turn_north, turn_north, turn_north, turn_east, turn_east, turn_east  };
	int i;

	// Input
	scanf("%d",&d.top);
	scanf("%d",&d.south);
	scanf("%d",&d.east);
	scanf("%d",&d.west);
	scanf("%d",&d.north);
	scanf("%d",&d.bottom);

	// Solve
	scanf("%d",&q_cnt);
	while(q_cnt-->0){
		// Input Quest
		scanf("%d%d",&q_top,&q_south);

		// Turn
		i = 0;
		while( d.top != q_top ){
			dice_cmd[i](&d);
			i++;
		}
		while( d.south != q_south ){
			clockwise(&d);
		}

		// Output
		printf("%d\n",d.east);
	}

	return 0;
}

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

// マクロ
// forループ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(ll)(b);i--)
// xにはvectorなどのコンテナ
#define ALL(x) (x)begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
// 出力
#define PRINT(x) cout<<(x)<<endl
#define PRINTA(x,n) REP(i,n)PRINT(x[i])
// 定数
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
// 略記
#define PB push_back
#define MP make_pair



int main() {
    string S; cin >> S;
    if (S == "ABC") cout << "ARC" << endl;
    else cout << "ABC" << endl;
    return 0;
}

Measured memory_bytes: 3596
A,B,C,X,Y = list(map(int,input().split()))
c = [X,Y]
total = 0
if A+B >= 2*C:
  total += 2*C*(min(c))
  if X > Y:
    if A >= 2*C:
      total += 2*C*(X-Y)
    else:
      total += A*(X-Y)
  else:
    if B >= 2*C:
      total += 2*C*(Y-X)
    else:
      total += B*(Y-X)
else:
  total += A*X + B*Y

print(total)

Measured memory_bytes: 3064
import bisect
from operator import itemgetter
import math
import copy
import collections
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
d = IL()
d.sort()
num = N//2

print(d[num] - d[num-1])

Measured memory_bytes: 23388
package main

import (
	"fmt"
	"math"
)

func main() {
	var n int
	fmt.Scan(&n)

	a := make([]float64, n)
	sum := 0.0
	for i := 0; i < n; i++ {
		fmt.Scan(&a[i])
		sum += a[i]
	}

	ans := 0
	m := round(sum / float64(n))
	for i := 0; i < n; i++ {
		ans += int(math.Pow(math.Abs(m-a[i]), 2))
	}
	fmt.Println(ans)
}

func round(f float64) float64 {
	return math.Floor(f + .5)
}


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

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using ii = pair<int, int>;
using vii = vector<ii>;

#define rep(i, n)   for (int i = 0; i < (n); i++)
#define sz(x)       (int)x.size()
#define eb          emplace_back
#define pb          push_back
#define all(x)      x.begin(), x.end()
#define rall(x)     x.rbegin(), x.rend()
#define fi          first
#define se          second

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef LOCAL
    freopen("io\\in.txt", "r", stdin);
    freopen("io\\out.txt", "w", stdout);
#endif

    int n;
    cin >> n;
    vii a(n);
    rep(i, n) cin >> a[i].fi >> a[i].se;

    vii b(n);
    rep(i, n) b[i] = {a[i].fi + a[i].se, a[i].fi - a[i].se};
    sort(all(b));

    int cnt = 0, x = -(1 << 30);
    rep(i, n) {
        if (x <= b[i].se) x = b[i].fi, cnt++;
    }
    cout << cnt;

    return 0;
}


Measured memory_bytes: 4784
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
    int n,k,s;
    cin >> n >> k >> s;
    vector<int> ans(n);
    if(s<1e9){
        for(int i=0;i<n;i++){
            if(i<k)
                ans[i] = s;
            else
                ans[i] = s+1;
        }
    }
    else{
        for(int i=0;i<n;i++){
            if(i<k)
                ans[i] = s;
            else
                ans[i] = 1;
        }
    }
    for(int i=0;i<n;i++){
        cout << ans[i] << endl;
    }
    return 0;
}

Measured memory_bytes: 1664
Q = int(input())
querys = [tuple(map(int, input().split())) for _ in range(Q)]

anss = []
for A, B in querys:
    if A > B:
        A, B = B, A

    if A == B:
        ans = 2*(A-1)
    elif A+1 == B:
        ans = 2*(A-1)
    else:
        C = -(-((A*B)**0.5) // 1) - 1
        if C*(C+1) >= A*B:
            ans = 2*(C-1)
        else:
            ans = 2*C-1

    anss.append(int(ans))

print('\n'.join(map(str, anss)))


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

#define ll long long
#define db double
#define el "\n"
#define ld long double
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define tr(ds, it) for(auto it=ds.begin(); it!=ds.end(); it++)
#define rtr(ds, it) for(auto it=ds.rbegin(); it!=ds.rend(); it--)
#define all(ds) ds.begin(), ds.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
typedef priority_queue <int> pq;
typedef vector< long long > vi;
typedef pair<long long, long long> ii;

const ll mod = 1000000007;
ll po(ll x, ll n ){ 
	ll ans=1;
     while(n>0){
     	if(n&1) ans=(ans*x)%mod;
     	x=(x*x)%mod;
     	n/=2;
     }
     return ans;
}



int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T=1;
	//cin >> T;
	while(T--){
		ll r1,c1,r2,c2,x1,x2,x3,x4,d1,d2,d3,d4;
		cin>>r1>>c1>>r2>>c2;
		ll f=1;
		rep_a(i,1,2000005){
			f*=i;
			f%=mod;
			if(i==r2+c2+2) x1=f;
			if(i==r2+c1+1) x2=f;
			if(i==r1+c2+1) x3=f;
			if(i==r1+c1) x4=f;
			if(i==r2+1) d1=f;
			if(i==c2+1) d2=f;
			if(i==r1) d3=f;
			if(i==c1) d4=f;
		}
		ll ans=0;
		ans=(((x1*po(d1,mod-2))%mod)*po(d2,mod-2))%mod;
		ans%=mod;
		ans-=(((x2*po(d1,mod-2))%mod)*po(d4,mod-2))%mod;
		if(ans<0) ans+=mod;
		ans%=mod;
		ans-=(((x3*po(d3,mod-2))%mod)*po(d2,mod-2))%mod;
		if(ans<0) ans+=mod;
		ans%=mod;
		ans+=(((x4*po(d3,mod-2))%mod)*po(d4,mod-2))%mod;
		ans%=mod;
		cout<<ans<<el;
	}

	return 0;
}

Measured memory_bytes: 256
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,j,n) for(int i = j; i < n; i++)
#define RFOR(i,j,n) for(int i = j-1; i >= n; i--)
#define PREC(n) fixed << setprecision(n)
#define print_array(v) REP(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define _LIBCPP_DEBUG 0
using namespace std;
int64_t MOD = 1000000007;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int w, a, b;
  cin >> w >> a >> b;
  int mini = min(a,b);
  int maxi = max(a,b);
  mini += w;
  int res = maxi - mini;
  if(res < 0) res = 0;
  cout << res << endl;
  return 0;
}
//templete by private_yusuke

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

typedef long long   ll;
typedef long double ld;

using namespace std;
const ld pi=2*acos(0.0);
ll mod = 998244353;

int main() {
 //    freopen("input.txt", "r", stdin);
 //    freopen("output.txt", "w", stdout);
 // ios::sync_with_stdio(0);
 // cin.tie(0);
    string k = "keyence";
    string s;
    cin >> s;
    string ss = s;
    string kk = k;
    reverse(kk.begin(), kk.end());
    reverse(ss.begin(), ss.end());
    if(s.substr(0, k.size()) == k || ss.substr(0, k.size()) == kk)
        return puts("YES") * 0;
    string q;
    for(int i = 1; i < k.size(); i ++){
        if(k.substr(0, i) == s.substr(0, i) && kk.substr(0, k.size() - i) == ss.substr(0, k.size() - i))
            return puts("YES") * 0;
    }
    return puts("NO") * 0;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define pb push_back
using namespace std;


const int mod = 1000000007, E = 26, maxN = 100042;

inline void add_mod(long long& a, long long b)	{   a = (a + b) % mod;  }
inline void mult_mod(long long& a, long long b)	{   a = a * b % mod;    }

long long cnt[E];
char T[maxN];

int main()
{
	FOR(i, 0, E)
		cnt[i] = 1;
	long long res = 0;

	int n;
	scanf ("%d", &n);
	scanf ("%s", T);
	FOR(i, 0, n)
	{
		long long temp = 1;
		FOR(j, 0, E)
			if (j != T[i]-'a')
				mult_mod(temp, cnt[j]);
		add_mod(res, temp);
		cnt[T[i] - 'a']++;	
	}

	printf("%lld\n", res);
    return 0;
}


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

using namespace std;

#define rep(i, a, b)  for(int i = (a); i < (b); i++)
#define rrep(i, a, b) for(int i = (a); i > (b); i--)
#define sq(x) ((x) * (x))
#define bit(x) bitset<32>(x)
#define vsort(v)  sort(v.begin(), v.end())
#define rvsort(v) sort(v.begin(), v.end(), greater<llint>())
#define debug(x) cout << #x << " " << (x) << endl
#define ci cin
#define co cout
#define en endl
#define ln cout<< '\n'
#define pb push_back
#define fi first
#define se second
#define MOD 1000000007

typedef long long int llint;
typedef pair<int, int> pii;
typedef pair<llint, llint> pll;
typedef vector<int> vi;
typedef vector<llint> vl;
typedef vector<pii> vii;
typedef vector<pll> vll;


template<typename Tn> Tn __lcm(Tn a, Tn b)
{
    return a / __gcd(a, b) * b;
}

struct UF
{
    vi par, sizes;

    UF() {}
    UF(int size) : par(size, -1), sizes(size, 1) {
        for(int i = 0; i < size; i++) par[i] = i;
    }

    int root(int x)
    {
        return par[x] == x ? x : par[x] = root(par[x]);
    }

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

    int size(int x)
    {
        return sizes[root(x)];
    }

    void unite(int x, int y)
    {
        x = root(x);
        y = root(y);

        if(x == y) return ;

        if(sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
        sizes[y] = 0;
    }
};

int n, m;
vi x(100001);
vi y(100001);
vi z(100001);

int main()
{
    ci >> n >> m;

    UF uf(n + 1);
    
    rep(i, 0, m) {
	ci >> x[i] >> y[i] >> z[i];
	uf.unite(x[i], y[i]);
    }

    int ans = n;
    vi used(n + 1, 0);

    rep(i, 1, n + 1) {
	int par = uf.root(i);
	if(used[par] == 0) used[par] = 1;
	else ans--;
    }
    
    co << ans << en;
    
    return 0;
}


Measured memory_bytes: 2560
///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1e5 + 10; 
const int mod = 1e9 + 7;

char s[N]; 
int dp[N][2], n; 

int f(int i, int small) {
    if(i == n) return 1;
    int &ret = dp[i][small]; 
    if(~ret) return ret; 

    ret = 0; 

    for(int a = 0; a <= 1; ++a) {
        for(int b = 0; b <= 1; ++b) {
            if(a && b) continue; 

            int c = a ^ b;

            if(small || c <= s[i]) {
                ret += f(i + 1, small | (c < s[i])); 
                if(ret >= mod) ret -= mod;
            }
        }
    }

    return ret;
}

int main(int argc, char const *argv[]) {
    scanf("%s", s);
    n = strlen(s); 

    for(char &c : s) c -= '0';

    memset(dp, -1, sizeof dp); 

    printf("%d\n", f(0, 0));
}

Measured memory_bytes: 8960
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <string.h>
#define REP(i,n) for(int i=0;i<(int)n;i++)
#define REP1(j,n) for(int j=0;j<(int)n;j++)
#define REPD(i,n) for(int i=n;i>=0;i--)
#define REPD1(j,n) for(int j=n;j=>0;j--)
#define REPS(i,n) for(int i=1;i<=(int)n;i++)
#define REPS1(j,n) for(int j=1;j<=(int)n;j++)
#define rep(i,a,n) for(int i=a;i<(int)n;i++)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define DescSort(a) sort(a.begin(),a.end(),std::greater<int>())

using namespace std;
typedef long long ll;

int main(void) {
	string s;
	int ans=0;
	cin >> s;
	REP(i, 4) {
		if (s[i] == '+') ans++;
		else ans--;
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using ll = long long;

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; }
const ll LINF = 1e18;

int main()
{
  int K, X; cin >> K >> X;
  cout << (500*K>=X ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
a = int(input())
b = list(map(int,input().split()))
test_dict = {}
for i in range(a):
    test_dict[i+1] = b[i]
score_sorted = sorted(test_dict.items(), key=lambda x:x[1])
ans = ''
for i in score_sorted:
    ans += str(i[0])+' '
print(ans)

Measured memory_bytes: 26204
import sys
import math
import collections
import itertools
import array
import inspect
import functools

# Set max recursion limit
sys.setrecursionlimit(1000000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in sys.stdin.readline().split()]


def gcd(n, m):
    if n % m == 0:
        return m
    else:
        return gcd(m, n % m)


def gcd_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = gcd(v, L[i])

    return v


def lcm(n, m):
    return (n * m) // gcd(n, m)


def lcm_list(L):
    v = L[0]

    for i in range(1, len(L)):
        v = lcm(v, L[i])

    return v

def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2, r + 1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p - 1, r, p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def bisearch(L, target):
    low = 0
    high = len(L) - 1
    
    while low <= high:
        mid = (low + high) // 2
        guess = L[mid]
        if guess == target:
            return True
        elif guess < target:
            low = mid + 1
        elif guess > target:
            high = mid - 1
    if guess != target:
        return False

# --------------------------------------------

dp = None


def main():
    x, y = li_input()

    if (x + y) % 3 != 0:
        print(0)
        return

    n = 0
    m1, m2 = 0, 0
    while x != 0 and y != 0:
        n += 1
        if x >= y:
            x -= 2
            y -= 1
            m1 += 1
        else:
            x -= 1
            y -= 2
            m2 += 1

    if not (x == 0 and y == 0):
        print(0)
        return(0)

    print(comb(n, m1) % (10 ** 9 + 7))


main()


Measured memory_bytes: 45732
#include<iostream>
#include<stdio.h>//printf("%.9f\n",*********);
#include<vector>//文字列.erase(n)
#include<algorithm>//next_permutation
#include<set>
#include<string>//char(小文字-32=大文字) to_string
#include<sstream>
#include<complex>
#include<time.h>
#include<random>
#include<cmath>
#include<math.h>
#include<queue>
#include<time.h>
#include<iomanip>
#include<locale>
#include<utility>//swap
#define rt "\n"
#define rep(i,n) for(int i=0;i<n;i++)
#define rop(i,n) for(int i=1;i<=n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define drop(i,n) for(int i=n;0<i;i--)
#define yes(ans) if(ans)cout<<"yes"<<rt;else cout<<"no"<<rt;
#define Yes(ans) if(ans)cout<<"Yes"<<rt;else cout<<"No"<<rt;
#define YES(ans) if(ans)cout<<"YES"<<rt;else cout<<"NO"<<rt;
#define Yay(ans) if(ans)cout<<"Yay!"<<rt;else cout<<":("<<rt;
#define sec(a,b,ans) if(ans)cout<<a<<rt;else cout<<b<<rt;
#define vcin(s,n) rep(i,n)cin>>s[i];//vcin(配列名),(繰り返し回数)
#define sort(s) sort(s.begin(),s.end())//標準=昇順
#define reve(s) reverse(s.begin(),s.end())
#define asas int ans=0
#define str string
#define please return
#define AC 0
#define rapid_pleaseAC_fast cin.tie(0);ios::sync_with_stdio(false)
#define pi 3.1415926535897932384626
#define nine 1000000000

using namespace std;
typedef vector<int> vint;
typedef long double ldouble;
typedef vector<string> vstr;
typedef vector<char> vchar;
typedef vector<double> vdou;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<char>> vvchar;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<string>> vvstr;
typedef vector<vector<bool>> vvbool;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;

long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
	return a * b / GCD(a, b);
}

unsigned GetDigit(unsigned num) {
	return std::to_string(num).length();
}

int tow(int n) {//2のn乗
	if (n == 0)return 1;
	int x = tow(n / 2);
	x *= x;
	if (n % 2 == 1)x *= 2;
	return x;//@domino
}

int SED(int n) { //Sum of each digit
	int sum = 0;
	while (n > 0) {
		sum += n % 10; n /= 10;
	}
	return sum;
}

/*

 (char)toupper(a[n])=文字列のn文字目を大文字で出力

  pow(a,b)=aのb乗

  */


int main(void) {

	int n;
	cin >> n;
	vint b(n - 1);
	vcin(b,n - 1);

	int sum = b[0];

	rep(i, n - 2) {
		if (b[i] > b[i + 1]) {
			sum += b[i + 1];
		}
		else {
			sum += b[i];
		}
	}
	sum += b[n - 2];

	cout << sum << rt;

	please AC;
}

Measured memory_bytes: 256
N = int(input())
A = map(int, input().split())
C = [0]*N
for a in A:
    C[a - 1] += 1
D = [0]*(N + 1)
for c in C:
    D[c] += 1

Dk_accum = [0]*(N + 1)
for i in range(1, N + 1):
    Dk_accum[i] = Dk_accum[i - 1] + i*D[i]
    
D_sum = sum(D)
D_accum = [0]*(N + 2)
D_accum[0] = D_sum
for i in range(1, N + 1):
    D_accum[i] = D_accum[i - 1] - D[i - 1]
    
F = [0]*(N + 1)
for i in range(1, N + 1):
    F[i] = (Dk_accum[i]//i + D_accum[i + 1])

i = N
for K in range(1, N + 1):
    while i > 0 and K > F[i]:
        i -= 1
    print(i)
        

Measured memory_bytes: 28252
# -*-coding: utf-8 -*-
N, M = map(int, input().split())

ab = [0] * N 
for i in range(N):
    ab[i] = list(map(int, input().split()))

ab = sorted(ab)
honsu = 0
money = 0
flag = False
for i in range(N):
    if flag:
        break
    count = ab[i][1]
    for k in range(count):
        if honsu == M:
            flag = True
            break
        else:
            money += ab[i][0]
            honsu += 1
print(money)

Measured memory_bytes: 28652
#include <iostream>
#include <string>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#define int long long
using namespace std;

void printVector(const vector<int>& vec) {
    for (int value : vec) {
        cout << value << " ";
    }
    cout << endl;
}

signed main() {

    string s;
    int n;
    set<char> S;

    cin >> s;
    n = s.length();
    for(int i = 0; i < n; i ++){
        S.insert(s[i]);
    }
    if(n == S.size()) cout << "yes";
    else cout << "no";
    return 0;
}

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

#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for (int i = x; i < n; i++)
#define OP(m) cout << m << endl
typedef long long ll;
typedef unsigned long long ull;

int main()
{
    int n;
    cin >> n;
    OP(n * n * n);
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main()
{	
	int N, Q;
	char S[1000001];
	scanf("%d", &N);
	scanf("%s", S);
	scanf("%d", &Q);
	
	int i, k, q;
	long long ans, tmp[3];
	for (q = 1; q <= Q; q++) {
		scanf("%d", &k);
		ans = 0;
		tmp[0] = 0;
		tmp[1] = 0;
		tmp[2] = 0;
		
		for (i = 0; i < k; i++) {
			if (S[i] == 'D') tmp[0]++;
			else if (S[i] == 'M') {
				tmp[1]++;
				tmp[2] += tmp[0];
			} else if (S[i] == 'C') ans += tmp[2];
		}
		for (; S[i] != 0; i++) {
			if (S[i-k] == 'D') {
				tmp[0]--;
				tmp[2] -= tmp[1];
			} else if (S[i-k] == 'M') tmp[1]--;
			if (S[i] == 'D') tmp[0]++;
			else if (S[i] == 'M') {
				tmp[1]++;
				tmp[2] += tmp[0];
			} else if (S[i] == 'C') ans += tmp[2];
		}
		
		printf("%lld\n", ans);
	}
	
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 2672
while 1:
    n = int(raw_input())
    if n == 0: break
    w,h = map(int, raw_input().split())
    #print w,h
    tree = [[0 for j in xrange(w)] for i in xrange(h)]
    for i in xrange(n):
        a,b = map(int, raw_input().split())
        tree[b-1][a-1] = 1
    s,t = map(int, raw_input().split())
    p = []
    for i in xrange(w-s+1):
        for j in xrange(h-t+1):
            temp = 0
            for k in xrange(i, s+i):
                for l in xrange(j, t+j):
                    temp += tree[l][k]
                p.append(temp)
    print max(p)

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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rInt(a) scanf("%d",&a);


main(){
    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);
    if((b-a)%2==1) cout << "Borys" << endl;
    else cout << "Alice" << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#define maxn 200010
#define N maxn / 26 + 10
char s[maxn];
int l[N], r[N];
int cnt[26];
int sum[maxn][26], nxt[maxn][26];
int n, m, sz, ans;
char find(int r, int l = 0) {
	for (int i = 0; i < 26; i++) if (!(sum[r][i] - sum[l][i])) return i + 97;
	return 20040826;
}
int main() {
	sz = sizeof cnt;
	scanf("%s", s + 1);
	n = strlen(s + 1);
	int num = 0; r[m = 1] = n;
	for (int i = n; i; i--) {
		memcpy(nxt[i], nxt[i + 1], sz);
		int x = s[i] - 'a';
		nxt[i][x] = i;
		num += cnt[x]++ == 0;
		if (num >= 26) {
			l[m] = i;
			r[++m] = i - 1;
			memset(cnt, 0, sz);
			num = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		memcpy(sum[i], sum[i - 1], sz);
		sum[i][s[i] - 'a']++;
	}
	putchar(ans = find(r[m]));
	for (int i = m - 1; i; i--) putchar(ans = find(r[i], nxt[l[i]][ans - 'a']));
	putchar(10);
	return 0;
}
 

Measured memory_bytes: 41088
while 1:
        p=0
        e=map(int,raw_input().split())
        if e[0]==e[1]==0:
                break
        for i in range(e[0]):
                for j in range (e[0]):
                        for k in range (e[0]):
                                if i+j+k+3==e[1] and i!=j and j!=k and i<j<k:
                                        p+=1
        print p

Measured memory_bytes: 4228
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int main() {
    int N, Y;
    cin >> N >> Y;
    
    int a=-1, b=-1, c=-1;
    for (int i=0; i<=N; ++i) {
        for (int j=0; j<=N-i; ++j){
            int total = 10000*i + 5000*j + 1000*(N-i-j);
            if (total == Y) {
                a = i;
                b = j;
                c = N-i-j;
            }
        }
    }
    cout << a << " " << b << " " << c << endl;
}


Measured memory_bytes: 256
i,j,k,v,N,A[100];
main(){
    for(scanf("%d",&N);i<N;scanf("%d",&A[i++]));
    for(k=0;k<N;printf("%d%s",A[k],k==N-1?"\n":" "),k++);
    for(i=1;i<N;i++){
        for(j=i-1,v=A[i];A[j]>v;A[j+1]=A[j],j--);
        A[j+1]=v;
        for(k=0;k<N;printf("%d%s",A[k],k==N-1?"\n":" "),k++);
    }
}

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

int main() {
  int K, S;
  cin >> K >> S;
  int ans = 0;
  for (int i=0; i<=K; i++) {
    for (int j=0; j<=K; j++) {
      if (S-i-j <= K && S-i-j >= 0)
        ans ++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
use proconio::marker::*;
use proconio::*;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    };

    let mut ans = 0;

    for &i in a.iter().step_by(2) {
        if i % 2 == 1 {
            ans += 1;
        }
    }

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


Measured memory_bytes: 2132
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author khokharnikunj8
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        arc087_a solver = new arc087_a();
        solver.solve(1, in, out);
        out.close();
    }

    static class arc087_a {
        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt(), temp;
            HashMap<Integer, Integer> hs = new HashMap<>();
            while (n-- > 0) {
                temp = in.scanInt();
                if (!hs.containsKey(temp)) hs.put(temp, 1);
                else hs.put(temp, (hs.get(temp) + 1));
            }
            long ans = 0;
            for (int i : hs.keySet()) {
                temp = hs.get(i);
                if (temp >= i) temp -= i;
                ans += (temp);
            }
            out.println(ans);
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}



Measured memory_bytes: 29024
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define in(a)                       ll a; cin>>a;
#define in2(a,b)                    ll a,b; cin>>a>>b;
#define in3(a,b,c)                  ll a,b,c; cin>>a>>b>>c;
#define in4(a,b,c,d)                ll a,b,c,d; cin>>a>>b>>c>>d;
#define in5(a,b,c,d,e)              ll a,b,c,d,e; cin>>a>>b>>c>>d>>e;
#define lelo(b)                     for(auto &i:b)cin>>i;
#define ff                          first
#define ss                          second
#define call(v)                     v.begin(),v.end()
#define rall(v)                     v.rbegin(),v.rend()
#define show(x)                     for(auto t:x)cout<<t<<" ";
#define pb                          push_back
#define bhar(s,v)                   memset(s,v,sizeof(s))
#define endl                        "\n"                       
#define ce(x)                       cout<<x<<"\n";
#define nl                          cout<<endl;
#define jaldi                       ios_base::sync_with_stdio(false);cin.tie(NULL);
#define dekh_lo                     ce("dekh_lo");
#define sz(x)                       (ll)x.size()
#define re                          return

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<ll,ll> pii;
typedef vector<pii> vii;
typedef vector<ll> vi;

const ll mod=1e9+7;
const ll N=4e5+5;
ll i,j;

/*


*/

void solve(){
    in2(n,k);
    vi a(n+1);
    for(i=1;i<=n;i++){
    	cin>>a[i];
    }
    ll dp[n+1][k+1];
    dp[0][0]=1;
    for(i=1;i<=k;i++){
    	dp[0][i]=0;
    }
    for(i=1;i<=n;i++){
    	vi sum(k+1);
    	sum[0]=dp[i-1][0];
    	for(j=1;j<=k;j++){
    		sum[j]=(sum[j-1]+dp[i-1][j])%mod;
    	}
    	for(j=0;j<=k;j++){
    		if(j<=a[i]){
    			dp[i][j]=sum[j];
    		}
    		else{
    			ll non=j-a[i]-1;
    			dp[i][j]=(sum[j]-sum[non]+mod)%mod;
    		}
    	}
    	sum.clear();
    }
    ce(dp[n][k]);
}

int32_t main(){
    // jaldi
    ll t; 
    // cin>>t;
    t=1;     
    while(t--){
        solve();
    }
}

/*


*/

  

Measured memory_bytes: 83068
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
    public static void main(String[] args){
        FastScanner sc = new FastScanner();
        int k = sc.nextInt();
        String s = sc.next();

        if(s.length() <= k) {
            System.out.println(s);
        }else{
            System.out.println(s.substring(0, k) + "...");
        }


    }

    static class FastScanner {
        private final InputStream in = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            }else{
                ptr = 0;
                try {
                    buflen = in.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long nextLong() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }else if(b == -1 || !isPrintableChar(b)){
                    return minus ? -n : n;
                }else{
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
        public int nextInt() {
            long nl = nextLong();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double nextDouble() { return Double.parseDouble(next());}
    }
}

Measured memory_bytes: 36196
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#include <map>
#define ll long long
#define out(a) printf("%d ",a)
#define ln printf("\n")
const int N=2e5+50;
const int MOD=1e9+7;
const int inf=0x7f7f7f7f;
using namespace std;
int n;
int tot=0,num=0;
int a[N],ans[N],b[N];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	  scanf("%d",&a[i]);
	for (int i=n;i;i--){
	  num=0;
	  for (int j=i;j<=n;j+=i)
	    if (b[j]) num++;
	  if (num%2!=a[i]) b[i]=1,ans[++tot]=i;
	}
	out(tot); ln;
	for (int i=1;i<=tot;i++)
	  out(ans[i]);
	return 0;
}

Measured memory_bytes: 2816
#include<iostream>
#include<algorithm>
#include<vector>
using lint=int64_t;
using namespace std;

int main()
{
	int N;
	int A[100010]={};
	
	cin >> N;
	for(int i=0;i<N;i++)
		cin >> A[i];
	
	int cnt=0;
	int type=0;
	for(int i=1;i<N;i++)
	{
		if(A[i]==A[i-1])continue;
		if(A[i]>A[i-1])
		{
			if(type==0)
				type=1;
			if(type==-1)
			{
				type=0;
				cnt++;
			}
		}
		if(A[i]<A[i-1])
		{
			if(type==0)
				type=-1;
			if(type==1)
			{
				type=0;
				cnt++;
			}
		}
	}
	
	cout << cnt+1 << endl;
	return 0;
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	  
	public static void main(String args[]) {
		    Scanner scanner = new Scanner(System.in);
		    
			int N = scanner.nextInt();
			int K = scanner.nextInt();
			if( N %  K == 0 ) 
			{
				System.out.println(0);
			}
			else 
			{
				System.out.println(1);
			}
		    scanner.close(); }
		  }

Measured memory_bytes: 21972