akhauriyash/Code-Regression huggingface dataset:
#include <set>
#include <string>
#include <vector>
#include <iostream>
using namespace std;

typedef long long ll;

#ifdef _MSC_VER
#define __builtin_popcount __popcnt
#endif

int n, m;
int main() {
	while (cin >> n >> m, n) {
		vector<int> a(n);
		for (int i = 0; i < n; i++) cin >> a[i];
		vector<set<ll> > dp(1 << n);
		dp[0] = set<ll>({ 0 });
		for (int i = 1; i < 1 << n; i++) {
			if (__builtin_popcount(i) > m) continue;
			for (int j = 0; j < n; j++) {
				if (i & (1 << j)) {
					for (int k : dp[i - (1 << j)]) {
						dp[i].insert(stoll(to_string(k) + to_string(a[j])));
					}
				}
			}
		}
		set<ll> ret;
		for (int i = 0; i < 1 << n; i++) {
			if (__builtin_popcount(i) == m) {
				ret.insert(dp[i].begin(), dp[i].end());
			}
		}
		cout << ret.size() << endl;
	}
	return 0;
}

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

#define MOD 1000000007

int64_t expotent(int64_t n,int64_t m){
  if (m == 1) return n;
  else if (m % 2 == 0) return expotent(n * n % MOD, m/2);
  else return expotent(n * n % MOD, m/2) * n % MOD;
}

int64_t nCr(int64_t n, int64_t r){
  int Ans = 1;  
  if (r > n / 2) r = n - r;
  for (int i = 1; i <= r; i++)
    Ans = Ans * (n + 1 - i) % MOD * expotent(i, MOD-2) %MOD;
  
  return Ans;
}

int main(){
  int64_t H, W, A, B;
  int64_t currentways = 1;
  int64_t ways = 0;
  
  cin >> H >> W >> A >> B;

  currentways = nCr(H+W-B-2, W-B-1);
  ways += currentways;
  for (int i = 1; i < H-A; i++){
    //ways += nCr(i+B-2, B-1) * nCr(H+W-i-B-1, W-B-1);  
    currentways = currentways * (i+B-1) % MOD * expotent(i, MOD-2) % MOD * (H-i) % MOD * expotent(H+W-i-B-1, MOD-2) %MOD;
    ways =(ways + currentways) % MOD;
  }
  
  cout << ways;
}

Measured memory_bytes: 3620
#include <algorithm>
#include <cstdlib>
#define REP(i,n) for(int i=0; i<(int)(n); i++)

#include <cstdio>
inline int getInt(){ int s; scanf("%d", &s); return s; }

#include <set>

using namespace std;

int main(){
  const int n = getInt();
  const int x = getInt();

  int ans = 1;
  REP(i,n){
    const int a = std::abs(getInt() - x);
    if(i == 0) ans = a;
    else ans = __gcd(ans, a);
  }

  printf("%d\n", ans);
  return 0;
}

Measured memory_bytes: 128
def is_perfect_power(n):
    return n in {
        1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144,
        169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512,
        529, 576, 625, 676, 729, 784, 841, 900, 961, 1000
    }


X = int(input())
for x in range(X, 0, -1):
    if is_perfect_power(x):
        print(x)
        break


