akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
vector <long long> num;
string a;
long long k,res1,res2;
long long f[10005][200][3];
long long call(int pos,long long remain,long long status)
{
    if(pos==num.size())
    {
        if (remain==0)
            return 1;
        return 0;
    }
    if(f[pos][remain][status]!=-1)
        return f[pos][remain][status]%MOD;
    long long res=0,limit;
    if(status==0)
        limit=num[pos];
    else
        limit=9;
    for(int i=0; i<=limit; i++)
    {
        int cur_status=status;
        int cur_remain=(remain+i)%k;
        if(status==0 && i<limit)
            cur_status=1;
        res+=call(pos+1,cur_remain,cur_status);
    }
    return f[pos][remain][status]=res%MOD;
}
void preprocess(string x)
{
    num.clear();
    int p=0;
    while (p<=x.size()-1)
    {
        num.push_back(x[p]-'0');
        p++;
    }
    memset(f,-1,sizeof(f));
}
int main ()
{
    cin>>a;
    cin>>k;
    preprocess(a);
    res1=call(0,0,0);
    cout<<(res1-1+MOD)%MOD<<endl;
}


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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

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

int N, M;
priority_queue<int> pq;

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

    std::cin >> N >> M;

    for(int i=0;i<M;++i){
        int a, b;
        std::cin >> a >> b;

        pq.emplace(a);
    }

    int res = 0;
    for(int i=0;i<M-1;++i){
        int a = pq.top(); pq.pop();
        res += max(N - a, 0);
    }

    std::cout << res << std::endl;
}



Measured memory_bytes: 3232
#include <vector>
#include <iostream>

#define int long long

using namespace std;

const int N = 2e5 + 10;

int h[N];
vector<int> g[N];

