akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

static long long try(int sign, long long a[100000], int n);

int main(int argc, char *argv[])
{
	int i, n;
	long long a[100000], plus, minus;
	scanf("%d", &n);

	for ( i = 0; i < n; i++ ){
		scanf("%lld", &a[i]);
	}

	/* 最初の符号を変えたほうが少ない場合があるので、両方ためす */
	plus = try(1, a, n);
	minus = try(-1, a, n);
	printf("%lld\n", plus>minus?minus:plus);
	return 0;
}

static long long try(int sign, long long a[100000], int n)
{
	int i;
	long long t = 0, c = 0;
	for ( i = 0; i < n; i++ ){
		if ( sign < 0 ){
			if ( t+a[i] >= 0 ){
				c += t+a[i]+1;
				t = -1;
			} else {
				t += a[i];
			}
		} else {
			if ( t+a[i] <= 0 ){
				c += llabs(t+a[i]-1);
				t = 1;
			} else {
				t += a[i];
			}
		}
		sign *= -1;
	}
	return c;
}


Measured memory_bytes: 896
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

const int N = 100000;

int a[N], t[N], result[N];

int main()
{
#ifdef LOCAL_JUDGE
    freopen("E.in", "r", stdin);
#endif
    int x, n, q;
    while (scanf("%d%d", &x, &n) == 2) {
        std::vector<std::pair<int, int>> events;
        for (int i = 0, turn; i < n; ++ i) {
            scanf("%d", &turn);
            events.emplace_back(turn, -1);
        }
        int q;
        scanf("%d", &q);
        for (int i = 0; i < q; ++ i) {
            scanf("%d%d", t + i, a + i);
            events.emplace_back(t[i], i);
        }
        std::sort(events.begin(), events.end());
        int dir = -1, i = 0, j = x, yi = 0, yj = x, t0 = 0;
        for (auto&& event : events) {
            int t = event.first;
            if (t0 < t) {
                int dt = t - t0;
                if (dir == -1) {
                    if (yi >= dt) {
                        yi -= dt;
                        yj -= dt;
                    } else if (yj < dt) {
                        i = j = yi = yj = 0;
                    } else {
                        i += dt - yi;
                        yi = 0;
                        yj -= dt;
                    }
                } else {
                    if (yj + dt <= x) {
                        yi += dt;
                        yj += dt;
                    } else if (yi + dt > x) {
                        i = j = 0;
                        yi = yj = x;
                    } else {
                        j -= yj - (x - dt);
                        yj = x;
                        yi += dt;
                    }
                }
            }
            t0 = t;
            int id = event.second;
            if (~id) {
                if (a[id] < i) {
                    result[id] = yi;
                } else if (a[id] > j) {
                    result[id] = yj;
                } else {
                    result[id] = yi + (a[id] - i);
                }
            } else {
                dir *= -1;
            }
        }
        for (int i = 0; i < q; ++ i) {
            printf("%d\n", result[i]);
        }
    }
}

Measured memory_bytes: 4080
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<iomanip>

#define REP(i,n) for(int i=0;i<(n);i++)
#define EPS (1e-7)
#define INF (2e9)
// cout << setprecision(10)

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

queue<PI> q[100000];
int N;
int u,v,w;
int R[100000];

void setter(int color, int i){
    while(!q[i].empty()){
        PI p = q[i].front();
        q[i].pop();
        if(R[p.first] == -1){
            if(p.second % 2 == 0) R[p.first] = color;
            else R[p.first] = color^1;
            setter(R[p.first], p.first);
        }
    }
}

int main(void){
    cin >> N;
    REP(i,N) R[i] = -1;
    R[0] = 0;
    REP(i,N-1){
        cin >> u >> v >> w;
        q[u-1].push(PI(v-1,w));
        q[v-1].push(PI(u-1,w));
    }

    setter(0,0);

    REP(i,N) cout << R[i] << endl;
    return 0;
}



Measured memory_bytes: 70272
#include <iostream>
using namespace std;
typedef unsigned long long ll;
ll K,N,inf = 998244353;
ll func[4010] = {0};
ll inv[4010] = {0};

ll mult(ll n, ll m){
	if(n==0 || m==0) return 1;
	if(m==1) return n%inf;
	else if(m%2==0){
		ll t = mult(n,m/2);
		return (t*t)%inf;
	}else{
		ll t = mult(n,m-1);
		return (t*n)%inf;
	}
}

void factorial(ll N){
	for(ll i=0;i<=N;i++){
		if(i==0){
			func[i] = 1;
			inv[i] = 1;
		}
		else{
			func[i] = (i*func[i-1])%inf;
			inv[i] = mult(func[i],inf-2);
		}
	}
}

ll comb(ll n,ll k){
	if(n<k || n<0 || k<0) return 0;
//	if(k==0 || n==k) return 1;
	else return (((func[n]*inv[k])%inf)*inv[n-k])%inf;
}

ll hcomb(ll n,ll k){
	if(n==0 && k==0) return 1;
	return comb(n+k-1,k);
}

int main(){
	cin >> K >> N;
	factorial(4000);
	for(ll i=2;i<=2*K;i++){
		ll ans = 0;
		ll n = min(i,(2*K+2-i))/2;
		if(i%2==1){
			for(ll j=0;j<=n;j++){
				ll t = (comb(n,j)*mult(2,j))%inf;
				ans = (ans+hcomb(K-2*n+j,N-j)*t)%inf;
			}
		}else{
			n--;
			for(ll j=0;j<=n;j++){
				ll t = (comb(n,j)*mult(2,j))%inf;
				ans = (ans+hcomb(K-2*n-1+j,N-j-1)*t)%inf;
				ans = (ans+hcomb(K-2*n-1+j,N-j)*t)%inf;
			}
		}
		cout << ans << endl;
	}
}

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

template <class T>
inline void read(T &x) {
	static char ch; 
	while (!isdigit(ch = getchar())); 
	x = ch - '0'; 
	while (isdigit(ch = getchar()))
		x = x * 10 + ch - '0'; 
}