Measured memory_bytes: 3060
#include <stdio.h>
#include <string.h>
char a[300];
int m[1000][3];
int main()
{
  int na,nb,nc,n,i,j,k,r,l;
  for(;;){
    scanf("%d%d%d",&na,&nb,&nc);
    if(na==0 && nb==0 && nc==0) break;
    memset(a,0,sizeof(a));
    memset(m,0,sizeof(m));
    l = 0;
    scanf("%d",&n);
    while(n-->0){
      scanf("%d%d%d%d",&i,&j,&k,&r);
      if(r==1){
	a[i-1] = 1; a[j-1] = 1; a[k-1] = 1;
      }else{
	m[l][0] = i-1; m[l][1] = j-1; m[l][2] = k-1;
	l++;
      }
    }
    while(--l>=0){
      if(a[m[l][0]] == 1 && a[m[l][1]] == 1) a[m[l][2]] = 2;
      else if(a[m[l][0]] == 1 && a[m[l][2]] == 1) a[m[l][1]] = 2;
      else if(a[m[l][1]] == 1 && a[m[l][2]] == 1) a[m[l][0]] = 2;
    }
    for(i=0;i<na+nb+nc;i++){
      switch(a[i]){
      case 0: printf("2\n"); break;
      case 1: printf("1\n"); break;
      case 2: printf("0\n"); break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

class Main{
    public static void main(String[] args){
	Scanner scan = new Scanner(System.in);
	int A = scan.nextInt();
	int B = scan.nextInt();
	int C = scan.nextInt();

	if(A+B >= C){
	    System.out.println("Yes");
	}else{
	    System.out.println("No");
	}
    }
}

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

int N;
vector<int> x;

using pint = pair<int,int>;
vector<int> po; // その場所に制約があるなら、そこに置かれる数、なければ 0
vector<int> con; // con[i] := i 番目の checkpoint についての数

int main() {
    int N; cin >> N;
    x.resize(N); for (int i = 0; i < N; ++i) cin >> x[i], --x[i];
    po.resize(N*N, 0);
    for (int i = 0; i < N; ++i) po[x[i]] = i + 1;
    con.clear();
    for (int i = 0; i < N*N; ++i) if (po[i]) con.push_back(po[i]);
    
    int iter = 0;
    vector<int> num(N+2, 0); // num[i] := 数 i を何個使ったか
    vector<int> res(N*N, 0);
    set<int> alr;
    bool ok = true;
    for (int i = 0; i < N*N; ++i) {
        if (!ok) break;
        if (po[i]) {
            if (num[po[i]] < po[i]-1) { ok = false; break; }
            res[i] = po[i];
            ++num[po[i]];
            alr.insert(po[i]);
        }
        else {
            while (iter < N && num[con[iter]] >= con[iter]-1) ++iter;
            if (iter == N) {
                int canuse = 1;
                while (canuse <= N && (!alr.count(canuse) || num[canuse] == N)) ++canuse;
                if (canuse == N + 1) { ok = false; break; }
                res[i] = canuse;
                ++num[canuse];
            }
            else {
                res[i] = con[iter];
                ++num[con[iter]];
            }
        }
    }
    
    if (!ok) puts("No");
    else {
        puts("Yes");
        for (int i = 0; i < N*N; ++i) cout << res[i] << " ";
        cout << endl;
    }
}

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

string s,a;
int x;

int main(){
	cin>>s;
	x=s.length();
	a="Yes";
	for(int i=0;i<=x/2-1;i++){
		if(s[i]!=s[x-i-1]){
			a="No";
		}
	}
	cout<<a<<endl;
}

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    vector<vector<int>> x(N), y(N);
    int s, t;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        for (int j = 0; j < A[i]; j++) {
            cin >> s >> t;
            s--;
            x[i].push_back(s);
            y[i].push_back(t);
        }
    }

    int ans = 0;
    for (int bit = 0; bit < (1<<N); bit++) {
        bool check = true;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            if (!(bit & (1<<i))) continue;
            cnt++;
            for (int j = 0; j < A[i]; j++) {
                if (((bit>>x[i][j]) & 1) != y[i][j]) check = false;
            }
        }
        if (check) ans = max(ans, cnt);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdlib.h>
using namespace std;
int cmp(const void *a,const void *b)
{
	return *(int*)a-*(int*)b;
}
int main()
{
	int N,i,a[3];
	cin>>N;
	for (i=0;i<N;i++)
	{
			cin>>a[0]>>a[1]>>a[2];
			qsort(a,3,sizeof(int),cmp);
			if (a[0]*a[0]+a[1]*a[1]==a[2]*a[2])
				//d[i]=1;
				cout<<"YES"<<endl;
			else
				cout<<"NO"<<endl;
				//d[i]=0;
			//i++;
	}
	return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
#ifdef _DEBUG
#include "debug.hpp"
#else
#define debug(...)
#endif
#define REP(i, m, n) for(int (i) = (m); (i) < (n); ++i)
#define rep(i, n) REP(i, 0, n)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const int INF = 1e9 + 7;
const ll LINF = 1LL << 60;
template <class T, class U>
inline bool chmax(T &a, const U &b) {
  if(a < b) {
    a = b;
    return true;
  }
  return false;
}
template <class T, class U>
inline bool chmin(T &a, const U &b) {
  if(a > b) {
    a = b;
    return true;
  }
  return false;
}

int n;
vector<int> g[100];

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  cin >> n;
  rep(i,n) {
    int u, k;
    cin >> u >> k;
    --u;
    rep(j,k) {
      int v;
      cin >> v;
      --v;
      g[u].push_back(v);
    }
  }
  queue<int> q;
  q.push(0);
  vector<int> dst(n, -1);
  dst[0] = 0;
  while(!q.empty()) {
    int v = q.front();
    q.pop();
    for(int u : g[v]) {
      if(dst[u] != -1) continue;
      dst[u] = dst[v]+1;
      q.push(u);
    }
  }
  rep(i,n) cout << i+1 << " " << dst[i] << '\n';
  return 0;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i, n) cin >> x.at(i);
    
    int minsum = 100100100;

    for(int i = 1; i <= 100; i++) {
        int sum = 0;
        rep(j, n) {
            sum += pow(x.at(j) - i, 2);
        }
        minsum = min(minsum, sum);
    }

    cout << minsum << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.*;
	import java.util.Map.Entry;
	 
	 
	 class Main {
//		 static int mod =  (int) (Math.pow(10,9)+7);
		 static int mod =  (int) 998244353;
		 static List<ArrayList<Integer>> list= new ArrayList<ArrayList<Integer>>();
		 public static void main(String[] args) {
	    	
	        Scanner sc = new Scanner(System.in);
	        int N = sc.nextInt();
	        long ans=0;
	        for(long i=1;i<N;i++) {
	        	for(long j=i;i*j<N;j++) {
	        		if(i==j)ans++;
	        		else ans=ans+2;
	        	}
	        }
	        
	        
	        System.out.println(ans);
		 }
	}


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

using namespace std;

int n;
double data[100005];

main()
{
  double up = 0;
  double ter;
  double min = 20000000000;
  double down;

  cin >> n;
  for ( int i = 0; i < n; i++) {
    cin >> data[i];
    data[i];

    if ( up < data[i] ){
      up = data[i];
    }
  }

  ter = up / 2.0;
  sort(data, data + n);

  for ( int i = 0; i < n; i++) {
    if ( fabs(data[i] - ter) < min) {
      min = fabs(data[i] - ter);
      down = data[i];
    }
  }

  printf("%.0lf %.0lf\n", up, down);

  return (0);
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <iterator>
#include <limits>
#include <numeric>
#include <utility>
#include <cmath>
#include <cassert>
#include <cstdio>

// #include <unordered_set>
// #include <unordered_map>

#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())

#define pb push_back
#define mp make_pair

int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}

typedef std::pair<int, int> P;
typedef long long ll;
typedef long double ld;

const int MOD = 1000000007;
const int INF = 1e9;
const ll LINF = INF * 1ll * INF;
const ld DINF = 1e200;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

using namespace std;

// #define int long long



signed main(){
  
    ios::sync_with_stdio(false);
    cin.tie(0);
	//cin高速化

	int r,g;
	cin>>r>>g;

	cout<<2*g-r<<endl;

 	return 0;

}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 2e5 + 7;
inline int lowbit(int x) {return x & -x;}
int n, h[MAXN];
ll dp[MAXN], a[MAXN];
void update(int x, ll v) {for (; x <= n; x += lowbit(x)) dp[x] = max(dp[x], v);}
ll query(int x) {ll res = 0; for (; x; x -= lowbit(x)) res = max(res, dp[x]); return res;}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), update(h[i], query(h[i] - 1) + a[i]);
    printf("%lld\n", query(n));
    return 0;
}

Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
#define MAX_N 1000000
ll inv[MAX_N], fac[MAX_N], finv[MAX_N];
void make() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i=2; i<MAX_N; i++) {
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    fac[i] = fac[i-1] * (ll)i % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}
ll perm(ll n, ll r) {
  if(n < 0)       return 0;
  else if(n < r)  return 0;
  else            return (fac[n] * finv[n-r]) % mod;
}
ll comb(ll n, ll r) {
  ll ans = 1;
  ans = perm(n, r); // n * (n-1) * ... * (n-r+1)
  ans = (ans * finv[r]) % mod; // フェルマーの小定理
  return ans;
}
int main() {
  int X, Y;
  cin >> X >> Y;
  int a = (2*Y-X)/3;
  int b = (2*X-Y)/3;
  if(a+2*b!=X || 2*a+b!=Y) cout << 0 << endl;
  else {
    make();
    cout << comb(a+b, max(a, b)) << endl;
  }
  return 0;
}


