akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll n, m;
	cin >> n >> m;

	string s; cin >> s;
	
	set<ll> safe;
	FOR(i,0,n+1) if (s[i] == '0') safe.insert(i);

	vl dist(n+1,oo);
	dist[n] = 0;
	
	ll i = n;
	vl path = {n};
	while (i > 0) {
		ll ni = i;
		FORD(j,max(0LL,i-m),i) if (s[j] == '0') {
			dist[j] = dist[i]+1;
			ni = j;
		}
		if (ni == i) {
			cout << -1 << endl;
			return 0;
		}
		i = ni, path.pb(i);
	}
	
	reverse(all(path));
	FOR(i,0,sz(path)-1) {
		cout << path[i+1]-path[i] << " ";
	}
	cout << endl;
}



Measured memory_bytes: 6984
#include <stdio.h>
#include <string.h>
#include <math.h>
int main(void)
{
    int P, Q, R;
    int ans;
    scanf("%d %d %d", &P, &Q, &R);
    ans = P + Q;
    if (ans > P + R) {
        ans = P + R;
    }
    if (ans > Q + R) {
        ans = Q + R;
    }
    printf("%d", ans);
    return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <stdio.h>
using namespace std;

int main(){
    int n = 10000;
    int N = 0;
    int H[n];
    int W[n];
    int h, w;

    bool flag = 0;

    for(int i = 0; i < n; i++){
        cin >> H[i] >> W[i];
        N++;
        if(H[i] == 0 and W[i] == 0){
            break;
        }
    }
    
    for(int i = 0; i < N - 1; i++){ 
        flag = 0;
        if(W[i] % 2 != 0){ 
        for(int y = 0; y < H[i]; y++){
            for(int x = 0; x < W[i]; x++){
                if(flag == 0){
                    printf("#");
                    flag = 1;
                }
                else{
                    printf(".");
                    flag = 0;
                }
            }
            printf("\n");
        }    
        printf("\n");
        }
        else{ 
        for(int y = 0; y < H[i]; y++){
            for(int x = 0; x < W[i]; x++){
                if(flag == 0){
                    printf("#");
                    flag = 1;
                }
                else{
                    printf(".");
                    flag = 0;
                }
            }
            flag = !flag;
            printf("\n");
        }    
        printf("\n");
        }
    }
    return 0;
}


Measured memory_bytes: 3104
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <iomanip>	
#include <deque>
#include <set>
#include <climits>
#include <memory>
#include <numeric>
#include <utility>


#define rep(i,a,b) for(int i=a;i<b;++i)
#define rrep(i,a,b) for(int i=a;i>=b;--i)
#define fore(i,a) for(auto &i:a)
#define INF INT_MAX/2;
#define PI 3.14159265358979323846264338327950L;
const int INF2 = 1001001001;
typedef long long ll;
using namespace std;
using vi = vector<int>;
using vll = vector<ll>;
ll mod = 1e9 + 7;
//ll llmax = 10000000000000000000ll;
const ll LINF = 1e18;
using namespace std;
using Graph = vector<vector<int>>;



int cnt_digit(ll N)
{
	int digit = 0;

	while (N > 0)
	{
		N /= 10;
		digit++;
	}
	return digit;
}


 // 最大公約数計算
 
ll gcd(ll a, ll b)
{
	if (b == 0) {
		return a;
	}
	else {
		return gcd(b, a % b);
	}
}
// 最小公倍数の計算

ll lcm(ll a, ll b)
{
	ll g = gcd(a, b);

	return a / g * b;
}

struct union_find
{
	vector<int> par, r;
	union_find(int n)
	{
		par.resize(n);
		r.resize(n);
		init(n);
	}


	void init(int n)
	{
		for (int i = 0; i < n; i++) par[i] = i;
		for (int i = 0; i < n; i++) r[i] = 0;
	}

	int find(int x)
	{
		if (par[x] == x)return x;
		else return find(par[x]);
	}

	void unite(int x, int y)
	{
		x = find(x);
		y = find(y);

		if (r[x] < r[y])
		{
			par[x] = y;
		}
		else
		{
			par[y] = x;
			if (r[x] == r[y])
			{
				r[x]++;
			}
		}
	}
};

const int MAX_N = 110000;

int memo[MAX_N];

int rec(int n) {
	if (n == 0)return 0;
	if (memo[n] != -1)return memo[n];

	int res = n;

	for (int pow6 = 1; pow6 <= n; pow6 *= 6)res = min(res, rec(n - pow6) + 1);

	for (int pow9 = 1; pow9 <= n; pow9 *= 9)res = min(res, rec(n - pow9) + 1);

	return memo[n] = res;
}

int calc(int x) {
	int ret = 0;
	while (x % 2 == 0) {
		x /= 2;
		ret++;
	}

	return ret;
}

int a[12][12];
int D;
ll G;
vector<ll> P, C;

//aのp乗を求めるアルゴリズム
long modpow(long a, int p) {
	if (p == 0)return 1;
	if (p % 2 == 0) {
		//pが偶数のとき
		int halfP = p / 2;
		long half = modpow(a, halfP);
		return half * half % mod;
	}
	else {
		//pが奇数の時は、
		//pを偶数にするために1減らす
		return a * modpow(a, p - 1) % mod;
	}

}


//(10*9*8)/(3*2*1);
//10*9*8 -> ansMul
//3*2*1 -> ansDiv;
long calcComb(int a, int b) {
	if (b > a - b) return calcComb(a, a - b);
	long ansMul = 1;
	long ansDiv = 1;
	rep(i, 0, b) {
		ansMul *= (a - i);
		ansDiv *= (i + 1);
		ansMul %= mod;
		ansDiv %= mod;
	}
	//ansMul /ansDivをやりたい
	//ansDivの逆元を使って求めよう。

	long ans = ansMul * modpow(ansDiv, mod - 2) % mod;
	return ans;

}

bool is_war(const vector<int>& x, const vector<int>& y) {
	for (int Z = -100; Z <= 100; Z++) {
		bool is_ok = true;
		rep(i, 0, x.size()) {
			if (x[i] >= Z) {
				is_ok = false;
			}
			rep(i, 0, y.size()) {
				if (y[i] < Z) {
					is_ok = false;
				}
			}
			
		}
		if (is_ok)return false;
		
	}
	return true;
}
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);

	int s, t;
	cin >> s;
	
	int h = s / 100;
	if (100 * h + 10 * h + h >= s) {
		cout << 100 * h + 10 * h + h << endl;

	}
	else {
		cout << 100 * (h + 1) + 10 * (h + 1) + h + 1 << endl;
	 }



}


