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


class Program {

	static long mod = 1000000007;
	//static long mod =998244353;
	static int[] ans;
	static void Main(string[] args) {

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

		//int n = int.Parse(Console.ReadLine());
		//int val = int.Parse(Console.ReadLine());
		//int[] vals = parseAry(Console.ReadLine().Split(cs));
		//string str = Console.ReadLine();
		//string[] strs = Console.ReadLine().Split(cs);

		//string res = "";
		int res = 0;



		int[] vals = parseAry(Console.ReadLine().Split(cs));
		int n = vals[0];
		int k = vals[1];
		vals = parseAry(Console.ReadLine().Split(cs));

		for ( int i = 0; i < n; i++ ) {
			if ( vals[i] >= k ) { res++; }
		}


		
				Console.WriteLine(res);

		return;

	}



	//	int配列をスペース区切りの文字列に変換
	static string stringBuilderArrayInt(int[] a) {
		StringBuilder sb = new StringBuilder();

		for ( int i = 0; i < a.Length; i++ ) {
			if ( a[i] == 1 ) { sb.Append(i + " "); }
		}
		if ( sb.Length > 1 ) {
			sb = sb.Remove(sb.Length - 1, 1);
		}
		return sb.ToString(); ;
	}


	//	文字列strをindex番目からdで上書き
	static string strOverWrite(string str, int i, string s) {
		return str.Remove(i, s.Length).Insert(i, s);
	}

	//　String[]  ----->  int[]
	static int[] parseAry(string[] str) {
		int[] nums = new int[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = int.Parse(str[i]); }
		return nums;
	}
	//　String[]  ----->  long[]
	static long[] parseAryL(string[] str) {
		long[] nums = new long[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { nums[i] = long.Parse(str[i]); }
		return nums;
	}

	//文字列を1文字ずつString[]に入れる
	static string[] strAry(String str) {
		string[] re = new string[str.Length];
		for ( int i = 0; i < str.Length; i++ ) { re[i] = str[i].ToString(); }
		return re;
	}



}

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

// typedef
// -----------------------------------------------------------------------------
typedef long long ll;
typedef long double ld;

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

// constant
// -----------------------------------------------------------------------------
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double EPS = 1e-9;
const double PI = acos(-1.0);

// debug
// -----------------------------------------------------------------------------
#define DUMP(x)  cerr << #x << " = " << (x) << endl


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(15);
    ll A, Bi, Bd; scanf("%lld %lld.%lld", &A, &Bi, &Bd);

    cout << A * (Bi * 100 + Bd) / 100 << "\n";
}


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

bool isSubstr(const int n, const string& s, const string& t, int i) {
  for (int is = i, it = 0; is < n; ++is, ++it) {
    if (s[is] != t[it])
      return false;
  }
  return true;
}

int Solve(const int n, const string& s, const string& t) {
  for (int i = 0; i < n; ++i) {
    if (isSubstr(n, s, t, i))
      return i + n;
  }
  return 2 * n;
}

int main() {
  int n;
  string s, t;
  cin >> n >> s >> t;
  cout << Solve(n, s, t) << "\n";
  return 0;
}


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

#define REP(i,n) for(int i=0;i<(n);i++)
#define REAP(i,a,n) for(int i=(a);i<(n);i++)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define fr first
#define sc second
#define pb push_back
#define All(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int res=0;
    int n;
    char c;
    cin >> res;
    while(1){
        cin >> c;
        if(c=='=')break;
        cin >> n;
        if(c=='+')res+=n;
        else if(c=='-')res-=n;
        else if(c=='*')res*=n;
        else if(c=='/')res/=n;
    }
    cout <<res << endl;
}



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

using ll = long long;
using ull = unsigned long long;
using st = string;
using db = double;
using vll = vector<long long>;
using vvll = vector<vll>;
using vchar = vector<char>;
ll mod = 1000000007;


int main(){
    st s;
    cin >> s;
    ll n = s.size();
    ll ans = 0;
    for(ll i = 0; i < (n - 1) / 2; i++){
        if(s.at(i) != s.at(n - i - 1)) ans++;
    }
    for(ll i = 0; i < (n - 1) / 2 / 2; i++){
        if(s.at(i) != s.at((n - 1) / 2 - i - 1)) ans++;
    }
    cout << (ans ? "No" : "Yes") << endl;
}

Measured memory_bytes: 256
N = gets.to_i
X, Y = N.times.map{gets.split.map(&:to_i)}.transpose

def route(i, j)
  Math.sqrt((X[i] - X[j]) ** 2 + (Y[i] - Y[j]) ** 2)
end

sum = 0
N.times do |i|
  c = Array.new(N){|i| i}
  c.delete(i)
  c.each do |other|
    sum += route(i, other)
  end
end

puts sum / N

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

int main()
{
    ll N, M;
    cin >> N >> M;
    vector<ll> pena(N,0);
    vector<ll> ok(N,0);
    ll res1=0;
    ll res2=0;
    for (int i = 0; i < M; i++)
    {
        ll p;
        string status;
        cin >> p >> status;--p;
        if(status=="AC"){
            if(!ok[p]){
                ++res1;
                res2+=pena[p];
                ok[p]=true;
            }
        }
        else pena[p]++;
    }
    cout<<res1<<" "<<res2;
    return 0;
}

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

