akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#define MN 201000

int n, a[MN];
bool ok[MN]; int s[MN], f[MN];
int Max[MN * 20], ls[MN * 20], rs[MN * 20], tot = 0;
int rt[MN];

int modify(int x, int l, int r, int k, int v)
{
	int o = ++tot;
	ls[o] = ls[x]; rs[o] = rs[x];
	Max[o] = std::max(Max[x], v);
	if(l == r) return o;
	int mid = l + r >> 1;
	if(k <= mid) ls[o] = modify(ls[x], l, mid, k, v);
	else rs[o] = modify(rs[x], mid + 1, r, k, v);
	return o;
}

int query(int x, int l, int r, int L, int R)
{
	if(l == L && r == R) return Max[x];
	int mid = l + r >> 1;
	if(R <= mid) return query(ls[x], l, mid, L, R);
	else if(L > mid) return query(rs[x], mid + 1, r, L, R);
	else return std::max(query(ls[x], l, mid, L, mid), query(rs[x], mid + 1, r, mid + 1, R));
}

int Abs(int x) {return x > 0 ? x : -x;}

bool check(int len0, int len1, int now0, int now1, int i)
{
	if(Abs(len0 - len1) <= s[i] && ((len0 - len1) & 1) == (s[i] & 1)) return 1;
	if(len0 - len1 <= s[i] && len1 - len0 <= query(rt[i], 1, n, now0, n) - s[i]) return 1;
	if(len1 - len0 <= s[i] && len0 - len1 <= query(rt[i], 1, n, now1, n) - s[i]) return 1;
	return 0;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int now = 0;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] > now) ok[i] = 1;
		now = std::max(now, a[i]);
	}
	for(int i = n; i >= 1; i--)
	{
		s[i] = s[i + 1] + ok[i];
		int g = query(rt[i + 1], 1, n, a[i], n);
		if(!ok[i]) f[i] = std::max(2 * s[i], g) + 1;
		else if(g) f[i] = g + 2;
		rt[i] = modify(rt[i + 1], 1, n, a[i], f[i]);
	}
	int len0 = 0, len1 = 0, now0 = 1, now1 = 1;
	if(!check(0, 0, 1, 1, 1)) return 0 * puts("-1");
	for(int i = 1; i <= n; i++)
	{
		if(check(len0 + (a[i] >= now0), len1, std::max(now0, a[i]), now1, i + 1))
		{
			printf("0");
			len0 += (a[i] >= now0);
			now0 = std::max(now0, a[i]);
		}
		else
		{
			printf("1");
			len1 += (a[i] >= now1);
			now1 = std::max(now1, a[i]);
		}
	}
}

Measured memory_bytes: 50944
fun main(args: Array<String>){
    val c = Array(3){ readLine()!!.split(" ").map { it.toInt() }.toIntArray() }
    val f = c[0][1] - c[0][0] == c[1][1] - c[1][0] && c[1][1] - c[1][0] == c[2][1] - c[2][0] &&
            c[0][2] - c[0][1] == c[1][2] - c[1][1] && c[1][2] - c[1][1] == c[2][2] - c[2][1] &&
            c[0][0] - c[0][2] == c[1][0] - c[1][2] && c[1][0] - c[1][2] == c[2][0] - c[2][2] &&
            c[1][0] - c[0][0] == c[1][1] - c[0][1] && c[1][1] - c[0][1] == c[1][2] - c[0][2] &&
            c[2][0] - c[1][0] == c[2][1] - c[1][1] && c[2][1] - c[1][1] == c[2][2] - c[1][2] &&
            c[0][0] - c[2][0] == c[0][1] - c[2][1] && c[0][1] - c[2][1] == c[0][2] - c[2][2]
    println(if(f) "Yes" else "No")
}

Measured memory_bytes: 37900
#include<stdio.h>

int main(){
	int s,j,i,a[1000000],c=0;
	scanf("%d",&s);
	a[0]=s;
	for(i=1;;i++){
		if(a[i-1]%2==0)a[i]=a[i-1]/2;
		if(a[i-1]%2==1)a[i]=3*a[i-1]+1;
		for(j=0;j<i;j++){
			if(a[i]==a[j]){
				printf("%d\n",i+1);
				return 0;
			}
		}
	}
	return 0;
}

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

typedef long long ll;
ll mod = 1000000007;
const double PI = 3.141592653589793238460;

ll power(ll x, ll y)
{
    ll res = 1;
    x = x%mod;
    while (y)
    {
        if (y&1) res = ((res%mod)*(x%mod))%mod;

        y>>=1;
        x = ((x%mod)*(x%mod))%mod;
    }
    return res;
}

const int INF = 1e9+5;

int main(){

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

    int n, k;
    cin >> n >> k;
    vector<int> h(n+1);
    for(int i=1; i<=n; i++) cin >> h[i];    

    vector<int> dp(n+1, INF);
    dp[1]=0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=k && i+j<=n; j++){
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]));
        }
    }

    cout<<dp[n]<<'\n';

    return 0;
}


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

#define ull unsigned long long
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

const int INF = 1e9 + 7;


int main(void)
{
	FAST
	int n; cin >> n;
	
	vector<int> digits;
	
	int x = n%10;
	
	set<int> hon = {2,4,5,7,9};
	set<int> pon = {0,1,6,8};
	set<int> bon = {3};
	
	if(hon.count(x) != 0) cout << "hon";
	else if(pon.count(x) != 0) cout << "pon";
	else cout << "bon";
	
	
	return 0;
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#define lp3(i,a,b) for(int i=a;i<b;i++)
#define lp2(i,n) for(int i=0;i<n;i++)
#define ll long long
#define W 1000000007
using namespace std;

int main(){
	int n,sum=0;
	cin>>n;
	for(int i=n;i>0;i--)sum+=i;
	cout<<sum<<endl;
	return 0;
}


Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author bcools
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskA solver = new TaskA();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskA {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int a = in.nextInt();
            int b = in.nextInt();

            if (a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0) out.println("Possible");
            else out.println("Impossible");
        }

    }
}