Measured memory_bytes: 256
require 'set'

MOD = 1000000007

A = Set.new

# s = input()
# n = int(input())
# A = list(map(int, input().split()))
n, m = gets.split.map(&:to_i)

m.times {
  a = gets.to_i
  A.add(a)
}

res = [0]*(n+1)

res[0] = 1
if !A.include?(1)
  res[1] = 1
end

(2..n).each do |i|
  next if A.include?(i)
  res[i] = (res[i-1] + res[i-2])%MOD
end

p(res[n])


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

int dfs(int n,int s,int i){
  if(n == 0){
    if(s == 0)return 1;
    else return 0;
  }
  if(s - i < 0)return 0;
  if(i > 9)return 0;

  return dfs(n,s,i + 1) + dfs(n - 1,s - i,i + 1);
}

int main(){
  int n,s;
  
  while(cin >> n >> s,n|s){
    cout << dfs(n,s,0) << endl;
  }
}

Measured memory_bytes: 3080
N, A, B, C = map(int, input().split())

MOD = 10**9 + 7
M = 2*N

fact = [1]*(M+1)
rfact = [1]*(M+1)
r = 1
for i in range(1, M+1):
  fact[i] = r = r * i % MOD
rfact[M] = r = pow(fact[M], MOD-2, MOD)
for i in range(M, 0, -1):
  rfact[i-1] = r = r * i % MOD

rev = pow(A+B, MOD-2, MOD)

p = 0
b = B * rev % MOD
e = 1
for k in range(N):
    v = fact[N+k-1] * rfact[N-1] * rfact[k] % MOD
    v = v * e * (N + k) % MOD
    e = e * b % MOD
    p += v
p *= pow(A * rev % MOD, N, MOD) * 100 * rev % MOD

q = 0
b = A * rev % MOD
e = 1
for k in range(N):
    v = fact[N+k-1] * rfact[N-1] * rfact[k] % MOD
    v = v * e * (N + k) % MOD
    e = e * b % MOD
    q += v
q *= pow(B * rev % MOD, N, MOD) * 100 * rev % MOD

print((p + q) % MOD)

Measured memory_bytes: 20084
#include <bits/stdc++.h>
using namespace std;
int main () {
  int A;
  cin >> A;
  int B;
  cin >> B;
  if ( A % 2 == B % 2 ) {
    cout << (A+B) / 2 << endl; }
  else {
    cout << "IMPOSSIBLE" ; } }
  

Measured memory_bytes: 256
n=int(input())
s_=input()
r, g, b = s_.count("R"), s_.count("G"), s_.count("B")
rgb = r * g * b
cnt=0
for i in range(len(s_)):
  for j in range(i+1,len(s_)):
    h=j-i+j
    if h<n:
      if s_[i]!=s_[j] and s_[h]!=s_[j] and s_[i]!=s_[h]:
        cnt+=1

print(rgb-cnt)
    

Measured memory_bytes: 9188
#include<stdio.h>

int main(){
        int i;
        int d;
        int sum;

        while(scanf("%d",&d) != EOF){
                sum = 0;
                for(i = d; i < 600; i += d)
                        sum += i * i * d;                  

                printf("%d\n",sum);
        }


        return 0;
}

Measured memory_bytes: 596
fun main(args: Array<String>) {
    val (N, K) = listOfInt()
    val L = listOfInt()
    val R = L.asReversed()
    val nk = Math.min(N, K)
    var ans = Long.MIN_VALUE
    for (A in 0 .. nk) {
        for (B in 0 .. nk - A) {
            val v = mutableListOf<Int>()
            for (l in 0 until A) v.add(L[l])
            for (r in 0 until B) v.add(R[r])
            v.sort()
            val k = Math.min(K - (A + B), v.count { it < 0 })
            val d = v.drop(k).sumByDouble { it.toDouble() }.toLong()
            if (ans < d) ans = d
        }
    }
    println(ans)
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)

Measured memory_bytes: 41128
H,N=map(int, input().split())
A=[list(map(int, input().split())) for i in range(N)]
maxa=max(a for a,b in A)
DP=[0]*(H+maxa)
for i in range(0,H+maxa):
  if i<=0:
    DP[i]=0
  else:
    DP[i]=min(DP[i-a]+b for a,b in A)
print(min(DP[H:]))

Measured memory_bytes: 3668
#pragma region header
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define resort(v) sort((v).rbegin(), (v).rend())
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vb vector<bool>
#define vvb vector<vector<bool>>
using ll = long long;
using P = pair<int, int>;
/* ----------------よく使う数字や配列----------------- */
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
constexpr ll mod = 1e9+7;
constexpr ll inf = INT32_MAX/2;
constexpr ll INF = LLONG_MAX/2;
constexpr long double eps = DBL_EPSILON;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */

/* --------------------テンプレート------------------ */
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;
}
/* ----------------------end----------------------- */

/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ----------------------end----------------------- */
#pragma endregion
int n,k,dp[100100];

