akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
//----***やべーやつら***----
using namespace std;
#define int long long

//----***型定義***----
using ll = long long;
using P = pair<int,int>;

//----***Like a Pythonista***----
#define REP(ii,jj,nn) for (ll ii=jj;ii<(nn);ii++)
#define RREP(ii,nn,jj) for (ll ii = nn; jj<ii;ii--)
#define each(i,...) for (auto&& i:__VA_ARGS__)
#define ALL(vec) (vec).begin(),(vec).end()
#define sum(...) accumulate(ALL(__VA_ARGS__),0LL)
#define dsum(...) accumulate(ALL(__VA_ARGS__),0.0)
#define vec(type,name,...) vector<type> name(__VA_ARGS__)
template<class T> inline auto max(const T& a){ return *max_element(ALL(a)); }
template<class T> inline auto min(const T& a){ return *min_element(ALL(a)); }
inline ll gcd(ll a,ll b){if(b == 0) return a;return  gcd(b,a%b);}
inline ll lcm(ll a,ll b){ll g = gcd(a,b);return a / g * b;}

//----***定数***----
#define MOD 1000000007
#define INF 100000000000000000
#define EPS 1e-9
const vector<vector<int>> DXY={{-1,0},{1,0},{0,-1},{0,1}};

//----***パーツ***----
#define fr first
#define se second

//----***入出力***---
#define print(out) cout<< out  << "\n";
#define debug(var)  do{std::cerr << #var << " ↓ "<<"\n";view(var);}while(0);
#define dbg cerr<<"🥺🥺🥺🥺🥺🥺"<<endl;
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }

//----***初期時読み込み***----
struct initial{initial(){cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(15);};}initial_;


string S;

signed main(){
  int A,B,C,D;
  cin>>A>>B>>C>>D;
  while(A>0&&C>0){
    C-=B;
    if(C<=0){
      print("Yes")
      return 0;
    }
    A-=D;
    if(A<=0){
      print("No")
      return 0;
    }

  }


}


Measured memory_bytes: 3652
import sys
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,K = IL()
a = [list(S()) for i in range(H)]

rui = [[0]*(W+1) for i in range(H)]
for i in range(H):
  for j in range(W):
    rui[i][j+1] = rui[i][j] + int(a[i][j])
#print(rui)

ans = MAX_INT
for x in range(1<<(H-1)):
  l = 0
  num = 0
  for h in range(H-1):
    if (x >> h) & 1 == 1: # 割る
      num += 1

  for w in range(W):
    # 1行で割れるか判定
    judge = int(a[0][w])
    for h in range(H-1):
      if (x >> h) & 1 == 0: # 割らない
        judge += int(a[h+1][w])
      else: # 割る
        judge = 0
        judge += int(a[h+1][w])
      if judge > K: #どうやって割ってもダメ
        break
    else:
      continue
    break
  else:
    cnt = 0
    for w in range(W):
      #print("w:",w)
      cnt = rui[0][w+1] - rui[0][l]
      if cnt > K:
        num += 1
        l = w
        #print("break1")
        continue

      for h in range(H-1):
        #print("cnt",cnt)
        if (x >> h) & 1 == 0: # 割らない
          cnt += rui[h+1][w+1] - rui[h+1][l]
        else: # 割る
          cnt = rui[h+1][w+1] - rui[h+1][l]
        #print(rui[h+1][w+1],rui[h+1][l])

        if cnt > K:
          num += 1
          l = w
          #print("break")
          break
      #print("--")
    else:
      ans = min(ans, num)
      #print(num)

print(ans)

Measured memory_bytes: 46428
/*
   Author: Shivam Shukla
   Problem URL: 
*/
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pair<ll,ll> > vpll;
 
const int MOD=1e9+7;
const int MAX=1e5+5;
const double PI= acos(-1.0);
const long double EPS=1e-10;
const int64_t INF=1e18+10;
 
#define fastio() ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0)
#define trace(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define vi vector<int>
#define vl vector<ll>
#define vs vector<str>
#define vc(x) vector<x>
#define mapll map<ll,ll>
#define mapib map<int,bool>
#define mapiv map<int,vector>
#define mapsi map<string,int>
#define repa(i,n) for(ll i=0;i<n;i++)
#define dowa(i,n) for(ll i=n;i>=0;i--)
#define reps(i,j,k,s) for(ll i=j;i<k;i+=s)
#define downs(i,j,k,s) for(ll i=j;i>=k;i-=s)
#define trv(i,x) for(auto i:x)
#define pb push_back
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define str string 
#define dub double
#define pqmax priority_queue<ll>
#define pqmin priority_queue<ll,vl,greater<ll> >
 
template<typename t> t lcm(t a, t b) {return (a*b)/__gcd(a,b);}
template<typename t> t gcd(t a, t b) {return __gcd(a,b);}
template<typename t> t mul_mod(t a, t b, t m){t res=((a%m)*(b%m)%m); return res;}
template<typename t> t add_mod(t a, t b, t m){t res=((a%m)+(b%m))%m; return res;}
template<typename t> t pow(t a,t b,t m) {t res=1;while(b){if(b&1) res=mul_mod(res,a,m);a=mul_mod(a,a,m), b>>=1;} return res%m;}
template<typename t> vc(t) num_vec(t num) {t res; while (num) res.pb(num%10), num/=10; return res;}
template<typename t> t vec_num(t vec) {t res=0; ll mul=1; repa(i,sz(vec)) res=vec[i]*mul, mul*=10; return res;}
 

