akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct node {
	int deg;
	int parent;
	int depth;
	vector<int> child;
};

vector<node> tree;

void update_depth(int ind, int d) {
	tree[ind].depth = d;
	for (int i = 0; i < tree[ind].deg; ++i) {
		update_depth(tree[ind].child[i],d+1);
	}
	return;
}

int main(void) {
	int n;
	cin >> n;
	tree = vector<node>(n);
	for (int i = 0; i < n; ++i) {
		tree[i].parent = -1;
	}
	int temp;
	for (int i = 0; i < n; ++i) {
		cin >> temp;
		cin >> tree[temp].deg;
		tree[temp].child = vector<int>(tree[temp].deg);
		for (int j = 0; j < tree[temp].deg; ++j) {
			cin >> tree[temp].child[j];
			tree[tree[temp].child[j]].parent = temp;
		}
	}
	int root;
	for (int i = 0; i < n; ++i) {
		if (tree[i].parent < 0) {
			root = i;
			break;
		}
	}
	update_depth(root,0);

	for (int i = 0; i < n; ++i) {
		cout << "node " << i;
		cout << ": parent = " << tree[i].parent;
		cout << ", depth = " << tree[i].depth;
		if (tree[i].parent < 0) {
			cout << ", root, [";
		}
		else {
			if (tree[i].deg > 0) {
				cout << ", internal node, [";
			}
			else {
				cout << ", leaf, [";
			}
		}
		for (int j = 0; j < tree[i].deg; ++j) {
			cout << tree[i].child[j];
			if (j < tree[i].deg-1) {
				cout << ", ";
			}
		}
		cout << "]" << endl;
	}
	return 0;
}



Measured memory_bytes: 10684
# python3
import sys

input = sys.stdin.readline


def main():
    # 2 <= N <= pow(10,5), 1 <= K <= 100
    N, K = [int(ele) for ele in input().split()]
    h = [Node(int(ele)) for ele in input().split()]

    for idx, n in enumerate(h):
        s = max(0, idx - K)
        n.parents = h[s:idx]
        n.cal_dp()

    print(h[-1].dp_val)


class Node():

    def __init__(self, val):
        self.val = val
        self.dp_val = 1000000000000
        self.parents = []

    def cal_dp(self):
        if self.parents == []:
            self.dp_val = 0
            return

        for n in self.parents:
            self.dp_val = min(self.dp_val, abs(n.val - self.val)+n.dp_val)


if __name__ == '__main__':
    main()


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

int main(){
	int N;
	cin >> N;
	vector<ll> X(N);
	vector<pll> Y(N), Z(N);
	REP(i, N) cin >> X[i];
	REP(i, N){
		Y[i] = make_pair(X[i], (ll)i);
	}
	sort(Y.begin(), Y.end());
	REP(i, N){
		Z[i] = make_pair(Y[i].second, (ll)i);
	}
	sort(Z.begin(), Z.end());
	/*
	REP(i, N){
		cout << Y[i].first << " " << Y[i].second << endl;
	}
	cout << endl;
	REP(i, N){
		cout << Z[i].first << " " << Z[i].second << endl;
	}
	cout << endl;
	*/
	REP(i, N){
		cout << (Z[i].second < N/2 ? Y[N/2].first : Y[(N-1)/2].first ) << endl;
	}

    return 0;
}

Measured memory_bytes: 9984
//k_k_dubey_
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
#define inf 999999999999
#define mx 200005
#define gcd __gcd
#define pb push_back
#define mk make_pair
#define bs binary_search
#define ub upper_bound
#define lb lower_bound
#define endl "\n"
#define vl vector<ll>
#define vs vector<string>
#define non __builtin_popcount
#define ml map<ll, ll> 
#define ms map<string , ll> 
using namespace std;

bool isp[mx];

void sv(){

	ll i,j;
	memset(isp, true, sizeof(isp));
	
	isp[1]= false;
	for(i=2;i*i<mx;i++){
		if(isp[i]){
			for(j=i*i;j<mx;j+=i)
			isp[j]= false;
		}
	}
}