signed main() {
    cin >> n >> k;
    fill(dp,dp+n,inf);
    dp[0]=0;
    vi h(n);
    rep(i, n)cin >> h[i];
    rep(i, n) {
        rep1(j, k) {
            chmin(dp[i+j],dp[i]+abs(h[i]-h[i+j]));
        }
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 4708
#include <cstdio>

const int MaxN = 100000 + 5, MaxM = 100000 + 5;

struct Graph {
  int cnte;
  int Head[MaxN], To[MaxM], Next[MaxM];

  inline void addEdge(int from, int to) {
    cnte++; To[cnte] = to;
    Next[cnte] = Head[from]; Head[from] = cnte;
  }
};

int N, M;
int Ind[MaxN];
int Dp[MaxN];
Graph G;

inline int max(int x, int y) { return x > y ? x : y; }

void init() {
  scanf("%d %d", &N, &M);
  for (int i = 1; i <= M; ++i) {
    int u, v;
    scanf("%d %d", &u, &v);
    Ind[v]++;
    G.addEdge(u, v);
  }
}

void solve() {
  static int que[MaxN];
  int head = 1, tail = 0;
  for (int i = 1; i <= N; ++i)
    if (Ind[i] == 0) que[++tail] = i;
  while (head <= tail) {
    int u = que[head++];
    for (int i = G.Head[u]; i; i = G.Next[i]) {
      int v = G.To[i];
      Dp[v] = max(Dp[v], Dp[u] + 1);
      Ind[v]--;
      if (Ind[v] == 0) que[++tail] = v;
    }
  }
  int ans = 0;
  for (int i = 1; i <= N; ++i)
    ans = max(ans, Dp[i]);
  printf("%d\n", ans);
}

int main() {
  init();
  solve();
  return 0;
}

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

const string data[2]={"JOI","IOI"};
int main() {
	// your code goes here
	string str;
	while(cin>>str){
		int ans[2]={0,0};
		for(int i=0;i<(int)str.size()-2;i++){
			for(int j=0;j<2;j++){
				if(str[i]==data[j][0] &&str[i+1]==data[j][1] && str[i+2]==data[j][2])ans[j]++;
		}
}
		cout<<ans[0]<<endl<<ans[1]<<endl;
	

}
}

Measured memory_bytes: 1204
#include <bits/stdc++.h>
#define ad(x) (((x - 1) ^ 1) + 1)
#define ID isdigit(c = *next++)

struct Istream {
	int size; char *next, buf[20030731 * 3 / 2];
	Istream (FILE *f = stdin) {fread(buf, 1, sizeof buf, f); next = buf;}
	Istream & operator >> (int &x) {
		int c; x = 0;
		for (; !ID; ) if (!~c) return *this;
		for (x = c & 15; ID; x = x * 10 + (c & 15));
		return *this;
	}
} cin;

const int N = 510000, M = 2040000 * 2;

int n, V, E, Es = 0;

inline void down(int &x, const int y) {x > y ? x = y : 0;}

namespace Green_Hackenbush {
	int to[M], first[N], Tfirst[N], next[M];
	int cnt = 0, id[N], low[N];
	int stc = 0, stack[N], top[N], w[N];
	bool bridge[M];

	inline void addedge(int u, int v, int *fst) {
		to[++Es] = v; next[Es] = fst[u]; fst[u] = Es;
		to[++Es] = u; next[Es] = fst[v]; fst[v] = Es;
	}

	void dfs(int x, int px = 0) {
		int i, y; id[x] = low[x] = ++cnt; stack[stc++] = x;
		for (i = first[x]; i; i = next[i])
			if (!id[y = to[i]]) {
				dfs(y, i); down(low[x], low[y]);
				if (id[x] < low[y]) bridge[ad(i)] = bridge[i] = true;
			} else if (px - 1 ^ i - 1 ^ 1)
				down(low[x], id[y]);
		if (id[x] == low[x])
			for (y = 0; y != x; )
				y = stack[--stc], top[y] = x;
	}

	int dfs2(int x, int px = 0) {
		int i, y, ret = 0;
		for (i = Tfirst[x]; i; i = next[i])
			if ((y = to[i]) != px)
				ret ^= dfs2(y, x) + 1;
		return ret ^ w[x];
	}

	int main() {
		int i, u, v;
		cin >> V, E = V - 1;
		for (i = 0; i < E; ++i) cin >> u >> v, addedge(u, v, first);
		dfs(1);
		for (i = 1; i <= E * 2; i += 2) {
			u = top[to[i]], v = top[to[i + 1]];
			u == v ? w[u] ^= 1 : (addedge(u, v, Tfirst), 0);
		}
		return dfs2(top[1]);
	}
}

int main() {
	puts(Green_Hackenbush::main() ? "Alice" : "Bob");
	return 0;
}

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

ll cal_xor(ll num)
{
  int r = (num+1) % 4;
  switch (r) {
    case 0 : return 0LL;
    case 1 : return num;
    case 2 : return 1LL;
    case 3 : return num ^ 1LL;
  }
}
  
  
int main() {
  ll a, b;
  cin >> a >> b;
  ll ans;

  if (a == 0) ans = cal_xor(b);
  else ans = cal_xor(a-1) ^ cal_xor(b);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int n,i,flag=0;
     cin>>n;
    string s[n];
    for(i=0;i<n;i++)
        cin>>s[i];
        set<string>uni;
        for(i=0;i<n;i++)
        uni.insert(s[i]);
        cout<<uni.size();
}



Measured memory_bytes: 25344
#include<iostream>
#include<iomanip>
#include<string>
#include<set>
#include<vector>
#include<utility>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define LL long long
#define MOD 100000
#define inf 1999999999
typedef string St;

char stb(char c) { return 'A' + (c - 'a'); }

int main() {
	St a, b, c;
	cin >> a >> b >> c;
	cout << ((a.back() == b.front() && b.back() == c.front()) ? (St)"YES" : (St)"NO") << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef		 long long int    ll;
typedef		vector<ll>      vll;
#define     fi              first
#define     se              second
#define		pb              push_back
#define		nn              "\n"
#define		all(p)          p.begin(),p.end()
#define		zz(v)           (ll)v.size()
#define 	S(a)            scanf("%lld",&a)
#define 	SS(a,b)         scanf("%lld %lld",&a,&b)
#define 	SSS(a,b,c)      scanf("%lld %lld %lld",&a,&b,&c)
#define		ss              ' '
#define     pii             pair<ll,ll>
#define		gcd(a,b)        __gcd(a,b)
#define		lcm(a,b)        (a*b)/gcd(a,b)
const double eps = 1e-8;



int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    map<ll,ll>mp;
    ll n;
    cin>>n;
    ll p1=7;
    if(p1%n==0)
    {
        cout<<1<<nn;
        return 0;
    }
    ll p2=10;
    ll ans=-1;
    for(ll i=2; i<1e6; i++)
    {
        p1=(p1*10)+7;
        p1%=n;
        if(p1==0)
        {
            cout<<i<<nn;
            return 0;
        }
        if(mp[p1])
        {
            cout<<-1<<nn;
            return 0;
        }
        mp[p1]=1;



    }















}


/* Final check before submit :

1. array size or integer overflow,like uninitialised 0 index.

2. Think twice,code once.check all possible counter test case.

3. Be careful about corner case! n=1?k=1? something about 0?

4. avoid stupid mistake!complexity(t/m)?precision error?submit same code twice?

5. if got WA than remember that you are missing something common.
   *** Be confident!!! who knows? may be your one step back to AC ***

*/





Measured memory_bytes: 66112
#include <stdio.h>
int main(){
  int cnt=0,n,i,q,A[100000],j;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&A[i]);
  q=A[n-1];
  for(i=0;i<n;i++){
    if(A[i]<=q){
      j=A[i];
      A[i]=A[cnt];
      A[cnt]=j;
      cnt++;
    }
  }
  for(i=0;i<n;i++){
    if(cnt-1==i)printf("[%d]",A[i]);
    else printf("%d",A[i]);
    if(i!=n-1)printf(" ");
    else printf("\n");
  }
  return 0;
}



Measured memory_bytes: 2072
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
#include <vector>
#include <iostream>
#include <ctime>
#include <unistd.h>

using namespace std;

#define TRACE(x) cerr << #x <<  " = " << x << endl
#define _ << " " <<
#define FOR(i, a, b) for (int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)

#define X first
#define Y second

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

const int MAX = 1<<19;

P svi[MAX];
int a[MAX], b[MAX], n;
ll prefa[MAX], prefb[MAX];
ll prefsve[MAX];
int posa[MAX], posb[MAX];

int main()
{
  scanf("%d", &n);
  REP(i, n) scanf("%d%d", &a[i], &b[i]);

  FOR(i, 1, n+1) {
    prefa[i] = prefa[i-1] + a[i-1];
    prefb[i] = prefb[i-1] + b[i-1];
  }

  REP(i, n) {
    svi[i] = P(a[i], i);
    svi[i+n] = P(b[i], i);
  }

  sort(svi, svi+2*n);
  FOR(i, 1, 2*n+1)
    prefsve[i] = prefsve[i-1] + svi[i-1].X;

  ll sol = min(prefb[n], prefa[n]);

  REP(i, n) {
    posa[i] = (int) (lower_bound(svi, svi+2*n, P(a[i], i)) - svi);
    posb[i] = (int) (lower_bound(svi, svi+2*n, P(b[i], i)) - svi);
  }

  REP(i, n) {
    ll tmp = a[i] + b[i];
    int donea = 0, doneb = 0;
    int gdje = n-2;
    for (;;) {
      int kol = gdje - (posa[i] < gdje) - (posb[i] < gdje);
      if (kol >= n-2) break;
      if (posa[i] < gdje && !donea) {
        donea = 1;
        tmp -= a[i];
        gdje++;
        continue;
      }
      if (posb[i] < gdje && !doneb) {
        doneb = 1;
        tmp -= b[i];
        gdje++;
        continue;
      }
    }

    sol = min(sol, tmp + prefsve[gdje]);
  }

  printf("%lld\n", sol);

  return 0;
}



Measured memory_bytes: 14976
#include <iostream>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <utility>
#include <string>
#include <cmath>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int dir[9][2] = { 0, 1, 0, -1, 1, 0, -1, 0, 1, 1, 1, -1, -1, 1, -1, -1, 0, 0 };
const ll  ll_inf = 0x7fffffff;
const double PI=acos(-1.0);
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
const int inf = 0x3f3f3f;
const int mod = (int) 998244353;
const int Max = (int) 1e5 + 22;
stringstream ss;

/**********************************************Head-----Template****************************************/
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}