int main(){
  int H,W;
  char a[1000][1000];
  cin>>H>>W;
  for (int i(0);i<H;i++){
    for (int j(0);j<W;j++){
      cin>>a[i][j];
    }
  }
  int cnt[1000][1000]={0};
  cnt[0][0]=1;
  for (int i(0);i<H;i++){
    for (int j(0);j<W;j++){
      if (i==0&&j==0) continue;
      if (j==0){
        if (a[i-1][j] != '#'){
          cnt[i][j] = cnt[i-1][j];
        }
      }else if(i==0){
        if (a[i][j-1] != '#'){
          cnt[i][j] = cnt[i][j-1];
        }
      }else{
        if (a[i-1][j] != '#'){
          cnt[i][j] = cnt[i-1][j];
        }
        if (a[i][j-1] != '#'){
          cnt[i][j] += cnt[i][j-1];
        }
      }
      cnt[i][j]%=mod;
    }
  }
  cout << cnt[H-1][W-1] << endl;
  for (int i(0);i<H;i++){
    for (int j(0);j<W;j++){
      //cout << cnt[i][j] << " ";
    }
    //cout << endl;
  }
  return 0;
}



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

#define PI 3.141592

int main() {
  double l, ang;
  double nowang = PI/2;
  double x = 0, y = 0;
  while(true) {
    scanf("%lf,%lf", &l,&ang);
    if (l+ang==0) break;
    x += cos(nowang) * l;
    y += sin(nowang) * l;
    nowang -= ang * PI / 180;
  }
  printf("%d\n%d\n", (int)x,(int)y);
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
const ll Mod=1000000007;
const ll INF=999999999999999999;
const ll NN=(ll)(1e6+5);
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
vector <ll> sieve(NN);
void build()
{
    ll i,j;
    for(i=1;i<NN;i++)
      for(j=i;j<NN;j+=i)
       sieve[j]++;
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {
       ll n,i,j,ans=0;
       cin>>n;
       build();
       map <ll,ll> mp;
       for(i=1;i*i<NN;i++)
        mp[i*i]++;
       for(i=1;i<n;i++)
       {
           ll x=n-i;
           //cout<<sieve[x]<<" "<<x<<"\n";
           ans+=sieve[x];
       } 
       cout<<ans;
   }
}

Measured memory_bytes: 11000
/**********
Author: WLBKR5
Problem: ABC176 E
Date: 2020/08/22
**********/
#include<bits/stdc++.h>
using namespace std;
inline int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
const int N=3e5+01;
int r[N],c[N];
int main(){
    int n=getint(),m=getint(),k=getint();
    set<pair<int,int> >s;
    for(int i=0;i<k;i++){
        int x=getint(),y=getint();
        r[x]++;
        c[y]++;
        s.insert(make_pair(x,y));
    }
    int rmax=0,cmax=0;
    vector<int>rm,cm;
    for(int i=1;i<=n;i++){
        if(r[i]>r[rmax])rmax=i,rm.clear();
        if(r[i]==r[rmax])rm.push_back(i);
    }
    for(int i=1;i<=m;i++){
        if(c[i]>c[cmax])cmax=i,cm.clear();
        if(c[i]==c[cmax])cm.push_back(i);
    }
    bool b=0;
    for(auto i:rm){
        for(auto j:cm){
            if(s.count(make_pair(i,j))==0){
                b=1;
                break;
            }
        }
        if(b)break;
    }
    cout<<r[rmax]+c[cmax]-1+b;
    return 0;
}


Measured memory_bytes: 23708
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.next();
		String s2 = sc.next();
		String s3 = sc.next();

		String[] str1 = s1.split("");
		String[] str2 = s2.split("");
		String[] str3 = s3.split("");

		String small = "abcdefghijklmnopqrstuvwxyz";
		String[] small1 = small.split("");
		String large = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
		String[] large1 = large.split("");

		for(int i=0; i<small1.length; i++){
			if(str1[0].equals(small1[i])){
				System.out.print(large1[i]);
				break;
			}
		}

		for(int i=0; i<small1.length; i++){
			if(str2[0].equals(small1[i])){
				System.out.print(large1[i]);
				break;
			}
		}

		for(int i=0; i<small1.length; i++){
			if(str3[0].equals(small1[i])){
				System.out.print(large1[i]);
				break;
			}
		}

	}

}