Measured memory_bytes: 21844
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <cmath>
using namespace std;
#define MOD 1000000007
#define MAX 510000
#define INF 1<<30
#define LINF (ll)1<<62
#define rep(i,n) for(ll i=0; i<(n); i++)
#define REP(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> P;
typedef vector<pair<ll, ll>> vpl;

int main(){
    ll n; cin >> n;
    vl a(n),b(n),c(n-1);
    rep(i,n) cin >> a[i];
    rep(i,n) cin >> b[i];
    rep(i,n-1) cin >> c[i];
    ll mae = INF;
    ll ans = 0;
    rep(i,n){
        ll t = a[i] - 1;
        if(mae == t-1) ans += c[mae];
        ans += b[t];
        mae = t;
        //cout << ans << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
# define ll int64_t
# define rep(i,n) for(ll i=0;i<n;i++)
# define rrep(i,n) for(ll i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
# define mod 1000000007
# define PI 3.141592653589793
# define vec vector
#define dump(x) cerr<<#x<<"="<<x<<endl
using namespace std;

bool compare_by_b(pair<string,ll> a,pair<string,ll> b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}

bool my_compare(pair<string,ll> a,pair<string,ll> b){
    if(a.first != b.first) return a.first<b.first;
    if(a.second != b.second) return a.second>b.second;
    else return true;
}

ll factorial(ll n){
    ll x=1;
    rrep(i,n) (x*=i)%=mod;
    return x;
}

ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b,a%b));
}

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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    vector<ll> s(4,0);
    rep(i,3){
        ll a,b;
        cin>>a>>b;
        s[a-1]++;
        s[b-1]++;
    }
    sort(ALL(s));
    cout<<(s[3]>=3 ? "NO":"YES")<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main(void){
  char s[11], t[11];
  scanf("%s", s);
  int i, j = 0;
  for(i = 0; i < strlen(s); i++){
    if(s[i] != 'B') t[j++] = s[i];
    else{
      if(0 < j) t[--j] = '\0';
      else t[j] = '\0';
    }
  }
  t[j] = '\0';
  
  printf("%s\n", t);
  return 0;
}

Measured memory_bytes: 128
import sys

sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque


'''
dp[i][j]...(0,0)からスタートして(i,j)に到達する経路のなかでの最大の価値
dp[i][j]=max(dp[i][j-1],dp[i-1][j]) + v[i][j]


dp[i][j][k] ... (0,0)からスタートして(i,j)に到達する経路のなかでi行目ですでにk(以下)個選んでいるときの最大の価値

遷移は、i,jのvを拾うときと拾わないときのmax
dp[i][j][k] = max(dp[i][j-1][k-1]+V[i,j], dp[i][j-1][k]
                  ) #k個のままのほうが価値が高いかk-1から拾ったほうが価値が高いか

上からの遷移 # 拾うか拾わないかでこうかな
dp[i][j][0]=max(dp[i][j-1][0],max_k(dp[i-1][j]))
dp[i][j][1]=max(dp[i][j-1][0],max_k(dp[i-1][j][k])+V[i][j])
'''

R, C, K = ints()
RCV = read_tuple(K)
V = [[0] * C for _ in ra(R)]
for r, c, v in RCV:
    V[r - 1][c - 1] = v

# dp = [[[0] * 4 for _ in ra(C)] for _ in ra(R)]
dp0 = [[0] * C for _ in ra(R)]
dp1 = [[0] * C for _ in ra(R)]
dp2 = [[0] * C for _ in ra(R)]
dp3 = [[0] * C for _ in ra(R)]

# dp[0][0][0] = 0
dp1[0][0] = V[0][0]
dp2[0][0] = V[0][0]
dp3[0][0] = V[0][0]

for j in ra(1, C):
    dp1[0][j] = max(dp1[0][j - 1], dp0[0][j - 1] + V[0][j])
    dp2[0][j] = max(dp2[0][j - 1], dp1[0][j - 1] + V[0][j])
    dp3[0][j] = max(dp3[0][j - 1], dp2[0][j - 1] + V[0][j])

for i in ra(1, R):
    dp0[i][0] = dp1[i - 1][0]
    dp1[i][0] = dp0[i][0] + V[i][0]
    dp2[i][0] = dp0[i][0] + V[i][0]
    dp3[i][0] = dp0[i][0] + V[i][0]


for i in ra(1, R):
    for j in ra(1, C):
        ma = max(dp0[i - 1][j],
                 dp1[i - 1][j],
                 dp2[i - 1][j],
                 dp3[i - 1][j])

        dp0[i][j] = max(dp0[i][j - 1],  # 左
                        ma)  # 上

        if ma > max(dp3[i][j - 1], dp2[i][j - 1], dp1[i][j - 1]):  # 上から採用
            dp1[i][j] = ma + V[i][j]
            dp2[i][j] = ma + V[i][j]
            dp3[i][j] = ma + V[i][j]
        else:  # 横から採用
            dp1[i][j] = max(dp0[i][j - 1] + V[i][j],  # 左から来て拾う
                            dp1[i][j - 1],  # 拾わないほうが大きい場合もある
                            ma + V[i][j])  # 上から来て拾う
            dp2[i][j] = max(dp1[i][j - 1] + V[i][j], dp2[i][j - 1])
            dp3[i][j] = max(dp2[i][j - 1] + V[i][j], dp3[i][j - 1])


print(max(dp0[R - 1][C - 1],
          dp1[R - 1][C - 1],
          dp2[R - 1][C - 1],
          dp3[R - 1][C - 1],
          ))

# print(*values, sep='\n')
# print(*dp3, sep='\n')

# dp2 = [[-1] * C for _ in ra(R)]
# for i in ra(R):
#     for j in ra(C):
#         dp2[i][j] = max(dp[i][j])
# print(*dp2, sep='\n')


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

using namespace std;

int h[200000];
int dp[200000];

int main()
{
  int n;
  cin>>n;
  for(int i=0;i<n;i++){
      cin>>h[i];
  }
  dp[0]=0;
  dp[1]=abs(h[1]-h[0]);
  for(int i=2;i<n;i++){
      dp[i]=min(dp[i-1]+abs(h[i-1]-h[i]),dp[i-2]+abs(h[i-2]-h[i]));
      
  }
  cout<<dp[n-1]<<"\n";
  
   
   return 0;
}

