akhauriyash/Code-Regression huggingface dataset:
//  0570.cpp
//  12/03/19.

#if 1

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <cctype>
#include <sstream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <complex>
#include <fstream>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T> T RoundOff(T a){ return int(a+.5-(a<0)); }
template<class T, class C> void chmax(T& a, C b){ if(a < b) a = b; }
template<class T, class C> void chmin(T& a, C b){ if(b < a) a = b; }
template<class T, class C> pair<T, C> mp(T a, C b){ return make_pair(a, b); }

const int MOD = 10000;
int memo[501][10][2][2][501];
string A, B;
int M;


// x*10^nをvで割った時の余り
int calc_rest(int x, int n, int v)
{
	for(int i = 0; i < n; i++)
	{
		x -= (x / v) * v;
		x *= 10;
	}
	
	return x / 10;
}

// 数値列をディクリメントする
string dec(string S)
{
	for(int i = S.size() - 1; 0 <= i; i--)
	{
		if(S[i] != '0')
		{
			S[i]--;
			if(S[i] == '0' && i == 0 && 1 < S.size()) S = S.substr(1);
			return S;
		}
		else S[i] = '9';
	}
	
	return S;
}

// S=対象の文字列, pnt=着目している文字の場所, prv=直前の文字, ul=数字は増えるか, sp=既に最大の数より小さいことが決まっているか, rest=累積の余り, zero=最初であり0が禁止されているか
int rec(string &S, int pnt, int prv, bool inc, bool sp, int rest, bool zero)
{
	if(pnt == S.size())	return rest == 0;
	
	if(!zero && memo[pnt][prv][inc][sp][rest] != -1) return memo[pnt][prv][inc][sp][rest];
	
	int dig = S.size() - pnt;
	ll res = 0;
	
	if(inc)
	{
		int lim = (sp ? 10 : S[pnt] - '0' + 1);
		for(int i = prv + 1; i < lim; i++)
		{
			res += rec(S, pnt + 1, i, false, sp || i < S[pnt] - '0', (rest * 10 + i) % M, false);
			res %= MOD;
		}
	}
	else
	{
		for(int i = min(prv - 1, (sp ? prv - 1 : S[pnt] - '0')); i >= zero; i--)
		{
			res += rec(S, pnt + 1, i, true, sp || i < S[pnt] - '0', (rest * 10 + i) % M, false);
			res %= MOD;
		}
	}
	
	return memo[pnt][prv][inc][sp][rest] = res;
}

// S以下のZigZagNumberを数える
int count(string &S)
{
	if(S.size() == 1) return (S[0] - '0') / M;
	
	memset(memo, -1, sizeof memo);
	
	ll res = 9 / M;

	for(int i = 1; i < S.size(); i++)
	{
		int inc = rec(S, S.size() - i - 1, 0, true, i != S.size() - 1, 0, false);
		int fal = rec(S, S.size() - i - 1, (i == S.size() - 1 ? S[0] - '0' + 1 : 10), false, i != S.size() - 1, 0, true);
		
		res += inc + fal;
		res %= MOD;
	}
	
	return res;
}


int solve()
{
	A = dec(A);
	return (count(B) - count(A) + MOD) % MOD;
}


int main()
{
	cin >> A >> B >> M;
	cout << solve() << endl;
}

#endif

Measured memory_bytes: 39000
n=int(input())
s=input()
cnt1=[0]*n
cnt2=[0]*n

if s[0]=="#": cnt1[0]=1
if s[n-1]==".": cnt2[n-1]=1

for i in range(1,n):
    cnt1[i]=cnt1[i-1]
    if s[i]=="#": cnt1[i]+=1

for i in range(n-2,-1,-1):
    cnt2[i]=cnt2[i+1]
    if s[i]==".": cnt2[i]+=1

ans=10**18
for i in range(n-1):
    ans=min(ans,cnt1[i]+cnt2[i+1])
ans=min(ans,cnt1[n-1])
ans=min(ans,cnt2[0])
print(ans)

Measured memory_bytes: 12804
#include<iostream>
#include<cstdio>
#include<cstring>
//#include<vector>
#include<algorithm>


#ifdef L_JUDGE
#pragma warning(disable:4996)
#endif

using namespace std;
const int MAXN=1005;

int A[6][6];


int main(){
	#ifdef L_JUDGE
		freopen("in.txt","r",stdin);
//		freopen("out.txt","w",stdout);
	#endif
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                scanf("%d",A[i]+j);
            }
        }

        bool flag=true;
        for(int ri=1;ri<3;ri++){
            bool p0=(A[ri][0]-A[ri-1][0]==A[ri][1]-A[ri-1][1]);
            bool p1=(A[ri][2]-A[ri-1][2]==A[ri][1]-A[ri-1][1]);
            bool p2=(A[0][ri]-A[0][ri-1]==A[1][ri]-A[1][ri-1]);
            bool p3=(A[2][ri]-A[2][ri-1]==A[1][ri]-A[1][ri-1]);
            flag=p0&&p1&&p2&&p3;
        }
        if(flag)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;

	#ifdef L_JUDGE
		fclose(stdin);
		fclose(stdout);
