akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
int main(void){
	int n,k=100000;
	scanf("%d",&n);
	while(n>0){
		n--;
		k*=1.05;
		if(k%1000>0)k=(k/1000+1)*1000;
	}
	printf("%d\n",k);
	return 0;
}

Measured memory_bytes: 592
#include<stdio.h>
int main(void){
	int a[4] = {0};
	int b[4] = {0};
	int i,j,k;
	int counthit = 0;
	int countblow = 0;
	i = 0;
	while(scanf("%d",&a[i]) != EOF){
		for(j = 1;j < 4;j++){
			scanf("%d",&a[j]);
		}
		for(j = 0;j < 4;j++){
			scanf("%d",&b[j]);
		}
		for(j = 0;j < 4;j++){
			if(a[j] == b[j]){
				counthit++;
			}
		}
		printf("%d ",counthit);
		for(j = 0;j < 4;j++){
			for(k = 0;k < 4;k++){
				if(a[j] == b[k]){
					countblow++;
					break;
				}
			}
		}
		printf("%d\n",countblow - counthit);
		counthit = 0;
		countblow = 0;
	}
	return 0;
}

Measured memory_bytes: 596
n = int(input())
a = list(map(int,input().split()))
box = [0] * n
ansli = []
ans = 0
for i in reversed(range(n)):
  if sum(box[i::i+1]) % 2 != a[i]:
    box[i] = not box[i]
    ansli.append(str(i+1))
    ans += 1
print(ans)
print(' '.join(ansli))


Measured memory_bytes: 17224
#include <cstdio>
#include <cmath>
using namespace std;

int n, s;

int main(){
	scanf("%d", &n);
	for(int i = 0; i < n; i++){
		scanf("%d", &s);
		printf("Case %d:\n", i+1);
		for(int j = 0; j < 10; j++){
			int tmp = 0;
			s *= s;
			for(int k = 0; k < 4; k++) tmp += ((s%(int)pow(10,6-k))/(int)pow(10,5-k))*(int)pow(10,3-k);
			printf("%d\n", tmp);
			s = tmp;
		}
	}
}

Measured memory_bytes: 1064
-- abc333.hs --- ABC333

-- author: Seong Yong-ju <sei40kr@gmail.com>

main :: IO ()
main = do
  [a, b] <- map (read :: String -> Int) . take 2 . words <$> getLine
  putStrLn $
    if a `mod` 2 == 1 && b `mod` 2 == 1
      then "Yes"
      else "No"


Measured memory_bytes: 508
#include <stdio.h>
#include <stdlib.h>
#include <math.h>


int main()
{
    int result=0;
    double n, d, x, y, t;

    scanf("%lf %lf \n", &n, &d);

    if(n>=1 && d>=0)
    {
        for(int cont=0; cont< n; cont++)
           {
               scanf("%lf %lf",&x,&y);

               t = sqrt(pow(x,2)+ pow(y,2));

               if(t<=d)
                   {
                      result++;
                   }

           }

    }


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

}


Measured memory_bytes: 2240
#include <cstdio>
#define INF 1e9
#define eps 1e-6
typedef long long ll;

int n, k;
double d[200010], sum[200010], ans;

int main(){

	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++)
		scanf("%lf", &d[i]), d[i] = (1 + d[i]) / 2;
	for(int i = 1; i <= n; i++)
		sum[i] = sum[i - 1] + d[i];
	for(int i = 1; i <= n - k + 1; i++)
		ans = ans < sum[i + k - 1] - sum[i - 1] ? sum[i + k - 1] - sum[i - 1] : ans;
	printf("%.8lf\n", ans);

	return 0;
}


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


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

			try{
				name=br.readLine();
				StringBuffer sb=new StringBuffer(name);
				name=sb.reverse().toString();
				System.out.println(name);
				name="";
				sb=null;

			}

			catch(Exception e){
				System.exit(0);
			}
		}
	}
}

Measured memory_bytes: 24192
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int i,j,k,n,m;
void read(int &x){
	char c;x=0;do c=getchar();while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);
}
void read(ll &x){
	char c;x=0;do c=getchar();while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);
}
int main() {
    long long x,y,z;
	cin>>x>>y>>z;
	cout<<max(0ll,y+z-x)<<endl;
    return 0;
}

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    
    def F(a,b):
        na=len(str(a))
        nb=len(str(b))
        return max(na,nb)
    
    def make_divisors(n):
        divisors = []
        for i in range(1, int(n**0.5)+1):
            if n % i == 0:
                divisors.append(i)
                if i != n // i:
                    divisors.append(n//i)

        # divisors.sort()
        return divisors
    
    L=make_divisors(N)
    ans=10**10
    for i in range(len(L)):
        a=L[i]
        b=N//L[i]
        temp=F(a,b)
        ans=min(ans,temp)
        
    print(ans)
        
        

main()


Measured memory_bytes: 39536
/*
今日は, 記念すべき AtCoder Beginner Contest 100 が開催される. そのため, 高橋君はりんごさんに, ある整数をプレゼントしようと思った.
今日のコンテストは「AtCoder Beginner Contest 100」なので, りんごさんは 
100
 で ちょうど 
D
 回割りきれる正の整数をプレゼントされると喜ぶ.

さて, りんごさんがプレゼントされると喜ぶような整数のうち 
N
 番目に小さいものを求めなさい.
*/

/*
int calc(int x) {
	int ret = 0;
	while(x % 100 == 0) {
		x /= 100;
		++ret;
	}
	return ret;
}
int main() {
	int D, N;
	cin >> D >> N;
	int cnt = 0, val = 0;
	while(cnt < N) {
		++val;
		if(calc(val) == D) ++cnt;
	}
	cout << val << '\n';
	return 0;
}
*/
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>

using namespace std;

int check(int x){
	int cnt=0;
	while(1){
		if(x%100==0){
			cnt++;
			x=x/100;
		}else{
			return cnt;
		}
	}
}

int main(){
	int D,N;
	cin >> D >> N;
	int cnt=0;
	for(int ans=1;;ans++){
		if(check(ans)==D)cnt++;
		if(cnt==N){
			cout << ans << endl;
			return 0;
		}	
	}
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <map>
#include <stack>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-10;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll maxn = 1e6 + 5;

int b[20];
int a[5][5];
int flag[5][5];
map<int,pair<int,int> >mp;

int main(){
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			cin>>a[i][j];
			mp[a[i][j]]={i,j};
		}
	}
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>b[i];
		if(mp.find(b[i])!=mp.end()){
			flag[mp[b[i]].first][mp[b[i]].second]=1;
		}
	}
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			if(flag[i][j]){
				flag[i][0]++;
				flag[0][j]++;
				if(i==j) flag[0][0]++;
				if(i+j==4) flag[4][4]++;
		    }
		}
	}
	bool ok=false;
	for(int i=0;i<=4;i++){
		for(int j=0;j<=4;j++){
			if(flag[i][j]>2){
				ok=1;
				break;
			}
		}
	}
	cout<<(ok?"Yes":"No");
	return 0;
}