Measured memory_bytes: 23252
//#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
int main(){
  ll a,b,c,d;cin>>a>>b>>c>>d;
  if(d==1)cout<<1<<endl;
  else cout<<0<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repf(i, a, b) for(ll i = (a); i < (b) ; i++ )
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807


int main()
{
ll n;
cin >> n;
pair<ll, ll> t[n];
rep(i, n){
    cin >> t[i].second>> t[i].first;
}
ll tim=0,now=0;
sort(t,t+n);
rep(i,n){
    tim=t[i].first;
    now+=t[i].second;
    if(tim<now){
        cout << "No" << endl;
        return 0;
    }
}

cout << "Yes" << endl;
return 0;
}

Measured memory_bytes: 3328
/*
for (int i = 0; i < N; ++i){}

// 各桁の和を計算する関数
int findSumOfDigits(int n) {
  int sum = 0;
  while (n > 0) { // n が 0 になるまで
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

sort(a, a + N, greater<int>());  // a[0:N] を大きい順にソート

int num[110] = {0};  // バケット
for (int i = 0; i < N; ++i) {
    num[d[i]]++;  // d[i] が 1 個増える
}

map<string, int> mp; // 連想配列 map<キー型, 値型> オブジェクト名
for (int i = 0; i < N; ++i) {
    auto itr = mp.find(s[i]);        // s[i] が設定されているか？
    if(itr != mp.end() ) {
         mp[s[i]] += 1;
    }
    else {
         mp[s[i]] += 1 ;
    }
}
stack<int> s;	//intをデータとするスタックを用意
s.push(1);		//{} -> {1}
printf("%d\n", s.top());	// 3
s.pop();

queue<int> que;	//intをデータとするキューを用意
que.push(1);		//{} -> {1}
printf("%d\n", que.front());	// 1
que.pop();
*/
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <bitset>

using namespace std;

// #define for(i,a,b) for (int i=(a);i<(b);++i)
typedef long long ll;
typedef pair<int,int> point;
#define rep(i,n) for(i,0,n)

int comb(int n, int r){
	int ans = 1;
	for (int i = 0; i < r; ++i){
		ans *= n - i;
		ans /= r - i;
	}
	return ans;
}

int main() {
	// 入力
	int n;
	cin >> n;
	int a[n];
	for (int i = 0; i < n; ++i) cin >> a[i];
 
	// 解法
	sort(a, a+n, greater<int>());
	int ans_n = a[0];
	int ans_r = a[1];
	// int ans_comb = comb(ans_n, ans_r);
	for (int i = 1; i < n; ++i){
		if (abs(ans_n/2-ans_r)>abs(ans_n/2-a[i])){
			ans_r = a[i];
		}
	}
		
	
	//出力
	// cout << sum << endl;
	printf("%lld %lld\n", ans_n, ans_r);
}
 


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

typedef long long ll;
typedef long double ld;

int score[100005];

int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;

    int n, k, q;
    cin >> n >> k >> q;
    for(int i=1; i<=q; i++){
        int x;
        cin >> x;
        score[x]++;
    }
    for(int i=1; i<=n; i++){
        if(k-(q-score[i]) > 0){
            cout << "Yes\n";
        }
        else cout << "No\n";
    }
    return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
#include<cstring>
#include<math.h>
#include<map>
#include<bitset>
#include<iomanip>
#include<queue>
#include<functional>
#include<stack>
#include<tuple>
#include<cassert>
using namespace std;

#define rep(i, n) for (long long i = 0; i < (long long)(n); ++i)
using ll = long long;
using P = pair<long long, long long>;
using MATRIX = vector< vector<ll> >;

const long long MAX = 510000;
const long long MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (long long i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(long long n, long long k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

long long N, K;
long long M;

int main() {
  COMinit();
  cin >> N >> K;
  M = N - K;
  long long sum[100000];
  sum[0] = 0;
  for(long long i = 1; i <= K; i++) {
    long long temp = COM(M + i, M) * COM(K-1, i-1);
    // cout << "bef " << temp << endl;
    temp %= MOD;
    for(int j = 1; j <= i-1; j++) {
      temp -= (sum[j] * COM(K-j, i-j)) % MOD;
      if(temp < 0) temp += MOD;
    }
    sum[i] = temp;
    sum[i] %= MOD;
    cout << temp << endl;
  }
  return 0;
}

Measured memory_bytes: 15580
#include<bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main(){
    int a,b;
    cin >> a >> b;
    bool ok = false;
    if(a<10 && b<10) ok = true;
    cout << (ok ? a*b : -1) << endl; 
    return 0;
}

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

int main() {
    int N, L; cin >> N >> L;
    vector<int> a(N + 1);
    for (int i = 1; i <= N; i++) cin >> a[i];

    for (int i = 1; i <= N - 1; i++) {
        if (a[i] + a[i + 1] >= L) {
            puts("Possible");
            for (int j = 1; j < i; j++) cout << j << endl;
            for (int j = N - 1; j >= i; j--) cout << j << endl;
            return 0;
        }
    }
    puts("Impossible");
    return 0;
}

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

using namespace std;

int main(void) {
  int d, n;
  cin >> d >> n;

  int tmp;
  if(d == 0) {
    tmp = 1;
  }
  else if(d == 1){
    tmp = 100;
  }
  else {
    tmp = 10000;
  }

  if(n == 100) {
    n++;
  }

  cout << tmp * n << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python
n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
DP = [n for i in range(n + 1)]
DP[0] = 0
for cost in c:
	for i in range(cost, n + 1):
		DP[i] = min(DP[i], DP[i - cost] + 1)
print(DP[n])



Measured memory_bytes: 7636
// start: 21:57
// AC: 00:12
#include <cstdio>
#include <climits>
#include <iostream>
#include <vector>
#include <queue>

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

using namespace std;

typedef pair<int, int> xy;

// 左足のときに置ける右足
int mx[] = {1, 1, 2, 1, 2, 3, 1, 2, 1},
    my[] = {2, 1, 1, 0, 0, 0, -1, -1, -2};

void dump(vector< vector<char> > &f, int x = -1, int y = -1, int l = -1) {
    REP(i, f.size()) {
        REP(j, f[i].size()) {
            if ( i == y && j == x ) {
                if ( l == 0 )
                    cout << "R";
                else
                    cout << "L";
            }
            else
                cout << f[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int w, h;

    while(cin >> w >> h, w||h) {
        int closed[h][w][2];
        vector< queue<xy> > foot(2);   // 0:右 1:左
        queue<int> cost, leg;
        vector< vector<char> > f(h);
        vector< xy > start;

        REP(i, h) REP(j, w) REP(k, 2) closed[i][j][k] = 0;

        REP(i, h) {
            REP(j, w) {
                char tmp;
                cin >> tmp;
                f[i].push_back(tmp);
                if ( f[i][j] == 'S' ) {
                    start.push_back( make_pair(j, i) );
                }
            }
        }

        // スタート地点＋左右を初期値としてpush
        REP(i, start.size()) {
            int l = 0;
            leg.push(l);
            foot[l].push( make_pair(start[i].first, start[i].second) );
            cost.push(0);

            l = 1;
            leg.push(l);
            foot[l].push( make_pair(start[i].first, start[i].second) );
            cost.push(0);
        }

        int min = INT_MAX;
        while(!cost.empty()) {
            int c = cost.front(); cost.pop();
            int l = leg.front(); leg.pop();
            xy ft = foot[l].front(); foot[l].pop();
            int x = ft.first, y = ft.second;

            // printf("f:%d, x:%d, y:%d, xy:%c\n", l, x, y, f[y][x]);
            // dump(f, x, y, l);
            if ( f[y][x] == 'T' && c < min ) {
                min = c;
                continue;
            }

            REP(i, 9) {
                int dir = l == 0 ? -1: 1,
                    nx = x + mx[i] * dir,
                    ny = y + my[i],
                    nl = !l;

                if ( !(0 <= nx && nx < w && 0 <= ny && ny < h) ) continue;
                if ( f[ny][nx] == 'X' || f[ny][nx] == 'S' ) continue;   // バグ出るかも

                int nc;
                if ( ((int)f[ny][nx] - 48) > 9 )
                    nc = c + 1;
                else
                    nc = c + ((int)f[ny][nx] - 48);

                if ( closed[ny][nx][nl] != 0 && closed[ny][nx][nl] < nc ) continue;

                cost.push(nc);
                leg.push(nl);   // 逆足
                foot[nl].push( make_pair(nx, ny) );
                closed[ny][nx][nl] = nc;

            }
        }

        if ( min == INT_MAX )
            cout << -1 << endl;
        else
            cout << (min-1) << endl;
    }
    return 0;
}

Measured memory_bytes: 1824
using System;
using System.Linq;

namespace V0025{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            while(true){
                var an = sr.Next<int>(4);
                var bn = sr.Next<int>(4);
                if(an[0] == int.MinValue) break;

                var hit = an.Where((x, i) => x == bn[i]).Count();
                var blow = an.Count(x => bn.Contains(x)) - hit;
                Console.WriteLine("{0} {1}", hit, blow);
            }
            //---------------------------------
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = Console.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }
    }
}

Measured memory_bytes: 10080
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15


def main():
    h, k = getlist()
    mag = []
    for i in range(k):
        mag.append((getlist()))
    dp = [INF for i in range(h+1)]
    dp[0] = 0
    for i in range(h):
        cur = dp[i]
        for ma in mag:
            a, b = ma
            if i + a >= h:
                tgt = h
            else:
                tgt = i + a
            if dp[tgt] > cur + b:
                dp[tgt] = cur + b
    print(dp[-1])
    # mag.sort()


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

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

using namespace std;

int solve(string str) {
    int res = 0;
    for (int i = 0; i <(int) str.length(); i++) {
        int count = 0;
        if (str[i] == 'R') {
            count++;
            for (int j = i + 1; j <(int) str.length(); j++) {
                if (str[j] == 'R') {
                    count++;
                }
                else {
                    break;
                }
            }
        }
        res = max(res, count);
    }
    return res;
}

int main() {
    string str;
    cin >> str;
    printf("%d\n", solve(str));
}


Measured memory_bytes: 3648
import numpy as np
L, R = list(map(int, input().split()))

min_val = 2019
for i in range(L, R):
  for j in range(i+1, R+1):
    val = (i*j)%2019
    if min_val > val:
      min_val = val
      if min_val == 0:
        break
  if min_val == 0:
    break
print(min_val)

Measured memory_bytes: 12420
a,b,c,d,e,f=map(int,input().split())
s=[]
for i in range(f):
    for j in range(f):
        y=i*c+j*d
        if y<=f:
            s.append(y)
w=[]
for i in range(0,f//100+1):
    for j in range(0,f//100+1):
        x=i*a*100+j*b*100
        if x<=f:
            w.append(x)
max_con=0
ans,ans_2=0,0
for i in w:
    for j in s:
        if i==0 and j==0:
            continue
        elif e*(i//100)<j:
            continue
        elif i+j>f:
            continue
        else:
            con=(100*j)/(i+j)
            if max_con<=con:
                max_con=con
                ans=i+j
                ans_2=j
print(ans,ans_2)


Measured memory_bytes: 12440
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		while(N>=10) {
			N=N-10;
		}
		if(N == 3) {
			System.out.println("bon");
		}else if(N == 0 ||N == 1 || N == 6 || N == 8) {
			System.out.println("pon");
		}else {
			System.out.println("hon");
		}
	}

}


Measured memory_bytes: 35748
#include <bits/stdc++.h>
    #define ll long long
    #define sz(a) int((a).size())
    #define fr(i,n) for(int i=0;i<n;i++) 
    #define rf(i,n) for(int i=1;i<=n;i++)
    #define jdb(i,v) for(__typeof(v.begin())i=v.begin(); i!=v.end();i++)
    #define present(c,a) (find(all(c),a) != c.end())
    #define spresent(c,a) (c.find(a)!=c.end())
    #define no(s,c) s.count(c)  
    #define pb push_back 
    #define eb emplace_back
    #define mp make_pair
    #define all(c) (c).begin(),(c).end()
    #define MAX INT_MAX 
    using namespace std;
    #define f first
    #define s second
    int a[100005][3];
    int dp[100005][3];
    int n;
    int main() 
    { 
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        fr(i,n)
        cin>>a[i][0]>>a[i][1]>>a[i][2];
        dp[0][0]=a[0][0];
        dp[0][1]=a[0][1];
        dp[0][2]=a[0][2];
        rf(i,n-1)
        {
            fr(j,3)
            {
                dp[i][j]=max(dp[i-1][(j+1)%3]+a[i][j],dp[i-1][(j+2)%3]+a[i][j]);
            }
        }
        cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]))<<endl;
        return 0;
    }

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    istream& in(cin);
    ostream& out(cout);
    int n,c{};
    in>>n;
    vector<int> p(n);
    for(auto&i:p) in>>i;
    int M=1e9;
    fr(i,n){
        if(M>=p[i]){
            ++c;
            M=p[i];
        }
    }
    cout<<c<<endl;
}

Measured memory_bytes: 1024
import numpy as np
N = int(input())
a_list = list(map(int, input().split()))
ave1 = int(np.average(np.array(a_list)))
ave2 = ave1 + 1
ans1 = sum([ (x-ave1)**2 for x in a_list ])
ans2 = sum([ (x-ave2)**2 for x in a_list ])
if ans1 < ans2:
    ans = ans1
else:
    ans = ans2
print(ans)

Measured memory_bytes: 21228
#include <bits/stdc++.h>
#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 INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  string S;
  cin >> S;
  
  string s(S.length(), 'x');
  cout << s << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

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

bool is_edge(int x, char c){
    if(x<2) return c=='-';
    return c=='|';
}

int main(){
    int h,w;
    char s,t;
    cin >>h >>w >>s >>t;

    vector<string> f(h);
    rep(i,h) cin >>f[i];

    pi start,goal;
    rep(i,h)rep(j,w){
        if(f[i][j] == s) start = {i,j};
        if(f[i][j] == t) goal = {i,j};
    }

    auto IN = [&](int y, int x){ return 0<=y && y<h && 0<=x && x<w; };

    vector<vector<int>> d(h,vector<int>(w,INF));
    queue<pi> que;
    d[start.fi][start.se] = 0;
    que.push(start);
    while(!que.empty()){
        pi now = que.front();
        que.pop();

        rep(i,4){
            int xx = now.se+2*dx[i], yy = now.fi+2*dy[i];
            if(IN(yy,xx) && is_edge(i,f[yy][xx])){
                while( !('A'<=f[yy][xx] && f[yy][xx]<='Z') ){
                    yy += dy[i];
                    xx += dx[i];
                }

                if(('A'<=f[yy][xx] && f[yy][xx]<='Z')){
                    if(d[yy][xx] > d[now.fi][now.se]+1){
                        d[yy][xx] = d[now.fi][now.se]+1;
                        que.push({yy,xx});
                    }
                }
            }
        }
    }

    cout << d[goal.fi][goal.se] << endl;
    return 0;
}


Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int,int>;

int main(){
  vector<vector<vector<int>>> hito(4,vector<vector<int>>(3, vector<int>(10, 0)));
  int n;
  cin >> n;
  rep(i, n){
    int b, f, r, v;
    cin >> b >> f >> r >> v;
    hito.at(b-1).at(f-1).at(r-1) += v;
  }
  rep(i,4){
    rep(j,3){
      rep(k,10){
        cout << " " << hito.at(i).at(j).at(k);
      }
      cout << endl;
    }
    if(i!=3){
      cout << "####################" << endl;
    }
  }



  return 0;
}



Measured memory_bytes: 3140
/* ****revpro**** */
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define endl       '\n'
#define pii         pair<ll,ll>
#define vi          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)    
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define mii        map<ll,ll>
using namespace std;

#define N  100005
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int TESTS=1;
//    cin>>TESTS;
    while(TESTS--)
    {
        string s[2];
        cin>>s[1]>>s[0];
        cout<<s[0]<<s[1];
    }
    return 0;
}