Measured memory_bytes: 1024
#include<stdio.h>

int main(){

	int a,b,c,i,t;

	scanf("%d",&t);

	for(i=0;i<t;i++)
	{
		scanf("%d %d %d",&a,&b,&c);
		if(a*a==b*b+c*c){
			printf("YES\n");
		}else if(b*b==a*a+c*c){
			printf("YES\n");
		}else if(c*c==a*a+b*b){
			printf("YES\n");
		}else{
			printf("NO\n");}
	}
	
	return 0;
}

Measured memory_bytes: 580
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll n; cin >> n;
  vl sum(n+1);
  
  rep(i,n){
    ll x; cin >> x;
    sum[i+1] = sum[i] + x;
  }
  
  ll ans = 1e10;
  for(ll i=1; i <= n; i++){
    ans = min(ans,abs(sum[n]-2*sum[i]));
  }
  
  cout << ans << endl;
  
  
}

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

using namespace std;

void solve(string S, string T) {
  int n = S.length();

  for (int i = 0; i < n; i++) {
    string c = S.substr(n - 1, 1);
    S.pop_back();
    S = c + S;
    if (S == T) {
      printf("Yes\n");
      return;
    }
  }
  printf("No\n");
}

int main() {
  string S, T;
  cin >> S >> T;
  solve(S, T);
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<math.h>
using namespace std;

int D, N;

double calc_dist(int i, int j, vector<vector<int>> &points){
    double dist = 0.0;
    for(int d = 0; d < D; ++d){
        dist += (double)((points[i][d] - points[j][d]) * (points[i][d] - points[j][d]));
        //cout << points[i][d] << " " << points[j][d] << " " << dist << endl;
    }
    return sqrt(dist);
}

int main(void){

    int cnt = 0;
    double dist = 0.0;
    cin >> N >> D;
    vector<vector<int>> points;
    points.resize(N);

    for(int n = 0; n < N; ++n){
        points[n].resize(D);
        for(int i=0; i < D; ++i){
                int x;
                cin >> x;
                points[n][i] = x;
        }
    }

    for(int n = 0; n < N; ++n){
        for(int m = n+1; m < N; ++m){
            dist = calc_dist(n,m,points);
            if(fabs(ceil(dist) - floor(dist))< 1.0e-03){
                cnt++;
            }
        }

    }
  
    cout << cnt;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<cstdio>
#define LL long long
using namespace std;
int n,m;
const int N=100010,mod=1e9+7;
int a[N];
struct ju
{
	LL v[3][3];
	ju(){memset(v,0,sizeof(v));}
	friend ju operator *(const ju &a,const ju &b)
	{
		ju c;
		for(int i=0;i<=2;++i)
			for(int j=0;j<=2;++j)
				for(int k=0;k<=2;++k)
					(c.v[i][j]+=a.v[i][k]*b.v[k][j])%=mod;
		return c;
	}
}A,B,Ans;
ju ksm(ju a,LL b)
{
	ju res;res.v[0][0]=res.v[1][1]=res.v[2][2]=1;
	for(;b;b>>=1,a=a*a)
		if(b&1)res=res*a;
	return res;
}
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;++i)scanf("%d",&a[i]);
	A.v[0][0]=A.v[1][0]=A.v[1][2]=2;
	A.v[0][1]=A.v[0][2]=A.v[1][1]=A.v[2][0]=A.v[2][2]=1;
	
	B.v[0][0]=B.v[0][1]=B.v[0][2]=B.v[1][1]=B.v[2][2]=1;
	B.v[1][2]=2;
	
	Ans.v[0][0]=1;
	for(int i=1;i<=m;++i)Ans=Ans*ksm(A,a[i]-a[i-1]-1)*B;
	Ans=Ans*ksm(A,n-a[m]);
	cout<<Ans.v[0][2];
	return 0;
}
/*
3 1 
2

13

5 2
2 3

66

10 9
1 2 3 4 5 6 7 8 9

100
*/

Measured memory_bytes: 640
n,z,w = gets.split.map(&:to_i)
a = gets.split.map(&:to_i)

ans = 0
if n == 1
    ans = (a[0] - w).abs
else
    ans = [(a[n-1] - a[n-2]).abs, (a[n-1] - w).abs].max
end

puts ans

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

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

  int a,b,c,x,y;
  cin >> a >> b>>c>>x>>y;

  int ans = 0;
  int ab = min(x, y);
  ans += ab * min(a+b, c*2);
  ans += (x - ab) * min(2 * c, a);
  ans += (y - ab) * min(2 * c, b);
  cout << ans << "\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REPR(i,n) for (int i=(int)(n)-1;i>=0;--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define valid(y,x,h,w) (0<=y&&y<h&&0<=x&&x<w)
#define tpl(...) make_tuple(__VA_ARGS__)
const int INF = 0x3f3f3f3f;
const double EPS = 1e-8;
const double PI = acos(-1);
const int dy[] = {-1,0,1,0};
const int dx[] = {0,1,0,-1};
typedef long long ll;
typedef pair<int,int> pii;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename Ch,typename Tr,typename C,typename=decltype(begin(C()))>basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>&os,
const C& c){os<<'[';for(auto i=begin(c);i!=end(c);++i)os<<(i==begin(c)?"":" ")<<*i;return os<<']';}
template<class S,class T>ostream&operator<<(ostream &o,const pair<S,T>&t){return o<<'('<<t.first<<','<<t.second<<')';}
template<int N,class Tp>void output(ostream&,const Tp&){}
template<int N,class Tp,class,class ...Ts>void output(ostream &o,const Tp&t){if(N)o<<',';o<<get<N>(t);output<N+1,Tp,Ts...>(o,t);}
template<class ...Ts>ostream&operator<<(ostream&o,const tuple<Ts...>&t){o<<'(';output<0,tuple<Ts...>,Ts...>(o,t);return o<<')';}
template<class T>void output(T t,char z=10){if(t<0)t=-t,putchar(45);int c[20];
int k=0;while(t)c[k++]=t%10,t/=10;for(k||(c[k++]=0);k;)putchar(c[--k]^48);putchar(z);}
template<class T>void outputs(T t){output(t);}
template<class S,class ...T>void outputs(S a,T...t){output(a,32);outputs(t...);}
template<class T>void output(T *a,int n){REP(i,n)cout<<a[i]<<(i!=n-1?',':'\n');}
template<class T>void output(T *a,int n,int m){REP(i,n)output(a[i],m);}
template<class T>bool input(T &t){int n=1,c;for(t=0;!isdigit(c=getchar())&&~c&&c-45;);
if(!~c)return 0;for(c-45&&(n=0,t=c^48);isdigit(c=getchar());)t=10*t+c-48;t=n?-t:t;return 1;}
template<class S,class ...T>bool input(S&a,T&...t){input(a);return input(t...);}
template<class T>bool inputs(T *a, int n) { REP(i,n) if(!input(a[i])) return 0; return 1;}