/********************************Head----Temlate**********************************************/

//tools:
//priority_queue <int, vector<int>, greater<int> > Q;
//ios::sync_with_stdio(false);
//freopen("input.txt", "r", stdin);
//ss<<int; ss>>str;

int n, q;
int Fa[Max];
int value[Max];

void Init() {
	Fa[1] = 0;
	memset(value, 0, sizeof(value));
	value[1] = 1;
}

int main() {
	while (~scanf("%d %d", &n, &q) && n+q) {
		Init();
		for (int i = 2; i <= n; ++i) {
			scanf("%d", &Fa[i]);
		}

		ll ans = 0;
		int x;
		char ch[10];
		for (int i = 0; i < q; ++i) {
			scanf("%s %d", ch, &x);
			if (ch[0] == 'Q') {
				while (x) {
					if (value[x]) {
						ans += (ll)x;
						break;
					}
					x = Fa[x];
				}
			}
			else {
				value[x] = 1;
			}
		}

		printf("%lld\n", ans);
	}
	return 0;
}



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


using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define VB vector<bool>
#define VVB vector<vector<bool>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1 << 30;
const ll INFL = 1LL << 60;
const ll mod = 998244353;


int ans = 0;

VI a[100005];

int dfs(int i) {
	VI v;
	for (int j : a[i]) {
		v.push_back(dfs(j));
	}
	sort(ALL(v));
	reverse(ALL(v));
	int ans = 0;
	REP(j, v.size()) {
		ans = max(ans, j + v[j] + 1);
	}
	return ans;
}

int main() {

	int n;
	cin >> n;
	REP(i, n - 1) {
		int b;
		cin >> b;
		b--;
		a[b].push_back(i + 1);
	}

	cout << dfs(0) << endl;
	

}



Measured memory_bytes: 13696
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
typedef pair<int, int> P;

P a[100000];

