akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
main(){
  int a,b,c,d,e=0;
  char A[21];
  char B[21];
  scanf("%s",A);
  b=strlen(A);
  for(a=0;a<strlen(A);a++){
    B[a]=A[b-1];
    b--;
  }
  for(c=0;c<strlen(A);c++){
    if(c==strlen(A)-1){
      printf("%c\n",B[c]);
    }
    else{
      printf("%c",B[c]);
    }
  }
  return 0;
}

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

#include <boost/math/common_factor_rt.hpp>
using namespace boost::math;

int main() {
	int n; cin >> n; int a_1; cin >> a_1; int a_2;
	for (int i = 0; i < n - 1; i++) {
		cin >> a_2;	a_1 = lcm(a_1, a_2);
	}
	cout << a_1 << endl;
	return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>

using namespace std;

#define REP(i,n)	for(int i=0;i<(n);++i)
#define REPS(i,s,t)	for(int i=(s);i<(t);++i)
#define SUMV(v)		(accumulate(v.begin(),v.end(),0.0))

#define INF 		2000000007
#define MOD			998244353

#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int ll;

//uint dp[MAX];

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

	if(N<=8&&B<=8)
		cout << "Yay!\n";
	else
		cout << ":(\n";
	
	return 0;
}

Measured memory_bytes: 256
n,m = gets.split.map(&:to_i)
abs = n.times.map { gets.split.map(&:to_i) }
price = 0
abs.sort_by{|ab| ab[0] }.each do |ab|
  cost,count = ab
  how_many_to_buy = [m,count].min
  m -= how_many_to_buy
  price += how_many_to_buy * cost
  if m == 0
    puts price
    exit
  end
end


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

int n, m = 0, s = 0;
int h[100];

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> h[i];
		s += h[i];
	}

	while (s > 0) {
		bool f = 0;
		for (int i = 0; i < n; i++) {
			if (h[i] > 0) {
				h[i]--;
				s--;
				if (!f) {
					m++;
					f = 1;
				}
			}
			else
				f = 0;
		}
	}

	cout << m << endl;

	return 0;
}

Measured memory_bytes: 256
a = []
a = gets.chomp.split("")
bit = []
cnt=0
c = []
for i in 0..(2**(a.length-1))-1
  c = a.clone
  #puts c.join(" ")
  b = i.to_s(2)
  bit = b.split("")
  while bit.length < a.length
    bit.insert(0,0)
  end
#puts bit.join(" ")
  for j in 0..bit.length-2   
   if bit[bit.length-1-j] == "1"
     c.insert(bit.length-1-j,"+") #後ろからやらないと挿入位置がずれる
   else
     c.insert(bit.length-1-j,"-") #後ろからやらないと挿入位置がずれる
   end
  end
  #puts c.join(" ")
  #puts eval(c.join(""))
  if eval(c.join("")) == 7
    puts "#{c.join("")}=7"
    exit
end
end
#puts cnt

Measured memory_bytes: 1788
#include<stdio.h>
#include<ctype.h>
 
void push(int);
int pop();
 
int top = 0; 
int S[101];
 
int main(){
 
  char A[100];
  int i, j;
 
  while(scanf("%s",A) != EOF){
    //printf("%d %d\n",top,A[top]);
    //fflush(stdout);
    if(isdigit(A[0])){
      push(atoi(A));
    }
    else{
       
      i = pop();
      j = pop(); 
  
      if(A[0] == '+')
    push( i + j);
      else if(A[0] =='-')
    push( j - i);
      else if (A[0] == '*')
    push (i * j);
      }
  }
 
  printf("%d\n",pop()  );
 
  return 0;
}
 
int pop(){
  return S[--top + 1];
}
 
void push(int x){
  //printf("%d %d\n",top,S[top]);
  // fflush( stdout );
  S[++top] = x;
}

