akhauriyash/Code-Regression huggingface dataset:
K = int(input())
sum = 0
class gcd:
    def __init__(self,a,b,c):
        self.a=a
        self.b=b
        self.c=c
        
    def gcds(self):
        if self.a>self.b:
            x=self.a
            y=self.b
        else:
            x=self.b
            y=self.a
            
        while x % y!=0:
            tem_y = y
            y = x % y 
            x = tem_y
       
        gcd_1 = y
        
        if gcd_1>self.c:
            x=gcd_1
            y=self.c
        else:
            x=self.c
            y=gcd_1
            
        while x % y!=0:
            tem_y = y
            y = x % y 
            x = tem_y
       
        return int(y)

for i in range(1,K+1):
    for j in range(i,K+1):
        for l in range(j,K+1):
            if i==j and j==l:
                sum = sum + gcd(i,j,l).gcds()
            elif i != j and j==l:
                sum = sum + gcd(i,j,l).gcds()*3
            elif i==j and j!= l:
                sum = sum + gcd(i,j,l).gcds()*3
            elif i!=j and j!=l:
                sum = sum + gcd(i,j,l).gcds()*6         
            
print(sum)

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

typedef long long LL;

LL t,n,m,ans,tot;
LL f[111],g[111];

int main()
{
	LL i,j,k,l,ca=0,u,v,w;
	cin>>n;
	for(i=1;ans<n;i++){
		ans+=i;
	}
	cout<<i-1;
	return 0;
 } 

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

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef long long int ll;
typedef unsigned long long int ull;
#define inf INT_MAX
#define minf INT_MIN
#define watch(x)	cout<<(#x)<<"=>"<<x<<'\n';
#define sz(a) (int)(a).size()
#define all(x) x.begin(),x.end()
#define MOD 1000000007 

ll ans;
int arr[300009];
vi vr;
void solve()
{
    int n;  cin>>n;
    ans = n;
    ans = ans * (n-1);
    ans = ans % MOD;
    for(int i = 2; i < n; ++i){
        ans = ((ans)*10)%MOD;
    }
    cout<<ans;

    cout<<'\n';
}

void sol(){
    int n;  cin>>n;
    ll tenn =1, ninen =1, aten = 1;

    for(int i = 0; i < n; ++i){
        tenn *= 10;
        tenn %= MOD;
        ninen *= 9;
        ninen %= MOD;
        aten *= 8;
        aten %= MOD;
    }
    ninen *= 2;
    ninen %= MOD;
    ans = (tenn - ninen) % MOD;
    if(ans < 0) ans += MOD;
    ans = (ans + aten) % MOD;
    cout<<ans;

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testc;  testc = 1;
    for(int t = 0; t < testc; ++t){
        sol();
    }
    return 0;
}

	//Sun 13 Sep 2020 05:46:43 PM IST


		/***astrainL3gi0N***/


Measured memory_bytes: 3616
from sys import stdin
from sys import setrecursionlimit
setrecursionlimit(10 ** 7)

n = int(input())
point = 0
flag = False

for _ in range(n):
    a,b = map(int,input().split())
    
    if a == b:
        point += 1
    else:
        point = 0

    if point == 3:
        flag = True

if flag:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9184
#include <bits/stdc++.h>
#define rep(i,n)for(long long i=0;i<(n);i++)
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int MAX = 1000000;
const ll INF = (1LL << 31) - 1;
const double pi=acos(-1);


