akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("3 4");
            WillReturn.Add("1 1");
            WillReturn.Add("2 2");
            WillReturn.Add("3 3");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 500000");
            WillReturn.Add("1 100000");
            WillReturn.Add("1 100000");
            WillReturn.Add("1 100000");
            WillReturn.Add("1 100000");
            WillReturn.Add("1 100000");
            WillReturn.Add("100000 100000");
            WillReturn.Add("100000 100000");
            WillReturn.Add("100000 100000");
            WillReturn.Add("100000 100000");
            WillReturn.Add("100000 100000");
            //1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(X => long.Parse(X)).ToArray();

        SplitAct(InputList[0]);
        long K = wkArr[1];

        var CntDict = new Dictionary<long, long>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);

            long wkKey = wkArr[0];
            long wkValue = wkArr[1];

            if (CntDict.ContainsKey(wkKey) == false) {
                CntDict.Add(wkKey, wkValue);
            }
            else CntDict[wkKey] += wkValue;
        }

        long RestCnt = K;
        foreach (var EachPair in CntDict.OrderBy(X => X.Key)) {
            RestCnt -= EachPair.Value;
            if (RestCnt <= 0) {
                Console.WriteLine(EachPair.Key);
                break;
            }
        }
    }
}


Measured memory_bytes: 29624
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int INF=1<<29,MOD=1e9+7;