int32_t main(int argc,char** argv){
	fastio();
	auto tstart= clock();
    /* Code Starts Here */
    ll n,m,s=0;cin>>n;
    vi a(n); repa(i,n) cin>>a[i], s+=a[i];
    
    cin>>m;
    vpii d(m); repa(i,m){
    	int p,t;cin>>p>>t;
    	cout<<(s-a[p-1]+t)<<endl;
    }
    /* Code Ends Here */

    cerr<<setprecision(2)<<fixed<<"Time elapsed: "<<(double)(clock() - tstart)/CLOCKS_PER_SEC<<endl; 
    return 0; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main() {
  int A, B, C, D, E;
  cin >> A >> B >> C >> D >> E;
  if(A==0) {
    cout << 1 << endl;
  }
  if(B==0) {
    cout << 2 << endl;
  }
  if(C==0) {
    cout << 3 << endl;
  }
  if(D==0) {
    cout << 4 << endl;
  }
  if(E==0) {
    cout << 5 << endl;
  }
}

Measured memory_bytes: 3552
import std.stdio, std.string, std.conv, std.algorithm;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;
import std.numeric;

void main() {
    int n;
    int[] a;

    scan(n);
    a = readln.split.to!(int[]);

    a = [0] ~ a ~ [0];

    auto lb = new int[](n + 2), rb = new int[](n + 2);
    auto st = Stack!(int)(n);
    st.push(0);

    foreach (i ; 1 .. n + 1) {
        while (!st.empty && a[st.top] > a[i]) {
            st.pop();
        }

        lb[i] = st.top;
        st.push(i);
    }

    st.clear();
    st.push(n + 1);

    foreach_reverse (i ; 1 .. n + 1) {
        while (!st.empty && a[st.top] >= a[i]) {
            st.pop();
        }

        rb[i] = st.top;
        st.push(i);
    }

    long ans;

    foreach (i ; 1 .. n + 1) {
        ans += 1L * (i - lb[i]) * (rb[i] - i) * a[i];
    }

    writeln(ans);
}



struct Stack(T) {
private:
    int N, peek;
    T[] data;

public:
    this(int size) 
    {
        N = size;
        data = new T[](N);
    }

    bool empty() @property
    {
        return peek == 0;
    }

    bool full() @property
    {
        return peek == N;
    }

    void push(T x) @property
    {
        assert(!full);
        data[peek++] = x;
    }

    void pop() @property
    {
        assert(!empty);
        --peek;
    }

    T top() @property
    {
        return data[peek - 1];
    }

    void clear() @property
    {
        peek = 0;
    }

    int length() @property
    {
        return peek;
    }

}



void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}



void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Measured memory_bytes: 11664
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
#define ULL unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
char s[100010];
int to[100010];
int main() {
    scanf("%s",s);
    memset(to,0,sizeof(to));
    int l=0,r=0,start=1;
    int ansl,ansr;
    for(int i=0;s[i]!='\0';i++){
        if(start==1){
            if(s[i]=='R'){
                r++;
            }else{
                start=-1;
                ansl=i;
                ansr=i-1;
                l++;
            }
        }else if(start==-1){
            if(s[i]=='R'){
                to[ansr]=(r+1)/2+l/2;
                to[ansl]=(l+1)/2+r/2;
                start=1;
                r=1;
                l=0;
            }else{
                l++;
            }
        }
    }
                to[ansr]=(r+1)/2+l/2;
                to[ansl]=(l+1)/2+r/2;
    for(int i=0;s[i]!='\0';i++){
        printf("%d ",to[i]);
    }
    return 0;
}


Measured memory_bytes: 896
import bisect
a,b,q=map(int,input().split())
shrines=[-10**20]+[int(input()) for i in range(a)]+[10**20]
temples=[-10**20]+[int(input()) for i in range(b)]+[10**20]
for i in range(q):
    x=int(input())
    s=bisect.bisect_left(shrines,x)
    t=bisect.bisect_left(temples,x)
    Dsleft=x-shrines[s-1]
    Dtleft=x-temples[t-1]
    Dsright=shrines[s]-x
    Dtright=temples[t]-x
    print(min(max(Dsleft,Dtleft),max(Dsright,Dtright),Dsleft+Dtright+min(Dsleft,Dtright),Dsright+Dtleft+min(Dsright,Dtleft)))

Measured memory_bytes: 12800
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
signed main(){
  int A,B;
  char op; cin>>A>>op>>B;
  int ans=A+B;
  if(op=='-')
    ans=A-B;
  cout<<ans<<endl;
  }


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

int main() {
    int N, M;
    cin >> N;
    vector<int> X(N, 0);
    for (int i = 1; i < N; i++) {
        cin >> M;
        X[M-1]++;
    }
    for (int i = 0; i < N; i++) {
        cout << X[i] << endl;
    }
    return 0;
}


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

using LL = long long;
const LL MOD = 1e9 + 7;
const int N = 100000;

vector<LL> factorial(N+1, 1);
LL power(LL m, LL n) {
  if(!n) return 1;
  return (n & 1) ? power(m, n - 1) * m % MOD : power(m * m % MOD, n >> 1);
}
LL inverse(LL x) {
  return power(x, MOD - 2);
}
LL combination(LL n, LL r) {
  if(r<0) return 0;
  if(n<r) return 0;
  return (factorial[n] * inverse(factorial[n-r]) % MOD) * inverse(factorial[r]) % MOD;
}

int main() {
  for(LL i=1; i<=N; ++i) factorial[i] = factorial[i-1] * i % MOD;

  int n;
  cin >> n;
  vector<int> a(n+1);
  for(auto& i: a) cin >> i, --i;

  vector<int> cnt(n);
  for(auto i: a) ++cnt[i];

  auto l=-1, r=-1;
  for(auto i=0; i<n+1; ++i) if(cnt[a[i]]==2) (l==-1) ? l=i: r=i;

  for(auto k=1; k<=n+1; ++k) {
    LL sum = combination(n-1, k);
    sum %= MOD;
    sum += combination(n-1, k-2);
    sum %= MOD;
    sum += combination(n-1, k-1);
    sum %= MOD;
    sum += combination(n-1, k-1);
    sum %= MOD;
    sum += MOD - combination(n-(r-l), k-1);
    sum %= MOD;
    cout << sum << endl;
  }
}