Measured memory_bytes: 256
/* Bismillahirrahmanirrahim */
/* Author : Jehian Norman Saviero (@Reiva5) */
#include <bits/stdc++.h>

// MACROS SAMPAH
#define Jehian using
#define Norman namespace
#define Saviero std

Jehian Norman Saviero;

// MACROS TYPE
typedef long l;
typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pi;
typedef pair<l,l> pl;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<l> vl;
typedef vector<ll> vll;

// MACROS FOR PRINT
#define nl printf("\n")
#define sp printf(" ")

// MACROS FOR ATTRIBUTE
#define fi first
#define se second

// MACROS FOR FUNCTION AND METHOD
#define eb emplace_back
#define mp make_pair
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define ALL(x) (x).begin(), (x).end()
#define ALLN(x,n) (x), (x)+(n)
#define CUBE(x) (SQR(x)*(x))
#define SET(x,y) fill_n(x, sizeof(x)/sizeof(x[0]), y)
#define SQR(x) ((x)*(x))
#define SSORT(x,sz) sort(ALLN(x,sz))
#define RESET(x) memset((x), 0, sizeof(x))
#define VSORT(x) sort(ALL(x))

// MACROS READ INPUT
#define sci(x) scanf("%d", &x)
#define scl(x) scanf("%ld", &x)
#define scll(x) scanf("%lld", &x)
#define scf(x) scanf("%f", &x)
#define scd(x) scanf("%lf", &x)
#define scld(x) scanf("%Lf", &x)
#define scul(x) scl(x)
#define scull(x) scll(x)

