akhauriyash/Code-Regression huggingface dataset:
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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

//for loop関係
#define rep(i,a,n) for(int i=(a);i<(n);++i)
#define repe(i,a,n) for(int i=(a);i<=(n);++i)
#define rrep(i,n,a) for(int i=(n);n>(a);--i)
#define rrepe(i,n,a) for(int i=(n);n>=(a);--i)

//略記
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define ENDL << "\n"

using ll = long long;
using P = pair<int,int>;
using itn = int;

//定数
const int INF = 1<<30;
const ll MOD = 1000000007;
const long double PI =(acos(-1));

//Degree <-> Radian
double toRad(double d){ double rad; rad=d*PI/180; return rad; }
double toDegree(double rad){ double d; d=rad*180/PI; return d; }
//The least common multiple : lcm
ll lcm(int a,int b){ return a*b/__gcd(a,b); }
//素数判定
bool isPrime(int n){
    int i; 
    if(n<2) return 0;
    else if(n==2) return 1;
    if(n%2==0) return 0;
    for(i=3;i*i<=n;i+=2) if(n%i==0) return 0;
    return 1;
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k,x;
    cin >> k >> x;
    if(500*k>=x) cout << "Yes" ENDL;
    else cout << "No" ENDL;
    
    return 0;
}

Measured memory_bytes: 3608
#include <stdio.h>

int a[110];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int sm = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            sm += (a[i] * a[j]);
        }
    }
    printf("%d\n", sm);
}

Measured memory_bytes: 128
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
int main()
{
	int num;
	scanf("%d", &num);
	string s;
	cin >> s;
	int query;
	scanf("%d", &query);
	for (int p = 0; p < query; p++)
	{
		int z;
		scanf("%d", &z);
		ll cnt = 0, cd = 0, cm = 0, ans = 0;
		for (int i = 0; i < num; i++)
		{
			if (s[i] == 'D')cd++;
			else if (s[i] == 'M')cnt += cd, cm++;
			else if (s[i] == 'C')ans += cnt;
			if (i >= z - 1)
			{
				if (s[i - z + 1] == 'D')cnt -= cm, cd--;
				else if (s[i - z + 1] == 'M')cm--;
			}
		}
		printf("%lld\n", ans);
	}
}

Measured memory_bytes: 1412
n, k = gets.split.map(&:to_i)
arr = []
count = 0

n.times do
  arr.push gets.split.map(&:to_i)
end

arr.sort_by! { |e| e.first }

0.upto(n-1) do |i|
  count += arr[i].last
  if count >= k
    puts arr[i].first
    break
  end
end


Measured memory_bytes: 12664
h = 0
n = 0
m = 0
s = 0
S = int(input())
h = int(S / 3600)
n = int(S % 3600)
m = int(n / 60)
s = int(n % 60)
print(str(h) + ":" + str(m) + ":" + str(s))



Measured memory_bytes: 5588
#include <stdio.h>

int main(void) {
  int A[100], i, n, sw;

  scanf("%d", &n);
  for (i = 0; i < n; i++)  {
    scanf("%d", &A[i]);
  }
  
  sw = bubbleSort(A, n);

  for (i = 0; i < n; i++)  {
    if (i)
      printf(" ");
    printf("%d", A[i]);
  }
  printf("\n");
  printf("%d\n", sw);

  return 0; 
}

int bubbleSort(int A[], int n)  {
  int i, j, sw = 0, temp, flag = 1;

  for ( i = 0; flag == 1; i++)  {
    flag = 0;
    for (j = n-1; j >= i+1; j--)  {
      if (A[j] < A[j-1])  {
        temp = A[j];
        A[j] = A[j-1];
        A[j-1] = temp; 
        flag = 1;
        sw++;
      }
    }
  }
  return sw;
}

    

