akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0;i < (int)(n);i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n);i++)
#define ALL(vec)  (vec).begin(),(vec).end()
#define lli long long int
#define pi 3.1415926535897932384626433832795
#define MAX_INF 9223372036854775807
#define MIN_INF 9223372036854775807+1
int main()
{
	int N, M;
	cin >> N >> M;
	int m[10][11];
	rep(i, 10) {
		rep(j, 11)
			m[i][j] = 12;
	}

	int ans1;
	rep(i, M) {
		int k;
		cin >> k;
		rep(j, k) {
			cin >> m[i][j];
		}
	}
	rep(i, M)
		cin >> m[i][10];
	int ans = 0;
	int jud = 0;
	int light[10];
	rep(a, 2) {
		light[0] = a;
		rep(b, 2) {
			light[1] = b;
			rep(c, 2) {
				light[2] = c;
				rep(d, 2) {
					light[3] = d;
					rep(e, 2) {
						light[4] = e;
						rep(f, 2) {
							light[5] = f;
							rep(g, 2) {
								light[6] = g;
								rep(h, 2) {
									light[7] = h;
									rep(i, 2) {
										light[8] = i;
										rep(j, 2) {
											light[9] = j;
											ans1 = 0;
											rep(p, M) {
												jud = 0;

												rep(q, 10) {
													if(m[p][q]!=12)
												jud += light[10-m[p][q]];

												}

												if (jud % 2 == m[p][10])
													ans1++;
											}
											if (ans1 == M)
												ans++;

										}
										if (N < 2)
											break;
									}
									if (N < 3)
										break;
								}
								if (N < 4)
									break;
							}
							if (N < 5)
								break;
						}
						if (N < 6)
							break;
					}
					if (N < 7)
						break;
				}
				if (N < 8)
					break;
			}
			if (N < 9)
				break;
		}
		if (N < 10)
			break;
	}
	cout << ans << endl;
}

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

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

    int n;
    cin >> n;

    int a = n / 100, b = n % 100;

    if(1<=a&&a<=12){
        if(1<=b&&b<=12)cout << "AMBIGUOUS" << endl;
        else cout << "MMYY" << endl;
    }else{
        if (1 <= b && b <= 12)
            cout << "YYMM" << endl;
        else
            cout << "NA" << endl;
    }

   
    return 0;
}


Measured memory_bytes: 256
class SegmentTree
  def initialize(size, default:, update: -> (nv, _) { nv }, merge:)
    n = 1
    while n < size
      n *= 2
    end
    @size = n
    @default = default
    @update_proc = update
    @merge_proc = merge
    @data = Array.new(n * 2 - 1, default)
  end

  # 0-origin
  def update(k, a)
    k += @size - 1
    @data[k] = @update_proc.call(a, @data[k])
    while k > 0
      k = (k - 1) / 2
      @data[k] = @merge_proc.call(@data[k * 2 + 1], @data[k * 2 + 2])
    end
    nil
  end

  # [a, b)
  # 0-origin
  def query(a, b)
    execute_query(a, b, 0, 0, @size)
  end

  private

  def execute_query(a, b, k, l, r)
    return @default if r <= a || b <= l
    return @data[k] if a <= l && r <= b
    vl = execute_query(a, b, k * 2 + 1, l, (l + r) / 2)
    vr = execute_query(a, b, k * 2 + 2, (l + r) / 2, r)
    @merge_proc.call(vl, vr)
  end
end

N, T = gets.split.map(&:to_i)
as = gets.split.map(&:to_i)

st = SegmentTree.new(
  N,
  default: -1,
  merge: -> (a, b) { a >= b ? a : b }
)
as.each.with_index do |a, i|
  st.update(i, a)
end
table = Hash.new { 0 }
(0...N).each do |i|
  a = as[i]
  b = st.query(i, N)
  c = b - a
  table[c] += 1 if c > 0
end
n = table.keys.max
ans = table[n]
puts ans


Measured memory_bytes: 17804
#include <bits/stdc++.h>
 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
 
typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
 
const ll e5 = 1 << 20;
const ll mod = 998244353;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;
 
int main() {
  string s;
  cin >> s;

  char bef = '\n';
  bool b = false;
  rep(i, 4) {
    if (s[i] == bef) {
      b = true;
    }
    bef = s[i];
  }

  if (b) {
    cout << "Bad" << endl;
  } else {
    cout << "Good" << endl;
  }

  return 0;
}

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll K;
    cin >> K;
    vector<ll> v;
    v.push_back(0);
    REP(i, 9) {
        v.push_back(1 + i);
    }
    ll m = 10;
    while (v.size() <= K) {
        vector<ll> t;
        for (ll n = 1; n <= 9; ++n) {
            ll d = m * n;
            REP(i, v.size()) {
                ll a = v[i] / (m / 10);
                if (a > 0) {
                    if (abs(a - n) <= 1) {
                        t.push_back(d + v[i]);
                    }
                }
                else if (n == 1) {
                    ll b = v[i];
                    ll c = b % 10;
                    while (b > 0) {
                        c = b % 10;
                        b /= 10;
                    }
                    if (c == 1 || c == 0)
                        t.push_back(d + v[i]);
                }
            }
        }
        REP(i, t.size()) {
            v.push_back(t[i]);
        }
        m *= 10LL;
    }

    sort(v.begin(), v.end());
    cout << v[K] << endl;
    
    return 0;
}

Measured memory_bytes: 3516
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multi_set;

#define mod         1000000007
#define pi          3.1415926535898
#define eps         1e-9