int main() {
	int N, K;
	sci(N), sci(K);
	string s;
	cin >> s;
	vector<pi> dat;
	deque<pi> proc;
	int curr = s[0];
	int cnt = 1;
	for (int i = 1; i < s.size(); ++i) {
		if (s[i] == curr) ++cnt;
		else {
			dat.pb({curr-'0', cnt});
			curr = s[i];
			cnt = 1;
		}
	}
	dat.pb({curr-'0', cnt});
	cnt = 0;
	int sum = 0;
	int MAX = 0;
	for (int i = 0; i < dat.size(); ++i) {
		proc.pb(dat[i]);
		cnt += proc.back().fi == 0;
		sum += proc.back().se;
		while (cnt > K) {
			cnt -= proc.front().fi == 0;
			sum -= proc.front().se;
			proc.ppf();
		}
		MAX = max(MAX, sum);
	}
	printf("%d\n", MAX);
	return 0;
}

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

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vll;

#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const int maxN = 1e6+10, mod=1e9+7;

void solve() {
	string s;
	cin >> s;
	int n = s.back()-'0';
	if(n == 3) {
		cout << "bon\n";
	} else if(n==0 or n == 1 or n == 6 or n == 8) {
		cout << "pon\n";
	} else {
		cout << "hon\n";
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(NULL);
	
	int t=1;
	//cin >> t;
	
	while(t--) {
		solve();
	}
	
	return 0;
}


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

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b)
{ if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b)
{ if(b < a) { a = b; return true; } else { return false; } }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
ostream& operator<<(ostream &os, const string& s)
{ FOR(v, s) os << *v; return os; }
template<typename T> auto operator<<(ostream& os, const T& t)
    -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }

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

    int N;
    std::cin >> N;
    std::vector<int> A(N);
    REP(i, N) {
        std::cin >> A[i];
    }
    SORT(A);

    ll ans = 0;
    REP(i, N - 1) {
        ans += A[N - (i + 1) / 2 - 1];
    }
    std::cout << ans << std::endl;

    return 0;
}