//		system("out.txt");
	#endif

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define REP(i,a) for (int i = 0;i < (a);++i)
#define FOR(i,a,b) for (int i = (a);i < (b); ++i)
#define FORR(i,a,b) for (int i = (a);i >= (b); --i)
#define ALL(obj) (obj).begin,(obj).end()
#define SORT(list) sort(ALL((list)));
using namespace std;
using ll = long long;
int main(){
    int N;
    int d[110];
    cin >> N;
    REP(i,N)cin >> d[i];

    set<int> values;

    REP(i,N)values.insert(d[i]);
    cout << values.size() << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
typedef long long int ll;
#define f(i, n) for(int i = 0; i < n; ++i)
#define pb push_back

void input(){
    ll n; cin >> n;
    vector<ll>a(n);
    f(i, n) cin >> a[i];
    vector<ll>ans(n, 0);
    for(ll i = n; i >= 1; --i){
       ll cnt = 0;
        for(ll j = i; j <= n; j += i){
            cnt += ans[j - 1];
        }
        if(cnt % 2 != a[i - 1]){
            ans[i - 1] = 1;
        }
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << endl;
    f(i, n)if(ans[i] == 1)cout << i + 1 << " ";cout << endl;
}
int main()
{
 input();
 return 0;
}


Measured memory_bytes: 3968
#include <stdio.h>

void update_BIT(int N, long long BIT[], int i, long long k)
{
	while (i <= N) {
		if (k > BIT[i]) BIT[i] = k;
		i += (i & -i);
	}
}

long long max_BIT(long long BIT[], int r)
{
	long long max = 0;
	while (r > 0) {
		if (BIT[r] > max) max = BIT[r];
		r -= (r & -r);
	}
	return max;
}

int main()
{
	int i, N, h[200001], a[200001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(h[i]));
	for (i = 1; i <= N; i++) scanf("%d", &(a[i]));
	
	long long BIT[200001] = {};
	for (i = 1; i <= N; i++) update_BIT(N, BIT, h[i], max_BIT(BIT, h[i]) + a[i]);
	printf("%lld\n", max_BIT(BIT, N));
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 4856
/* *>>>>>Anshit_Bhardwaj<<<<<* */
#include <bits/stdc++.h>
#define ll long long
#define f(i, x, n) for(int i = x; i < n; i++)
#define dbg(x) cout << x << endl
#define dbg2(x, y) cout << x << ' ' << y << endl
#define dbg3(x, y, z) cout << x << ' ' << y << ' ' << z << endl
#define mod 1000000007
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int l, r, d;
    cin >> l >> r >> d;
    cout << r/d - (l-1) / d << endl;
}

Measured memory_bytes: 3648
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n,m=map(int,input().split())

A=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1 ; b-=1
    A[a].append(b)
    A[b].append(a)

flag=[-1]*n
flag[0]=0

queue=deque([ [0,i] for i in A[0] ])
now=0
while queue:
    now,to=queue.pop()
    # print("now to",now,to)
    if flag[to]==-1:
        flag[to]=now
        for i in A[to]:
            queue.appendleft([to,i])

# print(flag)
if -1 in flag:
    print("No");exit()
print("Yes")
for i in range(1,n):
    print(flag[i]+1)

        

Measured memory_bytes: 57788
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int hsh[n+1];
    memset(hsh,0,sizeof(hsh));
    for(int i=0;i<n-1;i++)
    {
        int a;
        cin>>a;
        hsh[a]++;
    }
    for(int i=1;i<=n;i++)
        cout<<hsh[i]<<" ";
    return 0;
}


Measured memory_bytes: 4364
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
vector<int>atu;
int scan(void){int h,m;cin>>h>>m;atu.pub(h*60+m);return h*60+m;}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int W,H,i,j;cin>>W>>H;
	vector<int>sai(W);
	int e=0;
	for(j=0;j<W;j++){cin>>sai[j];e+=sai[j];}
	if(abs(e-(W-e))>1){cout<<"no"<<endl;return 0;}
	int a=1,b=0;
	for(i=1;i<H;i++){
		int s;cin>>s;
		if(sai[0]==s){s=0;}else{s=1;}
		for(j=1;j<W;j++){
			int c;cin>>c;
			if((c+s)%2!=sai[j]){cout<<"no"<<endl;return 0;}
		}
		if(s==0){a++;}else{b++;}
	}
	if(abs(a-b)<=1){cout<<"yes"<<endl;}
	else{cout<<"no"<<endl;}
	return 0;
}



Measured memory_bytes: 3180
#!/usr/bin/env python3
import sys
import math


def solve(A: int, B: int):
    for i in range(10000):
        per8 = math.floor(i * 0.08)
        per10 = math.floor(i * 0.10)
        if per8 == A and per10 == B:
            print(i)
            exit()

    print(-1)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    solve(A, B)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
N = int(input())
p = tuple(map(int, input().split()))
a = list(p)
b = list(p)

c = 0
for i in range(N):
    if i+1 == a[i] and i == N-1:
        c += 1
    elif i+1 == a[i]:
        a[i], a[i+1] = a[i+1], a[i]
        c += 1
cc = 0        
for i in range(N)[::-1]:
    if i+1 == b[i] and i == 0:
        cc += 1
    elif i+1 == b[i]:
        b[i], b[i-1] = b[i-1], b[i]
        cc += 1
        
print(min(c,cc))

Measured memory_bytes: 14132
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define FORq(i, m, n) for(int i = m;i <= n;i++)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef long long ll;
//////////////////////////////////////////////////////
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false;

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            
            return false;
        }
    }
    return true;
}

