akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define MAXN 200005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,cnt0,cnt1,color[MAXN];
vector<int> G[MAXN];
int p[MAXN];
string str;
void add(int &a,int b) {a+=b; if(a>=MOD) a-=MOD;}
void dec(int &a,int b) {a-=b; if(a<0) a+=MOD;}
int pow_mod(int a,int i)
{
    int s=1;
    while(i)
    {
        if(i&1) s=1LL*s*a%MOD;
        a=1LL*a*a%MOD;
        i>>=1;
    }
    return s;
}
bool used[MAXN];
void dfs(int v,int p,int c)
{
    if(c==0) cnt0++; else cnt1++;
    color[v]=c;
    for(auto to:G[v])
    {
        if(to==p) continue;
        dfs(to,v,1-c);
    }
}
void fill_rest()
{
    int cur=1;
    for(int i=1;i<=n;i++)
    {
        if(!p[i])
        {
            while(cur<=n&&used[cur]) cur++;
            used[cur]=true;
            p[i]=cur;
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    dfs(1,0,0);
    if(cnt0<=n/3)
    {
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==0)
            {
                tot++;
                if(tot*3>n) break;
                p[i]=tot*3;
                used[tot*3]=true;
            }
        }
        fill_rest();
    }
    else if(cnt1<=n/3)
    {
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==1)
            {
                tot++;
                if(tot*3>n) break;
                p[i]=tot*3;
                used[tot*3]=true;
            }
        }
        fill_rest();
    }
    else
    {
        int tot=0;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==0)
            {
                tot++;
                if(tot*3-2>n) break;
                p[i]=tot*3-2;
                used[tot*3-2]=true;
            }
        }
        tot=0;
        for(int i=1;i<=n;i++)
        {
            if(color[i]==1)
            {
                tot++;
                if(tot*3-1>n) break;
                p[i]=tot*3-1;
                used[tot*3-1]=true;
            }
        }
        fill_rest();
    }
    for(int i=1;i<=n;i++) printf("%d ",p[i]);
    puts("");
    return 0;
}

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

using namespace std;
using ll = long long;

#define eb emplace_back
#define pb push_back
// #define mp make_pair
#define ff first
#define ss second

#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif

void io(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);     
    #ifdef LOCAL
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// #include <ext/rope>
// using namespace __gnu_pbds; 
// using namespace __gnu_cxx;
// template<typename T> using oset = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update >;
// template<typename T> using MinPriorityQueue = priority_queue <T, vector <T>, greater <T> >;
// template<typename T> void done(T ans) {cout << ans << "\n"; exit(0);}


template <typename A>
istream& operator>>(istream& input,vector<A>& x) { for(auto& i:x) input>>i; return input; }
template<typename A>
ostream& operator<<(ostream& output,vector<A>& x) {  for(auto& i:x) output<<i<<' '; return output; }
template<typename T, typename U> 
istream& operator>>(istream& is, pair<T, U>& p){is >> p.first >> p.second;        return is;}
template<typename T, typename U> 
ostream& operator<<(ostream& os, pair<T, U>& p){os << p.first << ' ' << p.second; return os;}

const int mod = 1e9 + 7;
const int N = 1e6 + 5;


int ans;
int main () {
    io();

    ll a;
    cin >> a;
    cout << (a + a * a + a*a*a);
}

Measured memory_bytes: 3644
n = input()
A = input().split(' ')
A.sort()
A.reverse()
q = input()
M = input().split(' ')

A = list(map(int,A))
M = list(map(int,M))
A.sort()

A_sum = [0]
for a in A:
    A_sum.append(a+A_sum[-1])
A_sum.pop(0)

A.reverse()
A_sum.reverse()


#memo = [True]*(len(A))

def search(base, m, n):
    if base == m:
        return True
    if len(A)-1 < n or m - base > A_sum[n]:
        return False
    result = False
    for i in range(len(A)-1,n-1,-1):
        if base + A[i] <= m: # and memo[i]:
#           memo[i] = False
#           print(str(A[i]) + ',' + str(base+A[i]) + ',')
            if search(base+A[i], m, i+1):
                return True
#           memo[i] = True
    return result

def print_yn(result):
    if result:
        print('yes')
    else:
        print('no')

for m in M:
#   print(str(m)+':')
    print_yn(search(0,m,0))

Measured memory_bytes: 7780
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int data[n];
  for(int i=0;i<n;i++) cin >> data[i];
  for(int i=n-1;i>=0;i--) cout << (i!=n-1?" ":"") << data[i];
  cout << endl;
}


Measured memory_bytes: 3128
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
int main(void){
    int num_que;
    int *time;
    int kind_drink;
    int *between,*cut_time;
    int *sum_time;

    scanf("%d",&num_que);
    time=(int *)malloc(sizeof(int)*num_que);
    int i;
    for(i=0;i<num_que;i++){
        scanf("%d",&time[i]);
    }

    scanf("%d",&kind_drink);
    between=(int *)malloc(sizeof(int)*(kind_drink));
    cut_time=(int *)malloc(sizeof(int)*(kind_drink));
    sum_time=(int *)malloc(sizeof(int)*(kind_drink));

    for(i=0;i<kind_drink;i++){
        sum_time[i]=0;
    }

    int j;  
    for(i=0;i<kind_drink;i++){
        scanf("%d %d",&between[i],&cut_time[i]);

        for(j=0;j<num_que;j++){
            if(j==(between[i]-1)){
                sum_time[i]+=cut_time[i];
            }
            else if(j!=(between[i]-1)){
                sum_time[i]+=time[j];
            }
        }
    }

    for(i=0;i<kind_drink;i++){
        printf("%d\n",sum_time[i]);
    }
    return 0;

}


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