const int MaxN = 1e5 + 5; 

int n, K; 
struct per {
	int a[MaxN];

	inline void scan() {
		for (int i = 1; i <= n; ++i) {
			read(a[i]); 
		}
	}
	inline void print() {
		for (int i = 1; i <= n; ++i) {
			printf("%d%c", a[i], " \n"[i == n]); 
		}
	}

	inline per inv() {
		per res; 
		for (int i = 1; i <= n; ++i) {
			res.a[a[i]] = i; 
		}
		return res; 
	}
	inline per operator * (const per &rhs) const {
		per res; 
		for (int i = 1; i <= n; ++i) {
			res.a[i] = a[rhs.a[i]]; 
		}
		return res; 
	}
	inline per operator ^ (int p) const {
		per res; 

		static bool vis[MaxN]; 
		for (int i = 1; i <= n; ++i) vis[i] = false; 
		for (int i = 1; i <= n; ++i)
			if (!vis[i]) {
				int x = i, len = 0; 
				std::vector<int> cur; 

				while (!vis[x]) {
					cur.push_back(x); 
					vis[x] = true, x = a[x], ++len; 
				}

				for (int j = 0; j < len; ++j) {
					res.a[cur[j]] = cur[(j + p) % len]; 
				}
			}
		return res; 
	}
}a[10], A, B; 

int main() {
#ifdef orzczk
	freopen("permutation.in", "r", stdin); 
#endif
	
	read(n), read(K); 

	a[1].scan(), a[2].scan(); 
	for (int i = 3; i <= 6; ++i) {
		a[i] = a[i - 1] * a[i - 2].inv(); 
	}
	
	A = a[2] * a[1].inv() * a[2].inv() * a[1]; 
	B = A.inv(); 

	int t = (K - 1) / 6; 
	((A ^ t) * a[K - 6 * t] * (B ^ t)).print(); 

	return 0; 
}

Measured memory_bytes: 9108
#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<vector>
#include<random>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define endl "\n"
#define fi first
#define se second
#define db double
#define gcd __gcd
#define pb push_back
#define mp make_pair
#define lowbit(x) (x & (-x))
#define PII  pair<int, int> 
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << endl
#define rep(i, a, b) for(__typeof(b) i = a; i <= (b); i++)
#define Rep(i, a, b) for(__typeof(a) i = a; i >= (b); i--)
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
template<class T> inline T qmin(T a, T b) { return a < b ? a : b; }
template<class T> inline T qmax(T a, T b) { return a > b ? a : b; }
typedef long long ll;
typedef unsigned long long ull;
const db eps = 1e-9;
const db PI = acos(-1);
const int inf = 0x3f3f3f3f;
const int mod = (int)1e9 + 7;
const int maxn = (int)3e3 + 5;//remember to modify it, No RE or MLE
const ll INF = 0x3f3f3f3f3f3f3f3f;
using namespace std;
ll qpow(ll x, ll y) { ll ret = 1; for( ; y; y >>= 1, x = (x * x) % mod) if(y & 1) ret = (ret * x) % mod; return ret; }

