akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
#define _CRT_SECURE_NO_WARNINGS
#define rep(i,n) for(int i = 0;i < n;i++)
#define REP(i,n,k) for(int i = n;i < k;i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define Pi pair<int,int>
#define IINF 1e9
#define LINF 1e18
#define vi vector<int>
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 0, 1,0,-1};
int dy[] = { 1, 0,-1,0};
int dx8[] = { -1,-1,-1,0,0,1,1,1};
int dy8[] = { -1,0,1,-1,1,-1,0,1};

unsigned long long sttoi(std::string str) {
	unsigned long long ret;
	std::stringstream ss; ss << str;
	ss >> ret;
	return ret;
}

ull gcd(ull a, ull b) {
	if (b > a)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a%b);
}

int comb(int n, int k) {
	int ans = 1;
	for (int i = 0; i < min(k, n - k); i++) {
		ans *= n - i;
		ans /= i + 1;
	}
	return ans;
}

ll mod_pow(ll n,ll p,ll mod){	
	if (p == 0) return 1 % mod;
	if (p < 2) {
		return n % mod;
	}else {
		ll d = 2, value = (n%mod)*(n%mod)%mod;
		while (d*2 < p) { d *= 2;	value *= value;	value %= mod;}
		value %= mod;
		return ((value%mod) * (mod_pow(n, p - d, mod)%mod)) % mod;
	}
}

bool isPrime(int n) {
	if (n <= 1)return false;
	if (n == 2)return true;
	if (n % 2 == 0)return false;
	for (int i = 3; i*i <= n; i += 2) {
		if (n%i == 0)return false;
	}
	return true;
}

void solve() {
	int a, b;
	cin >> a >> b;
	if (a <= 0 && b >= 0) {
		P("Zero");
	}
	else if (a < 0 && b < 0) {
		P((abs(a - b) + 1) % 2 == 0 ? "Positive" : "Negative");
	}
	else if(a >= 0 && b >= 0){
		P("Positive");
	}
}

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

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#define dlog(str) cout << "====" << str << endl;
#else
#define dlog(str)
#endif
#define INF 999999999
#define MOD 1000000007
#define REP(i, n) for(int i = 0, i##_l = (n); i < i##_l; i++)
#define FOR(i, s, e) for(int i = s, i##_l = (e); i < i##_l; i++)
#define LLI long long int
#define _min(a,b) ((a<b)?a:b)
#define _max(a,b) ((a<b)?b:a)
#define chmax(a, b) a = _max(a, b)
#define chmin(a, b) a = _min(a, b)
#define bit(a, shift) ((a>>shift)&1))
#define pm(a) ((a)?1:-1)
#define SORT(v) sort(v.begin(),v.end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
// int 2.14E±9    lli 9.2E±18    double 1.7E±380

LLI power(LLI a, LLI b) { LLI res = 1; while (b > 0) { if (b & 1)res = res * a; a = a * a; b >>= 1; }return res; }

#define PAS_SIZE 60
LLI pas[PAS_SIZE][PAS_SIZE];
int main() {


	pas[0][0] = 1;
	for (int i = 1; i < PAS_SIZE; i++) {
		for (int j = 1; j < PAS_SIZE; j++) {
			pas[i][j] = pas[i - 1][j - 1] + pas[i - 1][j];
		}
	}




	cout << fixed << setprecision(10);
	int n, a, b;
	cin >> n >> a >> b;
	vector<LLI> v(n);
	REP(i, n)cin >> v[i];
	RSORT(v);

	// 平均の最大
	double sum = 0;
	REP(i, a)sum += v[i];
	double ave = sum / a;

	cout << ave << endl;

	// 組み合わせ
	int cnt = 0;
	REP(i, n)if (v[a - 1] == v[i])cnt++;
	int useA = 0;
	REP(i, a)if (v[a - 1] == v[i])useA++;
	int useB = 0;
	REP(i, b)if (v[a - 1] == v[i])useB++;


	LLI ans = 0;
	if (v[0] == v[a - 1]) {
		for (int i = useA; i <= useB; i++) {
			ans += pas[cnt + 1][i + 1];
		}
	}
	else {
		ans = pas[cnt + 1][useA + 1];
	}
	cout << ans;
	return 0;
}

/*
1125899906842623
19898961463

*/

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

using namespace std;

typedef long long LL;
typedef unsigned long long uLL;
typedef long double ldb;
typedef pair<int,int> pii;

int A[100001];
int B[100001];
int C[100001];
LL dp[100001][2];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin>>n;
    for(int i = 0; i < n; ++i)
        cin>>A[i];
    for(int i = 0; i < n; ++i)
        cin>>B[i];
    for(int i = 0; i < n; ++i)
        cin>>C[i];
    sort(A, A+n);
    sort(B, B+n);
    sort(C, C+n);
    int j = 0;
    for(int i = 0; i < n; ++i)
    {
        while(j < n && A[j]<B[i])
            ++j;
        dp[i][0] = j;
    }
    LL sum = 0;
    j = 0;
    LL ans = 0;
    for(int i = 0; i < n; ++i)
    {
        while(j < n && B[j]<C[i])
            sum += dp[j++][0];
        dp[i][1] = sum;
        ans += sum;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3072
// In the name of God //
 
#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define pii pair <int, int>
using namespace std;
const int N = 2e5 + 5;

void solve() {
    int h, w, K;
    cin >> h >> w >> K;
    vector<vector<char>> a(h, vector<char>(w));
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for (int r = 0; r < (1<<h); r++) {
        for (int c = 0; c < (1<<w); c++) {
            int black = 0;
            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    // cout << i << " " << j << " " << (r>>i) << " " << (c>>i) << "\n";
                    // cout << a[i][j] << " ";
                    if(((r>>i) & 1) && ((c>>j) & 1) && a[i][j] == '#') {
                        black++;
                    }
                }
            }
            // cout << black << "\n";
            if(black == K) {
                ans++;
            }
        }
    }
    cout << ans;
}