int main(){
	int N; SCD(N);
	vector<int> ans;
	int p = 1;
	int n = 0;
	while(n < N){
		p++;
		if (!IsPrime(p)) continue;
		if ((p % 5) != 1) continue;
		
		ans.PB(p);
		n++;
		
	}
	
	REP(i,N-1){
		printf("%d ",ans[i]);
	}
	
	printf("%d\n",ans[N-1]);
	
	
	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!
N,C=map(int,input().split())

log=[[0]*C for i in range(10**5)]


for _ in range(N):
    s,t,c=map(int,input().split())
    log[s-1][c-1]+=1
    log[t-1][c-1]-=1

ans=0
temp=0
for i in range(10**5):
    plus=log[i].count(1)
    temp+=plus
    ans=max(ans,temp)
    minus=log[i].count(-1)
    temp-=minus
#print(log[:15])
print(ans)



Measured memory_bytes: 37108
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
using namespace std;
using ll = long long;
using ld = long double;
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N,K;
  cin >> N >> K;
  vector<bool> ans(N,false);
  for(int i=0;i<K;i++){
    int d;
    cin >> d;
    for(int j=0;j<d;j++){
      int a;
      cin >> a;
      a--;
      ans.at(a)=true;
    }
  }

  int cnt=0;
  for(int i=0;i<N;i++)  if(!ans.at(i))  cnt++;
  cout << cnt << endl;

  return 0;
}

Measured memory_bytes: 3656
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
#define int long long
using namespace std;

template <typename X, typename T>
auto vectors(X x, T a) {
	return vector<T>(x, a);
}

template <typename X, typename Y, typename Z, typename... Zs>
auto vectors(X x, Y y, Z z, Zs... zs) {
	auto cont = vectors(y, z, zs...);
	return vector<decltype(cont)>(x, cont);
}

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

signed main(){
	int a, b;
	cin >> a >> b;

	int ans = 0;
	if(a % 2 == 1) ans ^= a;
	if(b % 2 == 0) ans ^= b;
	ans ^= ((b - a) / 2 + (a % 2 == 0 and b % 2 == 1)) % 2;

	cout << ans << endl;
}


Measured memory_bytes: 256
a = list(input())
b = list(input())
c = list(input())

now = a.pop(0)
while True:
    if now == "a":
        if a == []:
            print("A")
            exit()
        now = a.pop(0)

    if now == "b":
        if b == []:
            print("B")
            exit()
        now = b.pop(0)

    if now == "c":
        if c == []:
            print("C")
            exit()
        now = c.pop(0)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define push_back pb
void test(){
	ll x;
	cin>>x;
	cout<<((x == 0)?1:0)<<"\n";
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//~ cin>>t;
	while(t--){
		test();
	}
}


Measured memory_bytes: 3644
A,B,M=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
l=[list(map(int,input().split())) for _ in range(M)]

arr=[]
arr.append(min(a)+min(b))

for x in l:
  arr.append(a[x[0]-1]+b[x[1]-1]-x[2])
print(min(arr))

Measured memory_bytes: 86076
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000






int main() {
	char a[N];
	f(i, N)a[i] = 0;
	int n, k;
	long long x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%s", a);
	k = strlen(a);
	x = 0;
	y = 0;
	z = 0;
	s = 1;
	f(i, k) {
		x = (long long)(a[i] - '0');
		ans = ans * 10;
		x = x * s;
		if(i>1)y = y * 2;
		y += x;
		if(i>0)ans += x;
		ans += y;
		if(i>0)s = s * 2;
}


	printf("%lld\n", ans);


	return 0;
}

Measured memory_bytes: 384
#include<iostream>
#include<string>
#include<queue>
#include<vector>
using namespace std;
const long long INF=4000000000000000000LL;
typedef pair<long long,int> P;
int main(){
	long long ans=1;
	int N,K;
	int BX[55],BY[55],nx,ny;
	cin>>N>>K;
	for(int i=0;i<N;++i){
		ans=min(ans*2,ans+K);
	}
	cout<<ans<<endl;
	return 0;
}


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

map<int, bool> have;

int main()
{
    int n;
    cin>>n;
    int k;
    for(int i=0;i<n;i++) 
    {
        cin>>k;
        if(have[k]) have.erase(k);
        else have[k] = true;
    }
    cout<<have.size()<<endl;
    return 0;
}

Measured memory_bytes: 4864
#include<bits/stdc++.h>
#define rep(i,n)for(int i=0;i<n;++i)
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<int, int>P;
//max=({});
//条件式が真ならwhileの中身を回し続ける
//printf("%d\n", ans);

//pairの入力
//vector<pair<ll, ll>>work(n);
//rep(i, n) {
//	ll a, b;
//	cin >> a >> b;
//	work[i] = make_pair(a, b);
//}

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

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

//素因数分解
vector<pair<ll, int>>factorize(ll n) {
	vector<pair<ll, int>>res;
	for (ll i = 2;i * i <= n;++i) {
		if (n % i)continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1)res.emplace_back(n, 1);
	return res;
}

int dp[1010][1010];
int bingo[3][3];
bool flag[3][3];

ll n;
ll ans = 0;

void dfs(ll x, int a, int b, int c) {
	if (x > n)return;
	if (a && b && c)ans++;
	dfs(10 * x + 3, 1, b, c);
	dfs(10 * x + 5, a, 1, c);
	dfs(10 * x + 7, a, b, 1);
}

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


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

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int a[200000];
  cin>>n;
  rep(i,n){
    cin>>a[i];
  }
  int mini=a[0];
  int cnt=0;
  rep(i,n){
    if(mini>=a[i]){
      mini=a[i];
      cnt++;
    }
  }
  cout<<cnt<<endl;
   return 0;
}