Measured memory_bytes: 256
/**
 * ????°???????:
 * 	??¨???????????????????????????????´?????????\??????
 * 	???????????????:
 * 		g(n+1) = 3g(n)+1,g1=1;
 * 	?????\?°????????????´?????¨O(N^1.25)
 */

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6+10;
int n,m; // n?????´??°,??????G?????????
int A[MAX_N]; // ????´???°???
vector<int> G; // ??????????¨????????????¨??°?????°???
long long cnt;

// ??????g??´???????????????n?????°?????????
void insertionSort(int A[], int n, int g){
	int v,j;
	for (int i = g; i < n; ++i)
	{
		v = A[i];
		j = i-g; // ?????¢???????´?
		while(j >= 0 && A[j] > v) { // ????????????,?????¢??§????????????
		    A[j+g] = A[j];
		    j -= g;
		    cnt++;
		}
		A[j+g] = v;
	}
}

// ????????????n?????°?????????????°???????
void shellSort(int A[], int n){
	int h = 1;
	while(true) { // ????????????
	    if(h > n) break;
	    G.push_back(h); 
	    h = 3*h+1;
	}
	for (int i = G.size()-1; i >= 0; --i)
	{
		insertionSort(A, n, G[i]);
	}
}

int main(){
	//freopen("in.txt", "r", stdin);
	while(~scanf("%d", &n)) {
	    cnt = 0;
	    for(int i = 0; i < n; i++) scanf("%d", &A[i]); // ?????\??°???????´?
	    shellSort(A, n); // ??????????°???????
	    m = G.size();
	    cout << m << endl; // ??????????????????
	    for(int i = m-1; i >= 0; i--){
	    	printf("%d", G[i]);
	    	if(i) printf(" ");
	    }
	    printf("\n");
	    cout << cnt << endl; // ?????????????¬???°
	    for (int i = 0; i < n; ++i) // ????????????????????°???
	    {
	    	printf("%d\n", A[i]);
	    }
	    G.clear();
	}
	return 0;
}

Measured memory_bytes: 7160
#include <bits//stdc++.h>
using namespace std;
int main(void){
    int a,b,c,i,j,ans;
    ans=0;
    cin>>a;
    b=1;
    for(i=0;i<5;i++){
        b=b*10;
        if(i%2){
            if(b>a)
            break;
        
        continue;
        }
        if(b>a){
            ans=ans+a-b/10+1;
            break;
        }
        ans=ans+b-b/10;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  long n,k;
  scanf("%ld %ld", &n, &k);

  long evaluate = 1;
  long digits = 1;

  while (1) {
    evaluate *= k;
    if (evaluate <= n) {
      digits++;
    } else {
      break;
    }
  }

  printf("%ld\n", digits);

  return 0;
}

Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

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

        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        int k = sc.nextInt();

        sc.close();

        for (int i = 0; i < s.length; i++) {
            if (s[i] != s[k - 1]) {
                s[i] = '*';
            }
        }

        System.out.println(new String(s));

    }

}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, L[100000], R[100000], p;
bool b[100000];
ll c1, c2;
vector<pair<int, int>>r, l;

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		cin >> L[i] >> R[i];
		l.push_back(mkp(R[i], i));
		r.push_back(mkp(L[i], i));
	}
	sort(l.begin(), l.end());
	sort(r.rbegin(), r.rend());
	for (int i = 0; i < N; ++i) {
		if (!b[l[i].second]) {
			b[l[i].second] = true;
			if (p - l[i].first > 0) {
				c1 += p - l[i].first;
				p = l[i].first;
			}
		}
		if (!b[r[i].second]) {
			b[r[i].second] = true;
			if (r[i].first - p > 0) {
				c1 += r[i].first - p;
				p = r[i].first;
			}
		}
	}
	c1 += abs(p);
	memset(b, false, sizeof b);
	p = 0;
	for (int i = 0; i < N; ++i) {
		if (!b[r[i].second]) {
			b[r[i].second] = true;
			if (r[i].first - p > 0) {
				c2 += r[i].first - p;
				p = r[i].first;
			}
		}
		if (!b[l[i].second]) {
			b[l[i].second] = true;
			if (p - l[i].first > 0) {
				c2 += p - l[i].first;
				p = l[i].first;
			}
		}
	}
	c2 += abs(p);
	cout << max(c1, c2) << endl;
}

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

#define REP(i,n) for(long long i = 0; i < (n); i++)
#define FOR(i, m, n) for(long long i = (m);i < (n); ++i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SPEED cin.tie(0);ios::sync_with_stdio(false);

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T,vector<T>,greater<T>>;

constexpr long long MOD = (long long)1e9 + 7;
constexpr long long MOD2 = 998244353;
constexpr long long HIGHINF = (long long)1e18;
constexpr long long LOWINF = (long long)1e15;
constexpr long double PI = 3.1415926535897932384626433;