int main(){
  int n,m;
  cin >> n >> m;
  vector<int>c(n+1,0);
  rep(i,m){
    int l,r;
    cin >> l >> r;
    l--;
    c[l]++;
    c[r]--;  
  }
  rep(i,n){
    c[i+1]+=c[i];
  }
  int ans=0;
  rep(i,n+1){
    if(c[i]==m)ans++;
  }
  
  cout << ans << endl;
  return 0;
  
    
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define ll long long
const long long M = 10e9+7;
int main()
{
	int n;cin>>n;
	vector<int>p,q;
	for(int i=1;i<=n;i++) 
	{
		int x;cin>>x;
		p.push_back(x);
	}
	for(int i=1;i<=n;i++) 
	{
		int x;cin>>x;
		q.push_back(x);
	}
	vector<int>aasol;
	for(int i=1;i<=n;i++) 
	{
		aasol.push_back(i);
	}
	int a=1,b=1,idx=1;
	do
	{
		if(aasol==p) a = idx;
		if(aasol==q) b = idx;
		/*cout<<"idx = "<<idx<<" a = "<<a<<" b = "<<b<<endl;
		cout<<"Current elements after next permutation:\n";
		for(int i=0;i<aasol.size();i++)
			cout<<aasol[i]<<" ";
		cout<<endl;
		*/
		idx++;
	}
	while(next_permutation(aasol.begin(),aasol.end()));
	cout<<abs(a-b)<<"\n";
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
import numpy as np

h, n = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]
ab = np.array(ab)

a = ab[:, 0]
b = ab[:, 1]

dp = np.zeros(100001, dtype=np.int)
for i in range(1, h+1):
    dp[i] = (dp[i-a]+b).min()

print(dp[h])

Measured memory_bytes: 14540
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repr(i,n) for(int i = (int)(n); i >= 0; i--)
#define all(v) v.begin(),v.end()
typedef long long ll;

int main(){
    int N,K;
    cin >> N >> K;
    int ans = 1;
    while (N / K != 0){
        N /= K;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N,i,j,k;
  unsigned long counter=0;
  cin >> N;
  vector<unsigned long> A(N);
  for(i=0;i<N;i++){
    cin >> A[i];
  }
  
  sort(A.begin(), A.end());
 
  for(i=0;i<N-2;i++){
    for(j=i+1;j<N-1;j++){
      if(A[i]==A[j]) continue;
      for(k=j+1;k<N;k++){
        if(A[j]==A[k]) continue;
          if(A[k]<A[i]+A[j]){
            counter++;
          }else break;
        }

      }
    }
    cout << counter;
  }

Measured memory_bytes: 3632
#include <stdio.h>

int main(void)
{
	int i,j,mt_height[10];

	for (i = 0; i < 10; i++)
	{
		scanf("%d",&mt_height[i]);
	}

	for (i=0;i<9;i++)
	{
		for (j = 9; j >= 0; j--)
		{
			if (mt_height[j + 1] > mt_height[j])
			{
				int temp = mt_height[j+1];
				mt_height[j+1] = mt_height[j];
				mt_height[j] = temp;
			}
		}
	}

	for (i = 0; i < 3; i++)
		printf("%d\n", mt_height[i]);

	return 0;
}

Measured memory_bytes: 2664
N,W = map(int, input().split())
w = [0]*N
v = [0]*N
for i in range(N):
    w[i],v[i] = map(int, input().split())

dp = [[0 for i in range(W)] for j in range(N)]

for i in range(N):
    for j in range(w[i]-1,W):
        dp[i][j] = v[i]

for i in range(1,N):
    for j in range(W):
        if j >= w[i]:
            dp[i][j] = max(dp[i][j],dp[i-1][j],dp[i-1][j-w[i]]+v[i])
        else:
            dp[i][j] = max(dp[i][j],dp[i-1][j])
print(dp[-1][-1])

Measured memory_bytes: 172424
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
  int N;
  cin >> N;
  set<string> S;
  rep(i,N){
    string x;
    cin >> x;
    S.insert(x);
  } 
  cout << S.size() << endl;
  }



Measured memory_bytes: 19204
#include <cstdio>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int t, p, r;
        cin >> t >> p >> r;
        if(t == 0)
            return 0;

        vector<vector<int> > wrong(t, vector<int>(p, 0));
        vector<pair<pair<int, int>, int> > a(t);
        for(int i=0; i<t; ++i)
            a[i].second = i+1;

        while(--r >= 0){
            int tID, pID, time;
            string message;
            cin >> tID >> pID >> time >> message;
            -- tID;
            -- pID;

            if(message == "WRONG"){
                ++ wrong[tID][pID];
            }else{
                -- a[tID].first.first;
                a[tID].first.second += 1200 * wrong[tID][pID] + time;
            }
        }

        sort(a.begin(), a.end());
        for(int i=0; i<t; ++i)
            cout << a[i].second << ' ' << -a[i].first.first << ' ' << a[i].first.second << endl;
    }
}

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


int main()
{
  int n;
  cin >> n;
  int c = 0;
  for (int i=1; i<=n; i++)
  {
    int p;
    cin >> p;
    if (p != i)
      c++;
  }
  if (c == 0 || c == 2)
    cout << "YES\n";
  else
    cout << "NO\n";
  return 0;
}

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

