akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<((int)(n));i++)
#define reg(i,a,b) for(int i=((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i=((int)(n))-1;i>=0;i--)
#define ireg(i,a,b) for(int i=((int)(b));i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int,int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))
#define iter(v,ite) for(auto ite=(v).begin();ite!=(v).end();ite++)
#define mimunum(v,x) distance((v).begin(),lower_bound((v).begin(),(v).end(),x))


int n;
lli gl,t;

lli dat[100005]={};
lli dp[100005]={};
lli qdp[100005]={};

lli inf = IINF*100LL;

int main(void){
	scanf("%d%lld%lld",&n,&gl,&t);
	reg(i,1,n){
		scanf("%lld",&dat[i]);
		qdp[i]=dp[i]=inf;
	}
	qdp[0]=inf;
	dat[0]=0;
	dp[0]=0;
	int sen=0;
	rep(i,n+1){
		//printf("dp[%d] .. %lld qdp[%d] .. %lld\n",i,dp[i],i,qdp[i]);
		dp[i] = min(dp[i],qdp[i]);
		qdp[i+1] = min(qdp[i+1],qdp[i]+2*(dat[i+1]-dat[i]));
		if(sen<=i)sen=i+1;
		//printf("%d %d\n",i,sen);
		while(sen<=n && 2*(dat[sen]-dat[i+1])<t){
			dp[sen]=dp[i]+t;
			sen++;
		}
		qdp[sen] = min(qdp[sen],2*(dat[sen]-dat[i+1])+dp[i]);
		dp[i+1]=min(dp[i+1],dp[i]+t);
		/*
		dp[i]=dp[i-1]+t;
		rep(j,i){
			dp[i]=min(dp[i],dp[j]+max(2*(dat[i]-dat[j+1]),t));
		}
		//printf("dp[%d] .. %lld\n",i,dp[i]);
		*/
	}
	
	printf("%lld\n",gl+dp[n]);
	
	
	return 0;
}






Measured memory_bytes: 2688
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c,d;
	cin>>a>>b>>c>>d;
	int s1=a+b,s2=c+d;
	if(s1>s2)
		cout<<"Left";
	else if(s1==s2)
		cout<<"Balanced";
	else
		cout<<"Right";
	return 0;
 } 

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ins insert
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
ll modfac(ll a){
    ll ans=1;
    while(a>1){
        ans*=a;
        ans%=1000000007;
        a--;
    }
    return ans;
}
ll modinv(ll a,ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}
struct UnionFind {
    vector<int> par;
    
    UnionFind(int n) : par(n, -1) {}

    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    ll a,b;cin >> a >>b;
    ll count=0;
    while(count<=2000){
        ll p=count;
        p*=8;
        p/=100;
        ll f=count;
        f*=10;
        f/=100;
        if(p==a&&f==b){
            cout << count <<endl;
            return 0;
        }
        count++;
    }
    cout << -1 <<endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())


S=input()
M=INTMAX
for i in range(len(S)-2):
    M=min(M,abs(int(S[i:i+3])-753))

print(M)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    int h,w;
    cin >> h >> w;
    char s[h + 50][w + 50];
    for(int i = 0;i < h;i++)
    {
        for(int j = 0;j < w;j++)
        {
            cin >> s[i][j];
        }
    }
    bool flag = true;
    for(int i = 0;i < h;i++)
    {
        for(int j = 0;j < w;j++)
        {
            if(s[i][j] == '#')
            {
                bool check = false;
                if(s[i - 1][j] == '#')
                {
                    check = true;
                }
                else if(s[i][j - 1] == '#')
                {
                    check = true;
                }
                else if(s[i][j + 1] == '#')
                {
                    check = true;
                }
                else if(s[i + 1][j] == '#')
                {
                    check = true;
                }
                if(!check)
                {
                    flag = false;
                    break;
                }
            }
        }
    }
    if(flag)
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
    int n ;
    scanf("%d",&n);
    int tot=0,odd=0;
    for(int i=1;i<=n;i++)
    {
        tot++;
        if(i%2==1)
            odd++;
    }
    double ans = (odd*1.0)/tot;
    printf("%.10lf",ans);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

int main()
{
    int A, B, C, K;
    std::cin >> A >> B >> C >> K;

    if (K <= A)
    {
        std::cout << K << std::endl;
    }
    else if (K <= A + B)
    {
        std::cout << A << std::endl;
    }
    else
    {
        std::cout << A - (K - A - B) << std::endl;
    }
}