Measured memory_bytes: 1852
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define perl(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define pb push_back
#define ins insert
#define pqueue(x) priority_queue<x,vector<x>,greater<x>>
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
#define vtpl(x,y,z) vector<tuple<x,y,z>>
#define rev(x) reverse(x);
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
using vpl=vector<pl>;
using vvpl=vector<vpl>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[8]={1,0,-1,0,1,1,-1,-1};
const ll dx[8]={0,-1,0,1,1,-1,1,-1};
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

void rle(string s,vector<char> &cha,vector<ll> &num){
    ll a=0,cnt=0;
    string t;char x=s[0];
    while(a<s.size()){
        if(x==s[a])cnt++;
        else{
            cha.pb(x);num.pb(cnt);
            x=s[a];cnt=1;
        }
        a++;
    }
    cha.pb(x);num.pb(cnt);
}

int main(){
    ll n;cin >> n;
    string s;cin >> s;
    vl num;vector<char> c;
    rle(s,c,num);
    if(c[0]=='.')num[0]=0;
    if(*c.rbegin()=='#')*num.rbegin()=0;
    ll w=0,b=0;
    rep(i,c.size()){
        if(c[i]=='#')b+=num[i];
        else w+=num[i];
    }
    ll ans=w;
    ll cnt=0;
    rep(i,c.size()){
        if(c[i]=='#'&&i!=c.size()-1){
            w-=num[i+1];
            cnt+=num[i];
            chmin(ans,w+cnt);
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 5956
/**   Created by: Marcos Portales
          Codeforces User: marcosportales
          Country: Cuba
                         **/
#include<bits/stdc++.h>
using namespace std;
/// Macros:
#define int long long
#define f first
#define s second
#define db(x) cerr << #x << ": " << (x) << '\n';
#define pb push_back
#define lb lower_bound
#define up upper_bound
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
#define enl '\n'
#define vi vector<int>
#define sz size
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
typedef pair<int,int> ii;
typedef long double ld;
typedef unsigned long long ull;
/// Constraints:
const int maxn = 2*1e5+1;
const int mod = 1000000009;
const ld eps = 1e-9;
const int inf = ((1ll<<31ll)-1ll);
const int INF = 10000000000000000ll;
const ld pi = acos(-1);
/// Prime Numbers:
// 2, 173, 179, 181, 197, 311, 331, 737, 1009, 2011, 2027, 3079, 4001, 10037, 10079, 20011, 20089;
// 100003, 100019, 100043, 200003, 200017, 1000003, 1000033, 1000037, 1000081;
// 2000003, 2000029, 2000039, 1000000007, 1000000021, 2000000099;
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lgx(x,b) ( log(x) / log(b) )
/// Red-Black Tree Template ---------------------------------
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
/// Quick Pow------------------------------------------------
int qpow(int b,int e){
    if( !e ) return 1;
    if( e & 1 ) return qpow(b,e-1) * b;
    int pwur = qpow(b,e>>1);
    return pwur * pwur;
}
int modinv(int x){
    return qpow(x,mod-2);
}
/// Criba de Eratostenes ------------------------------------
const int pr=10000;
map<int,int>isp;
void criba(){
    for(int i=0;i<=pr;i++)isp[i]=i;
    isp[0]=isp[1]=-1;
    for(int i=2;i*i<=pr;i++){
        if(isp[i]==i){
        for(int j=i+i;j<=pr;j+=i)
            isp[j]=i;
        }
    }
}
/// My Code -------------------------------------------------

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout.setf(ios::fixed); cout.precision(0);
    srand(time(NULL));

    ///freopen("a.in","r",stdin);
    ///freopen("a.out","w",stdout);
    ///criba();
    vi v(3);int k;
    rep(i,3)cin>>v[i];cin>>k;
    sort(all(v));
    cout<<v[0]+v[1]+v[2]*qpow(2,k)<<enl;
    return 0;
}


Measured memory_bytes: 3656
#include <iostream>
#include <algorithm>
#include <tuple>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
using ll = long long;

int main()
{
    int n, t;
    cin >> n >> t;
    vector<int> a(n,0);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    vector<int> mx(n-1,0);
    mx[n-2] = a[n-1];
    for(int i = n-3; i >= 0; i--){
        mx[i] = max(mx[i+1], a[i+1]);
    }
    // for(int i = 0; i < n-1; i++){
    //     //cout << "mx: " << mx[i] << endl;
    // }
    map<int, int> mer;
    int tmp = 0, m = 0;
    for(int i = 0; i < n; i++){
        tmp = mx[i]-a[i];
        mer[tmp]++;
        m = max(m, tmp);
    }
    int ans = mer[m];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8708
#include<bits/stdc++.h>
#define Rushia_mywife ios::sync_with_stdio(0);cin.tie(0);
#define rep(i,head,n) for(int i=(head);i<n;i++)
#define int long long
#define F first
#define S second
#define pb push_back
#define p2(n) (1<<(n))
#define lg2(n) __lg(n)
using namespace std;
using ll = long long;
using pii = pair<long long,long long>;
using ld = long double;
mt19937 mt_rand(time(0));
const int mod = 1000000007;
const int hnum = 998244353;
const ld PI = acos(-1);
const int N = 2e5+10;

int n,m;
int p[N];
int sz[N];

int fp(int x){
    return p[x]==-1 ? x : p[x] = fp(p[x]);
}
void U(int x,int y){
    x = fp(x);
    y = fp(y);
    if(x==y)
        return;
    p[x] = y;
    sz[y] += sz[x];
}

void solve(){
    cin >> n >> m;
    memset(p,-1,sizeof(p));
    rep(i,0,N)
        sz[i] = 1;
    rep(i,0,m){
        int a,b; cin >> a >> b;
        U(a,b);
    }
    int mx = 0;
    rep(i,1,n+1)
        mx = max(mx,sz[fp(i)]);
    cout << mx << '\n';
}

signed main(){
    Rushia_mywife
    //int t; cin >> t;
    //while(t--)
    solve();
}

Measured memory_bytes: 12816
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main()
{
    int n,k;
    cin >> n >> k;
    int val[n];
    for (int q = 0; q < n; q++)
    {
        cin >> val[q];
    }
    int dp[n];
    dp[0]=0;
    for (int q = 1; q < n; q++)
    {
        dp[q]=1e9+10;
        for (int w = 1; w <= k; w++)
        {
            if (q-w<0)
            {
                break;
            }
            int temp = val[q]-val[q-w];
            if (temp<0)
            {
                temp *=-1;
            }
            dp[q]=min(dp[q], temp+dp[q-w]);
        //cout << q << " " << temp<< endl;
        }
    }
    cout << dp[n-1];
    return 0;
}


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

int main(){

int N;
cin >> N;
int A[N];
int kaisuu=0,i,j,k;
for(i=0;i<N;i++)cin >> A[i];
for(k=N-1;k>=0;k--)
{
for(i=N-1;i>0;i--)
{
  if(A[i]<A[i-1])
  {
    j = A[i];
    A[i] = A[i-1];
    A[i-1]=j;
    kaisuu++;
  }
}
}
for(i=0;i<N-1;i++)cout << A[i] << " ";
cout <<A[N-1] << endl;
cout << kaisuu << endl;

}


Measured memory_bytes: 3104
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

#define MAXCOIN 2500LL

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

	long long n, m, i, j, k, x, y, s, a, b, t, coin, id;
	cin >> n >> m >> s;

	vector<vector<tuple<long long, long long, long long>>> adj(n + 1);
	vector<long long> c(n + 1), d(n + 1);

	for (i = 0; i < m; i++) {
		cin >> x >> y >> a >> b;
		adj[x].push_back({ y, a, b });
		adj[y].push_back({ x, a, b });
	}

	for (i = 1; i <= n; i++) cin >> c[i] >> d[i];

	vector<vector<long long>> dp(n + 1, vector<long long>(MAXCOIN + 1, (1LL << 60)));	// dp[city][silve coins] = shortest time
	s = min(s, MAXCOIN);
	dp[1][s] = 0;
	priority_queue<tuple<long long, long long, long long>> pq;		// <-time, id, coin>
	pq.push({ 0, 1, s });

	while (!pq.empty()) {
		tie(t, id, coin) = pq.top();
		t = -t;
		pq.pop();
		if (dp[id][coin] != t) continue;

		// exchange
		if (dp[id][min(MAXCOIN, coin + c[id])] > t + d[id]) {
			dp[id][min(MAXCOIN, coin + c[id])] = t + d[id];
			pq.push({ -t - d[id], id, min(MAXCOIN, coin + c[id]) });
		}

		// use it to go somewhere
		for (auto p : adj[id]) {
			tie(x, a, b) = p;

			if (coin < a) continue;

			if (t + b < dp[x][coin - a]) {
				dp[x][coin - a] = t + b;
				pq.push({ -t - b, x, coin - a });
			}
		}
	}

	vector<long long> ans(n + 1, (1LL << 60));
	for (i = 2; i <= n; i++) {
		for (j = 0; j <= MAXCOIN; j++) ans[i] = min(ans[i], dp[i][j]);
	}

	for (i = 2; i <= n; i++) cout << ans[i] << "\n";

	return 0;
}



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

ans = 0

for i in range(n):
    ab = a[i] - b[i]
    
    if ab < 0:
        ans += a[i]
        b[i] -= a[i]
        a[i] = 0
        b[i] = abs(ab)
        ab = a[i+1] - b[i]
        
        if ab <= 0:
            ans += a[i+1]
            a[i+1] = 0
            b[i] = abs(ab)
        else:
            ans += b[i]
            a[i+1] -= b[i]
            b[i] = 0
           
    elif ab == 0:
        ans += b[i]
        a[i] = 0
        b[i] = 0
        
    else:
        ans += b[i]
        b[i] = 0
        
print(ans)

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

int main(void)
{
    int ans;
    int change;
    int money;
    
    while (1){
        scanf("%d", &money);
        if (money == 0) break;
        
        ans = 0;
        change = 1000 - money;
        while (change != 0){
            if (500 <= change){
                change -= 500;
                ans++;
                continue;
            }
            if (100 <= change){
                change -= 100;
                ans++;
                continue;
            }
            if (50 <= change){
                change -= 50;
                ans++;
                continue;
            }
            if (10 <= change){
                change -= 10;
                ans++;
                continue;
            }
            if (5 <= change){
                change -= 5;
                ans++;
                continue;
            }
            if (1 <= change){
                change -= 1;
                ans++;
                continue;
            }
        }
        printf("%d\n", ans);
    }
    
    return (0);
}

Measured memory_bytes: 0
n = int(input())
for i in range(n):
    a, b, c  = map(int, input().split())
    d = 2
    e = 1/2
    
    if (a**d+b**d)**e == c or (a**d+c**d)**e == b or (c**d+b**d)**e == a:
        print('YES')
        
    else:
        print('NO')


Measured memory_bytes: 5640
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define ALL(a) a.begin(),a.end()
typedef long long ll;
#define INF 1<<30

int main()
{
    int A,B;
    cin >> A >> B;
    bool exist = false;
    FOR(i,1,2000){
        if(floor(i*0.08)==A&&floor(i*0.1)==B){
            exist = true;
            cout << i << endl;
            break;
        }
    }
    if(!exist)cout << "-1" << endl;
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
from collections import Counter
MOD = 998244353


def solve(n,d):
    if d[0] != 0:
        return 0
    dc = Counter(d)
    if dc[0] > 1:
        return 0
    res = 1
    k = 1
    dmax = max(d)
    while k <= dmax:
        res *= dc[k-1]**dc[k]
        res %= MOD
        k += 1
    return res


def main():
    N = int(input())
    d = list(map(int,input().split()))
    # N,M = map(int,input().split())
    print(solve(N,d))


if __name__ == '__main__':
  main()


Measured memory_bytes: 24364
#include <bits/stdc++.h>
using namespace std;
#define ll          long long int
#define pb          push_back
#define pll         pair<ll,ll>
#define speed_up    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mod         1000000007
#define inf         1000000000000000000LL
#define vl          vector<ll>
#define F           first
#define S           second
#define ld          long double
#define sz(x)       (ll)x.size()
#define fix(n)      cout<<fixed<<setprecision(n)
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define all(x)      x.begin(),x.end()
#define pi          3.14159265358979323
#define M           998244353


void solve()
{
      ll a,b;
      cin>>a>>b;
      if(a>=13){ cout<<b; return; }
      if(a>=6 && a<=12) { cout<<b/2; return; }
      cout<<0;
}


int main()
{
       speed_up;
       //pre();
       ll T=1;
       //cin>>T;
       while(T--) solve();
	return 0;
}


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

int main() {
  int A,B,K;cin>>A>>B>>K;
  int k=0,i=min(A,B);
  while(true){
    if(A%i==0&&B%i==0)k++;
    if(K==k)break;
    i--;
  }
  cout<<i<<endl;
}

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

int main()
{
    char str[1001];
    char command[8];

    char print[6]   = "print";
    char reverse[8] = "reverse";
    char replace[8] = "replace";

    int q;

    scanf("%s", str);
    scanf("%d", &q);

    int i;
    for (i = 0; i < q; i++) {
        scanf("%s", command);

        if (strcmp(command, print) == 0) {
            int a, b;
            scanf("%d %d", &a, &b);
            char tmp[1001];
            strncpy(tmp, &(str[a]), b - a + 1);
            tmp[b - a + 1] = '\0';
            printf("%s\n", tmp);
        } else if (strcmp(command, reverse) == 0) {
            int a, b;
            scanf("%d %d", &a, &b);
            char tmp1[1001];
            char tmp2[1001];
            strncpy(tmp1, &(str[a]), b - a + 1);
            int n = b - a + 1;
            int i;
            for (i = 0; i < n; i++) {
                tmp2[i] =tmp1[n - 1 - i];
            }
            strncpy(&(str[a]), tmp2, b - a + 1);
        } else if (strcmp(command, replace) == 0) {
            int a, b;
            char tmp[1001];
            scanf("%d %d %s", &a, &b, tmp);
            strncpy(&(str[a]), tmp, b - a + 1);
        }
    }

    return 0;
}



Measured memory_bytes: 2056
import math
import numpy as np
def main(N, a1, a2):
    a1_cum = np.cumsum(a1)
    a2_cum = np.cumsum(a2)

    print(max([a1_cum[i] + a2[i] + (a2_cum[-1] - a2_cum[i]) for i in range(N)]))




if __name__ == "__main__":
    N = int(input())
    a1 = [int(x) for x in input().split()]
    a2 = [int(x) for x in input().split()]
    
    main(N, a1, a2)

def test1(capsys):
    inputs = [4, 8, 2]
    out = 3
    main(*inputs)
    captured = capsys.readouterr()    
    assert captured.out == str(out) + '\n'

def test3(capsys):
    inputs = [0, 5, 1]
    out = 6
    main(*inputs)
    captured = capsys.readouterr()    
    assert captured.out == str(out) + '\n'

def test4(capsys):
    inputs = [9, 9, 2]
    out = 0
    main(*inputs)
    captured = capsys.readouterr()    
    assert captured.out == str(out) + '\n'

def test5(capsys):
    inputs = [1, 1000000000000000000, 3]
    out = 333333333333333333
    main(*inputs)
    captured = capsys.readouterr()    
    assert captured.out == str(out) + '\n'

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

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

    stack<int> l_stack, r_stack;
    int cur;

    int k; cin >> k;
    cur = 0;

    for (int i = 0; i < k; ++i) {
        if (l_stack.empty() && cur == 9) { // 左隣がない
            l_stack.push(1);
            cur = 0;
        } else if (!l_stack.empty() && (l_stack.top() < cur || cur == 9)) { // 繰り上げ
            while (!l_stack.empty() && (l_stack.top() < cur || cur == 9)) {
                r_stack.push(cur);
                cur = l_stack.top();
                l_stack.pop();
            }
        } else {
            cur++;
        }

        if (!r_stack.empty()) {
            bool all9 = (l_stack.empty() && cur == 9);
            cur = all9 ? 1 : cur + 1;
            while (!r_stack.empty()) {
                l_stack.push(cur);
                cur = (l_stack.top() == 0) ? 0 : l_stack.top() - 1;
                r_stack.pop();
            }
            if (all9) l_stack.push(0);
        }
    }

    // build ans string
    string ans;
    while (!l_stack.empty()) {
        ans += to_string(l_stack.top());
        l_stack.pop();
    }
    reverse(ans.begin(), ans.end());
    ans += to_string(cur);

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define eps 1e-10
#define MAXN 100005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef unsigned int u32;
typedef double db;
template<class T>
void read(T &res) {
    res = 0;T f = 1;char c = getchar();
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 +c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;putchar('-');}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
struct node {
    int to,next;
}E[MAXN * 2];
int N,K,head[MAXN],sumE;
int a[MAXN],ans;
int rem[MAXN];
void add(int u,int v) {
    E[++sumE].to = v;
    E[sumE].next = head[u];
    head[u] = sumE;
}
void dfs(int u) {
    for(int i = head[u] ; i ; i = E[i].next) {
	int v = E[i].to;
	dfs(v);
	if(rem[v] == K - 1 && u != 1) {++ans;rem[v] = -1;}
	rem[u] = max(rem[u],rem[v] + 1);
    }
}
void Solve() {
    read(N);read(K);
    for(int i = 1 ; i <= N ; ++i) {
	read(a[i]);
    }
    if(a[1] != 1) ++ans;
    for(int i = 2 ; i <= N ; ++i) {
	add(a[i],i);
    }
    dfs(1);
    out(ans);enter;
}

int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
    return 0;
}


Measured memory_bytes: 6912
import java.util.*; 
import java.io.*;

public class Main {
    static StringTokenizer st;
    static BufferedReader br;  
    static PrintWriter out;
 
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));

        //ArrayList myList = new ArrayList<>();

        int N = nextInt();

        // for(int i = 1; i<=N; i++){
        //     String S = next();
        //     if(!myList.contains(S)){
        //         myList.add(S);
        //     }
        // }
        
        String[] myList = new String[N];

        
        for(int i = 0; i<N; i++){
            String S = next();
            myList[i] = S;
        }

        Arrays.sort(myList);

        int count= 1;
        String Temp = myList[0];
        for(int i = 1; i<N; i++){
            if(!Temp.equals( myList[i])){
                count++;
                Temp = myList[i];
            }
        }

        System.out.println(count);
    }
    
      
    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}