Measured memory_bytes: 2816
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
int main() 
{
  int n;
  cin >> n;
  long long h[n], dp[n];
  for (int i = 0; i < n; ++i) cin >> h[i];
  for (int i = 0; i < n; ++i) dp[i] = INF;
  dp[0] = 0;
  for(int i = 0; i < n; ++i){
    dp[i + 1] = min(dp[i] + abs(h[i + 1] - h[i]), dp[i + 1]);
    dp[i + 2] = min(dp[i] + abs(h[i + 2] - h[i]), dp[i + 2]);
  }  
  cout << dp[n-1] << endl;
  return 0;
}

Measured memory_bytes: 1792
/*!enjoy karo yaar!*/

//CF,CC,AtC,SPOJ: hp1999
//HE: hemant269
//HR: hemant2132

#include<bits/stdc++.h>
using namespace std;

#define     int             long long int
#define     fast()          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define     all(x)          begin(x),end(x)
#define     rz(x)           resize(x)
#define     asn(x,y)        assign(x,y)
#define     mem(a,b)        memset(a,b,sizeof(a))
#define     sz(x)           ((int)size(x))
#define     eb              emplace_back
#define     pb              push_back
#define     pf              push_front
#define     pob             pop_back
#define     pof             pop_front
#define     ins             insert
#define     vi              vector<int>
#define     pii             pair<int,int>
#define     mii             map<int,int>
#define     F               first
#define     S               second
#define     remax(a,b)      a=max(a,b)
#define     remin(a,b)      a=min(a,b)
#define     bitcount(x)     __builtin_popcountll(x)
#define     iceil(n,x)      (((n)-1)/(x)+1)
#define     dbug(x)         cout<<#x<<": "<<(x)<<"\n"
#define     flush           fflush(stdout)
#define     show(x)         for(auto zz:x)cout<<zz<<" ";cout<<"\n";
#define     show2(x)        for(auto zz:x)cout<<zz.F<<" "<<zz.S<<"\n";

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;

const ld pi=acos(-1);
const ll inf=1e18,M=1e9+7;
const int N=1;

void solve()
{
    int h1,m1,h2,m2;
    cin>>h1>>m1>>h2>>m2;

    int k;
    cin>>k;

    int a=h1*60+m1;
    int b=h2*60+m2;

    b-=k;
    cout<<b-a;
}

int32_t main()
{
    fast();

    int t=1;
    //cin>>t;
    for(int z=1;z<=t;++z)
    {
        solve();
        //cout<<"\n";
    }

    return 0;
}



Measured memory_bytes: 3628
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream> 
#include<map>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <iomanip>
#include <malloc.h>
using namespace std;
#define MAX_MOD 1000000007
#define REP(i,n) for(int i = 0;i < n;++i)
#define LONGINF 1000000000000000000
long long ans[10000] = {};
long long n, x;
vector<long long> a;
int main() {
	cin >> n >> x;
	REP(i, n) {
		long long b;
		cin >> b;
		a.push_back(b);
	}
	for (int i = 0;i < n;++i) {
		long long hoge = LONGINF;
		int wow = i;
		for (int q = 0;q < n;++q) {
			hoge = min(hoge, a[wow]);
			if (wow == 0) wow = n;
			wow--;
			ans[q] += hoge;
		}
	}
	long long hogee = LONGINF;
	for (int i = 0;i < n;++i) {
		hogee = min(hogee, ans[i] + x*i);
	}
	cout << hogee << endl;
}

Measured memory_bytes: 256
#include<stdio.h>


int main(){
    int N;
    int Q;
    scanf("%d",&N);
    scanf("%d",&Q);
    char S[100001];
    scanf("%s",S);
    int l[Q];
    int r[Q];
    for(int i=0;i<Q;i++){
        scanf("%d",&l[i]);
        scanf("%d",&r[i]);
    }
    int num[100001]={};
    for(int i=0;i<N;i++){
        if(S[i]=='A'&&S[i+1]=='C'){
                num[i]++;
                i++;
            }
    }
    
    int max = 0;
    for(int i=0;i<N;i++){
            max += num[i];
    }
    
    
    
    
    
    
    
    for(int i=0;i<Q;i++){    
        
        int counter=0;
        if(r[i]-l[i]<N/2)
        for(int j=l[i];j<r[i];j++){
            counter += num[j-1];
        }
        else {
            counter = max;
            for(int j=1;j<l[i];j++){
                counter -=num[j-1];
            }
            for(int j=r[i];j<=N;j++){
                counter -=num[j-1];
            }
        }
        
        
        printf("%d",counter);
        printf("\n");
    }

    return 0;







}