Measured memory_bytes: 3620
R,G,B,N=[int(i) for i in input().split()]
num = 0
for i in range(N//R+1):
  for j in range(N//G+1):
#    print(i*R,j*G)
    if i*R+j*G<=N:
      if (N-i*R-j*G)%B==0:
#        print((N-i*R-j*G))
        num+=1
print(num)

Measured memory_bytes: 40556
use std::io::stdin;

fn main() {
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let n = st.trim().parse::<usize>().unwrap();
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let a:Vec<_> = st.trim().split(" ").map(|x| x.parse::<i64>().unwrap()).collect();
    let mut st = String::new();
    stdin().read_line(&mut st).unwrap();
    let b:Vec<_> = st.trim().split(" ").map(|x| x.parse::<i64>().unwrap()).collect();
    let mut x:i64 = 0;
    let mut y:i64 = 0;
    let mut c:i64 = 0;
    for i in 0..n {
        c += b[i] - a[i];
        if b[i] < a[i] {
            x += a[i]-b[i];
        } else {
            y += (b[i]-a[i]+1)/2;
        };
    };

    if c >= y {
        println!("Yes");
    } else {
        println!("No");
    }
}


fn bisec(v:&Vec<i64>, num:&i64) -> usize {
    let mut l:usize = 0;
    let mut r = v.len() as usize;
    let mut m = (l+r)/2 as usize;
    while l < r {
        if num <= &v[m] {
            r = m;
        } else {
            l = m+1;
        };
        m = (l+r)/2;
    };
    l
}

fn max (a:&i64, b:&i64) -> i64 {
    if a < b {
        *b
    } else {
        *a
    }
}

fn min (a:&i64, b:&i64) -> i64 {
    if a > b {
        *b
    } else {
        *a
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
double n[100005];
double f[3005][3005];
double r; 
int main()
{ 
    int b;
    cin >> b;
    for(int i = 1; i <= b; i++)
    {
        cin >> n[i];
    }
    f[0][0] = 1;
    for(int i = 1; i <= b; i++)
    {
        f[i][0] = f[i-1][0] * (1-n[i]);
    }
    for(int i = 1; i <= b; i++)
    {
        for(int j = 1; j <= i; j++)
        {
            f[i][j] = n[i] * f[i-1][j-1] + f[i-1][j] * (1-n[i]);
        }
    }
    for(int i = 1; i <= b; i++)
	{ 
	    if(2*i > b) 
	    {
		    r += f[b][i];
	    } 
    }
	cout << fixed << setprecision(20) << r << endl;
}


Measured memory_bytes: 68992
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main()
{
	int N, K;
	cin >> N >> K;
	vector<int> p(N);
	for (auto& x : p) {
		cin >> x;
	}
	sort(p.begin(), p.end());

	int ans = accumulate(p.begin(), p.begin() + K, 0);
	cout << ans << endl;
}


Measured memory_bytes: 3632
#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 x, y; cin >> x >> y;
    for (ll i = 0; i <= x; i++) {
        if (2 * i + (x - i) * 4 == y) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
    return 0;
}


Measured memory_bytes: 3652
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int M = sc.nextInt();
    int resultEven =0;
    int resultOdd=0;
    if(N>1){
      resultEven=nCr(N,2);
    }
    if(M>1){
      resultOdd=nCr(M,2);
    }
    
    int result=resultEven+resultOdd;
    
    
    System.out.println(result);
  }
  static int nCr(int n, int r) 
{ 
    return (n*(n-1))/2;
} 
  
// Returns factorial of n 
 
}


Measured memory_bytes: 20948
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
inline int xmod(int a, int b) {
    int ret = a % b;
    return (ret >= 0) ? ret : ret + b;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;

    int len=1000050;
    vector<int> li(len);
    int fi=0, la=0;

    string op;
    int key;
    for (int i=0; i<n; ++i) {
        cin >> op;
        if (op == "insert") {
            cin >> key;
            fi = xmod(fi-1, len);
            li[fi] = key;
            continue;
        } else if (op == "deleteFirst") {
            fi = (fi+1) % len;
        } else if (op == "deleteLast") {
            la = xmod(la-1, len);
        } else if (op == "delete"){
            cin >> key;
            for (int j=fi; j!=la; j=(j+1)%len) {
                if (li[j] == key) {
                    li[j] = -1;
                    break;
                }
            }
        }
        while (li[fi] == -1) fi = (fi+1) % len;
        while (li[xmod(la-1, len)] == -1) la = xmod(la-1, len);
    }

    bool nospace = true;
    for (int i=fi; i!=la; i=(i+1)%len) {
        if (li[i] == -1) continue;
        if (nospace) {
            cout << li[i];
            nospace = false;
        } else {
            cout << " " << li[i];
        }
    }
    cout << endl;
    return 0;
}

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

int main() {
  string S;
  cin >> S;
  
  int color[S.size()];
  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) == '0') {
      color[i] = 0;
    } else {
      color[i] = 1;
    }
  }
  
  int start = 0;
  if (color[0] == 1) {
    start = 1;
  }
  
  int next = start;
  int cnt1 = 0;
  for (int i = 0; i < S.size(); i++) {
    if (color[i] == next) {
    } else {
      cnt1++;
    }
    if (next == 0) {
      next = 1;
    } else {
      next = 0;
    }
  }
  
  cout << cnt1 << endl;
}


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

int main() {
  string s;
  cin >> s;
  rep(i,s.size()-1){
    if(s[i] == s[i+1]) {
      cout << "Bad" << endl;
      return 0;
    }
  }
  cout << "Good" << endl;       
  return 0;
}


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