int32_t main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    while (m--)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    int ans = n;
    for (int i = 1; i <= n; ++i)
    {
        bool b = 1;
        for (int &x : g[i])
        {
            if (h[x] >= h[i]) 
            {
                b = 0;
                break;
            }
        }
        ans -= !b;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 12568
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
int MOD=1000000007;
int main(){
    int N;
    cin >> N;
    string S[N+10],P[N+10],A[N+10];
    int B[N+10];
    map<string, int> mp;
    for(int i=0; i<N; i++){
        cin >> S[i] >> P[i];
        B[i]=stoi(P[i]);
        B[i]=100-B[i];
        P[i]=B[i];
        A[i]=S[i]+P[i];
        mp[A[i]]=i+1;
    }
    sort(A,A+N); 
    for(int i=0; i<N; i++){
        cout << mp[A[i]] << 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 NUM 1440

struct Info{
	Info(int arg_station_id,int arg_stop_time){
		station_id = arg_station_id;
		stop_time = arg_stop_time;
	}
	bool operator<(const struct Info &arg) const{
		return stop_time < arg.stop_time;
	}
	int station_id,stop_time;
};

struct Data{
	Data(int arg_train_id,int arg_stop_index){
		train_id = arg_train_id;
		stop_index = arg_stop_index;
	}
	int train_id,stop_index;
};

int start,start_time;
int goal,goal_time;
int num_station,num_train;
int dp[1005][NUM];
vector<Info> TRAIN[105];
vector<Data> STATION[1005][NUM];

int getTime(char buf[6]){

	int hour = 10*(buf[0]-'0')+(buf[1]-'0');
	int minute = 10*(buf[3]-'0')+(buf[4]-'0');

	return 60*hour+minute;
}

void func(){

	for(int i = 0; i < num_station; i++){
		for(int k = 0; k < NUM; k++){

			STATION[i][k].clear();
		}
	}

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

		TRAIN[i].clear();
	}

	char buf[6];

	scanf("%d %s",&start,buf);
	start--;
	start_time = getTime(buf);

	scanf("%d %s",&goal,buf);
	goal--;
	goal_time = getTime(buf);

	int num_stop;
	int station_id,stop_time;

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

		scanf("%d",&num_stop);

		for(int k = 0; k < num_stop; k++){

			scanf("%d %s",&station_id,buf);
			station_id--;
			stop_time = getTime(buf);

			TRAIN[i].push_back(Info(station_id,stop_time));
		}
		sort(TRAIN[i].begin(),TRAIN[i].end());
	}

	if(start_time > goal_time){

		printf("impossible\n");
		return;
	}

	for(int i = 0; i < num_train; i++){
		for(int k = 0; k < TRAIN[i].size(); k++){

			STATION[TRAIN[i][k].station_id][TRAIN[i][k].stop_time].push_back(Data(i,k));
		}
	}

	for(int i = 0; i < num_station; i++){
		for(int k = start_time; k <= goal_time; k++){

			dp[i][k] = -1;
		}
	}

	dp[start][start_time] = 0;

	int train_id,stop_index;

	for(int k = start_time; k < goal_time; k++){
		for(int i = 0; i < num_station; i++){

			if(dp[i][k] == -1)continue;
			dp[i][k+1] = max(dp[i][k+1],dp[i][k]);

			for(int a = 0; a < STATION[i][k].size(); a++){

				train_id = STATION[i][k][a].train_id;
				stop_index = STATION[i][k][a].stop_index;

				for(int b = stop_index+1; b < TRAIN[train_id].size(); b++){

					if(TRAIN[train_id][b].stop_time > goal_time)break;

					station_id = TRAIN[train_id][b].station_id;
					stop_time = TRAIN[train_id][b].stop_time;

					dp[station_id][stop_time] = max(dp[station_id][stop_time],max(dp[i][k],stop_time-k));
				}
			}
		}
	}

	int ans = -1;

	for(int i = start_time; i <= goal_time; i++){

		ans = max(ans,dp[goal][i]);
	}

	if(ans == -1){

		printf("impossible\n");

	}else{

		printf("%d\n",ans);
	}
}

int main(){

	while(true){

		scanf("%d %d",&num_station,&num_train);
		if(num_station == 0 && num_train == 0)break;

		func();
	}

	return 0;
}



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

int main()
{
    int N;
    cin>>N;
    while(N!=0){
        int index=0;
        int maxDist=0;
        for ( int i = 0; i < N; i++ ) {
            int k,a,b;
            cin>>k>>a>>b;
            if(a+b>maxDist) {
                maxDist = a + b;
                index = k;
            }
        }
        cout << index << " " << maxDist << endl;
        cin >> N;
    }
    return ( 0 );
}



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

int main(){
  int n,d,x,ans;
  int a[100];

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

  ans = x;

  for(int i = 0; i < n; i++){
    int cnt = 1+a[i];
    ans++;

    while(cnt <= d){
      cnt += a[i];
      ans++;
    }
  }

  cout << ans << endl;

  return 0;
}

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

void solve()
{
    ll n, m; cin >> n >> m;
    vector<ll> v(n);
    ll ans = 0;
    for (ll i = 0; i < n; ++i) {
        cin >> v[i];
        ans += v[i];
    }
    sort(v.begin(), v.end());
    map<ll, ll, greater<ll>> vals;
    for (ll i = 0; i < m; ++i) {
        ll b, c; cin >> b >> c;
        vals[c] += b;
    }
    ll i = 0;
    for (auto it = vals.begin(); it != vals.end(); ++it) {
        ll val = it->first;
        ll count = it->second;
        while (i < n && v[i] < val && count-- > 0) {
            ans += val - v[i++];
        }
    }
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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

int main(){
    int N;
    cin >> N;
    double x[N] = {};
    string u[N] = {};

    for(int i = 0; i < N; i++){
        cin >> x[i] >> u[i];
    }
    
    double a = 0;

    for(int j = 0; j < N; j++){
        if(u[j] == "JPY"){
            a += x[j];
        }else{
            a += 380000 * x[j];
        }
    }
    
    cout << a << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define nmax 100000
using namespace std;
int n, a[nmax+1], cdd[nmax+1][2];
long long ans[nmax+1];
void in()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
      cin >> a[i];
}
void prs()
{
    int cnt = 1, mx = a[1];
    cdd[0][1] = 0;
    cdd[1][0] = 1;
    cdd[1][1] = a[1];
    for(int i = 2; i <= n; ++i) if(a[i] > mx){
      mx = a[i];
      cdd[++cnt][0] = i;
      cdd[cnt][1] = a[i];
    }
    std::sort(a + 1, a + n + 1);
    int ci = n, cm = a[n];
    for(int u = cnt; u > 0; --u){
      int i = cdd[u][0], v = cdd[u - 1][1];
      ans[i] = (long long) (n - ci) * (cm - v);
      for(; ci > 0 && a[ci] >= v; --ci)
        ans[i] += a[ci] - v;
      cm = v;
    }
}
void out()
{
    for(int i = 1; i <= n; ++i)
      cout << ans[i] << '\n';
}
void run()
{
    in();
    prs();
    out();
}
int main()
{
    std::ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
    return 0;
}


Measured memory_bytes: 3072
n,q = map(int, input().split())
s = input()
cum = [0,0]
for i in range(n-1):
    if s[i+1] == "C" and s[i] == "A":
        cum.append(cum[-1]+1)
    else:
        cum.append(cum[-1])
# print(cum)
for i in range(q):
    l,r = map(int, input().split())
    ans = cum[r] - cum[l-1]

    if cum[l] != cum[l-1]:
        ans -= 1
    print(ans)

Measured memory_bytes: 6096
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>

struct Eng {
  Eng(const double th_, const int x_, const int y_) : th(th_), x(x_), y(y_) {}
  double th;
  int x, y;
};

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

  std::vector<Eng> engs;
  for (int i = 0; i < N; i++) {
    int x, y;
    std::cin >> x >> y;
    engs.push_back(Eng(atan2(y, x), x, y));
  }

  std::sort(engs.begin(), engs.end(),
            [](const Eng &a, const Eng &b) -> bool { return a.th < b.th; });

  double max = 0;
  for (int i = 0; i < N; i++) {
    long xsum = engs[i].x, ysum = engs[i].y;
    double pre = xsum * xsum + ysum * ysum;
    if (pre > max) max = pre;
    for (int j = 1; j < N; j++) {
      int k = i + j < N ? i + j : i + j - N;
      xsum += engs[k].x;
      ysum += engs[k].y;
      double tmp = xsum * xsum + ysum * ysum;
      if (tmp > max) max = tmp;
      pre = tmp;
    }
  }

  printf("%0.12f\n", sqrt(max));

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F(i, l, r) for(int i = (l), _end_ = (int)(r); i <= _end_; ++i)
#define f(i, r, l) for(int i = (r), _end_ = (int)(l); i >= _end_; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define file(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std;

template<typename T>bool chkmax(T &a,T b){return (a<b)?a=b,1:0;}
template<typename T>bool chkmin(T &a,T b){return (a>b)?a=b,1:0;}

inline int read() {
 int x = 0, fh = 1; char ch = getchar();
    for (; !isdigit(ch); ch = getchar() ) if (ch == '-') fh = -1;
    for (; isdigit(ch); ch = getchar() ) x = (x<<1) + (x<<3) + (ch ^ '0');
    return x * fh;
}
int sum[105][105];
int h,w;
int ex,ey;
char s[105][105];
int dp[105][105][105];
int getsum(int lx,int ly,int rx,int ry){
    return sum[rx][ry]-sum[rx][ly-1]-sum[lx-1][ry]+sum[lx-1][ly-1];
}
int main () {
#ifndef ONLINE_JUDGE
//file("agc004e");
#endif
    h=read();
	w=read();
	F(i,1,h){
		scanf("%s",s[i]+1);
	   F(j,1,w){
	     if(s[i][j]=='o')sum[i][j]=1;
		 if(s[i][j]=='E')ex=i,ey=j;
	   }
	}
	F(i,1,h)F(j,1,w)sum[i][j]=sum[i][j]+sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
/*	F(i,1,h){
	   F(j,1,w)cout<<sum[i][j]<<" ";
	   cout<<endl;
	}*/
	Set(dp,-0x3f3f3f3f);
	dp[0][0][0]=0;
	//cout<<ex<<" "<<ey<<endl;
	int ans=0;
	int up,down,lef,rig;
	F(i,0,h){
	   if(ex-i<1)break;
	   F(j,0,h){
	      if(ex+j>h)break;
		  up=max(ex-i,j+1);
          down=min(ex+j,h-i);
		  if(up>down)continue;
          F(k,0,w){
		      if(ey-k<1)break;
			  F(l,0,w){
			   if(ey+l>w)break;
			   lef=max(ey-k,l+1);
			   rig=min(ey+l,w-k);
			   if(lef>rig)continue;
			   chkmax(ans,dp[j][k][l]);
			   if(i+j<h-ex)chkmax(dp[j+1][k][l],dp[j][k][l]+getsum(ex+j+1,lef,ex+j+1,rig));
			    if (k+l<ey-1)chkmax(dp[j][k+1][l],dp[j][k][l]+getsum(up,ey-k-1,down,ey-k-1));
                    if (k+l<w-ey)chkmax(dp[j][k][l+1],dp[j][k][l]+getsum(up,ey+l+1,down,ey+l+1));
                    if(i+j<ex-1)chkmax(dp[j][k][l],dp[j][k][l]+getsum(ex-i-1,lef,ex-i-1,rig));
			   chkmax(ans,dp[j][k][l]);
			  }
		  }
	   }
	}
//	F(i,0,h)F(j,0,w)F(k,0,w)printf("%d %d %d %d\n",i,j,k,dp[i][j][k]);
	printf("%d\n",ans);
    return 0;
}

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

int main()
{
    ios_base::sync_with_stdio(false);
    set<string> s;
    int n;
    string str1, str2;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> str1 >> str2;
        if(str1 == "insert"){
            s.insert(str2);
        } else {
            if(s.count(str2)){
                cout <<"yes" << endl;
            } else {
                cout << "no" << endl;
            }
        }
    }
}

Measured memory_bytes: 27812
#include<stdio.h>


int main ()
{
	int a,b,c,d,e,f;
	scanf("%d %d %d",&a,&b,&c);
	if     (a<=b&&b<=c) d=a,e=b,f=c;
    else if(a<=c&&c<=b) d=a,e=c,f=b;
    else if(b<=a&&a<=c) d=b,e=a,f=c;
    else if(b<=c&&c<=a) d=b,e=c,f=a;
    else if(c<=a&&a<=b) d=c,e=a,f=b;
    else if(c<=b&&b<=a) d=c,e=b,f=a;
    printf("%d %d %d\n",d,e,f);
    return 0;
}


Measured memory_bytes: 2752
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))