int main() {
  int n, k;
  while(cin>>n>>k) {
    string s;
    cin >> s;
    int i = 0, j = 0;
    int ana = 0;
    int ans = 0;
    while (j < n) {
      while(j < n)
      {
        if (s[j] == '0')
        {
          if (ana == k + 1) break;
          while(j < n && s[j] == '0') j++;
          ana++;
        }
        else j++;
        if (ana <= k) chmax(ans, j - i);
      }
      // cout << i << " " << j << endl;
      if (ana <= k) {
        break;
      }
      while (i < n && ana > k) {
        if (s[i] == '0')
        {
          while(i < n && s[i] == '0') i++;
          ana--;
        }
        else {
          while(i < n && s[i] == '1') i++;
        }
      }
      // cout << i << " " << j << endl;
      chmax(ans, j - i);

    }
    cout << ans << endl;
  }
}


Measured memory_bytes: 512
#include <stdio.h>
 
int main(void){
  int n,m,l,i,j,k;
  int amat[100][100],bmat[100][100];
  unsigned long cmat[100][100];
 
  for(i=0;i<100;i++){
    for(j=0;j<100;j++){
      amat[i][j]=0;  bmat[i][j]=0;  cmat[i][j]=0;
    }
  }
  scanf("%d%d%d",&n,&m,&l);
  for(i=0;i<n;i++){
    for(j=0;j<m;j++)  scanf("%d",&amat[i][j]);
  }
  for(i=0;i<m;i++){
    for(j=0;j<l;j++)  scanf("%d",&bmat[i][j]);
  }
 
  for(i=0;i<n;i++){
    for(j=0;j<l;j++){
      for(k=0;k<m;k++)  cmat[i][j]+=(amat[i][k]*bmat[k][j]);
    }
  }
 
  for(i=0;i<n;i++){
    for(j=0;j<l-1;j++)  printf("%lu ",cmat[i][j]);
    printf("%lu\n",cmat[i][l-1]);
  }
 
  return 0;
}

Measured memory_bytes: 760
def prime_factorize(n):
    a=[]
    while n%2 ==0:
        a.append(2)
        n //= 2
    f = 3
    while f*f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n!=1:
        a.append(n)
    return a
n,p = map(int,input().split())
keys_l = []
import collections
c=collections.Counter(prime_factorize(p))
#print(c)