Measured memory_bytes: 1024
#pragma region Template
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
#include <string>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

#define EPS 1e-14
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define REP(i,n) FOR(i, 0, n)
#define PI 2*acos(0.0)
#define ALL(a) (a).begin(),(a).end()
#define DEBUG(x) cout<<#x <<": "<< x << "\n"
#define DEBUG_ARR(a) REP(i, size(a)){ cout << #a << "[" << i << "]: " << a[i] << "\n"; }
const int VX[] = { 0, 1, 0, -1 };
const int VY[] = { 1, 0, -1, 0 };
const long MOD = 1000000007;

#pragma endregion

bool check(string& s, string t)
{
	if (s.length() < t.length())
	{
		return false;
	}

	if (s.substr(s.length() - t.length(), t.length()) == t)
	{
		s = s.substr(0, s.length() - t.length());
		return true;
	}

	return false;
}

int main()
{
	//	--- I/O 高速化 ---
	cin.tie(0);
	ios::sync_with_stdio(false);
	// --- ここまで ---

	string S;
	cin >> S;

	string T[] = { "dream", "dreamer", "erase", "eraser" };

	bool found = false;
	while (S.length() != 0)
	{
		for (int i = 0; i < 4; i++)
		{
			found = check(S, T[i]);
			if (found) break;
		}
		if (!found)
		{
			cout << "NO\n";
			return 0;
		}
	}

	cout << "YES\n";

	return 0;
}



Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define INFI 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3f
#define MMST(x,num) memset(x,num,sizeof(x))
#define prln(x) cout<<#x<<"="<<x<<endl;
#define PB(x) push_back(x)
#define LINK(x,y) G[x].PB(y),G[y].PB(x)
#define R freopen("at.in", "r", stdin);
///////////////////////////
const int N = 5 +  1e2;
int  c[N][N],f,dif,a,b;
int n, ans;
int main() {
    
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b;
    swap(a,b);
    if(a == b) {
        cout << "66 99" << endl;
        a--;
        for(int i = 2; i <= 33; i += 2) {
            for(int j = 2; j <= 99; j+=2) {
                if(a) {a--; c[i][j] = 1;}
            }
        }
        for(int i = 1; i <= 33; i ++) {
            for(int j = 1; j <= 99; j++) {
                if(c[i][j])cout << ".";
                else cout << "#";
            }
            cout << endl;
        }
        for(int i = 1; i <= 33; i ++) {
            for(int j = 1; j <= 99; j++) {
                if(!c[i][j])cout << ".";
                else cout << "#";
            }
            cout << endl;
        }
        return 0;

    }
    if(a > b)f = 1;
    dif = abs(a - b) +1;
    if(min(a, b) == 1) {
        cout << "33 99" << endl;
        for(int i = 2; i <= 33; i += 2) {
            for(int j = 2; j <= 99; j+=2) {
                if(dif) {dif--; c[i][j] = 1;}
            }
        }
        for(int i = 1; i <= 33; i ++) {
            for(int j = 1; j <= 99; j++) {
                if(c[i][j]^f)cout << ".";
                else cout << "#";
            }
            cout << endl;
        }
    }
    else
    {
       int  mi=min(a,b)-2;
        cout<<"99 99"<<endl;
        for(int i = 2; i <= 33; i += 2) {
            for(int j = 2; j <= 99; j+=2) {
                if(dif) {dif--; c[i][j] = 1;}
            }
        }
        for(int i = 1; i <= 33; i ++) {
            for(int j = 1; j <= 99; j++) {
                if(c[i][j]^f)cout << ".";
                else cout << "#";
            }
            cout << endl;
        }
        MMST(c,0);
    for(int i = 2; i <= 33; i += 2) {
        for(int j = 2; j <= 99; j+=2) {
            if(mi) {mi--; c[i][j] = 1;}
        }
    }
    for(int i = 1; i <= 33; i ++) {
            for(int j = 1; j <= 99; j++) {
                if((!c[i][j])^f)cout << ".";
                else cout << "#";
            }
            cout << endl;
        }
    for(int i = 1; i <= 33; i ++) {
            for(int j = 1; j <= 99; j++) {
                if(c[i][j]^f)cout << ".";
                else cout << "#";
            }
            cout << endl;
        }

    }





    return 0;
}


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


namespace AtC
{
    class Program
    {
        static void Main(string[] args)
        {
            var N = ReadInt();
            var S = ReadString();

            var counts = new int['z'      - 'a' + 1];
            foreach (var s in S) counts[s - 'a']++;
            for (var i = 0; i < counts.Length; i++) counts[i]++;

            long mod = 1000000000l + 7;

            long result = 1;
            counts.ForEach(val =>
            {
                result *= val;
                result %= mod;
            });

            Out((result + mod - 1) % mod);
        }

        static int[] ReadIntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }

        static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }

        static string ReadString()
        {
            return Console.ReadLine();
        }

        static void Out(object o)
        {
            Console.WriteLine(o);
        }
    }

    static class EnumerableExtension
    {
        public delegate void Function<in T>(T val);

        public static void ForEach<T>(this IEnumerable<T> enumerable, Function<T> function)
        {
            foreach (var x in enumerable)
            {
                function(x);
            }
        }
    }
}

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