t = inpl()
a = t[0]
b = t[1]
c = t[2]
k = t[3]
cnt = 0

if k == a + b + c:
    cnt = a - c

if k >= a + b and k < a + b + c:
    cnt = a - (k - (a + b))

if k >= a and k < a + b:
    cnt = a

if k < a:
    cnt = k

print(cnt)

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

int main(void)
{
    int N, M;
    cin >> N >> M;

    vector<int> p(M,0);
    vector<int> yp(M,0);
    vector<vector<int>> y(N,vector<int>(0,0));

    for (int i = 0; i < M; ++i)
    {
        int tmp_p, tmp_y;
        cin >> tmp_p >> tmp_y;
        --tmp_p;
        p[i] = tmp_p;
        yp[i] = tmp_y;
        y[tmp_p].push_back(tmp_y);
    }

    for (int i = 0; i < N; ++i)
    {
        sort(y[i].begin(), y[i].end());
    }

    for (int i = 0; i < M; ++i)
    {
        int index = lower_bound(y[p[i]].begin(), y[p[i]].end(), yp[i]) - y[p[i]].begin();
        cout << setw(6) << std::setfill('0') << p[i]+1;
        cout << setw(6) << std::setfill('0') << index+1 << endl;   
    }
    



    return 0;
}



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

int main(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    reverse(s.begin(),s.end());
    //cal number of w and e and store and sub pre-proessing
    int W=0,E=0;
    vector<pair<int,int>>v;
    for(int i=0;i<n;i++){
        if(s[i]=='E')E++;
        else W++;
        v.push_back(make_pair(E,W));
    }
    //left same and right opposite
    ll temp,ans=1234567891;
    //took some time but solved in O(n)
    for(int i=0;i<n;i++){
        if(s[i]=='E'){
            if(i==0 || i==n-1){
                temp=v[n-1].second;
            }else{
                temp=v[i-1].first;
                temp+=v[n-1].second-v[i-1].second;
            }
        }else{
            if(i==0 || i==n-1){
                temp=v[n-1].first; //all numbers with east
            }else{
                temp=v[i-1].first;
                temp+=v[n-1].second-v[i].second;
            }
        }
        //cout<<temp<<" ";
        if(temp<ans)ans=temp;
    }
    cout<<ans;
}


Measured memory_bytes: 6904
#include <iostream>
#define BUIL 4
#define FLOORS 3
#define ROOMS 10
using namespace std;

int main()
{
    int count[BUIL][FLOORS][ROOMS] = {};
    int n;

    cin >> n;

    for (int i = 0; i < n; i++) {
        int b, f, r, v;

        cin >> b >> f >> r >> v;
        count[b - 1][f - 1][r - 1] += v;
    }

    for (int i = 0; i < BUIL; i++) {
        for (int j = 0; j < FLOORS; j++) {
            for (int k = 0; k < ROOMS; k++) {
                cout << ' ' << count[i][j][k];
            }
            cout << endl;
        }
        if (i != BUIL - 1)
            cout << "####################" << endl;
    }
}