long long a, b, x;
 
int main()
{
	cin >> x;
	for (a = 0; a <= 1000; a++)
		for (b = -1000; b <= 1000; b++)
			if (a * a * a * a * a - b * b * b * b * b == x)
			{
				cout << a << " " << b << endl;
				exit(0);
			}
	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(), (x).end())
#define ALL(x) (x).begin(), (x).end()
#define rep(i, n) for (ll i = 0; i < n; i++)
#define reps(i, m, n) for (ll i = m; i < n; i++)
#define repr(i, m, n) for (ll i = m; i >= n; i--)
template <class T> bool maxi(T &a, const T &b) {
    if (a < b) { a = b; return 1;} return 0;}
template <class T> bool mini(T &a, const T &b) {
    if (b < a) { a = b; return 1;} return 0;}
#define dame {cout<< "No" <<"\n"; return;}
#define INF2 1000000000000000037
#define INF  1000000007
#define MOD  1000000007
#define PI (acos(-1))
using namespace std;
using ll = long long;
using ld = long double;
using P  = pair<ll,ll>;
//--GLOBAL---------------------------------
ll GCD(ll a, ll b) {
    if(a==-1) return b;
    return ( b==0 or b==-1 ? a : GCD(b, a%b) );
    //if (b == 0) return a; else return GCD(b, a%b);
}
//--MAIN-----------------------------------
void Main() {
    ll N,K; cin>>N>>K;
    vector<ll> A(N);
    rep(i,N) cin>>A[i];
    ll now=-1;
    rep(i,N) now=GCD(now,A[i]);
    if(K%now or *max_element(ALL(A))<K) cout<< "IMPOSSIBLE"<<"\n";
    else cout<< "POSSIBLE"<<"\n";
}
//--START----------------------------------
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
}
//-----------------------------------------


Measured memory_bytes: 1024
#include "bits/stdc++.h"

#define rep(i,n) for(int i = 0;i<n;i++)
#define vv(Type,Name, n,m,d) vector<vector<Type>> Name (n, vector<Type>(m, d));

using namespace std;
using ll = long long;

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

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(0);

	int h, w;
	cin >> h >> w;

	vector<string> maze(h + 2);

	vv(int, a, h + 2, w + 2, -1);

	rep(i, h) {
		string str;
		cin >> str;
		maze[i + 1] = '#' + str + '#';
	}

	rep(i, w + 2) {
		maze[0] += '#';
		maze[h + 1] += '#';
	}

	// set startpoint;
	pair<int, int> start;
	int ans = 0;
	rep(i, h + 2)rep(j, w + 2) {
		if (maze[i][j] == '.') {
			start = make_pair(i, j);
			queue<pair<int, int>> q;
			q.push(make_pair(start.first, start.second));
			int longest = 0;
			a[i][j] = 0;
			while (!q.empty()) {
				int x = q.front().first;
				int y = q.front().second;

				q.pop();

				if (longest < a[x][y]) {
					longest = a[x][y];
				}

				rep(k, 4) {
					int hx = x + dx[k];
					int hy = y + dy[k];
					if (maze[hx][hy] == '.' && a[hx][hy] == -1) {
						q.push(make_pair(hx, hy));
						a[hx][hy] = a[x][y] + 1;
					}
				}
			}

			rep(ii, h + 2)rep(jj, w + 2) a[ii][jj] = -1;
			ans = max(longest, ans);
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 3624
#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int x;cin>>x;
  ll num=1;
  ll ma=1;
  ll count=0;

  for(ll i=2;i<x;i++){
    num=i;
    count=0;
    while(num<=x){
      num*=i;
      count++;
    }
    if(count>1)ma=max(ma,num/i);
  }
  out(ma);
  return 0;
}


Measured memory_bytes: 256
import itertools

h, w = map(int, input().split())
s = [input() for _ in range(h)]

diffs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
t = [[0] * w for _ in range(h)]
group = 1
for i, j in itertools.product(range(h), range(w)):
    if t[i][j] != 0:
        continue

    stack = [(i, j)]
    while stack:
        x, y = stack.pop()
        t[x][y] = group
        for dx, dy in diffs:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < h and 0 <= ny < w and t[nx][ny] == 0 and s[x][y] != s[nx][ny]:
                stack.append((nx, ny))
    group += 1

d = [[0] * 2 for _ in range(group)]
for i, j in itertools.product(range(h), range(w)):
    d[t[i][j]][0 if s[i][j] == '.' else 1] += 1

ans = sum(d[i][0] * d[i][1] for i in range(len(d)))
print(ans)

Measured memory_bytes: 59996
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
ll x, y, z, k;
vector<ll> a;
vector<ll> b;
vector<ll> c;
vector<ll> ab;

bool check(ll num){

    ll res = 0;
    for(int i = 0; i < c.size(); i++){
        auto itr = upper_bound(ab.begin(), ab.end(), num - c[i]);
        ll idx = itr - ab.begin();
        idx = ab.size() - idx;
        res += idx;

    }
    return res < k;
}

int main(void){
    cin >> x >> y >> z >> k;
    a.resize(x);
    b.resize(y);
    c.resize(z);
    for(int i = 0; i < x; i++) cin >> a[i];
    for(int i = 0; i < y; i++) cin >> b[i];
    for(int i = 0; i < z; i++) cin >> c[i];

    sort(a.begin(), a.end(), greater<ll>());
    sort(b.begin(), b.end(), greater<ll>());
    sort(c.begin(), c.end(), greater<ll>());

    for(int i = 0; i < x; i++){
        for(int j = 0; j < y; j++){
            ab.push_back(a[i] + b[j]);
        }
    }

    sort(ab.begin(), ab.end());

    ll ok = INF;
    ll ng = 0;
    while(abs(ok - ng) > 1){
        ll mid = (ok + ng) / 2;
        if(check(mid)){
            ok = mid;
        } else {
            ng = mid;
        }
        //cout << ok << " " << ng << endl;
    }

    reverse(ab.begin(), ab.end());

    //cout << "ok" << ok << endl;
    vector<ll> ans;
    for(int i = 0; i < z; i++){
        for(int j = 0; j < ab.size(); j++){
            if(ok < ab[j] + c[i]) ans.push_back(ab[j] + c[i]);
            else break;
        } 
    }

    while(ans.size() < k) ans.push_back(ok);

    sort(ans.begin(), ans.end(), greater<ll>());
    for(int i = 0; i < k; i++){
        cout << ans[i] << endl;
    }
}

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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;
template <class T> using vec = vector<T>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  ll w, a, b;
  cin >> w >> a >> b;

  if (a + w < b) {
    put(b - (a + w));
    return 0;
  }

  if (b + w < a) {
    put(a - (b + w));
    return 0;
  }

  put(0);
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) {
  T c = min(a, b), d = max(a, b);
  return c * (d / gcd(c, d));
}

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