Measured memory_bytes: 62024
#include <stdio.h>
#include <inttypes.h>

int main(void) {
	int r, D;
	int64_t x;
	int i;
	if (scanf("%d%d%" SCNd64, &r, &D, &x) != 3) return 1;
	for (i = 1; i <= 10; i++) {
		x = r * x - D;
		printf("%" PRId64 "\n", x);
	}
	return 0;
}


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

int main() {
    std::string s, t;
    std::cin >> s >> t;
    std::vector<std::deque<int>> c(26), c2(26);
    for (int i = 0; i < t.size(); i++) c[t[i] - 'a'].push_back(i);
    for (auto& q : c) {
        std::set<char> a;
        for (auto i : q) a.insert(s[i]);
        if (a.size() > 1) {
            std::cout << "No" << std::endl;
            return 0;
        }
    }

    for (int i = 0; i < s.size(); i++) c2[s[i] - 'a'].push_back(i);
    for (auto& q : c2) {
        std::set<char> a;
        for (auto i : q) a.insert(t[i]);
        if (a.size() > 1) {
            std::cout << "No" << std::endl;
            return 0;
        }
    }

    std::cout << "Yes" << std::endl;

    return 0;
}

Measured memory_bytes: 2312
N, K, S = map(int, input().split())

ans = []
# if S % 2 == 0:
#     for i in range(K):
#         ans.append(S)
#     for i in range(N-K):
#         ans.append(S+1)
# else:
#     x = S // 2