int main(void) {
    int N, M, input, tmpSum;
    vector< vector<int> > matrix;
    vector<int> vect;

    cin >> N >> M;
    for(int i=0; i < N; i++) {
        vector<int> tmpVect;
        for(int j=0; j < M; j++) {
            cin >> input;
            tmpVect.push_back(input);
        }
        matrix.push_back(tmpVect);
    }

    for(int i=0; i < M; i++) {
        cin >> input;
        vect.push_back(input);
    }

    for(int i=0; i < N; i++) {
        tmpSum = 0;
        for(int j=0; j < M; j++) {
            tmpSum += vect[j] * matrix[i][j];
        }

        cout << tmpSum << endl;
    }

    return 0;
}

Measured memory_bytes: 3188
/*
{By GWj

*/
#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define rb(a,b,c) for(int a=b;a<=c;++a)
#define rl(a,b,c) for(int a=b;a>=c;--a)
#define LL long long
#define IT iterator
#define PB push_back
#define II(a,b) make_pair(a,b)
#define FIR first
#define SEC second
#define FREO freopen("check.out","w",stdout)
#define rep(a,b) for(int a=0;a<b;++a)
#define SRAND mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define random(a) rng()%a
#define ALL(a) a.begin(),a.end()
#define POB pop_back
#define ff fflush(stdout)
#define fastio ios::sync_with_stdio(false)
#define R(a) cin>>a
#define R2(a,b) cin>>a>>b
#define check_min(a,b) a=min(a,b)
#define check_max(a,b) a=max(a,b)
using namespace std;
const int INF=0x3f3f3f3f;
typedef pair<int,int> mp;
/*}
*/
int n;
int a[100000+20];

int main(){
	fastio;
	R(n);
	rb(i,1,n) R(a[i]);
	sort(a+1,a+1+n);
	int las=0;
	LL sum=0;
	while(1){
		int index=las+1;
		sum+=a[las+1];
		while(index!=n&&sum*2>=a[index+1]){
			index++;
			sum+=a[index];
		}
		if(index==n){
			cout<<n-las<<endl;break;
			
		}
		las=index;	
	}
	return 0;
}

Measured memory_bytes: 3960
fn main() {
    let x: i32 = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().parse().unwrap()
    };
    let a=x/500;
    let b=(x-a*500)/5;
    println!("{}",a*1000+b*5);
}

Measured memory_bytes: 4352
N = int(input())
W  = list(map(int, input().split(" ")))

diff_min = 10**10
for i in range(N):
    A = sum(W[:i])
    B = sum(W[i:])
    if A > B:
        diff = A - B
    else:
        diff = B - A
    if diff < diff_min:
        diff_min = diff
print(diff_min)

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> hight(n);
    for ( int i = 0; i < n; ++i ) {
        cin >> hight.at(i);
    }
    vector<vector<int>> pair(m, vector<int>(2));
    for ( int i = 0; i < m; ++i ) {
        cin >> pair.at(i).at(0) >> pair.at(i).at(1);
    }

    vector<vector<int>> pass(n, vector<int>(0));
    for ( int j = 0; j < m; ++j ) {
        pass.at(pair.at(j).at(0)-1).push_back(pair.at(j).at(1));
        pass.at(pair.at(j).at(1)-1).push_back(pair.at(j).at(0));
    }

    int count = 0;
    for ( int i = 0; i < n; ++i ) {
        int flag = 1;
        if ( pass.at(i).size() != 0) {
            for ( unsigned int j = 0; j < pass.at(i).size(); ++j) {
                if ( hight.at(i) <= hight.at(pass.at(i).at(j)-1)) {
                    flag = 0;
                    break;
                }
            }
        }
        if ( flag) {
            count++;
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 14348
import java.util.*;
public class Main {
 
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int r=scan.nextInt()*100;
        int g=scan.nextInt()*10;
        int b=scan.nextInt();
 
        int sum=r+g+b;
        System.out.println(sum%4==0?"YES":"NO");
 
    }
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
using ll = long long;
using vin=vector<int>;
using vll=vector<ll>;
using P = pair<int, int>;
const int inf=1e9+7;
const ll INF=1e18;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int main() {
int x,y;
  cin>>x>>y;
  bool ok=false;
  if(y%2!=0) ok=false;
  else{
    if(x*2<=y && x*4>=y) ok=true; 
    
  }
  if(ok) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}










Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define REP(i,b,e) for(int i=(b);i<(e);++i)
#define RREP(i,b,e) for(int i=(b)-1;i>=e;--i)
#define rep(i,e) for(int i=0;i<(e);++i)

constexpr int MOD = 1000000007;
constexpr int INF = 1LL << 30;
constexpr long long LLINF = 1LL << 62;
constexpr double EPS = 1e-9;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15) << boolalpha;
  }
} initializer;

template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (T &x : vec) is >> x;
  return is;
}

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "[";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (it != vec.begin()) os << ", ";
    os << *it;
  }
  return os << "]";
}

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

template<typename Tuple, size_t N>
struct TuplePrinter {
  static void print(const Tuple &t) {
    TuplePrinter<Tuple, N-1>::print(t);
    cout << ", " << get<N-1>(t);
  }
};

template<typename Tuple>
struct TuplePrinter<Tuple, 1> {
  static void print(const Tuple &t) {
    cout << get<0>(t);
  }
};

template<typename... T>
ostream &operator<<(ostream &os, const tuple<T...> &tup) {
  os << "(";
  TuplePrinter<decltype(tup), sizeof...(T)>::print(tup);
  return os << ")";
}