int main(){
    int n, m, i, mem = 0, count = 0;
    cin >> n >> m;
    for(i=0; i<m; i++){
        cin >> a[i].second >> a[i].first;
    }
    sort(a, a+m);
    for(i=0; i<m; i++){
        if(a[i].second > mem){
            mem = a[i].first-1;
            count++;
        }
    }
    cout << count << "\n";
    return 0;
}

Measured memory_bytes: 1024
import collections

h,w = map(int,input().split())

tizu = []
ans = 0
for i in range(h):
    s = list(input())
    ans += s.count(".")
    tizu.append(s)
  
#4方向走査
dy = [1,0,-1,0]
dx = [0,1,0,-1]

def f(y,x,count):
    for i in range(4):
        newy = y + dy[i]
        newx = x + dx[i]
        if 0 <= newy and newy < h and 0 <= newx and newx < w:
            if tizu[newy][newx] == ".":
                q.append((newy,newx))
                tizu[newy][newx] = count

#最短でゴールまで行く
q = collections.deque()
q.append((0,0))
tizu[0][0] = 0
while q:
    s =  q.popleft()
    count = tizu[s[0]][s[1]]
    f(s[0],s[1],count+1)

#たどり着けない時
if tizu[h-1][w-1] == ".":
    print(-1)
    exit()

            
print(ans-tizu[h-1][w-1] - 1)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}


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

    
    string s,t;
    cin>>s>>t;
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    reverse(t.begin(),t.end());
    if(s < t){
        cout << "Yes\n";
    }
    else cout << "No\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define chmax(x,y) x = max(x,y);
#define chmin(x,y) x = min(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;



int main() {
    ll n, x, m;
    cin >> n >> x >> m;
    vector<int> id(m, -1);
    vector<int> a;
    int len = 0;
    ll tot = 0;
    while (id[x] == -1) {
        a.push_back(x);
        id[x] = len;
        len++;
        tot += x;
        x = (x*x)%m;
    }

    int c = len-id[x];
    ll s = 0;
    for (int i = id[x]; i < len; i++) s += a[i];

    ll ans = 0;
    if (n <= len) {
        rep(i,n) ans += a[i];
    }
    else {
        ans += tot;
        n -= len;
        ans += s*(n/c);
        n %= c;
        rep(i,n) ans += a[id[x]+i];
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main(void) {
  int N, M; cin >> N >> M;
  int H[N+1]; for (int i = 1; i <= N; ++i) cin >> H[i];
  vector<int> Neighbor[N+1];

  for (int i = 0; i < M; ++i) {
    int a, b; cin >> a >> b;
    Neighbor[a].push_back(b);
    Neighbor[b].push_back(a);
  }

  int ans = N;
  for (int i = 1; i <= N; ++i) {

    if (Neighbor[i].empty()) {
      continue;
    }

    for (auto it = Neighbor[i].begin(); it != Neighbor[i].end(); ++it) {
      if (H[i] <= H[*it]) {
        ans--;
        break;
      }
    }
  }

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

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

//#define NIL 2000000001
#define N 500001


int A[N];
int n;
void maxHeapify(int A[]  ,int i);
void buildMaxHeap(int A[]);

int main(void){
  int i,j;
  
  scanf("%d",&n);
  /*for(i=1;i<=n;i++){
    A[i]=NIL;
    }*/
  for(i=1;i<=n;i++){
    scanf("%d",&A[i]);
    // buildMaxHeap( A);
  }
  
  //for(i=1 ; i<=n ; i++){
    
    buildMaxHeap(A);
    //} 
    for(i=1 ; i<=n ; i++){
      printf(" %d",A[i]);      
    }
    
  printf("\n");
  
  return 0;
}







void maxHeapify(int A[],int i){
  int l,r,largest,temp;

  l = 2*i;
  r = 2*i + 1;
  if(l <= n && A[l] > A[i]){
    largest = l;
  }
  else largest = i;
  
  if(r <= n && A[r] > A[largest]){
    largest = r;
  }
  
  if(largest != i){
    temp = A[i];
    A[i] = A[largest];
    A[largest] = temp;
    maxHeapify(A,largest);
  }
  
  
}






void buildMaxHeap(int A[]){
  int i;

  for(i=n/2;i>=1;i--){
    maxHeapify(A,i);   
  }  
}

Measured memory_bytes: 2552
use std::io::{stdin, stdout, BufReader, BufRead, StdinLock, Write, BufWriter};

fn main() {
    let (std_in, std_out) = (stdin(), stdout());
    let mut br = BufReader::new(std_in.lock());
    let mut bw = BufWriter::new(std_out.lock());
    
    let r: usize = rn(&mut br);
    writeln!(&mut bw, "{}", 3*r*r);
}


//////////////////////////////////////////////////////////////////////////////////
#[allow(dead_code)]
fn rs(br: &mut BufReader<StdinLock>) -> Vec<char> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().chars().collect()
}

#[allow(dead_code)]
fn rn<T: std::str::FromStr>(br: &mut BufReader<StdinLock>) -> T {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn rvs(br: &mut BufReader<StdinLock>) -> Vec<Vec<char>> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|e| e.chars().collect()).collect()
}

#[allow(dead_code)]
fn rvn<T: std::str::FromStr>(br: &mut BufReader<StdinLock>) -> Vec<T> {
    let mut buf = String::new();
    br.read_line(&mut buf).ok();
    buf.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect()
}

Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	string s,t,u;
	cin>>s>>t>>a>>b>>u;
	if(u==s)
		cout<<a-1<<" "<<b;
	else
		cout<<a<<" "<<b-1;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using static System.Console;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        solve();
    }
    static Scanner cin;
    static int X;

    static void input()
    {
        cin = new Scanner();

        X = cin.nextInt();
    }
    static void solve()
    {
        input();
        for(int i = 1;; i++)
        {
            if(i * (i + 1) / 2 >= X)
            {
                WriteLine(i);
                return;
            }
        }
    }
    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }
        
        public string next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return next();
            i = 0;
            return s[i++];
        }

        public int nextInt()
        {
            return int.Parse(next());
        }

        public int[] ArrayInt(int N, int add = 0)
        {
            int[] Array = new int[N];
            for(int i = 0; i < N; i++)
            {
                Array[i] = nextInt() + add;
            }
            return Array;
        }

        public long nextLong()
        {
            return long.Parse(next());
        }

        public long[] ArrayLong(int N, long add = 0)
        {
            long[] Array = new long[N];
            for(int i = 0; i < N; i++)
            {
                Array[i] = nextLong() + add;
            }
            return Array;
        }

        public double nextDouble()
        {
            return double.Parse(next());
        }

        public double[] ArrayDounble(int N, int add = 0)
        {
            double[] Array = new double[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = nextDouble() + add;
            }
            return Array;
        }
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>