int main() {
  int n,k; cin >> n >> k;
  vector<int> h(n);
  rep(i,n) cin >> h[i];
  int ans = 0;
  rep(i,n) if(h[i] >= k) ans++;
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define mt              make_tuple
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define range(a,b)		substr(a,b-a+1)
#define w(x)            int x; cin>>x; while(x--)
#define trace(x) 		cerr<<#x<<": "<<x<<" "<<endl;
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

struct FenwickTree
{
	int N;
	vector<int> tree;

	void init(int n)
	{
		N = n;
		tree.assign(n + 1, 0);
	}

	void update(int idx, int val)
	{
		while (idx <= N)
		{
			tree[idx] += val;
			idx += idx & -idx;
		}
	}

	void updateMax(int idx, int val)
	{
		while (idx <= N)
		{
			tree[idx] = max(tree[idx], val);
			idx += idx & -idx;
		}
	}

	int pref(int idx)
	{
		int ans = 0;
		while (idx > 0)
		{
			ans += tree[idx];
			idx -= idx & -idx;
		}
		return ans;
	}

	int rsum(int l, int r)
	{
		return pref(r) - pref(l - 1);
	}

	int prefMax(int idx)
	{
		int ans = -2e9;
		while (idx > 0)
		{
			ans = max(ans, tree[idx]);
			idx -= idx & -idx;
		}
		return ans;
	}
};

bool cmp(pair<pii, int> a, pair<pii, int> b)
{
	return a.ff.ss < b.ff.ss;
}

int32_t main()
{
	FIO;
	int n, q; cin >> n >> q;

	vi arr(n + 1);

	for (int i = 1; i <= n; ++i)
		cin >> arr[i];

	vector<pair<pii, int> > qr(q);

	for (int i = 0; i < q; ++i)
	{
		cin >> qr[i].ff.ff >> qr[i].ff.ss;
		qr[i].ss = i;
	}

	sort(qr.begin(), qr.end(), cmp);

	vi ls(n + 1, 0);
	FenwickTree bit;
	bit.init(n);

	int id = 1;

	vi ans(q);

	for (int i = 0; i < q; ++i)
	{
		int l = qr[i].ff.ff;
		int r = qr[i].ff.ss;

		while (id <= r)
		{
			int val = arr[id];

			if (ls[val])
				bit.update(ls[val], -1);

			bit.update(id, 1);

			ls[val] = id;

			id++;
		}

		ans[qr[i].ss] = bit.rsum(l, r);
	}

	for (int i : ans)
		cout << i << '\n';
	return 0;
}

Measured memory_bytes: 31140
import collections
n = int(input())
a = list(map(int,input().split()))
q = int(input())
bc = [[int(i) for i in input().split()] for _ in range(q)]

total = sum(a)
s = collections.Counter(a)


for x in range(q):
    if bc[x][0] in s and bc[x][1] in s:
        s[bc[x][1]] += s[bc[x][0]]
        total += (bc[x][1]-bc[x][0]) * s[bc[x][0]]
        del s[bc[x][0]]
    elif bc[x][0] in s and bc[x][1] not in s:
        s[bc[x][1]] = s[bc[x][0]]
        total += (bc[x][1]-bc[x][0]) * s[bc[x][0]]
        del s[bc[x][0]]
    print(total)

Measured memory_bytes: 36100
import  java.util.*;
class Main{
    int a;
    int b;
    
    Main(){
	Scanner sc=new Scanner(System.in);
	for(int i=1; i<8; i++){
	    a=sc.nextInt();
	    b=sc.nextInt();
	    System.out.println(a-b);
	}

    }

    public static void main(String[] args){
	new Main();
    }
}

Measured memory_bytes: 17364
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 405;
const int P = 998244353;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, sa, sb, a[MAXN], b[MAXN];
int f[MAXN][MAXN], g[MAXN], coef[MAXN][MAXN];
int fac[MAXN], inv[MAXN], binom[MAXN][MAXN];
int power(int x, int y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
int main() {
	read(n), sa = 0, f[0][0] = 1;
	for (int i = 1; i <= n; i++) {
		read(a[i]), read(b[i]);
		sa += a[i], sb += b[i];
	}
	fac[0] = inv[0] = binom[0][0] = 1;
	for (int i = 1; i <= max(sa, sb); i++) {
		fac[i] = 1ll * fac[i - 1] * i % P;
		inv[i] = power(fac[i], P - 2);
		binom[i][0] = 1;
		for (int j = 1; j <= i; j++) {
			binom[i][j] = (binom[i - 1][j - 1] + binom[i - 1][j]) % P;
		}
	}
	for (int x = 1, s = 0; x <= n; s += b[x++]) {
		memset(g, 0, sizeof(g));
		int p = 1ll * a[x] * power(sa, P - 2) % P;
		for (int i = 0, now = 1; i <= b[x] - 1; i++, now = 1ll * now * p % P)
			g[i] = (P - 1ll * now * inv[i] % P) % P;
		for (int i = sa; i >= 0; i--) {
			static int tmp[MAXN];
			memset(tmp, 0, sizeof(tmp));
			for (int j = 0; j <= b[x]; j++)
			for (int k = 0; k <= s; k++) {
				update(tmp[j + k], 1ll * f[i][k] * g[j] % P);
			}
			memcpy(f[i], tmp, sizeof(tmp));
			if (i >= a[x]) {
				for (int j = 0; j <= s; j++)
					update(f[i][j], f[i - a[x]][j]);
			}
		}
	}
	assert(f[sa][0] == 1);
	int ans = 0;
	for (int i = 0; i <= sb; i++)
		update(ans, 1ll * f[0][i] * fac[i] % P);
	coef[0][0] = 1;
	for (int i = 1; i <= sb; i++)
	for (int j = i; j >= 0; j--) {
		coef[i][j] = 1ll * coef[i - 1][j] * i % P;
		if (j != 0) update(coef[i][j], coef[i - 1][j - 1]);
	}
	for (int i = 1; i <= sa - 1; i++) {
		static int res[MAXN];
		int p = 1ll * i * power(sa, P - 2) % P;
		memset(res, 0, sizeof(res)), res[0] = power((1 - p + P) % P, P - 2);
		for (int j = 1; j <= sb; j++) {
			int tmp = 0;
			for (int k = 0; k <= j - 1; k++)
				update(tmp, 1ll * binom[j][k] * res[k] % P);
			res[j] = 1ll * tmp * p % P * res[0] % P;
		}
		for (int j = 0; j <= sb; j++) {
			int tmp = 0;
			for (int k = 0; k <= j; k++)
				update(tmp, 1ll * res[k] * coef[j][k] % P);
			update(ans, 1ll * tmp * f[i][j] % P);
		}
	}
	writeln((P - ans) % P);
	return 0;
}

Measured memory_bytes: 2176
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 *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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


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

N_s = getN()
A = [getList() for i in range(N_s)]
B = [getList() for i in range(N_s)]
query = []
# ノードの始点を2 * N_sに、終点を2 * N_s + 1に設定
for i in range(N_s):
    query.append([2 * N_s, i, 1])
    query.append([N_s + i, 2 * N_s + 1, 1])
for i in range(N_s):
    for j in range(N_s):
        if A[i][0] < B[j][0] and A[i][1] < B[j][1]:
            query.append([i, N_s + j, 1])

N = 2 * N_s + 2

ans = 0
lines = defaultdict(set)
cost = [[0] * N for i in range(N)]
for i in range(len(query)):
    a, b, c = query[i]
    lines[a].add(b)
    cost[a][b] += c

# 二部マッチング問題なので最大流
# staからスタート
def Ford_Fulkerson(sta, end):
    global ans
    queue = deque()
    queue.append([sta, float('inf')])

    ignore = [1] * N
    ignore[sta] = 0

    route = [0] * N
    route[sta] = -1

    while queue:
        s, flow = queue.pop()
        for t in lines[s]:  #s->t
            if ignore[t]: #未到達
                # flowは入ってくる量、出る量のうち小さい方
                flow = min(cost[s][t], flow)
                route[t] = s
                queue.append([t, flow])
                ignore[t] = 0
                if t == end: #ゴール到達
                    ans += flow
                    break
        else:
            continue #breakされなければWhile節の先頭に戻る
        # Falseはされない
        break
    else:
        return False

    t = end
    s = route[t]
    # goalまで流れた量はflow
    # 逆向きの辺を貼る
    while s != -1:
        #s->tのコスト減少，ゼロになるなら辺を削除
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)
            #t->s(逆順)のコスト増加，元がゼロなら辺を作成
        if cost[t][s] == 0:
            lines[t].add(s)

        cost[t][s] += flow

        # 一つ上の辺をたどる
        t = s
        s = route[t]

    return True

while True:
    # ちょびちょび流して行ってゴールまで流れなくなったら終了
    if Ford_Fulkerson(N - 2, N - 1):
        continue
    else:
        break

print(ans)

Measured memory_bytes: 84152
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
#define MOD (ll)(1e9+7)
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

signed main(){
    ll n,k,r,s,p;
    cin >> n >> k >> r >> s >> p;
    string t;
    cin >> t;

    ll ans = 0;
    bool is_proper[(ll)t.size()] = {false};
    rep(i,0,t.size()){
        if(i-k >= 0 && t[i] == t[i-k]){
            if(is_proper[i-k]){
                continue;
            }
        }
        switch (t[i]){
        case 'r':
            ans += p;
            break;
        case 's':
            ans += r;
            break;
        case 'p':
            ans += s;
            break;
        }
        is_proper[i] = true;
    }

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


Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph= vector<vector<int>>; 
#define rep(i,n) for (ll i=0; i < (n); ++i)
#define rep2(i,n,m) for(ll i=n;i<=m;i++)
#define rep3(i,n,m) for(ll i=n;i>=m;i--)
#define pb push_back
#define eb emplace_back
#define ppb pop_back
const ll INF=1e18 ;
inline void chmax(ll& a,ll b){a=max(a,b);}
inline void chmin(ll& a,ll b){a=min(a,b);}
 
int main(){
  ll n ; cin >> n;
  string s ;cin>>s ;
  ll k=s.size() ;
  ll wh=0 ;
  rep(i,k){
      if(s[i]=='.') wh++ ;
  }
   ll ans=wh ;
   rep(i,k){
       if(s[i]=='.') wh-- ;
       else wh++ ;
       chmin(ans,wh) ;
   } 
    cout <<ans<<endl ;
    return 0;
  }

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

int main() {

	int n,k,x,y;

	cin >> n >> k >> x >> y;

	if (n>k) {
		cout << k * x + (n - k)*y << endl;
	}

	else{
		cout << n*x << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n, m, f[100005];
int find(int x) {
	if(f[x]==x) return x;
	return f[x]=find(f[x]);
}
int read() {
	int x=0; char ch;
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
	return x;
}
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++) {
		int a, b, c;
		a=read(), b=read(), c=read();
		int x=find(a), y=find(b);
		if(x!=y) f[x]=y;
	}
	int cnt=0;
	for(int i=1;i<=n;i++) {
		if(find(i)==i) cnt++;
	}
	cout<<cnt;
}

Measured memory_bytes: 1152
import functools

import os

INF = float('inf')


def inp():
    return int(input())


def inpf():
    return float(input())


def inps():
    return input()


def inl():
    return list(map(int, input().split()))


def inlf():
    return list(map(float, input().split()))


def inls():
    return input().split()


def inpm(line):
    return [inp() for _ in range(line)]


def inpfm(line):
    return [inpf() for _ in range(line)]


def inpsm(line):
    return [inps() for _ in range(line)]


def inlm(line):
    return [inl() for _ in range(line)]


def inlfm(line):
    return [inlf() for _ in range(line)]


def inlsm(line):
    return [inls() for _ in range(line)]


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        ret = fn(*args, **kwargs)
        print(ret)
        return ret

    return wrapper

a, b, c = inl()
if a == b:
    print(c)
elif a ==c:
    print(b)
else:print(a)


Measured memory_bytes: 3572
M_lis = []  
H,W = map(int,input().split())
DP = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    M_lis.append(list(map(int,list(str(input())))))
for j in range(1,W):
    DP[0][j] += M_lis[0][j] + DP[0][j - 1]
for k in range(1,H):
    DP[k][0] += M_lis[k][0] + DP[k - 1][0]
for i in range(1,H):
    for j in range(1,W):
        DP[i][j] = min(DP[i - 1][j],DP[i][j - 1]) + M_lis[i][j]

print(DP[H - 1][W - 1])
    

Measured memory_bytes: 7816
x=int(input())
n=120
gojou=[0]*(n+1)*2
for i in range(n+1):
    gojou[i]=i**5

for i in range(n+1):
    for j in range(n+1):
        if gojou[i]-gojou[j]==x:
            print(i,j)
            break
        elif gojou[i]+gojou[j]==x:
            if i**5 - (-j)**5 == x:
                print(i,-j)
                break
    else:
        continue
    break

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

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 __ = rvn::<i32>(&mut br);
    let (a, b) = (__[0], __[1]);

    writeln!(&mut bw, "{}", max(a+b, max(a-b, a*b)));
}


//////////////////////////////////////////////////////////////////////////////////
#[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
def chkp(P):
    global n, k, w
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= P:
            s += w[i]
            i += 1
            if(i == n):
                return n
    return i

def binary_search():
    l = 0
    r = 100000 * 10000
    while r - l > 1:
        c = (l+r) // 2
        v =  chkp(c)
        if(v >= n):
            r = c
        else:
            l = c
    return r

n, k = map(int, input().split())
w = [int(input()) for i in range(n)]
res = binary_search()
print(int(res))


Measured memory_bytes: 9560
N = int(input())
l = [-1] * N

print(0)
s = input()
if s=="Male":
    l[0] = 0
elif s=="Female":
    l[0] = 1
else:
    exit(0)

print(N-1)
s = input()
if s=="Male":
    l[N-1] = 0
elif s=="Female":
    l[N-1] = 1
else:
    exit(0)

left, right = 0, N-1
while right-left>1:
    mid = (left+right)//2

    print(mid)
    s = input()
    if s=="Male":
        l[mid] = 0
    elif s=="Female":
        l[mid] = 1
    else:
        exit(0)

    if (l[mid]==l[left] and (mid-left)%2) or (l[mid]!=l[left] and (mid-left)%2==0):
        right = mid
    else:
        left = mid


Measured memory_bytes: 9868
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		 Scanner scan = new Scanner(System.in);
		 
		 long A = scan.nextLong();
		 long B = scan.nextLong();
		 int C = scan.nextInt();
		 int D = scan.nextInt();
		 
		 long cnt_C = 0;
		 long cnt_D = 0;
		 long cnt_C_and_D = 0;
		 
		 long lcm_C_and_D = lcm (C,D);
		 
		 cnt_C = B / (long)C - calc_rounding_quo(A, (long)C) + 1;
		 cnt_D = B / (long)D - calc_rounding_quo(A, (long)D) + 1;
		 cnt_C_and_D = B / lcm_C_and_D - calc_rounding_quo(A, lcm_C_and_D) + 1;
		 
		 System.out.println(B - A + 1 - cnt_C - cnt_D + cnt_C_and_D);
		 
		 scan.close();
		 
	}
	
	public static long lcm (long m, long n) {
		return m * n / gcd(m, n);
		
	}
	
	public static long gcd (long m, long n) {
		if (m < n) 	return gcd(n, m);
		if (n == 0) return m;
		return gcd(n, m % n);
		
	}
	
	public static long calc_rounding_quo (long a, long b) {
		return (a + b - 1) / b;
		
	}

}