template <class T> vector<T> multivector(size_t N,T init){return vector<T>(N,init);}
template <class... T> auto multivector(size_t N,T... t){return vector<decltype(multivector(t...))>(N,multivector(t...));}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "{" << obj.first << ", " << obj.second << "}"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print(void) {cout << endl;}
template <class Head> void print(Head&& head) {cout << head;print();}
template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {cout << head << " ";print(forward<Tail>(tail)...);}
template <class T> void chmax(T& a, const T b){a=max(a,b);}
template <class T> void chmin(T& a, const T b){a=min(a,b);}
void YN(bool flg) {cout << (flg ? "YES" : "NO") << endl;}
void Yn(bool flg) {cout << (flg ? "Yes" : "No") << endl;}
void yn(bool flg) {cout << (flg ? "yes" : "no") << endl;}

int main() {
	string S; cin >> S;
	int N = S.size();
	int ans =0;
	for(int i = 0; i < N; ++i){
		if(i>=N-1-i) break;
		if(S[i] != S[N-1-i]) ans++;
	}	
	cout << ans << endl;

}


Measured memory_bytes: 256
def div(N):
    ans = []


    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
    ans.sort()
    return ans

N,M=map(int,input().split())
if N==1:
    print(M)
    exit()

divM=div(M)

for i in range(1,len(divM)):
    if divM[i]>M//N:
        print(divM[i-1])
        exit()


Measured memory_bytes: 3060
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;
typedef string::const_iterator State;

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


int main(void) {
	long long int  b, c, d, n, m;
	long long int count = 0;
	long long int x;
	

	cin >> n >> x;

	vector<long long int> a(n);
	FOR(i, 0, n-1) {
		cin >> a[i];
	}

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

	FOR(i, 0, n - 1) {
		if (i == n - 1) {
			if (x == a[i]) {
				count++;
			}
		}
		else if (x >= a[i]) {
			count++;
			x -= a[i];
		}
		else {
			break;
		}
	}


	cout << count << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <numeric>
#include <bitset>
#include <ext/algorithm>
#include <ext/numeric>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
typedef long long LL; using namespace std;

const LL MOD = 1000000000 + 7LL;

LL fac[1000000];

LL powmy(LL a, LL p) {
	if (!p)
		return 1LL;
	LL ret = powmy(a, p >> 1);
	ret *= ret;
	ret %= MOD;
	if (p & 1) {
		ret *= a;
		ret %= MOD;
	}
	return ret;
}

LL invmy(int n) {
	return powmy(n, MOD - 2);
}

LL bin(int n, int k) {
	if (n < k)
		return 0LL;
	LL ret = fac[n];
	ret *= invmy(fac[k]);
	ret %= MOD;
	ret *= invmy(fac[n - k]);
	ret %= MOD;
	return ret;
}

vector<int> a;

int there[1000000];

int main() {
	fac[0] = 1LL;
	ffor (i, 1, 1000000) {
		fac[i] = fac[i - 1] * i;
		fac[i] %= MOD;
	}
	
	int n, x, same = -1, between = -1;
	cin >> n;
	SET(there, 255);
	FOR (i, n + 1) {
		cin >> x;
		a.pb(x);
		if (there[x] > -1) {
			same = x;
			between = i - there[x] - 1;
		}
		there[x] = i;
	}
	cout << n << endl;
	ffor (k, 2, n + 1) {
		LL ret = bin(n - 1, k);
		ret += bin(n - 1, k - 2);
		ret += 2LL * bin(n - 1, k - 1);
		ret -= bin(n - 1 - between, k - 1);
		if (ret < 0)
			ret += MOD;
		ret %= MOD;
		cout << ret << endl;
	}
	cout << "1" << endl;
	return 0;
}

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

int main()
{
	int X;
	// 標準入力から入力
	cin >> X;
	
	int t;
	int sum = 0;

	for (t = 1; t < X; t++) {
		sum += t;
		if(sum >= X) break;
	}

	cout << t << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String str = sc.next();
		int n = sc.nextInt();
		
		String Cstr = str;
		
		for(int i=0;i<n;i++) {
			String prg = sc.next();
			int a = sc.nextInt();
			int b = sc.nextInt();
			if(prg.equals("replace")) {
				String prs = sc.next();
				String Ccstr = "";
				//置換したい箇所を抜き出して置き換える
				for(int j=a;j<=b;j++) {
					Ccstr += Cstr.charAt(j);
				}
				//Ccstr.replace(Ccstr,prs);
				Ccstr = prs;
				//ここまで
				//置換したい箇所の前
				String Sstr = "";
				if(a != 0) {
					for(int j=0;j<a;j++) 
						Sstr += Cstr.charAt(j);
					
				}
				//ここまで
				//置換したい箇所の後ろ
				String Bstr = "";
				if(b != Cstr.length()) {//チェックポイント
					for(int j=b+1;j<Cstr.length();j++) 
						Bstr += Cstr.charAt(j);
					
				}
				//ここまで
				Cstr = Sstr + Ccstr + Bstr;
			}else if(prg.equals("reverse")) {
				String Vstr = "";
				for(int j=a;j<=b;j++) 
					Vstr += Cstr.charAt(j);
				StringBuffer sb = new StringBuffer(Vstr);
				Vstr = sb.reverse().toString();
				//反転したい箇所の前
				String Sstr = "";
				if(a != 0) {
					for(int j=0;j<a;j++) 
						Sstr += Cstr.charAt(j);
					
				}
				//ここまで
				//反転したい箇所の後ろ
				String Bstr = "";
				if(b != Cstr.length()) {//チェックポイント
					for(int j=b+1;j<Cstr.length();j++) 
						Bstr += Cstr.charAt(j);
					
				}
				//ここまで
				Cstr = Sstr + Vstr + Bstr;
			}else {
				for(int j=a;j<=b;j++)
					System.out.print(Cstr.charAt(j));
				System.out.println();
			}
		}
	}
}



Measured memory_bytes: 68064
#include <stdio.h>

int main(){
    int S, h, m, s;
    
    scanf("%d", &S);
    h = S/3600;
    m = (S%3600)/ 60;
    s = S % 60;
    
    printf("%d:%d:%d\n", h, m, s);
    return 0;
}


Measured memory_bytes: 2732
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	if(n==25) cout << "Christmas" << endl;
	else if(n==24) cout << "Christmas Eve" << endl;
	else if(n==23) cout << "Christmas Eve Eve" << endl;
	else cout << "Christmas Eve Eve Eve" << endl;
}