ll powr(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1)res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	//sv();
	
	ll n,k,i,j;
	cin>>n>>k;
	ll ans;
	if(k==1)
	ans= 0;
	else{
	    ans= n-k;
	}
	cout<<ans;
    return 0;
}























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

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

  for (int i = 0; i < N.size(); i++) {
    if (N.substr(i, 1) == "7") {
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
#define int long long
using namespace std;
typedef pair<int,int>P;
int n,sum,ans;
vector<P>v;
signed main(){
	cin>>n;
	int dp[n+1];
	r(i,n+1)dp[i]=1e16;
	r(i,n){
		int a,b;
		cin>>a>>b;
		v.push_back(P(b,a));
	}
	sort(v.begin(),v.end());
	dp[0]=0;
	r(i,n){
		int b=v[i].first;
		int a=v[i].second;
		for(int j=i;j>=0;j--)
			if(dp[j]+a<=b) dp[j+1]=min(dp[j+1],dp[j]+a);
	}
	for(int i=n;i>=0;i--)
		if(dp[i]!=1e16){
			cout<<i<<endl;
			return 0;
		}
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
int main(){
  int k, n, x = 0, y = 0, m = 0;
  cin >> k >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++){
  	cin >> a.at(i);
  }
  sort(a.begin(), a.end());
  for(int i = 1; i < n; i++){
  	x += a.at(i) - a.at(i-1);
  	if(a.at(i) - a.at(i-1) > m) m = a.at(i) - a.at(i-1);
  }
  if(m < a.at(0)+k-a.at(n-1)) m = a.at(0)+k-a.at(n-1);

  cout << k-m << endl;

}

Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

int main(){
    int n, k;
    cin >> n >> k;
    int d[k];
    int ans[n];
    for (int i=0; i<n; i++){
        ans[i] = 0;
    }
    int sum = 0;
    int a[100][100];
    for (int i=0; i<100; i++){
        for (int j=0; j<100; j++){
            a[i][j] = 0;
        }
    }
    for (int i=0; i<k; i++){
        cin >> d[i];
        for (int j=0; j<d[i]; j++){
            cin >> a[i][j];
            if (ans[a[i][j]-1]==0){
                sum += 1;
                ans[a[i][j]-1] += 1;
            }
        }
    }
    cout << n-sum << endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define print(x) cerr << (#x) << "is "<< x << "\n"
using ll = long long;
using pii = pair<int,int>;
const int MOD = 1e9+7, N = 1e5 + 10;

void test();

int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,t;
    cin >> a >> b >> t;
    int ans = ((int)(t+0.5)/a)*b;
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n); for(int i = 0;i < (int)(n);i++)
#define all(x) (x).begin(),(x).end()
typedef long long ll;
int main(){
    int n,k;
    cin >> n >> k;
    int x[n];
    rep(i,n)cin >> x[i];
    int ans = 0;
    rep(i,n){
        int kyori = min(x[i],k-x[i]);
        ans += kyori;
    }
    cout << 2*ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

#define MAX 100005
#define NIL -1

typedef struct { int p, l, r;} Node;

Node T[MAX];
int n, D[MAX];

void print(int u) {
  int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",D[u]);

  if( T[u].p == NIL ) printf("root, ");
  else if( T[u].l == NIL ) printf("leaf, ");
  else printf("internal node, ");

  printf("[");

  for(i=0, c=T[u].l; c != NIL; i++, c=T[c].r) {
    if(i) printf(", ");
    printf("%d",c);
  }
  printf("]\n");
}

void rec(int u, int p) {
  D[u] = p;
  if(T[u].r != NIL) rec(T[u].r,p);
  if(T[u].l != NIL) rec(T[u].l,p+1);
}

int main(void) {
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i=0;i<n;i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i=0;i<n;i++) {
    scanf("%d %d",&v,&d);
    for(j=0;j<d;j++) {
      scanf("%d",&c);
      if(j==0) T[v].l=c;
      else T[l].r =c;
      l = c;
      T[c].p = v;
    }
  }
  for(i=0;i<n;i++) {
    if(T[i].p == NIL) r = i;
  }
  
  rec(r,0);
  
  for(i=0;i<n;i++) print(i);
  
  return 0;
}


Measured memory_bytes: 6420
n, x = map(int, input().split())
def f(a, b):
    if (a > b):
        a, b = b, a
    if b % a == 0:
        return (b // a * 2 - 1) * a
    return b // a * 2 * a + f(b % a, a)

print(n + f(x, n - x))


Measured memory_bytes: 3060
n,a,b = map(int,input().split())

mod = 10**9+7
total = pow(2,n,mod) - 1 # 制約なしの全パターン_n**2-1※'-1'は0本の花束

# n個からr個を選択した時のパターン総数_組み合わせ重複なし
# n! / (r! * (n-r)!) → nが大き過ぎて出来ない →変形→ n*(n-1)*･･･(n-r+1)/r! ↓関数化
def nCr(n, r, mod):
    numerator=1 #分子_n*(n-1)*･･･(n-r+1)
    for i in range(n-r+1, n+1):
        numerator = (numerator*i) % mod

    denominator=1 #分母_r!
    for j in range(1,r+1):
        denominator = (denominator*j) % mod
    # 剰余の計算において割るとよくない → 割るのではなく逆元を掛ける
    # フェルマーの小定理_pが素数なら整数aのmod pにおける逆元は a**(p-2) ※aとpは互いに素
    return (numerator * pow(denominator,mod-2,mod)) % mod
    
ans = (total - nCr(n,a,mod) - nCr(n,b,mod)) % mod
print(ans)

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

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

    static class C {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int n = Integer.parseInt(in.next());
            // 出現する頭文字の回数
            long[] ins = new long[5];
            for (int i = 0; i < n; i++) {
                String tmp = in.next();
                if (tmp.startsWith("M")) ins[0]++;
                if (tmp.startsWith("A")) ins[1]++;
                if (tmp.startsWith("R")) ins[2]++;
                if (tmp.startsWith("C")) ins[3]++;
                if (tmp.startsWith("H")) ins[4]++;
            }
            long ans = 0;
            // ありうるMARCHの組合せ
            int[] c1 = {0, 0, 0, 0, 0, 0, 1, 1, 1, 2};
            int[] c2 = {1, 1, 1, 2, 2, 3, 2, 2, 3, 3};
            int[] c3 = {2, 3, 4, 3, 4, 4, 3, 4, 4, 4};

            for (int i = 0; i < 10; i++) {
                ans += ins[c1[i]] * ins[c2[i]] * ins[c3[i]];
            }

            // 出力
            out.println(ans);

        }

    }
}



Measured memory_bytes: 58224
#include<iostream>
using namespace std;
int main() {
  int N;
  cin >> N;
  double x, ans = 0;
  string u;
  for (int i = 0;i < N;++ i) {
    cin >> x >> u;
    ans += (u == "JPY" ? 1 : 380000) * x;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 256
N, M, L = map(int,input().split())
A = []
B = []

for n in range(N):
    A.append(list(map(int, input().split())))
for m in range(M):
    B.append(list(map(int, input().split())))

C = []
for n in range(N):
    tmp = []
    for l in range(L):
        total = 0
        for m in range(M):
            total += A[n][m] * B[m][l]
        tmp.append(total)
    C.append(tmp)

for c in C:
    str_c = [str(s) for s in c]
    str_c = " ".join(str_c)
    print(str_c)



Measured memory_bytes: 6912
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>

using namespace std;

double EPS = 1e-10;
const double PI = acos(-1);

double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}

struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}

  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }

  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }

  point operator * (double d){
    return point(x*d,y*d);
  }

  point operator / (double d){
    return point(x/d,y/d);
  }
  
  bool operator == ( const point &p ) const {
    return fabs(x-p.x) < EPS && fabs(y-p.y) < EPS;
  }
};

double areaPol(vector<point> t){
  t.push_back(t[0]);
  int tsz=t.size();
  double area=0;
  for(int i=0;i<tsz-1;i++){
    area+=(t[i].x-t[i+1].x)*(t[i].y+t[i+1].y);
  }
  return abs(area)/2.0;
}