Measured memory_bytes: 3076
S = input()
ans = 0
max_ans = 0
for i in range(len(S)):
  ans = 0
  for j in range(i, len(S)):
    if S[j] == 'A' or S[j] == 'T' or S[j] == 'G' or S[j] == 'C':
      ans += 1
    else:
      break
  if ans > max_ans:
    max_ans = ans
print(max_ans)

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

int main(void){
    string s; cin >> s;
    int a = 0;
    if(s[2]!=s[3]) {cout << "No" << endl; return 0;}
    if(s[4]!=s[5]) {cout << "No" << endl; return 0;}
    if(a==0) cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=20000005,M=1e9+7;
int fac[N],inv[N],f[5005][5005],n,m;
inline int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans; 
}
inline int P(int x,int y){
	if (x>y)return 1;
	if (!x)return 0;
	return fac[y]*inv[x-1]%M;
}
inline int C(int x,int y){
	if (x<0)return 1;
	if (x<y)return 0;
	return fac[x]*inv[y]%M*inv[x-y]%M;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	fac[0]=1;
	for (int i=1;i<N;i++)fac[i]=fac[i-1]*i%M;
	inv[N-1]=ksm(fac[N-1],M-2);
	for (int i=N-2;i>=0;i--)inv[i]=inv[i+1]*(i+1)%M;
	n-=m;int ans=0;
	for (int i=1;i<=m+1;i++)
		for (int j=0;j<=m;j++)f[i][j]=((!j?0:f[i][j-1])+inv[j]*fac[i-2+n+j])%M;
	for (int i=1;i<=m+1;i++)
		for (int j=0;j<i;j++){
			int s=f[i-j][max(0ll,m-i)];
			if (j&1)(ans+=M-C(i-1,j)*(i-j-1)%M*(i>m?1:fac[m-i])%M*s%M)%=M;
			else (ans+=C(i-1,j)*(i-j-1)%M*(i>m?1:fac[m-i])%M*s)%=M;
		}
	printf("%lld\n",ans);
} 

Measured memory_bytes: 511780
N = int(input())
H = [int(i) for i in input().split()]

ans = 0
count = 0
for i in range(N - 1):
    if H[i] >= H[i + 1]:
        count += 1
    elif count > ans:
        ans = count
        count = 0
    else:
        count = 0
if count > ans:
    ans = count
print(ans)

Measured memory_bytes: 14252
H=int(input())+1
A=[0]+list(map(int,input().split()))
def h(i):
 l=2*i;r=l+1
 g=i
 if l<H and A[g]<A[l]:g=l
 if r<H and A[g]<A[r]:g=r
 if g>i:A[i],A[g]=A[g],A[i];h(g)
for i in range(H//2,0,-1):h(i)
print(' '+' '.join(map(str,A[1:])))


Measured memory_bytes: 65140
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
#include <iomanip>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <numeric>
using namespace std;
using ll = long long;
int main()
{

	ll a = 0, b = 0, c = 0, d = 0, e = 0;
	ll n, m, h, w, X;
	ll k;
	ll insuusyurui[1000] = {};
	ll insuukazu[1000] = {};
	ll memo[4000] = {};
	ll memo2[4000] = {};
	string s;
	cin >> s;
	for (int i = 0; i < 3; i++)
	{

		if (s[i] == '1')
		{
			cout << "9" ;

		}
		else
		{
			cout << "1" ;

		}
	}

	cout  << endl;

	//cout << sum << endl;
	//cout <<  endl;

	return 0;
}

//memcpy(x, visited, sizeof(ll)*n);
//void kansuu(ll num, ll visited[10]) {}
//kansuu(1, zz);
//cout << setprecision(15) << v << endl;

//int temp;
//for (int i = 0; i < n - 1; i++) {
//	for (int j = n - 1; j > i; j--) {
//		if (w[j - 1] < w[j]) {  /* 前の要素の方が大きかったら */
//			temp = w[j];        /* 交換する */
//			w[j] = w[j - 1];
//			w[j - 1] = temp;
//		}
//	}
//}




//
//ll insuusyurui[1000] = {};
//ll insuukazu[1000] = {};
//ll memo[4000] = {};
//ll memo2[4000] = {};
//cin >> n;
//cin >> m;
//a = 2;
//// √n ≧ a ( n ≧ a * a ) の間ループ処理
//while (n >= a * a) {
//	// a で割り切れたら、a は素因数
//	// そして、割られる数を a で割る
//	// a で割り切れなかったら、 a を 1 増加させる
//	if (n % a == 0) {
//		printf("%d * ", a);
//		insuukazu[c]++;
//		n /= a;
//	}
//	else {
//		a++;
//		//if (insuukazu[c] != 0)
//		{
//			c++;
//			//cout << c << endl;
//
//		}
//	}
//}
//printf("%d\n", n);
//for (int i = 0; i < c; i++)
//{
//	//cout << insuukazu[i] << endl;
//}
//
//cout << "Yes" << endl;

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()

def mdiv(n):
    divisors=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
    return divisors
ans=0
for i in range(1,n+1):
    a=mdiv(i)
    if i%2==1 and len(a)==8:
        ans+=1
print(ans)

Measured memory_bytes: 64108
#include<stdio.h>
int main(){
  int B[]={6,7,8,9,5,4,3,2,1,0,1,2,3,4,5,6,7,8,9};
  int f,e,i,j,n;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&f,&e);
    if(f>e){
      for(j=0;B[j]!=f;j++);
      for(;B[j]!=e;j++){
	printf("%d ",B[j]);
      }
    }
    else{
      for(j=f;j!=e;j++){
	printf("%d ",j);
      }
    }
    printf("%d\n",e);
  }
  return 0;
}
	