Measured memory_bytes: 256
n = int(input())
a = [int(x) for x in input().split()]

a_odd = len([x for x in a if x % 2 != 0])
#a_eve = len([x for x in a if x % 2 == 0])

if a_odd % 2 == 0:
    print("YES")
else:
    print("NO")

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

int main()
{
	int n, d, x, ans = 0;
	cin >> n >> d >> x;
	for (int i = 0, x; i < n; i++)
	{
		cin >> x;
		ans += (d - 1) / x + 1;
	}
	cout << ans + x;
}

Measured memory_bytes: 256
/*Stay true to yourself, yet always be open to learn. Work hard, and never give up on your dreams, 
even when nobody else believes they can come true but you. These are not cliches but real tools you 
need no matter what you do in life to stay focused on your path.
*/
 
 /*Pppppppp    UU      UU     CCCCCCCC    CCCCCCCC     HH     HH     UU      UU
   pp    pp    UU      UU     CC          CC           HH     HH     UU      UU
   pp    pp    UU      UU     CC          CC           HHHHHHHHH     UU      UU
   pppppppp    UU      UU     CC          CC           HHHHHHHHH     UU      UU
   pp          UU      UU     CC          CC           HH     HH     UU      UU
   pp          UUUUUUUUUU     CCCCCCCC    CCCCCCCC     HH     HH     UUUUUUUUUU
   */
 