int main(){
	int n; cin>>n;
	int a[n],b[n];
	long ans=0;
	rep(i,n) cin>>a[i]>>b[i];
	for(int i=n-1;i>=0;i--){
		if((a[i]+ans)%b[i]!=0){
			ans+=b[i]-(a[i]+ans)%b[i];
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
#全体のボールの数
N = int( input() )
#Kの数
K = int( input() )
#入力のリスト代入
list = map( int, input().split() )
#個別に確認
x = 0
for num in list:
    a = num * 2
    b = (K - num) * 2
#比較して加算
    if b <= a:
        x += b
    elif b > a:
        x += a
#値の出力
print( x )

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef pair<int, int> pii;  // pair<int, int> に pii という別名を付ける
typedef long long ll;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  string S, T;
  cin >> S >> T;
  bool ans = true;
  for (int i = 0; i < S.size(); i++){
    if(S.at(i) != T.at(i)){
      ans = false;
      break;
    }
  }
  if(ans){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3644
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 24 14:53:50 2018
ITP21A
@author: maezawa
"""

from collections import deque

d = deque()

n = int(input())

for i in range(n):
    c = list(map(int, input().split()))
    if c[0] == 0:
        d.append(c[1])
    elif c[0] == 1:
        print(d[c[1]])
    else:
        d.pop()



    


Measured memory_bytes: 13756
import numpy as np

S = input()

tile_color = []
for i in S:
    tile_color.append(int(i))

candidate = np.zeros((2,len(S)))
candidate[0, 0::2] = 1
candidate[1, 1::2] = 1

distance = [np.sum(np.abs(candidate[0,:] - tile_color)), np.sum(np.abs(candidate[1,:] - tile_color))]

print(int(min(distance)))

Measured memory_bytes: 16892
from collections import Counter
n = int(input())
name = [str(input()) for _ in range(n)]
name_first = []
cnt = 0

for i in name:
    name_first.append(i[0])
name_dic = Counter(name_first)
# print(name_dic)

info = [name_dic["M"], name_dic["A"], name_dic["R"], name_dic["C"], name_dic["H"]]
# print(info)
for i in range(5):
    for j in range(5):
        for k in range(5):
            if i < j < k:
                cnt += info[i]*info[j]*info[k]

print(cnt)

Measured memory_bytes: 10880
#include <cassert>
#include <iostream>
#include <iomanip>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <set>
#include <limits>
#include <numeric>
#include <iterator>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  
  int n; //1 .. 6
  cin >> n;

  vector<pair<double, double> > koch = {{0.,0.}, {100., 0.}};

  for(int i = 0; i < n; ++i){
    vector<pair<double, double> > new_koch;
    for(unsigned int j = 0; j < koch.size()-1; ++j){
      const auto s = koch[j], t = koch[j+1];
      const double 
	sin = sqrt(3)/2.0,
	cos = 1./2.;
      const double 
	dx = t.first  - s.first,
	dy = t.second - s.second;
      
      pair<double, double> q1, q2, q3;
      q1 = make_pair( dx/3. + s.first,  dy/3. + s.second);
      q3 = make_pair(-dx/3. + t.first, -dy/3. + t.second);
      q2 = make_pair(q1.first + dx*cos/3. -dy*sin/3., 
		     q1.second+ dx*sin/3. +dy*cos/3.);

      new_koch.push_back(s);
      new_koch.push_back(q1);
      new_koch.push_back(q2);
      new_koch.push_back(q3);
      //new_koch.push_back(t);
    }
    new_koch.push_back(make_pair(100.,0.));
    koch = new_koch;
  }
  
  //output
  for(auto p : koch){
    cout << fixed
	 << setprecision(8) << p.first << " " 
	 << setprecision(8) << p.second <<endl;
  }

  return 0;
}

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

const int MAXN = 3010;
using ll = long long;

int N;
double p[MAXN];
// dp[i][j]: 前i个硬币j个头朝上的概率
double dp[MAXN][MAXN];

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> p[i];
    }

    dp[0][0] = 1; 
    for(int i=1; i<=N; i++) {
        for(int j=0; j<=i; j++) {
            if(j) dp[i][j] += dp[i-1][j-1]*p[i];
            dp[i][j] += dp[i-1][j] * (1-p[i]);
        }
    }
    /*
    for(int i=1; i<=N; i++) {
        dp[i][0] = dp[i-1][0] * (1-p[i]);
        dp[0][i] = 0.0;
    }
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=i; j++) {
            dp[i][j] = dp[i-1][j]*(1-p[i]) + dp[i-1][j-1]*p[i];
        }
    }
    */
    double ans = 0.0;
    for(int i=(N+1)/2; i<=N; i++) {
        ans += dp[N][i];
    }
    cout <<setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 49860
//
// Created by yamunaku on 2019/11/23.
//

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repl(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perl(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD9 998244353
#define MOD1 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)
#define CST(x) cout<<fixed<<setprecision(x)

using ll = long long;
using ld = long double;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
template<typename T>
using heap = priority_queue<T, vector<T>, function<bool(const T, const T)>>;

int main(){
    // CFS;
    int m;
    cin >> m;
    vi d(m);
    vl c(m);
    ll ans = -1;
    ll sum = 0;
    rep(i, m){
        cin >> d[i] >> c[i];
        ans += c[i];
        sum += d[i] * c[i];
    }
    ans+=(sum-1)/9;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
//#include <stdio.h>
//#include <stack>
//#include <queue>
#include <cstdio>
#include <cmath>
#include <iterator>
#include <map>
//#include <fstream>
//#include <list>
//#include <iomanip>
#include <stdlib.h>
#include <cctype>

using namespace std;

#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define ssort(z) sort(z.begin(),z.end())
#define rsort(z) sort(z.rbegin(),z.rend())
#define eerase(z) z.erase(unique(z.begin(),z.end()),z.end())
#define ccnt(z,w) count(z.begin(),z.end(),w)


void printVec(std::vector<int> & vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec1(std::vector<string>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}
void printVec2(std::vector<Int>& vec) {
	std::cout << "";
	for (auto it = vec.begin(); it != vec.end(); ++it) {
		std::cout << *it << " ";
	}
	std::cout << std::endl;
}

Int gcd(Int a, Int b) {
	return b != 0 ? gcd(b, a % b) : a;
}
Int lcm(Int a, Int b) {
	return a / gcd(a, b) *b;
	//a*bは64bit integer overflow
}

bool comp(const string a, const string b) {
	return a.length() < b.length();
}

bool integer(double num) {
	return floor(num) == num;
}

string gen(int num) {
	string str = "";
	for (int i = 0; i < num; i++) str += ".";
	return str;
}
Int fact(int num) {
	if (num == 0) return 1;
	else return num * fact(num - 1);
}


int main() {
	int a, b,c; cin >> a>>b>>c;
	//string s; cin >> s;
	if (b - c >= 0)cout << "delicious";
	else if (c - b <= a)cout << "safe";
	else cout << "dangerous";
	


	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define L(i,u) for(int i=head[u];i;i=nxt[i])
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
const int N = 123,inf=0x3f3f3f3f;
int n,deg[N];Pii T1[N],T2[N];
inline void read(Pii &c){int x,y;scanf("%d%d",&x,&y);if(x>y)swap(x,y);c=Pii(x,y);}
Vi e2[N],e1[N],e[N];int fa[N],ok[N],q[N],f,r;
void dfs(int u, int Fa){
	fa[u]=Fa;per(i,(int)e1[u].size()-1,0)if(e1[u][i]!=Fa)dfs(e1[u][i],u);
}
inline void upd(int u){
	per(i,(int)e[u].size()-1,0)if(deg[e[u][i]]==1&&!ok[e[u][i]]&&ok[fa[e[u][i]]])q[r++]=e[u][i];
}
inline void find(int u){
	ok[u]=1;
	per(i,(int)e2[u].size()-1,0)if(!ok[e2[u][i]]&&fa[e2[u][i]]==u)find(e2[u][i]);
	upd(u);
}
inline int solve(int rt){
//	rep(i,1,n-1)printf("%d %d %d %d\n",T1[i].fi,T1[i].se,T2[i].fi,T2[i].se);puts("");
	memset(ok,0,sizeof(ok));rep(i,1,n)e1[i].clear();
	rep(i,1,n-1)e1[T2[i].fi].pb(T2[i].se),e1[T2[i].se].pb(T2[i].fi);
	dfs(rt,0);memset(deg,0,sizeof(deg));rep(i,1,n-1)deg[T1[i].fi]++,deg[T1[i].se]++;
	rep(i,1,n)e[i].clear();rep(i,1,n)e[fa[i]].pb(i);
	rep(i,1,n)e2[i].clear();rep(i,1,n-1)e2[T1[i].fi].pb(T1[i].se),e2[T1[i].se].pb(T1[i].fi);
	int res=0;f=1;r=1;find(rt);while(f!=r){
		int u=q[f++];if(ok[u])continue;
		ok[u]=2;int v=0;per(i,(int)e2[u].size()-1,0)if(ok[e2[u][i]]!=2)v=e2[u][i];
		deg[v]--;if(deg[v]==1&&ok[fa[v]]&&!ok[v])q[r++]=v;upd(u);res++;
	}
	rep(i,1,n)if(!ok[i])return inf;return res;
}
int main(){//freopen("1.in","r",stdin);
	int T;scanf("%d",&T);
	while(T--){
		scanf("%d",&n);rep(i,1,n-1)read(T1[i]);rep(i,1,n-1)read(T2[i]);
		sort(T1+1,T1+n);sort(T2+1,T2+n);bool same=1;
		rep(i,1,n-1)same&=(T1[i]==T2[i]);
		if(same)puts("0");
		else{
			static int d[N];int res=inf;memset(d,0,sizeof(d));
			rep(i,1,n-1)d[T1[i].fi]++,d[T1[i].se]++;
			rep(rt,1,n)if(d[rt]==1)rep(i,1,n)if(i!=rt){
				int rec=0;rep(j,1,n-1)if(T1[j].fi==rt||T1[j].se==rt){
					if(T1[j].fi==rt)rec=T1[j].se,T1[j].se=i;else rec=T1[j].fi,T1[j].fi=i;
				}
				res=min(res,solve(rt)+1);
				rep(j,1,n-1)if(T1[j].fi==rt||T1[j].se==rt){
					if(T1[j].fi==rt)T1[j].se=rec;else T1[j].fi=rec;
				}
			}
			printf("%d\n",res<inf?res:-1);
		}
	}
	return 0;
}

Measured memory_bytes: 512
#include<stdio.h>

int input(int *h,int *m,int *s);
void output(int t);

int main()
{
	int inh,inm,ins,intime,lefttime;

	while(input(&inh,&inm,&ins)==0)
	{
		intime=inh*3600+inm*60+ins;
		lefttime=7200-intime;
		output(lefttime);
		output(lefttime*3);
	}
	return 0;
}

int input(int *h,int *m,int *s)
{
	scanf("%d %d %d",h,m,s);
	if(*h==-1&&*m==-1&&*s==-1){return 1;}
	else{return 0;}
}

void output(int t)
{
	int t60[3],i,radical=3600;
	for(i=0;i<3;i++)
	{
		t60[i]=t/radical;
		t%=radical;
		radical/=60;
	}
	printf("%02d:%02d:%02d\n",t60[0],t60[1],t60[2]);
}

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

int main(){
  int A,B,C;
  cin >> A >> B >> C;
  for(int i=1; i<=B;i++){
    int X = A*i;
    if(X%B == C){
      cout << "YES" << endl;
      return 0;
    }
  }
  cout << "NO" << endl;
}


Measured memory_bytes: 3520
#include "bits/stdc++.h"
#define ll long long int
using namespace std;
int main()
{
    map<ll,ll> m;
    
    int n;
    cin>>n;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        sum+=x;
        m[x]++;
    }
    int b;
    cin>>b;
    for(int i=0;i<b;i++)
    {
        int x,y;
        cin>>x>>y;
        
        sum= sum-m[x]*x+m[x]*y;
        m[y]+=m[x];
        m[x]=0;
        cout<<sum<<endl;
        
        
        
    }
    
    
    
}


Measured memory_bytes: 9444
from sys import stdin,stdout,setrecursionlimit
setrecursionlimit(10**7)
from collections import defaultdict
def dfs(src):
    vis[src]=1
    for neigh in g[src]:
        if not vis[neigh]:
            dfs(neigh)

for _ in range(1):#int(stdin.readline())):
    # n=int(stdin.readline())
    n,e=list(map(int,stdin.readline().split()))
    g=defaultdict(list);cc=0
    for _ in range(e):
        x,y=list(map(int,stdin.readline().split()))
        g[x]+=[y]
        g[y]+=[x]
    vis=[0]*(n+1)
    for nd in range(1,n+1):
        if not vis[nd]:
            cc+=1
            dfs(nd)
    print(cc-1)

Measured memory_bytes: 49464
#include <iostream>
#include <vector>
using namespace std;
#define INF 10000000

int main(){
  int n,k,ti,tv,tc;
  int d[100];
  vector<int> v[100],w[100];
  
  int minc,mi,i;
  bool flg[100];
  
  cin >> n;
  for (i=0;i<n;i++){
    cin >>ti>>k;
    for (int j=0;j<k;j++){
      cin >> tv>>tc;
      v[ti].push_back(tv);
      w[ti].push_back(tc);
    }
    d[i]=INF;
    flg[i]=false;
  }

  d[0]=0;
  while (true){
    minc=INF;
    for (i=0;i<n;i++){
      if (!flg[i]&&d[i]<minc){
	minc=d[i];
	mi=i;
      }
    }

    for (i=0;i<n;i++){
      //cout << d[i] << " ";
    }
    //cout <<" :" << mi << endl;
    if (minc==INF) break;
    flg[mi]=true;
    for (i=0;i<v[mi].size();i++){
      if (!flg[v[mi][i]]&&d[v[mi][i]]>d[mi]+w[mi][i]){
	//cout <<v[mi][i] <<" "<<d[mi]+w[mi][i] << endl;
	d[v[mi][i]]=d[mi]+w[mi][i];
      }
    }
  }
  
  for (i=0;i<n;i++){
    cout << i <<" "<<d[i]<<endl;
  }
  
  return 0;
}

Measured memory_bytes: 3160
f = input().strip().split()
q = []
for e in f:
    if e == '+':
        q.append(q.pop() + q.pop())
    elif e == '-':
        q.append(-q.pop() + q.pop())
    elif e == '*':
        q.append(q.pop() * q.pop())
    else:
        q.append(int(e))
print(q[0])

Measured memory_bytes: 6724
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
#include <iomanip>
#include <bitset>
using namespace std;

typedef long long int ll;
typedef long double ld;


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


Measured memory_bytes: 256
#include <iostream>

using namespace std;

bool memo[1000001];
int n, x, m, price[30];

bool sosuu(int k) { 
	if (k == 2) return true;
	else if (k < 2) return false;
	else if (k % 2 == 0) return false;
	for (int i = 3; i*i<=k; i += 2)
		if (k % i == 0) return false;
	return true;
}
int next(){
	memo[0] = true;
	for(int i = 0 ; i < n ; i++){
		for(int j = price[i] ; j <= x ; j++)
			memo[j] |= memo[j-price[i]];
	}
}

int main() {
	while (cin >> n >> x, n || x) {
		for (int i = 0; i < n; ++i)
			cin >> price[i];
		for (int i = 0; i < 1000001; ++i) memo[i] = 0;
		m = 0;
		memo[0] = true;
		for(int i = 0 ; i < n ; i++)
			for(int j = price[i] ; j <= x ; j++)
				memo[j] |= memo[j-price[i]];
		
		for (int i = x; i; --i)
			if (memo[i] && sosuu(i)) {
				m = i;
				break;
			}

		if (m) cout << m << endl;
		else cout << "NA" << endl;
	}
	return 0;
}

Measured memory_bytes: 1844
#include <iostream>
#include <cstdlib>
#include <vector>
typedef long long ll;
using namespace std;

int main(void) {
    string S;cin>>S;
    char before = S[0];
    ll cur = 0;
    vector<ll> vc;
    for (int i = 0; i < S.size(); i++) {
        char c = S[i];
        if (c == '<' && c == before) cur++;
        else if (c == '<' && c != before) {
            vc.push_back(cur); 
            cur = 1;

        } else if (c == '>' && c == before) cur--;
        else if (c == '>' && c != before) {
            vc.push_back(cur);
            cur = -1;
        }
        before = c;
    }
    vc.push_back(cur);

    ll vc_before = vc[0];
    for (int i = 1; i < vc.size(); i++) {
        
        ll int_vc = vc[i];
        if (vc_before > 0 && int_vc < 0) {
            if (vc_before < abs(int_vc)) vc[i-1] -= 1;
            else vc[i] += 1;
        }
        vc_before = vc[i];
    }
    ll result = 0;
    for (auto int_vc:vc) {
        result += abs(int_vc) * (abs(int_vc) + 1) / 2;
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3316
import  java.util.*;
class Main{     
	Scanner sc = new Scanner(System.in);   
	int n; 
	int m=-2000000000;  
	int mini;
	   
	void mp(){  
		n=sc.nextInt();
		mini=sc.nextInt();
		
		for(int i=0; i<n-1; i++){         
			int d=sc.nextInt();
		   	m=maxv(m,d-mini);        
			mini=minv(mini,d);     
		}        
		System.out.println(m); 
		}       
	
		int maxv(int a,int b){    
		if(a>b)return a;     
		else return b;     
		}       
	
		int minv(int a,int b){   
		if(a<b)return a;   
		else return b;     
		}    
	           
	public static void main(String[] args){     
		new Main().mp();     
		} 
	}

Measured memory_bytes: 94388
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll MOD = 1e9+7;

#define vec     vector<int>
#define vecll   vector<ll>
#define vec2    vector<vector<int>>
#define vec2ll  vector<vector<ll>>
#define vpair   vector<pair<int, int>>
#define vpairll vector<pair<ll, ll>>

#define rep(i,n)         for(int i=(int)0; i<(int)n; i++)
#define REP(i,m,n)       for(int i=(int)m; i<(int)n; i++)
#define arr(var, n)      vec var(n); rep(i,n){cin >> var[i];}
#define arrll(var, n)    vecll var(n); rep(i,n){cin >> var[i];}
#define all(var)         (var).begin(), (var).end()
#define sortall(var)     sort(all(var))
#define mpair(v1, v2)    make_pair(v1, v2);
#define prt(var)         cout << var << "\n"
#define prtd(n, var)     cout << fixed << setprecision(n) << var << "\n"
#define prt2(v1, v2)     cout << v1 << " " << v2 << "\n"
#define prt3(v1, v2, v3) cout << v1 << " " << v2 << " " << v3 << "\n"
#define prtall(var)      rep(i,var.size()){cout << var[i] << " ";} cout << "\n"

//----------------------------------------------------------------

int main(void) {
  int n;
  cin >> n;
  arr(a,n);

  vec num(n+1);
  num[0]=0;
  rep(i,n){
    num[a[i]]++;
  }

  ll ans=0;
  rep(i,n+1){
    ans+=(ll) num[i]*(num[i]-1)/2;
  }
  rep(i,n){
    prt(ans-num[a[i]]+1);
  }

}


Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 
#define pi 3.1415926535897
#define ll long long int
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mod 1000000007
#define mod1 998244353
#define inf 1000000000000000000
#define inf1 1000000000
#define endl '\n'
vector<ll> adj[100005];
pair<ll,ll> dp[100005];
void dfs(ll v,ll p)
{
	ll a=1,b=1;
	for(auto it:adj[v])
	{
		if(it!=p)
		{
			dfs(it,v);
			a=(a*dp[it].ff)%mod;
			b=(b*((dp[it].ff+dp[it].ss)%mod))%mod;
		}
	}
	dp[v].ff=b;
	dp[v].ss=a;
	return;
}
int main()
{
	fastio;
	#ifdef APNA_IO
		freopen("input.txt" , "rt" ,stdin);
		freopen("output.txt" , "wt" ,stdout);
	#endif
	ll n;
	cin>>n;
	for(ll i=1;i<n;i++)
	{
		ll a,b;
		cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,-1);
	cout<<(dp[1].ff+dp[1].ss)%mod<<endl;
	return 0;
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vpi;
typedef map<int,int> mapii;
typedef map<int,bool> mapib;
typedef map<char,int> mapci;

#define small 1e-9
#define big5 1000000005
#define big7 1000000007
#define big 100000
#define large 200001
#define pi 3.1415926

#define inp(arr,n) for(int i=0;i<n;i++)cin>>arr[i];
#define cum(arr,n,cumm) cumm[0]=0;for(int i=0;i<n;i++)cumm[i+1]=cumm[i]+arr[i];
#define bsdk ios_base::sync_with_stdio(false);cin.tie(NULL);
#define disp(arr) for(auto i:arr)cout<<i<<" ";cout<<"\n"
#define yes cout<<"YES\n"
#define no cout<<"NO\n"
#define m1 cout<<"-1\n"
#define nl <<endl
#define hs cout<<"#"

#define fori(a, b, c) for (a = (b); (a) <= (c); ++(a))
#define ford(a, b, c) for (a = (b); (a) >= (c); --(a))
#define rep(i,n) fori(i,0,n-1)
#define rep1(i,n) fori(i,1,n-1)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pob pop_back
#define ub upper_bound
#define lb lower_bound
#define allv(v) v.begin(), v.end()
#define sorti(v) sort(allv(v))
/*bool isprime[big+1];
vector<int> primes;
void makesieve()
{
    ll i,j;
    rep(i,1000001)
        isprime[i]=false;
    isprime[2]=true;
    for(i=3;i<=big;i+=2)
        isprime[i]=true;
    for(i=3;i<=big;i+=2)
    {
        if(isprime[i])
            for(j=i*i;j<=big;j+=i)
            isprime[j]=false;
    }
    rep(i,big+1)
    {
        if(isprime[i])
            primes.pb(i);
    }
}
ll poww(ll n,ll m){
    if(m==0)return 1;
    if(m==1)return n;
    ll ans = poww(n,m/2);
    if(m%2==1) return (ans*ans)*n;
    else return (ans*ans);
}*/
void solve()
{
   long double a,b;
   cin>>a>>b;
   ll ans=trunc(a*b);
   cout<<ans;
}
int main()
{
    bsdk
    int t;
    //cin>>t;
    t=1;
    while(t--) solve();
    return 0;
}


Measured memory_bytes: 3800
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i,x) for(int i=1;i<=(int)(x);i++)
#define rrep(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(int i=((int)(x));i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>

using namespace std;
int n, m;
int graph[50][50];
int visited[50];
int a[50];
int b[50];

void dfs(int v) {
	rep(i, m) {
		if (!graph[v][i]) continue;
		if (visited[i]) continue;
		visited[i] = 1;
		dfs(i);
	}
}

int main(void) {
	cin >> n >> m;
	rep(i, m) {
		cin >> a[i] >> b[i];
		a[i]--; b[i]--;
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = 1;
	}
	int ans = 0;
	rep(i, m) {
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = 0;
		rep(j, n) visited[j] = 0;
		visited[0] = 1;
		dfs(0);
		rep(j, n) {
			if (!visited[j]) {
				ans++;
				break;
			}
		}
		graph[a[i]][b[i]] = graph[b[i]][a[i]] = 1;
	}
	cout << ans << endl;
	return 0;
}

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

// Define
using ll = int64_t;
using ul = uint64_t;
using ld = long double;
const ll MOD = 1e9 + 7;
const ll INF = LONG_MAX;
const ul MAX = ULONG_MAX;
const char nl = '\n';

#define elif else if
#define def inline auto
#define run __attribute__((constructor)) def _

// Debug
#define debug(x) cerr << (x) << " (L:" << __LINE__ << ")" << '\n'

// Loop
#define inc(i, a, n) for (ll i = (a), _##i = (n); i < _##i; ++i)
#define dec(i, a, n) for (ll i = (a), _##i = (n); i > _##i; --i)
#define rep(i, n) inc(i, 0, n)
#define be(c) begin(c), end(c)

// Stream
#define fout(n) cout << fixed << setprecision(n)
#define fasten cin.tie(0), ios::sync_with_stdio(0)

// Speed
run() { fasten, fout(10); }
#pragma GCC optimize("-O3")
#pragma GCC target("avx")

inline ll gcd(ll a, ll b) {
  for (; a; swap(b %= a, a));
  return b;
}

signed main() {
    int a, b, k;
    cin >> a >> b >> k;
    int g = gcd(a, b);
    vector<int> as;
    for(int i = g; i >= 1; --i) {
        if(a%i == 0 && b%i == 0)
            as.push_back(i);
    }
    cout << as[k-1] << nl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll i, temp,t, n, dp[100100], x, y, M, N;
vector<ll>adj[100010];
bool vis[100010];
int dfs(int x)
{
    if(adj[x].size()==0)
        return 0;
    int ans = 0;
    if(vis[x])
        return dp[x];
    vis[x] = true;
    for(int i=0;i<adj[x].size();i++)
        ans = max(ans, dfs(adj[x][i])+1);
    return dp[x] = ans;
}
int main()
{
    //I am Monim, a tiny creature of Allah
    cin >> N >> M;
    int ans= 0;
    for(i=1;i<=M;i++)
    {
        cin >> x >> y;
        adj[x].push_back(y);
    }
    for(i=1;i<=N;i++)
        if(!vis[i])
            ans = max(ans,dfs(i));
    cout << ans <<endl;
    return 0;
}



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

int main() {
  int A, B, X;
  cin >> A >> B >> X;

  if (A > X) {
    cout << "NO" << endl;
  } else {
    if (A + B >= X) cout << "YES" << endl;
    else cout << "NO" << endl;
  }

  return 0;
}


Measured memory_bytes: 256
import collections
N,K,Q=list(map(int,input().split()))
A=[]
point=[K-Q]*N
for i in range(Q):
    A.append(int(input()))
C=collections.Counter(A)
for i in range(N):
    point[i]+=C[i+1]
    if point[i]>0:
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 19600
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

int main(){
    ll n;
    cin >> n;
    ll a[n];
    rep(i, n)cin >> a[i];
    ll bit = 0;
    ll tail = 0;
    ll ans = 0;
    rep(i, n){
        // cout << tail << " & " << ans << " & " << bit<< " " << a[i] <<  endl;
        if(!(bit&a[i]))bit+=a[i], ans+=i-tail;
        else {
            while((bit&a[i]))bit-=a[tail++];
            ans+=i-tail;
            bit+=a[i];
        }
        
    }
    cout << ans+n << endl;


}

Measured memory_bytes: 1792
import java.util.*;
import java.util.stream.Collectors;

public class Main {

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

        long N = sc.nextLong()-1;

        List<Integer> list = new ArrayList<>();

        list.add(Long.valueOf(N%26).intValue());
        N /= 26;
        while (N > 0) {
            N -= 1;
            list.add(Long.valueOf(N%26).intValue());
            N /= 26;
        }

        Collections.reverse(list);

        char[] alphabet = "abcdefghijklmnopqrstuvwxyz".toCharArray();

        list.stream().map(i -> alphabet[i]).forEach(System.out::print);
    }
}


Measured memory_bytes: 35924
#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    al = list(map(int, input().split()))
    for i in range(n):
        al[i] = al[i] - (i + 1)
    al.sort()

    b = al[(n-1)//2]
    ans = sum([abs(a - b) for a in al])
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 97872
input_list = list(map(int, input().split()))
monster_num = input_list[0]
atk_times = input_list[1]
hps_list = list(map(int, input().split()))
sort_hp_list = sorted(hps_list, reverse=True)
if monster_num < atk_times:
  print(0)
else:
  print(sum(sort_hp_list[atk_times: ]))


Measured memory_bytes: 26180
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
	int n;
	scanf("%d",&n);
	int i,x[200005],y[200005];
	for(i = 0;i < n; i++)
	{
		scanf("%d",&x[i]);
		y[i] = x[i];
	}
	sort(y,y + n);
	int temp = y[n / 2];
	for(i = 0;i < n; i++)
	{
		if(x[i] >= temp)
			printf("%d\n",y[n / 2 - 1]);
		else
			printf("%d\n",temp);
	}
	return 0;
}


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

using namespace std;
#define rep(i, n) for(int i = 0 ; i < (int)(n) ; i++)
typedef long long ll;
typedef long double Double;

#ifndef INPUTS_DIR
#define INPUTS_DIR "./"
#endif


void solve(ll D, ll G, vector<ll> p, vector<ll> c) {
    vector<int> ps;
    for (int i = 0; i < D; i++) {
        ps.push_back(i);
    }
    int ans = 1e9;
    do {
        ll g = G;
        int cnt = 0;
        for (int i = 0; i < D; i++) {
            if (g < 0) break;
            ll C = c[ps[i]];
            ll P = p[ps[i]];
            int u = (int) min(P - 1, g / ((ps[i] + 1) * 100));
            cnt += u;
            P -= u;
            g -= u * (ps[i] + 1) * 100;
            if (P == 0) {
                g -= C;
            } else {
                if (g <= 0) break;
                while (P > 0 && g > 0) {
                    g -= (ps[i] + 1) * 100;
                    cnt++;
                    P--;
                }
                if (P == 0) g -= C;
            }
            if (g <= 0) break;
        }
        ans = min(ans, cnt);
    } while (next_permutation(ps.begin(), ps.end()));
    cout << ans << endl;
}


void main_(istream &cin) {
    ll G;
    ll D;
    cin >> D;
    vector<ll> p(D - 1 + 1);
    vector<ll> c(D - 1 + 1);
    cin >> G;
    for (int i = 0; i <= D - 1; i++) {
        cin >> p[i];
        cin >> c[i];
    }
    solve(D, G, p, c);
}

int main() {
#ifdef INTELLIJ
    ifstream ifs(string(INPUTS_DIR) + "in_1.txt");
    if (ifs.is_open()) {
        main_(ifs);
        ifs.close();
    } else {
        cerr << "Error: no input." << endl;
    }
#else
    ios::sync_with_stdio(false);
    cin.tie(0);
    main_(cin);
#endif
}





Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(void) {
 
    int n;
    cin >> n;
 
    int b,f,r,v;
    int a[4][3][10] = {};
 
    for(int i=0;i<n;i++) {
        cin >> b >> f >> r >> v;
        a[b-1][f-1][r-1] += v;
    }
 
    for(int i=0;i<4;i++) {
        for(int j=0;j<3;j++) {
            for(int k=0;k<10;k++) {
                cout << " " << a[i][j][k];
            }
            cout << endl;
        }
        if(i != 3) {
            cout << "####################" << endl;
        }
 
    }
 
    return 0;
}	

Measured memory_bytes: 1164
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

const double PI = 3.1415926535897932384626433832795;

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

int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : abs(x); }
int lcm(int x, int y) { return x / gcd(x, y) * y; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }

string solve(string s) {
	bool isYYMM = true, isMMYY = true;

	// YY/MM
	int mm = (int)(s[2] - '0') * 10;
	mm  += (int)(s[3] - '0');

	if (mm <= 0 || 12 < mm) {
		isYYMM = false;
	}

	// MM/YY
	mm = (int)(s[0] - '0') * 10;
	mm += (int)(s[1] - '0');

	if (mm <= 0 || 12 < mm) {
		isMMYY = false;
	}

	if (isYYMM && isMMYY) {
		return "AMBIGUOUS";
	} else if (isYYMM && !isMMYY) {
		return "YYMM";
	} else if (!isYYMM && isMMYY) {
		return "MMYY";
	} else {
		return "NA";
	}
}

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

	string s;
	cin >> s;

	cout << solve(s) << endl;
	return 0;
}


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

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
// ascending order
#define asort(array, N) sort(array, array + N)
// descending order
#define asort_r(array, N) sort(array, array + N, greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

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

	string s;
	cin >> s;
	int n = s.size();
	if(s[0] != 'A') {
		cout << "WA" << endl;
		return 0;
	}

	int count = 0;
	int idx = 0;

	for(int i = 2; i < n - 1; i++) {
		if(s[i] == 'C') { 
			count++;
			idx = i;
		}
	}
	if(count != 1) {
		cout << "WA" << endl;
		return 0;
	}

	for(int i = 1; i < n; i++) {
		if(i == idx) continue;
		if('A' <= s[i] && s[i] <= 'Z') {
			cout << "WA" << endl;
			return 0;
		}
	}
	cout << "AC" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int H,W,i,j; //??????H??¨???W
	
	while(1){
		scanf("%d %d", &H, &W);
		if(H == 0 && W == 0 )break;
		
		for( i = 1; i <= H; i++ ){		//i??????????´???§?????????
			for( j = 1; j <= W; j++ ){	//j???????´???§?????????
				
				if( j%2 == 1 ){			//j????\???°?????¨???
					if(i%2 == 1){		//i????\???°?????¨???
						printf("#");
					}else {				//i?????¶??°?????¨???
						printf(".");
					}
				}else if( j%2 == 0 ){	//j?????¶??°?????¨???
					if( i%2 == 0){		//i????\???°?????¨???
						printf("#");
					}else {				//i?????¶??°?????¨???
						printf(".");
					}
				}	
			}
			printf("\n");
		}
		printf("\n");
	}
	return 0;
}

Measured memory_bytes: 1000
#include<iostream>
#include<stack>
using namespace std;
int main(){
	int n,q,key,t,x;
	cin>>n>>q;
	stack<int> S[1001];
	for(int i=0;i<q;i++){
		cin>>key>>t;
		if(key==0){
			cin>>x;
			S[t].push(x);
		}else if(key==1){
			if(S[t].empty()==0)cout<<S[t].top()<<endl;
		}else{
			if(S[t].empty()==0)S[t].pop();
		}
	}
	return 0;
}


Measured memory_bytes: 4396
#include<bits/stdc++.h>
using namespace std;
int main(){
  int L, R, D;
  cin >> L >> R >> D;
  int ans = 0;
  for(int i=L; i<=R; i++){
    if(i %D == 0){
      ans++;
    }
  }
  cout << ans << endl;
}

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

 /* int sub(int x,int y) {
    if ( x > y ) {
      return x-y;
    }
    else {
      return y-x;
    }
  }*/
  
int main() {
  int64_t n,k;
  cin >> n >> k;
  int64_t m = n%k;
  int64_t l = m-k;
  
  if ( l < 0 ) {
    l = l*(-1);
  }
  
  cout << min(l,m) << endl;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int value[22];
int cost[22];
int sub[22];

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

    int N;
    cin >> N;

    ll sum = 0;

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

    for (int i = 0; i < N; i++){
        ll temp = value[i] - cost[i];
        sum += (temp > 0) ? temp : 0;
    }

    cout<< sum;
}

Measured memory_bytes: 256
fn solve(s: String) -> usize {
    let cs = s.chars().collect::<Vec<_>>();

    let mut cnt = 1;
    let mut lastc = cs[0];
    for c in cs[1..].iter() {
        if *c != lastc {
            cnt += 1;
            lastc = *c;
        }
    }

    cnt
}

#[test]
fn test_solve() {
    assert_eq!(solve("aabbbbaaca".to_string()), 5);
    assert_eq!(solve("aaaaa".to_string()), 1);
}

#[allow(unused_macros)]
macro_rules! parse_line {
    ( $t:ty ) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            iter.next().unwrap().parse::<$t>().unwrap()
        }
    );

    ( $( $t:ty), +) => (
        {
            let mut line = String::new();
            ::std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            ( $(iter.next().unwrap().parse::<$t>().unwrap()),* )
        }
    );
}

#[allow(unused_macros)]
macro_rules! read_line {
    () => {{
        let mut line = String::new();
        ::std::io::stdin().read_line(&mut line).unwrap();
        line.pop();
        line
    }};
}

#[allow(unused_macros)]
macro_rules! parse_vec {
    ( $t:ty ) => {{
        let mut line = String::new();
        ::std::io::stdin().read_line(&mut line).unwrap();
        let iter = line.split_whitespace();
        iter.map(|v| v.parse::<$t>().unwrap()).collect::<Vec<_>>()
    }};
}

fn main() {
    let _n = parse_line!(usize);
    let s = read_line!();

    println!("{}", solve(s));
}


Measured memory_bytes: 4352
(defun compressor (list)
  (let* ((ret nil))
    (map 'nil (lambda (x)
                (if (and ret (equal x (caar ret)))
                    (incf (cdar ret))
                    (push (cons x 1) ret)))
         list)
    ret))

(let* ((n (read))
       (lst (sort (loop :repeat n :collect (read)) #'<))
       (lst-a (compressor lst)))
  (princ (reduce #'+ (mapcar (lambda (x)
                               (if (< (cdr x) (car x))
                                   (cdr x)
                                   (- (cdr x) (car x)))) lst-a))))


Measured memory_bytes: 59752
N,C = gets.split.map(&:to_i)
ch = Array.new(C){[]}
N.times do
  s,t,c = gets.split.map(&:to_i)
  ch[c-1] << [s,t]
end
ch.each{|seq| seq.sort_by!(&:first)}
merged_ch = Array.new(C){[]}
ch.each_with_index do |seq, i|
  m_seq = merged_ch[i]
  seq.each do |s, t|
    if m_seq.empty?
      m_seq << [s,t]
    elsif m_seq[-1][1] == s
      m_seq[-1][1] = t
    else
      m_seq << [s,t]
    end
  end
end

max = 2*10**5+10
imos = Array.new(max, 0)
merged_ch.each do |seq|
  seq.each do |s, t|
    imos[2*s-1] += 1
    imos[2*t] -= 1
  end
end

(max-1).times do |i|
  imos[i+1] += imos[i]
end
puts imos.max

Measured memory_bytes: 13432
// solution by formal power series

#include <bits/stdc++.h>

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

using namespace std;

class mint{
	static const int MOD=1e9+7;
	int x;
public:
	mint():x(0){}
	mint(long long y){ x=y%MOD; if(x<0) x+=MOD; }

	mint& operator+=(const mint& m){ x+=m.x; if(x>=MOD) x-=MOD; return *this; }
	mint& operator-=(const mint& m){ x-=m.x; if(x<   0) x+=MOD; return *this; }
	mint& operator*=(const mint& m){ x=1LL*x*m.x%MOD; return *this; }
	mint& operator/=(const mint& m){ return *this*=inverse(m); }
	mint operator+(const mint& m)const{ return mint(*this)+=m; }
	mint operator-(const mint& m)const{ return mint(*this)-=m; }
	mint operator*(const mint& m)const{ return mint(*this)*=m; }
	mint operator/(const mint& m)const{ return mint(*this)/=m; }

	friend mint inverse(const mint& m){
		int a=m.x,b=MOD,u=1,v=0;
		while(b>0){ int t=a/b; a-=t*b; swap(a,b); u-=t*v; swap(u,v); }
		return u;
	}

	friend istream& operator>>(istream& is,mint& m){ long long t; is>>t; m=mint(t); return is; }
	friend ostream& operator<<(ostream& os,const mint& m){ return os<<m.x; }
	int to_int()const{ return x; }
};

int main(){
	int n,k; scanf("%d%d",&n,&k);

	mint dp[100001]={1};
	rep(i,n){
		int a; scanf("%d",&a);
		// *(1-x^{a_i+1})
		for(int j=k;j>=a+1;j--) dp[j]-=dp[j-(a+1)];
		// /(1-x)
		rep(j,k) dp[j+1]+=dp[j];
	}
	printf("%d\n",dp[k].to_int());

	return 0;
}


Measured memory_bytes: 640
from collections import deque

N, M = map(int, input().split())
F_C_of_S = [{} for i in range(N)]
# Companies of Station
C_of_S = {}

# def Union-find
parent = [-1]*M
def root(x):
    if (parent[x] < 0): return x
    else:
        parent[x] = y = root(parent[x])
        return y

def unite(x, y):
    px = root(x); py = root(y);
    if (px == py): return False
    if (parent[px] > parent[py]):
        px = root(y); py = root(x);
    parent[px] += parent[py]
    parent[py] = px
    return True

# Union-find
pqcs = []
for i in range(M):
    p, q, c = map(int, input().split())
    p -= 1; q -= 1;
    pqcs += [(p, q, c)]
    # The first
    if not c in F_C_of_S[p]:
        F_C_of_S[p][c] = i
    # else
    else:
        unite(F_C_of_S[p][c], i)
    C_of_S.setdefault(p, set()).add(c)
    # The first
    if not (c in F_C_of_S[q]):
        F_C_of_S[q][c] = i
    # else
    else:
        unite(F_C_of_S[q][c], i)
    C_of_S.setdefault(q, set()).add(c)

# stations of company
S_of_C = {}
for i in range(M):
    p, q, c = pqcs[i]
    c_set = S_of_C.setdefault(root(i), set())
    c_set.add(p); c_set.add(q);

Q = deque([(0, 0, 0)])
# cost to go to the stations from station_0
dist = [float('inf')] * N
dist[0] = 0

gdist = [float('inf')] * M

while Q:
    cost, v, flag = Q.popleft()
    if not (flag):  # (flag == 0) then gdist_update
        for l in F_C_of_S[v].values():
            l = root(l)
            if (cost < gdist[l]):
                gdist[l] = cost
                Q.appendleft((cost, l, 1))
    else:  # (flag == 1) then dist_update
        for s in S_of_C[v]:
            if (cost + 1 < dist[s]):
                dist[s] = cost + 1
                Q.append((cost + 1, s, 0))

print(dist[N - 1] if dist[N - 1] < float('inf') else -1)

Measured memory_bytes: 196920
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define MOD 1000000007
template <typename Type>
istream &operator>>(istream &in, vector<Type> &vec) {
    ll n = vec.size();
    for (ll i = 0; i < n; i++)
        in >> vec[i];
    return in;
}
template <typename Type>
ostream &operator<<(ostream &out, vector<Type> &vec) {
    for (auto val : vec)
        out << val << " ";
    return out;
}
#define PI 3.14159265
void solve()
{
    ll n;
    cin>>n;
    vector<ll>a(n);
    cin>>a;
    ll ans=0;
    ll maxa[n];
    maxa[0] = a[0];
    for(ll i=1;i<n;i++)
    {
        maxa[i] = max(maxa[i-1],a[i]);
    }
    for(ll i=n-1;i>=0;i--)
    {
        ans+=maxa[i]-a[i];
    }
    cout<<ans<<endl;
}
int main()
{
    ll t=1;
    // cin>>t;
    while(t--)
    solve();
    return 0;
}

Measured memory_bytes: 6420
tmp = input().split()
N = int(tmp[0])

ListG = []

for i in range(N):
    ListG.append(input().split())

ListG.sort()
p = 1
for i in range(N-1):
    if ListG[i] == ListG[i+1]:
        continue
    else:
        p = p +1

print(p)

Measured memory_bytes: 55592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using V = vector<ll>;
#define _GLIBCXX_DEBUG
#define rep(i, a) for(int i = 0; i < a; i++)
#define ALL(v) v.begin(), v.end()

int main(){
    int a,b; cin>>a>>b;
    if(a>b) cout<<a-1<<endl;
    else cout<<a<<endl;
}

Measured memory_bytes: 256
using Yorukatsu044.Questions;
using Yorukatsu044.Extensions;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace Yorukatsu044.Questions
{
    /// <summary>
    /// ABC130 C
    /// </summary>
    public class QuestionC : AtCoderQuestionBase
    {
        public override IEnumerable<object> Solve(TextReader inputStream)
        {
            var whxy = inputStream.ReadIntArray();
            long w = whxy[0];
            long h = whxy[1];
            long x = whxy[2];
            long y = whxy[3];

            var half = w * h / 2.0;
            var canDivideArbitrarily = w == x * 2 && h == y * 2;
            yield return $"{half} {(canDivideArbitrarily ? 1 : 0)}";
        }
    }
}


namespace Yorukatsu044
{
    class Program
    {
        static void Main(string[] args)
        {
            IAtCoderQuestion question = new QuestionC();    // 問題に合わせて書き換え
            var answers = question.Solve(Console.In);
            foreach (var answer in answers)
            {
                Console.WriteLine(answer);
            }
        }
    }
}

#region Base Classes

namespace Yorukatsu044.Questions
{

    public interface IAtCoderQuestion
    {
        IEnumerable<object> Solve(string input);
        IEnumerable<object> Solve(TextReader inputStream);
    }

    public abstract class AtCoderQuestionBase : IAtCoderQuestion
    {
        public IEnumerable<object> Solve(string input)
        {
            var stream = new MemoryStream(Encoding.Unicode.GetBytes(input));
            var reader = new StreamReader(stream, Encoding.Unicode);

            return Solve(reader);
        }

        public abstract IEnumerable<object> Solve(TextReader inputStream);
    }

}

#endregion

#region Extensions

namespace Yorukatsu044.Extensions
{
    internal static class TextReaderExtensions
    {
        internal static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader));
        internal static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader));
        internal static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader));
        internal static string ReadString(this TextReader reader) => reader.ReadLine();

        internal static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray();
        internal static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray();
        internal static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray();
        internal static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator);
    }
}

#endregion

Measured memory_bytes: 13524
#include <bits/stdc++.h>
#define int long long 

using namespace std;
const int maxn = 1e6 + 7;
string s[maxn];

int n, a[maxn];

int cnt(int x)
{
	int ans = 0;
	int val = 2;
	while(val <= x)
	{
		ans += x / val;
		val <<= 1;
	}
	return ans;
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
	cin >> n;
	for(int i = 1; i <= n; i++)
	{
		char s;
		cin >> s;
		a[i] = s - '0';
		//cin >> a[i];
	}
	n--;
	for(int i = 1; i <= n; i++)
	{
		a[i] = abs(a[i] - a[i + 1]);
	}
	if(n == 1) return cout << a[1], 0;
	int ans = 0;
	for(int i = 0; i < n; i++)
	{	
		int sum2 = cnt(n - 1) - cnt(i) - cnt(n - 1 - i);
		if(sum2 == 0)
		{
			if(i & 1) ans -= a[i + 1];
			else ans += a[i + 1];
		}
	}
	if(ans % 2 != 0)
	{
		cout << 1 << '\n';
	}
	else
	{
		int d[3];
		d[0] = d[1] = d[2] = 0;
		for(int i = 1; i <= n; i++)
		{
			d[a[i]]++;
		}
		if(d[1] == 0)
		{
			for(int i = 0; i < n; i++)
			{	
				int sum2 = cnt(n - 1) - cnt(i) - cnt(n - 1 - i);
				if(sum2 == 0)
				{
					if(i & 1) ans -= a[i + 1] / 2;
					else ans += a[i + 1] / 2;
				}
			}
			if(ans % 2 != 0) 
			{
				cout << 2 << '\n';
				exit(0);
			}
		}
		cout << 0;
	}
}

Measured memory_bytes: 16000
import kotlin.system.exitProcess

fun main(args: Array<String>) {
	val (n, m) = readLine()!!.split(' ').map { it.toLong() }
	val s = readLine()!!
	val t = readLine()!!

	val l = lcm(n, m)
	val dic = mutableMapOf<Long, Char>()

	for ((i, c) in s.withIndex()) {
		val j = l / n * i
		dic[j] = c
	}

	for ((i, c) in t.withIndex()) {
		val j = l / m * i
		if (dic[j] != null && dic[j] != c) {
			println(-1)
			exitProcess(0)
		}
	}
	println(l)
}

fun gcd(a: Long, b: Long): Long {
	return when {
		a < b -> {
			gcd(b, a)
		}
		b == 0L -> {
			a
		}
		else -> {
			gcd(b, a % b)
		}
	}
}

fun lcm(a: Long, b: Long): Long {
	return (a * b) / gcd(a, b)
}


Measured memory_bytes: 48204
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    int l= c-b;
    int count=0;
    
    if(b>c)
    { count=b+c;}
    
    else if(b==c)
    { count=2*b;}
    
    else if(c>b)
    { count=(2*b);
     if(l==a)
    { count=count+l;}
    
    else if(a>l)
    { count+=l;}
    
    else if(l>a)
    { count+=(a+1);}
    }
    
    cout<<count;
}
    
    
    


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

int main(void) {
	int a, b, n;
	cin >> a >> b;

	if (b >= 100)
		n = 1000 * a + b;
	else if (b >= 10)
		n = 100 * a + b;
	else
		n = 10 * a + b;

	bool ans = false;
	for (int i = 1; i * i <= n; ++i) {
		if (n == i * i) {
			ans = true;
			break;
		}
	}

	if (ans)
		cout << "Yes\n";
	else
		cout << "No\n";
	return 0;
}


Measured memory_bytes: 256