Measured memory_bytes: 2048
#include <iostream>
using namespace std;
int main(){
    int N, K;
    cin >> N >> K;
    int d[K];
    for(int i = 0; i < K; i++) cin >> d[i];
    int ans = N;
    while(1){
        int res = ans;
        int flag = 0;
        while(res > 0){
            int a = res % 10;
            for(int i = 0; i < K; i++){
                if(a == d[i]){
                    flag = 1;
                }
            }
            res /= 10;
        }
        if(flag == 0) break;
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>

using namespace std;

struct point {
	double x, y;
};

struct segLine {
	point s, e;	
}segA, segB;

int main() {
	int t;
	scanf ("%d", &t);
	while (t--) {
		scanf ("%lf%lf%lf%lf", &segA.s.x, &segA.s.y, &segA.e.x, &segA.e.y);
		scanf ("%lf%lf%lf%lf", &segB.s.x, &segB.s.y, &segB.e.x, &segB.e.y);
		if ((segA.e.y-segA.s.y)*(segB.e.x-segB.s.x)==(segB.e.y-segB.s.y)*(segA.e.x-segA.s.x))  printf ("YES\n");
		else printf ("NO\n");
	}
	return 0; 
}

Measured memory_bytes: 0
#include <iostream>

using namespace std;

int main()
{
	double n, m;
	int d;
	cin >> n >> m >> d;

	double ans = 1.0;
	if (d == 0) {
		ans *= m - 1;
		ans /= n;
	}else{
		ans = 2.0 * (n - d);
		ans *= m - 1;
		ans /= n * n;
	}
	printf("%.10f\n", ans);

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++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 T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }


long long K, N;

vector<int> solve() {
	vector<int> res;
	if (K % 2 == 0) {
		res.push_back(K / 2);
		for (int i = 1; i < N; ++i) res.push_back(K);
		return res;
	}

	if (K == 1) {
		for (int i = 0; i < (N + 1) / 2; ++i) res.push_back(1);
		return res;
	}

	int d = 0;
	long long pow = 1, M = 0;
	while (pow <= N) pow *= K, ++d;
	for (int i = 0; i < N - d; ++i) res.push_back((K + 1) / 2);
	for (int i = 0; i < d; ++i) {
		M *= K;
		M += K;
	}
	long long newK = (M - (N - d) + 1) / 2 - 1;

	for (int i = 0; i < d - 1; ++i) {
		long long div = 0;
		for (int j = 0; j < d - i; ++j) div *= K, div += 1;
		long long q = newK / div;
		long long r = newK % div;
		res.push_back(q + 1);
		newK = r - 1;
		if (newK < 0) break;
	}
	if (newK >= 0) res.push_back(newK + 1);

	return res;
}

int main() {
  while (cin >> K >> N) {
		vector<int> res = solve();
		for (int i = 0; i < res.size(); ++i) {
			cout << res[i];
			if (i != res.size() - 1) cout << " ";
		}
		cout << endl;
  }
}














Measured memory_bytes: 3568
'''3/18 AtCoder（漸化式dp）
一番左の棒からスタートして、K番目の棒に到達するようなあみだくじは
何通り作れますかという趣旨の問題
まず、この問題を解くうえで一番重要なのは、
「ある高さh、棒jに至る経路の総数を求める漸化式が立てられる」ということ
高さh、棒jに至る経路の総数をdp[h][j]とすれば、
高さh-1からこの位置に至ることができるのは、
棒j-1,j,j+1のいずれかしかない
さらに、そこに至る経路数というのは結局
「ほかの棒にどんな風に架け橋（横棒）がかかっているか」の場合の数なので、
それをdp[h-1][j-1],dp[h-1][j],dp[h-1][j+1]にかけていく必要がある
例えば、dp[h-1][j]を見てみる　これは、同じ棒から下ってくることを
意味しているが、換言すれば「高さi-1とiには、棒jから伸びる横棒はない」
ということである
つまり、この高さにおける横棒の架かり方というのは
「棒1~j-1までの架かり方」と「棒j+1~棒Wまでの架かり方」の
二パターンしかないということになる
ある高さにおける横棒のかかり方も漸化式で求められる　
高さhにおける(横一列にかけ橋が並んでいる状況を考える）、
n本の棒の間にかかる橋の場合の数の総数をf(n)と置くと、
f(n) = f(n-1)+f(n-2)と書くことができる
これは、f(n)が
①n本目とn-1本目の棒の間に橋が架かっていない→場合の数はf(n-2)と同じ
②n本目とn-1本目の棒の間に橋が架かっている→場合の数はf(n-1)と同じ
の二パターンの合計だからである
だから、dp[h-1][j]に掛ける数はいくつかということを考えたら、
j-1本の棒の間にかかる橋の場合の数f(j-1)と、
W-j本の棒の間にかかる橋の場合の数f(W-j)本ということになる　
これと同様に、残り二本に対してもいくつかければよいかを考えて、
dp[h][j]]に対する漸化式を立てればよい
'''
H,W,K = map(int,input().split())
dp = []
for i in range(H+1): #高さ0の分を余分に持っておく
  L = [0]*W
  dp.append(L)
fb = [1,1] #フィボナッチ（f(n)=f(n-1)+f(n-2)）
for i in range(W-2):
  fb.append(fb[i]+fb[i+1])
dp[0][0] = 1 #左端の棒の高さ0は初期位置なので1に
if W != 1: #棒が一本以上あるときは
  for i in range(1,H+1):
    for j in range(W): #棒が左端、右端、それ以外で場合分け
      if 1 <= j <= W-2:
        dp[i][j] = dp[i-1][j-1]*fb[j-1]*fb[W-j-1]+dp[i-1][j]*fb[j]*fb[W-j-1]+dp[i-1][j+1]*fb[j]*fb[W-j-2]
      elif j == 0:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j+1]*fb[W-2]
      else:
        dp[i][j] = dp[i-1][j]*fb[W-1]+dp[i-1][j-1]*fb[W-2]
else:
  dp[H][0] = 1
print(dp[H][K-1]%(10**9+7)) #高さH（一番下）、K-1番目の棒を調べる

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

class dice(object):
	def __init__(self, d):
		self.d = d

	def roll(self,com):
		a1,a2,a3,a4,a5,a6=self.d
		if com=="E":
			self.d = [a4,a2,a1,a6,a5,a3]
		elif com=="W":
			self.d = [a3,a2,a6,a1,a5,a4]
		elif com=="S":
			self.d = [a5,a1,a3,a4,a6,a2]
		elif com=="N":
			self.d = [a2,a6,a3,a4,a1,a5]

import random
ds=[]
for i in range(n):
	ds.append(dice(list(map(int,input().split()))))
flag="Yes"
for i in range(n):
	for j in range(i):
		if sorted(ds[i].d)!=sorted(ds[j].d):
			continue
		else:
			c=["E","W","S","N"]
			n=0
			while n<1000:
				if ds[i].d==ds[j].d:
					break 
				else:
					ds[i].roll(c[random.randint(1,2)])
				n+=1
			if n==1000:
				pass
			else:
				flag="No"

print(flag)

Measured memory_bytes: 11760
using System;

namespace abc160C
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split();
            int K = int.Parse(str[0]);
            int N = int.Parse(str[1]);
            int[] a = new int[N];
            str = Console.ReadLine().Split();
            for (int i = 0; i < N; i++)
            {
                a[i] = int.Parse(str[i]);
            }
            int[] b = new int[N];
            for(int i = 0; i < N-1; i++)
            {
                b[i] = K-(a[i + 1] - a[i]);
            }
            b[N - 1] = K-(K - a[N - 1] + a[0]);
            Array.Sort(b);
            Console.WriteLine(b[0]);
        }
    }
}


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