Measured memory_bytes: 600
#include<iostream>
using namespace std;
int main(){
int a[10000]={0},au[30];
	int i,j,s;
	int c=0,t=0;
	while(cin>>s){
		a[s]++;
		c++;
	}
	int max=0;
	for(i=0;i<c;i++){
		if(max<a[i]){
			max=a[i];
			au[0]=i;
			t=1;
		}
		else if(max==a[i]){
			au[t]=i;
			t++;
		}
	}
	for(i=0;i<t;i++){
		cout<<au[i]<<endl;
	}
	return 0;
}

Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
#define int long long
int gcd(int a, int b)
{
    // Everything divides 0
    if (a == 0)
       return b;
    if (b == 0)
       return a;

    // base case
    if (a == b)
        return a;

    // a is greater
    if (a > b)
        return gcd(a%b, b);
    return gcd(a, b%a);
}
main()
{
 int n,k;
 cin>>n>>k;
 int x=n%k;
 if(x==0)
    cout<<0;
 else
 {
int     last=abs(x-k);
     while(abs(last-k)<last)
        last=abs(last-k);
     cout<<last;
 }
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define _rep(i, n) for (int i = (int)(n - 1); i >= 0; i--)
#define _REP(i, e, s) for (int i = (int)(e - 1); i >= (int)(s); i--)

#define yes cout << "yes" << endl;
#define Yes cout << "Yes" << endl;
#define YES cout << "YES" << endl;

#define no cout << "no" << endl;
#define No cout << "No" << endl;
#define NO cout << "NO" << endl;

#define AC cout << "AC" << endl;
#define WA cout << "WA" << endl;

#define out(s) cout << s << endl;

#define ll long long
#define ull unsigned long long

const unsigned int BIT_FLAG_0 = (1 << 0);  // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1);  // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2);  // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3);  // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4);  // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5);  // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6);  // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7);  // 0000 0000 1000 0000

const double PI = 3.14159265358979323846;

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

#define H_MAX 500
#define W_MAX 500
#define INF 1e9 + 7
const ll mod = 1000000007;

int main() {
    int N, X, T;
    cin >> N >> X >> T;
    if (N % X == 0) {
        cout << N / X * T << endl;
    } else {
        cout << (N / X + 1) * T << endl;
    }
}

Measured memory_bytes: 3604
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();
		while (in.hasNext()) {
			int lenH = in.nextInt();
			int lenW = in.nextInt();

			if (lenH == 0) {
				break;
			}

			String topBottom = repeat('#', lenW);
			sb.append(topBottom).append("\n");
//			if (lenH > 1) {
			String side = "#" + repeat('.', lenW - 2) + "#";
			for (int i = 0, len = lenH - 2; i < len; i++) {
				sb.append(side).append("\n");
			}
			sb.append(topBottom).append("\n");
//			}

			sb.append("\n");
		}
		System.out.print(sb.toString());
	}

	private static String repeat(char c, int len) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < len; i++) {
			sb.append(c);
		}
		return sb.toString();
	}
}

Measured memory_bytes: 18392
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#define  rep(i,a,b)for(int i=a;i<b;++i)
#define  rrep(i,a,b)for(int i=a;i>b;--i)
#define  yesno(flag)if(flag)cout<<"Yes"<<endl; else cout<<"No"<<endl;
using namespace std;
typedef long long ll;
const ll INF=100000000000LL;
typedef pair<int,int>P;
vector<P> v1[100001];
int main() {
	int a,b;
	char c;
	cin>>a>>c>>b;
	if(c=='+')cout<<a+b<<endl;
	else cout<<a-b<<endl;
	return 0;
}


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

int main(){
	int n,a,b;
	cin>>n;
	int t[n+1],x[n+1],y[n+1];
	t[0]=0; x[0]=0; y[0]=0;
	for(int i=1;i<=n;i++){
		cin>>t[i]>>y[i]>>x[i];
	}
	for(int i=1;i<=n;i++){
		a=t[i]-t[i-1];
		b=fabs(x[i]-x[i-1])+fabs(y[i]-y[i-1]);
		if(a>=b){
			if(a%2!=b%2){
				cout<<"No"<<endl;
				return 0;
			}
		}else{
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
	return 0;
}

Measured memory_bytes: 1408
import java.util.Scanner;

class Main {

	public static void main(String[] args) {
		try (Scanner sc = new Scanner(System.in)){
			int target = sc.nextInt();
			int xNum = sc.nextInt();
			int xMoney = sc.nextInt();
			int yNum = sc.nextInt();
			int yMoney = sc.nextInt();
			
			int x = target/xNum;
			if (target%xNum!=0) x++;
			x*=xMoney;
			
			int y = target/yNum;
			if (target%yNum!=0) y++;
			y*=yMoney;
			
			System.out.println(Math.min(x, y));
		}
	}
}


Measured memory_bytes: 26336
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = INF+7;
const ll LINF = 1e18;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define all(v) v.begin(),v.end()
#define MP make_pair
#define pb(n) push_back(n)


int main(){
    int N;
    cin >> N;
    vector<int> p(N);
    int sum = 0;
    rep(i,N) cin >> p[i];
    sort(all(p));
    rep(i,N){
        if(i == N-1) sum += (p[i]/2);
        else sum += p[i];
    }

    cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define ff first
#define pii pair<int, int>
#define vii vector< pair<int,int> >
#define vi vector<int>
#define vvi vector< vector< int> >
#define vs vector<string>
#define ss second
#define pb push_back
#define mp make_pair
#define int long long
#define all(a) a.begin(), a.end()
#define inf (1LL<<61)
#define ull unsigned long long
#define trace1(x)                cout<<#x<<": "<<x<<endl
#define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace4(x, y, z, d)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<" | "<<#d<<": "<<d<<endl
#define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define debug1(x) cerr << #x << ": " << x <<'\n'
#define debug2(x, y) cerr << #x << ": " << x << '\t' << #y << ": " << y <<'\n'
#define debug3(x, y, z) cerr << #x << ": " << x << '\t' << #y << ": " << y << '\t' << #z << ": " << z <<'\n'
using namespace std;
int dx[]={1,0,-1, 0};int dy[]={0,1,0, -1}; //4 Direction
//int dx[]={1,1,0,-1,-1,-1,0,1};int dy[]={0,1,1,1,0,-1,-1,-1};//8 direction
bool compare(const pair<pair<string,int>, int> &a,const pair<pair<string,int>, int> &b)
{
    if(a.ff.ff == b.ff.ff) {
        return (a.ff.ss > b.ff.ss);
    }
    return (a.ff.ff<b.ff.ff);
}
int min(int a, int b){
    if(a<b){
        return a;
    }
    else{
        return b;
    }
}
int max(int a, int b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
}
int poww(int a, int b)
{
    int res = 1;
    for(int i = 1; i<=b; ++i)
        res *= a;

    return res;
}
int findlcm(int arr[], int n) 
{ 
    // Initialize result 
    int ans = arr[0]; 
  
    // ans contains LCM of arr[0], ..arr[i] 
    // after i'th iteration, 
    for (int i = 1; i < n; i++) 
        ans = (((arr[i] * ans)) / 
                (__gcd(arr[i], ans))); 
  
    return ans; 
}
bool prime[100001];
void SieveOfEratosthenes(int n) 
{
    memset(prime, true, sizeof(prime));

    for (int p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<=n; i += p)
                prime[i] = false;
        }
  }
}

//Define mx for maximum range and MOD for large numbers
#define mx 200005
#define MOD 1000000007;
// Declare all the variables and global functions here - 
string s;
int32_t main(){
    IOS;
    cin >> s;
    int mar = -1;
    int cnt = 0;
    int t = 1;
    int c = 0;
    for(int i = 0;i<s.length();i++){
        if(s[i] == 'A' && s[i+1] == 'B' && s[i+2] == 'C'){
            while(s[i+1] == 'B' && s[i+2] == 'C'){
                s[i] = 'B';
                s[i+1] = 'C';
                s[i+2] = 'A'; 
                i = i +2;
                c++;

            }
            cnt += t*c;
            c = 0;
        }
        if(s[i] == 'A' && s[i+1] == 'A'){
            t++;
        }
        else{
            t = 1;
        }

        // trace2(i, cnt);
        // cout << s << endl;
        
    }

    cout << cnt << endl;
}

Measured memory_bytes: 720
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>

using namespace std;

typedef long long ll;

int main() {
	ios::sync_with_stdio(0);
	ll n,a,b;
	cin >> n;
	cin >> a >> b;
	if ((b - a) % 2 == 0) {
		cout << (b - a) / 2ll << "\n";
	}
	else {
		ll ans = (b - a) / 2ll;
		ans += min(n - b + 1, a);
		cout << ans << "\n";
	}
	//system("pause");
	return 0;
}

Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let s: Vec<char> = iterator.next().unwrap().chars().collect();

    let mut r = 0;
    let mut b = 0;
    for i in 0..n {
        if s[i] == 'R' {
            r += 1;
        } else {
            b += 1;
        }
    }

    if r > b {
        "Yes".to_string()
    } else {
        "No".to_string()
    }
}