int main()  {
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    int tt = 1;
    // cin >> tt;
    for (int tc = 1; tc <= tt; ++tc) {
        solve();
    } 
}                                   

Measured memory_bytes: 3672
x = int(input())
# 下から
xr = int(x ** 0.2)
m = 0
for i in reversed(range(xr + 1)):
    for j in range(m,i):
        ip = i ** 5
        jp = j ** 5
        sumij = ip + jp
        if sumij < x:
            m = j
        elif sumij > x:
            break
        else:
            print(str(i) + " " + str(-1 * j))

#上から
m = 0
for i in range(xr + 1,1000):
    for j in range(m,i):
        ip = i ** 5
        jp = j ** 5
        subij = ip - jp
        if subij > x:
            m = j
        elif subij < x:
            break
        else:
            print(str(i) + " " + str(j))


Measured memory_bytes: 9400
import sys

N, M = map(int, sys.stdin.readline().split())

L = []
R = []

for i in range(M):
    temp_l, temp_r = map(int, sys.stdin.readline().split())
    L.append(temp_l)
    R.append(temp_r)

temp = min(R) - max(L) + 1

if temp > 0:
    print(temp)
else:
    print(0)


Measured memory_bytes: 10996
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;

int main(){
	int N,l;
	cin >> N;
	vector<int> A(N);
	vector<int> B(N);
	vector<int> C(N-1);

	for (int i = 0;i < N;i++){
		cin >> l;
		A[i] = l;
	}
	for (int i = 0;i < N;i++){
		cin >> l;
		B[i] = l;
	}for (int i = 0;i < N - 1;i++){
		cin >> l;
		C[i] = l;
	}
	int ans = 0;
	for (int i = 0;i<N;i++){
		ans += B[i];
		if (A[i] + 1 == A[i+1] && i < N -1){
			ans += C[A[i] - 1];
		}
	}
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

int q;
string A, B;

void findlongest() {
	int res[1001][1001];
	A = ' '+A ;
	B = ' '+B ;
	int l1 = A.size();
	int l2 = B.size();
	int max = 0;
	int j;
	for (int i = 0; i < l1; ++i) {
		for (j = 0; j < l2; ++j) {
			if (i == 0) {
				res[0][j] = 0;
			}
			else if (j == 0) {
				res[i][0] = 0;
			}
			else {
				if (A[i] == B[j]) {
					res[i][j] = res[i - 1][j - 1] + 1;
					if (max < res[i][j]) {
						max = res[i][j];
					}
				}
				else {
					if (res[i - 1][j] >= res[i][j - 1]) {
						res[i][j] = res[i - 1][j];
					}
					else {
						res[i][j] = res[i][j - 1];
					}
				}
			}
			//cout << res[i][j] << ' ';
		}
		//cout << endl;
	}

	cout << max << endl;
}

int main() {
	cin >> q;
	for (int i = 0; i < q; ++i) {
		cin >> A;
		cin >> B;
		findlongest();
	}
	return 0;
}


Measured memory_bytes: 7080
def get_current_v_max(t, t_from, t_to, v_max):
    # 制約(t_from, t_to, v_max)の元で、時刻tにおける最大速度を返す
    if t <= t_from:
        return - t + t_from + v_max
    elif t_to <= t:
        return t - t_to + v_max
    else:
        return v_max


def main():
    N = int(input())
    # t, vを縦横2倍にスケールしておけば、グラフの交点が全部格子点上に乗る
    # 最後にt-vグラフの面積を1/4倍する
    SCALE = 2
    T = list(map(lambda t: int(t) * SCALE, input().split()))
    V = list(map(lambda v: int(v) * SCALE, input().split()))
    MAX_V = 100 * SCALE
    # (t_from, t_to, v_max): t_from～t_toの間は速度v_max以下
    constraint_list = [(0, 0, 0)]
    t_from = 0
    for t, v in zip(T, V):
        constraint_list.append((t_from, t_from + t, v))
        t_from += t
    constraint_list.append((t_from, t_from, 0))
    # 各時刻においてすべての制約を満たす最大速度を求めていく
    v_max_list = [MAX_V] * (sum(T) + 1)
    for t in range(sum(T) + 1):
        for t_from, t_to, v_max in constraint_list:
            v_max_list[t] = min(v_max_list[t], get_current_v_max(t, t_from, t_to, v_max))
    # 答えは走行距離なので、t-vグラフの面積を求める
    ans = 0
    for t in range(sum(T)):
        ans += (v_max_list[t] + v_max_list[t + 1]) / 2
    print(ans / (SCALE**2))


if __name__ == '__main__':
    main()

Measured memory_bytes: 74352
n,m=map(int,input().split())
a,b=[],[]
for i in range(n):
  j,k=map(int,input().split())
  a.append(j)
  b.append(k)
a,b=zip(*sorted(zip(a,b)))
ans=0
for i in range(n):
  if m>b[i]:
    ans+=a[i]*b[i]
    m-=b[i]
  else:
    ans+=a[i]*m
    break
print(ans)

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

#define ll long long
#define str string
#define INF (1e9)

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


ll V[10000000] = {}, G[10000000] = {},a = 0,b = 0,n = 0, k = 0,sum = 0;;
str S,Sa;
bool ans = false;

int findSumOfDigits(int n) {
	int sum = 0;
	while (n > 0) {
		
		sum += n%10;
		n /= 10;
	}
	return sum;
}

int main(){
cin.tie(0);
ios::sync_with_stdio(false);
		//Code Line
cin >> a >> b;
if(b % a == 0)cout << a + b << endl;
else cout << b - a << endl;

		//Code Line
return 0; 
}




Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int h,r;
	scanf("%d%d",&h,&r);
	if(h>-r){
		printf("1\n");
	}else if(h==-r){
		printf("0\n");
	}else{
		printf("-1\n");
	}
	return 0;
}