#define ll long long
#define ull unsigned long long

using namespace std;

int main() {
	string S;
	cin >> S;

	int sol = 0;
	for (int ii = 0; ii < 4; ++ii){
		if (S[ii] == '+'){
			sol++;
		} else {
			sol--;
		}
	}

	cout << sol << endl;

	return 0;
}


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

int a[12][12];

int main(){
	int n,m,x;
	cin >> n >> m >> x;
	vector<int> c(n);
	for(int i=0;i<n;i++){
		cin >> c[i];
		for(int j=0;j<m;j++){
			cin >> a[i][j];
		}
	}

	int ans = 1001001001;

	for(int s=0;s<1<<n;s++){ 
		int cost = 0;
		vector<int> d(m);
		for(int i=0;i<n;i++){
			if(s>>i&1) {
				cost += c[i];
				for(int j=0;j<m;j++){
					d[j] += a[i][j];
				}
			}
		}
		bool ok = true;
		for(int j=0;j<m;j++){
			if(d[j] < x){
				ok = false;
			}
		}
		if(ok){
			ans = min(ans,cost);
		}
	}
	if(ans==1001001001){
		cout << -1 << endl;
	}else{
		cout << ans << endl;
	}
	return 0;

}

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

#define ll long long
#define ull unsigned long long 
#define endl '\n'
#define pii pair<int, int>
#define all(a) a.begin(),a.end()
template <typename T>
inline T gcd(T a, T b) { while (b != 0) swap(b, a %= b); return a; }

int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    for(int i=0; i<n; ++i){
        cin>> a[i];
    }
    int ans=0;
    int active=0;
    for(int i=0; i<n; ++i){
        if(active >= a[i]){
            active = a[i];
        }
        else{
            ans+=a[i]-active;
            active = a[i];
        }
    }
    cout << ans;
}

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

int main(){
  string S;
  cin >> S;
  vector<string> T={"AKIHABARA","AKIHABAR","AKIHABRA","KIHABARA","AKIHABR","AKIHBAR","AKIHBRA",
                    "KIHABAR","KIHABRA","KIHBARA","AKIHBR","KIHABR","KIHBAR","KIHBRA","KIHBR"};
  bool a=false;
  for(int i=0;i<15;i++){
    if(S==T.at(i)){
      a=true;
      break;
    }
  }
  if(a){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}
      


Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using ll = long long int;

int main(){
    int N;
    cin >> N;
    vvi vec(N+1, vi(2));
    for(int i=1; i<N+1; i++){
        int a, b; cin >> a >> b;
        vec[i][0] = b;
        vec[i][1] = a;
    }
    sort(vec.begin(), vec.end());
    bool ans = true;
    if(vec[1][1] > vec[1][0]){
        cout << "No";
    }
    else{
        ll sum = 0;
        for(int i=2; i<N+1; i++){
            sum += vec[i-1][1];
            if(sum + vec[i][1] > vec[i][0]){
                ans = false;
            }
        }
        if(ans == true){
        cout << "Yes";
        }
        else{cout << "No";}
    }
    
}

Measured memory_bytes: 11264
import kotlin.math.*

typealias Num=Int

fun binarySearch(ok:Num,ng:Num,eps:Num,f:(Num)->Boolean):Num {
	var _ok = ok
	var _ng = ng
	while(abs(_ok-_ng)>eps) {
		val mid = (_ok+_ng)/2
		if(f(mid))
			_ok = mid
		else
			_ng = mid
	}
	return _ok
}

fun main() {
	for(n in 1..readLine()!!.toInt()) {
		var r = 0L
		for(x in 1..n) {
			val m = n-x*x
			if(m<2*x+3)
				break

			for(y in x..m) {
				val o = m-y*y-x*y
				if(o<x+y+1)
					break

				val z = binarySearch(y,o,1) {z-> z*z+x*z+y*z<=o}
				if(z*z+x*z+y*z==o) {
					when {
						x==y&&y==z->++r
						x==y||y==z||z==x->r += 3
						else->r += 6
					}
				}
			}
		}
		println(r)
	}
}


Measured memory_bytes: 54256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<(int)n;i++)
const ll INF = (1LL<<60);
const int MOD = 998244353;

ll dp[201010] = {0};
int main(){
    int n,k; cin >> n >> k;
    vector<ll> L(k),R(k);
    rep(i,k){
        cin >> L[i] >> R[i];
    }

    dp[0] = 1;
    dp[1] = -1;
    for(int i=0;i<n;i++){
        if(i>0) dp[i] += dp[i-1];
        dp[i] %= MOD;
        rep(j,k){
            int l = L[j], r = R[j];
            if(i+l >= n) continue;
            dp[i+l] += dp[i];
            dp[i+l] %= MOD;

            if(i+r+1 >= n) continue;
            dp[i+r+1] -= dp[i];
            dp[i+r+1] += MOD;
            dp[i+r+1] %= MOD;
        }
    }

    cout << dp[n-1] << endl;
}

Measured memory_bytes: 5196
import java.util.Scanner;


public class Main {

		public static class BIT{
				int[] dat;
				
				public BIT(int n){
						dat = new int[n + 1];
				}
				
				public void add(int k, int a){
						for(int i = k + 1; i < dat.length; i += i & -i){
								dat[i] += a;	
						}
				}
				
				public int sum(int s, int t){
						if(s > 0) return sum(0, t) - sum(0, s);
						
						int ret = 0;
						for(int i = t; i > 0; i -= i & -i) {
								ret += dat[i];
						}
						return ret;
				}
				