Measured memory_bytes: 2104
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static class Proc {
        public String name;
        public int time;

        public Proc(String name, int time) {
            this.name = name;
            this.time = time;
        }

        public int run(int quantum) {
            if (time > quantum) {
                time -= quantum;
                return quantum;
            } else {
                quantum = time;
                time = 0;
                return quantum;
            }
        }

        public boolean isFinished() {
            return time == 0;
        }
    }

    static class Queue {
        Proc[] elements;
        int head = 0;
        int tail = 0;
        int count = 0;
        
        public Queue(int max) {
            elements = new Proc[max];
            head = 0;
            tail = 0;
            count = 0;
        }

        public boolean enqueue(Proc t) {
            if (isFull()) {
                return false;
            }
            elements[head++] = t;
            count++;
            if (head >= elements.length) {
                head = 0;
            }
            return true;
        }
        
        public Proc dequeue() {
            Proc elem = null;
            if (!isEmpty()) {
                elem = elements[tail++];
                count--;
                if (tail >= elements.length) {
                    tail = 0;
                }
            }

            return elem;
        }

        public boolean isEmpty() {
            return count == 0;
        }
        
        public boolean isFull() {
            return count == elements.length;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        String[] nAndq = r.readLine().split(" ");
        int n = Integer.parseInt(nAndq[0]);
        int q = Integer.parseInt(nAndq[1]);
        Queue queue = new Queue(n);
        
        for (int i = 0;i < n;i++) {
            String[] elems = r.readLine().split(" ");
            if (!queue.enqueue(new Proc(elems[0], Integer.parseInt(elems[1])))) {
                System.err.println("Failed enqueue.");
            }
        }

        int clock = 0;
        while (!queue.isEmpty()) {
            Proc p = queue.dequeue();
            clock += p.run(q);
            if (p.isFinished()) {
                System.out.println(p.name + " " + clock);
                if (queue.isEmpty()) {
                    break;
                }
            } else {
                queue.enqueue(p);
            }
        }
    }
}

Measured memory_bytes: 60480
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const string s1="dream";
const string s2="dreamer";
const string s3="erase";
const string s4="eraser";
string str;
int main()
{
    /*cout<<s1.substr(0,2)<<endl;
    cout<<s1<<endl;*/
    cin>>str;
    for(; str!=""; )
    {
        int i=str.length();
        if(str.length()==0) break;
        int flag=0;
        string temp;
        for(int j=5; j<=7; j++)
        {
            if(i<j)
                continue;
            else
            {
                temp=str.substr(i-j);
                //cout<<i-j<<endl;
                if(temp==s1|temp==s2||temp==s3||temp==s4)
                {
                    flag=1;
                    str=str.substr(0,i-j);
                    //cout<<str<<endl;
                    break;
                }
            }
        }
        if(flag==0)
        {
            cout<<"NO"<<endl;return 0;
        }
    }
    cout<<"YES"<<endl;
}


Measured memory_bytes: 596
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

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

    int ret = 0;
    for(int i=0; i<n; ++i){
        long long a;
        cin >> a;
        a = 2 * a + 1;

        bool ng = true;
        for(long long j=2; j*j<=a; ++j){
            if(a % j == 0){
                ng = false;
                break;
            }
        }

        if(ng)
            ++ ret;
    }

    cout << ret << endl;

    return 0;
}