Measured memory_bytes: 2696
n, a, b = list(map(int, input().split(' ')))

# 二項係数 mod [検索]
mmm = 1000000000 + 7
fac = []
inv = []
inv_fac = []
def init(n):
    fac.append(1)
    fac.append(1)
    inv.append(0)
    inv.append(1)
    inv_fac.append(1)
    inv_fac.append(1)
    for i in range(2, n):
        fac.append(fac[-1] * i % mmm)
        inv.append(mmm - inv[mmm%i] * (mmm // i) % mmm)
        inv_fac.append(inv_fac[-1] * inv[-1] % mmm)

def choice(a, b):
    if a < b:
        return 0
    v = 1
    for i in range(b):
        v = (v * (n-i)) % mmm
    return v * inv_fac[b]

init(int(2e5) + 1)


ans = pow(2, n, mmm) - 1  # v, e, mod
bunshi = 1
for i in range(a):
    bunshi = (bunshi * (n-i)) % mmm
ans -= choice(n, a)
ans -= choice(n, b)
print(ans % mmm)

'''
4, 1, 3 => 4c2 + 4c4 -> 6+1 = 7
4 + 6 + 4 + 1 - 4c1 - 4c2 
1        1
11       2
121      4
1331     8
14641   16, 0が無いので-1, 大きい combination -> 二項係数 mod [検索]
'''

Measured memory_bytes: 109952
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

use std::collections::BinaryHeap;
use std::collections::HashMap;

fn main() {
    let n: usize = read();
    let k: usize = read();
    let mut map: HashMap<i64, i64> = HashMap::new();
    let mut bh: BinaryHeap<i64> = BinaryHeap::new();

    for _ in 0..n {
        let ai = read();
        let current = map.entry(ai).or_insert(0);
        *current += 1;
    }

    if map.len() <= k {
        println!("{}", 0);
        return;
    }

    for (_, v) in &map {
        bh.push(-(*v));
    }

    let mut ans = 0;

    for _ in 0..(map.len() - k) {
        let a = bh.pop().unwrap();
        ans -= a;
    }
    println!("{}", ans);
}


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

using namespace std;

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

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int n,m;
int q;
int a[125252];
bool used[125252];
int t[125252];
int t_i;
int rev[125252];
int cnt[125252];

int main(){
  scanf("%d%d%d",&n,&m,&q);
  REP(i,q)scanf("%d",a+i),--a[i];
  // calc target sequence
  t_i = 0;
  FORR(i,0,q){
    int c = a[i];
    if(used[c])continue;
    used[c] = true;
    t[t_i++] = c;
  }
  REP(i,m){
    if(!used[i])t[t_i++] = i;
  }
  REP(i,m){
    rev[t[i]] = i;
  }
  // split
  cnt[0] = n;
  FORR(i,0,q){
    int c = a[i];
    int id = rev[c];
    if(cnt[id]>0){
      cnt[id]--;
      cnt[id+1]++;
    }
  }
  REP(i,m){
    if(cnt[i]>0){
      bool flag = true;
      FOR(j,i,m-1){
        if(t[j]>t[j+1]){
          flag = false;
          break;
        }
      }
      puts(flag?"Yes":"No");
      break;
    }
    if(i==m-1){
      puts("Yes");
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 1920
#include <iostream>
#include <bitset>

using namespace std;
typedef long long  ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)

int main() {
	int N; cin >> N;
	int T[101];
	rep(i, 1, N + 1) cin >> T[i];

	int M; cin >> M;
	int P[101], X[101];
	rep(i, 1, M + 1) {
		cin >> P[i] >> X[i];
	}
	rep(i, 1, M + 1) {
		int time = 0;
		rep(j, 1, N + 1) {
			time += (j == P[i]) ? X[i] : T[j];
		}
		cout << time << endl;
	}

	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef pair<int,int> P;
constexpr ll INF = (1LL << 55);
int main(){ 
  int n;
  cin >> n;
  vector<vector<P>> g(n);
  rep(i,n-1) {
    int u, v, c;
    cin >> u >> v >> c;
    u--; v--;
    g[u].emplace_back(make_pair(v,c));
    g[v].emplace_back(make_pair(u,c));
  }
  auto dijkstra = [&](int s) {  
    vector<ll> d(n,INF);
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> que;
    d[s] = 0;
    que.push(make_pair(0LL,s));
    while (!que.empty()) {
      auto p = que.top(); que.pop();
      int u = p.second;
      if (d[u] < p.first) continue;
      for (auto v : g[u]) {
        if (v.first == u) continue;
        if (d[u] + v.second < d[v.first]) {
          d[v.first] = d[u] + v.second;
          que.push(make_pair(d[v.first], v.first));
        }
      }
    }
    return d;
  };
  int q, k;
  cin >> q >> k;
  k--;
  auto d = dijkstra(k);
  while (q--) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    cout << d[x] + d[y] << endl;
  }
  return 0;
} 

Measured memory_bytes: 9460
import sys
sys.setrecursionlimit(200000)


def input():
    return sys.stdin.readline()[:-1]


# Kから順に探索して、Kからの距離を求める
def dfs(v, parent=-1, distance=0):
    # Kから現在の位置までの距離を記録する
    sum_distance[v] = distance
    for i, j in tree[v]:
        if i == parent:
            continue
        dfs(i, v, distance+j)


N = int(input())

tree = [[] * N for i in range(N)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    tree[a].append([b, c])
    tree[b].append([a, c])

Q, K = map(int, input().split())

# 事前に各頂点から頂点Kまでの距離を求める
sum_distance = [0]*N
dfs(K-1)

# クエリを処理する。xからKまでとyからKまでの距離の合計を求める
for _ in range(Q):
    x, y = map(int, input().split())
    print(sum_distance[x-1]+sum_distance[y-1])


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

using namespace std;

#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVS vector<vector<string>>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)
typedef long long ll;
typedef pair <int, int> P;
const int  INF = 2147483647;
const ll INFL = 9223372036854775807;
const ll mod = 1000000007;

using namespace std;

struct UnionFind {
	vector<int> par;
	int cnt;
	UnionFind(int size_) : par(size_, -1), cnt(size_) { }
	bool unite(int x, int y) {
		x = find(x); y = find(y);
		if (x != y) {
			if (par[y] < par[x]) swap(x, y);
			par[x] += par[y]; par[y] = x;
			cnt--;
		}
		return x != y;
	}
	bool same(int x, int y) {
		return find(x) == find(y);
	}
	int find(int x) {
		return par[x] < 0 ? x : par[x] = find(par[x]);
	}
	int size(int x) {
		return -par[find(x)];
	}
	int size() {
		return cnt;
	}
};

int main() {
	int n, m;
	cin >> n >> m;
	UnionFind uf(n + m);
	REP(i, n) {
		int k;
		cin >> k;
		REP(j, k) {
			int l;
			cin >> l;
			l--;
			uf.unite(i, l + n);
		}
	}
	bool b = true;
	FOR(i, 1, n) {
		if (!uf.same(0, i))b = false;
	}
	if (b)cout << "YES" << endl;
	else cout << "NO" << endl;
	return 0;
}

Measured memory_bytes: 1024
// I'm a f*cking looser
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fasino ios_base::sync_with_stdio(false); cin.tie(0);
#define asc(A) sort(A.begin(),A.end())
#define dsc(A) sort(A.begin(),A.end(),greater<ll>())
#define input(A,N) for(ll i=0;i<N;i++) cin>>A[i];
int main()
{
    fasino
    int n;
    cin>>n;
    vector<ll> a(n);
    input(a,n);
    int dp[n];
    dp[0] = 0;
    dp[1] = abs(a[1] - a[0]);  // Because At step 1 : Only i+1 jump is possible.
    for(int i = 2; i < n; i++) {
        dp[i] = min(dp[i - 1] + abs(a[i] - a[i - 1]), dp[i - 2] + abs(a[i] - a[i - 2]));
    }
    cout<<dp[n-1];
    return 0;
}

Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b,c;
	cin>>a>>b>>c;
    if(a==b&&a!=c){
      cout<<"Yes";
    }else if(b==c&&b!=a){
      cout<<"Yes";
    }else if(a==c&&a!=b){
      cout<<"Yes";
    }else{
      cout<<"No";
    }
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict, deque, Counter
import sys
import bisect
import heapq
import math

# input = sys.stdin.readline

sys.setrecursionlimit(1000000000)

MIN = -10 ** 9
MOD = 10 ** 9 + 7

ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"


def keta(n):
    if n < 10:
        return 1
    return math.floor(math.log10(n - 1)) + 1


def check(A, B, X, n):
    return A * n + B * keta(n) <= X


def main():
    N = int(input())
    ab = [[int(a) - 1 for a in input().split()] for _ in range(N - 1)]

    tree = defaultdict(list)
    # res = {}

    for i, (a, b) in enumerate(ab):
        # aa = tt[a]
        # aa.append((b, i))
        # tt[a] = aa
        if a not in tree:
            tree[a] = []
        tree[a].append((b, i))

    # def p(tt, parent):
    #     children = tt[parent]
    #     res[parent]=children
    #     # res = {parent: children}
    #     for c, ii in children:
    #         p(tt, c)
    #     return res
    #
    #
    # tree = p(tt, 0)

    colors = len(tree[0])
    for k, v in tree.items():
        if k == 0:
            continue
        colors = max(colors, len(v) + 1)

    print(colors)

    res = [None] * (N - 1)

    def solve(pos, parentcol):
        children = tree[pos]
        for iii, (c, i) in enumerate(children):
            res[i] = (parentcol + 1 + iii) % colors
            solve(c, res[i])

    solve(0, -1)

    for i in range(N - 1):
        print(res[i] + 1)


if __name__ == '__main__':
    main()


Measured memory_bytes: 146008
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
using ll = long long;

void print_ans(bool flag){
    if(flag){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }   
}

int main(){
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    string t1 = "maerd";
    string t2 = "remaerd";
    string t3 = "esare";
    string t4 = "resare";
    bool ans = false;
    while(true){
        if(s.size() == 0){
            ans = true;
            break;
        }
        if(s.size() < 5){
            ans = false;
             break;
        } else {
            if(s.size() >= 7){
                string sub5 = s.substr(0, 5);
                string sub6 = s.substr(0, 6);
                string sub7 = s.substr(0, 7);
                if(sub5 == t1 || sub5 == t3){
                    string next = s.substr(5);
                    s = next;
                } else if(sub6 == t4) {
                    string next = s.substr(6);
                    s = next;
                } else if(sub7 == t2) {
                    string next = s.substr(7);
                    s = next;
                } else {
                    ans = false;
                    break;
                }
            } else if(s.size() >= 6){
                string sub5 = s.substr(0, 5);
                string sub6 = s.substr(0, 6);
                if(sub5 == t1 || sub5 == t3){
                    string next = s.substr(5);
                    s = next;
                } else if(sub6 == t4) {
                    string next = s.substr(6);
                    s = next;
                } else {
                    ans = false;
                    break;
                }
            } else if(s.size() >= 5){
                string sub5 = s.substr(0, 5);
                if(sub5 == t1 || sub5 == t3){
                    string next = s.substr(5);
                    s = next;
                } else {
                    ans = false;
                    break;
                }
            }
        }
    }
    print_ans(ans);
    return 0;
}


Measured memory_bytes: 512
r,c=map(int,input().split())
sheet=[list(map(int,input().split())) for i in range(r)]
for i in range(r):
    sheet[i].append(sum(sheet[i]))
Column_sum=[0]*(c+1)
for j in range(c+1):
    for i in range(r):
        Column_sum[j]+=sheet[i][j]
        
for i in range(r):
    print(*sheet[i])
print(*Column_sum)


Measured memory_bytes: 6228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
ll gcd(ll a,ll b){
	if(b == 0) return a;
	return gcd(b,a%b);
}
 
ll lcm(ll a,ll b){
	ll g = gcd(a,b);
	return a / g * b; // Be careful not to overflow
}
 
int main(void) {
	int N;
	cin >> N;
 
	ll ans = 1LL;
 
	for (int i = 0; i < N; ++i) {
		ll T;
		cin >> T;
		ans = lcm(ans, T);
	}
 
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <bitset>
#include <iomanip>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int main(int argc, const char * argv[]) {
    int N, M;
    cin >> N >> M;
    N = min(N, M);

    vector<int> X(M);
    for (int i = 0; i < M; i++) cin >> X[i];
    sort(X.begin(), X.end());

    vector<int> adj_dst(M);
    adj_dst[0] = 0;
    for (int i = 1; i < M; i++) adj_dst[i] = X[i] - X[i-1];
    sort(adj_dst.begin(), adj_dst.end());

    int tmp = 0;
    for (int i = 1; i < N; i++) {
        tmp += adj_dst[M - i];
    }
    cout << X.back() - X.front() - tmp << endl;

    return 0;
}

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

using namespace std;

int main(void) {
  
 long long N;
 long long D;
 cin >> N >> D;
 long long count = 0;
 for(long long i =0 ;i<N; i++) {
   long long X, Y;
   cin >> X >> Y;
   double d = sqrt(X*X + Y*Y);
   if(d <= D) {
     count++;
   }
 }

  cout << count << endl;

}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    const int N = 1e5+1;
    int n; cin >> n;
    vector<int> m(N);
    REP(i,n) {
        int x;
        cin >> x;
        m[x]++;
    }
    int cnt = 0;
    REP(i,N) if (m[i] != 0) cnt++; 

    cout << ( cnt % 2 == 0 ? cnt -1 : cnt ) << endl;

    return 0;
}

Measured memory_bytes: 640
#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <utility>
#include <math.h>
#include <stdexcept>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
#include <string.h>

using namespace std;
#define  rep(i,n) for(int i=0;i<n;i++)
#define  rrep(i,n) for(int i=n-1;i>=0;i--)///n-1番目からn回
#define  REP(i,a,b) for(int i=a;i<b;i++) ///a番目からb回
#define  RREP(i,a,b) for(int i=a;i<b;i--)
typedef long long int ll;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<string> vs;



//int arr[N]
////sort(arr,arr +N)

//vector <int> hoge
////sort(hoge.begin(),hoge.end());
///*min_element(hoge.begin(),hoge.end();　最小値　　　最大値はmax_element();
///(10-(n%10))%10  1桁目取得

#define Ru(n)  ( ((n)+9)/10*10  ) //切りあげ
#define Rd(n)  ( ((n)-10)/10*10 +10 )	切り捨て

int gcd(int a,int b);
int main() {
		int n;
		cin>>n;

		cout<<180*n-360;
		return 0;

}




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


Measured memory_bytes: 256
n, W = map(int, input().split())
dp = [0]*(W+1)
for _ in range(n):
    w, v = map(int, input().split())
    tmp_dp = [max(dp[sum_w], dp[sum_w - w] + v) for sum_w in range(w, W+1)]
    dp[w:] = tmp_dp
print(dp[-1])

Measured memory_bytes: 119876
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

VL slide_max(VL a, int k){
    VL ret;
    deque<int> dq;
    REP(i,a.size()){
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        ret.push_back(a[dq.front()]);
        if (i - k + 1 >= 0){
            if (dq.front() == i - k + 1) dq.pop_front();
        }
    }
    return ret;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    VL a(n);
    REP(i,n) scanf("%lld", &a[i]);

    VL dp(n);
    REP(i,n) dp[i] = a[i];

    REP(x,k-1){
        VL ma = slide_max(dp, m);

        dp[0] = -1e18;
        REP(i,n-1) dp[i+1] = ma[i] + a[i+1] * (x + 2);

        // REP(i,n) cout << dp[i] << " ";
        // cout << endl;
    }

    ll ma = 0;
    REP(i,n) ma = max(ma, dp[i]);
    cout << ma << endl;
    
    return 0;
}


Measured memory_bytes: 4436
#include <iostream>
#include <string>

using namespace std;

int main()
{
	int n;
	string str;
	
	cin >> n;
	cin.ignore();
	while (n > 0){
		getline(cin, str);
		int len = 0;
		while (1){
			len = str.find("Hoshino", len);
			if (len == -1)  break;
			str[len + 6] = 'a';
		}
		cout << str << endl;
		n--;
	}
	return (0);
}

Measured memory_bytes: 1204
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
a = factorization(N)

ans = []

for i in range(len(a)):
    tmp = 1
    while a[i][1] >= tmp and a[i][0] != 1:
        b = a[i][0]**tmp
        ans.append(b)
        a[i][1] -= tmp
        tmp += 1

print(len(ans))

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

int main(){
    int r, c;
    int table[101][101] = {};
    
    cin >> r >> c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++) cin >> table[i][j];
    }
    
    for(int i = 0; i < r; i++){
        int sum = 0;
        for(int j = 0; j < c; j++) sum += table[i][j];
        table[i][c] = sum;
    }
    
    for(int i = 0; i <= c; i++){
        int sum = 0;
        for(int j = 0; j < r; j++) sum += table[j][i];
        table[r][i] = sum;
    }
    
    for(int i = 0; i <= r; i++){
        for(int j = 0; j < c; j++) cout << table[i][j] << " ";
        cout << table[i][c] << endl;
    }
    
    return 0;
}


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


bool solve(){
	int n;
	cin >> n;
	if( n == 0 )return false;
	int now = 0;
	int le = 0,ri = 0,cnt = 0;
	for(int i=0;i<n;i++){
		string s;
		cin >> s;
		if(s[0] == 'l'){
			if(s[1] == 'u')le = 1;
			else le = 0;
		}else{
			if(s[1] == 'u')ri = 1;
			else ri = 0;
		}
		if(le == 1 && ri == 1 && now == 0){
			now = 1;cnt++;
		}else if(le == 0 && ri == 0 && now == 1){
			now = 0;cnt++;
		}
	}
	cout << cnt << endl;
	return true;
}

int main(void){
	while(solve()){}


	return 0;
}

Measured memory_bytes: 3136
from collections import defaultdict

import sys
sys.setrecursionlimit(10**6)
ii = lambda: int(input())
mis = lambda: map(int,input().split())
lmis = lambda: list(mis())
INF = float('inf')

def main():
    n,k=mis()
    if n>=k:
        n%=k
        print(k%n if n!=0 else 0)
        exit()    
    print(n if n<=k//2 else k-n)



if __name__ == "__main__":
    main()

Measured memory_bytes: 3316
import collections

N = int(input())

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

c = collections.Counter(prime_factorize(N))

ans=0
for i in c.values():
    tmp = i
    cnt=0
    val=1
    while True:
        tmp = tmp-val
        val+=1

        if tmp > 0:
            cnt+=1
        
        if tmp == 0:
            cnt+=1
            ans+=cnt
            break
        
        if tmp < 0:
            ans+=cnt
            break

print(ans)


Measured memory_bytes: 9468
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
 
typedef map<int, int> Flag;
 
bool FindValueFromMap(int i, const Flag flag, int *out = NULL)
{
    Flag::const_iterator it = flag.find(i);
 
    if (it != flag.end()) {
        if (out != NULL) {
            *out = it->second;
        }
        return true;
    }
    return false;
}
 
int main()
{
    int A,N;
    int max_num,next_max_num;
    Flag flag;
    max_num = next_max_num = 0;
    string s;
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> A;
        int tmp = 0;
        if (flag[A]) {
            tmp = flag[A];
            if (tmp % 2 == 1) {
                if (max_num < A) {
                    next_max_num = max_num;
                    max_num = A;
                } else {
                     next_max_num = max(next_max_num, A);
                }
            }
            flag[A]++;
        } else {
            flag[A] = 1;
        }
    }
    
    cout <<  (long long) max_num * next_max_num << "\n";
    return 0;
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 1e5+7;
const int INF = 1e9+7;
const double eps = 1e-5;
#define pb push_back

int main(){
    int x, y, z;
    cin >> x >> y >> z;
    cout << z << ' ' << x << ' ' << y << endl;;
}
/*

*/


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

int main(void){
	int N;
	ll K;
	cin >> N >> K;
	int P[N+1];
	rep(i,N) cin >> P[i+1];
	ll C[N+1];
	rep(i,N) cin >> C[i+1];

	ll ans = -1e10;
	for (int i = 1; i <= N; i++) {
		ll tot = 0;
		int period = 0;
		int j = i;
		vector<ll> v;
		while (1) {
			j = P[j];
			tot += C[j];
			v.push_back(C[j]);
			period++;
			if (j == i) break;
		}

		ll cand;
		ll tmp = 0;
		int vsize = v.size();
		rep(j, vsize) {
			if (j+1>K) break;
			tmp+=v[j];
			cand = tmp;
			if (tot>0) {
				cand += tot*((K-j-1)/period);
			}
			ans = max(ans, cand);
		}
	}

	cout << ans << endl;

return 0;
}


Measured memory_bytes: 3796
# use dp
# python 3.

m, n = map(int, input().split())
k = int(input())

# answer matrix
dp_j = [[0 for i in range(n+1)]for j in range(m+1)]
dp_o = [[0 for i in range(n+1)]for j in range(m+1)]


# input row and calc dp
for i in range(1, m+1):
   row = list(input())
   # print(row)
   for j in range(1, n+1):
      dp_j[i][j] = dp_j[i-1][j] + dp_j[i][j-1] - dp_j[i-1][j-1] + (1 if row[j-1] == 'J' else 0)
      dp_o[i][j] = dp_o[i-1][j] + dp_o[i][j-1] - dp_o[i-1][j-1] + (1 if row[j-1] == 'O' else 0) 

      
for i in range(k):
   a, b, c, d = map(int, input().split())

   j_cnt = dp_j[c][d] - dp_j[a-1][d] - dp_j[c][b-1] + dp_j[a-1][b-1]
   o_cnt = dp_o[c][d] - dp_o[a-1][d] - dp_o[c][b-1] + dp_o[a-1][b-1]
   i_cnt = (abs(c-a)+1) *  (abs(d-b)+1) - j_cnt - o_cnt

   print(str(j_cnt) + ' ' + str(o_cnt) + ' ' + str(i_cnt))

Measured memory_bytes: 87828
<?php
fscanf(STDIN, "%d%d", $N, $H);
for($i = 0; $i < $N; $i++){
    fscanf(STDIN, "%d%d", $a[], $b[]);
}
$max = max($a);
rsort($b);
$count = 0;
for($i = 0; $i < $N; $i++){
    if($b[$i]<$max)break;
    $H-=$b[$i];
    $count++;
    if($H<=0){echo $count,"\n";exit;}
}
echo $count + ceil($H/$max),"\n";


Measured memory_bytes: 15988
n = input()
l = len(n)

table = [[0] * 9 for _ in range(9)]
for i in range(9):
    for j in range(9):
        if l == 1:
            if i + 1 <= int(n) and i == j:
                table[i][j] += 1
        elif l == 2:
            if 10 * (i + 1) + (j + 1) <= int(n):
                table[i][j] += 1
            if i == j:
                table[i][j] += 1
        else:
            if i + 1 < int(n[0]):
                for k in range(l-1):
                    table[i][j] += 10 ** k
            elif i + 1 == int(n[0]):
                if j + 1 <= int(n[-1]):
                    table[i][j] += int(n[1:l-1]) + 1
                else:
                    table[i][j] += int(n[1:l-1])
                for k in range(l-2):
                    table[i][j] += 10 ** k
            else:
                for k in range(l-2):
                    table[i][j] += 10 ** k
            if i == j:
                table[i][j] += 1

res = 0
for i in range(9):
    for j in range(9):
        res += table[i][j] * table[j][i]

print(res)

Measured memory_bytes: 38256
N,K = map(int,input().split())
d = []
A = []
for i in range(K):
    d.append(int(input()))
    A.append(list(map(int,input().split())))
def search(A,i):
    for j in range(0,len(A)):
        for k in range(0,len(A[j])):
            if A[j][k] == i:
                return False
    return True
ans = 0
for i in range(1,N+1):
    if search(A,i):
        ans += 1
print(ans)




Measured memory_bytes: 9208
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const long double EPS = 1e-9;
const ll mod = 1e9 + 7;
const ll INF = 1e9;

#define rep(i, n) for(ll i = 0; i < n ; i++ )
#define For(i, a, b) for(ll i = (a); i < (b) ; i++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

const ll MAX_N = 200000;

int main(void){
    ll N;
    ll X[MAX_N], sortX[MAX_N];
    ll answer;

    cin >> N;
    rep(i, N){
        cin >> X[i];
        sortX[i] = X[i];
    }

    sort(sortX, sortX + N);
    ll pre_med = sortX[N / 2 - 1];
    ll post_med = sortX[N / 2];

    rep(i, N) if (X[i] <= pre_med) cout << post_med << endl; else cout << pre_med << endl;

    return 0;
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(i=0;i<n;i++)
#define ll long long
#define test(a) cout << * << a << endl;
int main(){
  int i;
  int sum = 0;
  string str;
  int num[10] = {0};
  
  cin >> str;
  rep0(i,str.size()){
    num[i] = (int)(str[i] - '0');
    sum += num[i];
    //test(num[i]);
  }
  if( atoi(str.c_str()) % sum == 0 )
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
//#include <unistd.h>
//#include <stdio.h>
#define rep(i,x) for(ll i = 0;i<x;i++)
#define all(a) (a).begin(),(a).end()
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll INF = 1LL << 60;
const ll mod = 1000000007;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logN)
ll modpow(ll n,ll m,ll MOD){
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}

//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
/*
    cout << fixed << setprecision(15);
*/

int main(){
    ll N;
    cin >> N;
    ll made = 0;
    for(ll i = 1;i < 50000;i++){
        if((i * i + i) / 2 >= N){
            made = i;
            break;
        }
    }
    for(ll i = made;i >= 1;i--){
        if(N >= i){
            cout << i << endl;
            N -= i;
        }
        else{
            if(N != 0){
            cout << N << endl;
            }
            break;
        }
    }
}

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

using namespace std;
using ll = long long;

int main() {
    ll n = 0;
    cin >> n;
    vector<ll> a(pow(10,5) + 1);
    for(ll i = 0;i < n;i++){
        ll tmp = 0;
        cin >> tmp;
        a[tmp] ++;
    }
    ll sum = 0;
    for(ll i = 1;i < a.size();i++){
        sum += i * a[i];
    }
    //cout << sum << endl;
    ll q = 0;
    cin >> q;
    for(ll i = 0;i < q;i++){
        ll b,c = 0;
        cin >> b >> c;
        sum -= a[b] * b;
        //cout << sum << " ";
        a[c] += a[b];
        sum += c * a[b];
        a[b] = 0;
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 4064
#include<iostream>
using namespace std;
int x[110][110];
int p[100][100][4];
int n, m;
int main() {
	while (true) {
		cin >> n >> m;
		if (n == 0 && m == 0) { break; }
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> x[i][j];
			}
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < m; j++) {
				cin >> p[i][j][0];
			}
		}
		for (int i = 1; i <= 3; i++) {
			for (int j = 0; j < m; j++) {
				for (int k = 0; k < m; k++) {
					p[m - 1 - k][j][i] = p[j][k][i - 1];
				}
			}
		}
		int cnt = 0;
		for (int i = 0; i <= n - m; i++) {
			for (int j = 0; j <= n - m; j++) {
				for (int k = 0; k < 4; k++) {
					bool ok = true;
					for (int l = 0; l < m; l++) {
						for (int o = 0; o < m; o++) {
							if (p[l][o][k] == -1) { continue; }
							if (p[l][o][k] != x[i + l][j + o]) {
								ok = false;
							}
						}
					}
					if (ok == true && cnt == 0) {
						int ok2 = false;
						for (int l = 0; l < m; l++) {
							for (int o = 0; o < m; o++) {
								if (p[l][o][k] >= 0 && ok2 == false) {
									int X = i + l + 1;
									int Y = j + o + 1;
									cout << Y << ' ' << X << endl;
									cnt = 1;
									ok2 = true;
								}
							}
						}
					}
				}
			}
		}
		if (cnt == 0) { cout << "NA" << endl; }
	}
	return 0;
}

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

#define ll long long

using namespace std;
ll a[200050];
int main()
{
   int n,m,a,num=0;
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
       cin>>a;
       num+=a;
   }
   if(num>n) cout<<-1<<endl;
   else cout<<n-num<<endl;
}



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

typedef long long ll;
typedef long double ld;

#define pb push_back
#define sort(s) sort(s.begin(),s.end())
#define reverse(s) reverse(s.begin(),s.end())
#define rep(i,n) for(ll (i)=0;(i)<(n);(i)++)

const ll mod = 1e9+7;

//最大公約数
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;
}

//素数判定
bool isPrime(ll x){
    ll i;
    if(x < 2)return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(i = 3; i*i <= x; i += 2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(ll n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

//桁数
int dignum(ll n) {
    int res = 0;
    while(n > 0) {
        res++;
        n /= 10;
    }
    return res;
}

//文字列中の特定の文字カウント
ll stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}

//階乗
ll ka(ll i){
    ll res=1;
    while(i>0){
        res=res*i;
        i--;
    }
    return res;
}
 
//ncr
ll ncr(ll x,ll y){
    ll a = x;
    ll b = 1;
    if(y>(x/2)){
        y=x-y;
    }
    for(ll i=1;i<y;i++){
        a*=x-i;
        b*=i+1;
    }
    return a/b;
}

//フィボナッチ数列 -92
ll f(ll x){
    ll dp[x+1];
    dp[1]=1;
    dp[2]=1;
    for(ll i=3;i<=x;i++){
        dp[i]=dp[i-1]+dp[i-2];
    }
    return dp[x];
}



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

    string s;
    cin >> s;
    vector<string> ans(n);
    int check = 0;
    int ka = 0;

    for(int i=0;i<n;i++){
        if(s[i]=='a'&&check<a+b){
            ans[i]="Yes";
            check++;
        }else if(s[i]=='b'&&check<a+b&&ka<b){
            ans[i]="Yes";
            check++;
            ka++;
        }else{
            ans[i]="No";
        }
    }

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

Measured memory_bytes: 6272
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  int ans = a[n/2] - a[n/2-1];
  cout << ans << endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define MOD 1000000007

vvi G(200010);
vector<long> addi(200010,0);

void dfs(int v,int pv){
  for(int nv : G.at(v)){
    if(nv == pv) continue;
    addi.at(nv) += addi.at(v);
    dfs(nv,v);
  }
}

int main(){
  int n,q;
  cin >> n >> q;
  rep(i,n-1){
    int a,b;
    cin >> a >> b;
    G.at(a-1).push_back(b-1);
    G.at(b-1).push_back(a-1);
  }
  rep(i,q){
    int p,x;
    cin >> p >> x;
    addi.at(p-1) += x;
  }
  dfs(0,-1);
  rep(i,n){
    cout << addi.at(i) << " ";
  }
}


Measured memory_bytes: 27392
#include<iostream>
#include<algorithm>
#include<math.h>

using namespace std;

int main(void) {
  int n;
  cin >> n;
  int h[n];
  for(int i=0;i<n;i++) cin >> h[i];
  long long int cost[n];
  fill(cost, cost+n, 1e9);
  cost[0]=0;
  cost[1]=abs(h[0]-h[1]);
  for(int i=2;i<n;i++) {
    cost[i] = min(cost[i-1]+abs(h[i]-h[i-1]), cost[i-2]+abs(h[i]-h[i-2]));
  }
  
  cout << cost[n-1] << endl;
  
}

Measured memory_bytes: 1408
while true
	w, h = gets.chomp.split.map(&:to_i)
	break if [w, h] == [0, 0]

	wall_x, wall_y = [], []
	(h - 1).times{
		wall_x << [1] + gets.chomp.split.map(&:to_i) + [1]
		wall_y << gets.chomp.split.map(&:to_i)
	}
	wall_x << [1] + gets.chomp.split.map(&:to_i) + [1]
	wall_y.unshift(Array.new(w, 1))
	wall_y << Array.new(w, 1)

	step = Array.new(h){Array.new(w, 0)}
	list = [[0, 0, 1]]
	until list.empty?
		y, x, count = list.shift
		if step[y][x] == 0 || step[y][x] > count
			step[y][x] = count
			list << [y, x - 1, count + 1] if wall_x[y][x] == 0
			list << [y, x + 1, count + 1] if wall_x[y][x + 1] == 0
			list << [y - 1, x, count + 1] if wall_y[y][x] == 0
			list << [y + 1, x, count + 1] if wall_y[y + 1][x] == 0
		end
	end
	puts step[h - 1][w - 1]
end



Measured memory_bytes: 7164
#include <iostream>
using namespace std;
int main(void){
    string s;
    long long count=0, n_b=0;
    
    cin>>s;
    
    for(int i=0; i<s.length(); i++)
        s[i]=='W' ? count+=n_b : n_b++;
    cout<<count<<endl;
}


Measured memory_bytes: 640
// D.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

int main(int argc, char* argv[]) {
#ifdef _MSC_VER
	while (true)
#endif
	{
		LL h = -1, ans = 0, d = 1;
		cin >> h;
		if (h < 0) return 0;
		while (h > 0) {
			ans += d;
			h /= 2;
			d *= 2;
		}
		cout << ans << endl;
	}
	return 0;
}


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vi cnt(26, 0);
	REP(i, n) {
		string s;
		cin >> s;
		REP(j, m)cnt[s[j] - 'a']++;
	}
	REP(i, 26)cnt[i] %= 4;
	int a = 0, b = 0, c = 0;
	REP(i, 26) {
		if (cnt[i] == 1)a++;
		else if (cnt[i] == 2)b++;
		else if (cnt[i] == 3)c++;
	}
	if (n % 2 ) {
		if (m % 2) {
			if ((a == 1 && c == 0&&b<=n/2+m/2) || (a == 0 && c == 1&&b<n/2+m/2))cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		else {
			if (a == 0 && c == 0 && b <= m / 2)cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
	else {
		if (m % 2) {
			if (a == 0 && c == 0 && b <= n / 2)cout << "Yes" << endl;
			else cout << "No" << endl;
		}
		else {
			if (a == 0 && b == 0 && c == 0)cout << "Yes" << endl;
			else cout << "No" << endl;
		}
	}
}


Measured memory_bytes: 256