Measured memory_bytes: 3932
#include<bits/stdc++.h>
#include<math.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int b[n],i;
    long long sum=0;
    for(i=1; i<=n-1; i++)
        cin>>b[i];
    sum+=b[1];
    if(n>1)
    {
        for(i=2; i<=n-1; i++)
        {
            if(b[i]>b[i-1])
                sum+=b[i-1];
            else
                sum+=b[i];
        }
    }
    sum+=b[i-1];
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
S_ = list(input())
T = list(input())

now = 0

flag2 = False

for i in reversed(range(len(S_) - len(T) + 1)):
    flag = True
    for j in range(len(T)):
        if S_[i + j] != '?' and S_[i + j] != T[j]:
            flag = False
            break
    if flag == True:
        flag2 = True
        for j in range(len(T)):
            S_[i + j] = T[j]
        break

S = ''
for i in S_:
    if i == '?':
        S += 'a'
    else:
        S += i

if flag2 == True:
    print(S)
else:
    print('UNRESTORABLE')

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
int main()
{
    ld a,b,c;
    cin >> a >> b >> c;
    if(c-a-b>0 && 4*a*b<(c-a-b)*(c-a-b)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>

const int MOD=1000000007; //10^9+7
const double PI=3.1415926535;

int main(){
    int N,M;
    cin>>N>>M;
    priority_queue<int> Q;
    for(int i=0;i<N;i++){
        int A;
        cin>>A;
        Q.push(A);
    }
    for(int i=0;i<M;i++){
        int t=Q.top();
        Q.pop();
        Q.push(t>>1);
    }
    ll ans=0;
    for(int i=0;i<N;i++){
        ll t=Q.top();
        Q.pop();
        ans+=t;
    }
    cout<<ans<<endl;

}

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

vector<pair<int, int> > w;
int n;

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		w.push_back({ b, a });
	}
	sort(w.begin(), w.end());
	long long ls = 0;
	for (int i = 0; i < w.size(); i++) {
		ls += w[i].second;
		if (ls > w[i].first)
			return cout << "No", 0;
	}
	cout << "Yes";
}

Measured memory_bytes: 3444
MAX_N=10**6
P=10**9+7
Fact=[0 for i in range(MAX_N+1)]
Fact[0]=1
for i in range(MAX_N):
    Fact[i+1]=(Fact[i]*(i+1))%P
N,M=map(int,input().split())
X=sorted([int(i) for i in input().split()])
Y=sorted([int(i) for i in input().split()])
A=[i for i in X]
B=[i for i in Y]
if len(set(A))!=N or len(set(B))!=M:
    print(0)
    exit()