Measured memory_bytes: 21844
N = input()
mod = 10 ** 9 + 7
num_p = [1] * 1001
p = []
# find p
for i in range(2, N + 1):
  canDivide = True
  for j in range(2, i):
    if i % j == 0:
      canDivide = False
      break
  if canDivide:
    p.append(i)

# factorization
for i in range(2, N + 1):
  for j in p:
    c = 0
    target = i
    while target % j == 0:
      c += 1
      target /= j
    num_p[j] = (num_p[j] + c) % mod

print reduce(lambda x, y: x * y, num_p) % mod

Measured memory_bytes: 2820
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
  int n;
  while(cin >> n,n)
    {
      vector<int> vec;
      vec.resize(n);
      for(int i=0;i<n;i++)
	cin >> vec[i];

      int ans = 0;

      for(int i= vec.size()-1;i>0;i--)
	for(int j=0;j<i;j++)
	  if(vec[j+1] < vec[j])
	    ans++,swap(vec[j+1],vec[j]);

      cout << ans << endl;

    }
  return 0;
}

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

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> L(n);
    for(int i=0; i<n; i++) cin >> L[i];
    vector<int> D = {0};
    int count = 1;

    for(int i=1; i<=n; i++ ) {
        D[i] = D[i-1]+L[i-1];
        if(D[i] <= x) count++;
    }
    cout << count << endl;
}

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