ans = 1
a=1
a_l=[]
for key in c.keys():
    if c[key] >= n:
        #for a in range(2,(c[key]//n)+1):
            #if c[key]>= n*a:
               # a_l.append(a)
                #print(a_l)
        #ans *= key * max(a_l)
        ans *= key**(c[key]//n)
        #print('ans',ans,'key',key)

print(ans)     

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

using T = tuple<int32, int32, int32>;

vector<T> G;
int64 N=20, M;
int64 idx;

void init(int64 X){
	REP(i, N-1){
		G.push_back(T(i, i+1, 0));
	}
	int64 a = 0;
	idx = 0;
	while((1<<a)-1 <= X-1){
		a++;
	}
	a--;
	while(1<<idx <= X){
		idx++;
	}
	idx--;
	cerr << idx << endl;

	REP(i, a){
		G.push_back(T(i, i+1, 1<<i));
	}
}

void answer(){
	cout << N << " " << G.size() << endl;
	REP(i, G.size()){
		int32 a, b, c;
		tie(a, b, c) = G[i];
		cout << a+1 << " " << b+1 << " " << c << endl;
	}
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 L;
	cin >> L;
	init(L);

	while(idx >= 0){
		if(L >> idx & 1){
			int32 k = idx-1;
			while(k >= 0 && !(L >> k & 1)){k--;}
			if(k >= 0){
				G.push_back(T(k, N-1, L & ~((1<<(k+1))-1)));
				cerr << (L & ~((1 << (k+1))-1)) << endl;
			}
		}
		idx--;
	}

	answer();
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector <int> ans(1000000,0);
  for(int i = 0;i<999;i++){
      ans.at(i*i) = 1;
  }
  int a, b;
  cin >> a >> b;
  if(b/10==0) b += a*10;
  else if(b/100==0) b += a*100;
  else b += a*1000;
  if(ans.at(b)) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 7004
#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
  int n;
  cin >> n;
  int num;
  if (n >= 64) num = 64;
  else if (n >= 32) num = 32;
  else if (n >= 16) num = 16;
  else if (n >= 8) num = 8;
  else if (n >= 4) num = 4;
  else if (n >= 2) num = 2;
  else num = 1;

  cout << num << endl;
  
  return 0;
}


Measured memory_bytes: 256
-- https://github.com/minoki/my-atcoder-solutions
{-# LANGUAGE BangPatterns #-}
import Data.Char (isSpace)
import Data.List (unfoldr)
import Control.Monad
import Control.Monad.ST
import qualified Data.Vector as V
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Builder as BSB
import System.IO (stdout)
import Data.Monoid

warshallFloyd1 :: Int -> U.Vector (Int, Int, Int) -> V.Vector (U.Vector Int)
warshallFloyd1 !n !edges = runST $ do
  !arr <- V.replicateM n (UM.replicate n (10^9+1))
  U.forM_ edges $ \(a,b,c) -> do
    UM.write (arr V.! a) b c
    UM.write (arr V.! b) a c
  forM_ [0..n-1] $ \a -> do
    UM.write (arr V.! a) a 0
  flip V.imapM_ arr $ \ !k !a_k -> do
    V.forM_ arr $ \ !a_i -> do
      !a_ik <- UM.read a_i k
      forM_ [0..n-1] $ \j -> do
        a_kj <- UM.read a_k j
        UM.modify a_i (min (a_ik + a_kj)) j
  V.mapM U.unsafeFreeze arr

warshallFloyd2 :: Int -> Int -> V.Vector (U.Vector Int) -> V.Vector (U.Vector Int)
warshallFloyd2 !n !l !graph = runST $ do
  !arr <- V.replicateM n (UM.replicate n (10^9+1))
  flip V.imapM_ (V.zip arr graph) $ \ !a (!a_a,!g_a)-> do
    flip U.imapM_ g_a $ \b v -> do
      when (v <= fromIntegral l) $ do
        UM.write a_a b 1
    UM.write a_a a 0
  flip V.imapM_ arr $ \ !k !a_k -> do
    V.forM_ arr $ \ !a_i -> do
      !a_ik <- UM.read a_i k
      forM_ [0..n-1] $ \j -> do
        a_kj <- UM.read a_k j
        UM.modify a_i (min (a_ik + a_kj)) j
  V.mapM U.unsafeFreeze arr

main = do
  [n,m,l] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
  edges <- U.replicateM m $ do
    [a,b,c] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (a-1,b-1,c)
  let !w1 = warshallFloyd1 n edges
      !w2 = warshallFloyd2 n l w1
  q <- readLn
  queries <- U.replicateM q $ do
    [s,t] <- unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
    return (s,t)
  BSB.hPutBuilder stdout $ mconcat [ BSB.intDec (if d > 10^9 then -1 else d - 1) <> BSB.char7 '\n' | (s,t) <- U.toList queries, let d = w2 V.! (s-1) U.! (t-1) ]


Measured memory_bytes: 7676
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007
	ll ch[26];
int main() {
	ll h,w;
	cin>>h>>w;

	for(ll i=0;i<h;i++){
		for(ll j=0;j<w;j++){
			char now;
			cin>>now;
			ch[now-'a']++;
		}
	}
	bool ans=true;
	ll cnt1=0;
	for(ll i=0;i<26;i++){
		if(ch[i]%2!=0){
			cnt1++;
			ch[i]--;
		}
	}
	if(cnt1>=2){
		ans=false;
	}
	if(cnt1==1){
		if(h%2==0||w%2==0){
			ans=false;
		}
	}
//	cout << ans<<endl;
	ll cnt2=0;
	for(ll i=0;i<26;i++){
		if(ch[i]%4!=0){
			cnt2++;
		}
	}
	if(cnt2!=0){
		ll now=0;
		if(h%2!=0){
			now+=w/2;
		}
		if(w%2!=0){
			now+=h/2;
		}
		if(cnt2>now){
			ans=false;
		}
	}
	cout << (ans?"Yes":"No");
	// your code goes here
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
	int n,m,i,j,k,a,b,min=999999999,ans=0;
	scanf("%d %d",&n,&m);
	char map[n][m+1];
	for(i=0;i<n;i++){
		scanf("%s",map[i]);
	}
	
	
	for(a=0;a<=n-3;a++){
		for(b=a+1;b<=n-2;b++){
			
			for(i=0;i<=a;i++){
				for(j=0;j<m;j++){
					if(map[i][j]!='W')ans++;
				}
			}
			
			for(i=a+1;i<=b;i++){
				for(j=0;j<m;j++){
					if(map[i][j]!='B')ans++;
				}
			}
			
			for(i=b+1;i<n;i++){
				for(j=0;j<m;j++){
					if(map[i][j]!='R')ans++;
				}
			}
			
			if(ans<min)min=ans;
			ans=0;
		}
	}
	
	
	
	printf("%d\n",min);
	return 0;
}

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

int main()
{
    int n, num, pc, qc;
    int qnum = 0;
    int pnum = 0;
    cin >> n;
    num = n;
    vector<int> p(n), q(n), fp(n), fq(n);
    rep(i, n) cin >> p[i];
    rep(i, n) cin >> q[i];

    rep(i, n) {
        int pcnt = 0;
        int qcnt = 0;
        if (i == 0) {
            rep(j, n) if (p[i] == j+1) {
                pc = j;
                fp[i] = j+1;
                break;
            }
            rep(j, n) if (q[i] == j+1) {
                qc = j;
                fq[i] = j+1;
                break;
            }
        }
        else {
            rep(j, n) if (p[i] == j+1) {
                fp[i] = j+1;
                rep(k, i) if (p[i] > fp[k]) pcnt++;
                pc = j - pcnt;
                break;
            }
            rep(j, n) if (q[i] == j+1) {
                fq[i] = j+1;
                rep(k, i) if (q[i] > fq[k]) qcnt++;
                qc = j - qcnt;
                break;
            }
        }
        int sum=1;
        for (int i=1; i < num; i++) sum *= i;
        pnum = pnum + (sum * pc);
        qnum = qnum + (sum * qc);
        num--;
    }

    cout << abs(pnum - qnum) << endl;
    
    return 0;
}

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

int main()
{
  int n;
  cin>>n;
  int64_t time=0;
  string ans="Yes";
  vector<pair<int64_t,int64_t>> t(n);
  for(int i=0;i<n;i++)
  {
    cin>>t.at(i).second>>t.at(i).first;
  }
  sort(t.begin(),t.end());
  for(int i=0;i<n;i++)
  {
    time+=t.at(i).second;
    if(t.at(i).first<time)
    {
      ans="No";
      break;
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 6408
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
if n==1:
    print(0)
    quit()
a.sort(reverse=True)
ans=0
ans+=a[0]
n-=2
cnt=2
while n:
    ans+=a[cnt//2]
    cnt+=1
    n-=1
    # print(ans,cnt,n)
print(ans)

Measured memory_bytes: 94400
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<algorithm>
#include<functional>
#include<utility>
#include<bitset>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<cstdio>
#include<cstring>
#define n 1e9+5
typedef long long ll; 
using namespace std;
ll N,T,aa,res=0,pos=0;
bool a[int(n)];
int main()
{
	cin>>N>>T;
	for (ll i=0;i<N;i++){
		cin>>aa;
		if (aa>pos) {res+=T;pos=aa+T-1;}
		else if ((aa+T-1)>pos) {res+=aa+T-1-pos;pos=aa+T-1;} 
	}
	cout<<res+1;
	return 0;
}

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

//配列を表示する関数
void ShowAllay(const int a[], int n){
    for(int i = 0; i < n;i++){
        if(i>0) cout << " ";
        cout << a[i];
    }
    cout << endl;
}

//挿入ソート
void insertionSort(int a[], int n){
    for(int i = 1;i<n;i++){
        int key = a[i];
        //a[0]~a[i-1]のソートされた部分に挿入する。
        int j = i-1;
        while(j >=0 && a[j]>key){
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = key;
        ShowAllay(a,n);
    }
}

int main(void){
    int n;
    cin >> n;
    int a[n];
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    ShowAllay(a,n);
    insertionSort(a, n);
    return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
#define im 2147483647
#define lm 9223372036854775807
#define ll long long
#define vb vector<bool>
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define ii pair<int, int>
#define lower_str(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
#define upper_str(s) transform(s.begin(), s.end(), s.begin(), ::toupper)
#define debug(index, num) cout << "Case #" << index << ": " << num << endl
#define mx(an, na) an = max(an, na)
#define mn(an, na) an = min(an, na)
#define rep(i, a, b) for (long long i = a; i < b; i++)
#define rep2(i, a, b) for (long long i = a; i <= b; i++)
#define repp(i, a, b) for (long long i = a; i >= b; i--)
#define repp2(i, a, b) for (long long i = a - 1; i >= b; i--)
#define be(x) x.begin(), x.end()
#define rbe(x) x.rbegin(), x.rend()
#define pb push_back   

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
  vector<int> data(4);
  for(int i = 0; i < 4; i++)cin >> data.at(i);
  sort(data.begin(), data.end());
  int A[4] = {1, 4, 7, 9};
  for(int i = 0; i < 4; i++){
    if(A[i] != data.at(i)){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}


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

void Simaltaneous(double a,double b,double c,double d,double e,double f){
    double x,y;
    y=(a*f-d*c)/(a*e-d*b);
    x=(c-b*y)/a;
    printf("%4.3f %4.3f\n",x,y);
    return ;
}

int main(){
    double a,b,c,d,e,f;
    while(cin >>a>>b>>c>>d>>e>>f){
        Simaltaneous(a,b,c,d,e,f);
    }
    return 0;
}

Measured memory_bytes: 1236
#include <cmath>

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <map>
#include <set>
#include <vector>

using namespace std;

int main() {
#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif

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

  cout.precision(16);
  cout << fixed;

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

  cout << min(n * a, b);
}


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

typedef long long ll;
typedef string st;
typedef vector<int> vi;
typedef vector<st> vs;
#define rep(i, n) for(int i = 0; i < n; i++)
#define fogg(i,a,b) for(int i = (a); i <= (b); i++)
#define ford(i,a,b) for(int i = (a); i >= (b); i--)
#define test int t; cin >> t; while(t--)
#define debug(x) cout << '>' << #x << ':' << x << "\n";
#define endl '\n'
#define pb push_back
#define gp " "
#define ff first
#define ss second
#define mp make_pair



int main() {
	ll n;
	cin >> n;
	ll ans=0;
	int temp = n/500;
	n = n-temp*500;
	ans+=1000*temp;
	ans+=(n/5)*5;
	cout << ans;

	return 0;
}

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


int main(){
  std::string str;
  std::cin >> str;
  char prev=str[0];
  for(auto &&c : str)
  {
    if(c != prev){
      std::cout << "Yes" << std::endl;
      return 0;
    }
  }
  std::cout << "No" << std::endl;
  return 0;
}

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

using namespace std;
typedef long long ll;

#define INF 2000000000
#define LLINF 4000000000000000000
#define SIZE 5000

int other = 0;

/* topologicalSort */
const int topo_SIZE = 5000;

vector<int> topologicalSort(vector<vector<int> > G,int n=-1){
    int indeg[topo_SIZE] = {0},u;
    vector<int> ret,ret2;
    queue<int> que;
    
    if(n==-1) n=(int)G.size();
    
    for(int i=0;i<n;i++){
        for(int j=0;j<G[i].size();j++){
            indeg[G[i][j]]++;
        }
    }
    
    for(int i=0;i<n;i++){
        if(indeg[i]==0){
            que.push(i);
        }
    }
    
    while(!que.empty()){
        
        if(que.size() > 1) other = 1;
        
        u = que.front();
        que.pop();
        
        ret.push_back(u);
        
        for(int i=0;i<G[u].size();i++){
            indeg[G[u][i]]--;
            if(indeg[G[u][i]]==0){
                que.push(G[u][i]);
            }
        }
    }
    
    if(n==(int)ret.size()){
        return ret;
    }else{
        return ret2;
    }
}

int main(){
    int n,m,w,l;
    vector<vector<int> > result(SIZE);
    vector<int> ans;
    
    
    scanf("%d%d",&n,&m);
    
    for(int i=0;i<m;i++){
        scanf("%d%d",&w,&l);
        w--;
        l--;
        result[w].push_back(l);
    }
    
    ans = topologicalSort(result,n);
    
    for(int i=0;i<n;i++){
        printf("%d\n",ans[i]+1);
    }
    
    printf("%d\n",other);
    
    return 0;
}

Measured memory_bytes: 2576
// God put a smile upon your face <3

#include <bits/stdc++.h>`

#define slld(longvalue) scanf("%lld", &longvalue)

#define ll long long
#define ull unsigned long long
#define pll pair < long long, long long >

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

#define pb push_back

#define bug printf("BUG\n")

#define mxlld LLONG_MAX
#define mnlld -LLONG_MAX

#define mxd 2e8
#define mnd -2e8

#define pi 3.14159265359

#define mod 958585860497

#define base 2001487

using namespace std;

bool check(ll n, ll pos)
{
	return n & (1LL << pos);
}

ll Set(ll n, ll pos)
{
	return n = n | (1LL << pos);
}

int main()
{
    ll i, j, k, l, m, n, o, r, q;
    ll testcase;
    ll input, flag, tag, ans;

//    freopen("input.txt", "r", stdin);

//    freopen("output.txt", "w", stdout);

    string s;

    while(cin >> s)
    {
		for(auto &it: s) if(it == '?') it = 'D';
		cout << s << '\n';
    }


}





Measured memory_bytes: 3748
#include<stdio.h>
#include<stdlib.h>
 
struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node *Node;
#define NIL NULL
 
Node root;
/*
  Node treeMinimum(Node x){
  while(x->left != NIL){
  x=x->right;
  }
  return x;
  }
   
  Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key){
  return u;
  }
  if(k<u->key){
  return treeSearch(u->left,k);
  } else {
  return treeSearch(u->right,k);
  }
  }
   
  Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL){
  return treeMinimum(x->right);
  }
  y=x->parent;
  while(y!=NIL && x==y->right){
  x=y;
  y=y->parent;
  }
  return y;
  }
   
  void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
   
   
   
  }
*/
void insert(int k){
   
  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){
    inorder(u->left);
    printf(" %d",u->key);
    inorder(u->right);
  }
}
void preorder(Node u){
  if(u!=NIL){  
    printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}
 
 
int main(){
  int n, i, x;
  char com[20];
  Node z;
  scanf("%d", &n);
   
  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");
      } else if ( com[0] == 'd' ){
    scanf("%d", &x);
    //treeDelete(treeSearch(root, x));
      }
  }
   
  return 0;
}

Measured memory_bytes: 24036
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};

#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;

int main(){
    mp::cpp_int t1,t2,a1,a2,b1,b2;cin >> t1 >> t2 >> a1 >> a2 >> b1 >> b2;
    mp::cpp_int v1 = a1 * t1 + a2 * t2, v2 = b1 * t1 + b2 * t2;
    if(v1==v2){
        puts("infinity");
        return 0;
    }
    if(v1 < v2){
        swap(v1,v2);
        swap(a1,b1);
        swap(a2,b2);
    }
    mp::cpp_int l = -1,r = mp::cpp_int("100000000000000000000000");
    if(a1 > b1){
        puts("0");
        return 0;
    }
    while(abs(r - l) > 1){
        mp::cpp_int m = (r - l) / 2 + l;
        mp::cpp_int t = (v1 - v2) * m;
        mp::cpp_int k1 = t+a1*t1, k2 = b1*t1;
        if(k1 > k2){
            r = m;
        }
        else{
            l = m;
        }
    }
    mp::cpp_int ans = 2 * l + 1;
    if(l > 0){
        mp::cpp_int k1 = (v1-v2)*l+a1*t1, k2 = b1*t1;
        if(k1==k2) ans--;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main() {
    int H, W, i, j;
    while (scanf("%d%d", &H, &W) == 2 && (H || W)) {
        for (i = 0; i < H; i++) {
            printf("#");
            for (j = 1; j < W - 1; j++) {
                if (i > 0 && i < H - 1) {
                    printf(".");
                } else {
                    printf("#");
                }
            }
            printf("#\n");
        }
        printf("\n");
    }
    return 0;
}

Measured memory_bytes: 588
#include <iostream>
#include <string>
using namespace std;
// const string S = "(1+1)*2";
string S;
int cur = 0;
int digit();
int number();
int factor();
int term();
int _term(int m);
int exp();
int _exp(int m);
int parse();
bool isdigit(char);
bool is_plu_min(char);
bool is_tim_div(char);
int main() {
  int N;
  cin >> N;
  for (int i=0;i<N;i++) {
    cin >> S;
    cur = 0;
    S.resize(S.size()-1);
    cout << parse() << endl;
  }
  return 0;
}
int digit() {
  int n = S[cur] - '0';
  cur++;
  return n;
}
int number() {
  int n = digit();
  while (cur < S.size() && isdigit(S[cur]))
    n = n*10 + digit();
  return n;
}
bool isdigit(char c) {
  if (c <= '9' and c >= '0') return true;
  else return false;
}
bool is_plu_min(char c) {
  if (c == '+' || c == '-') return true;
  else return false;
}
bool is_tim_div(char c) {
  if (c == '*' || c == '/') return true;
  else return false;
}
// exp    = term exp`
// exp`   = + term exp` | eps
// term   = factor term`
// term`  = * factor term` | eps
// factor = ( exp ) | num
int term() {
  int n = factor();
  return _term(n);
}
int _term(int m) {
  int n = m;
  switch (S[cur]) {
    case '*':
      cur++;
      n *= factor();
      return _term(n);
    case '/':
      cur++;
      n /= factor();
      return _term(n);
    default:
      return n;
  }
}
int factor() {
  if (S[cur] != '(') return number();
  else {
    cur++;
    int n = exp();
    cur++;
    return n;
  }
}
int exp() {
  int n = term();
  return _exp(n);
}
int _exp(int m) {
  int n = m;
  switch (S[cur]) {
    case '+':
      cur++;
      n += term();
      return _exp(n);
    case '-':
      cur++;
      n -= term();
      return _exp(n);
    default:
      return n;
  }
}
int parse() {
  return exp();
}

Measured memory_bytes: 1204
#if defined(LOCAL)
#define PROBLEM_NAME "a"
const double _max_double_error = 1e-9;
#include "testutils.h"
#define L(x...) (debug(x, #x))
#define C(x...) CHECK(x)
#else
#define L(x, ...) (x)
#define C(x, ...) ;
#include <bits/stdc++.h>
#endif

using namespace std;
using vi = vector<int>; using vvi = vector<vi>;
using ii = pair<int,int>; using vii = vector<ii>;
using l = long long; using vl = vector<l>; using vvl = vector<vl>;
using ll = pair<l,l>; using vll = vector<ll>; using vvll = vector<vll>;
using lu = unsigned long long;
using vb = vector<bool>; using vvb = vector<vb>;
using vd = vector<double>; using vvd = vector<vd>;
using mll = unordered_map<l, l>;
const l INF = numeric_limits<l>::max();
const double EPS = 1e-10; static constexpr auto PI = acos(-1);
const l e0=1, e3=1000, e5=100000, e6=10*e5, e7=10*e6, e8=10*e7, e9=10*e8;
const char lf = '\n';
#define all(x) begin(x), end(x)
#define F(a,b,c) for (l a = l(b); a < l(c); a++)
#define B(a,b,c) for (l a = l(c) - 1; a >= l(b); a--)

void solve(istream& cin, ostream& cout) {
  l a, b, c, x, y;
  cin >> a >> b >> c >> x >> y;
  l ans = 0;
  if (2 * c <= a + b) {
    ans += 2 * c * min(x, y);
    if (x > y) {
      swap(x, y);
      swap(a, b);
    }
    if (2 * c <= b) {
      ans += 2 * c * (y - x);
    } else {
      ans += b * (y - x);
    }
  } else {
    ans = x * a + y * b;
  }
  cout << ans << lf;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cout << fixed << setprecision(15);
#if defined(LOCAL)
  // _generate_random_test = generate_random;
  // _solve_brute = solve_brute;
  // _player_b = player_b;
  // _custom_solution_checker = solution_checker;
  maybe_run_tests(cin, cout);
#else
  solve(cin, cout);
#endif
}


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

int main() {
  int W, a, b;
  scanf("%d%d%d", &W, &a, &b);

  if ((a <= b && b <= a + W) || (b <= a && a <= b + W)) {
    printf("0");
  } else {
    if (a < b) {
      printf("%d", min(b - (a + W), (b + W) - a));
    } else {
      printf("%d", min((a + W) - b, a - (b + W)));
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define all(v) (v).begin(), (v).end()
#define rev(s) (s).rbegin(), (s).rend()
#define MP make_pair
#define X first
#define Y second
#define debug(x) cout << #x << " = " << x << endl;
#define sq(x) ((x)*(x))

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> vi;

struct Point{ 
    double a, b, L;
    double operator-(const Point &r){ 
        return sq(r.a-a)+sq(r.b-b)+sq(r.L-L);
    }
};

int popcnt(int x){
    int cnt = 0;
    while(x > 0){
        x&=x-1;
        cnt++;
    }
    return cnt;
}

int main(){
    int n, m;
    cin >> n >> m;
    vector<Point> v(n);
    rep(i, n){ 
        cin >> v[i].L >> v[i].a >> v[i].b;
    }
    double cost[21][21];
    rep(i, n) for(int j = i; j < n; j++){
        cost[i][j] = cost[j][i] = v[i]-v[j];
    }

    int use = 0;
    double ans = 0;
    while(++use < (1<<n)){
        if(popcnt(use) != m) continue; 
        vector<int> elem;
        rep(i, n){
            if((use>>i)&1) elem.push_back(i);
        }
        double sum = 0;
        rep(i, m) for(int j = i+1; j < m; j++){ 
            sum += cost[elem[i]][elem[j]];
        }
        ans = max(sum, ans);
    }
    cout.setf(ios::fixed);
    cout.precision(6);
    cout << ans << endl;

	return 0;
}

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

using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n, x, a, b;
	vector<int> hist{0};
	
	cin>>n;
	
	while (n--)
	{
		cin>>x;
		a = floor(log2(x)), b = ceil(log2(x));
		
		if (hist.back() <= a)
		{
			hist.push_back(a);
			hist.push_back(b);
		}
		else
		{
			hist.push_back(b);
			hist.push_back(a);
		}
	}
	
	stack<int> s;
	int sol = 0;
	for (int x: hist)
	{
		if (!s.empty() && s.top() >= x)
		{
			sol += s.top() - x;
			
			while (!s.empty() && s.top() >= x)
				s.pop();
		}
		s.push(x);
	}
	sol += s.top();
	
	cout<<sol<<'\n';
}


Measured memory_bytes: 1400
n = int(input())
p = list(map(int, input().split()))

q = [0] * n
for i in range(n):
    if i == p[i]-1:
        q[i] = 1
    if q[i-1] == 1 and q[i] == 1:
        q[i] = 0
print(sum(q))

Measured memory_bytes: 20540
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define _USE_MATH_DEFINES
#include <math.h>
#define rep(i,n) for(int i = 0;i < n;i++)
#define NIL = -1;

unsigned getdigit(unsigned NUM){
    return log10(NUM) + 1;
}

ll gcd(long long a,long long b) {
    if (a < b) swap(a,b);
    if (b == 0) return a;
    
    return gcd(b,a%b);
}

ll lcm(ll a,ll b){
    a / gcd(a,b) * b;
}
const ll mod = 1e9 + 7;
const ll INF = 1e9 + 7;

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


/////////////////////////////////////////////////////////////////////////////////////////
int main(){
    int n;
    cin >> n;
    int g[15][15];
    for (int i = 0;i < 15;i++){
        for (int j = 0;j < 15;j++){
            g[i][j] = -1;
        }
    }

    for (int i = 0;i < n;i++){
        int a;
        cin >> a;
        for (int j = 0;j < a;j++){
            int x,y;
            cin >> x >> y;
            x--;
            g[i][x] = y;
        }
    }

    int ans = 0;
    for (int bit = 0;bit < (1 << n);bit++){
        vector<int> d(n);
        for (int i = 0;i < n;i++){
            if (bit >> i&1){
                d[i] = 1;
            }
        }
        bool ok = true;
        for (int i = 0;i < n;i++){
            if (d[i]){
                for (int j = 0;j < n;j++){
                    if (g[i][j] == -1)continue;
                    if (g[i][j] != d[j]) ok = false;
                }
            }
        }
        if (ok) ans = max(ans,__builtin_popcount(bit));
    }

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

Measured memory_bytes: 256