Measured memory_bytes: 23680
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long int;

int main(){
    int a, b, k; cin >> a >> b >> k;
    int cnt = k;
    while(true){
        a /= 2;
        b += a;
        cnt -= 1;
        if(cnt == 0){break;}
        b /= 2;
        a += b;
        cnt -= 1;
        if(cnt == 0){break;}
    }
    cout << a << " " << b << endl;
    return 0;
}

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

int main(){
	int a, b, c; cin >> a >> b >> c;
	if (a + b >= c) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

int main() {
string s;
int k=0,o=0;
  cin >> s;
  for (int i=0; i<s.size(); i++){
    if (s.at(i)=='0'){
      k+=1;
    } else {
      o+=1;
    }
  }
  cout << min(k,o)*2 << endl;
}


Measured memory_bytes: 512
/**
 *      ABC 55 B
 *      author  : kyomukyomupurin
 *      created : 2018-09-06 01:43:16
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int INF = 1000000000 + 7;
    long long power = 1;
    int N; cin >> N;
    for (int i = 1; i <= N; ++i) {
        power *= i;
        power %= INF;
    }
    cout << power << endl;

    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<stack>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<bitset>
#include<iomanip>
using namespace std;

typedef stack<int> IntStack;
typedef queue<int> IntQueue;

const double pi = 3.141592653589793;

/*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*//*ここまでテンプレ*/

int H, W, N;
char field[1005][1005];

queue<int> qh[10], qw[10];
int cou[10][1005][1005];

int dh[4] = { -1,0,0,1 };
int dw[4] = { 0,-1,1,0 };
char num[11] = "0123456789";

int serch(int t)
{
	while (qh[t - 1].size() > 0)
	{
		int h = qh[t - 1].front();
		int w = qw[t - 1].front();
		qh[t - 1].pop();
		qw[t - 1].pop();

		for (int i = 0; i < 4; i++)
		{
			int nh = min(max(h + dh[i], 0), H - 1);
			int nw = min(max(w + dw[i], 0), W - 1);
			if (nh == h && nw == w) continue;

			if (field[nh][nw] == num[t])
			{
				qh[t].push(nh);
				qw[t].push(nw);
				return cou[t - 1][h][w] + 1;
			}

			if (field[nh][nw] != 'X' && field[nh][nw] != num[t-1] && cou[t - 1][nh][nw] == 0)
			{
				qh[t - 1].push(nh);
				qw[t - 1].push(nw);
				cou[t - 1][nh][nw] = cou[t - 1][h][w] + 1;
			}
		}
	}

	return 100000000;
}

int main()
{	
	cin >> H >> W >> N;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> field[i][j];
			if (field[i][j] == 'S')
			{
				field[i][j] = '0';
				qh[0].push(i);
				qw[0].push(j);
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < N; i++)
	{
		ans += serch(i + 1);
	}

	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 39364
/*------------------------------------
........Bismillahir Rahmanir Rahim....
..........created by Abdul Aziz.......
------------------------------------*/
#include <bits/stdc++.h>
#define   int  long long 
#define   pb   push_back
#define   co(x)  cout << x << '\n' 
#define   sz(x)  (int)x.size()
#define   all(a) a.begin(),a.end() 
using namespace std;


bool cmp(int a,int b){
    return  ( a > b ) ; 
}

inline void solve(){
    int n, k, ans = 0 ; 
    cin >> n >> k ; // max(n,k) <= 100 
    vector <int> a(n+5);
    for (int i=0;i<n;i++) 
        cin >> a[i] ; 
    for (int  i=1 ; i <= min(n,k) ; i++) { 
        for (int j=0;j<=i;j++){
            int  l = j, r = i - j, cur = 0 ; 
            vector <int> hand;
            for (int  t = 0 ; t < l ; t++ ) {
                hand.pb( a[t] ) ; 
            }
            for (int  t = 0 ; t < r ; t++ ) { 
                hand.pb( a[n-t-1] ) ; 
            }
            sort(all(hand), cmp) ; 
            for (int  t=1 ; t <= k-i and sz(hand)>0 ; t++) { 
                if (hand.back()<0) hand.pop_back();
                else break;
            }
            for (auto &it: hand) cur += it ; 
            ans = max(ans, cur) ; 
        }
    }
    co (ans) ; 
}

//problem link: https://atcoder.jp/contests/abc128/tasks/abc128_d 

signed main()
{
    int n=1; // cin>>n;
    while (n--) solve();
    return 0;
}


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

int main(){
    string s, t; cin >> s >> t;

    sort(s.begin(), s.end());
    sort(t.begin(), t.end(),greater<int>());

    put((s < t ? "Yes":"No"));
}

Measured memory_bytes: 256
import heapq
from collections import defaultdict

def dijkstra(i, V, E, INF=1e9):
    D = [INF for v in V]
    D[i] = 0
    Q = [(d, v) for v, d in enumerate(D)]
    heapq.heapify(Q)
    prev = [None for v in V]

    while len(Q) > 0:
        du, u = heapq.heappop(Q)
        for v, (duv, *_) in E[u].items():
            dv = du + duv
            if D[v] > dv:
                D[v] = dv
                prev[v] = u
                heapq.heappush(Q, (dv, v))
    return prev

def count_path(prev, E):
    x = [(i, p) for i, p in enumerate(prev)]
    while len(x) > 0:
        i, p = x.pop()
        if p is not None:
            E[i][p][-1] += 1
            E[p][i][-1] += 1
            x.append((p, prev[p]))
    return E

n, m = map(int, input().split())
E_list = [list(map(int, input().split())) for _ in range(m)]
E = defaultdict(dict)
for j in range(m):
    a, b, c = E_list[j]
    E[a][b] = [c, 0]
    E[b][a] = [c, 0]
V = list(range(n + 1))

for i in range(1, n + 1):
    prev = dijkstra(i, V, E)
    E = count_path(prev, E)

ans = 0
for v1 in E.values():
    for v2 in v1.values():
        ans += (v2[-1] == 0)
print(ans // 2)


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

using LL = long long;

#define ALL(a) begin((a)), end((a))
#define FOR(i, a, b) for (int(i) = (a); (i) < (b); (i)++)
#define RFOR(i, a, b) for (int(i) = (a); (i) > (b); (i)--)
#define debug(x) cout << #x << " : " << x << '\n'

const int INF = 1e9;

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

  int ans;
  int N, A, B;
  cin >> N >> A >> B;

  if (A * N <= B) {
    ans = A * N;
  } else {
    ans = B;
  }

  cout << ans << '\n';

  return 0;
}

Measured memory_bytes: 256
N,M = map(int,input().split())
X = [int(i) for i in input().split()]
X.sort()
X_intvl = [0 for i in range(M-1)]

#print(X)

for i in range(1,M):
    X_intvl[i-1] = X[i] - X[i-1]

#print(X_intvl)

X_intvl.sort(reverse=True)

#print(X_intvl)

print(sum(X_intvl[N-1:]))


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

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

using namespace std;
const int INF = 1 << 30;
const long long MOD = 1000000000 + 7;

// 最小公約数
long long gcd(long long a, long long b) {
	if (a % b == 0)return(b);
	else return(gcd(b, a % b));
}

// 最小公倍数
long long lcm(long long a, long long b) {
	return a * b / gcd(a, b);
}

int main() {
	long long A, B, C, D; cin >> A >> B >> C >> D;
	long long range = B - A + 1;
	long long ans = range;
	long long div = C;
	long long num = B / div - (A + div - 1) / div + 1;
	ans -= num;
	div = D;
	num = B / div - (A + div - 1) / div + 1;
	ans -= num;
	div = lcm(C, D);
	num = B / div - (A + div - 1) / div + 1;
	ans += num;

	cout << ans;

}

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

int main() {
    int N;
    cin >> N;
    priority_queue<int> p;
    rep(i,N) {
        int a;
        cin >> a;
        p.push(a);
    }
    int S = 0;
    while (true) {
        S += p.top(); p.pop();
        if (p.empty()) break;
        S -= p.top(); p.pop();
        if (p.empty()) break;
    }
    cout << S << endl;
}


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

using namespace std;

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

// container util
#define all(x) (x).begin(), (x).end()

// debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x)                                         \
  cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
       << " " << __FILE__ << endl;

// typedef
typedef long long lint;
typedef unsigned long long ull;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

// constant
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
const int ddx[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[] = {1, 1, 0, -1, -1, -1, 0, 1};

// conversion
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
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 main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int a, b, c;
  cin >> a >> b >> c;
  if (a + b + c <= 21)
    puts("win");
  else
    puts("bust");

  return 0;
}

Measured memory_bytes: 256
import sys
A=range(12)
m=[[0 for i in A] for j in A]
def f(y,x):
    f=0
    if m[y][x]==1:
        m[y][x]=c
        f=1
    return f
def LR(y,x,dx):
    P=[]
    x+=dx
    while 0<=x<12 and m[y][x]!=0:
        if f(y,x):P+=[(y,x)]
        x+=dx
    return P
def UD(y,x,dy):
    P=[]
    y+=dy
    while 0<=y<12 and m[y][x]!=0:
        if f(y,x):P+=[(y,x)]
        y+=dy
    return P
def v1(buf):
    f=0
    while len(buf)>0:
        f=1
        y,x=buf.pop()
        m[y][x]=c
        buf+=LR(y,x,-1)+LR(y,x,1)+UD(y,x,-1)+UD(y,x,1)
    return f
def solve():
    global c
    c=2
    for i in A:
        x=m[i]
        while x.count(1)>0:
            v1([(i,x.index(1))])
            c+=1
    return c-2

y=0
for s in sys.stdin:
    if y<12:
        x=0
        for e in map(int,list(s[:-1])):
            m[y][x]=e
            x+=1
        y+=1
    else:
        print solve()
        y=0
print solve()

Measured memory_bytes: 4324
using System;
using System.Collections.Generic;
class Program{
	const int mod=1000000007;
	static void Main(){
		string s=Console.ReadLine();
		int e=int.Parse(Console.ReadLine());
		int n=s.Length;
		long ans=0;
		int[,,] dp=new int[n+1,2,e];
		dp[0,0,0]=1;
		for(int i=0;i<n;i++){
			for(int j=0;j<2;j++){
				for(int l=0;l<e;l++){
					int lm=j==0?s[i]-'0':9;
					for(int d=0;d<=lm;d++){
						dp[i+1,(j==1||d<lm)?1:0,(l+d)%e]+=dp[i,j,l];
						dp[i+1,(j==1||d<lm)?1:0,(l+d)%e]%=mod;
					}
				}
			}
		}
		for(int j=0;j<2;j++){ans+=dp[n,j,0];}
		Console.WriteLine((ans-1+mod)%mod);
	}
}

Measured memory_bytes: 18528
main(n,r){for(;scanf("%d",&n),n;printf("%d\n",r)){n=1000-n;for(r=0;n/500;r++)n-=500;for(;n/100;r++)n-=100;for(;n/50;r++)n-=50;for(;n/10;r++)n-=10;for(;n/5;r++)n-=5;for(;n;r++)n--;}return 0;}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 5e6+5;
const ll inv2 = 500000004;
int main()
{
    string a;
    cin>>a;
    if(a.length()<6) puts("No");
    else if(a[2]==a[3]&&a[4]==a[5]) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
using ll = long long;

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

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

  if (n >= 10)
    cout << r << '\n';
  else
    cout << r + 100 * (10 - n) << '\n';
  return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<string>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int main(){
  int i,j;
  int a[100][100],b[100][100],n;
  int mn,mx;
  while(cin>>n&&n){
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
	cin>>a[j][i];
    memset(b,0,sizeof(b));
    for(i=0;i<n;i++){
      mn=0;
      mx=0;
      for(j=1;j<n;j++){
	if(a[mn][i]>a[j][i])
	  mn=j;
	if(a[i][mx]<a[i][j])
	  mx=j;
      }
      for(j=0;j<n;j++){
	if(a[mn][i]==a[j][i])
	  b[j][i]++;
	if(a[i][mx]==a[i][j])
	  b[i][j]++;
      }
    }
    for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	if(b[j][i]>1)
	  break;
      }
      if(j!=n)
	break;
    }
    if(i==n)
      cout<<0<<endl;
    else
      cout<<a[j][i]<<endl;
  }
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
using namespace std;
int main(){
  int n;
  string s;
  cin>>n>>s;
  long long r=0,g=0,b=0;
  for(auto c:s){
    if(c=='R') ++r;
    else if(c=='G') ++g;
    else ++b;
  }
  long long all=r*g*b;
  long long sub=0;
  for(int i=0;i<n;++i){
    for(int j=i+1;j<n;++j){
      if(s[i]==s[j]) continue;
      int k=j*2-i;
      if(k>=n||s[k]==s[i]||s[k]==s[j]) continue;
      ++sub;
    }
  }
  cout<<all-sub<<endl;
}


Measured memory_bytes: 3604
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>

using namespace std;
typedef long long ll;

int gcd(int x, int y) {
  if (x < y) swap(x, y);
  while (y > 0) {
    int r = x % y;
    x = y;
    y = r;
  }
  return x;
}

/*迷路
const int INF = 50;

typedef pair<int,int> P;
char field[52][52];
int d[51][51];
int r,c;
int sx,sy;
int gx,gy;

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

int bfs(){
    queue<P> que;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            d[i+1][j+1] = INF;
        }
    }
    que.push(P(sy,sx));
    d[sy][sx]=0;
while(que.size()){
    P p=que.front();
    que.pop();
    if(p.second==gx&&p.first==gy) break;
    for(int i=0;i<4;i++){
        int nx=p.second+dx[i];
        int ny=p.first+dy[i];

        if(1<=nx&&nx<=c&&1<=ny&&ny<=r&&field[ny][nx]!='#'&&d[ny][nx]==INF){
            que.push(P(ny,nx));
            d[ny][nx] = d[p.first][p.second] + 1;
        }
    }
}
return d[gy][gx];
}
*/

int main(){
  int n,m;
  cin>>n>>m;
  int l[m],r[m];
  for(int i = 0;i<m; i++) cin>>l[i]>>r[i];
  int min= 0;
  int max = 1000000;
  for(int i = 0; i<m; i++){
      if(l[i]>min) min = l[i];
      if(r[i]<max) max = r[i];
  }
  if(max-min<0) cout<<0<<endl;
  else cout<<max-min+1<<endl;
  return 0;
}


Measured memory_bytes: 1024
import java.util.*;

public class Main {

    long INF = Long.MAX_VALUE;

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

    void solve() {
        Scanner sc = new Scanner(System.in);
        long N = sc.nextLong();
        long X = sc.nextLong();
        long A = N + ans(N - X, X);
        System.out.println(A);
    }

    long ans(long a, long b) {
        if (a == 0) {
            return -b;
        }
        return 2 * (b / a) * a + ans(b % a, a);
    }
}


Measured memory_bytes: 23124
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		while(scan.hasNext()){
			int hit = 0;
			int blow = 0;
			int[] aNums = new int[4];
			int[] bNums = new int[4];
			for(int i = 0; i < 4; i++){
				aNums[i] = scan.nextInt();
			}
			for(int i = 0; i < 4; i++){
				bNums[i] = scan.nextInt();
			}
			for(int i = 0; i < 4; i++){
				for(int j = 0; j < 4; j++){
					if(aNums[i] == bNums[j]){
						if(i == j){
							hit++;
						} else{
							blow++;
						}
					}
				}
			}
			System.out.printf("%d %d\n", hit, blow);
		}
	}
}