int main() {
  int a,b,i;
  string s;
  cin>>a>>b>>s;
  bool yubin=true;
  for(i=0;i<a+b+1;i++){
    if(i!=a && s[i]=='-')
      yubin=false;
    if(i==a && s[i]!='-')
      yubin=false;
  }
  if(yubin)
    cout<<"Yes";
  else cout<<"No";
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;

#define MOD 1000000007

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  vector<int> left(n + 2), right(n + 2);
  for (int i = 0; i < n; ++i) {
    left[i + 1] = gcd(left[i], a[i]);
    right[n - i] = gcd(right[n - i + 1], a[n - 1 - i]);
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    int res = gcd(left[i - 1], right[i + 1]);
    ans = max(ans, res);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <cmath>
#include <bitset>

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

#define FALSE printf("false\n");
#define TRUE printf("true\n");
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i = 0;i < ((int)(n));++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define test(a) cout<<"line:"<<__LINE__<<"["<<(#a)<<": "<<(a)<<"]"<<endl

const int INF = 1e9+7;
const ll INFL = 9*1e18;

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

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

#define SUM(vec) accumulate(all(vec),0LL) // 配列の中身を全部足す
template<typename T>void print(T&& x){cout<<x<<endl;}// 改行付き出力
ll inline digit(ll num){int tmp = 0;while(num){tmp++;num/=10;}return tmp;} // 桁数
template<typename T>inline T digitSum(T num){T sum = 0;while(num){sum+=num%10;num/=10;}return sum;} // 各桁の和
template<typename T>inline T gcd(T a,T b){if(b == 0)return a;return gcd(b,a%b);} // 最大公約数
template<typename T>inline T lcm(T a, T b){T g = gcd(a,b);return a/g*b;} // 最小公倍数
template<typename T>inline T power(T a,T b){T tmp=1;rep(i,b){tmp*=a;}return tmp;} // 累乗
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
int ctoi(char c){return c-'0';}

// TODO: write
int main() {
  int n,m;cin>>n;
  vector<string> a(n);rep(i,n)cin>>a[i];
  cin>>m;
  vector<string> b(m);rep(i,m)cin>>b[i];
  map<string,int> blue,red;
  rep(i,n){
    blue[a[i]]++;
  }
  rep(i,m){
    red[b[i]]++;
  }
  int ans = 0;
  for(auto&& one: blue){
    chmax(ans,one.se - red[one.fi]);
  }
  print(ans);
  return 0;
}



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

char tile[100][100];
bool memo[100][100];

template <typename T>
void init(T a[100][100]) {
  for(int i = 0; i < 100; ++i) {
	for(int j = 0; j < 100; ++j) {
	  a[i][j] = 0;
	}
  }
}

void Step(char tile[100][100]) {
  int h = 0, w = 0;

  while(1) {
	if(memo[h][w] == 1) {
	  cout << "LOOP" << endl;
	  break;
	}
	
	// '>'??????????????\???????????????
	if(tile[h][w] == '>') {
	  memo[h][w] = 1;
	  w++;
	}
	// '<'??????????????\???????????????
	else if(tile[h][w] == '<') {
	  memo[h][w] = 1;
	  w--;
	}
	
	// '^'??????????????\???????????????
	else if(tile[h][w] == '^') {
	  memo[h][w] = 1;
	  h--;
	}

	// 'v'??????????????\???????????????
	else if(tile[h][w] == 'v') {
	  memo[h][w] = 1;
	  h++;
	}

	// '.'??????????????\???????????????
	else {
	  cout << w << " " << h << endl;
	  break;
	}
  }// END:while

}

int main() {
  int H, W;
  while(cin >> H >> W) {
	if(H == 0 && W == 0) break;

	init<bool>(memo);
	init<char>(tile);
	
	for(int i = 0; i < H; ++i) {
	  for(int j = 0; j < W; ++j) {
		cin >> tile[i][j];
	  }
	}
	
	Step(tile);
  }

  return 0;
}

Measured memory_bytes: 3000
#include <stdio.h>
#include <math.h>
int main(void){
    int i;
    double v,y,t;
    
    while(scanf("%lf",&v) !=EOF){
        t=v/9.8;
        y=4.9*t*t;
        
        i=1;
        while(5*(i-1)<y){
            i++;
        }
        
        printf("%d\n",i);
    }
    return 0;
}

Measured memory_bytes: 628
#include <bits/stdc++.h>
using namespace std;
int dp[2001] = {0};
const int mod = 1e9+7;
long long n;
long long solver(long long sum){
	if(sum > n) return 0;
	if(dp[sum] != -1) return dp[sum];
	if(sum == n) return 1;
	long long ans = 0;
	for(int i=3; i<=2000; ++i){
		ans += solver(sum+i);
		ans %= mod;
	}
	ans = (ans+mod)%mod;
	return dp[sum] = ans;
}
int main()
{
	for(int i=0; i<=2000; ++i) dp[i] = -1;
	scanf("%lld", &n);
	printf("%lld\n", solver(0));
}


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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
//ll MOD = 1000000007;
ll MOD = 998244353;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

template<class Abel> struct UnionFind {
    vector<int> par;
    vector<int> rank;
    vector<Abel> diff_weight;

    UnionFind(int n = 1, Abel SUM_UNITY = 0) {
        init(n, SUM_UNITY);
    }

    void init(int n = 1, Abel SUM_UNITY = 0) {
        par.resize(n); rank.resize(n); diff_weight.resize(n);
        for (int i = 0; i < n; ++i) par[i] = i, rank[i] = 0, diff_weight[i] = SUM_UNITY;
    }

    int root(int x) {
        if (par[x] == x) {
            return x;
        }
        else {
            int r = root(par[x]);
            diff_weight[x] += diff_weight[par[x]];
            return par[x] = r;
        }
    }

    Abel weight(int x) {
        root(x);
        return diff_weight[x];
    }

    bool issame(int x, int y) {
        return root(x) == root(y);
    }

    bool merge(int x, int y, Abel w) {
        w += weight(x); w -= weight(y);
        x = root(x); y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y), w = -w;
        if (rank[x] == rank[y]) ++rank[x];
        par[y] = x;
        diff_weight[y] = w;
        return true;
    }

    Abel diff(int x, int y) {
        return weight(y) - weight(x);
    }
};

signed main()
{   
    gearup;
    ll n,m; cin >> n >> m;
    UnionFind<ll> uf(n);
    rep(i,m){
        ll l,r,d; cin >> l >> r >> d;
        l--;r--;
        if(uf.issame(l,r)){
            if(uf.diff(l,r) != d){
                out("No");
                return 0;
            }
        }
        else uf.merge(l,r,d);
    }
    out("Yes");
}


Measured memory_bytes: 1792
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
s = input()

search = [
["S"]+["_"]*(N-1), 
["S"]+["_"]*(N-1), 
["W"]+["_"]*(N-1),
["W"]+["_"]*(N-1)
]

if s[0] == "o":
	search[0][1] = "S"
	search[0][-1] = "S"
	search[1][1] = "W"
	search[1][-1] = "W"
	search[2][1] = "W"
	search[2][-1] = "S"
	search[3][1] = "S"
	search[3][-1] = "W"
else:
	search[0][1] = "S"
	search[0][-1] = "W"
	search[1][1] = "W"
	search[1][-1] = "S"
	search[2][1] = "W"
	search[2][-1] = "W"
	search[3][1] = "S"
	search[3][1] = "S"

for lis in search:
	for i in range(N):
		# print(i, lis)
		if s[i] == "o" and lis[i] == "S":
			if lis[(i+1)%N] != "_" and lis[i-1] != lis[(i+1)%N]:
				break
			if lis[(i+1)%N] == "_":
				lis[i+1] = lis[i-1]
		elif s[i] == "x" and lis[i] == "S":
			if lis[(i+1)%N] != "_" and lis[i-1] == lis[(i+1)%N]:
				break
			if lis[(i+1)%N] == "_":
				if lis[i-1] == "W":
					lis[i+1] = "S"
				else:
					lis[i+1] = "W"

		elif s[i] == "o" and lis[i] == "W":
			if lis[(i+1)%N] != "_" and lis[i-1] == lis[(i+1)%N]:
				break
			if lis[(i+1)%N] == "_":
				if lis[i-1] == "W":
					lis[i+1] = "S"
				else:
					lis[i+1] = "W"
			
		elif s[i] == "x" and lis[i] == "W":
			if lis[(i+1)%N] != "_" and lis[i-1] != lis[(i+1)%N]:
				break
			if lis[(i+1)%N] == "_":
				lis[i+1] = lis[i-1]

	else:
		print(*lis, sep="")
		break
else:
	print(-1)


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

int main() {
  int A, B, sum = 0, cal = 1;
  cin >> A >> B;
  for (;;) {
    if (B <= cal) {
      break;
    }
    cal += A;
    cal -= 1;
    ++sum;
  }
  ++cal;
  cout << sum << endl;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-

S = int(input())

def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = S  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

#print(cmb(n, r, p))

ans = 0
for i in range(S//3):
    ans += cmb(S - (i+1)*2 - 1, i, p)
    ans %= p
print(ans)

Measured memory_bytes: 65416
#include <iostream>
#include <numeric>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
ll Max(ll(a), ll(b), ll(c)) {
	return max(max(a, b), c);
}
ll Min(ll(a), ll(b), ll(c)) {
	return min(min(a, b), c);
}





int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll> A(N);
	rep(i, N) {
		ll p;
		cin >> p;
		A.at(p - 1)++;
	}
	sort(A.begin(), A.end());
	reverse(A.begin(), A.end());
	
	rep(i, K) {
		N -= A.at(i);
	}
	cout << N << endl;

}


Measured memory_bytes: 1792
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

ll calc(ll x,ll y){
	if(y == 0){
		return x;
	}else{
		return calc(y,x%y);
	}
}

ll N,D,X;
ll dp[2001][2001],next_dp[2001];

void func(){

	if(X == 1){
		printf("0\n");
		return;
	}

	ll ans = 0;
	ll D_C_day;
	ll array[N],ruisekiwa[N];

	for(int i = 0; i <= N; i++){
		for(int k = 0; k <= N; k++)dp[i][k] = 0;
	}

	for(int i = 0; i <= N; i++){
		ruisekiwa[i] = 0;
	}

	dp[0][0] = 1;

	for(int eat_day = 1; eat_day <= N; eat_day++){

		if(eat_day != 1){

			array[eat_day-1] = (D-(eat_day-1));
			ll divisor = eat_day;

			while(divisor != 1){

				for(int i = 0; i < eat_day; i++){

					ll common;
					if(array[i] >= divisor){
						common = calc(array[i],divisor);
					}else{
						common = calc(divisor,array[i]);
					}

					array[i] /= common;
					divisor /= common;

					if(divisor == 1)break;
				}
			}

			D_C_day = 1;

			for(int i = 0; i < eat_day; i++){
				D_C_day *= array[i]%MOD;
				D_C_day %= MOD;
			}

			D_C_day %= MOD;

		}else{ //eat_day == 1;
			array[0] = D;
			D_C_day = D%MOD;
		}

		for(int i = 0; i <= N; i++){
			ruisekiwa[i] = dp[eat_day-1][i];
		}

		for(int i = 1; i <= N; i++){
			ruisekiwa[i] += ruisekiwa[i-1];
		}

		for(int num = 1; num <= N; num++){

			if(num-(int)(X-1)-1 < 0){
				next_dp[num] = ruisekiwa[num-1];
			}else{
				next_dp[num] = (ruisekiwa[num-1]-ruisekiwa[num-(int)(X-1)-1]);
			}
		}
		for(int i = 1; i <= N; i++){
			dp[eat_day][i] += next_dp[i];
			dp[eat_day][i] %= MOD;
		}

		ans += ((dp[eat_day][N]%MOD)*(D_C_day%MOD))%MOD;
		ans %= MOD;
	}

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

int main(){

	while(true){
		scanf("%lld %lld %lld",&N,&D,&X);
		if(N == 0 && D == 0 && X == 0)break;

		func();
	}

	return 0;
}

Measured memory_bytes: 34500
#include <iostream>
#include "bits/stdc++.h"
using namespace std;
#define print(x) cout<<x<<endl;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a) for(int i=0;i<a;i++)
#define debug int debug = 0;
#define RREP(i,a) for(int i=a-1;i>=0;i--)
#define rrep(i,a,b) for(int i=a-1;i>=b;i--)
#define printall(n,array) {for(int i=0;i<n;i++){cout<<array[i]<<" ";}cout<<endl;}
#define U() cout<<endl;
typedef long long ll;
typedef pair<int, int> PI;
typedef pair<int, PI> V;
typedef vector<int> VE;
const ll mod = 1000000007; //10^9+7

int main(){
    ll n, m, ans;
    cin >> n >> m;
    if(n > 1 && m > 1){
        ans = (n - 2) * (m - 2);
    }else if(n + m == 2){
        ans = 1;
    }else{
        ans = max(n, m) - 2;
    }
    print(ans);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <utility>
using namespace std;
typedef long long ll;
 
bool graph[8][8];
int dfs(int v, int n, bool visited[8]){
	bool all_visited = true;
	for (int i = 0;i < n;i++){
		if (visited[i]==false) all_visited = false;
	}
 
	if (all_visited == true) return 1;
	int ret = 0;
	for (int i=0;i<n;++i){
		if (graph[v][i]==false) continue;
		if (visited[i]) continue;
		visited[i] = true;
		ret += dfs(i,n,visited);
		visited[i] = false;
	}
    return ret;
}
 
int main(){
	int n,m;
	cin >> n >> m;
	for (int i=0;i<m;i++){
		int a, b;
		cin >> a >> b;
		graph[a-1][b-1] = graph[b-1][a-1] = true;
	}
	bool visited[8];
	for (int i = 0;i < n;i++){
		visited[i]=false;
	}
	visited[0] = true;
	cout << dfs(0, n, visited) << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+100;
const int P = 1e9+7;
#define fr(i,a,b) for(int i = a;i <= b; ++i)
#define nfr(i,a,b) for(int i = a;i >= b; --i)

inline int pow_mod(int x,int k){
   int res = 1,base = x;
   while(k){
      if(k&1)res = 1LL*res*base%P;
      k >>= 1; base = 1LL*base*base%P;
   }
   return res;
}

inline void add(int &x,int y){
   x += y; if(x >= P)x -= P;
}

struct segment_tree{
   int val[N*20],ch[N*20][2];
   int cnt;
#define lc ch[x][0]
#define rc ch[x][1]
#define mid (l+r)/2
   inline int newnode(){
      ++cnt; ch[cnt][0] = ch[cnt][1] = val[cnt] = 0;
      return cnt;
   }
   inline void modify(int &x,int l,int r,int pos,int v){
      if(!x)x = newnode();
      add(val[x],v);
      if(l == r)return ;
      if(pos <= mid)modify(lc,l,mid,pos,v);
      else modify(rc,mid+1,r,pos,v);
   }
   inline int merge(int x,int y,int l,int r){
      if(x*y == 0)return x|y;
      int pre = x;
      x = newnode();
      add(val[x] = val[pre],val[y]);
      if(l == r)return x;
      lc = merge(ch[pre][0],ch[y][0],l,mid);
      rc = merge(ch[pre][1],ch[y][1],mid+1,r);
      return x;
   }
   inline int query(int x,int l,int r,int ql,int qr){
      if(ql > r || qr < l)return 0;
      if(ql <= l && r <= qr){
         return val[x];
      }
      int res = 0;
      add(res = query(lc,l,mid,ql,qr),query(rc,mid+1,r,ql,qr));
      return res;
   }
   inline int qid(int x,int l,int r,int ql,int qr){
      if(ql > r || qr < l)return 0;
      if(ql <= l && r <= qr){
         return x;
      }
      return qid(lc,l,mid,ql,qr)+qid(rc,mid+1,r,ql,qr);
   }
}s;

int h,l[N],n;
int rt[N],L[N],R[N];
int prod[N],inv[N];
int lb,rb;

void init(){
   scanf("%d",&h);
   n = (1<<h);

   fr(i,1,n-1)rt[i] = s.newnode();
   lb = n/2,rb = n-1;
   fr(i,n/2,n-1){
      scanf("%d",l+i);
      l[i] += n/2-1;
   }

   prod[1] = inv[1] = 1;
   fr(i,2,n-1){
      prod[i] = 1LL*prod[i/2]*i%P;
      inv[i] = pow_mod(prod[i],P-2);
      inv[i] = 1LL*inv[i]*inv[i]%P;
   }

   nfr(i,n-1,1){
      if(i >= n/2){
         s.modify(rt[i],lb,rb,l[i],1LL*prod[i]*prod[l[i]]%P);
         L[i] = R[i] = i;
      } else {
         rt[i] = s.merge(rt[i<<1],rt[i<<1|1],lb,rb);
         L[i] = L[i<<1]; R[i] = R[i<<1|1];
      }
   }

   int ans = 0;
   fr(i,n/2,n-1){
      for(int j = i;j > 1;j /= 2){
         int cj = (j == (j/2)*2) ? j+1 : j-1;

         int k = 1;
         int kid = rt[cj];
         while(k != l[i]){
            int ck = 0;
            if(l[i] >= L[k<<1|1])ck = 1;
            int qv = s.val[s.ch[kid][ck^1]];
            add(ans,1LL*qv*
                  inv[j/2]%P*inv[k]%P*prod[i]%P*prod[l[i]]%P*(j/2)%P*k%P);
            k = (k<<1|ck); kid = s.ch[kid][ck];
         }
      }
   }
   printf("%d\n",1LL*ans*pow_mod(2,P-2)%P);
}

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


Measured memory_bytes: 63244
#include <cstdio>
#include <vector>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int n,T,s,a,b,dp[3001],ans;
vector<int> t,v;

int main(){
	scanf("%d%d%d",&n,&T,&s);
	rep(i,n){
		scanf("%d%d",&a,&b);
		v.push_back(a);t.push_back(b);
	}
	rep(i,t.size()){
		for(int j = T; j >= 0; j--){
			if((j<s&&j+t[i]>s)||j+t[i]>T)continue;
			dp[j+t[i]]=max(dp[j+t[i]],dp[j]+v[i]);
		}
	}
	rep(i,T+1)ans=max(ans,dp[i]);
	printf("%d\n",ans);
}

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

using namespace std;
using llint = long long;

using pint = pair<string,int>;

int n;
vector<pint> s1;
vector<pint> s2;

void bubblesort(vector<pint> &s,int size){
    for(int i = 0; i < size; i++){
        for(int j = i + 1; j < size; j++){
            if(s[i].first == s[j].first){
                if (s[i].second < s[j].second)
                {
                    pint tmp = s[i];
                    s[i] = s[j];
                    s[j] = tmp;
                }
                
            } else if (s[i].first > s[j].first){
                pint tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
            }
        }
    }
}

int main() {
    cin >> n;

    s1.resize(n);
    s2.resize(n);

    for (int i = 0; i < n; ++i) {
        cin >> s1.at(i).first >> s1.at(i).second;
    }

    for (int i = 0; i < n; ++i) {
        s2.at(i) = s1.at(i);
    }


    bubblesort(s1, n);

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (s1.at(i).first == s2.at(j).first && s1.at(i).second == s2.at(j).second)
            {
                cout << j+1 << endl;
            }
        }
    }


}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MAX 100005
using namespace std;
 
int main(){
  long long n, m, a[MAX], sum = 0;
  scanf("%lld", &n);
  for(int i = 0; i < n; i++){
    scanf("%lld", &a[i]);
    sum += a[i];
  }
  if(sum%(n*(n+1)/2)) return 0*puts("NO");
  m = sum/(n*(n+1)/2);
  a[n] = a[0];
  for(int i = 0; i < n; i++){
    long long k = m + a[i] - a[i+1];
    if(k < 0 || k % n) return 0*puts("NO");
  }
  puts("YES");
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int,int>;
#define rep(i,n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1LL << 60;
int main(){
    int n,m;
    cin >> n >> m;
    rep(i,m){
        int a;
        cin >> a;
        n-=a;
    }
    int ans = n;
    if(ans<0) ans = -1;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3644
/************************
*                       *
* Nothing Is Impossible *
*                       *
************************/
#include <algorithm>
#include <iostream>
#include <fstream>
#include <ctype.h>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <map>
#define GetRand(Min, Max) ((rand()%(int)(((Max) + 1)-(Min))) + (Min))
#define Rep(i, min, max) for (int i = min; i < max; ++i)
#define PB push_back
#define MP make_pair
typedef long long ll;
typedef long double ld; 
using namespace std;

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

	int w, h, a, b;
	cin >> h >> w >> a >> b;
	Rep(i,0,h)
	{
		Rep(j,0,w)
		{
			if(i < b && j < a || i >= b && j >= a)
			{
				cout << "1";
			}
			else
			{
				cout << "0";
			}
		}
		cout << endl;
	}
		return 0;
	}

Measured memory_bytes: 1280
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<bitset>
using namespace std;
typedef long long LL;
const int N=1e3;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
struct P{ int x,y; inline bool operator < (const P &b) const { return x==b.x?y<b.y:x<b.x; } }p[N];
inline P operator - (const P &a,const P &b) { return (P){a.x-b.x,a.y-b.y}; }
inline int operator * (const P &a,const P &b) { return a.x*b.y-a.y*b.x; }
const int mod=998244353;
inline bool line(int a,int b,int c) { return !((p[b]-p[a])*(p[c]-p[a])); }
int qp[N];
int main()
{
	int n=gi(),i,j,k,s,ans=n+1;

	for (i=qp[0]=1;i<=n;i++) {
		p[i].x=gi(),p[i].y=gi();
		qp[i]=qp[i-1]*2%mod;
	}
	
	sort(p+1,p+1+n);
	for (i=1;i<n;i++)
		for (j=i+1;j<=n;j++) {
			for (k=1;k<j;k++)
				if (k!=i&&line(i,j,k)) break;
			if (k<j) continue;
			for (k=j+1,s=2;k<=n;k++) s+=line(i,j,k);
			(ans+=qp[s]-s-1)%=mod;
		}

	cout<<((LL)qp[n]-ans+mod)%mod;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std; 
int main()
{
	string S;
	cin >> S;
	bool easy = true;
	for (int i = 0; (size_t)i < S.size(); i++) {
		if ((i % 2 == 0 && S[i] == 'L') || (i % 2 == 1 && S[i] == 'R')) {
			easy = false;
		}
	}
 
	if (easy) {
		cout << "Yes" << endl;
	} else {
		cout << "No" << endl;
	}
 
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
#define REP(i,N) for(int i=0;i<N;i++)

int main(){
    int n; cin>>n;
    using Entry = pair<pair<string,int>,int>;
    vector<Entry> v;
    for(int i=0;i<n;i++){
        string s; int p;
        cin>>s>>p;
        v.push_back({{s,-p}, i+1});
    }
    sort(all(v),[](const Entry& a, const Entry& b)->bool{return a.first<b.first;});
    for(auto e:v){
        cout<<e.second<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
from collections import Counter


def solve(d, t):
    for ti, tc in t.items():
        if ti not in d:
            return False
        if d[ti] < tc:
            return False
    return True


input()
d = Counter(map(int, input().split()))
input()
t = Counter(map(int, input().split()))

print('YES' if solve(d, t) else 'NO')


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

using namespace std;

int main () {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	long long x;
	cin >> x;
	long long ans = x - 1;
	for (long long i = 2 ; i * i <= x ; ++ i) {
		if (x % i == 0) {
			long long j = x / i;
			ans = min (ans, i + j - 2);
		}
	}
	cout << ans;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#include <numeric>
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)

int N;
int a[202020];
vector<ll>dp(202020,inf);
int ans[202020];
vector<int>E[202020];

void dfs(int now, int p) {
	int idx = lower_bound(all(dp),a[now])-dp.begin();
	ll tmp = dp[idx];
	dp[idx] = a[now];
	int idx2 = lower_bound(all(dp),1e12) - dp.begin();
	ans[now] = idx2;
	fore(x, E[now]) {
		if (x != p) {
			dfs(x,now);
		}
	}
	dp[idx] = tmp;
}

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

	cin >> N;
	for (int i = 0; i < N; i++)cin >> a[i];

	for (int i = 0; i < N - 1; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;
		E[u].pb(v);
		E[v].pb(u);
	}
	dfs(0,-1);

	for (int i = 0; i < N; i++)puts(ans[i]);

	return 0;
}

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

int main(void){
  int i,j,n,l,k,q;
  int a[100][2], m[100][100];
  int *p;

  scanf("%d",&n);

  for( i=0 ; i<n ; i++ ){
    for( j=0 ; j<2 ; j++ ){
      scanf("%d",&a[i][j]);
    }
  }

  p = malloc(sizeof(int)*(n+1));

  p[0] = a[0][0];
  for( i=0 ; i<n ; i++ ){
    p[i+1] = a[i][1];
  }


  for( i=1 ; i<=n ; i++ ){
    m[i][i] = 0;
  }
  for( l=2 ; l<=n ; l++ ){
    for( i=1 ; i<= n-l+1 ; i++ ){
      j = i+l-1;
      m[i][j] = 1000000;
      for( k=i ; k<=j-1 ; k++ ){
	q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
	if( m[i][j] > q ){
	  m[i][j] = q;
	}
      }
    }
  }

  printf("%d\n",m[1][n]);

  return 0;
}

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

vector<vector<pair<int, int>>> G;
vector<int> ans;

void dfs(int now, int before, int color) {
  ans.at(now) = color;
  for (auto next : G.at(now)) {
    if (next.first == before) continue;
    if (next.second % 2 == 0) dfs(next.first, now, color);
    else dfs(next.first, now, 1-color);
  }
}

int main() {
  int N; cin >> N;
  G.assign(N, vector<pair<int, int>>());
  for (int i = 0; i < N-1; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    u--;
    v--;
    G.at(u).push_back(make_pair(v, w));
    G.at(v).push_back(make_pair(u, w));
  }
  ans.assign(N, 0);
  dfs(0, -1, 1);
  for (auto v : ans) cout << v << endl;
}


Measured memory_bytes: 8960
from collections import defaultdict
N, Q = map(int, input().split())
E = defaultdict(list)
for i in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
d = [0]*N
ok = [True]*N
cnt = [0]*N
for i in range(Q):
    p, x = map(int, input().split())
    cnt[p-1] += x
stack = [0]
while stack:
    p = stack.pop()
    d[p] += cnt[p]
    ok[p] = False
    for np in E[p]:
        if ok[np]:
            cnt[np] += cnt[p]
            stack.append(np)

print(*d)

Measured memory_bytes: 119256
<?php
fscanf(STDIN, "%d%d%d", $n, $m, $x);

for($i=0;$i<$n;$i++){
    $temp = explode(" ", trim(fgets(STDIN)));
    $book[$i] = $temp;
}
$ans = PHP_INT_MAX;
for($i=1;$i<=(pow(2,$n+1));$i++){
    $und = array_fill(1,$m,0);
    $cost = 0;
    for($j=0;$j<$n;$j++){
        if(($i & pow(2,$j)) > 0){
            foreach($book[$j] as $key => $value){
                if($key == 0){
                    $cost += $value;
                }else{
                    $und[$key] += $value;
                }
            }
        }
    }
    $ok = 1;
    foreach($und as $value){
        if($value < $x){
            $ok = 0;
            break;
        }
    }
    if($ok == 1){
        $ans = min($cost, $ans);
    }


}
if($ans === PHP_INT_MAX){
    echo -1;
}else{
    echo $ans;
}


Measured memory_bytes: 16148
public class Main {
	
	public void run(java.io.InputStream in, java.io.PrintStream out) {
		final java.util.Scanner sc = new java.util.Scanner(in);
		final char[] str = sc.next().toCharArray();
		final int q = sc.nextInt();
		
		for (int i = 0; i < q; ++i) {
			final String cmd = sc.next();
			
			if (cmd.equals("print")) {
				final int a = sc.nextInt();
				final int b = sc.nextInt();
				for (int j = a; j <= b; ++j) {
					out.print(str[j]);
				}
				out.println();
			} else if (cmd.equals("reverse")) {
				final int a = sc.nextInt();
				final int b = sc.nextInt();
				for (int j = a, k = b; j < k; ++j, --k) {
					final char t = str[j];
					str[j] = str[k];
					str[k] = t;
				}
			} else if (cmd.equals("replace")) {
				final int a = sc.nextInt();
				final int b = sc.nextInt();
				final char[] p = sc.next().toCharArray();
				for (int j = a; j <= b; ++j) {
					str[j] = p[j - a];
				}
			}
		}
		
		sc.close();
	}

	public static void main(String[] args) {
		(new Main()).run(System.in, System.out);
	}

}

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


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
st=int(sum(A)/len(A))
go=st+1
ans=10**9+1
for i in range(st,go+1):
  val=0
  for a in A:
    val+=(a-i)**2
  ans=min(ans,val)
print(ans)

Measured memory_bytes: 3064
#include<stdio.h>
int main(void) {
	char S[3], T[3];
	scanf("%s", S);
	scanf("%s", T);
	int count = 0, i;
	for (i = 0; i < 3; i++) {
		if (S[i] == T[i]) {
			count += 1;
		}
	}
	printf("%d",count);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
#define show(x) {for(auto i: x){cout << i << " ";} cout << endl;}
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
    int N;
    cin >> N;
    N ^= 1;
    cout << N << '\n';
    return 0;
    // ll, 0, -, 1i, for s&g, debug
}

Measured memory_bytes: 3616
#// Problem link : 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <unordered_map>
#include <queue>
#include <stack>
#include <cmath>
#include <functional>
#include <deque>
#include <bitset>
#include<bits/stdc++.h>
using namespace std;

#define ll long long int
#define F(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define F1(a,n) for(int i=1;i<=n;i++){cin>>a[i];}
#define P(a,n) for(int i=0;i<n;i++){cout<<a[i]<<' ';}cout<<endl;
#define P1(a,n) for(int i=1;i<=n;i++){cout<<a[i]<<' ';}cout<<endl;
#define NF(a,n,m) for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>a[i][j];}}
#define NF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];}}
#define PNF(a,n,m) for(int i=0;i<=n;i++){for(int j=0;j<m;j++){cout<<a[i][j]<<' ';}}cout<<endl;
#define PNF1(a,n,m) for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cout<<a[i][j]<<' ';}}cout<<endl;
int n;
double p[3001];
double dp[3001][3001];
double f(int i,int head)
{
	if(head==0)
	{
		return 1;
	}
	if(i==n)
	{
		return 0;
	}
	if(dp[i][head]>-1){return dp[i][head];}
	dp[i][head]=f(i+1,head-1)*p[i] + f(i+1,head)*(1-p[i]);
	return dp[i][head];
}
int main()
{
	cin>>n;
	memset(dp,-1,sizeof dp);
	for(int i=0;i<n;i++)
	{
		cin>>p[i];

	}

	cout<<fixed<<setprecision(10)<<f(0,(n+1)/2);
}

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

struct UnionFind {
    vector<int> par; // parent
    UnionFind(int N) {
        par = vector<int>(N, -1); // negative num is size
    }
    int root(int x) {
        return par[x] < 0 ? x : par[x] = root(par[x]);
    }
    int size(int x) {
        return -par[root(x)];
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;

        if (size(x) < size(y)) swap(x, y);
        par[x] += par[y];
        par[y] = x;
    }
};

int main() {
    int N, M;
    cin >> N >> M;
    int a[M], b[M];
    rep(i, M) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }
    
    UnionFind uni(N);
    vector<ll> ans(M);
    ans[M-1] = (ll)N * (N - 1) / 2;
    for (int i = M - 1; i >= 1; i--) {
        ans[i-1] = ans[i];
        if (!uni.same(a[i], b[i])) {
            ans[i-1] -= (ll)uni.size(a[i]) * uni.size(b[i]);
            uni.unite(a[i], b[i]);
        }
    }
    rep(i, M) cout << ans[i] << endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define rep1(i,n) for(int i=1;i<=(int)n;i++)
#define sp(n) cout << fixed << setprecision(n)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
using namespace std;
int main(void){
    map<int,int> mp;
    rep(i,3){
        int a;cin>>a;
        mp[a]++;
    }
    if(mp[5]==2&&mp[7]==1){
        cout<<"YES"<<endl;
    }else{
        cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
typedef long long ll;
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
void fast()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
}

int main()
{
    fast();
    int x,a,b;
    cin>>x>>a>>b;
    if(a%x==0||b%x==0)
    cout<<"OK\n";
    else if(x*((a/x)+1)>=a&&x*((a/x)+1)<=b)
        cout<<"OK\n";
    else
        cout<<"NG\n";

   
}

Measured memory_bytes: 3652
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include <queue>
#include <cstring>

#define pb push_back
#define p push

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ll long long

#define getI(a) scanf("%d",&a)
#define getII(a, b) scanf("%d%d",&a,&b)
#define getIII(a, b, c) scanf("%d%d%d",&a,&b,&c)
#define getL(a) scanf("%lld",&a)
#define getLL(a, b) scanf("%lld%lld",&a,&b)
#define getLLL(a, b, c) scanf("%lld%lld%lld",&a,&b,&c)
#define BEND(c) (c).begin(),(c).end()
#define BEND2(c) (c).rbegin(),(c).rend()
#define fi first
#define se second
#define pi 3.1415926535897932384626
#define getS(a) scanf("%s",a)
#define pfb(a) printf("%.10lf\n",a);
#define pfi(a) printf("%d",a);
#define pfii(a, b) printf("%d%d",a,b);
#define pfl(a) printf("%lld",a);
#define pfll(a, b) printf("%lld%lld",a,b);
#define pfd(a) printf("%.12lf\n",a);
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define endl "\n"

#define SIZE  ( int)(1e9 + 7)
#define MAXN (ll) ((1e6+5))
#define K 25
#define  ALPHABET_SIZE  26
//#define N (int)(1e5+10)
#define sag (sol|1)
#define sol (root<<1)
#define ort (bas+son)/2
#define INF (ll )1e18
#define int ll
using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vector<int>> vvi;
typedef vector<vector<pair<int,int>>> vvpi;
typedef vector<long long> vl;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
typedef vector<vi> graph ;



signed main ( ) {
    ll n ,k ;
    cin >> n >> k   ;
    vi vec ( n +1 );
    pair <ll , ll> mn (INF , 0);
    for (int i = 1; i <=n ; ++i) {
        cin >> vec[i];
        if (vec[i] < mn.fi) {
            mn.fi = vec[i];
            mn.se = i;
        }
    }
    ll res= 0 ;
    for (int j = mn.se; j <=n ; j +=(k-1) ) {
        while(vec[j]==mn.fi)j++;

        res++;
    }
    for (int l = mn.se;l >=1 ; l-=(k-1)) {
        while(vec[l]==mn.fi)l--;

        res++;
    }
    ll res2 = 0;
    for (int m = 1; m <=n ; m+=(k-1)) {
        while(vec[m] == mn.fi)m++;
        res2++;
    }
    cout << ceil( ((double)(n-1)) / (k-1));

}



















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

int main(){

    string s;
    cin>>s;

    if(s.at(0)==s.at(1)&&s.at(2)==s.at(3)&&s.at(0)!=s.at(2)
    || s.at(0)==s.at(2)&&s.at(1)==s.at(3)&&s.at(0)!=s.at(1)
    || s.at(0)==s.at(3)&&s.at(1)==s.at(2)&&s.at(0)!=s.at(1))

        cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
typedef long long ll;

#define MAX(x, y)	(((x) > (y))? (x) : (y))
#define MIN(x, y)	(((x) < (y))? (x) : (y))
#define ABS(x)		(((x) < 0)? (-1*(x)) : (x))
#define REPI(x,y)	for (i=(x);i<(y);i++)
#define REPJ(x,y)	for (j=(x);i<(y);i++)
#define MEMCLR(X)	memset((X),0,sizeof((X)))

using namespace std;

vector<int> s;
int i,j,N,x,ans;

int main() {
	cin >> N;
	
	REPI(0,N) {
		cin >> x;
		s.push_back(x);
	}
	
	sort(s.begin(),s.end());
	i = 0;
	while(i<N){
		x = s[i];
		j = 0;
		while(s[i]==x) {
          j++;
          i++;
        }
		cout << endl;
		if (j < x) ans += j;
		else if (j>x) ans += j-x;
	}
	  
	cout << (ans) << endl;
	
	return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

bool isPrime(int x);


int main() {
    int n;
    cin >> n;
    vector<int> nums;
    for(int i=0; i<n; ++i) {
        int x;
        cin >> x;
        nums.push_back(x);
    }

    int count = 0;
    for(int i=0; i<n; ++i) {
        if(isPrime(nums[i])) {
            count++;
        }
    }
    cout << count << endl;

    return 0;
}


bool isPrime(int x) {
    if(x == 2) {
        return true;
    }
    if(x < 2 || x % 2 == 0) {
        return false;
    }

    int i =3;
    while(i <= sqrt(x)) {
        if(x % i == 0) {
            return false;
        }
        i += 2;
    }
    return true;
}

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

int n;
string idccd, idop, tambah, idakhir;

int main (){
    cin>>idccd>>idop;
    n=idccd.length();
    tambah=idop [n];
    if (idccd+tambah==idop){
        cout<<"Yes"<<endl;
    }else {
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,a,b,c,d,e,f,g,h;
	while(cin>>n,n){
		while(n--){
			cin>>a>>b>>c>>d>>e>>f>>g>>h;
			cout<<a*e-b*f-c*g-d*h<<" "<<b*e+a*f+c*h-d*g<<" "<<a*g-b*h+c*e+d*f<<" "<<a*h+b*g-c*f+d*e<<endl;
		}
	}
}

Measured memory_bytes: 1160
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
const int N=2e5+5;
struct eg{int v,nx;}e[N<<1];int head[N],tot;
inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}
int c[N],mp[N],pv[N],pfv[N],n,sz;
void dfs(int u,int fa,int fv){mp[u]=fv,cmax(fv,u);go(u)if(v!=fa)dfs(v,u,fv);}
void find(int u,int fa,int lim){++sz;go(u)if(v!=fa&&v<lim)find(v,u,lim);}
void fsd(int u,int fa){
	go(u)if(v!=fa){
		fsd(v,u);
		if(v<mp[u]){
			if(mp[u]==mp[v])pv[u]+=pv[v]+1;
			else sz=0,find(v,u,mp[u]),pv[u]+=sz;
		}
		if(v<mp[fa]){
			if(mp[u]==mp[fa])pfv[u]+=pfv[v]+1;
			else sz=0,find(v,u,mp[fa]),pfv[u]+=sz;
		}
	}
//	printf("%d %d %d %d\n",u,mp[u],pv[u],pfv[u]);
}
void sdf(int u,int fa){
	c[u]=c[fa]+(u>mp[fa]?pv[u]+1:pv[u]-pfv[u]);
	go(u)if(v!=fa)sdf(v,u);
}
int main(){
//	freopen("testdata.in","r",stdin);
	scanf("%d",&n),mp[0]=-1;
	for(R int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs(1,0,0);
	fsd(1,0);
	sdf(1,0);
	fp(i,2,n)printf("%d%c",c[i]-1," \n"[i==n]);
	return 0;
}

Measured memory_bytes: 21120
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <cstdio>

using namespace std;

typedef long long ll;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)

int main(int argc, char **argv)
{
    int N;
    cin >> N;
    double x[N];
    string u[N];
    REP(i, N) cin >> x[i] >> u[i];

    ll sy = 0;
    double sb = 0;
    REP(i, N) {
        if (u[i] == "JPY") sy += (ll)(x[i]);
        else sb += x[i];
    }
    sb = sb * 380000 + (double)sy;
    cout << sb << endl;
    return 0;
}


Measured memory_bytes: 256