Measured memory_bytes: 548
a= [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
k= int(input())
print(a[k-1])

Measured memory_bytes: 3060
//g++ -std=c++14 test.cpp -o test.out
 
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

LL N;
LL x[200000],y[200000];

LL ans = 0;

void solve(){
	LL u_max = -INF;
	LL u_min = INF;
	LL v_max = -INF;
	LL v_min = INF;
	for(int i=0;i<N;i++){
		u_max = max(u_max,x[i]+y[i]);
		u_min = min(u_min,x[i]+y[i]);
		v_max = max(v_max,x[i]-y[i]);
		v_min = min(v_min,x[i]-y[i]);
	}
	ans = max(u_max-u_min,v_max-v_min);
}
 
int main(){
	cin >> N;
	for(int i=0;i<N;i++) cin >> x[i] >> y[i];
 
    solve();

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

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

int check(void) {

}

int main() {
    int t_hp, t_at;
    int a_hp, a_at;

    cin >> t_hp >> t_at >> a_hp >> a_at;

    while (true) {

        a_hp -= t_at;

        if (a_hp <= 0) {
            cout << "Yes" << endl;
            break;
        }

        t_hp -= a_at;

        if (t_hp <= 0) {
            cout << "No" << endl;
            break;
        }
    }
}

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

int main(){
  char s[4];
  int a,b,c,d;
  b=0;
  cin>>s;
  for(a=0;a<2;a++){
    if(s[a]==s[a+1]&&s[a+1]==s[a+2]){
      b=1;
      break;
    }
  }
  if(b==1){
    cout<<"Yes"<<endl;
  }
  else {
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define SIZE 100005

struct Info{

	bool operator<(const struct Info &arg) const{

		return pre_need_level < arg.pre_need_level;
	}

	int index;
	ll limit,value,pre_node,pre_need_level;
};

struct Data{

	void set(ll arg_index,ll arg_diff){
		index = arg_index;
		diff = arg_diff;
	}
	ll index,diff;
};


ll V,K;
ll dp[105][SIZE];
ll first[SIZE],work[SIZE];
Info info[SIZE];
Data DEQ[SIZE];
vector<Info> G[SIZE];


void calc_dp(ll *base,ll *result,ll budget,ll value, ll limit){

	ll head = 0,tail = 0;

	for(int i = 0; i <= budget; i++){

		ll diff = base[i]-i*value;

		while(head < tail && DEQ[tail-1].diff <= diff)tail--;

		DEQ[tail++].set(i,diff);

		result[i] = DEQ[head].diff+i*value;

		if(i-DEQ[head].index == limit)head++;
	}
}


void recursive(int node_id,ll budget,ll *table){

	calc_dp(table,dp[node_id],budget,info[node_id].value,info[node_id].limit);

	for(int i = 0; i < G[node_id].size(); i++){

		int child = G[node_id][i].index;

		if(info[child].pre_need_level > budget)continue;

		recursive(child,budget-info[child].pre_need_level,table);

		table = dp[child];

		calc_dp(dp[child],work,budget,info[node_id].value,info[node_id].limit-info[child].pre_need_level);

		ll add = info[child].pre_need_level*info[node_id].value;

		for(int k = 0; k+info[child].pre_need_level <= budget; k++){

			dp[node_id][k+info[child].pre_need_level] = max(dp[node_id][k+info[child].pre_need_level],work[k]+add);
		}
	}
}

void func(){

	for(int i = 0; i < V; i++){

		scanf("%lld",&info[i].limit);
		info[i].index = i;
	}
	for(int i = 0; i < V; i++){

		scanf("%lld",&info[i].value);
	}
	for(int i = 1; i < V; i++){

		scanf("%lld",&info[i].pre_node);
		info[i].pre_node--;
	}
	for(int i = 1; i < V; i++){

		scanf("%lld",&info[i].pre_need_level);
		G[info[i].pre_node].push_back(info[i]);
	}

	for(int i = 0; i < V; i++){
		if(G[i].size() == 0)continue;

		sort(G[i].begin(),G[i].end());
	}

	for(int i = 0; i < V; i++){
		for(int k = 0; k <= K; k++){
			dp[i][k] = 0;
		}
	}

	for(int i = 0; i <= K; i++){

		first[i] = 0;
	}

	recursive(0,K,first);

	printf("%lld\n", dp[0][K]);
}

int main(){

	while(true){

		scanf("%lld %lld",&V,&K);
		if(V == 0 && K == 0)break;

		for(int i = 0; i < V; i++)G[i].clear();

		func();
	}

	return 0;
}




Measured memory_bytes: 86868
import java.util.*;

public class Main

{

	public static void main(String[] args)

	{

		Scanner input = new Scanner(System.in);

		int a = input.nextInt();

		int b = input.nextInt();

		if(a > 8 || b > 8) {

			System.out.println(":(");

		} else {

			System.out.println("Yay!");

		}

	}

}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define C(n,m) ((jc[n]*Jc[m])%1000000007*Jc[(n)-(m)]%1000000007)
#define add(a,b) a=((a)+(b))%1000000007
#define abs(x) ((x)>0?(x):-(x))
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define mod 1000000007
#define Mod 1000000005
#define ll long long
//#define file
using namespace std;

ll f[51][51],jc[51],Jc[51];
int n,i,j,k,l,x;

ll qpower(ll a,int b) {ll ans=1; while (b) {if (b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;} return ans;}

int main()
{
	#ifdef file
	freopen("agc022f.in","r",stdin);
	#endif
	
	scanf("%d",&n);
	jc[0]=1;
	fo(i,1,n) jc[i]=jc[i-1]*i%mod;
	Jc[n]=qpower(jc[n],Mod);
	fd(i,n-1,0) Jc[i]=Jc[i+1]*(i+1)%mod;
	
	f[1][0]=f[1][1]=1;
	fo(i,1,n-1)
	{
		fo(j,0,i)
		{
			fo(k,max(1,j),n-i)
			{
				fo(l,0,k)
				if (!((j+k)&1))
				{
					x=(j+k)/2;
					add(f[i+k][abs(x-l)],f[i][j]*C(i+k,i)%mod*C(k,l));
				}
			}
		}
	}
	printf("%lld\n",f[n][0]);
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Measured memory_bytes: 3800
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 1000000007;
const ll MAX = 1000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};


///////////////////////////

ll K;
vector<ll> A;

ll win(ll N) {
	repn(i, K) { N = N / A[i] * A[i]; }
	return N;
}


int main() {
	cin >> K;

	A.assign(K + 1, 0);
	repn(i, K) cin >> A[i];

	ll l = 0;
	ll r = INF;

	while (r - l > 1) {
		ll m = (r + l) / 2;
		if (win(m) > 2) { r = m; }
		else { l = m; }
	}

	ll X = r;

	l = 0;
	r = INF;

	while (r - l > 1) {
		ll m = (r + l) / 2;
		if (win(m) >= 2) { r = m; }
		else { l = m; }
	}

	ll Y = r;

	if (X == Y) { cout << -1; }
	else { cout << Y << " " << X - 1; }
	

	system("PAUSE");
}


Measured memory_bytes: 1272
#include <iostream>
#include <cstring>
#include <cstdlib>
using namespace std;

struct dic{
	string s;
	int page[1001];
};

dic d[101];

int comp(const void *a, const void *b){
if(((dic*)a)->s > ((dic*)b)->s) return 1;
else return -1;
}

int main(void){
	int i,j,p,tail=0;
	string str;
while((cin >> str) != NULL){
		for(i=0;i<tail;i++){
			if(str == d[i].s){
				cin >> p;
				d[i].page[p]=1;
				break;
			}
		}
		if(i == tail){
			d[tail].s = str;
			cin >> p;
			d[tail].page[p]=1;
			tail++;
		}
	}

	qsort(&d,tail,sizeof(dic),comp);
	int f;
	for(i=0;i<tail;i++){
		f=0;
		cout << d[i].s << endl;
		for(j=0;j<1001;j++){
			if(d[i].page[j] == 1){
				if(f) cout << " " << j;
				else{ cout << j; f++;}
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <cmath>
#include <utility>

using namespace std;

bool compare_by_b(pair<int, int> a, pair<int, int> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main(){

    int N = 0;
    cin >> N;

    vector<pair<int, int> > r(N);
    vector<pair<int, int> > b(N); 

    for(int i = 0; i < N; i++){
        int x, y = 0;
        cin >> x >> y;
        r[i] = make_pair(x,y);
    }
    for(int i = 0; i < N; i++){
        int x, y = 0;
        cin >> x >> y;
        b[i] = make_pair(x,y);
    }

    sort(b.begin(),b.end());
    //sort(bx.begin(),bx.end());

    pair<int, int> maxry;
    maxry = make_pair(-1, -1);

    int pairNum = 0;

    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(b[i].first > r[j].first && r[j].first >= 0){
                if(b[i].second > r[j].second){
                    if(maxry.first < r[j].second){
                        maxry = make_pair(r[j].second, j);
                    }
                }
            }
        }
        //ペア決定
        if(!(maxry.first == -1)){
            pairNum++;
            //ペアにしたやつはもうペアにはしない
            r[maxry.second].first = -1;
            r[maxry.second].second = -1;
            //初期化
            maxry = make_pair(-1, -1);
        }
    }
    
    std::cout << pairNum << std::endl;
}

Measured memory_bytes: 256
x = []
b = []
for i in range(3):
    s = list(map(int,input().split()))
    x.append(s)
N = int(input())
for j in range(N):
    b.append(int(input()))
temp =0
for j in range(3):
    if x[0][j] in b and x[1][j] in b and x[2][j] in b:
        temp = 1
        break
for j in range(3):
    if x[j][0] in b and x[j][1] in b and x[j][2] in b:
        temp = 1
        break
if x[0][0] in b and x[1][1] in b and x[2][2] in b:
    temp = 1
elif x[0][2] in b and x[1][1] in b and x[2][0] in b:
    temp = 1
if temp ==1:
    print("Yes")
else:print("No")


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

signed main(){
    int a,b,k;
    cin>>a>>b>>k;
    if(a>=k){
        cout<<a-k<<" "<<b<<endl;
        return 0;
    }
    k-=a;
    a=0;
    b=max(0ll,b-k);
    cout<<a<<" "<<b<<endl;
    return 0;

}


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



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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second
 
const int mx=200010;
const ll mod=1e9+7;

int main(){
  int n,m;
  string s;
  cin >> n >> m >> s;
  vector<int> dp(mx,inf);
  dp[n] = 0;
  queue<int> q;
  q.push(0);
  for(int i=n-1; i>=0; i--){
    while(1){
      if(q.size()==0){
        cout << -1 << endl; return 0;
      }
      if(q.front()!=inf && q.size()<=m) break;
      q.pop();
    }
    if(s[i]=='0') dp[i]=q.front()+1;
    q.push(dp[i]);
  }

  vector<int> ans;
  int x = 0;
  int cnt = dp[0];
  while(x<n){
    cnt--;
    int i=1;
    while(dp[x+i]!=cnt) i++;
    ans.push_back(i);
    x += i;
  }
  for(auto it:ans){
    cout << it << " ";
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 1912
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES cout<<"YES"<<'\n'
#define NO cout<<"NO"<<'\n'
#define Yes cout<<"Yes"<<'\n'
#define No cout<<"No"<<'\n'
#define yes cout<<"yes"<<'\n'
#define no cout<<"no"<<'\n'
void YN(bool flg) {cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg) {cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg) {cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#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 out(n) cout << n << '\n'
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
int ABS(int a) {if(a<0) a = -a; return a;}
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n >>= 1; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数の個数*/int divisor_number(int n){auto p = prime_factor(n); int res = 1; for(auto x:p)res*=(x.second+1); return res;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int a,b; char op; cin >> a >> op >> b;
    if(op=='+') out(a+b);
    else out(a-b);

    return 0;
}

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

using namespace std;

typedef long long ll;

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

	int n;
	cin >> n;

	queue<int> a[n];
	rep(i, n) rep(j, n-1){
		int x;
		cin >> x;
		x--;
		a[i].push(x);
	}

	queue<int> q;
	rep(i, n) q.push(i);

	int cnt = 0;
	bool updated = true;

	queue<int> q2;
	while(updated){
		updated = false;

		vector<bool> used(n, false);
		while(q.size() > 0){
			int i = q.front();
			q.pop();

			if(!used[i] && !a[i].empty()){
				int j = a[i].front();
				if(!used[j] && !a[j].empty() && a[j].front() == i){
					// cout << cnt << "," << i << "," << j << endl;
					updated = true;
					a[i].pop();
					a[j].pop();
					q2.push(i);
					q2.push(j);
					used[i] = true;
					used[j] = true;
				}
			}
		}

		if(updated) cnt++;
		swap(q, q2);
	}

	rep(i, n){
		if(!a[i].empty()){
			cout << -1 << endl;
			return 0;
		}
	}

	cout << cnt << endl;
}


Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long 

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

    int res=n%1000;

    if(res!=0)cout<<1000-res<<"\n";
    else cout<<res<<"\n";
    return 0;
}





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

int main() {
  string K;
  int D;
  cin >> K >> D;

  static long long dp[10001][2][100] = {};
  dp[0][0][0] = 1;
  for (size_t i = 0; i < K.size(); ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < D; ++k) {
        for (int d = 0; d <= (j ? 9 : K[i] - '0'); ++d) {
          dp[i + 1][j || d < K[i] - '0'][(k + d) % D] =
              (dp[i + 1][j || d < K[i] - '0'][(k + d) % D] + dp[i][j][k]) %
              1000000007;
        }
      }
    }
  }

  long long ans = dp[K.size()][0][0];
  ans = (ans + dp[K.size()][1][0]) % 1000000007;
  ans = (ans + 1000000006) % 1000000007;
  cout << ans << endl;
}

Measured memory_bytes: 15872
#include <cassert>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <limits.h>
#include <map>
#include <queue>
#include <set>
#include <string.h>
#include <vector>

using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

struct Node {
  int id;
  int cnt;

  Node(int id = -1, int cnt = -1) {
    this->id = id;
    this->cnt = cnt;
  }

  bool operator>(const Node &n) const {
    return cnt < n.cnt;
  }
};

int H, W, K;
char grid[10][1000];

bool splitPoint[10];
int roomId[10];

int updateSplitPoint(int mask) {
  int splitCnt = 0;
  int id = 0;

  for (int i = 0; i < H; ++i) {
    roomId[i] = id;

    if ((mask >> i) & 1) {
      splitPoint[i] = true;
      splitCnt++;
      ++id;
    } else {
      splitPoint[i] = false;
    }
  }

  return splitCnt;
}

int checker(int splitCnt) {
  int total[splitCnt];
  memset(total, 0, sizeof(total));
  int cnt = 0;

  for (int x = 0; x < W; ++x) {
    int counter[splitCnt];
    memset(counter, 0, sizeof(counter));

    for (int y = 0; y < H; ++y) {
      int id = roomId[y];

      if (grid[y][x] == '1') {
        counter[id]++;
      }
    }

    bool safe = true;

    for (int i = 0; i < splitCnt && safe; ++i) {
      // fprintf(stderr, "Room %d: %d\n", i, total[i] + counter[i]);
      if (total[i] + counter[i] > K) {
        safe = false;
      }
    }

    if (!safe) {
      // fprintf(stderr, "update => %d - %d\n", cnt, cnt + 1);
      cnt++;

      for (int i = 0; i < splitCnt; ++i) {
        total[i] = counter[i];

        if (total[i] > K) {
          return -1;
        }
      }
    } else {
      for (int i = 0; i < splitCnt; ++i) {
        total[i] += counter[i];
      }
    }
  }

  // fprintf(stderr, "return cnt = %d\n", cnt);
  return cnt;
}

int main() {
  cin >> H >> W >> K;

  string row;
  for (int y = 0; y < H; ++y) {
    cin >> row;

    for (int x = 0; x < W; ++x) {
      grid[y][x] = row[x];
    }
  }

  int ans = INT_MAX;

  for (int mask = 0; mask < pow(2, H - 1); ++mask) {
    int sc = updateSplitPoint(mask);
    int res = checker(sc + 1);

    // fprintf(stderr, "%d: (%d, %d)\n", mask, sc, res);
    if (res == -1) continue;

    int cnt = sc + res;
    ans = min(ans, cnt);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 2e5 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

int n, m, L[M], R[M];
ll mem[M][M][3];

ll add(ll a, ll b) {
  a += b;
  a %= MOD;
  return a;
}

ll sub(ll a, ll b) {
  a = (((a - b) % MOD) + MOD) % MOD;
  return a;
}

ll solve(int l, int r, int can) {
  if(l == n || r == m)
    return can == 1;
  ll& ret = mem[l][r][can];
  if(~ret)
    return ret;
  ret = 0;
  if(L[l] == R[r]) {
    if(can != 0)
//      ret += solve(l + 1, r + 1, 1);
      ret = add(ret, solve(l + 1, r + 1, 1));
  }
  if(can != 0) {
//    ret += solve(l + 1, r, can);
//    ret += solve(l, r + 1, can);
    ret = add(ret, solve(l + 1, r, can));
    ret = add(ret, solve(l, r + 1, can));
    ret = sub(ret, solve(l + 1, r + 1, can));
//    ret -= solve(l + 1, r + 1, can);
  }
  return ret;
}

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  cin >> n >> m;
  for (int i = 0; i < n; ++i) {
    cin >> L[i];
  }
  for (int i = 0; i < m; ++i) {
    cin >> R[i];
  }
  memset(mem, -1, sizeof mem);
  cout << add(solve(0, 0, 2), 1);
  return 0;
}


Measured memory_bytes: 588672
using System;
using System.Linq;
using System.Collections.Generic;

namespace ConsoleApp2
{
    public class Program
    {

        static long D = (long)Math.Pow(10, 9) + 7;


        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            List<int[]> poses = new List<int[]>();
            int[] order = new int[N];
            for (int i = 0; i < N; i++)
            {
                poses.Add(Read(Console.ReadLine()));
                order[i] = i + 1;
            }

            List<int[]> orders = Enumerate(order).ToList();
            List<double> ds = new List<double>();
            foreach (var item in orders)
            {
                double d = 0;
                for (int i = 0; i < N-1; i++)
                {
                    int[] posFrom = poses[item[i]-1];
                    int[] posTo = poses[item[i+1]-1];

                    d += Math.Sqrt(Math.Pow(posTo[0] - posFrom[0], 2) + Math.Pow(posTo[1] - posFrom[1], 2));
                }
                ds.Add(d);
            }
            Console.WriteLine(ds.Average());
            Console.ReadLine();
        }


        public static IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items)
        {
            if (items.Count() == 1)
            {
                yield return new T[] { items.First() };
                yield break;
            }
            foreach (var item in items)
            {
                var leftside = new T[] { item };
                var unused = items.Except(leftside);
                foreach (var rightside in Enumerate(unused))
                {
                    yield return leftside.Concat(rightside).ToArray();
                }
            }
        }


        private static int[] Read(string input)
        {
            string[] aaa = input.Split(' ');
            int num = aaa.Length;
            int[] ints = new int[num];
            for (int i = 0; i < num; i++)
            {
                ints[i] = int.Parse(aaa[i]);
            }
            
            return ints;
        }


    }


}


Measured memory_bytes: 24388
from operator import add
from functools import reduce

def exist(S, x):
    #print("exist S, %d" % x)
    left, right = 0, len(S)
    while left < right:
        idx = (left + right) // 2
        if S[idx] == x:
            return 1
        if S[idx] < x:
            left = idx + 1
        else: 
            right = idx
    return 0

def solve(S, T):
    return reduce(add, (exist(S, x) for x in T))

if __name__ == '__main__':
    n = int(input())
    #print("input n")
    S = [int(s) for s in input().split()]
    #print("input S")
    assert len(S) == n
    q = int(input())
    #print("input q")
    T = [int(s) for s in input().split()]
    #print("input T")
    assert len(T) == q
    print(solve(S, T))





Measured memory_bytes: 17572
using System;
using System.Text;
using System.Linq;
using System.Collections;
using System.Collections.Generic;


class Program
{


    static void Main(string[] args)
    {

        char[] cs = new char[] { ' ', ',' };
        //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 t = int.Parse(Console.ReadLine());
        //string str = Console.ReadLine();
        ///int[] vals = parseAry(Console.ReadLine().Split(cs));
        //int n = int.Parse(Console.ReadLine());
		string res="No";
        int[] vals = parseAry(Console.ReadLine().Split(cs));
		if ( vals[0] == vals[1] && vals[0] == vals[2] ) { res = "Yes"; }
        Console.WriteLine(res);

        return;
    }

    //　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: 13140
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <iomanip>
#include <bitset>
#include <set>
#include <map>
#include <stdio.h>
#include <numeric>
#include <cstring>

#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i < (n); i++)
#define FOR(i,a,b) for (int i=(a); i < (b); i++)
#define MOD 1000000007 //10^9+7
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
const int INF = numeric_limits<int>::max();
const ll INFL = numeric_limits<ll>::max();


// 負の数にも対応した % 演算
long long mod(long long val, long long m) {
    long long res = val % m;
    if (res < 0) res += m;
    return res;
}

//greatest common divisor
long long gcd(ll a, ll b) 
{
    if (a % b == 0) {
        return b;
    } else {
        return gcd(b, a % b);
    }
}

//least common multiple
long long lcm(ll a, ll b)
{
    return a / gcd(a, b) * b ;
}

ll factorial(ll n) {
    ll res = 1;
    for (ll i = 1; i <= n; i++) {
        res *= i;
    }
    return res;
}

int main()
{
    int n; cin >> n;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    int ans = 0;
    for (int i = 1; i < n - 1; i++) {
        if (p[i-1] < p[i] && p[i] < p[i+1])
            ans++;
        if (p[i-1] > p[i] && p[i] > p[i+1])
            ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3612
// Vicfred
// https://atcoder.jp/contests/abc052/tasks/abc052_b
// simulation
import std.algorithm;
import std.conv;
import std.stdio;
import std.string;

void main() {
    int n = readln.chomp.to!int;
    string s = readln.chomp;

    int maxima = 0;
    int x = 0;
    foreach(ch; s) {
        if(ch == 'I')
            x += 1;
        else
            x -= 1;
        maxima = max(maxima, x);
    }

    maxima.writeln;
}



Measured memory_bytes: 256
import bisect
n = int(input())

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ppp = [[0,0] for i in range(n)]

a.sort()
b.sort()
c.sort()

su = 0
for i in range(n):
    ppp[i][0] = bisect.bisect_left(a,b[i])
for i in range(n):
    ppp[i][1] = n-bisect.bisect_right(c,b[i])
for i in range(n):
    su += ppp[i][0]*ppp[i][1]
print(su)

Measured memory_bytes: 32436
#include <iostream>
#include <string>
using namespace std;
    int main(){
    string S;
    int a=0;
    cin >> S;
    for(int x=0; x<=4; x++){
        if(S[x]=='+'){
            a+=1;
        }else if(S[x]=='-'){
            a-=1;
        }
    }
    cout << a << endl;
    }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <queue>
#include <stack>
#include <tuple>
#include <cmath>
#include <iomanip>
#include <map>
#include <cstring> //memset(dp,0,sizeof(dp))
#include <functional>
#include <cctype>
#include <locale>
#define ll long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
typedef pair<int,int> P;
typedef pair<long long,long long> Pll;
#define fout(num) cout << fixed << setprecision(20) << (num) << endl
//s[i]=tolower(s[i]); islower(s[i]); cout << tolower(s[i])はバグ
//vector<vector<ll>> dp(n,vector<ll>(n))
//exist x map o setconst ll MOD = 1e9+7;return fac[n]*(finv[k]*finv[n-k] % MOD) % MOD;

signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    ll k; cin >> k;
    ll x=7;
    rep(i,10010010){
        if(x%k==0){
            cout<<i+1<<endl;
            return 0;
        }
        x=(10*x+7)%k;
    }
    cout<<-1<<endl;
}



Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1000000007;
long long modpow(long long a, long long n)
{
    long long res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main()
{
    long long n;
    cin >> n;
    long long ans = modpow(10, n) - modpow(9, n) * 2 + modpow(8, n); //この値は正の値とは限らない
    while (ans < 0) {
        ans += mod;
    } //これで正の値と保証された

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

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,A,ASum,BSum;
  bool boolA;
  
  //優先度付きキュー
  priority_queue<int> pq;
  
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A;
    //優先度付きキューに順次格納
    pq.push(A);
  }
  
  ASum = 0;
  boolA = true;
  BSum = 0;
  
  //キューが空でない間繰り返す
  while (!pq.empty()) {
    if (boolA == true){
      ASum = ASum + pq.top();
      pq.pop();
      boolA = false;
    }
    else{
      BSum = BSum + pq.top();
      pq.pop();
      boolA = true;
    }
  }  

  cout << ASum - BSum << endl;
  
}

Measured memory_bytes: 3632
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define FOR(n) for(int i=0;i<n;i++)
#define FORJ(n) for(int j=0;j<n;j++)
#define PRN(n) printf("%d\n",n)
#define PRF(n) printf("%lf\n",n)
#define PRL(n) printf("%lld\n",n)
#define PRS(s) printf("%s\n",s)
#define PRC(c) printf("%c",c)
#define mod 1000000007
typedef long long int ll;
ll dp[100001];
int q(const void *a, const void *b){
    return *(ll*)a-*(ll*)b;
}
int min(int a,int b){
  if(a>b)return b;
  return a;
}
int max(int a,int b){
  if(a>b)return a;
  return b;
}
int gcd(int a,int b){
  if(!b)return a;
  return gcd(b,a%b);
}
int main(void) {
  char w[7][4]={
    "thu","fri","sat","sun","mon","tue","wed"
  };
  int n;
  scanf("%d",&n);
  PRS(w[n%7]);
  return 0;
}


Measured memory_bytes: 2140
use std::io::*;
use std::str::FromStr;

type NodeId = usize;

struct Node {
    parent: Option<NodeId>,
    left: Option<NodeId>,
    right: Option<NodeId>,
}

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn preorder(node_id: NodeId, nodes: &Vec<Node>) {
    print!(" {}", node_id);
    if nodes[node_id].left != None {
        preorder(nodes[node_id].left.unwrap(), nodes)
    }
    if nodes[node_id].right != None {
        preorder(nodes[node_id].right.unwrap(), nodes)
    }
}

fn inorder(node_id: NodeId, nodes: &Vec<Node>) {
    if nodes[node_id].left != None {
        inorder(nodes[node_id].left.unwrap(), nodes)
    }
    print!(" {}", node_id);
    if nodes[node_id].right != None {
        inorder(nodes[node_id].right.unwrap(), nodes)
    }
}

fn postorder(node_id: NodeId, nodes: &Vec<Node>) {
    if nodes[node_id].left != None {
        postorder(nodes[node_id].left.unwrap(), nodes)
    }
    if nodes[node_id].right != None {
        postorder(nodes[node_id].right.unwrap(), nodes)
    }
    print!(" {}", node_id);
}

fn main() {
    let n: usize = read();
    let mut nodes: Vec<Node> = (0..n)
        .map(|_| Node {
            parent: None,
            left: None,
            right: None,
        })
        .collect();

    let mut root_node_id: NodeId = 0;

    for _ in 0..n {
        let node_id: NodeId = read();
        let left_input: i64 = read();
        let right_input: i64 = read();

        if left_input == -1 {
            nodes[node_id].left = None;
        } else {
            nodes[node_id].left = Some(left_input as usize);
            nodes[left_input as usize].parent = Some(node_id);
        }

        if right_input == -1 {
            nodes[node_id].right = None;
        } else {
            nodes[node_id].right = Some(right_input as usize);
            nodes[right_input as usize].parent = Some(node_id);
        }
    }

    for index in 0..n {
        if nodes[index].parent == None {
            root_node_id = index;
        }
    }

    println!("Preorder");
    preorder(root_node_id, &nodes);
    println!();
    println!("Inorder");
    inorder(root_node_id, &nodes);
    println!();
    println!("Postorder");
    postorder(root_node_id, &nodes);
    println!();
}



Measured memory_bytes: 5024
#include<stdio.h>
int main()
{
	int n,p,d1,d2,i,m,a;
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		m=0;
		for(i=0;i<n;i++){
			scanf("%d%d%d",&p,&d1,&d2);
			if(d1+d2>m){
				a=p;
				m=d1+d2;
			}
		}
		printf("%d %d\n",a,m);
	}
	return 0;
}

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

int main() {

  string A, B, C;
  cin >> A >> B >> C;

  int currentA = 0;
  int currentB = 0;
  int currentC = 0;

  string turn = "a";
  string winner = "";

  while (winner == "") {
    if (turn == "a") {
      if (currentA == A.size()) {
        winner = "A";
      } else {
        turn = A.at(currentA);
        currentA++;
      }
    } else if (turn == "b") {
      if (currentB == B.size()) {
        winner = "B";
      } else {
        turn = B.at(currentB);
        currentB++;
      }
    } else {
      if (currentC == C.size()) {
        winner = "C";
      } else {
        turn = C.at(currentC);
        currentC++;
      }
    }
  }

  cout << winner << endl;

}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF (3e15)

using namespace std;

string S;

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

    cin >> S;

    if (S[0] == S[S.size() - 1]) {
        // 奇数個で終わる
        if (S.size() & 1) {
            cout << "Second" << endl;
        } else {
            cout << "First" << endl;
        }
    } else {
        // 偶数個で終わる
        if (S.size() & 1) {
            cout << "First" << endl;
        } else {
            cout << "Second" << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 512
import std.stdio, std.conv, std.string, std.array;

bool f(int[] nList, int i, int m)
{
    if(m == 0)
        return true;
    if(m < 0)
        return false;
    if(i == nList.length)
        return false;
    return f(nList, i+1, m) || f(nList, i+1, m-nList[i]);

}
void main()
{
    readln();
    int[] nList = readln.split.to!(int[]);
    readln();
    int[] qList = readln.split.to!(int[]);
    foreach(int q; qList)
    {
        if(f(nList, 0, q))
            writeln("yes");
        else
            writeln("no");
    }
}


Measured memory_bytes: 2468
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<time.h>
#include<tuple>
#include<set>
#include<map>
#include<cctype>
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define vint vector<int> 
#define vvint vector<vint>
#define ct(a) cout<<a<<endl
#define tget(a,b) get<a>(b)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;
const int MOD = 1e9 + 7;

string a, b, c;
int main(void) {
	cin >> a >> b >> c;
	cout << a[0] << b[0] << c[0]<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#define max 500000
int size,A[max];

int RIGHT(int i){
    return 2*i;
}
int LEFT(int i){
    return 2*i+1;
}
//配列を関数で渡すのはややこしくなるからしない
void maxheapify(int i){
    int left,right,largest;
    left=LEFT(i);
    right=RIGHT(i);
    if(left<=size && A[left]>A[i]){
        largest=left;
        }else{
            largest=i;
        }
    if(right<=size && A[right]>A[largest]){
        largest=right;
    }
    if(largest!=i){
        //swap
        int temp=0;
        temp=A[i];
        A[i]=A[largest];
        A[largest]=temp;
        maxheapify(largest);
    }
}
/*
void buildmaxheap(A){
    int i;
    for(i=size/2;i>0;i--){
        maxheapify(A,i);
    }
}*/
/*
void swap(int *a,int *b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}*/
int main(){
    int i;
    scanf("%d",&size);
    for(i=1;i<=size;i++){
        scanf("%d",&A[i]);
    }
     for(i=size/2;i>0;i--){
        maxheapify(i);
    }
    for(i=1;i<=size;i++){
      printf(" %d",A[i]);
        if(size==i){
            printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 3668
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;

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

struct E {
  int from, to, c;
};

using G = vector<vector<E>>;

int main() {
  int n, m;
  cin >> n >> m;
  G g(n);
  set<pair<int, int>> st;
  REP(i, m) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    if (b == n - 1)
      st.insert({a, c});
    else
      g[a].push_back({a, b, c});
  }
  using P = pair<int, int>;
  constexpr int INF = 1e9 + 1;
  vector<int> d(n, INF);
  d[0] = 0;
  priority_queue<P, vector<P>, greater<>> q;
  q.push({0, 0});
  while (!q.empty()) {
    P p = q.top();
    q.pop();
    if (p.first > d[p.second])
      continue;
    for (auto e : g[p.second]) {
      if (e.c >= d[p.second] && d[e.to] > e.c) {
        d[e.to] = e.c;
        q.push({e.c, e.to});
      }
    }
  }

  int ans = -1;
  for (auto a : st) {
    if (d[a.first] <= a.second)
      ans = max(ans, a.second);
  }
  cout << ans << endl;
}


Measured memory_bytes: 8996
#include <stdio.h>
#include <math.h>

int main(){

  int i,n,count = 0,a;

  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&a);
    count += isPrime(a);
  }
  
  printf("%d\n",count);
  
  return 0;
}

int isPrime(int a){
  int i;

  if(a==2){
    return 1;
  }

  if(a<2 || (a%2 == 0)){
    return 0;
  }

  i = 3;

  while(i<=sqrt(a)){
    
    if(a%i == 0){
      return 0;
    }
    
    
    i = i + 2;
  }
  
  return 1;
 
  
}




Measured memory_bytes: 2040
#include<bits/stdc++.h>
#include<cmath>
#define SZ(x) ((int)x.size())
#include<vector>
#include<set>
#include<map>
#define ll long long
#define lli long long int
#define REP(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#include<string>
#include<cctype>
#include<queue>
#define ii pair<int,int>
#include <sstream>
#define lli long long int
#define pairs pair<int,int>
#define mod 1000000007
const double PI = 3.141592653589793238460;
typedef std::complex<double> Complex;
typedef std::valarray<Complex> CArray;
using namespace std;
ll pows(ll a,ll n,ll m)
{
	ll res=1;
	while(n)
	{
	if(n%2!=0)
	{
		res=(res*a)%m;
		n--;
		}
		else
		{
			a=(a*a)%m;
			n=n/2;
			}	
	}
	return res%m;
}
ll  gcd(ll a,ll b)
{
	if(b==0)
	return a;
	else 
	return gcd(b,a%b);
}
bool isprime(ll n)
{
	if(n==1)
	{
		return false;
	}
	for(ll i=2;i*i<=n;i++)
	{
		if(n%i==0)
		{
			return false;
		}
	}
	return true;
}
bool istrue(string s)
{
	int i=0;
	int j=s.size()-1;
	while(i<j)
	{
	if(s[i]==s[j])
	{
		i++;
		j--;
		}
		else
		{
			return false;
			}	
	}
	return true;
}
ll n;
ll a[100001];
ll k;
ll dp[100001];
ll getans(ll i)
{
if(i>=n-1)
{
	return 0;
	}
	if(dp[i]!=-1)
	{
		return dp[i];
	}
	ll ans=1e12;
	for(ll j=1;j<=k;j++)
	{
if(i+j<=n-1)
{
	ans=min(ans,getans(i+j)+abs(a[i]-a[i+j]));
}
	}
return dp[i]=ans;
}
int main()
{
ios::sync_with_stdio(false);
	 cin.tie(0);
    cout.tie(0);
cin>>n;
cin>>k;

for(ll i=0;i<n;i++)
{
	cin>>a[i];
}
memset(dp,-1,sizeof(dp));
cout<<getans(0)<<endl;
}




Measured memory_bytes: 9804
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,k,n) for(int i = (int)(k); i < (int)(n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(a) a.begin(), a.end()
#define MS(m,v) memset(m,v,sizeof(m))
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int, int> pii;
const int MOD = 1000000007;
const int INF = MOD + 1;
const ld EPS = 1e-12;
template<class T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<class T> T &chmax(T &a, const T &b) { return a = max(a, b); }

/*--------------------template--------------------*/

int main()
{
	cin.sync_with_stdio(false); cout << fixed << setprecision(10);
	int n, t; cin >> n >> t;
	vi a(n);
	REP(i, n) cin >> a[i];
	int mn = INF;
	int bene = -1;
	for (auto i : a)
	{
		if (mn > i) mn = i;
		chmax(bene, i - mn);
	}
	map<int, int> mp;
	int ans = 0;
	for (int i = n - 1; i >= 0; i--)
	{
		int t = a[i] + bene;
		ans += mp[t];
		mp[t - 1] += mp[t];
		mp[t] = 0;
		mp[a[i]]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 14720
#include<cstdio>
#include<algorithm>
using namespace std;
int n , w, h, p, a[200][200];
int main() {
	scanf("%d%d%d", &h, &w, &n);
	int x = 0, y = 0, dir = 1; 
	for(int i = 1; i <= n; i++) {
		scanf("%d", &p);
		for(int j = 1; j <= p; j++) {
			a[x][y] = i;
			y += dir;
			if(y == w && dir == 1) {
				y = w - 1;
				x++;
				dir = -1;
			}
			if(y == -1 && dir == -1) {
				y = 0;
				x++;
				dir = 1;
			}
		}
	}
	for(int i = 0 ; i < h; i++)  {
		for(int j = 0; j < w; j++) printf("%d ",a[i][j]);
		printf("\n");
	}
		
	return 0;
}

Measured memory_bytes: 256
ST = str(input())

S = list(ST)

#print(S[0])

retu = len(S)

sa = 9999

for i in range(0,retu-2):

    kazu = int(S[i]) *100 + int(S[i+1])*10 + int(S[i+2])

    kazu = abs(kazu -753)

    if sa > kazu:
        sa = kazu

print(sa)


Measured memory_bytes: 2940
s=input()
p=int(s[:2])
n=int(s[2:])
if 1<=p<=12 and 1<=n<=12:
    print("AMBIGUOUS")
elif 1<=p<=12:
    print("MMYY")
elif 1<=n<=12:
    print("YYMM")
else:
    print("NA")


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
using namespace std;
int main(void){
    int x;
    vector<bool> v;
    cin >> x;
    v.assign(1e6, true);
    for(int i = 2; i < 1e6; i++){
        if(!v[i]) continue;
        if(i >= x){
            cout << i << endl;
            return 0;
        }
        for(int j=i*2;j<1e6;j+=i){
            v[j] = false;
        }
    }
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<ctime>

using namespace std;
using ll = long long;

bool solve(vector<int>masu, vector<int>point){
  for(int i = 0; i < 8; i++){
    if(point[i] != -1){
      if(point[i] != masu[i]) return false;
    }
  }
  vector<int> used_a(15, 0), used_b(15, 0);
  for(int i = 0; i < 8; i++){
    if(used_a[masu[i] - i + 7]) return false;
    if(used_b[masu[i] + i]) return false;
    used_a[masu[i] - i + 7] = 1;
    used_b[masu[i] + i] = 1;
  }
  return true;
}

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int ti = clock();
  // start-----------------------------------------------
  int n; cin >> n;
  vector<int> masu(8);
  vector<int> point(8, -1);
  for(int i = 0; i < 8; i++) masu[i] = i;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    point[a] = b;
  }
  do{
    if(solve(masu, point)) point = masu;
  }while(next_permutation(masu.begin(), masu.end()));
  for(int i = 0; i < 8; i++){
    for(int j = 0; j < 8; j++){
      if(point[i] == j)cout << 'Q';
      else cout << '.';
    }
    cout << endl;
  }
  // end-----------------------------------------------
  // cerr << 1.0 * (clock() - ti) / CLOCKS_PER_SEC << endl;
}



Measured memory_bytes: 3196
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    priority_queue<ll> q;
    REP(i,n){
        ll a;
        cin >> a;
        q.push(a);
    }
    REP(i,m){
        ll now = q.top();
        q.pop();
        now = now/2;
        q.push(now);
    }
    ll ans = 0;
    while(!q.empty()){
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1400