#define fast       ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define vt vector
#define ar array
#define fs          first
#define sc          second
#define pb         push_back
#define sp          printf(" ")
#define nl          '\n'
#define all(a) a.begin(),a.end()
#define unique(c) (c).resize(unique(all(c)) - (c).begin())
#define sz(x) (int)(x).size()
#define revsort(x) sort(all(x));reverse(all(x))

#define set0(a)     memset(a,0,sizeof(a))
#define setneg(a)   memset(a,-1,sizeof(a))
#define setinf(a)   memset(a,126,sizeof(a))

#define REP(i,start,end) for (int i = start; i <=end; i++)
#define RREP(i,end,start) for (int i=end; i>=start ;i--)
#define EACH(x, a) for (auto& x: a)

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<double, double> pdd;
typedef vector<int> vi;
typedef vector<LL> vll;
typedef vector<double> vd;
typedef vector<vector<LL> > matrix;
typedef vector<vector<int> > graph;
LL INF=1e9;


 
template<class A> void read(vt<A>& v);
template<class A, size_t S> void read(ar<A, S>& a);
template<class T> void read(T& x) {
	cin >> x;
}
void read(double& d) {
	string t;
	read(t);
	d=stod(t);
}
void read(long double& d) {
	string t;
	read(t);
	d=stold(t);
}
template<class H, class... T> void read(H& h, T&... t) {
	read(h);
	read(t...);
}
template<class A> void read(vt<A>& x) {
	EACH(a, x)
		read(a);
}
template<class A, size_t S> void read(array<A, S>& x) {
	EACH(a, x)
		read(a);
}

LL powm(LL x, LL y,LL m)
{
    if(y==0)
        return 1;
    if(y==1)
        return x%m;
    if(y&1)
        return (x*(powm((x*x)%m,y/2,m)))%m;
    return powm((x*x)%m,y/2,m)%m;
}

LL inv(LL x, LL m)
{
    return powm(x,m-2,m);
}

int add(int var1, int var2){
    return (((((LL)(var1)) % mod + (LL)(var2)) % mod) + mod) % mod;
}


int mul(int var1, int var2){
    return (((LL)(var1)) % mod * (LL)(var2)) % mod;
}

void solve()
{
    string s;
    read(s);
    LL a=0;
    REP(i,0,sz(s)-1)
        a+=(s[i]-'0');
    string ans="Yes";
    if(a%9)
        ans="No";
    cout<<ans<<nl;

}
int main()
{
    fast;
        solve();
}


Measured memory_bytes: 3776
N,x = map(int,input().split())
a = list(map(int, input().split()))

a.sort()

s = 0
counter = 0

for i in range(N):
    if i != N-1:
        s += a[i]
        if s <= x:
            counter += 1
        else:
            break
    else:
        if x - s == a[i]:
            counter += 1
        else:
            break

print(counter)


Measured memory_bytes: 3060
let is_palindrome n =
  let d = n / 10000 in
  if d = n mod 10 then
    let m = (n - d * 10000) / 10 in m / 100 = m mod 10
  else false

let solve s f =
  let rec aux x sum =
    if x > f then sum
    else if is_palindrome x then aux (x + 1) (sum + 1)
    else aux (x + 1) sum
  in
  aux s 0

let () = Scanf.scanf "%d %d" solve |> Printf.printf "%d\n"

Measured memory_bytes: 384
#include<stdio.h>
int main()
{
  int A,B;
  scanf("%d %d",&A,&B);
  if(A==1 && B==2 || A==2 && B==1){
    printf("3\n");
  }
  else if(A==1 && B==3 || A==3 && B==1){
    printf("2\n");
  }
  else if(A==2 && B==3 || A==3 && B==2){
     printf("1\n");
  }
  else{

  }
  return 0;
}


Measured memory_bytes: 128
D,G = map(int, input().split())
pc = [input().split() for _ in range(D)]

ans = []

for i in range(2**D):
  x = bin(i).replace("0b","")
  x = x.zfill(D)
  
  point,cnt = 0,0
  
  for l,st in enumerate(x):
    if st == "1":
      cnt += int(pc[l][0])
      point += int(pc[l][1]) + (((l + 1)*100) * int(pc[l][0]))
      
  if point >= G:
    ans.append(cnt)
  else:
    for n,st2 in enumerate(x[::-1]):
      if st2 == "0":
        for z in range(int(pc[D-(n+1)][0])):
          point += ((D-n)*100)
          cnt += 1
          if point >= G:
            ans.append(cnt)

print(min(ans))

Measured memory_bytes: 4504
from fractions import gcd

def segfunc(x, y):
    return gcd(x, y)
ide_ele = 0
"""
最小値 min(x, y),float('inf) RMQ
最大値 max(x, y),float('inf)
区間和 x + y,0 BIT
区間積 x * y,1
最大公約数 math.gcd(x, y),0
"""

class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):
 
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        # 葉の数 2**n個
        self.tree = [ide_ele] * 2 * self.num
        # 木の要素数は1originだとこう
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築 葉に数列の値を
        # 葉のindexはnum ~ num + n
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])
        # 節は子の値を参照する

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        # 葉のスタートのindexはnumのため
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1
            # 親へ
            # 1とのXORは兄弟になる

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N = int(input())
A = list(map(int, input().split()))
seg = SegTree(A, segfunc, ide_ele)
ans = 0
for i in range(N):
    left = seg.query(0, i)
    right = seg.query(i + 1, N)
    ans = max(ans, gcd(left, right))

print(ans)


Measured memory_bytes: 96104
/* 160 */

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