Measured memory_bytes: 25952
nii=lambda:map(int,input().split())
lnii=lambda:list(map(int,input().split()))

x,y=nii()

for i in range(x+1):
  turu=2*i
  kame=4*(x-i)
  if turu+kame==y:
    print('Yes')
    exit()

print('No')

Measured memory_bytes: 9180
import itertools

n = int(input())
an_list = []
xy_list = []
for _ in range(n):
  an_list.append(int(input()))
  xy_list.append([list(map(int, input().split())) for __ in range(an_list[-1])])

#print(an_list)
#print(xy_list)

max_honest = 0

h_or_u = [0, 1]
for i in itertools.product(h_or_u, repeat=n):
  honest = []
  unkind = []
  for j in range(n):
    if i[j] == 1:
      honest.append(j+1)
      for k in range(an_list[j]):
        if xy_list[j][k][1] == 1:
          honest.append(xy_list[j][k][0])
        else:
          unkind.append(xy_list[j][k][0])
    else:
      unkind.append(j+1)
  b = 0
  for l in set(honest):
    if l in unkind:
      b += 1
  if b == 0:
    max_honest = i.count(1)
  #print(honest)
  #print(unkind)
    

print(max_honest)

Measured memory_bytes: 3064
using System;

namespace Rainy
{
    class Program
    {
        static void Main(string[] args)
        {
            string inD0 = Console.ReadLine();

            int NumR = 0;
            int MaxNumR = 0;

            for (int i = 0; i < 3; i++ ){
                if (inD0.Substring(i, 1)=="R")
                {
                    NumR+=1;
                    if (MaxNumR <= NumR) MaxNumR = NumR;
                }
                else
                {
                    NumR = 0;

                }
            }
            Console.WriteLine(MaxNumR);
        }
    }
}