template<typename T>
ostream &operator<<(ostream &os, const set<T> &se) {
  os << "{";
  for (auto it = se.begin(); it != se.end(); ++it) {
    if (it != se.begin()) os << ", ";
    os << *it;
  }
  return os << "}";
}

template<typename T, typename U>
ostream &operator<<(ostream &os, const map<T, U> &ma) {
  os << "{";
  for (auto it = ma.begin(); it != ma.end(); ++it) {
    if (it != ma.begin()) os << ", ";
    os << it->first << ": " << it->second;
  }
  return os << "}";
}

inline void print(void) { cout<<'\n'; }
template<class T> inline void print(const T &x) { cout<<x<<'\n'; }
template<class T, class... U> inline void print(const T &x, const U&... y) { cout<<x<<" "; print(y...); }
#define dump(...) cout<<#__VA_ARGS__<<": [L_"<<__LINE__<<"]"<<'\n'; print(__VA_ARGS__);cout<<'\n';

template<class T, class U>inline bool chmax(T &a, const U &b) { if(a<b){ a=b; return 1; } return 0; }
template<class T, class U>inline bool chmin(T &a, const U &b) { if(b<a){ a=b; return 1; } return 0; }


int main() {
  string s; cin>>s;
  int n = s.size();
  vector<long long> dp(2020, 0);
  vector<long long> tmp1(2020, 0);
  vector<long long> tmp2(2020, 0);
  int rem = (s[0] - '0') % 2019;
  dp[rem] = 1;
  tmp1[rem] = 1;

  REP(i, 1, n) {
    ++tmp2[(s[i] - '0')];
    rep(j, 2020) if (tmp1[j] != 0) {
      int rem = (j * 10 + (s[i] - '0')) % 2019;
      tmp2[rem] += tmp1[j];
    }
    rep(j, 2020) if (tmp2[j] != 0) {
      dp[j] += tmp2[j];
    }
    swap(tmp1, tmp2);
    fill(tmp2.begin(), tmp2.end(), 0);
  }

  print(dp[0]);

  return 0;
}

Measured memory_bytes: 3788
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int a, b, c = 0, d = 1, e, f = 0;
	cin >> a >> b;
	if (b >= 1 && b <= 9) {
		c = a * 10 + b;
	}
	else if (b == 100) {
		c = a * 1000 + b;
	}
	else {
		c = a * 100 + b;
	}
	for (int h = 1; h <= 320; h++) {
		if (h * h == c) {
			cout << "Yes" << "\n";
			f++;
		}
	}
	if (f == 0) {
		cout << "No" << "\n";
	}
	cin >> e;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using static System.Console;
using static System.Math;
using static MyIO;
using static MyUtil;

public class B { public static void Main() => (new Solver()).Solve(); }

public class Solver
{
	public void Solve()
	{
		long N = GetLong();
		long K = GetLong();
		WriteLine(GetLongs((int)N).OrderBy(x => x).Take((int)K).Sum());
	}
}

public static class MyIO
{
	private static string[] args = new string[0];
	private static int cnt = 0;
	private static IEnumerable<string> getArgs(long N) => Range(0, N).Select(_ => getArg());
	private static string getArg()
	{
		if(cnt == args.Length) { args = Console.ReadLine().Split(); cnt = 0; }
		return args[cnt++];
	}

	public static int GetInt() => int.Parse(getArg());
	public static long GetLong() => long.Parse(getArg());
	public static double GetDouble() => double.Parse(getArg());
	public static decimal GetDecimal() => decimal.Parse(getArg());
	public static string GetString() => getArg();
	public static char GetChar() => getArg()[0];
	public static int[] GetInts(long N) => getArgs(N).Select(int.Parse).ToArray();
	public static long[] GetLongs(long N) => getArgs(N).Select(long.Parse).ToArray();
	public static double[] GetDoubles(long N) => getArgs(N).Select(double.Parse).ToArray();
	public static decimal[] GetDecimals(long N) => getArgs(N).Select(decimal.Parse).ToArray();
	public static string[] GetStrings(long N) => getArgs(N).ToArray();
}

public static class MyUtil
{
	public static void chmax<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) < 0) x = y; }
	public static void chmin<T>(ref T x, T y) where T : IComparable<T> { if(x.CompareTo(y) > 0)	x = y; }
	public static void swap<T>(ref T x, ref T y) { T tmp = x; x = y; y = tmp; }
	public static long rightShift(long x, long y) => (x >> (int)y);
	public static long leftShift(long x, long y) => (x << (int)y);
	public static bool contains(long s, long x) => (rightShift(s, x) & 1L) == 1L;
	public static long gcd(long x, long y) => (y == 0) ? x : gcd(y, x % y);
	public static long lcm(long x, long y) => (x / gcd(x,y)) * y;	
	public static IEnumerable<int> Range(long start, long count) => Enumerable.Range((int)start, (int)count);
	public static void Sort(this List<string> source) => source.Sort(StringComparer.Ordinal);
}


Measured memory_bytes: 28732
//Code Forces - DP Educational Contest
 
 
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <climits>
 
 
const long long int INF = LLONG_MAX;
const int NMAX = 101;
const int VMAX = 1001;
 
struct Object {
 