				public int get(int k){
						int p = Integer.highestOneBit(dat.length - 1);
						for(int q = p; q > 0; q >>= 1, p |= q){
								if( p >= dat.length || k < dat[p]) p ^= q;
								else k -= dat[p];
						}
						return p;
				}
		}
		
		public static void main(String[] args){
				Scanner sc = new Scanner(System.in);
				
				final int n = sc.nextInt();
				final int q = sc.nextInt();

				BIT bit = new BIT(n);
				for(int tt = 0; tt < q; tt++){
						final int op = sc.nextInt();
						final int x  = sc.nextInt() - 1;
						final int y  = sc.nextInt();
						
						if(op == 0){
								bit.add(x, y);
						}else{
								System.out.println(bit.sum(x, y));
						}
				}
		}
}

Measured memory_bytes: 96876
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define MOD 1000000007
#define pb emplace_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define sz(x) (ll)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(ll i=a;i<=b;++i)
#define ROF(i,a,b) for(ll i=a;i>=b;--i)
typedef long long ll;
using namespace std;

int main(){
    IOS

    int n;
    cin >> n;
    ll sum = 0;
    FOR(i,1,n){
        if(i%3 == 0 || i%5 == 0){
            continue;
        }
        sum += i;
    }
    cout << sum;
    return 0;
}

Measured memory_bytes: 3604
#include<stdio.h>
#include<iostream>
#include<string>
#include<bits/stdc++.h>
using namespace std;
int a[100006];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1; i<=2*n; i++)
    {
        scanf("%d",&a[i]);
    }
    sort(a+1,a+1+n*2);
    int sum=0;
    for(int i=1; i<2*n; i++)
    {
        sum=sum+a[i];
        i++;
    }
    printf("%d\n",sum);
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>

#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define INF (1<<30)
#define ALEN(ARR) (sizeof(ARR) / sizeof((ARR)[0]))
#define MP make_pair
#define mp make_pair
#define pb push_back
#define PB push_back

#if DEBUG
#define _DEBUG(x) cout<<#x<<": "<<x<<endl
#define _DDEBUG(x,y) cout<<#x<<": "<<x<<", "<<#y<<": "<<y<<endl
#else
#define _DEBUG(x) ;
#define _DDEBUG(x,y) ;
#endif

#define ll long long
#define ull unsigned long long
#define MOD 1000000007

/** FOR VECTOR DEBUG */
template <typename T>
ostream& operator<< (ostream& out, const vector<T>& v) {
    if ( !v.empty() ) {
        out << '[';
        copy (v.begin(), v.end(), ostream_iterator<T>(out, ", "));
        out << "\b\b]";
    }
    return out;
}


/* template end */
vector<int> mark;
vector<bool> checked;
vector<vector<pair<int, int>>> vvp;
int current_mark = -1;

void dfs(int index) { 
    if(current_mark == -1) {
        mark[1] = 0;
        current_mark = 0;
    }
    for(int i = 0; i < vvp[index].size(); i++) {
        int n = vvp[index][i].first;
        int c = vvp[index][i].second;
        if(checked[n]) {
            continue;
        }
        mark[n] = c % 2 == 1 ? (mark[index] ^ 1) : mark[index];
        checked[n] = true;
        dfs(n);
    }
}

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

    int n;
    cin >> n;

    mark.resize(n + 1);
    checked.resize(n + 1);
    vvp.resize(n + 1);

    REP(i, n - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        vvp[u].push_back(make_pair(v, w));
        vvp[v].push_back(make_pair(u, w));
    }

    dfs(1);

    for(int i = 1; i <= n; i++) {
        cout << mark[i] << endl;
    }

    return 0;
}


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

const int INF = 1e9;

int calc(vector<int>& st) {
	st.push_back(0);
	int n = st.size();
	if (n <= 2) return 0;
	vector<vector<int>> dp(n, vector<int>(3));
	dp[0][0] = -INF;
	dp[0][1] = -INF;
	dp[0][2] = 0;
	for (int i = 1; i < n; i++) {
		dp[i][0] = max(dp[i - 1][0] + st[i - 1] - 1, dp[i - 1][2] + st[i - 1]);
		if (st[i - 1] >= 2) {
			dp[i][1] = max(dp[i - 1][0] + st[i], max(dp[i - 1][1] + st[i] - 1, dp[i - 1][2] + st[i]));
		}
		else {
			dp[i][1] = max(dp[i - 1][1] + st[i] - 1, dp[i - 1][2] + st[i]);
		}
		dp[i][2] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2]));
	}
	return dp[n - 1][2];
}

int main()
{
	int N;
	string s;
	cin >> N >> s;
	char ch = '0';
	int res = 0;
	vector<int> st = { 0 };
	for (auto c : s) {
		if (c == '0' && ch == '0') {
			while (!st.empty() && st.back() == 0) st.pop_back();
			res += calc(st);
			st.clear();
			st.push_back(0);
			continue;
		}
		if (c == '0') {
			st.push_back(0);
		}
		else {
			st.back()++;
		}
		ch = c;
	}
	while (!st.empty() && st.back() == 0) st.pop_back();
	res += calc(st);
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 900
import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        char[] c = sc.next().toCharArray();
        int n = c.length;


        int a = c[0] - '0';
        int b = 11 - c[0] + '0';
        for(int i=1; i<n; i++) {
            int na = Integer.MAX_VALUE;
            int nb = Integer.MAX_VALUE;
            int num = c[i] - '0';
            if(num == 0) {
                na = Math.min(a, b);
            } else {
                na = Math.min(a, b) + num;
                nb = a + 11 - num;
                if(b != Integer.MAX_VALUE) {
                    nb = Math.min(nb, b + 9 - num);
                }
            }
            a = na;
            b = nb;
        }

        System.out.println(Math.min(a, b));
    }

}




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