#define REP(i, n) for(int (i) = 0; (i) < (n); ++(i))
#define REPR(i, n) for(int (i) = (n); (i) >= 0; --(i))
#define FOR(i, n, m) for(int (i) = (n); (i) < (m); ++(i))

constexpr int INF = 1e9;
// constexpr ll INF = 1LL<<61;
constexpr ll mod = 1e9+7;


int main(){
  int N;
  cin >> N;
  if(N % 1000 == 0){
    cout << 0 << endl;
  }
  else{
    cout << 1000 - N % 1000 << endl;
  }
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include<cmath>
#include<vector>
#include<bitset>
#include<bitset>
#include<string>
#include<utility>
#include<algorithm>
#include<queue>

using namespace std;

int main(){
    string s;
    int q,nfront=0,ntail=0;
    bool isrev=false;
    vector<char> front(200000);
    vector<char> tail(200000);

    cin >> s >> q;
    int t,f;
    char c;
    for(int i=0;i<q;i++){
        cin >> t;
        if(t==1){
            isrev= (!isrev);
        }else{
            cin >> f >>  c;
            if(((isrev==false)&&f==1) || ((isrev==true)&&f==2)){
                front.at(nfront)=c;
                nfront++;
            }else{
                tail.at(ntail)=c;
                ntail++;
            }
        }
    }
    if(isrev){
        reverse(s.begin(),s.end());
        for(int i=ntail-1;i>=0;i--){
            cout << tail.at(i);
        }
        cout << s;
        for(int i=0;i<nfront;i++){
            cout << front.at(i);
        }
        cout << endl;
    }else{
        for(int i=nfront-1;i>=0;i--){
            cout << front.at(i);
        }
        cout << s;
        for(int i=0;i<ntail;i++){
            cout << tail.at(i);
        }
        cout << endl;
    }

    return 0;
}

Measured memory_bytes: 3676
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
inf = 10**17
mod = 10**9 + 7


d,n=MI()
ans=100**d*(n+n//100)
print(ans)

Measured memory_bytes: 3700
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
*/

#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cassert>
#include <iomanip>
#include <set>
#include <stack>
#include <bitset>

////多倍長整数, cpp_intで宣言
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;

#pragma GCC target ("avx2")
#pragma GCC optimization ("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define repeat(i, n, m) for(int i = n; i < (m); ++i)
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printim(a) printf(a ? "possible\n" : "imposible\n")
#define printdb(a) printf("%.50lf\n", a) //少数出力
#define printLdb(a) printf("%.50Lf\n", a) //少数出力
#define printdbd(a) printf("%.16lf\n", a) //少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str()) //string出力
#define all(x) (x).begin(), (x).end()
#define deg_to_rad(deg) (((deg)/360.0L)*2.0L*PI)
#define rad_to_deg(rad) (((rad)/2.0L/PI)*360.0L)
#define Please return
#define AC 0
#define manhattan_dist(a, b, c, d) (abs(a - c) + abs(b - d)) /*(a, b) から (c, d) のマンハッタン距離 */
#define inf numeric_limits<double>::infinity();
#define linf numeric_limits<long double>::infinity()

using ll = long long;
using ull = unsigned long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1e9 + 7;
constexpr ll mod = 998244353;
constexpr long double eps = 1e-6;
const long double PI = acosl(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);
	while (c != '\n' && c != -1 && c != ' ') {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

ll LSB(ll n) { return (n & (-n)); }

template<typename T>
inline T chmin(T& a, const T& b) {
	if (a > b)a = b;
	return a;
}

template<typename T>
inline T chmax(T& a, const T& b) {
	if (a < b)a = b;
	return a;
}


/*-----------------------------------------ここからコード-----------------------------------------*/



int main() {

	int n;
	scanf("%d", &n);
	vector<pair<int, int>> d(n);
	for (const auto& [a, b] : d)scanf("%d%d", &a, &b);
	bool ans = false;
	rep(i, n - 2) {
		if (d[i].first == d[i].second and d[i + 1].first == d[i + 1].second and d[i + 2].first == d[i + 2].second)ans = true;
	}
	printyn(ans);

	Please AC;
}


Measured memory_bytes: 3840
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>
#include <stack>
using namespace std;

#define rep(i, s) for (int i = 0; i < s; ++i)
#define all(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define VEC(a, n) vector<int>a(n)
#define PQ(a) priority_queue<int>a
#define PQmin(a) priority_queue< int, :vector<int>, greater<int> >a
#define PAIR pair<int, int>
/*
sort(sp.begin(), sp.end(), [](PAIR l, PAIR r){
        return l.first<r.first || (l.first==r.first && l.second > r.second);
        });
*/

typedef long long  ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    int n;
    cin>>n;
    vector<pair<int,int> >a(n);
    for(int i=0;i<n;i++){
        cin>>a.at(i).first>>a.at(i).second;
    }
    int ans=n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int cnt=0;
            if(i==j){
                continue;
            }
            //n*(n-1)点の組み合わせについてベクトルを定める。
            int dx=a.at(i).first-a.at(j).first;
            int dy=a.at(i).second-a.at(j).second;

            //それぞれのdx.dyについて、その方向のベクトルが存在するかを確認する。
            for(int k=0;k<n;k++){
                for(int l=0;l<n;l++){
                    if((a.at(k).first-a.at(l).first)==dx){
                        if((a.at(k).second-a.at(l).second)==dy){
                            cnt++;
                            break;
                        }
                    }
                }
            }
            ans=min(ans,n-cnt);
        }
    }
    cout<<ans<<endl;



    return 0;
}