using namespace std;
int main(){
  int N,M;
  cin >>N>>M;
  vector<vector<int> >data(M);
  for (int i=0;i<N;i++){
    int a,b;
    cin>>a>>b;
    if  (a>M){
      continue;
    }
    --a;
    
    data.at(M-a-1).push_back(b);
  }
 long long y;
  priority_queue<int> pq;
  for (int i=M-1;i>=0;i--){
   for(int b:data.at(i)){
     pq.push(b);
   } 
   if(!pq.empty()){
   y+=pq.top();
     pq.pop();
   }
  }
   cout << y<<endl;
}
  


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

using namespace std;

#define Q int t, q; scanf("%d", &t); for(q=1; q<=t; q++)
typedef long long int lli;
typedef pair<lli, lli> pli;

int main()
{
    char c;
    cin >> c;
    cout << (char)(c+1) << "\n";

    return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;

class Node {
	private int parent;
	private int depth;
	private String type;
	private int childnum;
	private int[] child;
	
	Node(int d,int p){
		depth=d; parent=p; 
	}
	
	void setChildnum(int childnum){
		this.childnum=childnum;
		child=new int[childnum];
	}
	
	int getChildnum(){ return childnum; }
	
	void setChild(int x,int idx){
		child[idx]=x;
	}
	
	int getChild(int idx){ return child[idx]; }
	
	void setType(){
		if(parent==-1)
			type="root";
		else if(childnum==0)
			type="leaf";
		else 
			type="internal node";
	}
	
	int getParent(){ return parent; }
	
	void setParent(int p){ parent=p; }
	
	int getDepth(){ return depth; }
	
	void setDepth(int d){ depth=d; }
	
	String getType(){ setType(); return type; }
	
	void printChild(){
		
		System.out.print("[");
		
		for(int i=0;i<childnum;i++){
			if(i==childnum-1)
				System.out.print(child[i]);
			else 
				System.out.print(child[i] +", ");
		}
		
		System.out.println("]");
		
	}

}

class Main {
	
	static int getRoot(Node[] a,int n){
		for(int i=0;i<n;i++){
			if(a[i].getParent() == -1)
				return i;
		}
		return 0;
	}
	
	static void setdepth(Node[] a,int root){
		int c=a[root].getChildnum();
		for(int i=0;i<c;i++){
			int t=a[root].getChild(i);
			a[t].setDepth( a[root].getDepth()+1 );
			setdepth(a,t);
		}
		return;
	}
	
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		
		int n=scan.nextInt();
		Node[] a=new Node[n];
		
		for(int i=0;i<n;i++)
			a[i]=new Node(0,-1);
		
		for(int i=0;i<n;i++){
			int x=scan.nextInt(); int y=scan.nextInt();
			a[x].setChildnum(y);
			for(int j=0;j<y;j++){
				int z=scan.nextInt();
				a[x].setChild(z,j);
				a[z].setParent(x);
			}
		}
		
		int root=getRoot(a,n);
		setdepth(a,root);
		
		for(int i=0;i<n;i++){
			System.out.print("node "+i+": parent = "+a[i].getParent()+", "+"depth = "+a[i].getDepth()+", "+a[i].getType()+", ");
			a[i].printChild();
		}
			
		
	}
}