for i in range(K):
    ans.append(S)

if S != 10 ** 9:
    for i in range(N-K):
        ans.append(S+1)
else:
    for i in range(N-K):
        ans.append(S-1)


ans = [str(i) for i in ans]
print(" ".join(ans))



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

int main() {
  int N;
  cin >> N;
  vector<int> A(N), B(N), C(N);
  for(int i=0; i<N; ++i){
    cin >> A[i];
  }
  for(int i=0; i<N; ++i){
    cin >> B[i];
  }
  for(int i=0; i<N; ++i){
    cin >> C[i];
  }
  sort(A.begin(), A.end());
  sort(B.begin(), B.end());
  sort(C.begin(), C.end());

  long long ans = 0;
  for(int j=0; j<N; ++j) {
    ans += (lower_bound(A.begin(), A.end(), B[j]) - A.begin())
     * (C.end() - upper_bound(C.begin(), C.end(), B[j]));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
#define ll	        long long
#define all(v)      (v).begin() , (v).end()
#define vi          vector <ll>
#define vii         vector <pair<ll,ll>>
#define ii          pair<int,int>
#define lp(i,a,b)	for(int i=a;i<b;i++)
#define pb          push_back
#define F           first
#define S           second
const ll mod=1e9+7,MAX=2e5+7;
void fast();
int main()
{
    fast();
    ll n;
    cin>>n;
    ll res=0;
    res=n*(n+1)/2;
    res-=((n/3)*(n/3+1)/2)*3;
    res-=((n/5)*(n/5+1)/2)*5;
    res+=((n/15)*(n/15+1)/2)*15;
    cout<<res;
}

void fast(){
std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
/*

*/


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

char getGrade(int m, int f,int r) {
		char grade;
		if (m == -1 || f == -1)grade= 'F';
		else if (m + f >= 80)grade= 'A';
		else if (m + f >= 65 && m + f < 80)grade = 'B';
		else if (m + f >= 50 && m + f < 65)grade= 'C';
		else if (m + f >= 30 && m + f < 50) {
			if (r >= 50)grade = 'C';
			else  grade = 'D'; 
		}
		else if (m + f < 30)grade= 'F';

		return grade;
	}
int main(){	
	while (1) {
		int m, f, r;
		cin >> m >> f >> r;
			if (m == -1 && f == -1 && r == -1)break;
			cout << getGrade(m, f, r) << endl;
	}
	return 0;
}


Measured memory_bytes: 3104
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    int t = sc.nextInt();
    int answer = x - t;
    if (answer < 0) {
      answer = 0;
    }
    System.out.println(answer);
  }
}


Measured memory_bytes: 21844
#include <iostream>
#include <cstdio>
#include <malloc.h>
#include <string>
using namespace std;
int main()
{
	int n;
	int a[14];
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", a + i);
	int cnt = 1;
	for (int i = 0; i < n; i++)
		if (a[i] % 2 == 0)
			cnt *= 2;
	int ans = 1;
	for (int i = 0; i < n; i++)
		ans *= 3;
	ans -= cnt;
	printf("%d\n", ans);
	//system("pause");

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main(){
    int N,M;
    cin >> N >> M;
    if(N==M){
        cout << "Yes";
    }
    else{
        cout << "No";
    }
    return 0;
}


Measured memory_bytes: 256
A, B, C, X, Y = map(int, input().split())
ans = 0

if 2 * C <= A + B:
    tmp = min(X, Y)
    ans += tmp * 2 * C
    X -= tmp
    Y -= tmp
    if X == 0:
        if 2*C <= B:
            ans += Y * 2 * C
        else:
            ans += Y * B
    if Y == 0:
        if 2*C <= A:
            ans += X * 2 * C
        else:
            ans += X * A
else:
    if 2 * C <= B:
        ans += 2 * C * Y
        X -= Y
        if X >= 1:
            ans += min(X*A, X*2*C)
    elif 2 * C <= A:
        ans += 2 * C * X
        Y -= X
        if Y >= 1:
            ans += min(Y*B, Y*2*C)
    else:
        ans += A*X + B*Y
print(ans)


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
template <class T> void corner(bool flg, T hoge) {
    if (flg) {
        cout << hoge << endl;
        exit(0);
    }
}
#define all(v) v.begin(), v.end()
#define inputv(v, n)                                                           \
    vl v;                                                                      \
    rep(i, n) {                                                                \
        ll x;                                                                  \
        cin >> x;                                                              \
        v.push_back(x);                                                        \
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
struct LazySegmentTree {
private:
	ll n;
	vector<ll> node, lazy;

public:
	LazySegmentTree(vector<ll> v) {
		ll sz = (ll)v.size();
		n = 1; while (n < sz) n *= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1, 0);

		for (ll i = 0; i < sz; i++) node[i + n - 1] = v[i];
		for (ll i = n - 2; i >= 0; i--) node[i] = node[i * 2 + 1] + node[i * 2 + 2];
	}

	// k 番目のノードについて遅延評価を行う
	void eval(ll k, ll l, ll r) {

		// 遅延配列が空でない場合、自ノード及び子ノードへの
		// 値の伝播が起こる
		if (lazy[k] != 0) {
			node[k] += lazy[k];

			// 最下段かどうかのチェックをしよう
			// 子ノードは親ノードの 1/2 の範囲であるため、
			// 伝播させるときは半分にする
			if (r - l > 1) {
				lazy[2 * k + 1] += lazy[k] / 2;
				lazy[2 * k + 2] += lazy[k] / 2;
			}

			// 伝播が終わったので、自ノードの遅延配列を空にする
			lazy[k] = 0;
		}
	}

	void add(ll a, ll b, ll x, ll k = 0, ll l = 0, ll r = -1) {
		if (r < 0) r = n;

		// k 番目のノードに対して遅延評価を行う
		eval(k, l, r);

		// 範囲外なら何もしない
		if (b <= l || r <= a) return;

		// 完全に被覆しているならば、遅延配列に値を入れた後に評価
		if (a <= l && r <= b) {
			lazy[k] += (r - l) * x;
			eval(k, l, r);
		}

		// そうでないならば、子ノードの値を再帰的に計算して、
		// 計算済みの値をもらってくる
		else {
			add(a, b, x, 2 * k + 1, l, (l + r) / 2);
			add(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = node[2 * k + 1] + node[2 * k + 2];
		}
	}

	ll getsum(ll a, ll b, ll k = 0, ll l = 0, ll r = -1) {
		if (r < 0) r = n;
		if (b <= l || r <= a) return 0;

		// 関数が呼び出されたら評価！
		eval(k, l, r);
		if (a <= l && r <= b) return node[k];
		ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
		ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
		return vl + vr;
	}
};
int main() {
    cin >> n >> d >> a;
    vector<PP> P;
    vl A, B;
    rep(i, n) {
		cin >> x >> y;
		P.push_back({ x,(y - 1) / a + 1 });
    }
	sort(all(P));

	rep(i, n) {
		A.push_back(P[i].first);
		B.push_back(P[i].second);
	}

	LazySegmentTree SEG(B);

	vl C;
	rep(i, n) {
		C.push_back(upper_bound(all(A), A[i] + d * 2)-A.begin());
	}

	rep(i, n) {
		x= SEG.getsum(i, i + 1);
		if (x > 0) {
			SEG.add(i, C[i], -x);
			ans += x;
		}
	}

	cout << ans << endl;
}

Measured memory_bytes: 20204
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int main(void)
{
    cin.sync_with_stdio(false);
    int N;
    cin >> N;

    vector<tuple<ll,ll,ll>> info;
    tuple<ll, ll, ll> non_zero;
    REP(n, N) {
        ll x, y, h;
        cin >> x >> y >> h;
        info.pb(mt(x, y, h));
        if (h != 0) {
            non_zero = mt(x, y, h);
        }
    }
    for(ll y_center = 0; y_center < 101; ++y_center) {
        for(ll x_center = 0; x_center < 101; ++x_center) {

            ll x, y, h;
            tie(x, y, h) = non_zero;
            ll h_expect = abs(y_center - y) + abs(x_center - x) + h;

            bool ok = true;
            REP(i, SIZE(info)) {
                tie(x, y, h) = info[i];
                // !!! maxをとるのを忘れてWA
                auto should_h = max(0LL, h_expect - (abs(y_center - y) + abs(x_center - x)));
                if (should_h != h) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                cout << x_center << " " << y_center << " " << h_expect << endl;
                return 0;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=55;
const LL inf=1e18;
char s[N][22];
int c[N],l[N],n;
bool vis[N][22][2];
LL f[N][22][2],ans=inf;
LL dp(int x,int y,int k){
	if(y==l[x])return 0;
	LL &ans=f[x][y][k];
	if(vis[x][y][k])return ans;
	vis[x][y][k]=1,ans=inf;bool fl=1;
	if(k)for(int L=0,R=l[x]-y-1;L<R;L++,R--){if(s[x][L]!=s[x][R]){fl=0;break;}}
	else for(int L=y,R=l[x]-1;L<R;L++,R--)if(s[x][L]!=s[x][R]){fl=0;break;}
	if(fl)return ans=0;
	for(int i=0;i<n;i++){
		fl=1;
		if(k)for(int R=l[x]-y-1,L=0;L<l[i]&&R>=0;R--,L++){if(s[x][R]!=s[i][L]){fl=0;break;}}
		else for(int R=l[i]-1,L=y;L<l[x]&&R>=0;R--,L++)if(s[x][L]!=s[i][R]){fl=0;break;}
		if(fl){
			if(y+l[i]<=l[x])ans=min(ans,c[i]+dp(x,y+l[i],k));
			else ans=min(ans,c[i]+dp(i,l[x]-y,k^1));
		}
	}
	return ans;
}
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%s%d",s[i],c+i),l[i]=strlen(s[i]);
	for(int i=0;i<n;i++)ans=min(ans,c[i]+dp(i,0,0));
	printf("%lld",ans==inf?-1:ans);
	return 0;
}

Measured memory_bytes: 3800
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
    int n;
    cin>>n;
	if(n==7 || n==5 || n==3){
		cout<<"YES\n";
	} 
	else{
		cout<<"NO\n";
	}
    return 0;
}


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

using namespace std;
#define ll long long
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> TUP;
#define a first
#define b second
#define bg begin()
#define ed end()
#define sz size()
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define mp(x,y) make_pair(x,y)
const ll MOD=1000000007;

int main(){
	ll x; cin>>x;
	ll tmp;
	if(x%11>=1 && x%11<=6) tmp=1;
	else tmp=2;
	cout<<((x-1)/11)*2+tmp;
}

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

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

  // ここにプログラムを追記
  int s = 0;
  for ( int i = 0; i < N; i++ ) {
    int l, r;
    cin >> l >> r;
    s += r - l + 1;
  }
  
  cout << s << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.util.stream.*;

public class Main{
	public static void main(String[] $){
		Scanner s=new Scanner(System.in);
		int n=s.nextInt();
		long x=s.nextInt();
		long[][] a=new long[n][n];
		Arrays.setAll(a[0],i->s.nextLong());
		for(int j=0;j<n;++j){
			for(int i=1;i<n;++i){
				a[i][j]=Math.min(a[i-1][j],a[0][(j-i+n)%n]);
			}
		}
		System.out.println(IntStream.range(0,n)
				.mapToLong(i->i*x+Arrays.stream(a[i]).sum())
				.min().getAsLong());
	}
}


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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
#define rep(pos, len) for(int pos=0;pos<len;pos++)
#define repp(pos, len) for(int pos=1;pos<=len;pos++)
 
#define INF 987654321
#define IINF 2987654321987654321
#define MOD 1000000007


const int MAXN = 2e5 + 50;
int n;
ll a[MAXN], s[MAXN];
void readInput() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	s[0] = 0;
	for(int i = 1; i <= n; i++)
		s[i] = s[i-1] + a[i];
}


inline ll f(int i, int j, int k) {
	if(0 > i || i > j || j > k || k > n)
		return IINF;
	ll P = s[i], Q = s[j] - s[i], R = s[k] - s[j], S = s[n] - s[k];
	if(!(P && Q && R && S)) 
		return IINF;
	return max({P, Q, R, S}) - min({P, Q, R, S});
}


void solve() {
	ll mn = IINF;
	for(int x = 2; x <= n-2; x++) {
		int p = lower_bound(s+1, s+x+1, s[x]/2) - s;
		int q = lower_bound(s+x+1, s+n+1, (s[n] + s[x]) / 2) - s;
		for(int i : {p-1, p})
			for(int k : {q-1, q})
				mn = min(mn, f(i, x, k));
	}
	printf("%lld\n", mn);
}


int main() {
	readInput();
	solve();
}

Measured memory_bytes: 3328
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=1e18;
using P=pair<int,int>;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  int n,x[55]={},y[55]={},cnt=0;
  cin >> n;
  map<pair<int,int>,int> mp;
  for(int i=0; i<n; i++) {
    cin >> x[i] >> y[i];
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<n; j++) {
      if(i!=j) {
        mp[make_pair(x[i]-x[j],y[i]-y[j])]++;
        cnt=max(cnt,mp[make_pair(x[i]-x[j],y[i]-y[j])]);
      }
    }
  }
  cout << n-cnt << endl;
}

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

using ll = int64_t;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
	os << "(" << p.first << "," << p.second << ")";
	return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
	os << "{";
	rep(i, (int)v.size()) {
		if (i)
			os << ",";
		os << v[i];
	}
	os << "}";
	return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
	for (auto val : array)
		std::cout << val << ", ";
	std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

	int n; std::cin >> n;
	vi d(n); rep(i, n) std::cin >> d[i];
	int ans = 0;
	rep(i, n) rep(j, n) {
		if (i == j) continue;
		ans += d[i] * d[j];
	}
	std::cout << ans / 2 << "\n";
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>

int a,b,c,x,y;

int ans;

int calc(int k)
{
	return std::min(k*(a+b),k*c*2);
}

int main()
{
	scanf("%d%d%d%d%d",&a,&b,&c,&x,&y);

	int tmp=calc(std::max(x,y));

	ans=0,ans+=calc(std::min(x,y));

	int k=std::min(x,y);
	x-=k,y-=k;

	ans+=x*a+y*b;

	printf("%d\n",std::min(ans,tmp));

	return 0;
}


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


#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()


using namespace std;
using namespace __gnu_pbds;

template<class T> using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
using ll  = long long;

using point = complex<double>;


void err(istream_iterator<string> it) {cerr << endl;}
template<typename T, typename... Args>void err(istream_iterator<string> it, T a, Args... args) {cerr << *it << " = " << a << endl;err(++it, args...);}


const double EPS = 1e-8;
const long long mod = 1e9 + 7;

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

const int N = 5e3 + 5;
const long long INF = 1e18;

int add(int a, int b){
        return (a + b) % mod;
}
int mul(int a, int b){
    return  (1ll * a * b) % mod;
}
int fp(int b, int p){
        int ret = 1;
        while(p){
            if(p & 1)
                    ret = mul(ret,b);
            b = mul(b,b);
            p >>= 1;
        }
        return ret;
}

int f[N];
int inv[N];
void init(){
    f[0] = 1;
    inv[0] = 1;
    for(int i = 1;i <N; ++i){
        f[i] = mul(i,f[i - 1]);
        inv[i] = fp(f[i],mod - 2);
    }
}
int nCr(int n , int r){
    return mul(f[n],mul(inv[n-r],inv[r]));

}
/*
int dp[2005][2005][4];
int solve(int blue, int red,int lstBlue){

        if(blue < 0 || red < 0)
                return 0;
        if(blue == 0 and red == 0)
                return 1;
        int &ret = dp[blue][red][lstBlue];
        if(~ret)
            return ret;
        ret = 0;
        if(lstBlue == 2){ // didn't put any ball yet
            ret = add(ret, solve(blue - 1,red,1));
            ret = add(ret, solve(blue,red - 1,0));
        }else if(lstBlue == 1){ // last ball was blue
            ret = add(ret,solve(blue,red - 1,0));
        }else{ // last ball was red
            ret = add(ret, solve(blue , red - 1,0));
            ret = add(ret, solve(blue - 1,red,1));
        }
        return ret;
}*/
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int n , k;
    cin >> n >> k;
    for(int i = 1; i <= k; ++i){
        if(n - k + 1 >= i and k >= i)
            cout << mul(nCr(n-k+1,i),nCr(k - 1,i - 1)) << '\n';
        else cout << 0 << '\n';
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define File(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout)

using namespace std;

typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;

template <typename T>
inline T gi()
{
	T f = 1, x = 0; char c = getchar();
	while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return f * x;
}

const int INF = 0x3f3f3f3f, N = 300003, M = N << 2;

int n, m;
int tr[N];
struct Node {int l, r, len;} x[N];
int ans[N];

inline int lowbit(int i) {return i & (-i);}

inline void add(int x, int val)
{
	for (int i = x; i <= m; i += lowbit(i)) tr[i] += val;
}

inline int getans(int x)
{
	if (x == 0) return 0;
	int sum = 0;
	for (int i = x; i; i -= lowbit(i)) sum += tr[i];
	return sum;
}

inline bool cmp(Node x, Node y) {return x.len < y.len;}

int main()
{
	//File("");
	n = gi <int> (), m = gi <int> ();
	for (int i = 1; i <= n; i+=1)
		x[i].l = gi <int> (), x[i].r = gi <int> (), x[i].len = x[i].r - x[i].l + 1, add(x[i].l, 1), add(x[i].r + 1, -1);
	sort(x + 1, x + 1 + n, cmp);
	int now = n;
	for (int i = m; i >= 1; i-=1)
	{
		while (now >= 1 && x[now].len >= i)
			add(x[now].l, -1), add(x[now].r + 1, 1), --now;
		ans[i] = n - now;
		for (int j = i; j <= m; j+=i) ans[i] += getans(j);
	}
	for (int i = 1; i <= m; i+=1) printf("%d\n", ans[i]);
	return 0;
}


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

bool check_next (int i, int j, vector<string> s) {
    bool exist_next = false;
    for (int x=-1; x<=1; x++) {
        for (int y=-1; y<=1; y++) {
            if (i+x < 0 || j+y < 0) continue;
            if (i+x >= s.size() || j+y >= s[i].size()) continue;
            if (x == 0 && y == 0) continue;
            if (x != 0 && y != 0) continue;
            if (s[i+x][j+y] == '#') exist_next = true;
        }
    }
    return exist_next;
}

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    for (int i=0; i<h; i++) cin >> s[i];
    bool ans = true;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (s[i][j] == '.') continue;
            if (ans) ans = check_next(i, j, s);
            else continue;
        }
    }
    if (ans) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*;
import java.util.function.ToDoubleFunction;


public class Main {
    private static final String ex = "9999999999";
//    private static final String ex = "125";

    public static void main(String[] args) {
        solve(new Scanner(System.in));
//        solve(new Scanner(ex));
    }

    private static void solve(Scanner scanner) {
        String S = scanner.nextLine();

        long num[][] = new long[S.length()][S.length()];
        for (int i = 0; i < S.length(); i ++) {
            for (int j = i; j < S.length(); j ++) {
                num[i][j] = Long.parseLong(S.substring(i, j + 1));
            }
        }

        long sum = 0;
        for (int i = 0; i < S.length(); i ++) {
            for (int j = i; j < S.length(); j ++) {
                long shift;
                if (i == 0 && j == S.length() - 1) {
                    shift = 0;
                } else if (i == 0 || j == S.length() - 1) {
                    shift = S.length() - 1 - (j - i + 1);
                } else {
                    shift = S.length() - 1 - (j - i + 2);
                }

                if (shift < 0) throw new RuntimeException();

                long numPattern = 1 << shift;
                sum += num[i][j] * numPattern;
            }
        }

        System.out.println(sum);
    }
}


Measured memory_bytes: 21844
#include <stdio.h>
int main() {
	int sx, sy, tx, ty;
	scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
	tx = tx - sx; ty = ty - sy;
	for (int i = 0; i < tx; i++)
		putchar('R');
	for (int i = 0; i < ty; i++)
		putchar('U');
	for (int i = 0; i < tx; i++)
		putchar('L');
	for (int i = 0; i < ty + 1; i++)
		putchar('D');
	for (int i = 0; i < tx + 1; i++)
		putchar('R');
	for (int i = 0; i < ty + 1; i++)
		putchar('U');
	putchar('L');
	putchar('U');
	for (int i = 0; i < tx + 1; i++)
		putchar('L');
	for (int i = 0; i < ty + 1; i++)
		putchar('D');
	putchar('R');
	return 0;
}


Measured memory_bytes: 128
import sys
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
root=[-1]*n
def r(x):
    if root[x]<0:
        return x
    else:
        root[x]=r(root[x])
        return root[x]
def unite(x,y):
    x=r(x)
    y=r(y)
    if x==y:
        return
    root[x]+=root[y]
    root[y]=x
def size(x):
    x=r(x)
    return -root[x]
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    unite(x,y)
ans=0
for i in range(n):
    ans=max(ans,size(i))
print(ans)





Measured memory_bytes: 96704
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//infinity
#define INTINF 2000000000
#define LONGINF 2000000000

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

	int one = (n - m) * 100 + m * 1900;
	int exp = one * pow(2, m);
	cout << exp << endl;
	return 0;
}


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

int main() {
    int N, T, A;
    cin >> N;
    cin >> T >> A;
    int H[N];
    for (int i=0; i<N; ++i) cin >> H[i];

    int ans = 0;
    float mint = 1000000000.0;
    for (int i=0; i<N; ++i) {
        float t = abs(A - (T - H[i]*0.006));
        if (t < mint) {
            mint = t;
            ans = i+1;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 888