Measured memory_bytes: 256
n=int(input())
a=sorted([int(i) for i in input().split()])
m,k=n//3,0
for i in range(n):
    d=i%3*m+i//3
    if a[d]^a[(d+2*m)%n]!=a[(d+m)%n]:
        k=1
print(['Yes','No'][k])


Measured memory_bytes: 60912
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author YahiaAshraf74
 */

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <complex>
#include <string>
#include <bitset>
#include <stdio.h>
#include <string.h>
#include <fstream>
#include <iomanip>
#include <assert.h>

using namespace std;
#define el  '\n'
#define ll long long
#define clr(a, b)memset(a,b,sizeof(a))
#define sz(a) (int)(a).size()
const long long N = 2e5 + 74, OO = 0x3f3f3f3f, MOD = (long long) 1e9 + 7;

int a[N];

class ASortedArrays {
public:
    void solve(istream &cin, ostream &cout) {
        int n;
        cin >> n;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        if (n <= 2)
            return (void) (cout << 1 << el);
        int ans = 1, inc = 0, dec = 0;
        for (int i = 0; i < n - 1; i++) {
            if (a[i] > a[i + 1]) {
                if (dec) {
                    dec = 0;
                    ans++;
                } else {
                    inc++;
                }
            } else if (a[i] < a[i + 1]) {
                if (inc) {
                    inc = 0;
                    ans++;
                } else {
                    dec++;
                }
            }
        }
        cout << ans;
    }
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    ASortedArrays solver;
    std::istream &in(std::cin);
    std::ostream &out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iomanip>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <iterator>
#include <string>

using namespace std;

using i64 = int64_t;
using P = pair<i64, i64>;
i64 mod = 1000000007;
int int_max = 2147483647;
int max_n = 1e5;
using mat2d_t = std::vector<std::vector<int64_t>>;

int main(int argc, char **argv) {
    int n;

    cin >> n;
    int a;
    for (int i=0; i<n; ++i) {
        cin >> a;
        if (a%2 == 0 && (a%3 != 0 && a%5 != 0)) {
            cout << "DENIED" << endl;
            return 0;
        }
    }
    cout << "APPROVED" << endl;
    return 0;
}

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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define debug if(true)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

int main(){
	string s,t;
	cin>>s>>t;
	int n = s.size(), m = t.size();
	int kiri = 0, kanan = m-1;
	int ans = inf;
	while(kanan < n){
		int idx = 0;
		int tot = 0;
		// printf("kiri: %d kanan: %d idx: %d\n",kiri, kanan, idx);
		for(int i=kiri;i<=kanan;i++){
			// printf("s[%d]: %c t[%d]: %c\n",i,s[i],idx,t[idx]);
			if(s[i] != t[idx]){
				tot++;
			}
			idx++;
		}
		ans = min(ans, tot);
		kiri++; kanan++;
	}
	printf("%d\n",ans);
	
	return 0;
};

Measured memory_bytes: 3684
package main

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

func main() {
  const mod int64 = 1000000007
  input := Input{bufio.NewReaderSize(os.Stdin,1000)}
  n,m := input.NextInts()
  a := make(map[int]struct{})
  for i:=0;i<m;i++ { a[input.NextInt()] = struct{}{} }
  dp := make([]int64,n+1)
  dp[0] = 1
  if _,ok := a[1];!ok { dp[1] = 1 }
  for i:=2;i<n+1;i++ {
    if _,ok := a[i];ok { continue }
    dp[i] = (dp[i-1]+dp[i-2])%mod
  }
  fmt.Println(dp[n])
}

type Input struct { reader *bufio.Reader }
func(i *Input) NextLine() string {
  var buffer []byte
  for {
    line,isPrefix,err := i.reader.ReadLine()
    if err != nil { panic(err) }
    buffer = append(buffer,line...)
    if !isPrefix { break }
  }
  return string(buffer)
}
func(i *Input) NextInt() int {
  x,_ := strconv.Atoi(i.NextLine())
  return x
}
func(i *Input) NextInts() (int,int) {
  s := strings.Split(i.NextLine()," ")
  x,_ := strconv.Atoi(s[0])
  y,_ := strconv.Atoi(s[1])
  return x,y
}

Measured memory_bytes: 4736
import java.util.*;

public class Main {
  
  private static final long INT10_9 = 1_000_000_000;
  
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long S = sc.nextLong();
    