L=[]
x=0
y=0
D=N*M
while(len(A)>0 and len(B)>0):
    if max(A[-1],B[-1])==D:
        if A[-1]>B[-1]:
            A.pop()
            L.append(y)
            x+=1
        elif A[-1]<B[-1]:
            B.pop()
            L.append(x)
            y+=1
        else:
            A.pop()
            B.pop()
            x+=1
            y+=1
        D-=1
    else:
        C=max(A[-1],B[-1])+1
        tmp=x*y-(N*M-D)
        for i in range(C,D+1)[::-1]:
            L.append(tmp)
            tmp-=1
        D=max(A[-1],B[-1])
if len(A)>0:
    D=min(Y)-1
    while(len(A)>0):
        C=A[-1]+1
        tmp=x*y-(N*M-D)
        for i in range(C,D+1)[::-1]:
            L.append(tmp)
            tmp-=1
        D=A.pop()-1
        x+=1
        L.append(M)
if len(B)>0:
    D=min(X)-1
    while(len(B)>0):
        C=B[-1]+1
        tmp=x*y-(N*M-D)
        for i in range(C,D+1)[::-1]:
            L.append(tmp)
            tmp-=1
        D=B.pop()-1
        y+=1
        L.append(N)
m=min(min(X),min(Y))-1
ans=Fact[m]
for i in L:
    ans*=i
    ans%=P
print(ans)


Measured memory_bytes: 114416
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1001001001;

int main() {
  int K, N;
  cin >> K >> N;
  int A[N];
  int d[N-1];
  int md = 0;
  rep(i,N) {
    cin >> A[i];
    if(i > 0) {
      d[i-1] = A[i] - A[i-1];
      md = max(md, d[i-1]);
      if (i == N-1) {
        d[i] = K + A[0] - A[i];
        md = max(md, d[i]);
      }
    }
  }

  cout<< K-md << endl;
  return 0;
}



Measured memory_bytes: 1792
// IN THE NAME OF ALLAH
#include <math.h>
#include <vector>
#include <set>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <stack>
#include<cstring>

#define F first
#define S second
#define mp make_pair

using namespace std;
typedef long long ll;

const int N = 1e3 + 10 , M = 2e5+10 , MOD = 1e9 + 7 , MAXN = 1e5 + 10;
const ll inf = 4e18 + 10;

ll a[N][N], dp[N][N];
int main()
{
      int n;
      cin>>n;
      for( int i = 1 ; i <= 2 ; i++ )
      {
            for( int j = 1 ; j <= n ; j++ )
            {
                  cin>>a[i][j];
            }
      }
      dp[1][1] = a[1][1];
      for( int i = 1 ; i <= 2 ; i++ )
      {
            for( int j = 1 ; j <= n ; j++ )
            {
                  if( i == 1 )
                        dp[i][j] = dp[i][j-1] + a[i][j];
                  else
                        dp[i][j] = max( dp[i][j-1] , dp[i-1][j] ) + a[i][j];
            }
      }
      cout<<dp[2][n]<<endl;
      return 0;
}


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

int main() {
  
  int D,N;
  cin >> D >> N;
  
  if ( D == 0 ){
    if( N != 100 ){
     cout << N << endl;
    }else{
     cout << 101 << endl;
    }
  }else if ( D == 1 ){
    if( N != 100 ){
     cout << 100*N << endl;
    }else{
     cout << 10100 << endl;
    }
  }else{
    if( N != 100 ){
     cout << 100*100*N << endl;
    }else{
     cout << 1010000<< endl;
    }
  }
  
}


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

using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<int> prime;
bool is_prime[1010];
int sieve(int n) {
  fill(is_prime + 2, is_prime + 1010, true);
  for (int i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime.emplace_back(i);
      for (int j = 2 * i; j <= n; j += i) is_prime[j] = false;
    }
  }
  return prime.size();
}

const ll mod = 1e9 + 7;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  int N;
  cin >> N;
  sieve(N);
  ll ans = 1;
  for (auto i : prime) {
    int p = i, sum = 0;
    while (p <= N) {
      sum += N / p;
      p *= i;
    }
    (ans *= (sum + 1)) %= mod;
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
// tree structure
// input id, number of sibling and each of sibling number, output id, parent, depth and type(root, internal and external)
#include<iostream>
typedef struct{
  int parent;
  int left_child;
  int next_sibling;
  int child;
}node;
int depth(int);
node *T;
int count;
int main(){
  int n, x, y, z, i, j;
  std::cin >> n;
  T = new node[n];
  for(i=0; i<n; i++) T[i].parent = -1;
  for(i=0; i<n; i++){
    std::cin >> x >> z;
    T[x].child = z;
    for(j=0; j<z; j++){
      if(j == 0){
        std:: cin >> y;
        T[y].parent = x, T[x].left_child = y;
      }
      else{
        std::cin >> T[y].next_sibling;
        T[y].parent = x, T[T[y].next_sibling].parent = x, y = T[y].next_sibling;
      }
    }
  }
  for(i=0; i<n; i++){
    count=0;
    std::cout<<"node "<<i<<": parent = "<<T[i].parent<<", depth = "<<depth(i);
    if(T[i].parent == -1) std::cout << ", root, [";
    else if(T[i].child == 0) std::cout << ", leaf, [";
    else std::cout << ", internal node, [";
    for(j=0; j<T[i].child; j++){
      if(j == 0){
        std::cout << T[i].left_child;
        x = T[T[i].left_child].next_sibling;
      }
      else{
        std::cout << x;
        x = T[x].next_sibling;
      }
      if(j != T[i].child - 1) std::cout << ", ";
    }
    std::cout << "]\n";
  }
  delete T;
  return 0;
}

int depth(int x){
  if(T[x].parent == -1) return count;
  else{
    count++;
    depth(T[x].parent);
  }
  return count;
}

Measured memory_bytes: 4344
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> z(n+2);
    for (int i = 0; i < n; i++) {
        cin >> z[i+1];
    }
    vector<vector<ll>> dp(n+2,vector<ll>(k+1,10000000000000));
    dp[0][0] = 0;
    for (int i = 1; i < n+2; i++) {
        for (int j = 0; j < k+1; j++) {
            for (int v = 0; v < min(i,j + 1); v++) {
                dp[i][j] = min(dp[i][j], dp[i - v - 1][j - v]+abs(z[i]-z[i - v - 1]));
            }
        }
    }
    cout << dp[n + 1][k]/2 << endl;
}

