akhauriyash/Code-Regression huggingface dataset:
#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn a(n: usize) -> Vec<usize> {
    let mut v = vec![0; n + 1];
    v[0] = 1;
    for i in 1..n + 1 {
        v[i] = v[i - 1] * 2 + 3;
    }
    v
}
fn b(n: usize) -> Vec<usize> {
    let mut v = vec![0; n + 1];
    v[0] = 1;
    for i in 1..n + 1 {
        v[i] = v[i - 1] * 2 + 1;
    }
    v
}
fn f(n: usize, x: usize, all: Vec<usize>, buns: Vec<usize>) -> usize {
    if n == 0 || x == 0 {
        if 1 <= x {
            return 1;
        }
        return 0;
    } else if x <= all[n - 1] + 1 {
        return f(n - 1, x - 1, all, buns);
    } else {
        return buns[n - 1] + 1 + f(n - 1, x - 2 - all[n - 1], all, buns);
    }
}
fn main() {
    let (n, x) = get!(usize, usize);
    let all = a(n);
    let buns = b(n);

    println!("{}", f(n, x, all, buns));
}


Measured memory_bytes: 4352
import sys
input = sys.stdin.readline

def main():
    H, W = map(int, input().split())
    N = int(input())
    a = list(map(int, input().split())) + [0]

    ans = [[0] * W for i in range(H)]

    num = 1
    rest = a[0]
    for y in range(H):
        if y&1:
            for x in range(W-1, -1, -1):
                ans[y][x] = num
                rest -= 1
                if rest == 0:
                    rest = a[num]
                    num += 1
        else:
            for x in range(W):
                ans[y][x] = num
                rest -= 1
                if rest == 0:
                    rest = a[num]
                    num += 1
    
    for y in range(H):
        for x in range(W-1):
            print(ans[y][x], end=" ")
        print(ans[y][-1])
                    

if __name__ == "__main__":
    main()

Measured memory_bytes: 3828
#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <iomanip>
#include <sstream>
#include <stdint.h>
#include <string.h>

#include <unordered_set>

#define _USE_MATH_DEFINES
#include <math.h>


#include <vector>
#include <list>

#include <set>
#include <map>

#include <unordered_map>

#include <queue>

#include <string>

#include <vector>

#define sqr(x) (x) * (x)

#include <algorithm>
#include <functional>

#include <bitset>

#include <functional>

#include <chrono>

typedef unsigned int u32;
typedef int i32;

typedef unsigned long long int u64;
typedef long long int i64;

typedef uint16_t u16;
typedef int16_t i16;

typedef uint8_t u8;
typedef int8_t i8;


using namespace std;
using namespace std::chrono;

struct less_key
{
    bool operator() (pair<i64, i64> p1, pair<i64, i64> p2)
    {
        return p1.first < p2.first || (p1.first == p2.first && p1.second < p2.second);
    }
};

struct pair_hash {
public:
    std::size_t operator()(const std::pair<u64, u64> &x) const
    {
        return std::hash<u64>()(x.first) ^ std::hash<u64>()(x.second);
    }
};
#include <random>

const i64 mod = 1000000007ll;
const i64 smod = 999983;
const i64 inf = mod;

const double eps = 1e-10;

// del

const i64 MAXN = 22;