int main()
{
    int n,t,ans;
    cin>>n;
    t=n/500;
    ans=t*1000;
    n -= t*500;
    t=n/5;
    ans += t*5;
    n -= t*5;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n, T;
    cin >> n >> T;
    map<int, int> mp;
    int c, t;
    for(int i = 0; i < n; i++){
        cin >> c >> t;
        mp[c] = t;
    }
    int count = 0;
    for(int i = 0; i < 1100; i++){
        count += 1;
        if(mp[i] != 0 && mp[i] <= T){
            cout << i;
            break;
        }
    }
    if(count == 1100) cout << "TLE";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
long long k,cl,cr,cm,l,r,m,tot,a[2000100],INF=1e9+1;
long long Get(){
	for(int i=0;i<n;i++){
		if(a[i]<0){
			l=-1,r=n;
			while(l+1<r){
				m=(l+r)/2LL;
				if(a[i]*a[m]<cm) r=m;
				else l=m;
			}
			tot+=(long long)(n)-r;
		}
		else{
			l=-1,r=n;
			while(l+1<r){
				m=(l+r)/2LL;
				if(a[i]*a[m]<cm) l=m;
				else r=m;
			}
			tot+=r;
		}
		if((a[i]*a[i])<cm) tot-=1LL;
	}
	tot/=2LL;
}
int main(){
	#ifdef FILIN
		#ifndef DavidDesktop
			freopen(FILIN,"r",stdin);
			freopen(FILOUT,"w",stdout);
		#endif
	#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>a[i];
	sort(a,a+n);
	INF*=INF,cl=-INF,cr=INF;
	while(cl+1<cr){
		cm=(cl+cr)/2LL,tot=0LL;
		if(Get()<k) cl=cm;
		else cr=cm;
		if(tot<k) cl=cm;
		else cr=cm;
	}
	cout<<cl<<endl;
	return 0;
}


Measured memory_bytes: 1920
def main():
    n = int(input())
    h_list = list(map(int, input().split()))

    r = 0
    res = 0
    for i in range(n - 1):
        if h_list[i] >= h_list[i + 1]:
            r += 1
            if r > res:
                res = r
        else:
            r = 0
    print(res)


if __name__ == "__main__":
    main()


Measured memory_bytes: 14252
#include <iostream>
#include <cmath>
#include <cstring>
#include <stdio.h>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <list>
#include <bitset>
#include <sstream>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double e = exp(1);
const double eps = 1e-9;
const int MAX_N = 100000 + 100;

char s[105];

int main()
{
#ifdef ANONYM
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    ios::sync_with_stdio(false);
    cin >> s;
    int len = strlen(s);
    cout << s[0] << len-2 << s[len-1] << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k; cin >> n >> k;
    vector<int> d(k);
    vector<int> t(n, 0);
    for(int i=0; i<k; ++i){
        cin >> d[i]; d[i]--; 
        for(int j=0; j<=d[i]; ++j){
            int a;
            cin >> a; a--; t[a]++;  
        }
    }
    int res = 0; 
    for(int i=0; i<n; ++i){
        if(t[i]==0){res++;}
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3612
import math
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

m_count = 0
for i in range(N):

    m_count += min(A[i], B[i])
    B[i] -= min(A[i], B[i])
    m_count += min(A[i + 1], B[i])
    A[i + 1] -= min(A[i + 1], B[i])

print(m_count)

Measured memory_bytes: 19244
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <queue>
using namespace std;

typedef pair<long long,long long> P;

int v,e,r;

struct edge{
    int to;
    long long cost;
    edge(int _to,long long _cost):to(_to),cost(_cost){}
};

vector<edge> G[1000010];
long long d[1000010];

void dijkstra(int start){
    priority_queue<P,vector<P>,greater<P>> que;
    
    for(int i=0;i<v;i++){
        d[i]=1e12;
    }
    d[start]=0;
    que.push(P(d[r],r));
    
    while(!que.empty()){
        P p=que.top();
        que.pop();
        int v=p.second;
        
        if(d[v]<p.first)continue;
        
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

int main(void){
    cin>>v>>e>>r;
    for(int i=0;i<e;i++){
        int s,t,d;
        cin>>s>>t>>d;
        G[s].push_back(edge(t,d));
    }
    
    dijkstra(r);
    
    for(int i=0;i<v;i++){
        if(d[i]!=1e12)cout<<d[i]<<endl;
        else cout<<"INF"<<endl;
    }
    return 0;
}

Measured memory_bytes: 40468
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
//#define mmod 1000000007
#define pi acos(-1)
ll n,w;
ll weight[105];
ll value[105];
ll dp[102][100005];
ll fun(int pos, ll x)
{
    if (pos==n) return 0;
    if (dp[pos][x]!=-1) return dp[pos][x];
    ll ret1=0,ret2=0;
    if (x-weight[pos]>=0)
        ret1=value[pos]+fun(pos+1,x-weight[pos]);
    ret2=fun(pos+1,x);
    return dp[pos][x]=max(ret1,ret2);
}
int main ()
{
    faster;

    cin>>n>>w;
    memset(dp,-1,sizeof(dp));
    for (int i=0;i<n;i++)
        cin>>weight[i]>>value[i];
    ll ans=fun(0,w);
    cout<<ans<<endl;



    return 0;
}



Measured memory_bytes: 80000
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>

#define PI 3.14159265359
using namespace std;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define bit(n,k) (((ll)n>>(ll)k)&1) /*nのk bit目*/
#define pb push_back
#define eb emplace_back
#define SZ(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const long long INF= 1e+18+1;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll> >vvl;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> T;
const ll MOD=1000000007LL;
//ll MOD=1000000007LL;
//const ll MOD=998244353LL;
//const ll MOD=1777777777LL;
//const ll MAX_V=114514LL;
//const ll MAX = 500010LL;
const ll mod=MOD;
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
vl dx={0,0,1,-1};
vl dy={1,-1,0,0};

//素因数分解O(√n)
map<ll,ll>prime_factor(ll n){
  map<ll,ll>res;
  for(ll i=2;i*i<=n;i++){
    while(n%i==0){
      res[i]++;
      n/=i;
    }
  }
  if(n!=1)res[n]=1;
  return res;
}

const ll MAX = 510000;
long long fac[MAX], finv[MAX], inv[MAX];
//finvが階乗の逆元

// テーブルを作る前処理
void COMinit() {
    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;
    }
}

// 二項係数計算
long long COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll modpow(ll a, ll n, ll mod) {
  
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
ll N=2000010;
vl arr(N);
void Eratosthenes(){
	for(ll i = 0; i < N; i++){
		arr[i] = 1;
	}
        arr[1]=0;
	for(ll i = 2; i < sqrt(N); i++){
		if(arr[i]){
			for(ll j = 0; i * (j + 2) < N; j++){
				arr[i *(j + 2)] = 0;
			}
		}
	}
}
//素数判定O(√n)
bool is_prime(ll n){
  for(ll i=2;i*i<=n;i++){
    if(n%i==0)return false;
  }
  return n!=1;
}

int main(){
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cout << fixed << setprecision(10);
  /*--------------------------------*/
  
  ll n,k,c;cin>>n>>k>>c;
  string s;cin>>s;
  vl vec1(n),vec2(n);
  ll ind=0;
  for(ll i=1;i<=k;i++){
    while(s[ind]!='o'){
        ind++;
    }
    if(ind>=n){
        return 0;
    }
    vec1[ind]=i;
    ind+=c+1;
  }
  ind=n-1;
  for(ll i=k;i>=1;i--){
    while(s[ind]!='o'){
        ind--;
    }
    if(ind<0){
        cout<<0<<endl;
        return 0;
    }
    vec2[ind]=i;
    ind-=c+1;
  }
  //ll cnt=0;
  vl ans;
  rep(i,n){
    if(vec1[i]!=0&&vec1[i]==vec2[i])ans.pb(i+1);
    //cout<<vec1[i]<<" ";
  }
//   cout<<endl;
//   rep(i,n)cout<<vec2[i]<<" ";
//   cout<<endl;
  rep(i,ans.size()){
      cout<<ans[i]<<" ";
      cout<<endl;
  }
  //cout<<endl;
}
  

Measured memory_bytes: 24244
#include <stdio.h>

int main( void ) {
	int i, e, ee, x, y, z, min;

	while ( scanf( "%d", &e ), e ) {
		min = e;
		for ( z = 0; z * z * z <= e; z++ ) {
			ee = e - z * z * z;

			for ( y = 0; y * y + 2 * y + 1 <= ee; y++ ) ;
			x = ee - y * y;

			if ( x + y + z < min )
				min = x + y + z;
		}

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

	return 0;
}

Measured memory_bytes: 600
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 逆元事前処理ver
# nが小さい場合に
lim = 2 * (10 ** 6) + 7 
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, lim + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    # 累計
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0

    if r == 0:
        return 1

    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % mod

"""
g(r,c) を 0 ≤ i ≤ r かつ 0 ≤ j ≤ c を満たす全ての整数の組 (i,j) に対する f(i,j) の総和とする。
ここでf(r + 1, c) = f(r, c) + f(r, c - 1)...f(r, 0)
f(r, c)からr方向へ1つ（一通り）
f(r, c - 1)からr方向へ1つ, c方向に1つ（一通り）
...

つまりf(r2 + 1, c2) = f(r2, c) + f(r2, c - 1) + ... f(r2, 0)
これをf(0, c2)からf(r2 + 1, c2)まで求めればg(r2, c2)が求まる
"""
r1, c1, r2, c2 = getNM()

ans = 0
for i in range(r1, r2 + 1):
    ans = (ans + cmb(c2 + i + 1, i + 1) - cmb(c1 + i, i + 1)) % mod
print(ans)

Measured memory_bytes: 232000
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.B
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var N = ReadLong();
            var A = ReadLongs();

            var count = long.MaxValue;
            var counted = new HashSet<long>();
            foreach (var a in A)
            {
                if (counted.Contains(a)) continue;
                counted.Add(a);
                var c = GetPrimeFactors(a).Count(x => x == 2);
                count = Math.Min(count, c);
            }

            return count;
        }

        public static IEnumerable<long> GetPrimeFactors(long n)
        {
            for (long a = 2; a * a <= n; ++a)
            {
                if (n % a != 0) continue;

                // 割れる限り割り続ける
                while (n % a == 0)
                {
                    yield return a;
                    n /= a;
                }

                // TODO：重複を許さない場合はここで返す
                //yield return a;

            }

            // 最後に残った数について
            if (n != 1) yield return n;
        }
        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


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

using namespace std;

using ll = long long;

template<typename T> using V = std::vector<T>;
using Vi = V<int>;
using VVi = V<V<int>>;
using Vll = V<ll>;
using VVll = V<V<ll>>;
using Vs = V<string>;

template<typename T1, typename T2> using P = std::pair<T1, T2>;
using Pii = P<int, int>;
using Pdd = P<double, double>;

template<typename T1, typename T2> using M = std::map<T1, T2>;
using Mii = M<int, int>;
using Msi = M<string, int>;

const ll MOD = 1e9+7;

#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define REP2(i,s,e) for(int i=(int)(s);i<(int)(e);++i)
#define RREP(i,s,e) for(int i=(int)(s);i>=(int)(e);--i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin(),ie=(c).end();i!=ie;++i)
#define ALL(c) (c).begin(), (c).end()

long long gcd(long long a, long long b) {
    return b ? gcd(b, a % b) : a;
}

std::vector<int> primes(int n) {
    std::vector<int> primes;
    std::vector<bool> isPrime(n+1, true);
    for (int i = 2; i <= n; i++) {
        if (!isPrime[i]) continue;
        primes.push_back(i);
        long long buf = i * 2;
        while (buf <= n) {
            isPrime[buf] = false;
            buf += i;
        }
    }

    return primes;
}

std::map<int, int> prime_fact(long long n) {
    std::map<int, int> cnt;

    long long m = n;
    for (int i: primes(int(sqrt(n))+1)) {
        if (m % i == 0) {
            cnt[i] = 1;
            m /= i;
        }
        while (m % i == 0) {
            cnt[i]++;
            m /= i;
        }
    }
    if (m != 1) {
        cnt[m] = 1;
    }

    return cnt;
}

int main() {
    ll a, b;
    cin >> a >> b;

    Mii m = prime_fact(gcd(a, b));
    std::cout << m.size()+1 << '\n';

    return 0;
}


Measured memory_bytes: 1020
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;
typedef long long ll;
int v[3][100100];
int dp[3][100100];
int main(){
    int n;
    cin >> n;
    rep(i,n){
        rep(j,3){
            cin >> v[j][i];
        }
    }
    rep(i,n){
        rep(j,3){
            rep(k,3){
                if(k==j){
                    continue;
                }
                dp[k][i + 1] = max(dp[k][i + 1],dp[j][i]+v[k][i]);
            }
        }
    }
    cout << max(dp[0][n],max(dp[1][n],dp[2][n])) <<endl; 
return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 9999999999;
const int INFI=2147483647;
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
  T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }


struct UnionFind{
  vector<int> par;  // 親ノードを格納
  vector<int> rank; // 木の深さを格納

  UnionFind(int N) : par(N), rank(N, 0) { // N要素で初期化する
    rep(i, N) par[i] = i;
  }

  int root(int x){ // 木の根を求める。自分じゃなかったら親の根を調べていき調べたノードの親はすべて根に
    return par[x] == x ? x : par[x] = root(par[x]);
  }

  void unite(int x, int y){ // xとyの木を併合
    x = root(x), y = root(y);
    if (x==y) return; // 元々同じならそのまま
    if (rank[x] < rank[y]){
      par[x] = y;
    }else{
      par[y] = x;
      if (rank[x]==rank[y]) rank[x]++; // 元のrankが同じなら親になる方のrankは1増える
    } 
  }

  bool same(int x, int y){ // x,yの木が同じかどうか
    return root(x) == root(y);
  }
};

int main() {
  int n,m; cin >>n >>m;
  vector<int> p(n);
  rep(i, n) cin >>p.at(i);
  rep(i, n) p.at(i)--;
  UnionFind uf(n);
  rep(i, m){
    int x,y; cin >>x >>y;
    x--; y--;
    uf.unite(x, y);
  }
  int res = 0;
  rep(i, n) if (uf.root(i) == uf.root(p.at(i))) res++;
  cout <<res <<endl;
}


Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const int N = 4e2+9;
const ll INF = 1LL<<60;

int n;
ll dp[N][N];
ll a[N];
ll sum[N];

ll rec(int l, int r) {
    if(dp[l][r])  return dp[l][r];
    if(l == r)  return dp[l][r] = 0;

    ll res = INF;
    for(int i = l; i < r; i++)
        res = min(res, rec(l, i) + rec(i+1, r) + sum[r] - sum[l-1]);
    return dp[l][r] = res;
}

int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[i] = sum[i-1] + a[i];
    }

    cout << rec(1, n) << endl;
}

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

int main(){

  string str;

  getline(cin,str);

  for(int i=0;i<(int)str.size();i++){
    
    if(islower(str[i])){
      str[i] = toupper(str[i]);
    }else if(isupper(str[i])){
      str[i] = tolower(str[i]);
    }
  }
  cout << str << endl;

  return 0;
}
    
  


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


using namespace std;
using llong = long long int;


#define rep(i, n) for (int i = 0; i < n; ++i)
#define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
#define stl_repr(itr, x) for (auto itr = x.rbegin(); itr != x.rend(); ++itr)
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()


const static int MOD = 1000000007;
const static int IINF = INT_MAX;
const static llong LINF = LLONG_MAX;
const static int dx[4] = {1, 0, -1, 0};
const static int dy[4] = {0, 1, 0, -1};


template<typename T> struct UnionFind {
    vector<int> par;
    vector<T> sz;

    UnionFind(int n) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; ++i) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int find_root(int x) {
        return par[x] == x ? x : par[x] = find_root(par[x]);
    }

    bool same(int x, int y) {
        return find_root(x) == find_root(y);
    }

    void unite(int x, int y) {
        x = find_root(x);
        y = find_root(y);
        if (x == y) return;
        
        if (sz[x] < sz[y]) swap(x, y);
        sz[x] += sz[y];
        par[y] = x;
    }

    T size_of_tree(int x) {
        return sz[find_root(x)];
    }
};


llong my_gcd(llong a, llong b) {
    return (a ? my_gcd(b % a, a) : b);
}
llong my_lcm(llong a, llong b) {
    return a * b / my_gcd(a, b);    
}

llong facmod(llong n) {
    if (n == 0) return 1;

    llong res = n;
    for (int i = n - 1; i > 0; --i) {
        res = (res * i) % MOD;
    }

    return res;
}
llong powmod(llong a, llong n) {
    llong res = 1;
    while (n > 0) {
        if (n & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        n >>= 1;
    }

    return res;
}
llong modinv(llong n) {
    return powmod(n, MOD - 2);
}
llong combmod(llong n, llong k) {
    llong res = 1;
    for (int i = 0; i < k; ++i) {
        res = (res * (n - i)) % MOD;
    }
    res = (res * modinv(facmod(k))) % MOD;

    return res;
}


int main(int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m, k;
    cin >> n >> m >> k;

    UnionFind<int> UF(n);
    vector<set<int> > FS(n);
    int a, b;
    rep(i, m) {
        cin >> a >> b;
        --a, --b;
        UF.unite(a, b);
        FS[a].insert(b);
        FS[b].insert(a);
    }
    rep(i, k) {
        cin >> a >> b;
        --a, --b;
        FS[a].insert(b);
        FS[b].insert(a);
    }
    
    int res;
    rep(i, n) {
        res = UF.size_of_tree(i);
        stl_rep(itr, FS[i]) {
            if (UF.same(i, *itr)) --res;
        }
        cout << res - 1;
        if (i == n - 1) cout << endl;
        else cout << " ";
    }

    return 0;
}

Measured memory_bytes: 25088
import bisect
n = int(input())
l = list(map(int,input().split()))
l.sort()
ans =0
for i in range(1,n):
    for j in range(i):
        p = l[i]+ l[j]
        q = bisect.bisect_left(l,p)
        ans += q-i-1

print(ans)

Measured memory_bytes: 3188
import sys
input = sys.stdin.readline


def main():
    N, A, B = map(int, input().split())
    if (B - A) % 2 == 0:
        print((B-A)//2)
    else:
        a = (A-1) + (B-A-1)//2 + 1
        b = (N-B) + (B-A-1)//2 + 1
        print(min(a, b))




if __name__ == '__main__':
    main()


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

int main(){
  ll N,M;cin >> N >> M;
  ll T = 100*N+1800*M;
  ll x=1;
  for(ll i=0;i<M;i++){
    x *= 2;
  }
  cout << T*x << endl;
}

Measured memory_bytes: 256
#define max(a,b)(a>b?a:b)
#define min(a,b)(a<b?a:b)
char s[1001];D[2][1001];main(n,i,j,k,l,x,M){
	for(;scanf("%d",&n),n;printf("%d\n",M))
		for(memset(D,0,sizeof(D)),M=i=0;i<n;i++){
			scanf("%s",s);
			for(j=1;j<=n;j++)if(s[j-1]=='*')D[1][j]=-1;
			for(j=1;j<=n;j++)D[1][j]=D[1][j]!=-1?min(D[0][j-1],min(D[0][j],D[1][j-1]))+1:0,M=max(M,D[1][j]);
			memcpy(D[0],D[1],sizeof(D[1]));
			memset(D[1],0,sizeof(D[1]));
		}
exit(0);}

Measured memory_bytes: 612
#include<iostream>
using namespace std;
int main()
{
float x,y,z;
 cin>>x>>y>>z;
 if(x<=z&&y<=z)
    cout<<(x/2)*y;
 else if(x<=y&&z<=y)
    cout<<(x/2)*z;
    else if(y<=x&&z<=x)
    cout<<(y/2)*z;
 return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i <= (n); i++)
#define repm(i,m,n) for (int i = m; i < (n); i++)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;

int main() {
  string S;
  cin >> S;
  
  sort(S.begin(), S.end());
    
  printf((S[0] == S[1] && S[1] != S[2] && S[2] == S[3]) ? "Yes\n" : "No\n");
}



Measured memory_bytes: 256
n = int(input())
a = list(map(int, [input() for i in range(n)]))

list=a[:]
list.sort(reverse=True)
max1 = list[0]
max2 = list[1]

for i in range(n):
    if a[i]==max1:
        print(max2)
    else:
        print(max1)

Measured memory_bytes: 23728
def main():
    N, K, *A = map(int, open(0).read().split())
    A = [0] + A
    cur_pos = 1
    last_visit = [-1] * (N + 1)
    last_visit[cur_pos] = 0
    for i in range(1, K + 1):
        nxt_pos = A[cur_pos]
        if cur_pos == nxt_pos:
            print(nxt_pos)
            return 
        elif (j := last_visit[nxt_pos]) != -1:
            print(last_visit.index((K - j) % (i - j) + j))
            return 
        else:
            last_visit[nxt_pos] = last_visit[cur_pos] + 1
            cur_pos = nxt_pos
    print(cur_pos)


if __name__ == "__main__":
    main()


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

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(), (x).end()

using namespace std;

template <typename T> T &chmin(T &a, const T &b) {return a = min(a, b);}
template <typename T> T &chmax(T &a, const T &b) {return a = max(a, b);}

using ll = long long;
using ld = long double;

const int INF = 1e9;
const ld eps = 1e-9, pi = acos(-1.0);

int solve(int x){
  if(x%2==0) return 0;
  int res = 0;
  REP(i, x) if(x%(i+1)==0) res++;
  return res;
}

int main(){
  int n;
  cin >> n;
  int res = 0;
  REP(i, n+1) if(solve(i)==8) res++;
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
#define rep(i,m,n) for(int i=m;i<n;i++)
ll mod=1e9+7;

int main(){
  int n;
  cin>>n;
  int f[n][10];
  rep(i,0,n){
    rep(j,0,10){
      cin>>f[i][j];
    }
  }
  int p[n][11];
  rep(i,0,n){
    rep(j,0,11){
      cin>>p[i][j];
    }
  }
  int ans=-2e9;
  rep(i,1,1<<10){
    int cur=0;
    rep(j,0,n){
      int cnt=0;
      rep(k,0,10){
        if(f[j][k]==1 && (1 & i>>k)){
          cnt++;
        }
      }
      cur+=p[j][cnt];
    }
    ans=max(ans,cur);
  }
  cout<<ans<<endl;
}

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

int main(){
  int n;cin>>n;
  map<int,int>a;
  for(int i=0,tmp;i<n;i++){
    cin>>tmp;a[tmp]++;
    if(a[tmp]>1){cout<<"NO"<<endl;return 0;}
  }
  cout<<"YES"<<endl;
  return 0;
}


Measured memory_bytes: 9600
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
using ll = long long;
int main() {
    int n,k;
    cin >> n >> k;
    vector<int> p(n);
    for(int i=0;i<n;i++){
        cin >> p[i];
    }
    sort(p.begin(),p.end());
    int ans = 0;
    for(int i=0;i<k;i++){
        ans += p[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3484
while True:
    n, k = map(int, raw_input().split())
    if k == 0:
        break
    A = [['.' for i in range(n)] for j in range(n)]
    k = bin(k - 1)[2:].zfill(n / 2)
    if n % 2 == 1 or len(k) > n / 2:
        print "No\n"
        continue
    for i in range(n / 2):
        if k[i] == '1':
            A[0][i * 2] = 'E'
            A[0][i * 2 + 1] = 'E'
    print ''.join(A[0])
    for i in range(n - 1):
        for j in range(n):
            cnt = 0
            if i > 0 and A[i][j] == A[i - 1][j]:
                cnt += 1
            if j > 0 and A[i][j] == A[i][j - 1]:
                cnt += 1
            if j < n - 1 and A[i][j] == A[i][j + 1]:
                cnt += 1
            if cnt == 1:
                A[i + 1][j] = A[i][j]
            elif A[i][j] == '.':
                A[i + 1][j] = 'E'
            else:
                A[i + 1][j] = '.'
        print ''.join(A[i + 1])
    print 


Measured memory_bytes: 4724
#include <iostream>
#include <cstdio>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    int tmp, lst = 0, res = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &tmp);
        if (tmp == i) {
            if (!lst) {
                lst = 1;
                res++;
            } else {
                lst = 0;
            }
        } else {
            lst = 0;
        }
    }
    printf("%d", res);
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
	string s,t;
	int cnt=0;
	cin>>s>>t;
	for(int i=0;i<s.size();i++){
		if(s[i]!=t[i]){
			cnt++;
		}
	}
	cout<<cnt<<"\n";
}

Measured memory_bytes: 3912
#include <iostream>

using namespace std;

int main() {
    int N, L;
    cin >> N >> L;
    int mint = abs(L);
    int mini = 0;
    int total = 0;
    for (int i = 0; i < N; ++i) {
        int current = L + i;
        total += current;
        if (abs(current) < mint) {
            mint = abs(current);
            mini = i;
        }
    }
    cout << (total - (L + mini)) << endl;
}


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

int main(){
  int a,b,c,x,y,z;
  cin >> a >> b >> c >> x >> y;
  long int res,need=2000000000;
  z=max(x,y);
  for(int i=0;i<=z;i++){
    res=i*2*c+a*max(x-i,0)+b*max(y-i,0);
    need=min(res,need);
  }
  cout << need <<endl;
}


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

using namespace std;

constexpr int MAX = 55;
constexpr int MOD = ((1e9) + 7);

int Na, Nt, Ng, Nc;
int mem[MAX][MAX][MAX][MAX];

int solve(int na, int nt, int ng, int nc,
          int idx, const vector<int>& v)
{
    if (idx == (int)v.size()) {
        return (na == Na && nt == Nt && ng == Ng && nc == Nc); 
    }
    
    int& res = mem[na][nt][ng][nc];
    if (res != -1) return res;
    res = 0;
    for (int i = 0; i < 4; i++) {
        if (!(v[idx] >> i & 1)) continue;            
        switch (i) {
            case 0:
                if (na < Na) {
                    res += solve(na + 1, nt, ng, nc, idx + 1, v);
                }                    
                break;
                
            case 1:
                if (nt < Nt) {
                    res += solve(na, nt + 1, ng, nc, idx + 1, v);
                }                    
                break;
                
            case 2:
                if (ng < Ng) {
                    res += solve(na, nt, ng + 1, nc, idx + 1, v);
                }                    
                break;
                
            case 3:
                if (nc < Nc) {
                    res += solve(na, nt, ng, nc + 1, idx + 1, v);
                }                    
                break;
        }
        res %= MOD;
    }    
    return res;
}

int to_num(char ch)
{
    if (ch == 'A') return 0;
    if (ch == 'T') return 1;
    if (ch == 'G') return 2;
    return 3;
}

map<string, vector<string>> mp;

vector<int> make(const string& s)
{
    vector<int> res;
    if (s[0] == '[') {
        int S = 0;
        for (int i = 1; i < (int)s.size() - 1; i++) {
            S |= (1 << to_num(s[i]));
        }            
        res.emplace_back(S);
    } else {        
        for (const auto& next : mp[s]) {
            auto r = make(next);
            res.insert(res.end(), r.begin(), r.end());
            if ((int)res.size() > Na + Nt + Nc + Ng) {
                break;
            }
        }
    }
    return res;
}

int main()
{
    int m;
    cin >> Na >> Nt >> Ng >> Nc >> m;
    cin.ignore();
        
    vector<string> name(m);
    for (int i = 0; i < m; i++) {
        string s;
        getline(cin, s);
        stringstream ss(s);
        ss >> name[i]; name[i].erase(name[i].size() - 1);
        while (ss >> s) {
            mp[name[i]].emplace_back(s);
        }
    }

    auto v = make(name[0]);
    memset(mem, -1, sizeof(mem));
    cout << solve(0, 0, 0, 0, 0, v) << endl;
    return 0;
}

Measured memory_bytes: 38964
#include <math.h>
#include <ctype.h>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
struct omt{omt(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int main(){
    int n;
    map<int, int> mp;

    while(cin >> n){
        mp[n]++;
    }
    
    int ma = 0;
    vector<int> A;
    for(auto x : mp){
        if(x.second > ma){
            A.clear();
            ma = x.second;
            A.push_back(x.first);
        }else if(x.second == ma){
            A.push_back(x.first);
        }
    }
    sort(A.begin(), A.end());
    for(auto x : A) cout << x << endl;


    return 0;
}


Measured memory_bytes: 3012
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,seg_func,unit):
        self.N = 1 << (N-1).bit_length()
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)

    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(len(init_value)):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])

    def set_val(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        i >>= 1
        while i:
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
            i >>= 1

    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)

    def max_right(self,l,z):  # [l,r-1] で True,[l,r] で False たる r
        if l >= self.N:
            return self.N
        l += self.N
        s = self.unit
        while True:
            while l % 2 == 0:
                l >>= 1
            if not z(self.func(s,self.tree[l])):
                while l < self.N:
                    l *= 2
                    if z(self.func(s, self.tree[l])):
                        s = self.func(s, self.tree[l])
                        l += 1
                return l - self.N
            s = self.func(s, self.tree[l])
            l += 1
            if l & -l == l:
                break
        return self.N

    def min_left(self,r,z):  # [l,r-1] で True,[l-1,r-1] で False たる l
        if r <= 0:
            return 0
        r += self.N
        s = self.unit
        while True:
            r -= 1
            while r > 1 and r % 2:
                r >>= 1
            if not z(self.func(self.tree[r], s)):
                while r < self.N:
                    r = r*2+1
                    if z(self.func(self.tree[r], s)):
                        s = self.func(self.tree[r], s)
                        r -= 1
                return r + 1 - self.N
            s = self.func(self.tree[r], s)
            if r & -r == r:
                break
        return 0


def seg_func(x,y):
    return max(x,y)

unit = 0


N,Q = MI()
A = LI()
ST = SegTree(N,seg_func,unit)

ST.build(A)

for _ in range(Q):
    t,a,b = MI()
    if t == 1:
        ST.set_val(a-1,b)
    elif t == 2:
        print(ST.fold(a-1,b))
    else:
        def z(x):
            return x < b
        print(min(ST.max_right(a-1,z),N)+1)


Measured memory_bytes: 97652
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;

int main()
{
  int n,m;
  string s;
  cin >> n;
  cin >> s;
  int ans = 0;
  for(int i=0;i<n-2;i++)
    if(s[i] == 'A' && s[i+1]=='B' && s[i+2]=='C')
      ans++,i+=2;
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
 
struct Puddle{
    int start, end, area;
};
 
int main(){
    string str;
    cin >> str;
    int n = str.size(), overall = 0;
    stack<Puddle> S;
    stack<int> slope;
 
    for(int i = 0; i < n; i++){
        if(str[i] == '\\'){
            slope.push(i);
        } else if(str[i] == '/'){
            if(!slope.empty()){
                int b = slope.top();
                Puddle temp;
                temp.start = slope.top();
                slope.pop();
                temp.end = i;
                temp.area = (temp.end - temp.start);
                overall += temp.area;
                while( !S.empty() ){
                    if(temp.start < S.top().start){
                        temp.area += S.top().area;
                        S.pop();
                    } else {
                        break;
                    }
                }
                S.push(temp);
            }
        }
    }
    cout << overall << endl;
    int m = S.size(), A[m];
    cout << m;
    for(int i = 0; i < m; i++){
        A[m - i - 1] = S.top().area;
        S.pop();
    }
    for(int i = 0; i < m; i++)
        cout << " " << A[i];
    cout << endl;
}

Measured memory_bytes: 1312
data = list(input().split(" "))
stack = []
for d in data:
    if d == '+':
        stack.append(stack.pop() + stack.pop())
    elif d == '-':
        stack.append(- stack.pop() + stack.pop())
    elif d == '*':
        stack.append(stack.pop() * stack.pop())
    else:
        stack.append(int(d))
print(stack[0])


Measured memory_bytes: 5600
#pragma GCC optimize("Ofast")
#include <iostream>
#define ll long long
using namespace std;

int main(){
  int x;
  cin>>x;
  if(400<=x&&x<600){
    cout<<8<<endl;
    return 0;
  }
  if(600<=x&&x<800){
    cout<<7<<endl;
    return 0;
  }
  if(800<=x&&x<1000){
    cout<<6<<endl;
    return 0;
  }
  if(1000<=x&&x<1200){
    cout<<5<<endl;
    return 0;
  }
  if(1200<=x&&x<1400){
    cout<<4<<endl;
    return 0;
  }
  if(1400<=x&&x<1600){
    cout<<3<<endl;
    return 0;
  }
  if(1600<=x&&x<1800){
    cout<<2<<endl;
    return 0;
  }
  if(1800<=x&&x<2000){
    cout<<1<<endl;
    return 0;
  }
}

Measured memory_bytes: 3628