inline int read(){
	char ch = getchar();
	int x = 0, f = 1;
	while(ch < '0' || ch > '9'){
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9'){
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

int n;
db p[maxn];
db dp[maxn][maxn];

int main()
{
	n = read();
	rep(i, 1, n) scanf("%lf", p + i);
	dp[0][0] = 1;
	rep(i, 1, n){
		dp[i][0] = dp[i-1][0] * (1 - p[i]);
		rep(j, 1, i){
			dp[i][j] = dp[i-1][j] * (1 - p[i]) + dp[i-1][j-1] * p[i];
		}
	}
	db ans = 0;
	Rep(i, n, (n + 2) / 2) ans += dp[n][i];
	printf("%.10f\n", ans);
	return 0;
}

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

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

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
typedef long long int ll;
static const ll MOD = 1000000007;

ll mod_pow(ll n, ll x){
	if(n == 0) return 1;
	ll ret = mod_pow(n / 2, x * x % MOD) % MOD;
	if(n % 2) return ret * x % MOD;
	return ret;
}

ll comb(int n, int k){
	if(k < 0 || k > n) return 0;
	vector<ll> memo(n + 1);
	memo[0] = 1; memo[1] = 1;
	for(int i = 2; i <= n; i++){
		memo[i] = memo[i - 1] * (ll)i;
		memo[i] %= MOD;
	}
	return ((memo[n] * mod_pow(MOD - 2, memo[k])) % MOD) * mod_pow(MOD - 2, memo[n - k]) % MOD;
}

int main(){
	int n, k;
	cin >> n >> k;
	cout << comb(n + k - 1, k - 1) << endl;
	return 0;
}



Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef tuple<ll, ll, ll> T;

int n, t;
vector<int> a(100001, 0);

int main(void){
	
	scanf("%d %d", &n, &t);
	for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
	
	int mx = -1, mn = a[0], cnt = 0;
	for(int i = 1; i < n; ++i){
	    mn = min(mn, a[i]);
	    if(mn == a[i] || mx > a[i] - mn) continue;
	    if(mx == a[i] - mn) ++cnt;
	    else cnt = 1;
	    mx = max(mx, a[i] - mn);
	}
	
	printf("%d\n", cnt);
	
    return 0;
}

Measured memory_bytes: 640
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <cassert>
#include <cmath>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long LL;
typedef pair<int, int> P;
typedef pair<LL, LL> PLL;

const int LIM = 100010;

int N;
LL a[LIM];
map<int, int> m;

int n;

int main() {
    cin >> N;
    for (int j = 0; j < N; ++j) {
        cin >> a[j];
        m[a[j]] = j;
    }
    sort(a, a + N);

    int ret = 0;
    for (int j = 0; j < N; ++j) {
        ret += (j + m[a[j]]) % 2;
    }

    cout << ret/2 << endl;

    return 0;
}


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

int main(){
  int n,K;
  cin >> n >> K;
  vector<pair<long,long>> p(n);
  rep(i,n){
    long x,y;
    cin >> x >> y;
    p.at(i).first = x;
    p.at(i).second = y;
  }
  sort(p.begin(),p.end());
  long ans = 1e18;
  ans *= 5;
  
  if(K == 2){
    rep(i,n-1){
      for(int j=i+1;j<n;j++){
        long x = abs(p.at(i).first - p.at(j).first);
        long y = abs(p.at(i).second - p.at(j).second);
        ans = min(ans,x*y);
      }
    }
    cout << ans << endl;
    return 0;
  }
  
  if(K == 3){
  rep(i,n-2){
    long sx,tx,sy,ty;
    for(int j=i+1;j<n-1;j++){
      for(int k=j+1;k<n;k++){
        /*if(k==j+1){
          sx = min(p.at(i).first,min(p.at(j).first,p.at(k).first));
          tx = max(p.at(i).first,max(p.at(j).first,p.at(k).first));
          sy = min(p.at(i).second,min(p.at(j).second,p.at(k).second));
          ty = max(p.at(i).second,max(p.at(j).second,p.at(k).second));
        }*/
        sx = min(p.at(i).first,min(p.at(j).first,p.at(k).first));
        tx = max(p.at(i).first,max(p.at(j).first,p.at(k).first));
        sy = min(p.at(i).second,min(p.at(j).second,p.at(k).second));
        ty = max(p.at(i).second,max(p.at(j).second,p.at(k).second));
        int count = 0;
        rep(l,n){
          long x = p.at(l).first;
          long y = p.at(l).second;
          if(sx <= x && x <= tx && sy <= y && y <= ty) count++;
        }
        if(count >= K){
          ans = min(ans,(ty-sy)*(tx-sx));
        }
      }
    }
  }
    cout << ans << endl;
    return 0;
  }
  
  rep(i,n-3){
    long sx,tx,sy,ty;
    for(int j=i+1;j<n-2;j++){
      for(int k=j+1;k<n-1;k++){
        for(int a=k+1;a<n;a++){
        sx = min(min(p.at(i).first,p.at(a).first),min(p.at(j).first,p.at(k).first));
        tx = max(max(p.at(i).first,p.at(a).first),max(p.at(j).first,p.at(k).first));
        sy = min(min(p.at(i).second,p.at(a).second),min(p.at(j).second,p.at(k).second));
        ty = max(max(p.at(i).second,p.at(a).second),max(p.at(j).second,p.at(k).second));
        int count = 0;
        rep(l,n){
          long x = p.at(l).first;
          long y = p.at(l).second;
          if(sx <= x && x <= tx && sy <= y && y <= ty) count++;
        }
        if(count >= K){
          ans = min(ans,(ty-sy)*(tx-sx));
        }
        }
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
while True:
  N = input()
  if not N:
    break
  a, b = -1, 100000000
  for j in range(N):
    i, h, w = map(int, raw_input().split())
    h /= 100.00
    bmi = w / (h * h)
    if abs(bmi - 22) < b:
      b = abs(bmi - 22)
      a = i
  print(a) 

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

int main(){
	int N;
	int A;
	int B;
	cin>>N>>A>>B;
	int a=A*N;
	int b=B;
	if(a<b){
		cout<<a;
	}
	else{
		cout<<b;
	}
	return 0;
}

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

int main(void){
    ll ans = 0;
    ll a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;

    ll mi = 10000000000000;
    for(int i = 0; i <= max(x, y); i++){
        ans = i * 2 * c;
        if(x - i > 0){
            ans += (x - i) * a;
        }
        if(y - i > 0){
            ans += (y - i) * b;
        }
        mi = min(mi, ans);
    }

    cout << mi << endl;
    return 0;
}


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

using namespace std;

#define fast_IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define int long long
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define MOD 1000000007

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

signed main()
{
    fast_IO;
    int test = 1;
    // cin >> test;
    while(test--)
    {
        int n;
        cin >> n;
        int a[n], ans = 0;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        for(int i = 1; i < n; i++)
        {
            ans += max(0LL, a[i - 1] - a[i]);
            a[i] = max(a[i], a[i - 1]);
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 5176
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

int main() {
  ll N, K;
  std::cin >> N >> K;
  vector<ll> x(N);
  REP(i, N) { std::cin >> x.at(i); }
  ll min_ = 1000000000;
  REP(i, N - K + 1) {
    ll left = x.at(i);
    ll right = x.at(i + K - 1);
    ll distance = abs(left - right);
    ll ltor = abs(left) + distance;
    ll rtol = abs(right) + distance;
    if (ltor < min_) {
      min_ = ltor;
    }
    if (rtol < min_) {
      min_ = rtol;
    }
  }
  std::cout << min_ << '\n';
}


Measured memory_bytes: 1024
n,k = map(int, input().split())
r,s,p = map(int, input().split())
t = list(input())

rsp = {"r":p, "s":r, "p":s}

ans = 0
for i in range(k): ans += rsp[t[i]]
for i in range(k,n):
  if t[i] != t[i-k]: ans += rsp[t[i]]
  else: t[i] = "a"
print(ans)

Measured memory_bytes: 9804
def insertionSort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
    return cnt


def shellSort(A, n):
    G = []
    h = 1
    while True:
        if h > n:
            break
        G.append(h)
        h = 3 * h + 1

    cnt = 0
    print(len(G))
    G = list(reversed(G))
    for g in G:
        cnt += insertionSort(A, n, g)

    print(*G)
    print(cnt)
    print('\n'.join(map(str, A)))


arr_length = int(input())
arr_num = []
for i in range(arr_length):
    arr_num.append(int(input()))

shellSort(arr_num, arr_length)


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

int main()
{
    int n, t, count=0;
    cin >> n;
    vector<int> array(n);
    for (int i = 0; i < n; i++)
    {
        cin >> array[i];
    }

    cin >> n;
    for(int i=0;i<n;i++){
        cin >> t;
        for(int s : array){
            if(s == t){
                ++count;
                break;
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3128
def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    total = 1000
    kabu = 0
    for i in range(N - 1):
        if A[i] < A[i+1]:
            kabu += int(total / A[i])
            total = total % A[i]
        else:
            total += kabu * A[i]
            kabu = 0
    print(total + kabu * A[i + 1])
main()

Measured memory_bytes: 9048
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define db double
#define ull unsigned long long
#define MIN INT_MIN
#define MAX INT_MAX
#define all(x) (x).begin(), (x).end()
#define ii pair <int,int>
#define iii pair <int,ii>
#define pll pair <ll,ll>
#define plll pair <ll,pll>
#define ff first
#define ss second
#define minQueue priority_queue <int,vector<int>,greater<int> >
#define maxQueue priority_queue<int,vector<int>,less<int> >
#define pb push_back
#define max3(a,b,c) max(a, max(b,c))
#define min3(a,b,c) min(a, min(b,c))
#define GCD(x,y) __gcd((x), (y))
#define LCM(x,y) ((x / GCD((x), (y))) * y)
#define loop(a,n) for(int i=a; i<n; i++)
#define mem(x,y) memset((x), (y), sizeof (x));
#define Case int T; scanf("%d", &T); for(int cas = 1; cas <= T; ++cas)
#define pf printf
#define sf scanf
#define Ziru 0
#define pr1(x) cout << x << endl
#define pr2(x,y) cout << x << ' ' << y << endl
#define powerOfTwo(x) (x && !(x & (x - 1)))
#define Iterator(type) type <int> :: iterator
#define mapIterator map <int,int> :: iterator //it->ff it->ss
#define FI freopen ("input.txt", "r", stdin)
#define FO freopen ("output.txt", "w", stdout)
using namespace std;


int main(){
    int n;
    vector <int> v;
    cin>>n;

    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        v.push_back(a);
    }
    int len=v.size();
    for(int i=len-1; i>=1; i--){
        cout<<v[i]<<" ";
    }
    cout<<v[0]<<endl;
    return Ziru;
}





Measured memory_bytes: 3160
N,M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
dp = [0]*(N+1)
dp[0] = 1
dp[1] =0 if 1 in a else 1
for i in range(2, N+1):
  dp[i] = (dp[i-1] + dp[i-2])%(10**9+7) if i not in a else 0
print(dp[N])

Measured memory_bytes: 13216
#include<iostream>
#include<string>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
#define rep(i,n) for(int i=0;i<(int)n;i++)

int main(void) {
	string str[3];
	rep(i, 3)cin >> str[i];
	rep(i, 3)
		printf("%c", str[i].at(0) - 0x20);
	return 0;
}

Measured memory_bytes: 256
S=input()
a,b=int(S[:2]),int(S[2:])
if 0<a<13 and 0<b<13:
    print('AMBIGUOUS')
elif 0<a<13:
    print('MMYY')
elif 0<b<13:
    print('YYMM')
else:
    print('NA')

Measured memory_bytes: 9000
#include <iostream>

int a[110][110];
using namespace std;
int main(){
	int r,c; cin >> r >> c ;
	for(int i=0;i<r;++i){
		for(int j=0;j<c;++j){
			cin >> a[i][j];
		}
	}
	for(int i=0;i<r;++i){
		int sum=0; for(int j=0;j<c;++j) sum+=a[i][j];
		a[i][c]=sum;
	}
	for(int j=0;j<=c;++j){
		int sum=0; for(int i=0;i<r;++i) sum+=a[i][j];
		a[r][j]=sum;
	}
	for(int i=0;i<=r;++i){
		for(int j=0;j<=c;++j){
			if(j!=0) cout << ' ' ;
			cout << a[i][j];
		}
		cout << '\n';
	}
}

Measured memory_bytes: 1204
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>

using ll = long long;


int main() {
    int N;
    std::cin >> N;
    std::map<std::string, std::vector<std::pair<int, int>>> m;
    for (int i = 0; i < N; i++) {
        std::string s;
        int p;
        std::cin >> s >> p;
        m[s].emplace_back(std::pair<int, int>(p, i + 1));
    }

    for (auto& s : m) {
        std::sort(s.second.begin(), s.second.end(), [](auto c1, auto c2)->bool {return c1.first > c2.first; });
        for (int i = 0; i < s.second.size(); i++) {
            std::cout << s.second[i].second << std::endl;
        }
    }

    return 0;
}


Measured memory_bytes: 256
require 'set'
require 'rational'

class Array
	def bsearch_first_index(l = 0, r = size - 1, &pred)
		return nil if l > r
		c = (l + r) / 2 
		if pred[self[c]]
			bsearch_first_index(l, c-1, &pred) || c
		else
			bsearch_first_index(c+1, r, &pred)
		end
	end

	def bsearch_first_item(l = 0, r = size - 1, &pred)
		i = bsearch_first_index(l, r, &pred)
		i ? self[i] : nil
	end
end

n = gets.to_i
as = gets.split.map(&:to_i)

ratios = Set.new
as.each do |a|
    (0..a-1).each do |d|
        ratios << Rational(d, a)
    end
end

ans = ratios.sort.bsearch_first_item {|r|
    d = r * as[0]
    s = ((as[0]-d).ceil .. (as[0]+d).floor).to_a
    as[1..-1].each do |a|
        min, max = a - a * r , a + a * r
        s2 = Set.new
        s.each do |x|
            ((min / x).ceil .. (max / x).floor).each do |k|
                s2 << x * k
            end
        end
        s = s2
    end
    ! s.empty?
}

printf("%.10f\n", ans)

Measured memory_bytes: 163044
N = int(input())
T, A = map(int, input().split())
H = list(map(int, input().split()))

rT = T - (H[0]*0.006)
dif = abs(A - rT)
ans = 1

for i in range(1, N):
    rTi = T - (H[i]*0.006)
    e_dif = abs(A - rTi)
    if e_dif<dif:
        dif = e_dif
        ans = i+1

print(ans)        






Measured memory_bytes: 3060
#include <iostream>
using namespace std;
int main(){
    int a;
    cin >> a;
    int n=a%10;
    if(n==2 or n==4 or n==5 or n==7 or n==9) cout << "hon" << endl;
    else if(n==3) cout << "bon" << endl;
    else cout << "pon" << endl;
    return 0;
}

Measured memory_bytes: 3540
#include<algorithm>
#include<complex>
#include<ctype.h>
#include<iomanip>
#include<iostream>
#include<map>
#include<math.h>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<stdio.h>
#include<string>
#include<string>
#include<vector>

using namespace std;
typedef long long ll;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

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

const ll mod = 1e9 + 7;
const ll inf = 1e18;

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

    // input
    ll a, b, c;
    cin >> a >> b >> c;

    p(a*b/2);
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  int N, K;
  cin >> N >> K;
  int a[N];
  for (int i = 0; i < N; i++)
  {
    cin >> a[i];
  }
  sort(a, a + N);
  int sum = 0;
  for (int i = 0; i < K; i++)
  {
    sum += a[i];
  }
  cout << sum << '\n';
}


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

typedef double du ;
typedef string st ;
typedef long long ll ;
typedef long double ld ;
typedef long long int lli ;

#define vi vector <lli>
#define loop(num) for (lli i = 0 ; i < num ; i ++ )
#define loopcin(num , ar ) for (lli i = 0 ; i < num ; i ++ ) {cin >> ar [i] ;}
#define loopcout(num , ar) for (lli i = 0 ; i < num ; i ++ ) {cout << ar [i] << ' '; }

#define forr(num1 , num2) for (lli i = num1 ; i < num2 ; i ++ )
#define forrcin(num1 , num2 , ar ) for (lli i = num1 ; i < num2 ; i ++ ) {cin >> ar [i] ;}
#define forrcout(num1 , num2 , ar) for (lli i = num1 ; i < num2 ; i ++ ) {cout << ar [i] << ' '; }

#define D2forrcin(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cin >> A[i][j] ;}}
#define D2forrcout(num1_1 , num1_2 , num2_1 , num2_2 , A ) for (lli i = num1_1 ; i < num1_2 ; i ++){ for (lli j = num2_1 ; j < num2_2 ; j++){cout << A[i][j] << ' ' ;}cout << endl ;}

#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

#define F first
#define S second

#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int main ()
{
    fastio
    lli num1 , num2 ;
    cin >> num1 >> num2 ;
    cout << ((num1 * num2) % 2 == 0 ? "Even" : "Odd") ;

    return 0 ;
}

/*___________________________________________________________________functions___________________________________________________________________________*/



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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define MOD 1000000007
#define el endl
#define INF 1e8
typedef long long ll;
typedef long double ld;

int main() {
    string s;
    cin >> s;
    int len = (int)s.length();
    string ans = "";
    rep(i, len){
        ans += "x";
    }
    cout << ans << endl;
}



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

int main() {
	int r, g, b;
	cin >> r >> g >> b;
	int a = r*100 + g*10 + b;
	if (a % 4 == 0) {
		cout << "YES" << endl;
	}
	else {
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ll long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
int main()
{
	string s, t;
	cin >> s;
	cin >> t;
	cout << (s[0]==t[0]) + (s[1]==t[1]) + (s[2]==t[2]) ;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

  class Main{
    public static void main(String args[]){
      Scanner sc = new Scanner(System.in);
  
      int a = sc.nextInt();
      int b = sc.nextInt();
      int x = sc.nextInt();
      int y = sc.nextInt();
      
      int ab = a*b;
      int xy = x*y;
      
      if(ab>xy){
        System.out.println(ab);
      }else{
        System.out.println(xy);
      }
  }
}

Measured memory_bytes: 22740
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#define rep(i, x, n) for(int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;
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;
}
const int MOD = 1000000007;
int main() {
    int N, D;
    cin >> N >> D;
    int k = 2 * D + 1;

    cout << (N + k - 1) / k << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 8
#define FREE 0
#define NOT_FREE 1

int row[N], col[N], dpos[2*N-1], dneg[2*N-1];
int X[N][N];

void init(){
  int i, j;
  for(i=0; i<N; i++) row[i] = col[i] = FREE;
  for(i=0; i<2*N-1; i++) dpos[i] = dneg[i] = FREE;
  for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
      X[i][j] = FREE;
    }
  }
}

void printBoard(){
  int i, j;
  for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
      if(X[i][j] == NOT_FREE) {
	if(row[i] != j) return;
      }
    }
  }
  for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
      if(row[i] == j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}

void putQueen(int i) {
  int j;
  if(i == N) {
    printBoard();
    return;
  }

  for(j=0; j<N; j++) {
    if(col[j] == NOT_FREE || dpos[i+j] == NOT_FREE || dneg[i-j+N-1] == NOT_FREE) continue;
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
    putQueen(i+1);
    row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
  }
}

int main() {
  int i, k, r, c;
  
  init();
  
  scanf("%d",&k);
  for(i = 0; i < k; i++) {
    scanf("%d%d",&r,&c);
    X[r][c] = 1;
  }

  putQueen(0);
  
  return 0;
}



Measured memory_bytes: 2112
import java.util.*;

class Main {
	Scanner sc;
	int[][] seg;
	int m;
	int N, Q;
	char[] S;
	static final int[] ZERO = new int[26];
	
	void calc() {
		sc = new Scanner(System.in);
		N = sc.nextInt();
		S = sc.next().toCharArray();
		Q = sc.nextInt();
		
		m = N-1;
		m = m | (m >>> 1);
		m = m | (m >>> 2);
		m = m | (m >>> 4);
		m = m | (m >>> 8);
		m = m | (m >>> 16);
		m += 1;
		
		seg = new int[2*m-1][26];
		
		for (int i = 0; i < S.length; i++) {
			int c = S[i] - 'a';
			seg[m-1+i][c] = 1;
		}
		for (int i = m-2; i >= 0; i--) {
			for (int j = 0; j < 26; j++)
				seg[i][j] = seg[i*2+1][j] + seg[i*2+2][j];
		}
		
		for (int i = 0; i < Q; i++) {
			int t = sc.nextInt();
			if (t == 1) {
				update(sc.nextInt()-1, sc.next().charAt(0));
			} else {
				calc(sc.nextInt()-1, sc.nextInt());
			}
		}
	}
	
	private void update(int index, char v) {
		int i = m-1+index;
		char o = (char)(S[index] - 'a');
		seg[i][o]--;
		seg[i][v - 'a']++;
		S[index] = v;
		
		while (i > 0) {
			i = (i-1) >>> 1;
			for (int j = 0; j < 26; j++) seg[i][j] = seg[i*2+1][j] + seg[i*2+2][j];
		}
	}
	
	private void calc(int s, int eExclusive) {
		int[] a = calcImpl(s, eExclusive, 0, 0, m);
		int v = 0;
		for (int i = 0; i < 26; i++) if (a[i] > 0) v++;
		System.out.println(v);
	}
	
	private int[] calcImpl(int s, int eExclusive, int n, int l, int r) {
		if (r <= s || eExclusive <= l) return ZERO;
		if (s <= l && r <= eExclusive) return seg[n];
		int[] buf = new int[26];
		int i = (l>>>1)+(r>>>1);
		int[] cl = calcImpl(s, eExclusive, 2*n + 1, l, i);
		int[] cr = calcImpl(s, eExclusive, 2*n + 2, i, r);
		for (int j = 0; j < 26; j++) buf[j] = cl[j] + cr[j];
		return buf;
	}
	
	public static void main(String[] args) {
		new Main().calc();
	}
}


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

using ll = int64_t;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

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

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

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

  int n, k, q;
  std::cin >> n >> k >> q;
  vi scores(n, k - q);
  rep(i, q) {
    int a;
    std::cin >> a;
    a--;
    scores[a]++;
  }

  for (auto &v : scores)
    if (v >= 1)
      std::cout << "Yes"
                << "\n";
    else
      std::cout << "No"
                << "\n";
}


Measured memory_bytes: 1024
#include <cstdio>
#include <vector>

std::vector<int> edges[100005];

int uninity[100005];

int msb[1<<20];

void dfs(int node,int parent){
  int once=0,twice=0;
  for(int child:edges[node]){
    if(child==parent) continue;
    dfs(child,node);
    twice|=(uninity[child]&once);
    once|=uninity[child];
  }
  uninity[node]=(once&~((1<<msb[twice])-1))+(1<<msb[twice]);
  //printf("uninity[%d]=%d\n",node,uninity[node]);
}

int main(){
  for(int i=1;i<(1<<20);i++){
    msb[i]=msb[i>>1]+1;
  }
  int N;
  scanf("%d",&N);
  for(int i=0;i<N-1;i++){
    int A,B;
    scanf("%d %d",&A,&B);
    A--,B--;
    edges[A].push_back(B);
    edges[B].push_back(A);
  }
  dfs(0,0);
  printf("%d\n",msb[uninity[0]]-1);
  return 0;
}


Measured memory_bytes: 15872
#pragma region template

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

// -type-
using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vs = vector<string>;


// -const-
const ll MOD = 1000000007;


const ll MAX = (ll)0x3f0000003f000000;
const double EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1},
          dy[] = {1, 0, -1, 0, 1, -1, -1, 1};


// -define-
#define reps(i, k, n) for (int i = (k), i##_len = (n); i < i##_len; ++i)
#define rep(i, n) reps(i, 0, n)
#define all(o) begin(o), end(o)
#define sz(a) ((int)(a).size())
#define debug(x) cerr << x << " (L:" << __LINE__ << ")" << '\n';


// -functions-

inline bool in(string s, string c) {
    return (s.find(c) != string::npos);
}
inline bool in(string s, char c) {
    return (s.find(c) != string::npos);
}

template <class T>
inline T udiv(T a, T b) {
    return (a + b - 1) / b;
}
template <class T>
inline T rdiv(T a, T b) {
    return (a + b / 2) / b;
}

template <class T>
void print(T& x) {
    cout << x << '\n';
}

struct setup_main {
    setup_main() {
        // cin.tie(0);
        // ios::sync_with_stdio(0);
        cout << fixed << setprecision(15);
    }
} setup_main_;

#pragma endregion

ll ans = 0;

void solve(long long N, std::vector<long long> d) {
    rep(i, N) {
        rep(j, i) {
            ans += d[i] * d[j];
        }
    }
    print(ans);
}
signed main() {
    long long N;
    scanf("%lld", &N);
    std::vector<long long> d(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &d[i]);
    }
    solve(N, std::move(d));

    return 0;
}


Measured memory_bytes: 256
//Name: Search
//Level: 2
//Category: 二分探索,シミュレーション
//Note:

/**
 * 問題文の通りに二分探索を実装し、比較回数を数える。
 *
 * オーダーは O(log N)。
 */

#include <iostream>
#include <vector>

using namespace std;

bool solve() {
    int N;
    if(!(cin >> N)) return false;
    if(!N) return false;

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

    int Q;
    cin >> Q;
    int ans = 0;
    int l = 0, r = N-1;
    while(l <= r) {
        const int m = (l+r) / 2;
        ++ans;
        if(v[m] == Q) {
            break;
        } else if(v[m] < Q) {
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans << endl;
    return true;
}

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

    while(solve()) ;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<x<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	ll n, a[5];
	cin>>n;
	ll mi=1e18;
	REP(i, 5){
		cin>>a[i];
		CHMIN(mi, a[i]);
	}
	cout<<(n-1)/mi+1+4;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
 
using namespace std;
 
#define INF 1000000007
#define LINF 1000000000000000007
 
typedef long long ll;
typedef pair<ll,ll> P;


int w, h, n, x[101], y[101], a[101];

int main(){
	cin >> w >> h >> n;
	int u = h, d = 0,l = 0,r = w;
	for(int i = 0; i < n; i++){
		cin >> x[i] >> y[i] >> a[i];
		if(a[i] == 1) l = max(l, x[i]);
		else if(a[i] == 2) r = min(r, x[i]); 
		else if(a[i] == 3) d = max(d, y[i]);
		else if(a[i] == 4) u = min(u, y[i]);
	}
	
	cout << max(0,(u-d)) * max(0,(r-l)) << endl;
	
	return 0;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
const int N = 2e5 + 7;
const ll mod = 998244353;

int main() {
	fastIO;
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> segs;
	for (int i = 0; i < k; i++) {
		int x, y;
		cin >> x >> y;
		segs.push_back({x, y});
	}
	ll dp[n+1] = {}, accum[n+1] = {};
	for (int i = 1; i <= n; i++) {
		if (i == 1) {
			dp[i] = 1;
			accum[i] = 1;
			continue;
		}
		int ans = 0;
		for (auto seg : segs) {
			int l = max(0, i-seg.second - 1), r = max(0, i-seg.first);
			ans += (accum[r] - accum[l] + mod) % mod;
			ans %= mod;
		}
		dp[i] = ans;
		accum[i] = ans + accum[i-1];
		accum[i] %= mod;
	}
	cout << dp[n];
}


Measured memory_bytes: 6768
""" AtCoder """

s = input()
ans = ''

for i in range(len(s)):
    if s[i] == 'B':
        if len(ans) != 0:
            ans = ans[:-1]
    elif s[i] == '1':
        ans += '1'
    else:
        ans += '0'

print(ans)


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

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int a, b, c;
    cin >> a >> b >> c;
    if(c >= a && c <= b)
        cout << "Yes";
    else cout << "No";
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <iostream>
#include <iomanip>
#include <map>
#include <algorithm>
#include <vector>
#include <math.h>
#include <queue>
#define MOD (long long)1000000007
#define INF (long long)998244353
using namespace std;

int main(void){
    string s;
    cin >> s;
    if(s.length()%2!=0){
            cout << "No" << endl;
            return 0;

    }
    for(int i=0; i+1<s.length(); i++){
        if(s[i]=='h' && s[i+1]=='i'){
            i++;
        }else {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC diagnostic ignored "-Wunused-result"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = (int)1e6 + 34;
//const ll INF = (ll)1e18 + 41;
const int INF = (int)1e9 + 41;
const ll MD = (ll)1e9 + 7;
bool D = false;

ll step(ll a, ll st) {
	if (st == 0) return 1;
	if (st % 2) return a * step(a, st - 1) % MD;
	ll q = step(a, st / 2);
	return q * q % MD;
}

ll bak(ll x) {
	return step(x, MD - 2);
}

void solve() {
	int n;
	cin >> n;
	ll ans = 0;

	vector<ll> sum(n + 1, 0);
	sum[1] = 1;
	ll f = 1;
	for (int i = 1; i <= n; i++) {
		f = f * i % MD;
	}
	for (int i = 2; i <= n; i++) {
		sum[i] = (sum[i - 1] + bak(i)) % MD;
	}

	for (int i = 0; i < n; i++) {
		ll x;
		cin >> x;

		ll num = (sum[i + 1] + sum[n - i] - 1 + MD);
		num = num * f % MD;
		ans = (ans + x * num) % MD;
	}
	cout << ans << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tst = 1;
	//scanf("%d", &tst);
	//cin >> tst;
#ifdef MADE_BY_SERT
	D = true;	
	tst = 3;
	while (tst--) {
		solve();
	}
#else
	while (tst--) solve();
#endif
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define whole(x) (x).begin(),(x).end()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
using ll = long long;
using P = pair<int, int>;
#define debug(var) cout << "[" << #var << "] " << var << endl
const ll mod = 1000000007;

ll level[55];
ll paty[55];

ll f(ll n, ll x) {
    if (x==0) return 0;
    if (x==level[n]) return paty[n];
    if (n==0) {
        if (x==1) return 1;
        else return -1;
    }
    if (x<=level[n-1]+1) {
        return f(n-1, x-1);
    }
    else {
        return 1LL + paty[n-1] + f(n-1, x-2-level[n-1]);
    }
}

int main(){
    ll n, x;
    cin >> n >> x;
    ll ans = 0;
    for (int i=0; i<=51; i++) {
        if (i==0) {
            level[i] = 1;
            paty[i] = 1;
            continue;
        }
        level[i] = level[i-1] * 2 + 3;
        paty[i] = paty[i-1] * 2 + 1;
    }
    ans = f(n, x);
    
    
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
from collections import Counter
n = int(input())
w = []

for k in range(n):
    w.append(input())

w_count = Counter(w)
if max(w_count.values()) > 1:
    print("No")
    exit()

for i in range(n - 1):
    tmp1, tmp2 = w[i][-1], w[i + 1][0]

    if tmp1 != tmp2:
        print("No")
        break

    if i == n - 2:
        print("Yes")


Measured memory_bytes: 3316
#include <iostream>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <string>
#include <sstream>
#include <algorithm>
#include <random>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <cassert>
#include <climits>
#include <bitset>
#include <functional>

#define FOR_LT(i, beg, end) for (int i = beg; i < end; i++)
#define FOR_LE(i, beg, end) for (int i = beg; i <= end; i++)
#define FOR_DW(i, beg, end) for (int i = beg; end <= i; i--)

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int a, b; cin >> a >> b;
	int m = 1; int c = 0;
	while (m < b) {
		m += a - 1;
		c++;
	}
	cout << c << endl;

	return 0;
}

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

int main() {
    ll n;
    cin >> n;
    ll a[n];
    for(ll i=0;i<n;i++) cin >> a[i];
    sort(a,a+n,greater<ll>());
    ll b[n];
    for(ll i=0;i<n;i++) b[i]=a[i]*2;
    ll res=0;
    if(n%2==0){
        ll m=n/2;
        for(ll i=0;i<m;i++){
            res+=b[i];
        }
        res-=a[0];
        cout << res << endl;
    }
    else{
        ll m=(n+1)/2;
        for(ll i=0;i<m;i++){
            res+=b[i];
        }
        res-=a[0]+a[m-1];
        cout << res << endl;
    }
    return 0;
}



Measured memory_bytes: 6704
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;

Node root, NIL;
int maxh;

Node treeSearch(Node u, int k){
  while( u != NIL && k != u->key ){
    if ( k < u->key ) u = u->left;
    else u = u->right;
  }
  return u;
}

void insert(int k){
  int H;
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while( x != NIL ){
    y = x;

    if ( z->key < x->key ){
      x = x->left;
    } 
    else {
      x = x->right;
    }

  }

  z->parent = y;
  if ( y == NIL ){
    root = z;
  } 
  else {
    if (z->key < y->key) {
      y->left = z;

    } 
    else {
      y->right = z;

    }
  }
}

void inorder(Node u){
  if ( u == NIL ) return;

  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
}
void preorder(Node u){
  if ( u == NIL ) return;

  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
}

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
  maxh = 0;
  for ( i = 0; i < n; i++ ){
    scanf("%s", com);

    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } 
    else if ( com[0] == 'i' ){
      scanf("%d", &x);

      insert(x);
    } 
    else if ( com[0] == 'p' ){
      
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }
  return 0;
}



Measured memory_bytes: 20516
let range ?(d=1) m n =
  let () = if d < 0 then failwith "range : d cannot be negative" in
  let rec iter i res =
    if i >= m then iter (i - d) (i::res)
    else res in
  let rec iter2 i res =
    if i <= m then iter2 (i + d) (i::res)
    else res in
  if m <= n then iter (n - ((n + m) mod d)) []
  else iter2 (n - ((n + m) mod d)) []

let (--) m n = range m n

let pr x = print_endline @@ string_of_int x

let n = Scanf.scanf "%d\n" (fun x -> x)

let b_cand = List.map (fun _ -> Scanf.scanf "%s\n" (fun x -> x)) (1--n)

let m = Scanf.scanf "%d\n" (fun x -> x)

let r_cand = List.map (fun _ -> Scanf.scanf "%s\n" (fun x -> x)) (1--m)

let b_count q = List.fold_left (fun cnt v -> if v = q then cnt + 1 else cnt) 0 b_cand

let r_count q = List.fold_left (fun cnt v -> if v = q then cnt - 1 else cnt) 0 r_cand

let () = List.map (fun q -> b_count q + r_count q) b_cand
         |> List.sort_uniq (fun a b -> compare b a)
         |> List.hd
         |> max 0
         |> pr


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)


int main(){
    string S; cin >> S;
//bit_flag集をvectorに格納
//
    vector<int> bit_flag(10);
    rep(i,10){
        bit_flag[i] = (1 << i);
    }

    int N = S.size(); // N = 10
    LL ans = 0;
    LL tmp = 1;
    // {0, 1, ..., n-1} の部分集合の全探索   n-1 = 8
    for (LL bit = 0; bit < (1<<N-1); ++bit){  // N-1 = 9
        tmp = 1;
        rep(i,N){
            if(bit_flag[i] & bit){
                ans += (S[N-1-i] - '0') * tmp;
                tmp = 1; 
            }
            else{
                ans += (S[N-1-i] - '0') * tmp;
                tmp *= 10;
            }
        }
    }
    cout << ans << endl;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<unordered_map>
#define ll long long
#define M 1000000007

#define pb push_back
#define fs first
#define se second
using namespace std;
// ll changeI(ll a)
// {
//     ll k=1;
//     ll st=0;
//     while(a)
//     {
//         st=(st%D+((a%10)*(k%D))%D)%D;
//         a/=10;
//         k*=100;
//     }
//     return st;
// }
 
long long powe(ll a, ll p , ll r)
{
    if(p==0)
        return 1;
    else if(p==1)
        return a;
    ll q=powe(a,p/2,r)%r;
    q= ((q%r)*(q%r))%r;
    if(p%2 == 1)
    {
        q = ((q%r)*(a%r))%r;
    }
    return q;
 
}
ll modInverse(ll a, ll m) 
{ 
    ll m0 = m; 
    ll y = 0, x = 1; 
  
    if (m == 1) 
      return 0; 
  
    while (a > 1) 
    { 
        // q is quotient 
        ll q = a / m; 
        ll t = m; 
  
        // m is remainder now, process same as 
        // Euclid's algo 
        m = a % m, a = t; 
        t = y; 
  
        // Update y and x 
        y = x - q * y; 
        x = t; 
    } 
  
    // Make x positive 
    if (x < 0) 
       x += m0; 
  
    return x; 
} 
pair<pair<ll,ll>,ll> maxSubArraySum(vector<ll>a, int size) 
{ 
    ll max_so_far = LLONG_MIN, max_ending_here = 0, 
       start =0, end = 0, s=0; 
    ll p=0;
    for (ll i=0; i< size; i++ ) 
    { 
        max_ending_here += a[i]; 
  
        if (max_so_far < max_ending_here) 
        { 
            max_so_far = max_ending_here; 
            start = s; 
            end = i; 
        } 
  
        if (max_ending_here < 0) 
        { 
            max_ending_here = 0; 
            s = i + 1; 
        } 
    } 
      
    return {{max_so_far,end},(end - start + 1)}; 
} 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //  #ifndef ONLINE_JUDGE
    //     freopen("mengawasi_sample_1.in", "r", stdin);
    //     freopen("mengawasi_sample_1.out", "w", stdout);
    // #endif
    ll n;
    cin>>n;
    vector<ll>arr(n);
    for(ll i=0;i<n;i++)
        cin>>arr[i];
    ll c=0;
    for(ll i=0;i<n;i++)
    {
        if(i+1 != arr[i])
            c++;
    }
    if(c<=2)
        cout<<"YES";
    else
        cout<<"NO";
    cout<<endl;
}


Measured memory_bytes: 256