Measured memory_bytes: 4300
### constant

LOSE = 1
BACK = 2

### main

loop do
  n, t, l, b = gets.split.map(&:to_i)
  break if (n | t | l | b) == 0

  brds = (0...n).map{nil}
  l.times.each{brds[gets.to_i] = LOSE}
  b.times.each{brds[gets.to_i] = BACK}
  #p brds

  pbs = (0...n).map{0.0}
  lss = (0...n).map{0.0}
  pbs[0] = 1.0
  gl = 0.0

  t.times do
    pbs0 = (0...n).map{0.0}
    lss0 = (0...n).map{0.0}

    for i in (0...n)
      pbi = pbs[i]
      next if pbi == 0.0

      pbi6 = pbi / 6

      for dc in (1..6)
        j = i + dc

        if j > n
          j = 2 * n - j
        end

        if j == n
          gl += pbi6
        elsif brds[j] == LOSE
          lss0[j] += pbi6
        elsif brds[j] == BACK
          pbs0[0] += pbi6
        else
          pbs0[j] += pbi6
        end
      end
    end

    pbs = (0...n).map{|i| pbs0[i] + lss[i]}
    lss = lss0
  end

  #p [gl, pbs.inject(:+) + lss.inject(:+)]
  puts "%.6f" % gl
end

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

void downheap(vector<long long> &data,int index,int m){
    int k = 2*index+1;
    while(k+1<m){
        if(data[k]<data[k+1])k++;
        if(data[k]>data[index]){
            swap(data[k],data[index]);
        }
        index = k;
        k = 2*index+1;
    }
    if(k<m and data[k]>data[index])swap(data[k],data[index]);
}

long long popp(vector<long long> &data,int m){
    swap(data[0],data[m-1]);
    long long tmp = data[m-1];
    data[m-1]=0;
    downheap(data,0,m);
    return tmp;
}

long long poppush(vector<long long> &data,long long item,int m){
    data[m-1] = item;
    return popp(data,m);
}

long long pushpop(vector<long long> &data,long long item,int m){
    if(data[0]<=item){return item;}
    else{return poppush(data,item,m);}
}

int main(){
    long long n,m;
    cin >> n >> m;
    vector<long long> data(n);
    for(auto i=0;i<n;i++)cin >> data[i];
    for(auto i=n-1;i>=0;i--){
        downheap(data,i,n);
    }
    long long tmp = popp(data,n);
    for(auto i=0;i<m;i++){
        tmp = pushpop(data,tmp/2,n);
    }
    long long ans=0;
    for(auto i=0;i<n;i++)ans+=data[i];
    ans += tmp;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>
 
int main(){
  int count = 0;
  int a, b, c;
  scanf("%d %d %d",&a ,&b, &c);
  
  for(; a<=b; a++){
    if(a%c == 0)
      count++;
  }
  
  printf("%d", count);
  
  return 0;
}

Measured memory_bytes: 2064
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define PB push_back
int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  int n,x,t;
  cin>>n>>x>>t;
  int ans=(n/x)*t;
  if (n%x!=0)
  {
    ans+=t;
  }
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <algorithm>

using namespace std;

int p[100'000];

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

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

    int cnt = 0;
    for (int i = 0; i < N - 1; i++)
    {
        if (i == p[i])
        {
            swap(p[i], p[i + 1]);
            cnt++;
        }
    }

    if (p[N - 1] == N - 1)
    {
        cnt++;
    }

    cout << cnt << endl;
}

Measured memory_bytes: 640
let n = Int(readLine()!)!
var dic: Dictionary<String, Int> = [:]
for _ in 1...n {
	let key = readLine()!
	dic[key, default: 0] += 1
}
let keys = ["AC", "WA", "TLE", "RE"]
for k in keys {
	var s = k
	s.append(" x ")
	s.append(String(dic[k, default: 0]))
	print(s)
}


Measured memory_bytes: 8036
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
using namespace std;
typedef long long ll;
int main() {
	ll q, h, s, d, n;
	cin >> q >> h >> s >> d >> n;
	if (q * 8 < d)d = q * 8;
	if (q * 4 < s)s = q * 4;
	if (q * 2 < h)h = q * 2;
	if (h * 4 < d)d = h * 4;
	if (h * 2 < s)s = h * 2;
	if (s * 2 < d)d = s * 2;
	ll money = (n / 2)*d;
	n %= 2;
	money += n * s;
	cout << money << endl;
	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 256