Measured memory_bytes: 256
LIM = 50001
 
# prepare primes
 
is_prime = [True for _ in range(LIM)]
 
is_prime[0] = is_prime[1] = False
 
# sieve of eratosthenes
for x in range(LIM//2 + 1):
    if is_prime[x]:
        for y in range(x*x, LIM, x):
            is_prime[y] = False
 
primes = [x for x in range(LIM) if is_prime[x]]
 
# END `prepare primes`
 
count_arr = [0 for x in range(LIM)]
 
len_primes = len(primes)
 
for x in range(len_primes):
    p = primes[x]
    for y in range(x, len_primes):
        q = primes[y]
        if p+q >= LIM:
            break
        count_arr[p+q] += 1
 
while True:
    n = int(input())
    if n == 0:
        break
    print(count_arr[n])


Measured memory_bytes: 6976
<?php
  list($n) = explode(" ", trim(fgets(STDIN)));

  if($n[0]==$n[1] && $n[1] == $n[2]){
    echo "Yes";
  }else if($n[2]==$n[3] && $n[1] == $n[2]){
    echo "Yes";
  }else{
    echo "No";
  }

Measured memory_bytes: 16228
/*
  Compete against Yourself.
  Author - Aryan Choudhary (@aryanc403)
*/

#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize ("-ffloat-store")

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

clock_t time_p=clock();
void aryanc403()
{
#ifdef ARYANC403
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
#endif
}

#ifdef ARYANC403
#include "/home/aryan/codes/PastCodes/header.h"
#else
    #define dbg(args...)
#endif

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
mt19937 rng(seed=chrono::steady_clock::now().time_since_epoch().count());
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt==m.end())         m.insert({x,cnt});
    else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
    auto jt=m.find(x);
    if(jt->Y<=cnt)            m.erase(jt);
    else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
    return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

    lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
    lli m;
    string s;
    vi a;
    //priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    // freopen("txt.in", "r", stdin);
    // freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
// cin>>T;while(T--)
{
    vi a;
    a={31,28,31,30,31,30,31,31,30,31,30,31};
    cin>>n>>m;
    n--;
    cout<<(a[n]==m)<<endl;

}   aryanc403();
    return 0;
}

Measured memory_bytes: 256
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　redcoderになるためAtCoderを巡る旅をしてます。