    long start = S / INT10_9;
    for (long i = start; i <= INT10_9; i++) {
      long x = (long) INT10_9 * i - S;
      if (0 <= x && x <= INT10_9) {
        // found
        System.out.println("0 0 " + INT10_9 + " 1 " + x + " " + i);
        break;
      }
    }
  }
}

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

#define SORT(c) sort((c).begin(), (c).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
#define ANS(ans) cout << (ans) << endl;
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
typedef vector<int> VI;
typedef pair<int, int> P;

// repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define REP(i, n) for (long long i = 0; i < (n); ++i)

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

  int cnt_ac = 0, cnt_wa = 0, cnt_tle = 0, cnt_re = 0;

  string tmp;
  REP(i, n) {
    cin >> tmp;
    if (tmp == "AC") {
      cnt_ac++;
    } else if (tmp == "WA") {
      cnt_wa++;
    } else if (tmp == "TLE") {
      cnt_tle++;
    } else if (tmp == "RE") {
      cnt_re++;
    }
  }

  cout << "AC x " << cnt_ac << endl;
  cout << "WA x " << cnt_wa << endl;
  cout << "TLE x " << cnt_tle << endl;
  cout << "RE x " << cnt_re << endl;
  
  return 0;
}


Measured memory_bytes: 3640
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A, B = MAP()
P = LIST()
L = [-1, A, B, 20]
print(min(map(len, [[x for x in P if L[i] < x <= L[i+1]] for i in range(3)])))


Measured memory_bytes: 10636
import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        HashSet<String> kind = new HashSet<>();
        int N = in.nextInt();
        in.nextLine();
        for(int i = 1; i <= N; i++){
            kind.add(in.nextLine());
        }
        System.out.print(kind.size());
    }

}


Measured memory_bytes: 79820
#!/usr/bin/python3

import math
import os
import sys


DEBUG = 'DEBUG' in os.environ


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


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