Measured memory_bytes: 1168
#include<stdio.h>
int main()
{
  int n,sum=0,nn=0;
  scanf("%d",&n);
  nn=n;
  while(0<n){
  	sum=sum+n%10;
    n=n/10;
  }
  if(nn%sum==0){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
  return 0;
}

Measured memory_bytes: 1652
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
const ll LINF=0x1fffffffffffffff;
const int INF=0x3fffffff;
const int MOD=1000000007;
#define VAR(type,...) type __VA_ARGS__;in(__VA_ARGS__)
#define VEC(type,name,size) vector<type> name(size);each(x, name)in(x)
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define rrep(i,a,b) for(int i=(a-1);i>=(b);--i)
#define each(x,v) for(auto &x:(v))
#define all(x) (x).begin(),(x).end()
#define print(...) out(__VA_ARGS__);cout<<endl
void in(){} template<class T,class... U> void in(T &t,U &...u){cin>>t;in(u...);}
void out(){} template<class T,class... U> void out(T t,U ...u){cout<<t<<" ";out(u...);}
void solve();
int main(){cin.tie(0);ios::sync_with_stdio(0);solve();}

void solve() {
  VAR(int, N, M);
  priority_queue<ll> pq;
  rep(i, 0, N) {
    VAR(ll, Ai);
    pq.push(Ai);
  }
  while (M) {
    ll a = pq.top(); pq.pop();
    pq.push(a / 2);
    M--;
  }
  ll ans = 0;
  while (!pq.empty()) {
    ans += pq.top(); pq.pop();
  }
  print(ans);
}


Measured memory_bytes: 1400
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

func ceil(a, b int) int {
	if a%b == 0 {
		return a / b
	} else {
		return a/b + 1
	}
}

// Sort
type RuneSlice []rune

func (a RuneSlice) Len() int           { return len(a) }
func (a RuneSlice) Less(i, j int) bool { return a[i] < a[j] }
func (a RuneSlice) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

// Main
func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	N := sc.nextInt()
	ans := 0
	for i := 1; i <= N; i++ {
		if i%10 == 0 {
			continue
		}
		h, t := f(i)
		if h == t {
			ans++
		}
		k := 10
		target := t*k + h
		for target <= N {
			power := len(strconv.Itoa(target)) - 2
			keta := 1
			for keta <= power {
				target += 9 * pow(10, keta)
				keta++
			}
			if target <= N {
				ans += pow(10, power)
			} else {
				num := N
				for num%10 != h {
					num--
				}
				ans += count(num)
			}
			k *= 10
			target = t*k + h
		}
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}

func count(n int) int {
	str := strconv.Itoa(n)
	mid := str[1 : len(str)-1]
	res, _ := strconv.Atoi(mid)
	return res + 1
}

func f(n int) (int, int) {
	if n < 10 {
		return n, n
	}
	tail := n % 10
	var head int
	n /= 10
	for {
		rest := n % 10
		n /= 10
		if n == 0 {
			head = rest
			break
		}
	}
	return head, tail
}


Measured memory_bytes: 3840
#include <stdio.h>

int main()
{
 int A,B,C,D;
 int judge;	//勝利判定
 int count;	//ターンカウント

 scanf("%d %d %d %d",&A, &B, &C, &D);

 judge = 0;
 count = 2;
 while(judge == 0){

  if(count % 2 == 0)	//高橋の攻撃
  {
   C = C - B;
   if(C <= 0)
    judge = 1;
  }

  else			//青木の攻撃
  {
   A = A - D;
   if(A <= 0)
    judge = 2;
  }
  count += 1;
 }

 if(judge == 1)		//高橋の勝利
  printf("Yes\n");
 else if(judge == 2)	//青木の勝利
  printf("No\n");

 return 0;
}

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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
std::string S;

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

    std::cin >> N >> S;
    
    ll res = 1ll * std::count(S.begin(), S.end(), 'R') * std::count(S.begin(), S.end(), 'G') * std::count(S.begin(), S.end(), 'B');

    for(int i=0;i<N;++i){
        for(int l=1;i+l*2<N;++l){
            int j = i + l, k = j + l;

            if(S[i] != S[j] && S[j] != S[k] && S[k] != S[i]){
                res -= 1;
            }
        }
    }

    std::cout << res << std::endl;
}


Measured memory_bytes: 3656
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

n,k = map(int,input().split())

ans = 0

if k >= n-1:
    print(cmb(2*n-1,n,p))
else:

    for i in range(k+1):
        ###i:0人の部屋の数
        x = cmb(n,i,p)###0人の部屋の選び方
        y = cmb(n-1,i,p)
            ###0人でないn-i個の部屋にn人が入る時の人数の組み合わせ
            ###各部屋に1人以上入るので, それを上回る分についてのみ考える
            ###すなわち, n-(n-i)=i人についての組み合わせを考える
            ###人間i人, 仕切りn-i-1個
        ans += (x*y)%p
        ans %= p

    print(ans)




Measured memory_bytes: 122068
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define MAX_N 100000
#define MAX_M 100000
const int MAX = 100100;
const int MOD = 1000000007;
#define vec vector<int>
#define vecll vector<ll>
#define vecllvec vector<vector<ll>>
#define vecb vector<bool>
#define vecBvec vector<vector<bool>>
#define vecst vector<string>
#define vecch vector<char>
#define vecd vector<double>
#define vecvec vector<vector<int>>
#define vecDvec vector<vector<double>>
#define vecHvec vector<vector<char>>
#define all(x) (x).begin(),(x).end()
const long long INF = 1LL<<60;
#define PI 3.141592653589793
// cout << setprecision(15) << std::fixed;

// もしかしてACですかぁ～～？！　Yse!! Yse!! Yse!!