i64 n;
i64 a[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(15); cout.setf(ios::fixed);

    cin >> n;

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

    i64 R = 1;
    for (i64 i = 1; i < n; i++) {
        bool f = true;
        for (i64 j = 0; j < i; j++) {
            if (a[j] > a[i]) {
                f = false;
                break;
            }
        }
        if (f) {
            R++;
        }
    }

    cout << R << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <set>

#define vi vector<int>;
#define vvi vector<vector<int>>;

using namespace std;

int main() {
    string t;
    cin >> t;
    int seven=0;
    for (int i=0 ; i<int(t.size()); i++){
        if (t[i]=='7'){
            seven=1;
            break;
        }
    }
    if (seven==1){
        cout << "Yes" << endl;
        return 0;
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3628
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int gcd(int a,int b);
int compare(const void* a, const void* b);

int main(void){
    int A,B;
    int i = 1;
    int ret = 0;
    scanf("%d %d",&A,&B);
    while(i < B){
        i = i + A - 1; //1口つかってA口ふやす
        ret++;
    }
    printf("%d\n",ret);    
}
int compare(const void* a, const void* b){
    return strcmp(a, b);
}
// 最大公約数
int gcd(int a,int b){
    int c;
    int tmp;
    if(b > a){  //bがaより大きい場合bとaを入れ替える
        c = a;
        a = b;
        b = c;
    }
    tmp = a % b;
    while(tmp!=0){
        a = b;
        b = tmp;
        tmp = a % b;
    }
    return b;
}


Measured memory_bytes: 128
import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    x=[0]*n
    y=[0]*n
    for i in range(n):
#        xy[i]=list(map(int,input().split()))
        x[i],y[i]=map(int,input().split())
elif icase==1:    
    n=3
#    xy=[[1, 5], [3, 9], [7, 8]]
    x=[1, 3, 7]
    y=[5, 9, 8]
elif icase==2:    
    n=6
#    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]
    x=[8, 4, 12,18,13,7]
    y=[3, 9, 19, 1, 5, 6]

xi=[[0]*2 for i in range(n)]
yi=[[0]*2 for i in range(n)]
for i in range(n):
    xi[i]=[x[i],i]
    yi[i]=[y[i],i]
    
xi.sort()
x=xi
y=yi.sort()
y=yi

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    wi=x[i+1][0]-x[i][0]
    heappush(que,(wi,x[i][1],x[i+1][1]))
    wi=y[i+1][0]-y[i][0]
    heappush(que,(wi,y[i][1],y[i+1][1]))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)
#    print(w,s,t)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1
#        print(icnt)

print(length_sum)   


Measured memory_bytes: 99040
#include<bits/stdc++.h>
#define ll long long
#define N 300
using namespace std;
int n, m, ans;
char s[N][20], t[N][20];
map<string, int> ma;
int main()
{
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt","w",stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%s", s[i]), ma[string(s[i])]++;
    scanf("%d", &m);
    for(int i = 1; i <= m; i ++) scanf("%s", t[i]), ma[string(t[i])]--;
    for(auto x : ma)
    {
        if(x.second > 0)
        {
            ans = max(ans, x.second);
        }
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
/*
  Motto - try hard to become an expert
*/
#include <bits/stdc++.h>
#include <map>
#include <algorithm>
#include <vector>
#include <string.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <chrono>
#include <thread>
#include <iomanip>
 
//define
#define rep(i,n)    for(int i=0;i<n;i++)
#define repu(i,k,n) for(int i=k;i<=n;i++)
#define repd(i,k,n) for(int i=k;i>=n;i--)
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define INF (int)INT_MAX
#define all(v)  v.begin(), v.end()
#define endl "\n"
 
//typedef
typedef long long int ll;
typedef long double ld;
typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector< pii > vii;
typedef std::vector< ll > vll;
typedef std::vector< std::pair < pii, int > > vpp;
 
const int N = 3*1e5 +5 ;
const long long MOD = 998244353;
const long long inf = 1e18;
 
using namespace std;
 
ll MAXN=100001;
ll spf[100001]; 
 
ll modpow(ll x,ll n){
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%MOD;
        x=x*x%MOD;
        n>>=1;
    }
    return res;
}
 
ll modFact(ll n, ll p) 
{ 
    if (n >= p) 
        return 0; 
  
    ll result = 1; 
    for (ll i = 1; i <= n; i++) 
        result = (result * i) % p; 
  
    return result;  
} 
 
bool isPrime(int x)
{
    if(x%2==0)
        return 0;
    for(int i=3;i<=sqrt(x);i+=2)
    {
        if(x%i==0)
            return 0;
    }
    return 1;
}
 

 
void solve()
{
    int ma = 360 ; 
    int d ; 
    cin>>d ;
    int gc = __gcd(720 , d) ;
    d /= gc ; 
    ma /= gc ;
    cout<<ma<<endl;
    
}

int main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        freopen("output.txt", "w", stdout);
    #endif
    
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    int t = 1;
    //cin>>t;
    while(t--)
    {
        solve();
    } 
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Measured memory_bytes: 3856
#include<stdio.h>
int main(void){
  int a,b,c,d,e,k;
  scanf("%d %d %d %d %d %d",&a,&b,&c,&d,&e,&k);
          if(e-a<=k){
            printf("Yay!");
          }
  else printf(":(");
  return 0;
}
        


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int num=1e9+7;
int main(){
    int n,m;
    cin >> n >> m;
    int a[m];
    ll sum=0;
    for(int i=0; i<m; i++){
        cin >> a[i];
        sum+=a[i];
    }
    if(n-sum>=0)cout << n-sum << endl;
    else cout << -1 << endl;
}

Measured memory_bytes: 3652
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define F first
#define S second
#define pss pair<string,string>
#define pcc pair<char,char>
#define pll pair<ll,ll>
#define pii pair<int,int>
#define piii pair<int,pii>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
#define vs vector<string>
#define vl vector<ll>
#define vs vector<string>
#define vll vector<pll>
#define vss vector<pss>
#define vcc vector<pcc>
#define MP make_pair
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=n-1;i>=0;i--)
#define Very_fast std::ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const int N = 5005;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
inline ll gcd(ll a,ll b){if(b==0)return a;else return gcd(b,a%b);}
inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
inline ll lowbit(ll x){return (x&-x);}
inline ll kissme(ll x,ll y)
{
	ll res=1;
	if(x==0)return 1;
	if(x==1)return y;
	res=kissme(x/2,y);
	res=res*res%mod;
	if(x%2==1)res=res*y%mod;
	return res;
}
int n,cnt,m,x[N],c[N];vi v[N];
bool vis[N];ll ans;
void dfs()
{
	
}
int main()
{
	Very_fast;
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>x[i],x[i]--;
	for(int i=0;i<n;i++)cin>>c[i];
	ans=c[0];
	for(int i=0;i<n;i++)
	{
		memset(vis,0,sizeof(vis));
		int now=i;ll sum=0,cnt=m;
		while(!vis[now]&&cnt--)
		{
			vis[now]=true;
			sum+=c[now];
			ans=max(ans,sum);
			now=x[now];
		}
		if(cnt<=0)continue;
		int org=x[now];cnt--;
		ll sum2=c[now],Cnt=1;
		ans=max(ans,sum+sum2);
		while(org!=now&&cnt--)
		{
			sum2+=c[org];
			ans=max(ans,sum+sum2);
			org=x[org];
			Cnt++;
		}
		if(sum2<=0||cnt<0)continue;
		bool add=false;
		if(cnt>Cnt)cnt-=Cnt,add=true;
		sum+=sum2+cnt/Cnt*sum2;
		cnt%=Cnt;
		ans=max(ans,sum);
		if(add)cnt+=Cnt;
		while(cnt--)
		{
			sum+=c[now];
			now=x[now];
			ans=max(ans,sum);
		}
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 3816
L, R = map(int, input().split())
MOD = 10 ** 9 + 7
l = '{:060b}'.format(L)[::-1]
r = '{:060b}'.format(R)[::-1]

memo = [[[[-1 for l in range(2)] for k in range(2)] for j in range(2)] for i in range(60)]

#上から1桁ずつ4パターン(x0y0, x1y0, x0y1, x1y1)に場合分けして計算
def f(pos, flagX, flagY, flagZ):
    if pos == -1:
        return 1
    if memo[pos][flagX][flagY][flagZ] != -1:
        return memo[pos][flagX][flagY][flagZ]
    ret = 0
    #x0, y0
    if flagX or l[pos] == '0':
        ret += f(pos-1, flagX, 1 if r[pos]=='1' else flagY, flagZ)
    #x0, y1
    if (flagX or l[pos] == '0') and (flagY or r[pos] == '1') and flagZ:
        ret += f(pos-1, flagX, flagY, flagZ)
    #x1, y1
    if flagY or r[pos] == '1':
        ret += f(pos-1, 1 if l[pos] == '0' else flagX, flagY, 1)
    ret %= MOD
    memo[pos][flagX][flagY][flagZ] = ret
    return ret

ans = f(59, 0, 0, 0)
print(ans)
        



Measured memory_bytes: 38416
#include <iostream>

#define MAX_NM 50

using namespace std;

void solve();
void dfs(int x, int y);

int w,h;
int field[MAX_NM][MAX_NM];

int main()
{
    while (1) {
        cin>>w>>h;
        if (w==0&&h==0) break;
        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                cin>>field[i][j];
            }
        }
        solve();
    }
    return 0;
}

void solve()
{
    int count=0;
    for (int i=0; i<h; i++) {
        for (int j=0; j<w; j++) {
            if (field[i][j]==1) {
                dfs(i,j);
                count++;
            }
        }
    }
    cout<<count<<endl;
}

void dfs(int x, int y)
{
    field[x][y]=0;
    
    for (int dx=-1; dx<=1; dx++) {
        for (int dy=-1; dy<=1; dy++) {
            int nx=x+dx, ny=y+dy;
            
            if (nx>=0&&nx<h&&ny>=0&&ny<w&&field[nx][ny]==1) {
                dfs(nx,ny);
            }
        }
    }
}

Measured memory_bytes: 1348
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mod=1e9+7;
int a[605],t[605],f[2][305][305];
inline void add(int &x,int y){
	x+=y;
	if(x>mod)x-=mod;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=2*n;i++)scanf("%d",&a[i]);
	int cnt=0,cnt1=0;
	for(int i=1;i<=n;i++){
		if(a[2*i-1]==-1)
			if(a[2*i]==-1)cnt++;
			else t[a[2*i]]=1,cnt1++;
		else if(a[2*i]==-1)t[a[2*i-1]]=1,cnt1++;
			 else t[a[2*i-1]]=t[a[2*i]]=2;
	}
	f[0][0][0]=1;
	for(int i=1;i<=2*n;i++){
		int c=i&1;
		memset(f[c],0,sizeof(f[c]));
		for(int j=0;j<=n;j++)
			for(int k=0;k<=n;k++)if(f[c^1][j][k]){
				if(t[i]==1){
					if(j)add(f[c][j-1][k],1ll*j*f[c^1][j][k]%mod);
					add(f[c][j][k+1],f[c^1][j][k]);
				}else if(t[i]==0){
					if(k)add(f[c][j][k-1],f[c^1][j][k]);
					add(f[c][j+1][k],f[c^1][j][k]);
					add(f[c][j][k+1],f[c^1][j][k]);
				}else if(t[i]==2){
					f[c][j][k]=f[c^1][j][k];
				}
				//printf("%d %d %d %d\n",i-1,j,k,f[i-1][j][k]);
			}
	}
	int res=f[0][0][0];
	for (int i = 1; i <= cnt; ++i)
	{
		res=1ll*res*i%mod;
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 896
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;

//typedef
typedef long long LL;
typedef vector<LL> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//conversion
inline LL toLong(string s) {LL v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

//math
//-------------------------------------------
template<class T> inline T sqr(T x) {return x*x;}

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) LL((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define UNTIL(p) while(!(p))

//constant
const double EPS = 1e-5;
const double PI  = acos(-1.0);

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

#define PUTS(x) cout << (x) << endl;

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    LL n;
    cin>>n;
    VL h(n);
    REP(i,n)cin>>h[i];
    bool yes = true;
    for(int i = n - 2; i >= 0 ; i--) {
        if(h[i] > h[i + 1])h[i]--;
        if(h[i] > h[i + 1]){
            yes = false;
            break;
        }
    }
    PUTS(yes ? "Yes" : "No");
}

Measured memory_bytes: 1024
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

int n,m,in[100010],ans[100010];
vector <int> g[100010];
bool vis[100010];

void dfs(int pos,int lst)
{
	//cout<<pos<<' '<<lst<<endl;
	ans[pos]=lst;
	vis[pos]=true;
	rep(i,g[pos].size()) in[g[pos][i]]--;
	rep(i,g[pos].size())
	{
		if(vis[g[pos][i]]||in[g[pos][i]]!=0) continue;
		/*
		dfs从祖先往子孙递归，连接到一个点的所有边在到达它真正父亲之前已经被它的祖先消得只剩下一个了，
		所以就能判断出真正的父亲 
		*/
		dfs(g[pos][i],pos);
	}
}

int main()
{
	cin>>n>>m;
	rep(i,n+m-1)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		g[x].pb(y);
		in[y]++;
	}
	repn(i,n)
	{
		if(in[i]==0)
		{
			dfs(i,0);
			repn(j,n) cout<<ans[j]<<endl;
			rt0;
		}
	}
	rt0;
}

Measured memory_bytes: 11904
// 課題4_2 AtCoder Beginner Contest 168 C - : (Colon)
// nk777
 
#include<stdio.h>
#include<math.h>
 
int main(void){
    // 時針の長さlength_h cm,分針の長さlength_min cm,時刻hour:min
    int length_h, length_min, hour, min;
    // 結果の格納ans, 短針と時針の間の角度rad
    double ans, rad;
 
    // length_h, length_min, hour, minを受け取る
    scanf("%d %d %d %d", &length_h, &length_min, &hour, &min);

    // intからdoubleに変換
    length_h = (double)length_h;
    length_min = (double)length_min;
    min = (double)min;
    hour = (double)hour;
 
    // 円周率M_PI
    // (分針)ー(時針)cosなので角度の正負は気にしない
    rad = 2.0 * M_PI / 60.0 * min - 2.0 * M_PI / 12 * (hour + min / 60.0);
    // 余弦定理 ans^2
    ans = length_h * length_h + length_min * length_min - 2.0 * length_h * length_min * cos(rad);
    // 平方根をとる
    ans = sqrt(ans);

    printf("%.20f\n", ans);
    
    return 0;
}

Measured memory_bytes: 2544
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    if (n % 10 == 3) cout << "bon\n";
    else if (n % 10 == 0 || n % 10 == 1 || n % 10 == 6 || n % 10 == 8) cout << "pon\n";
    else cout << "hon\n";
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
template<class T>bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int H, W;
	cin >> H >> W;
	char C[30][30];
	int ans = 0;
	REP(i, H) {
		REP(j, W) {
			cin >> C[i][j];
		}
	}

	REP(i, H) {
		REP(j, W) {

			queue<pair<pii,int> >Q;
			Q.push(make_pair(pii(i, j), 0LL));


			bool vis[21][21] = { false };
			int dx[] = { 0,0,1,-1 };
			int dy[] = { 1,-1,0,0 };
			vis[i][j] = true;


			if (C[i][j] == '#')continue;

			while (!Q.empty()) {

				int a = Q.front().first.first;
				int b = Q.front().first.second;
				int cnt = Q.front().second;
				Q.pop();

				REP(k, 4) {
					int nx = a + dx[k];
					int ny = b + dy[k];

					if (nx >= 0 && nx < H&&ny >= 0 && ny < W) {
						
						if (C[nx][ny]=='.'&&!vis[nx][ny]) {
							Q.push(make_pair(pii(nx, ny), cnt + 1));


							if (ans < cnt + 1) {
								chmax(ans, cnt + 1);
								//cout << i << " " << j << " " << nx << " " << ny << endl;
							}
							vis[nx][ny] = true;
						}
					}


				}



			}


		}
	}



	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 256
import numpy as np
w,h,n=map(int,input().split())
mass = np.ones([h,w])
#print(mass)
for i in range(n):
  x,y,a = map(int,input().split())
  if a==1:
    mass[:,:x]=0
  if a==2:
    mass[:,x:]=0
  if a==3:
    mass[(h-y):,:]=0
  if a==4:
    mass[:(h-y),:]=0
  #print(mass)
check = np.sum(mass,axis=1)
check = np.sum(check,axis=0)
print(check)


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

int main(){
  string s;
  cin >> s;
  int I = 0;
  bool can =  false, can2 = false;
  rep(i,s.size()){
    if(s[i] == 'C') {
      I = i;
      can = true;
      break;
    }
  }
  if(can){
    for(int j = I; j < s.size(); j++){
      if(s[j] == 'F') can2 = true;
    }
  }
  if(can2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

int main() {
  int N;
  cin >> N;
  int min = 0;
  for(int i = 0; i < N;i++){
    int x;
    cin >> x;
    int count = 0;
    while(x % 2 == 0){
      count++;
      x /= 2;
    }
    if(i == 0){
      min = count;
    }else if(min > count){
      min = count;
    }
  }
  cout << min << endl;
}


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

using namespace std;

using ull = unsigned long long;


int main() {
    ull H;
    cin >> H;

    ull n = 0;
    while (H > 0) {
        H /= 2;
        n++;
    }

    ull ans = 1;
    for (ull i = 0; i < n; i++)
        ans *= 2;
    ans--;
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <cstring>
#include <utility>
#include <vector>
#include <climits>
#include <cstdio>
#include <cmath>
#include <unordered_map>
using namespace std;
void solve()
{
	int n;
	cin>>n;n++;
	double ans=0,p[n],dp[n][n];
	for(int i=1;i<n;i++) {cin>>p[i];}
	

	dp[1][1]=p[1];dp[1][0]=1-p[1];
	for(int i=2;i<n;i++)
	{
		dp[i][0]=dp[i-1][0]*(1-p[i]);
		for(int j=1;j<i;j++)
		{
			dp[i][j]=dp[i-1][j]*(1-p[i])+dp[i-1][j-1]*p[i];
		}
		dp[i][i]=dp[i-1][i-1]*p[i];
	}
	// cout<<'\n';
	// for(int i=1;i<n;i++)
	// {
	// 	for(int j=1;j<=i;j++)
	// 	{
	// 		cout<<dp[i][j]<<' ';
	// 	}
	// 	cout<<'\n';
	// }
	n--;
	for(int i=n/2+1;i<=n;i++)
	{
		ans+=dp[n][i];
	}
	cout<<ans<<'\n';
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.precision(12);

	// int t;
	// cin>>t;
	// while(t--)
    solve();
    return 0;
}

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

int main() {
    int N; cin >> N;
    string S; cin >> S;
    int ok = 0, ng = N + 1;
    while (ng - ok != 1) {
        int med = (ok + ng) / 2;
        map<string, int> Z;
        bool f = false;
        for (int i = 0; i <= N - med; i++) {
            if (Z[S.substr(i, med)] == 0) {
                Z[S.substr(i, med)] = i + med;
            } else if (Z[S.substr(i, med)] <= i) {
                f = true;
                break;
            }
        }
        if (f) {
            ok = med;
        } else {
            ng = med;
        }
    }
    cout << ok << endl;
}


Measured memory_bytes: 6672
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
ll f(ll b,ll n){
  if(b<=1) return -1;
  ll res = 0;
  while(n>0){
    res += n%b;
    n /= b;
  }
  return res;
}
int main() {
  ll n,s;
  cin >> n >> s;
  if(n<s){
    cout << -1 << endl;
    return 0;
  }
  if(n==s){
    cout << n+1 << endl;
    return 0;
  }
  ll nr = 1;
  for(ll b=2;b*b<=n;++b){
    if(f(b,n)==s){
      cout << b << endl;
      return 0;
    }
    nr=b;
  }
  for(ll p=nr;p>0;--p){
    if(p>s) continue;
    ll b = (n-(s-p))/p;
    if(f(b,n)==s){
      cout << b << endl;
      return 0;
    }
  }
  cout << -1 << endl;
}

Measured memory_bytes: 3576
#!usr/bin/env python3
from collections import defaultdict
import math
def LI(): return list(map(int, input().split()))
def II(): return int(input())
def LS(): return input().split()
def S(): return input()
def IIR(n): return [II() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
mod = 1000000007

#A
"""
a,b = LS()
c = int(a+b)
for i in range(1,1000):
    if i * i == c:
        print("Yes")
        quit()
print("No")
"""

#B
"""
a,b = LI()
if a*b <= 0:
    print("Zero")
else:
    if b < 0:
        if (a-b) %2 == 1:
            print("Positive")
        else:
            print("Negative")
    else:
        print("Positive")
"""

#C
"""
n = II()
s = SR(n)
march = [[] for i in range(5)]
ch = list("MARCH")
for i in s:
    for j in range(5):
        if i[0] == ch[j]:
            march[j].append(i)
ans = 0
for i in range(5):
    for j in range(i):
        for k in range(j):
            if len(march[i])*len(march[j])*len(march[k]) == 0:
                break
            ans += len(march[i])*len(march[j])*len(march[k])
print(ans)
"""

#D
"""
n = II()
d = LIR(n)
q = II()
p = IIR(q)
d.insert(0,[0 for i in range(n+1)])
for i in range(n):
    d[i+1].insert(0,0)
for i in range(n):
    for j in range(n):
        d[i+1][j+1] += d[i+1][j]+d[i][j+1]-d[i][j]
ans = [0 for i in range(n**2+1)]

for a in range(n+1):
    for b in range(n+1):
        for c in range(a):
            for e in range(b):
                ans[(a-c)*(b-e)] = max(ans[(a-c)*(b-e)],d[a][b]-d[c][b]-d[a][e]+d[c][e])

for i in p:
    an = 0
    for a in range(i+1):
        an = max(an, ans[a])
    print(an)
"""
#E

s = list(S())
ans = -1
s.insert(0,0)
d = 0
for i in range(1,len(s)):
    if s[i] != d:
        d = s[i]
        ans += 1
print(ans)
#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 4332
#include <bits/stdc++.h>
#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,a,b) for (int i = (b-1); i >= (a); i--)
#define REP(i,n) FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ALL(x) (x).begin(),(x).end()
#define RALL(x) (x).rbegin(),(x).rend()
#define DEBUG(x)  cout << #x << " = " << (x) << endl;
#define SORT(x) sort(ALL(x));
#define RSORT(x) sort(RALL(x));
#define SUM(x) accumulate(ALL(x),0);
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
const ll mod = 1e9+7;
const int INF = (1<<30)-1;
const ll INFLL = (1LL<<62)-1;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//cout << fixed << setprecision(10);

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

int main () {
  int N; cin >> N;
  vi A(N+2,0); FOR(i,1,N+1) cin >> A[i];

  int S = 0;
  REP(i,N+1) {
    S += abs(A[i]-A[i+1]);
  }

  FOR(i,1,N+1) {
    cout << S - (abs(A[i-1]-A[i]) + abs(A[i]-A[i+1])) + abs(A[i-1]-A[i+1]) << endl;;
  }
}

Measured memory_bytes: 1664
using System;
using System.Collections.Generic;

namespace ABC121_C___Energy_Drink_Collector
{
    class Program
    {
        static void Main(string[] args)
        {
            var read = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
            var N = read[0];
            var M = read[1];
            var shops = new PriorityQueue<Shop>(false);

            for(int i = 0 ; i < N ; i++)
            {
                read = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
                shops.Push(new Shop(read[0],read[1]));
            }

            Shop currentShop  = currentShop = shops.Pop();
            long amount = 0;
            while(shops.Count() > 0)
            {
                if(currentShop.stock > M) break;
                M -= currentShop.stock;
                amount += currentShop.price * currentShop.stock;
                currentShop = shops.Pop();
            }
            amount += currentShop.price * M;

            Console.WriteLine(amount);
        }
    }
    class Shop : IComparable
    {
        public long price{get;set;}
        public long stock{get;set;}

        public int CompareTo(object _shop)
        {
            Shop shop = (Shop)_shop;
            if(this.price > shop.price) return -1;
            if(this.price < shop.price) return 1;
            if(this.price == shop.price) return 0;
            return 0;
        }
        public Shop(long _price,long _stock)
        {
            this.price = _price;
            this.stock = _stock;
        }
    }

    class PriorityQueue<T> where T : IComparable
{
    private List<T> nodes;
    private Boolean isAsc;

    public PriorityQueue(Boolean _isAsc)
    {
        this.nodes = new List<T>();
        this.isAsc = _isAsc;
    }

    public int Count()
    {
        return this.nodes.Count;
    }
    public T Pop()
    {
        T returnNode = this.nodes[0];
        this.nodes[0] = this.nodes[nodes.Count-1];
        this.nodes.RemoveAt(nodes.Count-1);
        int root = 0;
        while(root*2 + 1 < this.nodes.Count)
        {
            int child = root * 2 + 1;
            if(child+1<this.nodes.Count && compare(this.nodes[child+1],this.nodes[child]) > 0) child += 1;
            if(compare(this.nodes[child],this.nodes[root]) > 0)
            {
                swap(child,root);
                root = child;
            }else{
                break;
            }
        }
        return returnNode;
    }
    public void Push(T t)
    {
        this.nodes.Add(t);
        var addPosition = nodes.Count - 1;
        while(addPosition > 0)
        {
            var parent = (int)(addPosition-1)/2;
            if(compare(nodes[addPosition],nodes[parent]) > 0 )
            {
                swap(addPosition,parent);
                addPosition = parent;
            }else{
                break;
            }
     }
    }
    private int compare(T x,T y)
    {
        return this.isAsc ? y.CompareTo(x) : x.CompareTo(y);
    }
    private void swap(int x,int y)
    {
        T temp = nodes[x];
        nodes[x] = nodes[y];
        nodes[y] = temp;
    }
}
}


Measured memory_bytes: 21332
/*
    問題をよく読もう！
    論理的に考えよう！
    サンプルを確認しよう!
    絶対に諦めるな！
    工夫をしろ！
    配列は少し多めにとっておく

    Twitterは終わるまでログアウト！
    （間違えて解法をツイートしてはいけないから）

*/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
#include <functional>
#include <cmath>
using namespace std;
#define rep(i, n) for(int i=0; i<n; ++i)
typedef long long ll;
//必要な宣言

void solve();

int x;

int main() {
  cin >> x;

  solve();

  return 0;
}

void solve() {
  int max = 1;
  int n;

  if(x == 1) {
    cout << 1 << endl;
    return;
  }

  for(int i=2; i*i<=x; ++i) {
    n = i;
    while(n<=x) {
      n *= i;
      if(max < n && n <= x) max = n;
    }
  }

  cout << max << endl;

  return;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <iomanip>
#include <fstream>
using namespace std;
int main(){
	string s;
	cin>>s;
	if(s[s.size()-1]=='s'){
		cout<<s<<"es"<<endl;
	}else{
		cout<<s<<"s"<<endl;
	}
	return 0;
}

Measured memory_bytes: 3040
x,n=map(int,input().split())
p=set(list(map(int,input().split())))

if x not in p :
    print(x)
    exit()
i=1
while True:
    if x-i not in p:
        print(x-i)
        exit()
    if x+i not in p:
        print(x+i)
        exit()
    i+=1


Measured memory_bytes: 9136
N=int(input())
S=[input() for i in range(N)]
M=int(input())
T=[input() for i in range(M)]
max=0
for i in range(N):
    cnt=0
    for j in range(N):
        if S[i]==S[j]:
            cnt+=1
    for k in range(M):
        if S[i]==T[k]:
            cnt-=1
    if max<cnt:
        max=cnt
print(max)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define REVETSE(c) reverse((c).begin(),(c).end())
#define SUM(c) accumulate((c).begin(),(c).end(),0)
#define ALL(a)  (a).begin(),(a).end()
// int gcd(int a,int b){return b?gcd(b,a%b):a;}
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> T maxt(T x,T y) {
    if (x>y) return x;
    else return y;
}
template<class T> T mint(T x,T y) {
    if (x>y) return y;
    else return x;
}
//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
//cout << fixed << setprecision(10) << ans << defaultfloat << endl;
typedef long long ll;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<double> Vd;
typedef vector<string> Vs;

long long m = 1e9+7, mod = 1e9+7;
//逆元　a/b の modをとるとき -> a*modinv(b)%mod
long long modinv(long long a, long long m = 1e9+7) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

/* //約数列挙
vector< int64_t > divisor(int64_t n) {
  vector< int64_t > ret;
  for(int64_t i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}*/


int main() {
  int n,m;
  scanf("%d %d",&n,&m);
  if (n==m) printf("Yes");
  else printf("No");
  
}

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

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

    vector<string> A(H);

    rep2(i, 0, H){
        cin >> A.at(i);
    }

    vector<char> sharp(W+2, '#');

    rep2(i, 0, W+2) cout << sharp.at(i);
    cout << endl;

    rep2(i, 0, H) cout << '#' + A.at(i) + '#' << endl;

    rep2(i, 0, W+2) cout << sharp.at(i);
    cout << endl;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

int main()
{
  lli x;
  while (scanf("%lld", &x) != EOF)
  {
    lli ans = 1000LL * (x / 500LL);
    x = x % 500;
    ans += x / 5LL * 5LL;
    printf("%lld\n", ans);
  }
  return 0;
}

Measured memory_bytes: 256
s = input()

x = 0
count0 = 0
count1 = 0

for i in s:
    #if i == str(x):
     #   count0 += 1
    count0 = count0+1 if i==str(x) else count0
    x = int(not(x))

x = 1
for i in s:
    #if i == str(x):
    #    count1 += 1
    count1 = count1 + 1 if i == str(x) else count1
    x = int(not(x))

print(min(count0, count1))

Measured memory_bytes: 3188
import itertools
n,m,r=map(int,input().split())
rr=list(map(int,input().split()))
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])


ans=10**10
for i in itertools.permutations(range(0,r),r):
    kai=0
    for j in range(r-1):
        kai+=g[rr[i[j]]-1][rr[i[j+1]]-1]
    ans=min(ans,kai)
print(ans)

Measured memory_bytes: 47448
#pragma GCC optimize("O3")
//#pragma GCC target("avx")
#include <bits/stdc++.h>
using namespace std;
#define re return
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
#define fi first
#define se second
#define ss second.second
#define sf second.first
#define ff first.first
#define fs first.second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define PI 3.14159265358979323846
#define E 2.71828182845904523536
#define er erase
#define in insert
#define fo(i,n) for((i)=0;(i)<(n);(i)++)
#define ro(i,n) for((i)=n-1;(i)>=0;(i)--)
#define fr(i,j,n) for((i)=(j);(i)<(n);(i)++)
#define rf(i,j,n) for((i)=((n)-1);(i)>=(j);(i)--)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
    const int N=(int)1e5+100;
    const int M=(int)2e6+100;
    const int inf=(int)1e9+100;
#define filename ""
    int a[N];
    int d[N];
    int edge[2*N];
    vector<pair<int,int> > v[N];
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen(filename".in","r",stdin);
    //freopen(filename".out","w",stdout);
    //freopen("ans.txt","w",stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n,m,i,q,w;
    cin>>n>>m;
    set<pair<int,int> > s;
    fo(i,n)
    {
        cin>>a[i];
        s.in({a[i],i});
    }
    fo(i,m)
    {
        cin>>q>>w;
        q--;
        w--;
        v[q].pb({w,i});
        v[w].pb({q,i});
    }
    while(!s.empty())
    {
        int x=s.begin()->se;
        int c=s.begin()->fi;
        s.er(s.begin());
        bool f=0;
        for(auto y:v[x])
        {
            if (d[y.fi])
            {
                edge[y.se]=c;
                d[x]=3-d[y.fi];
                f=1;
                break;
            }
        }
        if (f) continue;
        f=1;
        for(auto y:v[x])
        {
            if (a[y.fi]==c)
            {
                d[x]=1;
                d[y.fi]=2;
                edge[y.se]=c;
                s.er({c,y.fi});
                f=0;
                break;
            }
        }
        if (f)
        {
            cout<<-1;
            re 0;
        }
    }
    fo(i,n)
    {
        if (d[i]==1)
        {
            cout<<'B';
        }
        else
        {
            cout<<'W';
        }
    }
    cout<<'\n';
    fo(i,m)
    {
        if (edge[i])
        {
            cout<<edge[i]<<'\n';
        }
        else
        {
            cout<<(int)1e9<<'\n';
        }
    }
}


Measured memory_bytes: 16640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i = (a); i < (b); i++)
#define iter(it,c) for(auto it = (c).begin(); it != (c).end(); ++it)
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
const ll INF = ~(1<<31);
#define fs first
#define sc second
#define pb push_back

const double EPS = 1e-9;
const double pi = acos(-1);
typedef unsigned long long ull;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
template <class T> T smod(T a, T b) {
    return (a % b + b) % b;
}

ll DP[105][100'050];

int main() {
    cin.sync_with_stdio(false);
    ll n,k;
    cin >> n >> k;
    vi A(n);
    rep(i,0,n) cin >> A[i];

    memset(DP,0,sizeof(DP));

    DP[0][0] = 1;

    ll md = 1000000000+7;

    for(ll i = 1; i <= n; i++) {

        vi PRE;
        PRE.pb(0);

        for(ll j = 0; j <= k; j++) {
            PRE.pb((PRE.back() + DP[i-1][j]) % md);
        }

        for(ll j = 0; j <= k; j++) {
            ll l = max(j-A[i-1],0ll), r = j;
            DP[i][j] = (PRE[r+1]-PRE[l]+md) % md;
        }
    }

    cout << DP[n][k] << endl;
    return 0;
}



Measured memory_bytes: 84200
#exec({'RUBY_THREAD_VM_STACK_SIZE'=>'100000000'},'/usr/bin/ruby', $0) if !ENV['RUBY_THREAD_VM_STACK_SIZE']

def inpf() a=gets.chomp.split(" ").map(&:to_f)end

def inps() a=gets.chomp.split(" ")end

def copy(a) Marshal.load(Marshal.dump(a)) end

def kaijo(n,r = 10**9+7)(n < 2)? 1 : (2..n).inject{|memo,u|memo=(memo*u)%r} end

def na(n,d=0) Array.new(n,d)end

def na2(n,m,d=0) Array.new(n){Array.new(m,d)}end

def na3(n,m,l,d=0) Array.new(n){Array.new(m){Array.new(l,d)}}end

def inp() a=gets.chomp.split(" ").map(&:to_i)end

def r_up(a, b) (a+b-1)/b end

def r_sort(a) a.sort{|a,b|b<=>a} end

a,b = inp
puts ((a+b).even?)? ((a+b)/2) : "IMPOSSIBLE"


Measured memory_bytes: 1788
import sys
sys.setrecursionlimit(3000)
import queue
h,w=map(int,input().split())
s=['#'*(w+2)]+['#'+input()+'#' for _ in [0]*h]+['#'*(w+2)]
l=[[0]*(w+2) for _ in [0]*(h+2)]
for i in range(h+2):
    for j in range(w+2):
        if s[i][j]=='#':
            l[i][j]=-1
L=queue.Queue()
L.put([1,1])
while not L.empty():
    n=L.get()
    for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
        if l[n[0]+dx][n[1]+dy]==0 and [n[0]+dx,n[1]+dy]!=[1,1]:
            l[n[0]+dx][n[1]+dy]=l[n[0]][n[1]]+1
            L.put([n[0]+dx,n[1]+dy])

if l[h][w]==0:print(-1)
else:print(h*w-l[h][w]-(sum(x.count('#') for x in s)-2*h-2*w-4)-1)

Measured memory_bytes: 3952
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define pb push_back
#define pp pop_back
#define pi pair<ll,ll>
#define pii pair<int,int>
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    ll n,i,j,k,l,m,b,t,sum,sum1,flag,max1,min1,tmp;
    cin>>n>>m>>j>>k;
    sum=n*j;
    sum1=n*k;
    b=m*j;
    l=m*k;
    cout<<max(max(sum,sum1),max(b,l))<<endl;;

}


Measured memory_bytes: 3648
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define MOD 1000000007
#define INIT -1

int main() {
	long long int a[7];
	for (int i = 0; i < 7; i++) {
		cin >> a[i];
	}
	long long int k = 0;
	k += 2 * (a[0] / 2);
	k += a[1];
	k += 2 * (a[3] / 2);
	k += 2 * (a[4] / 2);
	if (a[0] > 0 && a[3] > 0 && a[4] > 0) {
		long long int tmpk = 0;
		tmpk += 3;
		a[0]--;
		a[3]--;
		a[4]--;
		tmpk += 2 * (a[0] / 2);
		tmpk += a[1];
		tmpk += 2 * (a[3] / 2);
		tmpk += 2 * (a[4] / 2);
		k = max(k, tmpk);
	}

	cout << k << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
char s[MAXN],t[MAXN];
int n;
bool ok(int x){
	for(int i=0;i<n;i++)
		s[i]=t[i];
	int odd=0;
	for(int i=0;i+x-1<n;i++){
		if((s[i]-'0')^odd)
			odd^=1;		
		s[i]='0';	
	}
	if(odd){
		for(int i=n-x+1;i<n;i++){
			if(s[i]=='1')
				s[i]='0';
			else
				s[i]='1';
		}
	}odd=0;	
	for(int i=n-1;i-x+1>=0;i--){
		if((s[i]-'0')^odd)
			odd^=1;		
		s[i]='0';	
	}	
	if(odd){
		for(int i=n-x+1;i<n;i++){
			if(s[i]=='1')
				s[i]='0';
			else
				s[i]='1';
		}
	}
	for(int i=0;i<n;i++)
		if(s[i]=='1')
			return 0;
	return 1;		
}
int main(){
    //~ freopen("file.in", "r", stdin);
    scanf("%s",s);
    n=strlen(s);
    for(int i=0;i<n;i++)
		t[i]=s[i];
    int st=1,en=n;
    while(st+1<en){
		int mid=(st+en)>>1;
		if(ok(mid))
			st=mid;
		else
			en=mid;
	}
	if(ok(en))
		printf("%d\n",en);
	else
		printf("%d\n",st);
	return 0;
}


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

#define INF INT_MAX
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)

using namespace std;

class Node{
public:
	int index;
	bool used;	//????°???¨?????¨????????????????????????
	vector< pair<Node*,int> > road;	//first:?????°???????????????second:?????°?????????????????????
};

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

	int n,m;	//n:???????????°,m:??????????£?????????¶????????¬??°
	while(scanf("%d %d",&n,&m)  != EOF && n != 0){
		vector<Node> x;		//????°???¨?????¨(MST)
		vector<Node> t(n);	//??°????????¨???
		REP(i,n){t[i].index = i;t[i].used = false;}	//??????????????????????????£?????????
		int cost,a,b;
		REP(i,m){
			//cin >> a >> b >> cost;
			scanf("%d,%d,%d",&a,&b,&cost);
			t[a].road.push_back(make_pair(&t[b],cost));
			t[b].road.push_back(make_pair(&t[a],cost));
		}
		//???????????????????????????????????????a?????????MST???
		t[0].used = true;
		x.push_back(t[0]);
		//MST????????°?????¨?????????????????°n??????????????§??°?????????
		int ans = 0;
		while(x.size() < n){
			int min_cost = INF;
			Node* min_node;
			//?????¨???MST????????????MST??\???????????????????????°??????????°???????????????¨???????????¢???
			REP(i,x.size()){
				//?????????i???????????°????????¨??????????????????????°????????????????????????¢???
				REP(j,x[i].road.size()){
					if(x[i].road[j].first->used)continue;	//??????MST??????????????????????????´???
					if(min_cost > x[i].road[j].second){
						min_node = x[i].road[j].first;
						min_cost = x[i].road[j].second;
					}
				}
			}
			min_node->used = true;
			x.push_back(*min_node);	//????°???????????????¨???????????????????????????MST?????????
			ans += min_cost / 100 - 1;
		}
		cout << ans << endl;
		
	}

	return 0;
}

Measured memory_bytes: 3472
#include <iostream>
#include <chrono>
#include <cmath>
#include <string.h>
#include <iomanip>
#include <algorithm>
#include <unordered_set>
#include <vector>
#include <queue>

#define MAX(a, b) a > b ? a : b
constexpr auto NMAX = (int)1e5 + 20;

using namespace std;

typedef unsigned long long ull;

int a, b, c;

int main()
{
	cin >> a >> b >> c;
	cout << c << ' ' << a << ' ' << b;
	return 0;
}

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



signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);
    
    ll n,k;
    cin>>n>>k;
    if(n==1){
        cout << k << endl;
        return 0;
    }
    ll now = 1;
    ll cnt=0;
    while(now < k){
        now *=2;
        cnt++;
    }
    n = min(n,cnt);
    long long low=-1,up=k+1,mid;
    while(up-low>1){
        mid=(up+low)/2;
        ll now = mid;
        ll sum = 0;
        for(int i=0;i<n;i++){
            sum += now;
            now/=2;
        }
        if(sum <= k){
            low=mid;
        }
        else{
            up=mid;
        }
    }
    cout << low << endl;
}



Measured memory_bytes: 3208