Measured memory_bytes: 25960
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	ll n; cin >> n;
	vector<ll> a(n);
	for( auto &k : a ) cin >> k;
	ll ans = 0;
	for( int i = 0; i < 61; ++i ){
		ll nll = 0, eins = 0;
		for( int k = 0; k < n; ++k ){
			if( a[k] & (1ll<<i) ) ++eins;
			else ++nll;
		}
		ans += (1ll<<i)%mod * ((n*(n-1)/2-max(0ll, eins*(eins-1)/2)-max(0ll, nll*(nll-1)/2))%mod);
		ans %= mod;
	}
	cout << ans << endl;
}

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

using namespace std;

#define sz(a) static_cast<int>((a).size())
#define f first
#define s second
#define els(v) for (auto &el : (v))


#ifdef KIRYA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) {
    cerr << _s << " = " << _h << "\n";
}

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

const int64_t INF = static_cast<int64_t>(1e9) + 7;
const int64_t LINF = INF * INF;
const int MAXN = static_cast<int>(1e6) + 17;

void solve() {
    int m, d;
    cin >> m >> d;
    int res = 0;
    for (int i = 1; i <= m; ++i) {
        for (int j = 22; j <= d; ++j) {
            int d1 = j / 10, d2 = j % 10;
            if (d1 >=2 && d2 >= 2 && d1 * d2 == i) {
                ++res;
            }
        }
    }
    cout << res << '\n';
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int q = 1;

    for (int i = 0; i < q; ++i) {
        solve();
    }
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
//#define int long long

signed main(){
    int n, t, a;
    cin >> n >> t >> a;
    int ans_h = INT_MAX, ans = 0;
    rep(i,n){
        int h; cin >> h;
        if(abs(t-h*0.006-a) < abs(t-ans_h*0.006-a)){
            ans_h = h; ans = i+1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main(){
    int s, w;
    cin >> s >> w;
    if ( s <= w ) {
        cout << "unsafe" << endl;
    }
    else {
        cout << "safe" << endl;
    }
    return 0;
}


Measured memory_bytes: 3624
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

/*--- Macro ---*/
#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 mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

/*---  Type ---*/
typedef long long ll;

/*--- Constants ---*/
template <typename T> const T INF = numeric_limits<T>::max() / 10;
const int MOD = (int)1e9 + 7;

// Floating
const double EPS = 1e-11;
#define EQ0(x) (abs(x) < EPS)
#define EQ(x, y) (abs(a-b) < EPS)

// Util
int max(int a, int b, int c) {return max(a, max(b, c));}
int min(int a, int b, int c) {return min(a, min(b, c));}
ll max(ll x, ll y) {return x > y ? x : y;}
ll min(ll x, ll y) {return x < y ? x : y;}
ll max(ll a, ll b, ll c) {return max(a, max(b, c));}
ll min(ll a, ll b, ll c) {return min(a, min(b, c));}

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



int main() {
  int n;
  cin >> n;
  vector< vector<int> > f;
  f.assign(n, vector<int>(10, 0));
  rep(i, n) {
    rep(j, 10) {
      cin >> f[i][j];
    }
  }
  vector< vector<int> > p;
  p.assign(n, vector<int>(11, 0));
  rep(i, n) {
    rep(j, 11) {
      cin >> p[i][j];
    }
  }

  // bit全探索
  ll ans = -INF<ll>;
  rep(i, (1 << 10)) {
    if(i == 0) continue; // 必ず1つ以上の日で営業する
    ll tmp_p = 0;
    // 店ごとに被り数を求め、利益を出す
    rep(j, n) {
      int cnt = 0;
      rep(k, 10) {
        if( (f[j][k]==1) && (((i>>k)&1)==1) ) cnt++;
      }
      tmp_p += p[j][cnt];
    }
    ans = max(ans, tmp_p);
  }
  cout << ans << endl;

  return 0;
}

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

void SME(int W,int H,int x,int y,int r);

int main(){
    int W,H,x,y,r;
    cin>>W>>H>>x>>y>>r;
    SME(W,H,x,y,r);
    return 0;
}

void SME(int W,int H,int x,int y,int r){
    if(0<=x-r && x+r<=W && 0<=y-r && y+r<=H){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}






Measured memory_bytes: 3124
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

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

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 4000+5;

int n;
string s;
int F[N][3];

int main(){
	ri(n);
	cin >> s;
	map<char, int> id;
	id['R'] = 0;
	id['G'] = 1;
	id['B'] = 2;
	for(int i=1; i<=s.size(); i++){
		for(int j=0; j<3; j++) F[i][j] = F[i-1][j];
		F[i][id[s[i-1]]] += 1;
	}
	ll ans = 0LL;
	for(int i=0; i<n; i++){
		for(int k=i+3; k<n; k++){
			if(s[i] != s[k]){
				int want = 3^id[s[i]]^id[s[k]];
				ans += F[k+1][want] - F[i][want];
				if((i + k) % 2 == 0){
					if(id[s[(i + k) / 2]] == want) ans -= 1;
				}
			}
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<29;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

class Graph{
	private:
	int n;
	vvi g;
	int lv=20;
	vi rank;
	vvi Par;
	void LCA_dfs(int v,int t){
		rank[v]=t;
		for(auto u:g[v]) if(rank[u]==-1){
			Par[0][u]=v;
			LCA_dfs(u,t+1);
		}
	}
	public:
	void LCA_Prepare(){
		rank=vi(n,-1);
		Par=vvi(lv,vi(n));
		Par[0][0]=-1;
		LCA_dfs(0,0);
		for(int i=1;i<lv;i++) for(int j=0;j<n;j++){
			if(Par[i-1][j]<0) Par[i][j]=-1;
			else Par[i][j]=Par[i-1][Par[i-1][j]];
		}
	}
	int LCA(int s,int t){
		if(rank[s]>rank[t]) swap(s,t);
		for(int i=0;i<lv;i++) if((rank[t]-rank[s])>>i&1) t=Par[i][t];
		if(s==t) return s;
		for(int i=lv-1;i>=0;i--) if(Par[i][s]!=Par[i][t]){
			s=Par[i][s];
			t=Par[i][t];
		}
		return Par[0][s];
	}
	Graph(int v){
		n=v;
		g=vvi(v);
	}
	void add_edge(int s,int t){
		g[s].push_back(t);
		g[t].push_back(s);
	}
	int dis(int u,int v){
		return rank[u]+rank[v]-2*rank[LCA(u,v)];
	}
};

int n;
vvi a;

int main(){
	cin>>n;
	a=vvi(n);
	Graph g(n);
	for(int i=1;i<n;i++){
		int x;
		cin>>x;
		x--;
		g.add_edge(x,i);
		a[x].push_back(i);
	}
	g.LCA_Prepare();
	queue<int> q;
	q.push(0);
	ll res=0,pre=0;
	for(int i=0;i<n;i++){
		int v=q.front();q.pop();
		res+=g.dis(pre,v);
		pre=v;
		for(auto u:a[v]) q.push(u);
	}
	cout<<res<<endl;
}


Measured memory_bytes: 24616
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);

  char c[5][5];

  for(int i=0;i<3;i++)scanf(" %s", c[i]);

  printf("%c%c%c\n", c[0][0], c[1][1], c[2][2]);

  return 0;
}



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

using namespace std;

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

#define int ll

int c[12];
int a[12][12];

main(){
	int n,m,x;
	cin >> n >> m >> x;
	for(int i=0;i<n;i++){
		cin >> c[i];
		for(int j=0;j<m;j++){
			cin >> a[i][j];
		}
	}

	int ans = 1e10;
	for(int i=0;i<(1 << n); i++){
		int sum = 0;
		int s[12]={0};
		for(int j=0;j<n;j++){
			if(((i&(1<<j))>>j)){
				sum += c[j];
				for(int k=0;k<m;k++) s[k] += a[j][k];
			}
		}
		bool ok = true;
		for(int j=0;j<m;j++){
			if(s[j]<x) ok = false;
		}
		if(ok){
			ans = min(ans, sum);
		}
	}

	if(ans == 1e10){
		cout << "-1" << endl;
	}else{
		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MOD	1000000007
#define int	long long
#define pii pair<int,int> 
#define vi vector<int>
using namespace std;

int power(int a, int b){ int S = 1; while(b--)S *= a; return S;}

int32_t main(){
	int n, r;
	int s = 0;
	cin >> n >> r;
	while(n / r != 0){
		s++;
		n /= r;
	}
	cout << s+1;

	return 0;
}



Measured memory_bytes: 256
def resolve():
    N, K = list(map(int, input().split()))
    ans = 0
    mini = sum(range(K))
    maxi = sum(range(N, N-K, -1))
    for i in range(K, N+2):
        ans += maxi - mini + 1
        ans %= 10**9+7
        mini += i
        maxi += N - i
    print(ans)        


if '__main__' == __name__:
    resolve()


Measured memory_bytes: 69336
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using ll = long long;
using ld = long double;
using namespace std;
const int INF = 1e9+100;
const ll INF64 = 7e18l;
const int mod = 1000000007;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define ALL(a) (a).begin(), (a).end()
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);


int main(){
    FIN;
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin >> a[i];

    ll ans = 1;
    while(n > (k-1)*ans+1) ans++;

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


Measured memory_bytes: 3964
N=int(input())
A=[0]
for i in range(1,N+1):
    A.append(int(input()))

ans=0
i=1
while i<=N:
    # print(i)
    # print(A[1:])
    if A[i]>=2:
        ans+=A[i]//2
        A[i]%=2
    # print(A[1:])
    if i<N and A[i]==1 and A[i+1]>=1:
        ans+=1
        A[i]-=1
        A[i+1]-=1
    # print(A[1:])
    # print(ans)
    i+=1

print(ans)

Measured memory_bytes: 50648
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=2*acos(0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}

ll bit[800010];
ll u;
void bitinit(ll n){
    ll y=1;
    rep(i,0,69){
        
        if(y>=n){
            u=y;
            break;
        }
        y*=2;
    }
    fill(bit,bit+u+10,0);
}
void add(ll n,ll x){
    ll i=n;
    bit[i]+=x;
    bit[i]%=mod;
    while(i<u){
        i+=i&(-i);
        bit[i]+=x;
        bit[i]%=mod;
    }
}
ll sum(ll n){
    ll i=n;
    ll ret=0;
    while(i>0){
        ret+=bit[i];
        i-=i&(-i);
        ret%=mod;
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    string s;cin>>s;
    int cnt[26];
    fill(cnt,cnt+26,0);
    rep(i,0,s.size()){
        cnt[s[i]-'a']++;
    }
    int y=0;
    int num;
    rep(i,0,26){
        y+=cnt[i]%2;
        if(cnt[i]%2==1)num=i;
    }
    if(y>1){
        cout<<-1<<endl;
        return 0;
    }
    int now[26];
    rep(i,0,26)now[i]=cnt[i];
    vector<int> v;
    rep(i,0,s.size()){
        int u=s[i]-'a';
        if(now[u]>=2){
            v.push_back(u);
            now[u]-=2;
        }
        if(v.size()==s.size()/2)break;
    }
    if(s.size()%2==1)v.push_back(num);
    rep(i,(s.size()+1)/2,s.size()){
        v.push_back(v[s.size()-i-1]);
    }
    //rep(i,0,v.size())cout<<v[i]<<" ";
    //return 0;
    queue<int> q[26];
    rep(i,0,s.size()){
        q[s[i]-'a'].push(i+1);
    }
    vector<int> w;
    rep(i,0,s.size()){
        w.push_back(q[v[i]].front());
        q[v[i]].pop();
    }
    bitinit(200010);
    ll ans=0;
    rep(i,0,w.size()){
        ans+=i-sum(w[i]);
        add(w[i],1);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 7180
//
//  main.cpp
//  atCoder_D
//
//  Created by 박다원 on 24/03/2019.
//  Copyright © 2019 박다원. All rights reserved.
//

#include <iostream>
#include <cstring>

using namespace std;



using ll = long long;

ll cache[5][5][5][100005];
const ll MOD = 1e9 + 7;


enum
{
    NON,
    A,
    G,
    C,
    T
};

ll Solve(int pre1, int pre2, int pre3, int remain)
{
    if(remain == 0)
        return 1;
    
    ll& ret = cache[pre1][pre2][pre3][remain];
    if(ret != -1)
        return ret;
    
    ret = 0;
    
    for(int i = 1; i <= 4; i++)
    {
        if(pre2 == A && pre3 == G && i == C)
            continue;
        
        if(pre2 == G && pre3 == A && i == C)
            continue;
        
        if(pre2 == A && pre3 == C && i == G)
            continue;
        
        if(pre1 == A && pre3 == G && i == C)
            continue;
        
        if(pre1 == A && pre2 == G && i == C)
            continue;
        
        ret += Solve(pre2, pre3, i, remain-1);
        ret %= MOD;
    }
    
    return ret;
}

int main(int argc, const char * argv[])
{
    int num;
    cin >> num;
    
    memset(cache, -1, sizeof(cache));
    cout << Solve(0, 0, 0, num) << endl;
    return 0;
}


Measured memory_bytes: 97920
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    char s[101];
    int k,i;
    cin>>k;
    cin>>s;
    int len=strlen(s);
    if(len>k)
    {
        for(i=0;i<k;i++)
            cout<<s[i];
        cout<< "..."<<endl;
    }
    else
    {
        cout<<s<<endl;
    }
}

Measured memory_bytes: 3104
// finish date: 2018/07/23
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for(int (i)=a;(i)<(b);(i)++)
#define rep(i, n)  FOR(i,0,n)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<double> vd;
typedef vector<vector<double>> vvd;
typedef vector<vector<vector<double>>> vvvd;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef vector<vector<char>> vvc;
typedef pair<int, int> pii;
typedef pair<ll, int> pli;
typedef pair<ll, pair<int, int>> plii;
const int bigmod = 1000000007;
const int INF = 1050000000;
const long long INFll = 100000000000000000;


int main() {
    int N;
    cin >> N;
    vi D(N);
    rep(i, N) cin >> D[i];
    sort(D.begin(), D.end());
    if (D[0] == 0) {
        cout << 0 << endl;
        return 0;
    }
    int ans = 0;
    FOR(s, 1, 13) {
        vb used(24, false);
        used[0] = true;
        rep(i, N) {
            bool flg = false;
            for (int j = -s + 1; j <= s - 1; j++) {
                if (used[(D[i] + j + 24) % 24]) {
                    flg = true;
                    break;
                }
                if (j == s - 1) used[D[i]] = true;
            }
            if (flg) {
                for (int j = -s + 1; j <= s - 1; j++) {
                    if (used[(-D[i] + j + 24) % 24]) {
                        cout << s - 1 << endl;
                        return 0;
                    }
                    if (j == s - 1) used[(24 - D[i]) % 24] = true;
                }
            }
        }
    }
    cout << 12 << endl;
    
    return 0;
}



Measured memory_bytes: 256