int main() {
  int n, r; cin >> n >> r;
  if (10 <= n) cout << r;
  else cout << r + 100 * (10 - n);
  return 0;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
import java.util.function.*;

final class Solver {
	void solve(Supplier<String> sc) {
		int N = Integer.parseInt(sc.get());
		int M = Integer.parseInt(sc.get());
		var group = new UnionFind(N);
		for (int i = 0; i < M; i++) {
			int A = Integer.parseInt(sc.get())-1;
			int B = Integer.parseInt(sc.get())-1;
			group.union(A, B);
		}
		int max = 0;
		for (int i = 0; i < N; i++) {
			max = Math.max(max, group.size(i));
		}
		System.out.println(max);
	}
}

class UnionFind {
	int[] parent;

	UnionFind(int size) {
		parent = new int[size];
		Arrays.fill(parent, -1);
	}

	int find(int i) {
		if (parent[i] < 0) return i;
		return parent[i] = find(parent[i]);
	}

	int size(int i) {
		return -parent[find(i)];
	}

	boolean same(int i, int j) {
		return find(i) == find(j);
	}

	boolean union(int i, int j) {
		i = find(i);
		j = find(j);
		if (i == j) return false;
		if (size(i) < size(j)) {
			int temp = i;
			i = j;
			j = temp;
		}

		parent[i] += parent[j];
		parent[j] = i;
		return true;
	}
}

class Main {
	public static void main(String... args) {
		System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
		var reader = new BufferedReader(new InputStreamReader(System.in));
		new Solver().solve(new Supplier<>() {
			StringTokenizer line;

			public String get() {
				while (line == null || !line.hasMoreTokens()) try {
					line = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new UncheckedIOException(e);
				}
				return line.nextToken();
			}
		});
		System.out.flush();
	}
}

Measured memory_bytes: 55612
n = int(input())
t = [ int(input()) for i in range(n)]
def gcd(a,b):
    if a<b:a,b = b,a 
    if b==0:return a
    else : return gcd(b,a%b)    

def lc(a,b):
    return a //gcd(a,b) * b

def lcm(b):
    ans = b[0]
    for i in b:
        ans = lc(ans,i)
    return ans
print(lcm(t))



Measured memory_bytes: 3060
/*
 * 	The way if it's all predetermined
 * 		And the way i should go all my life
 * 			I swear to go wherever will be
 * 				'Cause there'll be something to see and to find
 */
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,fma,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#ifdef rd
#define trace(...) cout<<"Line:"<<__LINE__<<" "; __f(#__VA_ARGS__, __VA_ARGS__)
template<typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cout<<name<<" : "<<arg1<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
	const char* comma=strchr(names+1,',');
	cout.write(names,comma-names)<<" : "<<arg1<<" | ";
	__f(comma+1,args...);
}
#else
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=2e18;
const int infi=1e9;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}


int c[10005],d[10005];
vi gra[10005];
bool used[10005];
int anse[10005];
void solve() {
	int n;
	cin>>n;
	vector<pii> lol;
	fr(i,1,n-1) {
		int u,v;
		cin>>u>>v;
		gra[u].pb(v);
		gra[v].pb(u);
		d[u]++;
		d[v]++;
	}
	fr(i,1,n) {
		cin>>c[i];
		lol.pb({c[i],i});
	}
	sort(all(lol));
	int ans=0;
	fr(i,0,n-2) {
		ans+=lol[i].fi;
	}
	auto cmp=[](int i, int j) {
		if(d[i]!=d[j])
			return d[i]<d[j];
		return i<j;
	};
	set<int,decltype(cmp)> mind(cmp);
	for(int i=1; i<=n; i++)
		mind.insert(i);
	int cn=0;
	while(sz(mind)) {
		trace(sz(mind));
		int te=*mind.begin();
		anse[te]=lol[cn].fi;
		cn++;
		used[te]=1;
		for(int i:gra[te]) {
			if(!used[i]) {
				mind.erase(i);
				d[i]--;
				mind.insert(i);
			}
		}
		mind.erase(te);
		trace(te,sz(mind));
	}
	cout<<ans<<endl;
	fr(i,1,n) {
		cout<<anse[i]<<" ";
	}
	cout<<endl;

}

signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
	int t=1;
//	cin>>t;
	while(t--)
		solve();
#ifdef rd
	cout<<endl<<endl<<endl<<endl<<"Time elapsed: "<<(double)(clock()-clk)/CLOCKS_PER_SEC<<endl;
#endif
	return 0;
}


Measured memory_bytes: 1536
#include<stdio.h>

int main (){
char s[5];
scanf("%s",s);
int i=0;
int flag[3]={};
do {
  if(s[i]=='a')flag[0]++;
  if(s[i]=='b')flag[1]++;
  if(s[i]=='c')flag[2]++;
  i++;
} while(s[i]!='\0');


if(flag[0]==1 && flag[1]==1 && flag[2]==1)printf("Yes\n");
else printf("No\n");
return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int from;
    int to;
    int weight;
    Edge(int from, int to, int weight) : from(from), to(to), weight(weight) {
    }
    
    int other(int u) {
        return u == from ? to : from;
    }
};

struct TreeDiameter {
    int n;
    vector<vector<int>> g;
    vector<Edge> edges;
    int bestDist;
    int bestNode;
  
    TreeDiameter(int n) : n(n) {
        g.assign(n, vector<int>());
    }
    
    void addEdge(int from, int to, int w) {
        edges.push_back(Edge(from, to, w));
        g[from].push_back(edges.size() - 1);
        g[to].push_back(edges.size() - 1);
    }
    
    int solve() {
        bestDist = 0;
        bestNode = -1;
        dfs(0, -1, 0);
        dfs(bestNode, -1, 0);
        return bestDist;
    }
     
    void dfs(int u, int p, int d) {
        if (d > bestDist) {
            bestDist = d;
            bestNode = u;
        }
        for (int e : g[u]) {
            Edge edge = edges[e];
            int v = edges[e].other(u);
            if (v != p) {
                dfs(v, u, d +  edge.weight);
            }
        }
    }   
};

int main() {
    int n;
    cin >> n;
    
    TreeDiameter d(n);
    for (int i = 0; i < n - 1; i++) {
        int from, to, w;
        cin >> from >> to >> w;
        d.addEdge(from, to, w);
    }
    
    int ans = d.solve();
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 12372