　　　 　 ＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　 ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣/ヽ
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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

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

    ll q, h, s, d, n; cin >> q >> h >> s >> d >> n;
    ll ans = 1e9;
    if(n == 1) {
        ans = min(q * 4, min(h * 2, s));
        cout << ans << endl;
        return 0;
    }
    ll q_l = q * 4, h_l = h * 2, s_l = s, d_l = d / 2;
    ll mixi = d_l;
    if(mixi > q_l || mixi > h_l || mixi > s_l) {
        ans = min(q_l, min(h_l, s_l)) * n;
    } else {
        ans = d * (n / 2);
        ans += min(q_l, min(h_l, s_l)) * (n % 2);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
using namespace std;

int main(){
  int counter[26] = {};
  char ch;

  for (; cin >> ch;){

    int num = tolower(ch) - 'a';
    if(0 <= num && num <= 25){
      counter[num] += 1;
    }
  }

  for (int i = 0; i <= 25; i++){
    char al = i + 'a';
    cout << al << " : " << counter[i] << endl;
  }

  return 0;
}

Measured memory_bytes: 3056
import bisect
A, B, C, D, E, F = map(int, input().split())
water = []
sugar = []

for i in range(F//(100*A)+1):
  for j in range(F//(100*B)+1):
    if 100*A*i + 100*B*j <= F:
      water += [100*A*i + 100*B*j]

water = list(set(water))

for i in range(F//C+1):
  for j in range(F//D+1):
    if C*i + D*j <= F:
      sugar += [C*i + D*j]

sugar = list(set(sugar))
sugar = sorted(sugar)
ans_sw = 0
ans_s = 0
ans = 0
for w in water:
  s = min((E/100)*w, F-w)
  idx = bisect.bisect_right(sugar, s)
  if w + sugar[idx-1] == 0:
    continue
  conc = (sugar[idx-1]/(w+sugar[idx-1]))*100
  if ans < conc:
    if sugar[idx-1] <= (E/100)*w and sugar[idx-1] + w <= F:
      ans = conc
      ans_sw = w + sugar[idx-1]
      ans_s = sugar[idx-1]
if ans_sw == 0:
  ans_sw = 100*A
print(ans_sw, ans_s)

Measured memory_bytes: 86480
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

N, M, X = map(int, input().split())
C = []
A = []
for i in range(N):
    line = list(map(int, input().split()))
    C.append(line[0])
    A.append(line[1::])

min_price = 100000000000
for i in range(2 ** N):
    price = 0
    understand = [0] * M
    for j in range(N):  # このループが一番のポイント
        if ((i >> j) & 1):  # 順に右にシフトさせ最下位bitのチェックを行う
            price += C[j]
            for k, u in enumerate(A[j]):
                understand[k] += u

    if min(understand) >= X:
        min_price = min(min_price, price)

if min_price == 100000000000:
    print(-1)
else:
    print(min_price)


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

int n;

int main(void){
	while(cin >> n,n){
		set<string> member[100];
		string group[100];
		for(int i=0;i<n;i++){
			string tmp;
			cin >> tmp;
			size_t cur=0,pre=0;
			while(tmp[cur]!=':')
				cur++;
			group[i]=tmp.substr(pre,cur-pre);
			pre=cur+1;
			while(tmp[cur]!='.'){
				while(tmp[cur]!=','&&tmp[cur]!='.')
					cur++;
				member[i].insert(tmp.substr(pre,cur-pre));
				pre=cur+1;
				if(tmp[cur]!='.')
					cur++;
			}		
		}
	//for(set<string>::iterator it=group.begin();it!=group.end();it++)
	//	cout << *it << endl;
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				if(member[0].find(group[j])!=member[0].end()){
					member[0].erase(group[j]);
					member[0].insert(member[j].begin(),member[j].end());
				}
			}
		}
		cout << member[0].size() << endl;
	}	
	return 0;
}

Measured memory_bytes: 1360
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
using namespace std;
int main(){
    int n,k;
    cin >> n >> k;
    string str[k];
    map<char,long> mp;
    cin >> mp['s'] >> mp['p'] >> mp['r']; 
    string s;
    cin >> s;
    rep(i,n){
        str[i%k]+=s[i];
    }
    long long ans = 0;
    //cout << str[0] << " " << str[1] << endl;
    rep(i,k){
        long streak = 1;
        rep(j,str[i].size()-1){
            if(str[i][j]==str[i][j+1]) streak++;
            else{          
                ans+=((streak+1)/2)*mp[str[i][j]];
                streak=1;
            }
        }
        ans+=((streak+1)/2)*mp[str[i][str[i].size()-1]];  
        //cout << ans << endl;      
    }
    cout << ans << endl;
}

Measured memory_bytes: 5120
// LNU_Algotesters
#include <iostream>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <iterator>
#include <bitset>
#include <ctime>
#include <fstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for (int i = (a); i < (b); i++)
#define RFOR(i,b,a) for (int i = (b) - 1; i >= (a); i--)
#define ITER(it,a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a,value) memset(a, value, sizeof(a))

#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL) INF;
const int MAX = 100 * 1000 + 47;

VI G[MAX];
int D[MAX];


int DFS(int v, int p, int k)
{
    int res = 0;
    D[v] = 1;
    FOR(i, 0, SZ(G[v]))
    {
        int to = G[v][i];
        res += DFS(to, v, k);
        D[v] = max(D[v], D[to] + 1);
    }
    if (D[v] == k && p)
    {
        D[v] = 0;
        res++;
    }
    return res;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int n, k;
    scanf("%d%d", &n, &k);
    int ans = 0;
    FOR(i, 0, n)
    {
        int x;
        scanf("%d", &x);
        --x;
        if (!i)
        {
            if(x)ans++;
            continue;
        }
        G[x].PB(i);
    }
    //cout << "*" << endl;
    ans += DFS(0, 0, k);
    cout << ans << endl;
    
    return 0;
}



Measured memory_bytes: 13952
N = int(input())
ans = 0
if N >= 1 and N <= 9:
    ans = N
    print(ans)
    exit()

ans += 9
if N >= 10 and N <= 99:
    print(ans)
    exit()

if N >= 100 and N <= 999:
    ans += N - 99
    print(ans)
    exit()

ans += 999 - 99
if N >= 1000 and N <= 9999:
    print(ans)
    exit()


if N >= 10000 and N <= 99999:
    ans += N - 9999
    print(ans)
    exit()

ans += 99999 - 9999
if N == 100000:
    print(ans)







Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;   
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define ll long long int
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define sz(x) (ll)x.size() 

ll power(ll x,ll y,ll p) 
{ 
    ll res = 1;      
    x = x % p;  
    while (y > 0) 
    { 
        if (y & 1) 
            res = (res*x) % p; 
        y = y>>1; 
        x = (x*x) % p;   
    } 
    return res; 
} 

int main()
{
    ios_base::sync_with_stdio(false);
	ll n,i,j,k,x,y,t,m;

	cin >> x >> y;
	cout<<(x*y)/__gcd(x,y)<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m;
int main(void){
    while(1){
        int ans = 0;
        cin >> n >> m;
        if(n == 0 && m == 0) break;
        vector<int> a(n);
        for(int i = 0;i < n;i++) cin >> a[i];
        
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                if(i == j) continue;
                if(a[i]+a[j] <= m)ans = max(ans,a[i]+a[j]);
            }
        }
        if(ans == 0) cout << "NONE" << endl;
        else cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define plll pair<ll,pll>
#define ppll pair<pll, pll>
#define pii pair<int, int> 
#define pb push_back
#define mod 1000000007
#define N 2000007
ll power(ll a,ll b){
    ll res=1ll;
    while(b>0){
        if(b%2!=0) res=(res*a)%mod;
        a=(a*a)%mod;
        b/=2;
    }
    return res%mod;
}
ll ncr(ll n,ll k){
    if(k>n-k) k=n-k;
    ll pro=1;
    for(ll i=0;i<k;i++){
        pro=(pro*(n-i))%mod;
        pro/=(i+1);
    }
    return (pro)%mod;
}

void swap(ll *a,ll *b) {
    ll temp=*a;
    *a=*b;
    *b=temp;
}
vector<ll> prime;
void seive(){
    vector<bool > isprime(1000001,true);
    for(int i=2;i*i<=1000000;i++){
        if(isprime[i]){
            for(int j=i*i;j<=1000000;j+=i){
                isprime[j]=false;
            }
        }
    }
    for(int i=2;i<=1000000;i++){
        if(isprime[i]) prime.push_back(i);
    }
}
vector<ll> parent;
ll find(ll p) {
    if(parent[p]==p) return parent[p];
    return parent[p]=find(parent[p]); 
}
void unun(ll a,ll b) {
    ll r1=find(a);
    ll r2=find(b);
    if(r1!=r2) parent[r2]=r1;
}
void solve() {
    ll n;
    cin>>n;
    if(n==0) {
        cout<<0<<" "<<0<<"\n";
        return ;
    }
    set<ll> dp;
    map<ll,ll> mp;
    for(ll i=0;i<4e3;i++) {
        ll val=i*i*i*i*i;
        dp.insert(val);
        mp[val]=i;
    }
    if(dp.find(n)!=dp.end()) {
        ll x=mp[n];
        cout<<x<<" "<<0;
        return ;
    }
    for(auto itr: dp) {
        ll rem=itr-n;
        if(dp.find(rem)!=dp.end()) {
            ll x=mp[itr];
            ll y=mp[rem];
            cout<<x<<" "<<y;
            return ;
        }
        if(rem<0) {
            for(ll i=-1;i>=(-4e3);i--) {
                ll val=(i*i*i*i*i);
                if(val==rem) {
                    cout<<mp[itr]<<" "<<i;
                    return ;
                }
            }
        }
    }
}   


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

}


Measured memory_bytes: 4100
import sys

def input():
    return sys.stdin.readline().rstrip()

if __name__ == "__main__":
    n = int(input())
    pl = list(map(int, input().split()))

    pl_sorted = sorted(pl)

    diff_count = 0
    for i in range(n):
        if pl[i] != pl_sorted[i]:
            diff_count += 1

    print("YES" if diff_count == 0 or diff_count == 2 else "NO")


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

int main() {
  int d, g;
  cin >> d >> g;

  vector<int> p(d);
  vector<int> c(d);

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

  int ans = 100000;
  for(int bit = 0; bit < (1 << d); bit++){
    int k = 0;
    int point = 0;
    vector<bool> used(d);

    for(int i = 0; i < d; i++){
      if(bit & (1 << i)){
        k += p[i];
        point += 100*(i+1)*p[i];
        point += c[i];
        used[i] = true;
      }
    }

    if(point < g){
      int i = d-1;
      while(point < g){
        if(used[i] == false){
          for(int j = 0; j < p[i]-1; j++){
            if(point >= g) break;

            point += 100*(i+1);
            k++;
          }
        }

        i--;
        if(i < 0){
          break;
        }
      }
    }

    if(point >= g){
      ans = min(ans, k);
    }
  }

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

Measured memory_bytes: 3592
#include <iostream>
#include <ctype.h>

using namespace std;

int main(){
    string s;
    getline(cin,s);
    for(int i=0;i<s.length();i++){
        if(islower(s[i])){
            s[i]=toupper(s[i]);
        }else if(isupper(s[i])){
            s[i]=tolower(s[i]);
        }
    }
    cout<<s<<endl;;
}

Measured memory_bytes: 1184
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n=sc.nextInt();
		long h=sc.nextLong();
		long[] a=new long[n];
		long[] b=new long[n];
		long max=0;
		for(int i=0;i<n;i++){
			a[i]=sc.nextLong();
			b[i]=sc.nextLong();
			max=Math.max(max, a[i]);
		}
		
		Arrays.sort(b);
		long cnt=0;
		int k=n-1;
		while(k>=0 && b[k]>max && h>0){
			h-=b[k]; k--; cnt++;
		}
		if(h>0){
			cnt+=h/max;
			if(h%max!=0)cnt++;
		}
		System.out.println(cnt);		
	}	
}


Measured memory_bytes: 66068
<?php
 	fscanf(STDIN, "%s", $toi);
	fscanf(STDIN, "%s", $str);

    $arr1 = str_split($toi);
    $arr2 = str_split($str);
	$ans = 0;

	for($i=0; $i < 3; $i++){
    	if(strcmp($arr1[$i],$arr2[$i])==0 ){
          $ans++;
        }
    }
    echo $ans;
  
  
  ?>

Measured memory_bytes: 3828
#include<stdio.h>

int main(void)
{
	int a,b,x;
	
	scanf("%d %d %d",&a,&b,&x);
	
	if( x>(a+b) ){
		printf("NO\n");
	}else if(a > x){
		printf("NO\n");
	}else{
		printf("YES\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
N, X = map(int, input().split())


P, H = [1], [1]
for i in range(50):
    P.append(P[-1] * 2 + 1)
    H.append(H[-1] * 2 + 3)


def dfs(n, x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0

    elif 1 < x <= H[n - 1] + 1:
        return dfs(n - 1, x - 1)

    elif x == H[n - 1] + 2:
        return P[n - 1] + 1

    elif H[n - 1] + 2 < x <= 2 * H[n - 1] + 2:
        return P[n - 1] + 1 + dfs(n - 1, x - H[n - 1] - 2)

    elif x == 2 * H[n - 1] + 3:
        return 2 * P[n - 1] + 1


print(dfs(N, X))



Measured memory_bytes: 3064
n = int(input())
d, x = list(map(int, input().split()))

choco = []
while True:
	try:
		choco.append(int(input()))
	except EOFError:
		break

choco = [i * x + 1 for i in range(d) for x in choco if i * x + 1 <= d]

print(x + len(choco))


Measured memory_bytes: 9028
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

int main(){
  int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
  int N, n, d;
  while(scanf("%d", &N) && N){
    vector<pair<int, int> >sq(N);
    sq[0] = make_pair(0,0);
    REP(i, 1, N){
      scanf("%d%d", &n, &d);
      sq[i] = make_pair(sq[n].F+dy[d], sq[n].S+dx[d]);
    }
    int xmax = 0, ymax = 0, xmin = INF, ymin = INF;
    rep(i, N){
      xmax = max(xmax, sq[i].S); xmin = min(xmin, sq[i].S);
      ymax = max(ymax, sq[i].F); ymin = min(ymin, sq[i].F);
    }
    //    rep(i, N) printf("%d %d\n", sq[i].F, sq[i].S);
    printf("%d %d\n", abs(xmax-xmin)+1, abs(ymax-ymin)+1);
  }
  return 0;
}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int n;cin>>n;
    vector<P> d(n);
    rep(i,n){
        cin>>d.at(i).first;
        d.at(i).second=i+1;
    }
    sort(ALL(d));
    
    rep(i,n){
        cout<<d.at(i).second<<" ";
    }
    
    return 0;
}

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

int A[100000];

int partition(int p, int r)
{
	int x = A[r];//???????????????????????????????´????
	int i = p - 1;//x??\??????????´????????°??????????
	
	//j???x????????§??????????´????????°??????????
	for (int j = p; j < r; j++) {
		if (A[j] <= x) {
			i++;
			swap(A[j], A[i]);
		}
	}
	swap(A[i + 1], A[r]);
	return i + 1;
}

int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &A[i]);
	}
	int r = partition(0, n - 1);

	for (int i = 0; i < n; i++) {
		if (i) printf(" ");
		if (i == r) printf("[%d]", A[i]);
		else printf("%d", A[i]);
	}
	printf("\n");
	return 0;
}

Measured memory_bytes: 1580
#include <stdio.h>
#include <math.h>
int main(void) {
	// your code goes here
	int a[60],n,i;
	scanf("%d",&n);
	a[1]=11;
a[2]=31;
a[3]=41;
a[4]=71;
a[5]=101;
a[6]=131;
a[7]=151;
a[8]=181;
a[9]=191;
a[10]=211;
a[11]=241;
a[12]=251;
a[13]=271;
a[14]=281;
a[15]=311;
a[16]=331;
a[17]=401;
a[18]=421;
a[19]=431;
a[20]=461;
a[21]=491;
a[22]=521;
a[23]=541;
a[24]=571;
a[25]=601;
a[26]=631;
a[27]=641;
a[28]=661;
a[29]=691;
a[30]=701;
a[31]=751;
a[32]=761;
a[33]=811;
a[34]=821;
a[35]=881;
a[36]=911;
a[37]=941;
a[38]=971;
a[39]=991;
a[40]=1021;
a[41]=1031;
a[42]=1051;
a[43]=1061;
a[44]=1091;
a[45]=1151;
a[46]=1171;
a[47]=1181;
a[48]=1201;
a[49]=1231;
a[50]=1291;
a[51]=1301;
a[52]=1321;
a[53]=1361;
a[54]=1381;
a[55]=1451;
for(i=1;i<=n;i++){
	printf("%d ",a[i]);
}
printf("\n");
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define out(a) printf("%lld ",a)
using namespace std;
int a,b;
int read()
{
	int s=0,t=1; char c;
	while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
	return s*t;
}
int main()
{
	a=read(),b=read();
	if (a<=8&&b<=8) puts("Yay!");
	else puts(":(");
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cstdio>
#include <string>
#include <cmath>
#include <algorithm>
#include <climits>
#define ll long long
#define MAX 25 * 1e13
#define N  200010

using namespace std;
int MOD = 1000000007;

vector<ll> bitree(N);
int n;
int lowbit(int t){
  return t & (-t);
}

ll query(int h){
  ll ret = 0;
  for(int i = h ; i ; i -= lowbit(i)){
    ret = max( ret , bitree[i]);
  }
  return ret;
}

void update(int h,ll v){
  for(int i = h ; i <= n ; i += lowbit(i) ){
    bitree[i] = max( bitree[i] , v );
  }  
}

int main(){
    cin >> n;
    ll ret = 0;
    vector<int> h(n+1);
    vector<int> val(n+1);
    for(int i = 0 ; i < n ; i++ ){
      cin >> h[i];
    }
    for(int i = 0 ; i < n ; i++ ){
      cin >> val[i];
    }
    for(int i = 0 ; i < n ; i++){
      ll m = query(h[i]);
      ret = max(m + val[i] ,ret);
      update(h[i],m+val[i]);
    }
    cout << ret << endl;
    return 0;
}


Measured memory_bytes: 3328
#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int a,b,c;
    cin >> a >> b;
    if(b < 10 and a < 10 ){ c = a*b;}
    else{ c = -1;}


    // 出力
    cout << c;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;
using P = pair<int,int>;
#define MOD 1000000007
#define INF 1000000

int main()
{
  int N;cin>>N;
  N=N%10;
  if (N==2 || N==4 || N==5 || N==7||N==9)
  {
   cout<<"hon"<<endl; 
  }
  else if (N==0||N==1||N==6||N==8)
  {
    cout<<"pon"<<endl; 
  }
  else 
  {
    cout<<"bon"<<endl; 
  }
 
}

Measured memory_bytes: 3624
#include <iostream>
#include <map>

using namespace std;

long lcm(long a, long b){
    if(b>a){
        long t = a;
        a = b;
        b = t;
    }

    long sa = a;
    long sb = b;

    long r = 1;
    while(r!=0){
        r = a % b;
        a = b;
        b = r;
    }

    long gcd = a;

    return sa * sb / gcd; //最小公倍数をお返し

}

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

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

    long lm = 1;
    for(int i=0; i<N; i++){
        long tlm = lcm(lm, a[i]/2);
        lm = tlm;
    }

    int cnt,pcnt;
    bool fl = true;
    for(int i=0; i<N; i++){
        if(i != 0) pcnt = cnt;
        cnt = 0;
        while(a[i]%2 != 1){
            a[i] /= 2;
            cnt++;
        }
        if(i==0) continue;
        if(cnt != pcnt){
            fl = false;
            break;
        }
    }

    long ans = (M/lm+1)/2;

    if(fl) cout << ans << endl;
    else cout << 0 << endl;

    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = 999999999;

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

    string s;
    cin >> s;
    REP(i, s.size()-1){
        if(s[i] == s[i+1]){
            cout << i+1 << " " << i+2 << "\n";
            return 0;
        }else if(i < s.size()-2 && s[i] == s[i+2]){
            cout << i+1 << " " << i+3 << "\n";
            return 0;
        }
    }
    cout << "-1 -1" << "\n";
    return 0;
}

Measured memory_bytes: 512