Measured memory_bytes: 144600
{-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Char8 as B
import qualified Data.Vector.Unboxed as VU
import Data.Char

solve :: Int ->  VU.Vector (Int,Int) -> VU.Vector Int
solve !h !abs = VU.foldl' step (VU.singleton 0) (VU.generate h $ \ !i -> i + 1)
    where
        step :: VU.Vector Int -> Int -> VU.Vector Int
        step !v !i =  
            let
                m = VU.foldl' (\ !x (!a,!b) -> let !y = if i >= a then b + (v VU.! (i-a)) else b in min x y) (10^9) abs
            in
                VU.generate (i+1) $ \ !j -> if j == i then m else v VU.! j 

main = do
    [h, n] <- map  read . words <$> getLine :: IO [Int]
    abs <- VU.replicateM n $ do 
        s <- B.getLine 
        let Just (a, s') = B.readInt s
        let Just (b, _) = B.readInt $ B.dropWhile isSpace s'
        return (a,b)
    print $ VU.last $ solve h abs

Measured memory_bytes: 2428
// Bismillahir Rahmanir Rahim .Ya Allah...
#include<bits/stdc++.h>
using namespace std;
typedef long long int  ll;
typedef pair<int,int> PII;
const int mod = 1e9+7,INF = 1e9;
const int mx = 1e5+5;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    ll a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    ll  pre=0,ans=0;
    for(int i=0;i<n;i++)
    {
        pre= max(pre,a[i]);
        ans+= pre-a[i];
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 5196
#include <iostream>
using ll = long long;
using namespace std;

int main() {
    int n, ans = 0;
    cin >> n;
    if (n >= 105) ans++;
    if (n >= 135) ans++;
    if (n >= 165) ans++;
    if (n >= 189) ans++;
    if (n >= 195) ans++;
    cout << ans << "\n";
    return 0;
}


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

using namespace std;

int main()
{

    char ch;
    bool isSimm;
    string str;

    while(getline(cin, str) && str != ".") {
        isSimm = true;
        stack<char> st;
        for (unsigned long i = 0; i < str.size(); i++) {
            if (str[i] == '[' || str[i] == '(') st.push(str[i]);
            else if (str[i] == ']' || str[i] == ')') {
                if (st.empty()) {
                    isSimm = false;
                    break;
                }
                ch = st.top(); st.pop();
                if ((str[i] == ']' && ch != '[') || (str[i] == ')' && ch != '(')) {
                    isSimm = false;
                    break;
                }
            }
        }

        (isSimm && st.empty()) ? cout << "yes" << endl : cout << "no" << endl;
    }

    return 0;
}



Measured memory_bytes: 3168
#include <iostream>
#include <math.h>

using namespace std;  
typedef long long LL;

int N, A, B, h[(int)1e5];

bool judge(LL K) {
    LL sum = 0;
    for(int i = 0; i < N; i++) {
        LL t = (LL)h[i]-K*B;
        if (t > 0) {
            sum += (int)ceil(t*1.0/(A-B));
            if(sum > K)
                return false;
        }
    }
    return true;
}

int main()
{
    cin >> N >> A >> B;

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

    LL low = 0, high = (int)1e9;

    while (low < high) {
        LL mid = (low + high) / 2;
        if (judge(mid))
            high = mid;
        else
            low = mid+1;
    }

    cout << low << endl;

    return 0;
}

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

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define SIZE(c) (int) (c).size()
#define FORE(i,c) FOR(i,0,SIZE(c)-1)
#define FORDE(i,c) FORD(i,SIZE(c)-1,0)

#define pb push_back
#define mp make_pair
#define st first
#define nd second


using namespace std;

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

typedef vector <int> VI;
typedef vector <bool> VB;
typedef vector <pii> VP;
typedef vector <ll> VL;
typedef vector <pll> VPL;

typedef vector <VI> VVI;
typedef vector <VL> VVL;
typedef vector <VB> VVB;
typedef vector <VP> VVP;

const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000000000000001LL;


/*************************************************************************/

int main() {
    ios_base::sync_with_stdio(0);
    
    ll n, m;
    cin >> n >> m;
    
    m /= 2;
    
    if (n >= m) {
        cout << min(n, m) << '\n';
    } else {
        ll x = (m - n) / 2;
        
        ll ans = 0;
        for (ll xval = max(0LL, x - 1); xval <= x + 1; xval++) {
            ll here = min(n + xval, m - xval);
            ans = max(ans, here);
        }
        
        cout << ans << '\n';
    }

    return 0;
}

/*************************************************************************/


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

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

    string ans = "DENIED";

    vector<int> a(n), b(n);

    rep(i,n) cin >> a.at(i);

    rep(i,n) {
        if (a.at(i) % 2 == 0) {
            b.push_back(a.at(i));
        }
    }

    int count = 0;

    rep(i,b.size()) {
        if (b.at(i) % 3 == 0 || b.at(i) % 5 == 0) count++;
    }

    if (count == b.size()) ans = "APPROVED";

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  int a,b;
  int c = 0;
  cin >> N;
  for (int i = 0;i < N;i++){
    cin >> a >> b;
    if (a == b){
      c++;
    }
    else
      c = 0;
    if (c == 3)
      break;
  }
  if (c == 3)
    cout << "Yes";
  else
    cout << "No";
}

Measured memory_bytes: 3640
ans=0
def DFS(v,visited):
    global ans
    if visited == [1]*N:
        ans += 1
        return
    for next in edge[v]:
        if visited[next] != 1:
            visited[next] = 1
            DFS(next,visited)
            visited[next] = 0 
    return

N, M = map(int,input().split())
edge = [[] for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
visited = [0 for _ in range(N)]
visited[0]=1
DFS(0,visited)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep2(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define rep(i,n) rep2(i,0,n)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
using namespace std;
using ll = long long;
template <typename T>
T sq(T x){
  return x * x;
}

signed main (){
  int K;
  string s;
  cin >> K;
  cin >> s;
if(K>=SZ(s)){

cout << s << endl;
}
  if(K<SZ(s)){
  rep(i,K){
cout << s.at(i);
  }
cout << "..."<< endl;
  }
    return 0;
}


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

int top, S[1000];

void push(int );
int pop(void );

int main(){
  int a, b;
  top = 0;
  char s[1000];

  while( scanf("%s", s) != EOF ){

    if ( s[0] == '+' ){
      a = pop();
      b = pop();
      push(a + b);
    } else if ( s[0] == '-' ){
      b = pop();
      a = pop();
      push(a - b);
    } else if ( s[0] == '*' ){
      a = pop();
      b = pop();
      push(a * b);
    } else{
      push(atoi(s));
    }
  }
  printf("%d\n",pop());

  return 0;
}

void push(int x){
  S[++top] = x;
}

int pop(){
  top--;
  return S[top+1];
}



Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
int main(){
   char word[10],arr[1000];
    int c=0,i;
    scanf("%s", word);
    while(1){
        scanf("%s",arr);
        if(strcmp(arr,"END_OF_TEXT")==0){
            break;
        }
        for(i=0;i<1000;i++){
            arr[i]=tolower(arr[i]);
        }
        if(strcmp(arr,word)==0){
            c++;
        }
    }
    printf("%d\n",c);

    return 0;
}



Measured memory_bytes: 3204
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

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

    string s;
    cin >> s;

    if (s=="ABC")
        cout << "ARC" << endl; 
    else
        cout << "ABC" << endl; 

    return 0;
}


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

using namespace std;

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m, x;
    cin >> n >> m >> x;
    int costs[n];
    int values[n][m];
    for (int i = 0; i < n; i++) {
        cin >> costs[i];
        for (int j = 0; j < m; j++) {
            cin >> values[i][j];
        }
    }
    int res = -1;
    for (int i = 1; i < (1 << n); i++) {
        int bin = i, ind = 0;
        int cost = 0;
        long long sum[20] = {};
        while (bin) {
            if (bin & 1) {
                cost += costs[ind];
                for (int j = 0; j < m; j++) {
                    sum[j] += values[ind][j];
                }
            }
            bin /= 2;
            ind++;
        }
        bool poss = true;
        for (int j = 0; j < m; j++) {
            if (sum[j] < x)
                poss = false;
        }
        if (poss) {
            if (res == -1)
                res = cost;
            else
                res = min(res, cost);
        }
    }
    cout << res;


    return 0;
}

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

using namespace std;

const int N=1e6+3;

#define pb push_back
#define all(x) (x).begin(),(x).end()
typedef long long ll;

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

const int inf=1e9;

int n,m,a[N],k,q,u,v,x,y,tc,c,l,r,ans,cnt[N];

char s[N];

int main(){
	scanf("%s",s);
	char c='1';
	int ans1=0,ans2=0;
	for(int i=0;s[i];i++){
		if (s[i]!=c)
			ans1++;
		else
			ans2++;
		if (c=='1')
			c='0';
		else
			c='1';
	}
	printf("%d\n",min(ans1,ans2));
}



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

struct Point {int x1, y1, x2, y2;};

bool ok() {
  int R, C, N;
  cin >> R >> C >> N;
  vector<Point> P(N);
  for(auto& i: P) cin >> i.x1 >> i.y1 >> i.x2 >> i.y2;

  auto both = [&](auto p) {
    auto p1 = p.x1==0 || p.x1==R || p.y1==0 || p.y1==C;
    auto p2 = p.x2==0 || p.x2==R || p.y2==0 || p.y2==C;
    return p1 && p2;
  };
  auto index = [&](auto x, auto y) {
    if(y==0) return x;
    if(x==R) return R+y;
    if(y==C) return R+C+(R-x);
    return R+C+R+(C-y);
  };

  set<pair<int,int>> Q;
  for(auto i=0; i<N; ++i) if(both(P[i])) {
    Q.emplace(make_pair(index(P[i].x1, P[i].y1), i));
    Q.emplace(make_pair(index(P[i].x2, P[i].y2), i));
  }

  stack<int> S;
  set<int> used;
  for(auto q: Q) {
    auto i = q.second;
    if(used.count(i)) {
      if(i != S.top()) return false;
      S.pop();
    } else {
      used.emplace(i);
      S.emplace(i);
    }
  }
  return true;
}

int main() {
  cout << (ok() ? "YES" : "NO") << endl;
}


Measured memory_bytes: 15872
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define mat vector<vector<int>>
const int inf = 1 << 30;
const ll linf = 1e18;
const db EPS = 1e-7;
template<class T> void chmin(T& x, T y){if(x > y) x = y;}
template<class T> void chmax(T& x, T y){if(x < y) x = y;}

ll N, M, V, P;
vector<ll> as, sum;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> V >> P;
    for(int i = 0; i < N; ++i){
        int A;
        cin >> A;
        as.emplace_back(A);
    }
    sort(as.begin(), as.end());
    ll s = 0;
    for(int i = 0; i < N; ++i){
        s += as[i];
        sum.emplace_back(s);
    }
    int cnt = 0;
    for(int i = 0; i < N; ++i){
        int it = upper_bound(as.begin(), as.end(), as[i] + M) - as.begin() - 1;
        if(it < N - P) continue;
        it = N - P;
        chmax(it, i);
        ll len = it - i;
        ll cap = M * (P + i) + (as[i] + M) * len - (sum[it] - sum[i]);
        if(cap >= V * M) cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 2548
#include <iostream>
typedef long long ll;
using namespace std;

ll f(ll A) {
  ll X = (A + 1) / 2 % 2 == 0 ? 0 : 1;
  return A % 2 == 0 ? A ^ X : X;
}

int main() {
  ll A,B;
  cin >> A >> B;
  cout << (A > 0 ? f(A-1) ^ f(B) : f(B)) << endl;
}


Measured memory_bytes: 256
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	rs := make(Rests, n)
	for i := range rs {
		rs[i] = &Rest{s: next(), p: nextInt(), id: i + 1}
	}
	sort.Sort(rs)
	for i := range rs {
		puts(rs[i].id)
	}
	wt.Flush()
}

type Rest struct {
	s  string
	p  int
	id int
}

type Rests []*Rest

func (rs Rests) Len() int {
	return len(rs)
}

func (rs Rests) Less(i, j int) bool {
	if rs[i].s == rs[j].s {
		return rs[i].p > rs[j].p
	}
	return rs[i].s < rs[j].s
}

func (rs Rests) Swap(i, j int) {
	rs[i], rs[j] = rs[j], rs[i]
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	i, _ := strconv.Atoi(next())
	return i
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 640
#include<stdio.h>
#include<string.h>
int main(void)
{
	int i;
	char s[20];
	scanf("%s",s);
	for(i=0;i<=4;i++){
		printf("%c",s[i]);
	}
	printf(" ");
	for(i=6;i<=12;i++){
		printf("%c",s[i]);
	}
	printf(" ");
	for(i=14;i<=18;i++){
		printf("%c",s[i]);
	}
	printf("\n");
	return 0;
}

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

int main()
{
	string s;
	cin >> s;
	vector<int> vec;
	for(int i = 0; i < s.size(); i++)
	{
		if(s[i] == '1') vec.push_back(1);
		if(s[i] == '0')	vec.push_back(0);
		if(s[i] == 'B')
		{
			if(vec.size())
				vec.pop_back();
		}
	}
	for(const auto a: vec)
		cout << a;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 305, mod = 998244353;
int n, dp[MX][MX][MX];
ll fac[2 * MX], inv[2 * MX], res = 1;
string s;

ll pot (ll b, int p) {
	ll res = 1;
	while (p) {
		if (p & 1) (res *= b) %= mod;
		(b *= b) %= mod;
		p /= 2;
	}
	return res;
}

ll comb (int n, int k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

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

	fac[0] = inv[0] = 1;
	for (int i = 1; i < 2 * MX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = pot(fac[i], mod - 2);
	}

	cin >> s;
	n = s.size();
	
	dp[0][0][0] = 1;

	forn (i, n) forn (j, n) forn (k, n) if (dp[i][j][k]) {
		if (i + 1 < n) {
			if (s[i] == '0' || s[i + 1] == '0') dp[i + 2][j + 1][k] = 1;
			if (s[i] == '1' || s[i + 1] == '1') dp[i + 2][j][k + 1] = 1;
			dp[i + 1][j][k] = 1;
		}

		if (j || k) dp[i + 1][j][k] = 1;
		if (j && s[i] == '1') dp[i + 1][j - 1][k + 1] = 1;
		if (k && s[i] == '0') dp[i + 1][j + 1][k - 1] = 1;
	}

	for (int i = n - 1, x = 0, y = 0; i >= 0; i--) {
		if (s[i] == '0') y++;
		else x++;

		forn (j, n) forn (k, n) if (dp[i + 1][j][k]) {
			ll a = !j && !x ? 1 : comb(j + x - 1, j);
			ll b = !k && !y ? 1 : comb(k + y - 1, k);
			(res += a * b) %= mod;
		}
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 31588
#include <bits/stdc++.h>
using namespace std;
int n,a[100005];

int main(){
  cin>>n;
  for(int i=0,s,t;i<n;i++)cin>>s>>t,a[s-1]++,a[t]--;
  int ans=0;
  for(int i=1;i<=n;i++){
    a[i]+=a[i-1];
    if(i<=a[i]) ans=max(i,ans);
  }
  cout <<ans<<endl;
  return 0;
}

Measured memory_bytes: 1548
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

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

int main(){
	long a,b,res=1;
	cin >> a >> b;
	long max_div = gcd(a,b);
	long root_div = sqrt(max_div);
	for(int i=2;i<=root_div;++i){
		if(max_div%i == 0){
			while(max_div%i==0)max_div /= i;
			res++;
		}
	}
	if(max_div!=1)res++;
	cout << res << endl;
}

Measured memory_bytes: 256
l=[i for i in range(2,14)]
l.append(1)
a,b=map(int,input().split())
if a==b:
    print('Draw')
else: 
    ind1=l.index(a)
    ind2=l.index(b)
    if ind1<ind2:
        print('Bob')
    else:
        print('Alice')

Measured memory_bytes: 38384