def solve(N, P):
    revp = [-1] * (N + 1)
    for i, p in enumerate(P):
        revp[p] = i

    segt = [[(v, 0) for v in P]]
    while len(segt[-1]) > 1:
        base = segt[-1]
        if len(base) % 2 == 1:
            base.append((0, 0))
        new = []
        for i in range(len(base) // 2):
            a, b = base[2 * i]
            c, d = base[2 * i + 1]

            arr = [a, b, c, d]
            arr.sort()
            new.append((arr[-1], arr[-2]))
        segt.append(new)

    dprint('segt', segt)

    def get12(i, j):
        if j - i <= 0:
            return (0, 0)

        segi = 0
        top = []

        while True:
            if j - i <= 0:
                break

            seg = segt[segi]

            if j - i == 1:
                top.extend(seg[i])
                break

            if i % 2 == 1:
                top.extend(seg[i])
                i += 1
            if j % 2 == 1:
                top.extend(seg[j - 1])
                j -= 1

            i //= 2
            j //= 2
            segi += 1

        top.sort()
        return top[-1], top[-2]

    cache = [dict() for _ in range(N)]

    stk = [(0, N)]
    while stk:
        item = stk.pop()
        if len(item) == 2:
            i, j = item
            if j in cache[i]:
                continue

            a, b = get12(i, j)
            ai = revp[a]
            bi = revp[b]
            li, ri = (ai, bi) if ai < bi else (bi, ai)
            ri += 1

            sc = b * (li - i + 1) * (j - ri + 1)

            want = [(i, ri - 1), (li + 1, j), (li + 1, ri - 1)]
            req = []
            for c, d in want:
                if not (d - c < 2 or d in cache[c]):
                    req.append((c, d))
            if not req:
                left, right, mid = [0 if d - c < 2 else cache[c][d]
                                    for c, d in want]
                cache[i][j] = left + right - mid + sc
                continue

            stk.append((i, j, want, sc))
            for r in req:
                stk.append(r)
            continue

        i, j, want, sc = item
        left, right, mid = [0 if d - c < 2 else cache[c][d]
                            for c, d in want]
        cache[i][j] = left + right - mid + sc

    return cache[0][N]


def main():
    N = int(inp())
    P = [int(e) for e in inp().split()]
    print(solve(N, P))


if __name__ == '__main__':
    main()


Measured memory_bytes: 124832
# Enter your code here. Read input from STDIN. Print output to STDOUT

def find(x):
    dic={}
    
    def fact(t):
        T=int(t**0.5)+1
        for i in range(2,T):
            if t%i==0:
                if i in dic:
                    dic[i]+=1
                else:
                    dic[i]=1
                return i
        if t in dic:
            dic[t]+=1
        else:
            dic[t]=1            
        return t

    while x>1:
        #print(x)
        x=int(x/fact(x))
        #print(x)
    return dic

def find_ans(N,P):
    dic=find(P)
    ans=1
    for x in dic:
        ans*=pow(x,dic[x]//N)
    return ans    

N,P=list(map(int,input().split(" ")))
print(find_ans(N,P))

Measured memory_bytes: 39920
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N, K;
  int sum = 1;
  cin >> N >> K;
  
  for (int i = 0; i < N; i++) {
    if (sum * 2 >= sum + K) {
      sum += K;
    }
    else {
      sum *= 2;
    }
  }
  
  cout << sum << endl;
  
}


Measured memory_bytes: 256
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_B main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 10;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions

#endif


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

    int A, B; cin >> A >> B;

    int ans = (B - 1 + A - 2) / (A - 1);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main()
{
    // 整数の入力
    int N, X, T;
    cin >> N >> X >> T;
    // スペース区切りの整数の入力
    int x = N / X * T;
    if ( N % X > 0 ){
      x += T;
    }
    cout << x << endl;
    
}

Measured memory_bytes: 3624
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

def resolve():
    n,x=map(int,input().split())
    if(x!=1 and x!=2*n-1):
        print("Yes")
    else:
        print("No")
        return

    if(n==2):
        print(1,2,3)
        return

    if(x!=2):
        ans=[i for i in range(1,2*n) if(i not in [x-2,x-1,x,x+1])]
        ans=ans[:n-2]+[x-2,x,x+1,x-1]+ans[n-2:]
        print(*ans)
    else:
        ans=[i for i in range(5,2*n)]
        ans=ans[:n-2]+[1,2,4,3]+ans[n-2:]
        print(*ans)
resolve()

Measured memory_bytes: 66160
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

output:
Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0
"""

import sys


class Node(object):
    def __init__(self):
        # init node as a single leaf node.
        self.parent = -1
        self.children = []
        self.index = -1


def pre_parse(v):
    print(' ' + str(v.index), end='')
    if not v.children:
        return None
    left_child_idx = v.children[0]
    right_child_idx = v.children[1]

    if left_child_idx != -1:
        pre_parse(node_list[left_child_idx])

    if right_child_idx != -1:
        pre_parse(node_list[right_child_idx])

    return None


def in_parse(v):
    if not v.children:
        return None
    left_child_idx = v.children[0]
    right_child_idx = v.children[1]

    if left_child_idx != -1:
        in_parse(node_list[left_child_idx])

    print(' ' + str(v.index), end='')

    if right_child_idx != -1:
        in_parse(node_list[right_child_idx])

    return None


def post_parse(v):
    if not v.children:
        return None
    left_child_idx = v.children[0]
    right_child_idx = v.children[1]

    if left_child_idx != -1:
        post_parse(node_list[left_child_idx])

    if right_child_idx != -1:
        post_parse(node_list[right_child_idx])

    print(' ' + str(v.index), end='')

    return None


def generate_tree(_array):
    # add info of each node of a ordered tree
    for each in _array:
        idx, *children = [int(x) for x in each]
        # assert len(children) == 2 and idx >= 0
        node_list[idx].index = idx
        node_list[idx].children = children

        for child_idx in children:
            # non-existent node: no parent
            if child_idx == -1:
                continue
            node_list[child_idx].parent = idx

    # find root node
    root_idx = [i for i, x in enumerate(node_list) if x.parent == -1][0]

    # tree walk in 3 ways
    print('Preorder')
    pre_parse(node_list[root_idx])
    print('\n' + 'Inorder')
    in_parse(node_list[root_idx])
    print('\n' + 'Postorder')
    post_parse(node_list[root_idx])
    print('')

    return node_list


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(lambda x: x.split(), _input[1:]))
    # assert len(array) == array_length

    node_list = [Node() for _ in range(array_length)]
    ans = generate_tree(_array=array)

Measured memory_bytes: 7888
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = (ll)1000000007 * 1000000007;
const double EPS = 1e-9;
typedef pair<int, int> P;
typedef unsigned int ui;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
ll a[200000];
ll sum[200001];
ll c[199999];
int main() {
	int n; cin >> n;
	rep(i, n) {
		cin >> a[i];
	} sum[0] = 0;
	rep(i, n) {
		sum[i + 1] = sum[i] + a[i];
	}
	rep(i, n - 1) {
		c[i] = sum[i + 1] - (sum[n] - sum[i + 1]);
	}
	ll mi = INF;
	Rep(i, 1, n - 2) {
		ll ri = sum[n] - sum[i + 1];
		ll le = sum[i + 1];
		int l = lower_bound(c, c + i, -ri) - c;
		int r = lower_bound(c + i + 1, c + n-1, le) - c;
		if (r == n - 1)r--;
		if (l == i)l--;
		ll x1 = (ll)abs(sum[l + 1] - (le-sum[l+1]));
		ll x2 = (ll)abs(sum[l] - (le - sum[l]));
		ll y1 = (ll)abs(sum[r + 1] - le - (sum[n] - sum[r + 1]));
		ll y2 = (ll)abs(sum[r] - le - (sum[n] - sum[r]));
		ll c1, c2, c3, c4;
		ll mi1, ma1;
		if (x1 < x2) {
			mi1 = min(sum[l + 1], le - sum[l + 1]);
			ma1 = max(sum[l + 1], le - sum[l + 1]);
			c1 = ma1; c3 = mi1;
		}
		else {
			mi1 = min(sum[l], le - sum[l]);
			ma1 = max(sum[l], le - sum[l]);
			c1 = ma1; c3 = mi1;
		}
		if (y1 < y2) {
			mi1 = min(sum[r + 1] - le, sum[n] - sum[r + 1]);
			ma1 = max(sum[r + 1] - le, sum[n] - sum[r + 1]);
			c2 = ma1; c4 = mi1;
		}
		else {
			mi1 = min(sum[r] - le, sum[n] - sum[r]);
			ma1 = max(sum[r] - le, sum[n] - sum[r]);
			c2 = ma1; c4 = mi1;
		}
		c1 = max(c1, c2);
		c3 = min(c3, c4);
		mi = min(mi, c1 - c3);
	}
	cout << mi << endl;
	return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define inf INT_MAX
#define INF LLONG_MAX
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define int ll
#define vi vector<int>
#define IP pair<int,P>
#define PI pair<P,int>
#define PP pair<P,P>
#define Yes(f){cout<<(f?"Yes":"No")<<endl;}
#define YES(f){cout<<(f?"YES":"NO")<<endl;}


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

  int n,a,b;
  cin>>n>>a>>b;

  if(a%2==b%2){
    cout<<abs(a-b)/2<<endl;
  }else{
    cout<<1+abs(a-b)/2+min(min(a,b)-1,n-max(a,b))<<endl;
  }


}

Measured memory_bytes: 256