int main() {
  int h,w,k,c=1;
  cin>>h>>w>>k;
  vecvec cake(h,vec(w,0));
  bool che[h][w];
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      char a;
      cin>>a;
      if(a=='#'){
        cake[i][j]=c;
        che[i][j]=true;
        c++;
      }
      else{
        che[i][j]=false;
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(che[i][j]){
        for(int l=j-1;l>=0;l--){
          if(che[i][l]) break;
          cake[i][l]=cake[i][j];
        }
        for(int r=j+1;r<w;r++){
          if(che[i][r]) break;
          cake[i][r]=cake[i][j];
        }
      }
    }
  }
  for(int i=0;i<h;i++){
    if(cake[i][0]==0){
      if(i!=0){
        for(int u=i-1;u>=0;u--){
          if(cake[u][0]!=0){
            cake[i]=cake[u];
            break;
          }
        }
      }
      else{
        for(int d=i+1;d<h;d++){
          if(cake[d][0]!=0){
            cake[i]=cake[d];
            break;
          }
        }
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      cout<<cake[i][j]<<" ";
    }
    cout<<endl;
  }
}


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

int main() {
 bool ans=false;
   int K; 
     int A;
     int B;
   cin>>K>>A>>B; 
   for (int i = 0; i < 1000/K; i++) {
     if(K*(i+1)>=A && K*(i+1)<=B){
       ans=true;
       break;
     }
   }
   if (ans) {
    cout << "OK" << endl;
  }
  else {
    cout << "NG" << endl;
  }
   
}


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

//#define int int64_t

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)

#define all(c) begin(c), end(c)
#define maxup(ans, x) (ans = (ans < x ? x : ans))
#define minup(ans, x) (ans = (ans > x ? x : ans))

#define breakif(cond) if(cond) break; else

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

using VV = vector<vector<int>>;
using V = vector<int>;
using P = pair<int, int>;
using IP = pair<int, P>;

const int INF = 1 << 29;

signed main() {
	int n;
	while (cin >> n && n) {
		int m; cin >> m;
		V cs(m); input(cs);
		V xs(n); input(xs);
		VV dp(n + 1, V(256, INF));

		dp[0][128] = 0;
		rep(i, n) {
			int x = xs[i];
			rep(j, 256) {
				rep(k, m) {
					int c = cs[k];
					int val = max(0, min(j + c, 255));
					minup(dp[i + 1][val], dp[i][j] + pow(x - val, 2));
				}
			}
		}
		cout << *min_element(all(dp[n])) << endl;
	}
}

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

using namespace std;

int main() {
    ios_base :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, x;
    cin >> n;
    multiset <int> s;
    for (int i = 1; i <= n; i++) {
        cin >> x; s.insert(x);
    }
    int res = 0;
    while (s.size() > 0) {
        auto it = --s.end();
        s.erase(it);
        int x = *it;
        int cur = 1;
        while (cur <= x) {
            cur *= 2;
        }
        if (s.count(cur - x) > 0) {
            s.erase(s.find(cur - x));
            res++;
        }
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int inf = 1e9;
#define rep(i, n) for (int i = 0; i < n; i++)
using Graph = vector<vector<int>>;
using pint = pair<int, int>;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int dxx[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dyy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

int n;
const int MAX = 100;
int g[MAX][MAX];

int prim() {
    int u, minv;
    int d[MAX], p[MAX];
    bool seen[MAX] = {};
    rep (i, n) {
        d[i] = inf;
        p[i] = -1;
    }
    d[0] = 0;
    while (1) {
        minv = inf;
        u = -1;
        rep (v, n) {
            if (!seen[v] && minv > d[v]) {
                u = v;
                minv = d[v];
            }
        }
        if (u == -1) break;
        seen[u] = 1;
        rep (i, n) {
            if (!seen[i] && g[u][i] != -1) {
                if (d[i] > g[u][i]) {
                    d[i] = g[u][i];
                    p[i] = u;
                }
            }
        }
    }
    int sum = 0;
    rep (i, n) sum += d[i];
    // rep (i, n) cout << d[i] << " ";
    return sum;
}

int main() {
    cin >> n;
    rep (i, n) rep (j, n) cin >> g[i][j];
    // cout << prim << "\n";
    cout << prim() << "\n";
}



Measured memory_bytes: 3056
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,mod,C[3030][3030],S[3030][3030],pom[3030],po[3030],ans;
int main()
{
	scanf("%d %d",&n,&mod);
	for(int i=0;i<=n;++i)
	{
		S[i][0]=1;
		for(int j=1;j<=n;++j)S[i][j]=(S[i-1][j-1]+1ll*S[i-1][j]*(j+1))%mod;
	}
	for(int i=0;i<=n;++i)
	{
		C[i][0]=1;
		for(int j=1;j<=i;++j)(C[i][j]=C[i-1][j-1]+C[i-1][j])>=mod?C[i][j]-=mod:0;
	}
	pom[0]=2,po[0]=1;
	for(int i=1;i<=n;++i)pom[i]=1ll*pom[i-1]*pom[i-1]%mod,po[i]=(po[i-1]<<1)%mod;
	for(int i=0;i<=n;++i)
	{
		int res=0,w=1;
		for(int j=0;j<=n;++j)res=(res+1ll*S[i][j]*pom[n-i]%mod*w)%mod,w=1ll*w*po[n-i]%mod;
		if(i&1)ans=(ans+1ll*(mod-res)*C[n][i])%mod;
		else ans=(ans+1ll*res*C[n][i])%mod;
	}
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 71808
n = int(input())

r = [0] * n
c = [0] * n

for i in range(n):
    r[i], c[i] = map(int, input().split())

dp = [[float("inf")] * n for _ in range(n)]

for i in range(n):
    dp[i][i] = 0

for gap in range(1, n):
    for s in range(n):
        e = s + gap
        if e >= n:
            continue
        for k in range(s, e):
            dp[s][e] = min(dp[s][e], dp[s][k] + dp[k + 1][e] + r[s] * c[k] * c[e])

print(dp[0][n - 1])



Measured memory_bytes: 5668