int main(void){
  point p;
  vector<point>t;
  double x,y;
  char k;

  while(cin>>x>>k>>y){
    p.x = x;
    p.y = y;
    t.push_back(p);
 }

  printf("%.6f\n",areaPol(t));

  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<algorithm>
#include<vector>
#include <queue>
#include<map>
using namespace std;
int main() 
{
	long long int k; 
	cin >> k;
	int ans = 1;
	for (int mod = 7; mod % k; mod = (mod * 10 + 7) % k)
	{
		if (++ans > k)
		{
			ans = -1;
			break;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3636
n,m=map(int,input().split())
o,f,i=998244353,[1],1
while i<3*m+n:f+=[f[-1]*i%o];i+=1
c=lambda x,y=n-1:f[x]*pow(f[x-y]*f[y],o-2,o)
a=c(-1)-n*c(n+m-2)
while~-n>m<i-n:m+=2;a-=c(n,m)*c(n-1+i-m>>1)
print(a%o)

Measured memory_bytes: 149968
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		try(Scanner sc = new Scanner(System.in)) {

			int n = sc.nextInt();
			
			int[] orders = new int[n];
			
			for(int i = 0 ; i < n ; i++ ) {
				int order = sc.nextInt();
				orders[order-1] = i+1;
			}
			
			for(int i = 0 ; i < n ; i++ ) {
				if ( i > 0 ) {
					System.out.print(" ");
				}
				System.out.print(orders[i]);
			}
		}
	}
}


Measured memory_bytes: 66844
#include <iostream>

using namespace std;

int main(){

	int a,b,c,d,e;
    
    cin >> a >> b >> c >> d >> e;
    
    if(c - e < 0 | d - e < 0){
        cout << "No" << endl;
        return 0;
    }else if(c + e > a | d + e > b){
        cout << "No" << endl;
        return 0;
    }
    
    cout << "Yes" << endl;
    
    return 0;

}

Measured memory_bytes: 3104
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

// const int maxn = 
// const int mo = 1e9 + 7;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int a, b;
	cin >> a >> b;
	cout << (a*3 + b) / 2 << endl;

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<string>
#include<utility>
#include<queue>
#include<deque>
#include<tuple>
#include<stdio.h>
#include<iomanip>
#define rep(i, n) for(int i=0;i<n;i++)
using namespace std;

int main(){
	int x, n;
	cin>>x>>n;
	vector<int> v;
	int a, b=x, f=0;
	for(int i=0;i<=x*2;i++){
		v.push_back(i);
	}
	rep(i, n){
		cin>>a;
		rep(i, v.size()){
			if(v[i]==a){
				v.erase(v.begin()+i);
			}	
		}
	}
	sort(v.begin(), v.end());
	rep(i, v.size()){
		if(b>abs(x-v[i])){
			b=abs(x-v[i]);
			if(x-v[i]>0)
				f=0;
			else
				f=1;
		}
	}
	if(f==0)
		cout<<x-b<<endl;
	else
		cout<<x+b<<endl;
	return 0;
}

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int N,M,Q;
long long maxi = 0;
vector<int> a,b,c,d;
void dfs(vector<int>& A,int n,int idx) {
  if(idx == N) {
    long long sum = 0;
    for(int i = 0;i < Q;i++) {
      if(A[b[i]]-A[a[i]] == c[i]) sum += d[i];
    }
    maxi = max(maxi,sum);
  }else {
    A[idx] = n;
    for(int i = n;i <= M;i++) dfs(A,i,idx+1);
    A[idx] = 0;
  }
}


int main() {
  
  
  cin >> N >> M >> Q;

  vector<int> A(N);
  a.assign(Q,0);
  b.assign(Q,0);
  c.assign(Q,0);
  d.assign(Q,0);
  for(int i = 0;i < Q;i++) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    a[i]--;
    b[i]--;
  }

  dfs(A,1,0);
  cout << maxi << endl;


}


Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define INF 1000000000000
#define MOD 1000000007LL
#define RANGE(a,b,c) (a).begin()+(b),(a).begin()+(c) // [b,c) イテレータ
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;
typedef int64_t i64;

VI len, numP;

i64 f(i64 n, i64 x){
    if (n == 0)
        return ((x <= 0) ? 0 : 1);
    else if (x <= 1 + len[n - 1])
        return f(n - 1, x - 1);
    else 
        return numP[n - 1] + 1 + f(n - 1, x - 2 - len[n - 1]);
}

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

i64 N, X; cin >> N >> X;

len.assign(N+1, 1);
numP.assign(N+1, 1);

rep(i, 1, N+1){
    len[i] = 2 * len[i - 1] + 3;
    numP[i] = 2 * numP[i - 1] + 1;
}

cout << f(N, X) << endl;

}
// 書いて考える．場合分け
// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．求めたい量の変域．動かせる量．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 代数的処理．前処理によるクエリ高速化．
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり
// 実行エラー：vector添え字超え．0割り．



Measured memory_bytes: 256
calc :: Integer -> Integer -> Integer
calc n l
    | 0 < l = (n - 1) * (2 * l + n) `div` 2
    | l < (1 - n) = (n - 1) * (2 * l + n - 2) `div` 2
    | otherwise = n * (2 * l + n - 1) `div` 2

main = do
  n:l:_ <- map (read :: String -> Integer) . words <$> getLine
  putStrLn . show $ calc n l


Measured memory_bytes: 508
#include <bits/stdc++.h>
#include <climits>
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define srep(i, begin, end) for (__typeof(end) i = begin; i != end; i++)
#define si(x) int x = scanInt();
#define sll(x) LL x = scanLong();
#define sci(x) int x; scanf("%d", &x);
#define scll(x) LL x; scanf("%lld", &x);
#define pi(x) printf("%d ", x)
#define pll(x) printf("%lld ", x)
#define ps(x) printf("%s", x)
#define nl printf("\n")
#define clr(a) memset(a, 0, sizeof(a))
#define PB push_back
#define MP make_pair
using namespace std;
typedef unsigned int UI; // 32 bit integer
typedef long int LI; // 32 bit integer
typedef unsigned long int ULI; // 32 bit unsigned integer
typedef long long int LL; // 64 bit integer
typedef unsigned long long int  ULL; // 64 bit unsigned integer
typedef long double LD;
typedef vector<int> VI;
typedef vector<LL> VLL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
LL mod = 1e9+7;