	long long int v;
	int w;
};
 
 
int main() 
{
	int N, W;
	std::cin >> N >> W;
	
	std::vector<Object> objects(NMAX + 1);
 
	long long int sum_of_values = 0;
	for (int i = 1; i <= N; ++i) {
		std::cin >> objects[i].w >> objects[i].v;
		sum_of_values += objects[i].v;
	}
	std::vector<long long int> DP(sum_of_values + 2, 1000000000000);
	DP[0] = 0;
	//DP[1] = 0;
	for (long long int i = 0; i <= N; ++i) {
		
		std::vector<long long int> new_DP(sum_of_values + 2, 1000000000000);
		for (long long int j = 0; j <= sum_of_values; ++j) {
			new_DP[j] = DP[j];
 
			if(j >= objects[i].v)
				new_DP[j] = std::min(new_DP[j], DP[j - objects[i].v] + objects[i].w);
 
		}
 
		DP = new_DP;
 
	}
	
	long long int answer = 0;
 
	for (long long int i = 0; i <= sum_of_values; ++i) {
		if (DP[i] <= W) {
			//std::cout << DP[i] << ' ';
			answer = i;
		}
	}
 
	std::cout << answer;
 
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;

int main(){
    int a, b;

    cin >> a >> b;

    if(a > 8 || b > 8) {
        cout << ":(" << endl;
    } else {
        cout << "Yay!" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp6
{
	class Program
	{
		static void Main(string[] args)
		{
			while (true)
			{
				string num = Console.ReadLine();
				string[] xy = num.Split(' ');

				int x = int.Parse(xy[0]);
				int y = int.Parse(xy[1]);

				if (x == 0 && y == 0)
				{
					break;
				}
				else if (x < y)
				{
					Console.WriteLine("{0} {1}", x, y);
				}
				else
				{
					Console.WriteLine("{0} {1}", y, x);
				}

				
			}
		}
	}
}



Measured memory_bytes: 13796
#include <stdio.h>

#define MAX_N 100000
int tmp[MAX_N];

void func(int Len,long long *head){
    int cent = Len/2;
    int tip  = Len%2;
    if(Len > 2){
        func(cent, head);
        func(cent+tip, head+cent);
    }
    int i,j,k;
    i = k = 0;
    j = cent;
    if(Len == 1){
        tmp[k] = head[0];
        k++;
    }else{
        while(i < cent && j < Len){
            if(head[i] > head[j]){
                tmp[k] = head[i];
                k++;
                i++;
            }else{
                tmp[k] = head[j];
                k++;
                j++;
            }
        }

        while(i < cent){
            tmp[k] = head[i];
            k++;
            i++;
        }

        while(j < Len){
            tmp[k] = head[j];
            k++;
            j++;
        }
    }
    int l;
    for(l = 0;l < k;l++){
        head[l] = tmp[l];
    }
    return;
}

int main(void){
    int N;
    int A[MAX_N],B[MAX_N];
    long long int AB[MAX_N];
    scanf(" %d",&N);
    int i;
    for(i = 0;i < N;i++){
        scanf(" %d %d",&A[i],&B[i]);
        AB[i] = A[i] + B[i];
    }
    func(N,AB);
    long long int bsum = 0;
    for(i = 0;i < N;i++){
        bsum += B[i];
    }
    long long int ans = 0;
    for(i = 0;i < N;i+=2){
            ans += AB[i];
    }
    ans = ans - bsum;
    printf("%lld\n",ans);
    return 0;
}

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

using namespace std;

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


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

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

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

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

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

int main() {
	string s; cin >> s;
	Int k; cin >> k;
	Int pos=-1;
	string next="1";
	for (int i = 0; i < s.size(); i++) {
		if (s[i] != '1') {
			pos = i;
			if (i < s.size() - 1)next = s[i];
			else next = '1';
			break;
		}
	}
	if (s.size() == 1) {
		cout << s;
		return 0;
	}
	if (k > pos) cout << next;
	else cout << 1;

	cout << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

import static java.lang.Math.max;
import static java.lang.Math.min;


public class Main{

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n =scanner.nextInt();
        int[] cnt = new int[4];
        for (int i = 0; i < n; i++) {
            int tmp = scanner.nextInt();
            cnt[tmp]++;
        }
        double[][][]dp = new double[n+2][n+2][n+2];
        //dp[a][b][c]表示把a个1，b个2，c个3吃到0的期望操作次数
        dp[0][0][0] = 0;
        for(int k = 0;k<=n;k++) {
            for (int j =0;j<=n;j++) {
                for (int i=0;i<=n;i++) {
                    if(i==0&&j==0&&k==0)
                        continue;
                    double sum = (n/(double)(i+j+k));
                    if(i!=0) sum+=(i/(double)(i+j+k))*dp[i-1][j][k];
                    if(j!=0&&i+1<=n) sum+=(j/(double)(i+j+k))*dp[i+1][j-1][k];
                    if(k!=0&&j+1<=n) sum+=(k/(double)(i+j+k))*dp[i][j+1][k-1];
                    dp[i][j][k] = sum;
                }
            }
        }
        System.out.println(dp[cnt[1]][cnt[2]][cnt[3]]);
    }



}

Measured memory_bytes: 308052
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;
typedef long long ll;

int N;
ll T;


int main(){
  cin >> N >> T;
  ll sum = 0;
  ll t; cin >> t;
  ll st = t + T;
  for(int i = 1; i < N; i++){
    cin >> t;
    if(t <= st) sum += t - (st - T);
    else sum += T;
    st = t + T;
  }
  sum += T;

  cout << sum << endl;

  return 0;
}


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

int main() {
    int n, a[200];
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int cnt = 0;
    while(1) {
        for(int i = 0; i < n; ++i) {
            if(a[i] % 2 == 1) {cout << cnt << endl; return 0;}
            a[i] /= 2;
        }
        ++cnt;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>                                                                          
using namespace std;
int main()
{
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  int ans_1;
  int ans_2;
  if(A>C)
    ans_1=A;
  else
    ans_1=C;
  if(B<D)
    ans_2=B;
  else
    ans_2=D;
  if(ans_2-ans_1<0)
    cout << 0 << endl;
  else
    cout << ans_2-ans_1 << endl;
}

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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// random {{{ 1
ll rnd(){
    static ll x = time(0);
    x = x ^ (x << 13); x = x ^ (x >> 7);
    return x = x ^ (x << 17);
}
// }}}
// }}} 0

int main() {

    int a,b,x;
    Scd3(a,b,x);

    double over = atan(1.0*a/b);
    // over = over*PI/180;
    // printf ("%.9lf\n", (over)/PI*180 );

    if( a*a*b==x ) {
        printf ("%d\n", 0 );
        return 0;
    }

    double l = EPS;
    double r = PI/2;
    double c = 0;

    double s = 0;
    Rep(i,114514){
        c = (r+l)/2;
        s = 0;
        // s は 傾きcで入る量
        if( c < over ){
            // 三角
            s += 1.0*b*b*tan(c)/2;
        }else{
            // 台形(四角-三角)
            s += 1.0*a*b;
            s -= 1.0*a*a/tan(c)/2;
        }
        s *= a;
        if( s > x ){
            r = c;
        }else{
            l = c;
        }
    }

    printf ("%.19lf\n", (PI/2-c)/PI*180 );

    return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s-1);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

int main() {
    string s, t; cin>>s>>t;

    RREP(i, s.size(), 0) {
        if (i + t.size() > s.size()) continue;

        bool f = true;
        REP(j, t.size()) {
            f &= (s[i+j] == '?') || (s[i+j] == t[j]);
        }
        if (f) {
            s.replace(i, t.size(), t);
            while (s.find('?') != string::npos) {
                s[s.find('?')] = 'a';
            }

            cout << s << endl;
            return 0;
        }
    }

    cout << "UNRESTORABLE" << endl;
}


Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};

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

vector<in> gc(0);
in n,k;
in culc(in x){
    if(gc[x]>0) return gc[x];
    in y=2ll;
    in ret=modpow(k/x,n,MOD);
    while(x*y<=k){
        ret -=culc(x*y);
        ret=(ret+MOD)%MOD;
        y ++;
    }
    return gc[x]=ret;
}

int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    cin>>n>>k;
    in sum=0ll;
    gc.resize(k+1ll,-1ll);
    culc(1ll);
    in ans=0ll;
    REP(i,1ll,k+1){
        ans +=i*gc[i];
        ans %=MOD;
    }
    cout<<ans<<endl;
    // cout<<modpow(1ll,n,MOD);
}
//./problem.exe

Measured memory_bytes: 3956
#include <bits/stdc++.h>
using namespace std;
const int Maxn=305,mod=1e9+7;
int a[2*Maxn],vis[2*Maxn],ban[2*Maxn],f[2*Maxn][Maxn][Maxn];
int main(){
	int n,c=0;scanf("%d",&n);
	for(int i=1;i<=2*n;i++){
		scanf("%d",&a[i]);
		if(~a[i]){
			a[i]=2*n-a[i]+1;	
			vis[a[i]]=true;
		}
	}
	for(int i=1;i<=n;i++)
		if(a[2*i-1]*a[2*i]>1)
			ban[a[2*i-1]]=ban[a[2*i]]=1;
		else if(a[2*i-1]*a[2*i]==1)
			c++;
	f[0][0][0]=1;
	for(int i=0;i<2*n;i++){
		if(ban[i+1]){
			memcpy(f[i+1],f[i],sizeof(f[i]));
			continue;
		}
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++){
				if(!f[i][j][k])continue;
				if(vis[i+1]){
					if(j)f[i+1][j-1][k]=(f[i+1][j-1][k]+f[i][j][k])%mod;
					f[i+1][j][k+1]=(f[i+1][j][k+1]+f[i][j][k])%mod;
				}else{
					f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%mod;
					if(j)f[i+1][j-1][k]=(f[i+1][j-1][k]+f[i][j][k])%mod;
					if(k)f[i+1][j][k-1]=(f[i+1][j][k-1]+1ll*k*f[i][j][k])%mod;
				}
			}
	}
	for(int i=1;i<=c;i++)f[2*n][0][0]=1ll*f[2*n][0][0]*i%mod;
	cout<<f[2*n][0][0]<<"\n";
	return 0;
}

Measured memory_bytes: 219136
/* 	* In the name of GOD 
	* Thanks God */
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second

int32_t main(){
	int n;
	cin >> n;
	n = n % 10;
	set <int> s1 = {2
	 , 
	 4
	 , 
	 5
	 , 
	 7
	 , 
	 9}, s2 = {0
	 , 
	 1
	 , 
	 6
	  , 
	  8};
	if (s1.count (n)){
		cout << "hon";
	}else if (s2.count (n)){
		cout << "pon";
	}else{
		cout << "bon";
	}
}


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

int main(){
    int A, B, C, K;
    cin >> A >> B >> C >> K;
    int m = max(A, max(B,C));
    int d = pow(2,K);
    cout << (A + B + C - m) + m * d << endl;
}

Measured memory_bytes: 256