#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int h[n];
    for(int i=0;i<n;i++)
    cin >> h[i];
    int ans[n];
    ans[0]=0;
    ans[1]=abs(h[1]-h[0]);
    for(int i=2;i<n;i++)
    {
        ans[i]= min(ans[i-1]+abs(h[i]-h[i-1]),ans[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<ans[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 1024
x,y,z,k=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=[]
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
for i in range(min(x,k)):
  for j in range(min(y,k)):
    if i*j>k:
      break
    for l in range(min(z,k)):
      if i*j*l>k:
        break
      else:
        ans.append(a[i]+b[j]+c[l])
ans.sort(reverse=True)
for i in range(k):
  print(ans[i])

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

int E[6] = {3,0,-2,2,0,-3};
int N[6] = {1,4,0,0,-4,-1};
int lsp[6] = {0,1,2,-2,-1,0};


void DICE(int a,int d[]){
	
int d2[6];
int i;

	if(a == 0){
	for(i = 0;i < 6; i++){
		d2[i] = d[i + E[i]];
		}
		}	
	if(a == 1){
	for(i = 0;i < 6; i++){
		d2[i] = d[i + N[i]];
		}
		}	
	memcpy(d,d2,6 * sizeof(int));
}


void l_spin(int d[]){
	int d2[6];
	int i;
	
	for(i = 0; i < 6; i++){
		d2[i] = d[i + lsp[i]];
	}
	
	memcpy(d,d2,6 * sizeof(int));
}




int main(void){
	int d[6];
	int n, i, a, b;
	


	for(i = 0; i < 6; i++){
scanf("%d",&d[i]);
}

scanf("%d",&n);


for(i = 0; i < n; i++){
scanf("%d",&a);
scanf("%d",&b);


while(1){
	DICE(0,d);
	if(d[0] == a) break;
	DICE(1,d);
	if(d[0] == a) break;
}


while(1){
	l_spin(d);
	if(d[1] == b) break;
}


printf("%d\n",d[2]);

}

return 0;
}

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

using namespace std;

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

	vector< vector<int> > a(n,vector<int>(3));

	for(int i=0;i<n;i++)
	{
		for(int j=0;j<3;j++)
			cin>>a[i][j];
	}

	int dp[n+1][3];
	dp[0][0]=0;
	dp[0][1]=0;
	dp[0][2]=0;
	//for each day
	for(int i=1;i<=n;i++)
	{
		dp[i][0] = max(dp[i-1][1],dp[i-1][2])+a[i-1][0];
		dp[i][1] = max(dp[i-1][0],dp[i-1][2])+a[i-1][1];
		dp[i][2] = max(dp[i-1][0],dp[i-1][1])+a[i-1][2];
	}

	cout<<max(dp[n][0],max(dp[n][1],dp[n][2]));
}

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

using namespace std;
typedef long long unsigned int ll;

int dp[101][4][4][4];
int N;
int mod = 1e9 + 7;

int main() {
  cin >> N;
  dp[0][3][3][3] = 1;

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
	for (int l = 0; l < 4; ++l) {
	  if (dp[i][j][k][l] == 0) continue;

	  for (int a = 0; a < 4; ++a) {
	    if (a == 2 && j == 1 && k == 0) continue;
	    if (a == 2 && j == 0 && k == 1) continue;
	    if (a == 1 && j == 2 && k == 0) continue;
	    if (a == 2 && j == 1 && l == 0) continue;
	    if (a == 2 && k == 1 && l == 0) continue;

	    dp[i + 1][a][j][k] += dp[i][j][k][l];
	    dp[i + 1][a][j][k] %= mod;
	  }

	}
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < 4; ++i) {
    for (int j = 0; j < 4; ++j) {
      for (int k = 0; k < 4; ++k) {
	ans += dp[N][i][j][k];
	ans %= mod;
      }

    }

  }

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



Measured memory_bytes: 256
a, b, c, x, y = map(int, input().split())
total = 0
if a + b > c * 2:
    total += min(x, y) * 2 * c
    if x >= y:
        total += (x - y) * min(a, 2 * c)
    else:
        total += (y - x) * min(b, 2 * c)

else:
    total = x * a + y * b
print(total)


Measured memory_bytes: 9172
import math

n, d = (int(a) for a in input().split())
list_xy = [[int(x) for x in input().split()] for y in range(0, n)]
count = 0

for i in range(0, n):
    dist = math.sqrt(list_xy[i][0] ** 2 + list_xy[i][1] ** 2)
    if dist <= d:
        count += 1

print(count)

Measured memory_bytes: 42400
#include <iostream>
#include <utility>
#include <vector>
#include <cstring>
#include <cstdio>
#include <cstdint>
#include <string>
#include <algorithm>

using namespace std;

int main(int argc,char** argv) {
    int n;
    string s;
    cin >> n >> s;
    string r[4];
    int res = -1;
    for(int i = 0;i < 4;i++) {
        if(i % 2) r[i].append("S");
        else r[i].append("W");
        if(i > 1) r[i].append("S");
        else r[i].append("W");
    }
    for(int i = 0;i < 4;i++) {
        for(int j = 2;j < n;j++) {
            bool sheep = true;
            if(r[i][j-2] == 'W') sheep = !sheep;
            if(s[j-1] == 'x') sheep = !sheep;
            if(r[i][j-1] == 'W') sheep = !sheep;
            if(sheep) r[i].append("S");
            else r[i].append("W");
        }
        bool ok = true;
        for(int j = 0;j < 2;j++) {
            bool sheep = true;
            if(r[i][n + (j-2)] == 'W') sheep = !sheep;
            if(s[(n + (j-1))%n] == 'x') sheep = !sheep;
            if(r[i][(n + (j-1))%n] == 'W') sheep = !sheep;
            if((sheep && r[i][j] =='W') || (!sheep && r[i][j] =='S')) ok = false;
        }
        if(ok) res = i;
    }
    if(res == -1) cout << -1 << endl;
    else cout << r[res] << endl;
    return 0;
}


Measured memory_bytes: 1024
import sys
sys.setrecursionlimit(10 ** 9)

N = int(input())
graph = list()
for i in range(N):
  x = list(map(int, input().split()))
  graph.append(x[2:])

start = [0] * N
end = [0] * N
visited = [False] * N
time = 0
def dfs(n):
  if visited[n]:
    return
  visited[n] = True
  global time
  time += 1
  start[n] = time
  for i in graph[n]:
    dfs(i-1)
  time += 1
  end[n] = time

for i in range(N):
  dfs(i)
for i in range(N):
  print(i+1, start[i], end[i])


Measured memory_bytes: 5652
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;



class Myon
{
    public Myon() { }
    public static int Main()
    {
        cin = new Scanner();
        new Myon().calc();
        return 0;
    }

    static Scanner cin;

    void calc()
    {
        var N = cin.nextInt();
        var dp = new int[100010];
        for(int i = 1;i <= 100000; i++)
        {
            dp[i] = int.MaxValue;
            int power = 1;
            while(power <= i)
            {
                dp[i] = Math.Min(dp[i], dp[i - power] + 1);
                power *= 6;
            }

            power = 9;
            while (power <= i)
            {
                dp[i] = Math.Min(dp[i], dp[i - power] + 1);
                power *= 9;
            }
        }
        Console.WriteLine(dp[N]);
    }


    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }
        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }


        public double[] ArrayDouble(int N, double add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }
}

Measured memory_bytes: 13280
#include <algorithm>
#include <iostream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <iomanip>
#include <numeric>
#include <tuple>
#include <bitset>
#include <complex>
#include <unistd.h>
#include <cassert>
#include <cctype>
#include <random>
#include <time.h>
#define _USE_MATH_DEFINES
#define _GLIBCXX_DEBUG
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> plglg;
typedef pair<double, ll> pdlg;
typedef tuple<int, int, int> tiii;
typedef tuple<ll, ll, ll> tlglglg;
typedef tuple<double, double, double> tddd;
typedef complex<double> xy_t;
typedef vector<ll> vll;
typedef vector< vector<ll> > matrix;
#define REP(i, x, y) for(ll i = (ll)x; i < (ll)y; i++)
#define DREP(i, x, y, d) for(ll i = (ll)x; i < (ll)y; i += (ll)d)
#define PER(i, x, y) for(ll i = (ll)x; i > (ll)y; i--)
#define DPER(i, x, y, d) for(ll i = (ll)x; i > (ll)y; i -= (ll)d)
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
double pi = 3.141592653589793;
ll mod = 1000000007;
int intmax = 2147483647;
int intmin = -2147483648;
ll llmax = 9223372036854775807;
ll llmin = -9223372036854775807;
int iinf = intmax / 8;
ll inf = llmax / 8;
double eps = 1e-12;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll a[N];
    REP(i, 0, N) {
        cin >> a[i];
    }
    bool ok = true;
    ll mark[32];
    fill(mark, mark + 32, 0);
    REP(i, 0, N) {
        REP(j, 0, 32) {
            if (!((a[i] >> j) & 1)) {
                mark[j]++;
            }
        }
    }
    if (N % 3 == 0) {
        REP(i, 0, 32) {
            if (mark[i] != N && mark[i] != N / 3) {
                ok = false;
            }
        }
    } else {
        REP(i, 0, 32) {
            if (mark[i] != N) {
                ok = false;
            }
        }
    }
    if (ok) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 1024
#include <iostream>
#include <stdio.h>
int main(){
  int a,b,c;
  scanf("%d%d%d",&a,&b,&c);
  if((a!=b && b != c && c!=a)||(a == b && a== c)){
    printf("No\n");
  }else{
    printf("Yes\n");
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<stack>
#include<queue>

using namespace std;
const int N = 100009;
int num[N];
int a0[N],b0[N]; 
int n;
int a,b; 
int cop1[N],cop2[N];
void lisan()
{
	for(int i=1;i<=n;i++)
		{
			cop1[i]=a0[i];
			cop2[i]=b0[i];
		}
	sort(a0+1,a0+1+n);sort(b0+1,b0+1+n);
	return ;
}
int maxa;
int ans0;
int main()
{
	scanf("%d",&n);
	maxa=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&a,&b);
		if(a>maxa)
		{
			maxa=a;
			ans0=b;
		}
	}
	int ans;
	ans=maxa+ans0;
	printf("%d",ans);
	//lisan();
	
	return 0;
}
//3 47 29 62 ->8 

/*
3
4 7
2 9
6 2
*/ 

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define endl '\n'
#define FASTINOUT ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const ll mod = 1000000007;
const double PI = 3.141592653589793238463;
const int N=2e5+100;
int main()
{
    FASTINOUT;
    string s,t,a;
    cin>>s>>t>>a;
    cout<<s[0]<<t[1]<<a[2]<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>

using namespace std;

typedef long long ll;

int main(){
	ll dp[100][21]={};
	int data[100];
	int n;
	cin>>n;
	for(int i=0;i<n;i++)cin>>data[i];
	dp[0][data[0]]=1;
	for(int i=1;i<n-1;i++){
		for(int num=0;num<21;num++){
			if(num+data[i]<=20&&num-data[i]>=0){
				dp[i][num]=dp[i-1][num+data[i]]+dp[i-1][num-data[i]];
			}
			else if(num+data[i]<=20){
				dp[i][num]=dp[i-1][num+data[i]];
			}
			else if(num-data[i]>=0){
				dp[i][num]=dp[i-1][num-data[i]];
			}
		}
	}
	cout<<dp[n-2][data[n-1]]<<endl;
	return 0;
}

Measured memory_bytes: 1180
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


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


template<typename T> 
struct BIT{
  Int n;
  vector<T> bit;
  //1-indexed
  BIT():n(-1){}
  BIT(Int n_,T d):n(n_),bit(n_+1,d){}
  
  T sum(Int i){
    T s=bit[0];
    for(Int x=i;x>0;x-=(x&-x))
      s+=bit[x];
    return s;
  }
  void add(Int i,T a){
    if(i==0) return;
    for(Int x=i;x<=n;x+=(x&-x))
      bit[x]+=a;
  }
  
  Int lower_bound(Int w){
    if(w<=0) return 0;
    Int x=0,r=1;
    while(r<n) r<<=1;
    for(Int k=r;k>0;k>>=1){
      if(x+k<=n&&bit[x+k]<w){
        w-=bit[x+k];
        x+=k;
      }
    }
    return x+1;
  }
  
  T sum0(Int i){
    return sum(i+1);
  }
  void add0(Int i,T a){
    add(i+1,a);
  }

  T query(Int l,Int r){
    return sum(r-1)-sum(l-1);
  }

  T query0(Int l,Int r){
    return sum(r)-sum(l);
  }
};


template<typename T>
vector<T> compress(vector<T> v){
  sort(v.begin(),v.end());
  v.erase(unique(v.begin(),v.end()),v.end());
  return v;
}

template<typename T>
map<T, Int> dict(const vector<T> &v){
  map<T, Int> res;
  for(Int i=0;i<(Int)v.size();i++)
    res[v[i]]=i;
  return res;
}

//INSERT ABOVE HERE
signed main(){
  Int q;
  cin>>q;
  vector<Int> ts(q),as(q),bs(q);
  for(Int i=0;i<q;i++){
    cin>>ts[i];
    if(ts[i]==1) cin>>as[i]>>bs[i];    
  }

  vector<Int> vs(as);
  vs.emplace_back(-2e9);
  vs.emplace_back(+2e9);
  vs=compress(vs);
  auto dc=dict(vs);

  BIT<Int> bit1(vs.size()+1,0);
  BIT<Int> bit2(vs.size()+1,0);  
  Int num=0,ofs=0;
  for(Int i=0;i<q;i++){
    if(ts[i]==1){
      bit1.add(dc[as[i]],1);
      bit2.add(dc[as[i]],as[i]);
      num++;
      ofs+=bs[i];      
    }
    if(ts[i]==2){      
      Int k=bit1.lower_bound((num+1)/2);
      Int v=vs[k];      
      Int w=(bit2.query(k+1,vs.size())-v*bit1.query(k+1,vs.size()))
             +(v*bit1.query(0,k)-bit2.query(0,k));      
      cout<<v<<" "<<w+ofs<<"\n";
    }
  }
  
  cout<<flush;
  return 0;
}


Measured memory_bytes: 16712
#include <bits/stdc++.h>
        using namespace std;
        #define tani_nachi_ke  ios_base::sync_with_stdio(false); cin.tie(NULL);
        #define M_PI 3.14159265358979323846
        #define data data_
        #define ff first
        #define ss second
        #define pb push_back
        #define ld long double
        #define int long long
        #define print(t) cout << "Case #" << t << ": ";
        int32_t main()
        {
            tani_nachi_ke  
            
            
            int n,k;
            cin >> n >> k;

            int a[n+10];
            for(int i = 1; i <= n; i++)
                cin >> a[i];

            vector<int> bin;
           

            int id = -1;
            int cur = 1;
            bool dp[n+10] = {0};
            while(dp[cur] != 1)
            {
                bin.push_back(cur);
                dp[cur] = 1;
                cur = a[cur];
            }
            // for(int u:bin)
            //     cout << u << " ";
            // cout << endl;
            for(int i = 0; i < bin.size(); i++)
            {
                if(bin[i] == cur)
                {
                    id = i;
                    break;
                }
            }
            // cout << id << endl;
            if(k < id)
            {
                cout << bin[k] << endl;
            }
            else
            {
                k -= id;
                int len = bin.size() - id;
                k %= len;
                cout << bin[id + k] << endl;
            }
           return 0;
        }
          

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

int get2(int n, int *ar, int sol);

int main(void){
    int n;
    ////printf("input: n = ");
    scanf("%d", &n);

    int *ar;
    ar = (int *)malloc(n * sizeof(int));

    int i;
    for(i = 0; i < n; i++){
        ////printf("\ninput: ar[%d] = ", i);
        scanf("%d", &ar[i]);
    }

    int sol = 0;
    for(i = 0; i < n; i++){
        //printf("i = %d\n", i);
        if(ar[i] % 2 != 0){
            continue;
        }else{
            //printf("ar[%d] = %d, is even, sol = %d\n", i, ar[i], sol);
            while(ar[i] % 2 == 0){
                ar[i] /= 2;
                sol++;
                //printf("ar[%d] = %d, sol = %d\n", i, ar[i], sol);
            }
        }
    }

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

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

using namespace std;

map<string,int>mp;

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

    string str;
    mp.insert({"SUN",7});mp.insert({"MON",6});
    mp.insert({"TUE",5});mp.insert({"WED",4});
    mp.insert({"THU",3});mp.insert({"FRI",2});mp.insert({"SAT",1});
    cin>>str;
    cout<<mp[str]<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
  int d,n;
  cin >> d >> n;
  if(d==0&&n==100) cout << 101 << "\n";
  else if(d==1&&n==100) cout << 10100 << "\n";
  else if(d==2&&n==100) cout << 1010000 << "\n";
  else if(d==0) cout << n << "\n";
  else if(d==1) cout << 100*n << "\n";
  else cout << 10000*n << "\n";
  return 0;
}

Measured memory_bytes: 3628
#include <stdio.h>
#define MAX 10000

int S[MAX], n;
int linearSearch(int);

int main(){
  int i, q, count = 0, T[MAX];

  scanf("%d",&n);
  for(i = 0; i < n; i++){
    scanf("%d",&S[i]);
  }
  scanf("%d",&q);
  for(i = 0; i < q; i++){
    scanf("%d",&T[i]);
    if(linearSearch(T[i]) == 1) count++;
  }
  printf("%d\n",count);

  return 0;
}

int linearSearch(int t){
  int i;
  for(i = 0; i < n; i++){
    if(S[i] == t) return 1;
  }

  return 0; 
}

Measured memory_bytes: 640
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
 
 
int main(){
 
long long N,A[200001],i=0,S=0;
 
scanf("%lld",&N);
 
 
for(i;i<N;i++){
scanf("%lld",&A[i]);
if(A[i]<A[i-1] && i!=0){
    S = S + (A[i-1] - A[i]);
    A[i] = A[i-1];
}
 
else{
    S+=0;
}
 
}
 
printf("%lld",S);
 
return 0;
 
 
 
}

Measured memory_bytes: 3296
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL N, K, cnt1, cnt2, res1, res2, ans;

int main()
{
	in >> N >> K;
	for (LL i = 1; i <= N; ++i)
	{
		if (i % K == 0) ++cnt1;
		if (K % 2 == 0 && i % K == K / 2) ++cnt2;
	}
	res1 = cnt1 * cnt1 * cnt1;
	res2 = cnt2 * cnt2 * cnt2;
	out << (K % 2 == 0 ? res1 + res2 : res1) << std::endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define vi vector<int>
#define ll long long
#define ld long double
#define vvi vector<vi>
#define vll vector<ll>
#define vld vector<ld>
#define vvll vector<vll>
#define vvld vector<vld>
#define MOD 1000000007
#define endL << '\n'
#define ii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second
#define mp make_pair
#define endL << '\n'
#define vii vector<ii>
#define pb push_back

/*
ll powmod(ll x, ll y, ll mod){
	ll res = 1;
	while (y > 0){
		if (y%2) res = (res*x) % mod;
		x = (x*x) % mod;
		y /= 2;
	}
	return res;
}
*/

/*const int N = 1000000;
int lp[N+1];
vector<ll> pr;

void sieve(){
	for (int i=2; i<=N; ++i) {
	    if (lp[i] == 0) {
	        lp[i] = i;
	        pr.push_back (i);
	    }
	    for (int j=0; j<(int)pr.size() && pr[j]<=lp[i] && i*pr[j]<=N; ++j)
	        lp[i * pr[j]] = pr[j];
	}
}*/

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t=1; //cin >> t;
	while(t--){
		int n, k; cin >> n >> k;
		vll a(n); for (int i = 0; i < n; i++) cin >> a[i];
		vll pref(k+1, 0);
		vvll dp(n, vll(k+1, 0));
		for (int cand = 0; cand <= k; cand++){
			dp[0][cand] = (cand <= a[0]) ? 1 : 0;
			pref[cand] = (cand == 0) ? dp[0][cand] : pref[cand-1] + dp[0][cand];
		}

		for (int i = 1; i < n; i++){
			for (int cand = 0; cand <= k; cand++){
				dp[i][cand] = (cand <= a[i]) ? pref[cand] : ((pref[cand] - pref[cand - a[i] - 1]) + MOD) % MOD;
			}
			pref.resize(k+1, 0); pref[0] = dp[i][0];
			for (int cand = 1; cand <= k; cand++) pref[cand] = (pref[cand-1] + dp[i][cand]) % MOD;
		}
		/*for (int i = 0; i < n; i++){
			for (int cand = 0; cand <= k; cand++) cout << dp[i][cand] << " "; cout endL;
		}*/
		cout << dp[n-1][k];
	}
}

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

n = int(input())

connect_list = [ [] for i in range(n) ]
distance_list = [ -1 for i in range(n) ]
color_list = [ "Gray" for i in range(n) ]
distance_list[0] = 0

for i in range(n-1):
	u, v, w = [ int(v) for v in input().split() ]
	w %= 2
	connect_list[u-1].append((v-1,w))
	connect_list[v-1].append((u-1,w))
	

search_list = [0]

t = 0
stop = 0
while t < len(search_list):
	s = search_list[t]
	stop = 0
	for i in connect_list[s]:
		if distance_list[i[0]] == -1:
			distance_list[i[0]] = (distance_list[s] + i[1]) % 2
			search_list.append(i[0])
	t += 1


for i in distance_list:
	print(i)

Measured memory_bytes: 68716
use std::cmp;

const INF: i64 = 1e17 as i64;

fn main() {
    let s = std::io::stdin();
    let mut sc = Scanner { reader: s.lock() };
    let n: usize = sc.read();
    let a: Vec<i64> = sc.read_vec(n);
    let mut graph = vec![vec![]; n];
    for _ in 0..(n - 1) {
        let v = sc.read::<usize>() - 1;
        let u = sc.read::<usize>() - 1;
        graph[v].push(u);
        graph[u].push(v);
    }

    let mut dp1 = vec![vec![]; n];
    let mut dp2 = vec![vec![]; n];
    dfs(0, 0, &graph, &a, &mut dp1, &mut dp2);

    for i in 1..(n + 1) {
        if dp1[0][i] < INF {
            println!("{}", i - 1);
            return;
        }
        if dp2[0][i] < 0 {
            println!("{}", i - 1);
            return;
        }
    }
}

fn dfs(
    v: usize,
    p: usize,
    graph: &Vec<Vec<usize>>,
    a: &Vec<i64>,
    dp1: &mut Vec<Vec<i64>>,
    dp2: &mut Vec<Vec<i64>>,
) {
    dp1[v].push(INF);
    dp1[v].push(if a[v] > 0 { a[v] } else { INF });
    dp2[v].push(INF);
    dp2[v].push(a[v]);
    for &next in graph[v].iter() {
        if next == p {
            continue;
        }
        dfs(next, v, graph, a, dp1, dp2);

        dp1[v] = tr(&dp1[v], &dp1[next], &dp2[next], true);
        dp2[v] = tr(&dp2[v], &dp1[next], &dp2[next], false);
    }
}

fn tr(dp: &Vec<i64>, ch1: &Vec<i64>, ch2: &Vec<i64>, flag: bool) -> Vec<i64> {
    let child_cuts = ch1.len();
    assert_eq!(child_cuts, ch2.len());
    let mut ans = vec![INF; dp.len() + child_cuts - 1];
    for i in 0..dp.len() {
        if dp[i] == INF {
            continue;
        }
        for j in 0..child_cuts {
            if i + j >= 1 {
                if ch1[j] != INF {
                    ans[i + j - 1] = cmp::min(ans[i + j - 1], dp[i] + ch1[j]);
                }
                if ch2[j] != INF && !flag {
                    ans[i + j - 1] = cmp::min(ans[i + j - 1], dp[i] + ch2[j]);
                }
            }
            if ch1[j] != INF || ch2[j] < 0 {
                ans[i + j] = cmp::min(ans[i + j], dp[i]);
            }
        }
    }
    ans
}

pub struct Scanner<R> {
    reader: R,
}

impl<R: std::io::Read> Scanner<R> {
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .reader
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n')
            .take_while(|&b| b != b' ' && b != b'\n')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn read_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 211836
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int f[105][105][105],a[105][105];
char s[105][105];
int Sum(int x1,int y1,int x2,int y2){
	return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}
int main(){
	int h,w,x=0,y=0,ans=0;
	scanf("%d%d\n",&h,&w);
	for (int i=1;i<=h;i++){
		scanf("%s",s[i]+1);
		for (int j=1;j<=w;j++){
			if (s[i][j]=='E') x=i,y=j;
			a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+(s[i][j]=='o');
		}
	}
	memset(f,-0x3f,sizeof f);
	f[0][0][0]=0;
	for (int u=0;u<x;u++)
		for (int d=0;x+d<=h;d++){
			int U=max(x-u,d+1),D=min(x+d,h-u);
			if (U>D) continue;
			for (int l=0;l<y;l++)
				for (int r=0;y+r<=w;r++){
					int L=max(y-l,r+1),R=min(y+r,w-l);
					if (L>R || f[d][l][r]<0) continue;
					ans=max(ans,f[d][l][r]);
					if (u+d<h-x) f[d+1][l][r]=max(f[d+1][l][r],f[d][l][r]+Sum(x+d+1,L,x+d+1,R));
					if (l+r<y-1) f[d][l+1][r]=max(f[d][l+1][r],f[d][l][r]+Sum(U,y-l-1,D,y-l-1));
					if (l+r<w-y) f[d][l][r+1]=max(f[d][l][r+1],f[d][l][r]+Sum(U,y+r+1,D,y+r+1));
					if (u+d<x-1) f[d][l][r]+=Sum(x-u-1,L,x-u-1,R);
				}
		}
	printf("%d\n",ans);
}

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

int main()
{
    int n,j=0;
    cin>>n;
    char s[n+2],t[n+2],ans[2*n+2];
    cin>>s>>t;
    for(int i = 0;i<n;i++)
    {
        ans[j] = s[i];
        j++;
        ans[j] = t[i];
        j++;
    }
    
    for(int k=0;k<j;k++)
        cout<<ans[k];
    return 0;
}


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

void Main() {
  int X, A;
  cin >> X >> A;
  if (X < A) cout << 0 << endl;
  else cout << 10 << endl;
}

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  Main();
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

ll dp[2][100010];  /* dp[id][i+1] : 先頭からi桁目までの条件を満たす組の個数。
                                    ただし、id = 0 のときa+bが現時点でsと等しい。
                                    id = 1 のときa+bが現時点でsより小さいことが確定。 */
 
int main() {
    string s;
    cin >> s;
    ll m = s.size();

    dp[0][0] = 1;
    rep(i, m) {
        if(s[i] == '1') {
            dp[1][i+1] += 3*dp[1][i] + dp[0][i];
            dp[0][i+1] += 2*dp[0][i];
        }
        else if(s[i] == '0') {
            dp[1][i+1] += 3*dp[1][i];
            dp[0][i+1] += dp[0][i];
        }
        dp[1][i+1] %= mod;
        dp[0][i+1] %= mod;
    }
    
    ll ans = (dp[0][m] + dp[1][m])%mod;
    out(ans);
    re0;
}

Measured memory_bytes: 2048
#include<stdio.h>
#define M 100000
int main()
{
  int i,j=0,x,n,k=0,l=0;
 int A[M],B[M];
 scanf("%d",&n);
 for(i=0;i<n;i++){
  scanf("%d",&A[i]);
 }
 x=A[n-1];
 for(i=0;i<n;i++){
   if(A[i]==x) k++;
   if(A[i]<=x){
     B[j]=A[i];
     A[i]=A[j];
     A[j]=B[j];
     j++;
   }
 }
   for(i=0;i<n;i++){
     if(A[i]==x) l++;
     if(i!=0){
       printf(" ");
     }
     if(A[i]==x && A[i+1]!=x && l==k){
       printf("[");
     }
     printf("%d",A[i]);
     if(A[i]==x && A[i+1]!=x && l==k){
       printf("]");
     }
   }
   printf("\n");
return 0;
}



Measured memory_bytes: 2128
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <tuple>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
using namespace std;
typedef long long ll;

int main()
{
  int n, x, y;
  cin >> n >> x >> y;
  cout << min(x * n, y) << endl;
}

Measured memory_bytes: 256
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  // val inputs = Seq("3 3", "dxx", "axx", "cxx")
  val input1 = inputs(0).split(" ").map(_.toInt)
  val N = input1(0)
  val L = input1(0)
  val strings = inputs.tail
  val result = strings.sorted.mkString

  println(result)

}

Measured memory_bytes: 25788