/* Fast I/O */
inline int scanInt() {
	int n = 0;
	char ch = getchar();
	int sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(int)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

inline LL scanLong() {
	LL n = 0;
	char ch = getchar();
	LL sign = 1;
	while(ch < '0' || ch > '9') {
		if(ch == '-')	sign = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		n = (n<<1)+(n<<3)+(LL)(ch-'0');
		ch = getchar();
	}
	return n*sign;
}

const LL MAXN = 2e5+10;	
LL arr[MAXN], cnt[MAXN], present[MAXN];

int main() {
	sll(n); sll(m);
	rep(i, 0, n) {
		arr[i] = scanLong();
		cnt[arr[i]]++;
	}
	rep(i, 1, n+1) {
		LL low = max(0ll, i - cnt[i]);
		rep(j, low, i)	present[j]++;
	}
	LL ans = 0;
	rep(i, 0, n)	if(!present[i])	ans++;
	rep(i, 0, m) {
		sll(x); sll(y); x--;
		if(y != arr[x]) {
			if(y > cnt[y]) {
				if(present[y-cnt[y]-1] == 0)	ans--;
				present[y-cnt[y]-1]++;
			}
			if(arr[x] >= cnt[arr[x]]) {
				if(present[arr[x]-cnt[arr[x]]] == 1)	ans++;
				present[arr[x]-cnt[arr[x]]]--;
			}
			cnt[arr[x]]--;
			cnt[y]++;
			arr[x] = y;
		}
		pll(ans); nl;
	}
}


Measured memory_bytes: 6272
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>
#include <fstream>
#include <bitset>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef complex<double> Point;

#define PI acos(-1.0)
#define EPS 1e-10
const ll INF = 1e9 + 7;
const ll MOD = 1e9 + 7;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
#define EQV(a,b) ( EQ((a).real(), (b).real()) && EQ((a).imag(), (b).imag()) )
#define fi first
#define se second

int n, ma, mb;
int a[100], b[100], c[100];

int dp[1010][1010];

int main(){
	cin >> n >> ma >> mb;
	REP(i, n){
		cin >> a[i] >> b[i] >> c[i];
	}
	REP(i, 1010)REP(j, 1010)dp[i][j] = INF;
	dp[0][0] = 0;
	REP(i, n){
		for (int j = 1010 - 1; j >= 0;j--){
			for (int k = 1010 - 1; k >= 0;k--){
				if (j + a[i] < 1010 && k + b[i] < 1010){
					if (dp[j][k] != INF){
						dp[j + a[i]][k + b[i]] = min(dp[j][k] + c[i], dp[j + a[i]][k + b[i]]);
					}
				}
			}
		}
	}
	//REP(i, 20){
	//	REP(j, 20){
	//		cout << dp[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	int buf1 = ma, buf2 = mb;
	int ans = INF;
	while (ma < 1010 && mb < 1010){
		ans = min(ans, dp[ma][mb]);
		ma += buf1;
		mb += buf2;
	}
	if (ans == INF)cout << -1 << endl;
	else cout << ans << endl;
}

Measured memory_bytes: 4224
#include <bits/stdc++.h>
#pragma GCC optimize ("O2,unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> pi3;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) {cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;}
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod=1000000007;
const int N=18;

ll n, nn, k, u, v, x, y, a, b, ans;
ll A[1<<N];
int sz[4];
pi3 B[4][N*N<<N>>3];
pii C[4][N*N<<N>>3];
int L[4][1<<N], R[4][1<<N], ted[4][1<<N];
int sum[4][1<<N];

inline void fix(int &x){
	if (x>=mod) x-=mod;
	if (x<0) x+=mod;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n; nn=(1<<(n-1));
	for (int i=0; i<nn; i++){
		cin>>A[i];
		int u=i+nn, v=A[i]+nn-1;
		ll mul=1;
		while (u>1){
			mul=mul*u%mod;
			int vv=v;
			ll mul2=mul;
			while (vv>1){
				mul2=mul2*vv%mod;
				int tmp=((u&1)<<1)|(vv&1);
				B[tmp][sz[tmp]++]={{u>>1, vv>>1}, mul2};
//				cerr<<"path "<<(u>>1)<<' '<<(vv>>1)<<' '<<tmp<<" "<<mul2<<"\n";
				ted[tmp][u>>1]++;
				vv>>=1;
			}
			u>>=1;
		}
	}
	for (int tmp:{0, 1, 2, 3}){
		for (int i=1; i<(1<<n); i++) L[tmp][i]=R[tmp][i]=L[tmp][i-1]+ted[tmp][i-1];
	}
	for (int tmp:{0, 1, 2, 3}){
		for (int i=0; i<sz[tmp]; i++){
			int u=B[tmp][i].first.first, v=B[tmp][i].first.second, mul=B[tmp][i].second;
			C[tmp][R[tmp][u]++]={v, mul};
		}
	}
	for (int u=1; u<(1<<n); u++){
		for (int tmp:{0, 1, 2, 3}){
			for (int i=L[tmp][u]; i<R[tmp][u]; i++){
				pii p=C[tmp][i];
				fix(sum[tmp][p.first]+=p.second);
			}
		}
		for (int tmp:{0, 1, 2, 3}){
			for (int i=L[tmp][u]; i<R[tmp][u]; i++){
				int v=C[tmp][i].first, mul=C[tmp][i].second;
//				cerr<<"cycle "<<u<<' '<<v<<' '<<tmp<<"  "<<mul<<' '<<sum[tmp^3][v]<<"\n";
				ans=(ans + 1ll*sum[tmp^3][v]*mul%mod*v%mod*u%mod)%mod;
			}
		}
		for (int tmp:{0, 1, 2, 3}){
			for (int i=L[tmp][u]; i<R[tmp][u]; i++){
				pii p=C[tmp][i];
				sum[tmp][p.first]=0;
			}
		}
		
	}
	ans%=mod;
	ans=ans*(mod+1)/2%mod;
	cout<<ans<<"\n";
	
	
	return 0;
}


Measured memory_bytes: 756768
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <limits.h>

using namespace std;

typedef long long int ll;

int main() {
  int n, m;
  cin >> n >> m;
  const ll max_dist = (ll)(1000000000) * (ll)(m) + (ll)(1);
  vector<pair<ll, int>> vertexes(n);  //距離と自分の一つ前の点
  struct edge{
    int start;
    int end;
    ll cost;
  };
  vector<edge> edges(m);  //始点，終点，コスト
  for(int i = 0; i < m; i++)
  {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    edges[i] = {a - 1, b - 1, -c};
  }
  vertexes[0] = {0, 0};
  for(int i = 1; i < n; i++)
  {
    vertexes[i] = {max_dist, -1};
  }
  for(int i = 0; i < 2*n; i++)
  {
    for(auto e : edges)
    {
      if(vertexes[e.end].first > vertexes[e.start].first + e.cost && vertexes[e.start].first != max_dist)
      {
        vertexes[e.end].first = vertexes[e.start].first + e.cost;
        vertexes[e.end].second = e.start;
        if(i >= n - 1 && e.end == n - 1){
          cout << "inf" << endl;
          return 0;
        }
      }
    }
  }
  ///スコアの算出
  cout << (-1) * vertexes[n - 1].first << endl;
  return 0;
}


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

int main(){
  int n;
  cin >> n;
  ll a[n];
   map<ll,int> m; 
  rep(i,n) {
    cin >> a[i];
    m[a[i]]++;
  }
  sort(a,a+n,greater<ll>());
  int ans = 0;
  rep(i,n) {
    for(int j = 31; j >= 0; j--){
      ll c = (1<<j) - a[i];
      if(c == a[i]) {
        if(m[c] >= 2) {
          ans++;
          m[c] -= 2;
        }
      } else if(c > 0 && m[c] >= 1 && m[a[i]] >= 1) {
        ans++;
        m[c]--; m[a[i]]--;
        continue;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 45312
while True:
    s = input()
    if s == '.':break
    while True:
        if s.find('+') == -1 and s.find('-') == -1:
            index = s.rfind('[')
            if index == -1:
                break
            e = s[index:].find(']')
            s = s[:index] + s[index + 1:index + e][::-1] + s[index + e + 1:]
        else:
            if s.find('+') != -1:
                index = s.find('+')
            if s.find('-') != -1:
                if s.find('+') != -1:
                    index = min(index, s.find('-'))
                else:
                    index = s.find('-')
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                if s[e] == '+':
                    f += 1
                else:
                    f -= 1
                e += 1
            r = s[e]
            if r != '?':
                r = chr((ord(r) - ord('A') + f) % 26 + ord('A'))
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?', 'A'))


Measured memory_bytes: 5572
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<random>
using namespace std;

class Dice{
  public:
    vector<int> n;
    int top;
    Dice(){
      n.resize(6);
      top = 0;
    }
    void roll(char c){
      int tmp = n[0];
      if( c == 'E' ){
        n[0] = n[3];
        n[3] = n[5];
        n[5] = n[2];
        n[2] = tmp;
      }else if( c == 'W' ){
        n[0] = n[2];
        n[2] = n[5];
        n[5] = n[3];
        n[3] = tmp;
      }else if( c == 'N' ){
        n[0] = n[1];
        n[1] = n[5];
        n[5] = n[4];
        n[4] = tmp;
      }else if( c == 'S' ){
        n[0] = n[4];
        n[4] = n[5];
        n[5] = n[1];
        n[1] = tmp;
      }else if( c == 'R' ){
        tmp = n[4];
        n[4] = n[3];
        n[3] = n[1];
        n[1] = n[2];
        n[2] = tmp;
      }else if( c == 'L' ){
        tmp = n[4];
        n[4] = n[2];
        n[2] = n[1];
        n[1] = n[3];
        n[3] = tmp;
      }

      // cerr << " " << n[0] << endl;
    }
    void input(){
      for(int i=0; i<6; i++) cin >> n[i];
    }
    // void input_top_and_before(){
    //   int a, b;
    //   cin >> a >> b;
    //   q2(a, b);
    // }
    //
    // void q2(int a, int b){
    //   vector<int> tmp = n;
    //   for(int i=0; i<tmp.size(); i++){
    //     if( tmp[i] == a ){
    //
    //     }
    //   }
    // }

    void output_top(){
      cout << n[top] << endl;
    }
};

int main(){
  random_device rnd;
  // std::mt19937 mt(rnd());
  // std::uniform_int_distribution<> rand6(0, 5);

  string con = "NSEW";
  Dice d;
  d.input();
  // string s;
  // cin >> s;
  // for(int i=0; i<s.size(); i++) d.roll(s[i]);
  Dice d2;
  d2.input();

  int cnt = 0;
  while(true){
    if( cnt >= 1000 ) break;
    d2.roll( con[rnd()%4] );
    if( d.n[0] == d2.n[0] ){
      if( d.n[5] != d2.n[5] ) break;

      for(int i=0; i<4; i++){
        d2.roll('R');
        bool f = true;
        for(int i=1; i<5; i++){
          if( d.n[i] != d2.n[i] ) f = false;
        }
        if( f ){
          cout << "Yes" << endl;
          return 0;
        }
      }

      break;
    }
    cnt++;
  }
  cout << "No" << endl;

  // d.output_top();

  return 0;
}





// EOF

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

#define rep(i, n) for(int i = 0; i < (n); ++i)

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

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

    int N = S.size();
    
    int ans = N / 2;
    rep(i, N) {
        if (S[i] == 'p') ans--;
    }

    cout << ans << endl;
}

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

//使用する変数の宣言と初期化
double N,result;

int main()
{
  cin >> N;

  if(int(N)%2==0){
    result = 0.5;
  }
  else{
    result = (N+1.0)/2.0/N;
  } 
  
  cout << result;
    
  return 0;
}

Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void scan(T...)(ref T a) {
    string[] ss = readln.split;
    foreach (i, t; T) a[i] = ss[i].to!t;
}
T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void main() {
    string s = read!string;
    int n = 0;
    foreach (c; s) {
        if (c == 'o') n++;
    }

    auto m = 15 - s.length;
    if (n + m >= 8) writeln("YES");
    else writeln("NO");
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

signed main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int N, K;
	string S;

	cin >> N >> K >> S;
	S[K - 1] = 'a' + (S[K - 1]-'A');

	cout << S << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;

int main() 
{
	int n, m, ptr = 1;
	cin >> n >> m;
	int a[m + 1], ans[n + 1] = {};
	for (int i = 1; i <= m; i++) cin >> a[i];
	
	ans[0] = 1;
	if (ptr <= m && a[ptr] == 1) ptr++;
	else ans[1] = 1;
		
	for (int i = 2; i <= n; i++)
	{
		if (ptr <= m && a[ptr] == i) ptr++;
		else ans[i] = (ans[i - 1] + ans[i - 2]) % mod;
	}
	
	cout << ans[n];
}

Measured memory_bytes: 1024
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    s,p = map(int, input().split())
    n = input().rstrip()
    n = n[::-1]

    if p == 2 or p == 5:
        res = 0
        for i in range(s):
            a = int(n[i])
            if a%p == 0:
                res += s-i
        print(res)
    else:
        res = [0]*p
        res[0] += 1
        b = 1
        c = 0
        for i in range(s):
            a = int(n[i])
            c += a*b
            c %= p
            res[c] += 1
            b = b*10%p
        ans = 0
        for i in res:
            if i>=2:
                ans += i*(i-1)//2
        print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3876
// *
// *
// *  Created By : Pritish Thakkar 
// *  Hackerrank : ma5terdrag0n
// *  CodeChef : solo_loser
// *  Hackerearth : pritish9
// *------------------------------------
// *  OS : Ubuntu 16.04
// *  Language : CPP14
// *  Editor : Sublime Text 3
// *  C++ compiler : g++
// *
// *
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define inf 1000000007
#define fr first
#define sc second
#define eps 1e-9
#define clr(a) memset(a, 0, sizeof(a))
#define sz(x) x.size()
#define sni(x) scanf("%d",&x)
#define snl(x) scanf("%lld", &x)
#define snc(x) scanf("%c", &c);
#define rep(n) for(int i = 0 ; i < n ;i ++)
#define repc(i, n) for(int i = 0 ; i < n ; i ++)
#define FOR(i, x, y) for(int i = x ; i < y ; i ++)
#define DEC(i, x, y) for(int i = x ; i >= y ; i --)
#define all(v) v.begin(), v.end()
#define min3(a, b, c) min(a, min(b,c))
#define max3(a, b, c) max(a, max(b, c))
#define alla(a, n) a, a+n
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;

bool isUpper(char c) {return (c >= 'A' && c <= 'Z');}
bool isLower(char c) {return (c >= 'a' && c <= 'z');}
bool iplpha(char c) {return (c >= 'A' && c <= 'Z')||(c >= 'a' && c <= 'z');}
bool isnum(char c){return (c >= '0' and c <= '9');}
bool isalnum(char c) {return (c >= 'A' && c <= 'Z')||(c >= 'a' && c <= 'z')||(c >= '0' && c <= '9');}
char toUpper(char c){return isUpper(c)?c:c-'a'+'A';}
char toLower(char c){return isLower(c)?c:c+'a'-'A';}
bool isvowel(char c){c = toLower(c); return (c == 'a' or c == 'e' or c == 'i' or c == 'i' or c == 'o' or c == 'u');}
template<typename t> t gcd(t a, t b){return ((b == 0) ? a : gcd(b, a%b));} 
template<typename t> t lcm(t a, t b){return (a * (b / gcd(a, b)));}
template <typename T> T modpow(T base, T exp, T modulus) {base %= modulus;T result = 1;while (exp > 0) {if (exp & 1) result = (result * base) % modulus;base = (base * base) % modulus;exp >>= 1;}return result;}
string toLowerCase(string s){rep(s.size()){if(!isLower(s[i])){s[i] = toLower(s[i]);}}return s;}
string toUpperCase(string s){rep(s.size()){s[i] = toUpper(s[i]);}return s;}
template<typename T> void cumulative(T *a, T *b, T n){rep(n){i ? b[i] = b[i-1] + a[i] : b[i] = a[i];}}
bool ispal(string s){ll lo, hi;lo = 0;hi = s.length()-1;while(lo <= hi){if(s[lo] != s[hi]){return 0;}lo++;--hi;}return 1;}
template<class T >string toString(T n){string v = "";while(n){v.pb(n % 10 + '0');n /= 10;}reverse(all(v));return v;}

//--------------------------------------------------------------------

ll fun(ll x){
    ll ret = 0;
    while(x > 0){
        ret += x % 10;
        x /= 10;
    }
    return ret;
}

void solve(){
   ll x, y;
   cin >> x>> y;
   ll ans = 0;
   while(x <= y){
    ans++;
    x += x;
   }
   cout << ans << endl;
}

int main(){
    std::ios::sync_with_stdio(0);
    // int start = clock();
    #ifdef ONLINE_JUDGE
    #else
//      freopen("input.in" , "r" , stdin);
      // freopen("output.txt", "w", stdout);
    #endif
    solve();
    // cout << n;
    // int stop = clock();
    // cout << (stop - start) / 1000.0000<< endl;
}












Measured memory_bytes: 256
program prob4
    implicit none
    integer(16)::N, M
    integer(16)::i,j,ans,com
    integer::v(17)
    read(*,*) N

    v = 0
    M = N
    do i = 16, 0, -1
        if(N >= 10**i) then
            v(i+1) = N/(10**i)
            N = N - N/(10**i) * 10**i
        end if
    end do

    if(M < 10) then
        write(*,*) M
    else
        do i = 17, 1, -1
            if(v(i) > 0)then
                j = i
                exit
            end if
        end do

        ans = v(j) - 1 + 9*(j-1)
        do i = 1,j-1
            if(v(i) < 9) then
                exit
            else if(i == j-1)then
                ans = ans + 1
            end if
        end do
        write(*,*) ans      
    end if

    stop
end program

Measured memory_bytes: 2828
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
	int d[32769]={0};
	int cnt=0;
	for(int i=0;i<183;i++){
		if(i*i*4>32768)break;
		
		for(int j=i;j<183;j++){
			if(i*i+j*j*3>32768)break;
			
			for(int k=j;k<183;k++){
				if(i*i+j*j+k*k*2>32768)break;
				
				for(int l=k;l<183;l++){
					if(i*i+j*j+k*k+l*l>32768)break;
					
					d[i*i+j*j+k*k+l*l]++;
					cnt++;
				}
			}
		}
	}
	//cout<<"#"<<cnt<<endl;
	
	
	
	int n;
	while(cin>>n,n){
		cout<<d[n]<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 1296
#include<stdio.h>
int main(){
  int A,B,max;
  scanf("%d%d", &A, &B);
  
  max = A+B ;
  if(max < 2*A-1) max = 2*A-1;
  if(max < 2*B-1) max = 2*B-1;
  printf ("%d\n", max);
  
  return 0;
}

Measured memory_bytes: 128
n = gets.to_i
l_n = gets.split.map(&:to_i)

ans = 0
(0...n-2).each do |i|
  (i+1...n-1).each do |j|
    (j+1...n).each do |k|
      if l_n[i] != l_n[j] && l_n[j] != l_n[k] && l_n[k] != l_n[i]
        hen = [l_n[i], l_n[j], l_n[k]].sort
        ans += 1 if hen[0] + hen[1] > hen[2]
      end
    end
  end
end
p ans

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

using namespace std;

#define ll long long
#define fix cout << fixed; cout << setprecision(0)





void solve() {

	int n;
	int m;
	cin >> n >> m;
	vector<int> v(n);
	double sum = 0;
	for(int i = 0; i < n; i++) {
		cin >> v[i];
		sum += v[i];
	}
	sort(v.begin(), v.end(), greater<int>());
	sum = sum / double(4 * m);
	for(int i = 0; i < m; i++) {
		if(v[i] < sum) {
			cout << "No\n";
			return;
		}
	}
	cout << "Yes\n";




	
}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	fix;
	solve();

	return 0;
}

Measured memory_bytes: 3580
(defun input (n)
  (let ((A (make-array n)))
    (loop for i below n do (setf (aref A i) (read)))
    A))

(defun func2 (n k A)
  (format t "~A " (aref A k))
  (cond
    ((>= k (- n 2)) (return-from func2))
    (t     (func2 n (+ k 2) A))))
(defun func1 (n k A)
  (format t "~A "(aref A k))
  (cond
    ((= k 0) (func2 n (if (oddp n) 1 2) A))
    ((= k 1) (func1 n 0 A))
    (t       (func1 n (- k 2) A))))

(let* ((n (read))
       (A (input n)))
  (cond
    ((= n 1) (princ (aref A 0)))
    ((= n 2) (format t "~A ~A" (aref A 1) (aref A 0)))
    (t       (func1 n (1- n) A))))

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

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

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

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 200000;

int N;
vector<int> gp[MAX_N+1];
int lv[MAX_N+1], p[MAX_N+1];

int c1, c2;

void dfs(int x){
	if(lv[x]%2)	c1++;
	else	c2++;
	for(int i : gp[x]){
		if(i==p[x])	continue;
		lv[i] = lv[x]+1;
		p[i] = x;
		dfs(i);
	}
}

vector<int> v1, v2, v3;


int main(){
	scanf("%d", &N);
	for(int i=1; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		gp[a].pb(b); gp[b].pb(a);
	}
	for(int i=1; i<=N; i++){
		if(i%3==1){
			v1.pb(i);
		}else if(i%3==2){
			v2.pb(i);
		}else{
			v3.pb(i);
		}
	}
	lv[1] = 1;
	dfs(1);
	if(c1>v1.size()+v3.size()){
		for(int i=1; i<=N; i++){
			if(lv[i]%2==1){
				if(!v1.empty()){
					printf("%d ", v1.back());
					v1.pop_back();
				}else if(!v2.empty()){
					printf("%d ", v2.back());
					v2.pop_back();
				}else{
					printf("%d ", v3.back());
					v3.pop_back();
				}
			}else{
				printf("%d ", v3.back());
				v3.pop_back();
			}
		}
		return 0;
	}else if(c2>v2.size()+v3.size()){
		for(int i=1; i<=N; i++){
			if(lv[i]%2==0){
				if(!v1.empty()){
					printf("%d ", v1.back());
					v1.pop_back();
				}else if(!v2.empty()){
					printf("%d ", v2.back());
					v2.pop_back();
				}else{
					printf("%d ", v3.back());
					v3.pop_back();
				}
			}else{
				printf("%d ", v3.back());
				v3.pop_back();
			}
		}
		return 0;
	}
	for(int i=1; i<=N; i++){
		if(lv[i]%2==1){
			if(!v1.empty()){
				printf("%d ", v1.back());
				v1.pop_back();
			}else{
				printf("%d ", v3.back());
				v3.pop_back();
			}
		}else{
			if(!v2.empty()){
				printf("%d ", v2.back());
				v2.pop_back();
			}else{
				printf("%d ", v3.back());
				v3.pop_back();
			}
		}
	}
	return 0;
}


Measured memory_bytes: 19832
import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int a, b, c; readV(a, b, c);
  writeln(min(b/a, c));
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
using VL = vector<ll>;
using VVL = vector<VL>;
using VVVL = vector<VVL>;
template<class T> using VE = vector<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -UPPER;
const long double pi = 3.141592653589793;
/*
string dfs(ll n, string s) {
	if (n == 0) return s;
	ll Base = 1;
	while (Base * 26 < n) {
		Base *= 26;
	}
	rep(i, 26) {
		ll num = (i + 1) * Base;
		char c = 'a' + i;
		char b = 'a' + i - 1;
		if (num == n) return s + c;
		else if (num > n) return dfs(n - (num - Base), s + b);
		else if (i == 25) return dfs(n - (num - Base), s + b);
	}
}
*/
const int N = 101010;
int main() {
	ll n;
	cin >> n;
	// nを26進数表記しろという問題
	string s = "";
	do {
		ll k = n % 26;
		k--;
		if (k < 0) k += 26, n -= 26;
		char c = 'a' + k;
		s.push_back(c);
		n /= 26;
	} while (n);
	reverse(all(s));
	cout << s << endl;
	return 0;
}

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

long even(long rec);
long odd(long rec);

int main(){
  long L;
  std::cin>>L;
  std::vector<long> rec(L);
  for (int i = 0; i < L; i++){
    std::cin>>rec[i];
  }
  std::vector<std::vector<long>> DP(L,std::vector<long>(5));
  for (int i = 0; i < L; i++){
    if(i == 0){
      DP[i][0] = rec[i];
      DP[i][1] = even(rec[i]);
      DP[i][2] = odd(rec[i]);
      DP[i][3] = even(rec[i]);
      DP[i][4] = rec[i];
    }else{
      DP[i][0] = DP[i-1][0] + rec[i];
      DP[i][1] = std::min(DP[i-1][0],DP[i-1][1]) + even(rec[i]);
      DP[i][2] = std::min({DP[i-1][0],DP[i-1][1],DP[i-1][2]}) + odd(rec[i]);
      DP[i][3] = std::min({DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3]}) + even(rec[i]);
      DP[i][4] = std::min({DP[i-1][0],DP[i-1][1],DP[i-1][2],DP[i-1][3],DP[i-1][4]}) + rec[i];
    }

  }
  long min = DP[L-1][0];
  for (int i = 1; i < 5; i++){
    if(DP[L-1][i] < min){
      min = DP[L-1][i];
    }
  }
  std::cout<<min<<std::endl;

  return 0;
}

long even(long rec){
  if(rec == 0){
    return 2;
  }else if(rec % 2 == 0){
    return 0;
  }else{
    return 1;
  }
}
long odd(long rec){
  if(rec % 2 == 1){
    return 0;
  }else{
    return 1;
  }
}


Measured memory_bytes: 15872
from math import ceil


def A(n, x, t):
  return ceil(n / x) * t


def B(n_str):
  s = 0
  for c in n_str:
    s += int(c)
  if s % 9 == 0:
    return 'Yes'
  return 'No'


def main():
  # n, x, t = map(int, input().split())
  # print(A(n, x, t))
  n_str = input()
  print(B(n_str))


if __name__ == '__main__':
  main()


Measured memory_bytes: 9336
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("-ffloat-store")
 
#define int  long long
#define rep(i,begin,end) for(__typeof(end)i=(begin)-((begin)>(end));i!=(end)-((begin)>(end));i+=1-2*((begin)>(end)))
#define F first
#define S second
#define sz(x) ((int)x.size())
#define pb push_back
#define pf push_front
#define eb emplace_back
#define all(v) (v).begin(), (v).end()
#define mod 1000000007
#define what_is(x) cerr << #x << " is " << x <<"\n";
#define sortA(v) sort(v.begin(), v.end())
#define sortD(v) sort(v.rbegin(), v.rend())
#define PI 3.14159265358979323846
#define vout(a) for(auto x:a) cout<<x<<" ";
#define INF 2000000000000000000 //1e16
 
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
 
 
// using namespace __gnu_pbds;
using namespace std;
 
using ll  = long long;
using vi  = vector<int>;
using vvi = vector<vi>;
using pii = pair<int,int>;
using vii = vector<pii>;
using mi  = multiset<int>;
using mii = multiset<pii>;
 
int lcm(int a,int b) {return (a*(b/__gcd(a,b)));}



void solve()
{
    int n,m,t,i,k,r,l,u,v,w,j,pos,sum=0,flag=0,count=0;
    string S,T; 
    int h;
    cin>>h>>w>>m;
    map<int,int> row,col;
    map<pii,int> cell;
    while(m--)
    {
        cin>>u>>v;
        row[u]++;
        col[v]++;
        cell[{u,v,}]++;
    }
    int ans=1;
    vi irow,icol;
    int mxr=0,mxc=0;
    for(auto x:row)
    {
        mxr=max(mxr,x.S);
    }
    for(auto x:col)
    {
        mxc=max(mxc,x.S);
    }
    for(auto x:row)
    {
        if(x.S==mxr) irow.pb(x.F); 
    }
    for(auto x:col)
    {
        if(x.S==mxc) icol.pb(x.F);
    }
    for(int u:irow)
    {
        for(int v:icol)
        {
            if(!cell[{u,v}])
            {
                cout<<mxr+mxc;
                return;
            }
        }
    }
    cout<<mxr+mxc-1;
}


signed main()
{
    #ifndef ONLINE_JUDGE 
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
    #endif
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();
        if(t)cout<<"\n";
    }
    return 0;
}

Measured memory_bytes: 67804
/*  ex9_2
    shu_t */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node{
    char elem;
    struct node *next;
} node;

//add data to stack
void push(node **first, char elem){
    //make memory
    node *new = calloc(1, sizeof(node));
    new->elem = elem;
    new->next = *first;
    *first = new;
}

//pop data from stack
void pop(node **first){
    node *tmp = *first;
    if(tmp == NULL){
        exit(1);
    }
    *first = tmp->next;
    //free memory
    free(tmp);
}

int main(void){
    char color[100001];//for input
    int ans = 0;//answer
    int i=0;//roop variable
    //first node
    node *first = NULL;
    //input string
    scanf("%s",color);
    
    for(i=0;i<strlen(color);i++){
        //add to stack
        push(&first, color[i]);
        //more than two cube and its color is different
        if((first->next != NULL) && (first->elem != first->next->elem)){
        //pop two data and count + 2
            pop(&first);
            pop(&first);
            ans += 2;
        }
    }
    //output the answer
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 4904