akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

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

#define pb push_back
#define rep(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, n) for(int i = a; i < (n); i++)
#define mod (ll)(1e9+7)
#define int ll
#define INF 100000000

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

ll x[101], y[101];
signed main() {
	ll n, k;
  cin >> n >> k;
  rep(i, n) cin >> x[i] >> y[i];
  set<int> xx, yy;
  rep(i, n) xx.insert(x[i]);
  rep(i, n) yy.insert(y[i]);
  ll ans = -1;
  for(auto sx : xx) {
    for(auto sy : yy) {
      for(auto tx : xx) {
        for(auto ty : yy) {
          if (sx <= tx && sy <= ty) {
            ll sum = (tx - sx) * (ty - sy);
            ll c = 0;
            rep(i, n) {
              if(sx <= x[i] && x[i] <= tx && sy <= y[i] && y[i] <= ty) c++;
              if (k <= c) {
                if (ans < 0) ans = sum;
                ans = min(ans, sum);
              }
            }
          }
        }
      }
    }
  }
  cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<cstring>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll mod1=998244353;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  string tmp1, tmp2, tmp3;
  cin>>tmp1>>tmp2>>tmp3;
  cout<<"A"<<tmp2[0]<<"C"<<endl;
}



Measured memory_bytes: 3632
#include <iostream>

using namespace std;

int main(){
	long long h;
	cin >> h;
	
	h /= 2;
	long long count = 1;
	
	long long i = 1;
	
	while(h > 0){
		h /= 2;
		count += 2 * i;
		i *= 2;
	}
	
	cout << count << endl;
	
}

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

void solve(long long X)
{
    ll deposit = 100;
    ll ans = 0;
    while (deposit < X) {
        ans++;
        deposit += deposit / 100;
    }
    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
// clang-format off
int main(){
    long long X;
    scanf("%lld",&X);
    solve(X);
    return 0;
}


Measured memory_bytes: 3724
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;

int arr[101] = {0};

int main()
{
	int a, b;
	cin >> a >> b;
	if(a>b)
	{
		cout << "safe";
	}
	else
	{
		cout << "unsafe";
	}
}



Measured memory_bytes: 3528
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        char[] c = new char[1200];
        String str;

        //while((str = br.readLine()) != null){
            str = br.readLine();
            int l = str.length();

            for(int i = 0; i<l; i++){
                c[i] = str.charAt(i);
                
                if(c[i] >=65 && c[i] <= 90){
                    c[i] += 32;
                }else if(c[i] >= 97 && c[i] <=122){
                    c[i] -= 32;
                }
                System.out.print(c[i]);
            }
           System.out.print("\n");
            
       // }
   
    }
}


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

int main() {
  int N;
  std::cin >> N;
  std::vector<int> v(N);
  for (int i = 0; i < N; i++) std::cin >> v[i];
  std::sort(v.begin(), v.end());
  double a = static_cast<double>(v[0]);
  for (int i = 1; i < N; i++) {
    a = (a + static_cast<double>(v[i])) / 2;
  }
  std::cout << a << std::endl;
  return 0;
}


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

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 T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> P;
typedef long long ll;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define REVERSE(c) reverse((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);
const int INT_INF = 2147483647;
const long long LL_INF = 1LL<<60;
const long long MOD = 1000000007;

#define CLR(a) memset((a), 0 ,sizeof(a))

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

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

int main(void){
    int N,K; cin >> N >> K;
    VI xp, xm;
    xp.push_back(0);
    REP(i,N){
        int x; cin >> x;
        if(x >= 0) xp.push_back(x);
        else xm.push_back(x);
    }
    xm.push_back(0);
    REVERSE(xm);
    int ans = INT_INF;
    REP(i,K+1){
        int kp = min(i, (int)xp.size()-1), km = K-kp;
        if(km < xm.size()) chmin(ans, 2*xp[kp] - xm[km]);
        
        km = min(i, (int)xm.size()-1); kp = K-km;
        if(kp < xp.size()) chmin(ans, -2*xm[km] + xp[kp]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll> 
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) (a).begin(),(a).end()
#define rep(i,n) for(ll (i)=0; (i)<(n); ++(i))
#define print(a) cout << (a) << endl

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,k,ans=0;cin>>n>>k;
  lvector A(n,0);rep(i,n) cin>>A[i];
  lvector visited(n+1,0),route;
  route.emplace_back(1);visited[1]++;
  ll pos=0,val=0;
  for(ll i=1;i<=n;++i) {
    route.emplace_back(A[route[i-1]-1]);
    if(visited[A[route[i-1]-1]]==0) visited[A[route[i-1]-1]]=1;
    else {
      pos=i;
      val=route[i];
      break;
    }
  }
  if(k>=route.size()) {
    ll pos_l=0;
    while(route[pos_l]!=val) pos_l++;
    if(pos!=pos_l) {
      k-=pos_l;k%=(pos-pos_l);
      ans=route[pos_l+k];
    }
    else ans=route[pos_l];
  }
  else ans=route[k];
  print(ans);
  return 0;
}


Measured memory_bytes: 8456
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1000000007;

ll pd[200010];
ll rd[200010];
ll Ep(int x, int y){
  if(y == 0) return 1;
  if(y == 1) return x;
  ll r = Ep(x,y/2);
  if(y%2 == 1) return r *r%MOD *x%MOD;
  else return r *r%MOD;
}
ll Ftl(ll x){
  if(x == 1 || x == 0) return 1;
  if(pd[x] != 0) return pd[x];
  return pd[x] = Ftl(x-1) *x%MOD;
}
ll invFtl(ll x){
  if(x == 1 || x == 0) return 1;
  if(rd[x] != 0) return rd[x];
  return rd[x] = invFtl(x-1)*Ep(x,MOD-2)%MOD;
}
ll comb(ll m, ll n){
  if(m < n) return 0;
  return Ftl(m) *invFtl(n)%MOD *invFtl(m-n)%MOD;
}

int main(){
  int n, k;
  cin >> n >> k;
  ll ans = 0;
  int nk = min(k, n-1);
  for(int i=0; i<=nk; ++i){
    ans += comb(n,i) *comb(n-1,i) %MOD;
    ans %= MOD;
  }
  cout << ans << endl;
}

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

typedef long long LL;

LL N;

int arr[300010];
LL max_sum_before[300010];
LL min_sum_after[300010];

priority_queue<int, vector<int>, greater<int> > pq_min;
priority_queue<int, vector<int>, less<int> > pq_max;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> N;
    
    LL sz = N * 3;
    //arr.push_back(0);
    for(int i = 1; i <= sz; ++i) {
        cin >> arr[i];
        //arr.push_back(num);
    }
    
    LL sum = 0;
    for(int i = 1; i <= N; ++i) {
        sum += arr[i];
        max_sum_before[i] = sum;
        pq_min.push(arr[i]);
    }

    for(int i = N+1; i <= sz-N; ++i) {
        pq_min.push(arr[i]);
        max_sum_before[i] = max_sum_before[i-1] + arr[i] - pq_min.top();
        pq_min.pop();
    }

    sum = 0;
    for(int i = sz; i > sz - N; --i) {
        sum += arr[i];
        min_sum_after[i] = sum;
        pq_max.push(arr[i]);
    }
    
    

    for(int i = sz-N; i > N; --i) {
        // cout << "i: " << i << endl;
        pq_max.push(arr[i]);
        min_sum_after[i] = min_sum_after[i+1] + arr[i] - pq_max.top();
        // cout << "i: " << i << " m_sum i+1: " << min_sum_after[i+1]
        //      << " pq_top: " << pq_max.top() << " arr i: " << arr[i] << endl;
        pq_max.pop();
    }

    // for(int i = 1; i <= sz; ++i) {
    //     cout << max_sum_before[i] << " ";
    // }
    // cout << endl;
    // for(int i = 1; i <= sz; ++i) {
    //     cout << min_sum_after[i] << " ";
    // }
    // cout << endl;

    

    LL res = max_sum_before[N] - min_sum_after[N+1];

    for(int i = N+1; i <= sz - N; ++i) {
        res = max(res, max_sum_before[i] - min_sum_after[i+1]);
    }

    cout << res << endl;
        
    return 0;
}


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

int main()
{
    std::string str;
    std::cin >> str;
    long long sum = 0, i = 0,j=0;
    for (auto&& c : str) {
        if (c == 'W') {
          	sum += (i-j);
          	j++;
        }
        i++;
    }
    std::cout << sum << "\n";
    return 0;
}

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

int main() {
	int a,b,c;
	for(a = 1;a <= 9;a++) {
		for(b = 1;b <= 9;b++) {
			c = a * b;
			cout << a << "x" << b << "=" << c << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1116
#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <string.h>

using namespace std;

int qsort_int_compare_descend(const void *a,const void *b){
    long long c = *(long long*)a - *(long long*)b;
    if(c>0){ return -1;}
    else if(c<0){ return 1; }
    return 0;
}
void descendOrder(long long size,long long *array){//ko-jun
    qsort(array,size,sizeof(long long),qsort_int_compare_descend);
}

int main(){
    long long N,K;
    cin >> N;
    cin >> K;
    long long size = N*(N+1); size /= 2;
    long long *a = new long long[N];
    for(long long i=0;i<N;i++){
        cin >> a[i];
    }
    long long *s = new long long[size];
    
    long long k = 0;
    for(long long i=0;i<N;i++){
        long long sum = 0;
        for(long long j=i;j<N;j++){
            sum += a[j];
            s[k] = sum;
            k++;
        }
    }
    descendOrder(size, s);
    
    long long n = 1;
    for(int i=0;i<40;i++){ n*=2; }
    long long max=0;
    while(n>0){
        max += n;
        long long count = 0;
        for(long long i=0;s[i]>=max;i++){
            if((s[i]&max)==max){
                count++;
            }
        }
        if(count<K){
            max -= n;
        }
        n/=2;
    }
    
    cout << max << endl;
    
    delete[] a;
    delete[] s;
    return 0;
}


Measured memory_bytes: 8060
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
 
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
 
        List<String> list = new ArrayList<>();
 
        for (int i = 0; i < count; ++i)
            list.add(scanner.next());
 
        if (list.stream().distinct().count() < list.size()) {
            System.out.println("No");
            return;
        }
 
        boolean isSuccess = true;
        for (int i = 1; i < list.size(); ++i) {
            if (!list.get(i).startsWith("" + list.get(i - 1).toCharArray()[list.get(i - 1).length() - 1])) {
                isSuccess = false;
                break;
            }
        }
 
        if (isSuccess)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}

Measured memory_bytes: 27092
// by Balloons
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define mpr make_pair
#define debug() puts("okkkkkkkk")
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
 
using namespace std;
 
typedef long long LL;
 
const int inf = 1 << 30;
LL ans=0;
 
LL gd(LL x,LL y){
//	if(x==1 && y==1)return 2333;
	if(!y)return ans-=x,x;
	if(x<y)swap(x,y);
	ans+=x/y*y*2;
//	printf("%lld %lld %lld  %lld\n",x,y,ans,x/y*y*2);
	return gd(y,x%y);
}
 
int main(){
	LL n,x;cin>>n>>x;
	ans=n;
	gd(max(n-x,x),min(n-x,x));
	printf("%lld\n",ans);
 
	return 0;
}

Measured memory_bytes: 256
n,x,y=map(int,input().split())
l=[]
for i in range(n-1):
  for j in range(i+1,n):
    d1=j-i
    d2=abs((x-1)-i)+abs(j-(y-1))+1
    d=min(d1,d2)
    l.append(d)
import collections
c=collections.Counter(l)
for kk in range(1,n):
  print(c[kk])

Measured memory_bytes: 73212
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;

int main(){
	int ad, angle, angle_sum = 0;
	double x = 0, y = 0;
	while(1){
		scanf("%d,%d", &ad, &angle);
		if(ad == 0 && angle == 0) break;
		x += (double)ad * sin(angle_sum * M_PI / 180.0);
		y += (double)ad * cos(angle_sum * M_PI / 180.0);
		angle_sum += angle;
	}
	cout << (int)x << endl << (int)y << endl;
	return 0;
}

Measured memory_bytes: 1212
import sys
stdin = sys.stdin
from itertools import accumulate, groupby
mod = 10**9 + 7

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))


H, W = na()
if H == 1 or W == 1:
    print(1)
elif H % 2 != 0 and W % 2 != 0:
    print(H * W // 2 + 1)
else:
    print(H * W // 2)


Measured memory_bytes: 3060
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function eval(a::Tuple{Int,Int,Int},b::Tuple{Int,Int,Int})
	if a[2]<b[2]
		1
	elseif a[2]==b[2]
		0
	else
		-1
	end
end

function hpush(h::Array{Tuple{Int,Int,Int},1},x::Tuple{Int,Int,Int})
	push!(h,x)
	if length(h) > 1
		l = length(h)
		k = l>>1
		while eval(x,h[k])==1&&k>=1
			tmp = h[k]
			h[k] = x
			h[l] = tmp
			k = max(k>>1,1)
			l = l>>1
		end
	end
end

function hpop(h::Array{Tuple{Int,Int,Int},1})
	x = h[1]
	z = pop!(h)
	if !isempty(h)
		h[1] = z
		k = 1
		l = length(h)
		while k <= l
			if 2*k>l
				break
			elseif 2*k+1>l
				if eval(h[2*k],z)>=0
					break
				else
					tmp = h[2*k]
					h[2*k] = z
					h[k] = tmp
					k = 2*k
				end
			else
				if eval(z,h[2*k])>=0&&eval(z,h[2*k+1])>=0
					break
				else
					t = eval(h[2*k],h[2*k+1])>=0 ? 2*k : 2*k+1
					tmp = h[t]
					h[t] = z
					h[k] = tmp
					k = t
				end
			end
		end
	end
	x
end

function main()
	n,m = readline() |> split |> parseMap
	e = [Int[] for i in 1:n]
	for i in 1:m
		s,t = readline() |> split |> parseMap
		push!(e[s],t)
		push!(e[t],s)
	end
	dis = -ones(Int, length(e))
	ans = zeros(Int,n)
	h = Array{Tuple{Int,Int,Int},1}()
	push!(h,(1,0,1))
	while !isempty(h)
		v,w,x = hpop(h)
		if dis[v]<0||w<dis[v]
			dis[v] = w
			ans[v] = x
		end
		for i in e[v]
			if dis[i]<0||dis[i]>w+1
				dis[i] = w+1
				ans[i] = v
				hpush(h,(i,w+1,v))
			end
		end
	end
	println("Yes")
	for i in 2:n
		println(ans[i])
	end
end

main()

Measured memory_bytes: 238468
#include <bits/stdc++.h>
using namespace std;
int main(){
long long A,V,B,W,T;
  cin>>A>>V>>B>>W>>T;
 long long kyori=abs(B-A);
  long double sokudo=V-W;
if(kyori==0){
cout<<"YES";
}
  else if(sokudo==0){
  cout<<"NO";
  }
  else if(kyori <=  sokudo *T){
 cout<<"YES";
 }
  else{
  cout<<"NO"<<endl;
  }
}

Measured memory_bytes: 3636
def get_divisors(n):
    """
    引数の数字の約数を列挙し、setで返します。1および引数自身を含みます。
    計算量はO(log(n))です。
    """
    divisors = set()
    i = 1
    while i * i <= n:
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
        i += 1
    return divisors


n = int(input())

n_ = get_divisors(n)
n_1 = get_divisors(n - 1)
n_.remove(1)
n_1.remove(1)
n_.difference_update(n_1)
# print(n_)
# print(n_1)
# print(n_.difference(n_1))
ans = len(n_1)
for cand in n_:
    if cand == 2 or cand == n:
        ans += 1
        continue
    tmp = n
    while tmp % cand == 0:
        tmp //= cand
    tmp %= cand
    if tmp == 1:
        ans += 1
print(ans)


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

using namespace std;

int N, a[100009];

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%d", &N);
for (int i=1; i<=N; i++)
    scanf ("%d", &a[i]);
sort (a + 1, a + N + 1), reverse (a + 1, a + N + 1);
int x = 0;
a[0] = a[1];
while (a[x + 2] > x + 1 && x + 1 < N) x ++;
///x, x e punctul sa vedem cate sunt in stanga, cate sunt in dreapta
int right = 0, up = 0, k;
k = x;
while (x < a[k] && k <= N) right ++, k ++;
up = a[x + 1] - x, right --;
//printf ("x=%d\n%d %d\n", x, up, right);
if (up % 2 == 1 && right % 2 == 1) printf ("Second\n");
else printf ("First\n");

return 0;
}


Measured memory_bytes: 640
#include<stdio.h>

int main(){
  int d,n,a;
  scanf("%d %d",&d,&n);
  if(d==0)a=n;
  if(d==1)a=n*100;
  if(d==2)a=n*10000;
  if(n==100){
    if(d==0)a += 1;
    if(d==1)a+=100;
    if(d==2)a+=10000;
  }
  printf("%d\n",a);
  return 0;
}

Measured memory_bytes: 128
using System;

class MainClass
{
	public static void Main (string[] args)
	{
		int n = int.Parse (Console.ReadLine ());
		int[] a = new int[n];

		long max = -10000000;
		long min = 10000000;
		long sum = 0;


		string str = Console.ReadLine ();
		string[]spStr = str.Split(' ');

		for (int i = 0; i < n; i++) {
			a [i] = int.Parse (spStr [i]);

			if (a [i] < min) {min = a [i];}

			if (a [i] > max) {max = a [i];}

			sum += a [i];
		}

		Console.WriteLine (min + " " + max + " " + sum);
	}
}

Measured memory_bytes: 9924
#include <bits/stdc++.h>
using namespace std;
#define int long long int
int32_t main(){
	int a[3];cin>>a[0]>>a[1]>>a[2];sort(a,a+3);
	if((a[0]*a[1]*a[2])&1) cout<<a[0]*a[1];
	else cout<<0;
}


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

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;

int n,x,a[maxn];

int main() {
    read(n),read(x);
    for(int i=1;i<=n;i++) read(a[i]);
    sort(a+1,a+n+1);
    int ans=0;
    for(int i=1;i<=n;i++)
        if(x>=a[i]) x-=a[i],ans++;
    if(x&&ans==n) ans--;
    write(ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
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; }
typedef long long ll;
const long long INF = 1LL << 60;
const long long MOD = 1e9 + 7;
typedef pair<int, int> P;
ll modpow(ll a, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main()
{
    string L;
    cin >> L;

    vector<vector<ll>> dp((int)L.size() + 1, vector<ll>(2, 0));
    dp[0][0] = 1;

    rep(i, L.size()) {
        int num = L[i] - '0';
        rep(j, 2) {
            for (int k = 0; k <= (j ? 1 : num); k++) {
                int s = (k ? 2 : 1);
                dp[i + 1][j || (k < num)] += dp[i][j] * s;
                dp[i + 1][j || (k < num)] %= MOD;
            }
        }
    }

    int len = (int)L.size();
    cout << (dp[len][0] + dp[len][1]) % MOD << endl;
    return 0;
}

Measured memory_bytes: 5760
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
typedef long long li;
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }
// Container コンテナ型, map以外
template< template<class ...> class Ctn,class T>
std::ostream& operator<<(std::ostream& os,const Ctn<T>& v){
  auto itr=v.begin();
  while(itr!=v.end()){
    if(itr!=v.begin())cout << "";
    cout << *(itr++);
  }
  return os;
}

int main(){
  string s; cin >>s;
  int n=s.size();
  list<char> v;
  rep(i,n) v.push_back(s[i]);
  int q; cin >>q;
  int f=0;
  rep(_,q){
    int a; cin >>a;
    if(a==1){
      f^=1;
    }else{
      int b; cin >>b; b--;
      char c; cin >>c;
      if(f^b){
        v.push_back(c);
      }else{
        v.push_front(c);
      }
    }
  }
  if(f) reverse(v.begin(),v.end());
  print(v);
}


Measured memory_bytes: 12976
using System;

class Program
{
    static void Main(string[] args)
    {
        Console.WriteLine(Solve(Console.ReadLine(),
            Console.ReadLine(),
            Console.ReadLine(),
            Console.ReadLine()));
    }

    static string Solve(params string[] args)
    {
        var n500 = int.Parse(args[0]);
        var n100 = int.Parse(args[1]);
        var n50 = int.Parse(args[2]);
        var target = int.Parse(args[3]);

        var cnt = 0;
        for (int i = 0; i <= n500; i++)
        for (int j = 0; j <= n100; j++)
        for (int k = 0; k <= n50; k++)
        {
            if (500 * i + 100 * j + 50 * k == target) cnt++;
        }

        return cnt.ToString();
    }
}

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

int main(){
	ll n, m;
	cin >> n >> m;
	ll ans;
	if (2*n >= m){
		ans = m/2;
	}else{
		ans = n + (m-2*n)/4;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
PY = [list(map(int, input().split())) for _ in range(m)]

PY_sort = sorted(PY, key=lambda x: x[1])
PY_sort.sort(key=lambda x: x[0])

ID = {}
i, p = 1, PY_sort[0][0]
for v in PY_sort:
    if v[0] != p:
        i, p = 1, v[0]
    id = "%06d%06d"%(p, i)
    ID[v[1]] = id
    i += 1

for p, y in PY:
    print(ID[y])

Measured memory_bytes: 43064
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) < (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n) - 1; (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (i) = (a); (i) < (b); ++(i))
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;
#define all(x) (x).begin(),(x).end()

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

ll lcm(ll a,ll b){
    ll g = gcd(a,b);
    return a / g * b;
}

ll fac(ll n){
    ll t = 1;
    rep1(i, n + 1)t *= i;
    return t;
}

int main()
{
    ll n,x = 0,y = 0,cnt = 0;
    cin >> n;
    vector<ll> a(n);
    rep0(i, n){
        cin >> a[i];
    }
    sort(all(a),greater<>());
    rep0(i, n){
        if (a[i] == a[i + 1]) {
            if (cnt == 0) {
                x = a[i];
                ++cnt;
                ++i;
            }else if (cnt == 1){
                y = a[i];
                break;
            }
        }
    }
    cout << x * y << endl;
    return 0;
}


Measured memory_bytes: 1024
import java.util.*;
import java.io.*;
import java.math.*;
class Main{
	static int mod = (int)1e9+7;
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static void main(String sp[])throws IOException{
		FastReader sc = new FastReader();
		int n = sc.nextInt();
		long dp[][] = new long[n][3];
		long arr[][] = new long[n][3];
		for(int i=0;i<n;i++){
			for(int j=0;j<3;j++){
				arr[i][j]=sc.nextLong();
			}
		}
		for(int i=0;i<3;i++){
			dp[0][i] = arr[0][i];
		}
		
	
		for(int i=1;i<n;i++){
			for(int j=0;j<3;j++){
				dp[i][(j+1)%3] = Math.max(dp[i][(j+1)%3], arr[i][(j+1)%3]+dp[i-1][j]);
				dp[i][(j+2)%3] = Math.max(dp[i][(j+2)%3], arr[i][(j+2)%3]+dp[i-1][j]);
			}
		}
	
		long ans = Math.max(dp[n-1][0], Math.max(dp[n-1][1] , dp[n-1][2]));
		System.out.println(ans);
	}
	
	
	
	public static class pair{
		long a;
		long b;
	}
	
	public static class comp implements Comparator<pair>{
		public int compare(pair o1, pair o2){
			return Long.valueOf(o2.a-o2.b).compareTo(Long.valueOf(o1.a-o1.b));
		}
	}
	
	
	
	public static long sum(long a, long d, long n){
		
		long total = ((n)*((2*a)+(n-1)*d))/2;
		return total;
	}
	
	public static class trie{
		char ch;
		HashMap<Character,trie> hm = new HashMap<>();
		int count;
		boolean isterminal;
	}
	
	
	public static int partition(int [] arr, int s, int e){
		
		int index=s;
		int pivot = arr[e];
		for(int i=s;i<=e-1;i++){
			if(arr[i]<=pivot){
				arr = swap(arr, index, i);
				index++;
			}
		}
		swap(arr,index,e);
		print(arr);
		return index;
	}
	
	public static int[] swap(int[] arr, int low, int high){
		int temp = arr[low];
		arr[low]=arr[high];
		arr[high]=temp;
		return arr;
	}
	
	
	public static long gcd(long a, long b){
		if(a==0)
			return b;
		
		return gcd(b%a,a);
	}
	
	public static void print(int[] arr){
		for(int i=0;i<arr.length;i++)
			System.out.print(arr[i]+" ");
		System.out.println();
	}
	
 
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
	
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());//converts string to integer
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
}

Measured memory_bytes: 52916
#include <bits/stdc++.h>
using namespace std;
#define __ <<" "<<
#define ___ <<" "
#define bash push_back
#define ALL(x) x.begin(),x.end()
// #define int long long
struct IoSetup {
    IoSetup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
}IoSetup;

using Int = __int128_t;
using ll = long long;
using pii = pair<int, int>;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int SMOD = 1000000007;
constexpr int NMOD = 998244353;
constexpr int dx[]={1,0,-1,0,1,1,-1,-1};
constexpr int dy[]={0,-1,0,1,-1,1,-1,1};

inline bool inside(int x,int y,int w,int h){return (x>=0 && y>=0 && x<w && y<h);}
template<class T>bool chmax(T &a, const T&b){if(a<b)return(a=b,1);return 0;}
template<class T>bool chmin(T &a, const T&b){if(b<a)return(a=b,1);return 0;}

signed main() {

    int n, m;
    cin >> n;;
    vector<int> a(n);


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

    auto b = a;

    int gc = a[0];
    bool f = true;
    set<int> s;

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

        gc = __gcd(gc, a[i]);
        for(int j = 2; j * j <= a[i] and f; j++) {
            if(a[i]%j != 0) continue;
            while(a[i] % j == 0) a[i] /= j;
            if(s.find(j) != s.end()) {
                f = false;
            }
            else
                s.insert(j);
        }
        if(a[i] != 1) {
            if(s.find(a[i]) != s.end()) f = false;
            else s.insert(a[i]);
        }

    }

    if(f) {
        cout << "pairwise coprime\n";
    }
    else if(gc == 1) {
        cout << "setwise coprime\n";
    }
    else
        cout << "not coprime\n";

    return 0;
}

Measured memory_bytes: 57784
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(void){
    double x1,y1,x2,y2;
    cin >> x1;
    cin >> y1;
    cin >> x2;
    cin >> y2;
    double length = pow( (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1), 0.5 );
    cout << fixed << setprecision(9) << length;
    cout <<endl; 
}



Measured memory_bytes: 3428
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AOJ.Volume0
{
    class Program0025
    {
        static void Main(string[] args)
        {
            string line;
            var inputs = new Queue<string[]>();

            while ((line = Console.ReadLine()) != null)
            {
                inputs.Enqueue(new[] { line, Console.ReadLine() });
            }

            foreach (var input in inputs)
            {
                int hit, blow;            

                string[] a = input[0].Split(' ').ToArray();
                string[] b = input[1].Split(' ').ToArray();

                hit = Enumerable.Range(0, 4).Count(i => a[i] == b[i]);
                blow = a.Intersect(b).Count() - hit;

                Console.WriteLine("{0} {1}", hit, blow);
            }
        }
    }
}

Measured memory_bytes: 6420
x, n = gets.chomp.split(" ").map(&:to_i)
p = gets.chomp.split(" ").map(&:to_i)
if n == 0
  puts x
  exit
end
min = [p.min, x].min
max = [p.max, x].max
arr = (min-1..max+1).select { |n| !p.include?(n) }
m = arr.min_by { |n| (n - x).abs }
if m.nil?
  puts p.min - 1
else
  puts m
end

Measured memory_bytes: 14252
#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long n, i, j, u, v, vis[100001] = {0}, par[100001] = {0}, dp[100001][2] = {0};
vector<long long>adj[100001];

void dpdfs(long long x, long long p)
{
	vis[x] = 1;
	par[x] = p;
	for(long long y = 0; y < adj[x].size(); y++)
	{
		if(!vis[adj[x][y]])
		{
			dpdfs(adj[x][y], x);
		}
	}
	if(adj[x].size() == 1 && x != 1)
	{
		dp[x][0] = dp[x][1] = 1;
	}
	else
	{
		long long m = 1, p = 1;
		for(long long y = 0; y < adj[x].size(); y++)
		{
			if(adj[x][y] != par[x])
			{
				m = ((m % mod) * (dp[adj[x][y]][1] % mod)) % mod;
				p = ((p % mod) * ((dp[adj[x][y]][0] + dp[adj[x][y]][1]) % mod)) % mod;
			} 
		}
		dp[x][0] = m;
		dp[x][1] = p;
	}
}

int main()
{
	cin >> n;
	for(i = 0; i < n - 1; i++)
	{
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	dpdfs(1, 0);
	if(n == 1)
		cout << 2;
	else
		cout << (dp[1][0] + dp[1][1]) % mod;
	return 0;
}

Measured memory_bytes: 17764
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iterator>
#include <algorithm>
#include <string>
#include <cstring>
using namespace std;

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

typedef long long ll;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = b / a;
    if (ans < c)
        cout << ans << endl;
    else
        cout << c << endl;
    return 0;
}

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

main(){
  int tcase = 0;
  int n, k;
  while(1){
    cin >> n;
    if ( n == 0 ) break;
    int m2 = 0;
    int t = 0;
    for ( int i = 0; i < n; i++ ){
      cin >> k;
      if ( k >= 2 ) m2++;
      if ( k > 0 ) t++;
    }

    if ( m2 == 0 ) cout << "NA" << endl;
    else cout << t + 1 << endl;
    tcase++;
  }
}

Measured memory_bytes: 1160
#include <iostream>
#define llint long long

using namespace std;

llint h, n;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> h >> n;
	llint a, sum = 0;
	for(int i = 1; i <= n; i++){
		cin >> a;
		sum += a;
	}
	if(sum < h) cout << "No" << endl;
	else cout << "Yes" << endl;
	
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
 
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; }

//無限大
const ll INF = 1LL << 60;


//------------------------------------------------
int main() {
    
    int N,W;
    cin >> N >> W;

    //DPテーブル初期化
    ll dp[N+1][W+1];
    rep(i,N+1) rep(j,W+1) dp[i][j] = 0;

    //Baggage
    ll wi,vi;
    rep(i,N){
        cin >> wi >> vi;
        rep(sumw,W+1){
            //add
            if (sumw-wi>=0) chmax(dp[i+1][sumw], dp[i][sumw-wi] + vi);
            //not add
            chmax(dp[i+1][sumw], dp[i][sumw]);
        }
    }
    
    //answer
    ll ans = 0;
    rep(sumw,W+1) chmax(ans, dp[N][sumw]);
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 79104
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int main(){
	int n,m,a;
	bool safe[100001];
	cin>>n>>m;
	fill(safe,safe+100001,true);
	while(cin>>a)
		safe[a]=false;
	int dp[100001];
	dp[0]=1;
	for(int i=1;i<=n;i++){
		if(i==1)
			dp[i]=dp[i-1];
		else
			dp[i]=(dp[i-1]+dp[i-2])%mod;
		if(!safe[i])
			dp[i]=0;
	}
	cout<<dp[n]<<endl;
}


Measured memory_bytes: 768
#include <iostream>

using namespace std;

int main(){
  int n,s;
  cin >>n;
  int in[n],o[n];

  for(int i=0; i<n; i++){
    cin >>s;
    in[i]=s;
  }
  
  for(int i=0; i<n; i++){
    o[i]=in[(n-1)-i];
    cout <<o[i];
    if(i!=(n-1)){
      cout <<" ";
    }
  }
  cout<<endl;
  return 0;
}



Measured memory_bytes: 3076
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
#include<iomanip>
#include<queue>
#include<stack>
#include<time.h>
#define rep(i,n)for(ll i=0;i<n;i++)
#define ll long long
#define double long double
using namespace std;
ll a[114514];
signed main() {
	ll n, ans = 0;
	cin >> n;
	rep(i, n)cin >> a[i];
	sort(a, a + n);
	rep(i, n) {
		if (i != n - 1 && a[i] == a[i + 1])continue;
		if ((upper_bound(a, a + n, a[i]) - lower_bound(a, a + n, a[i])) % 2 == 1)ans++;
	}
	cout << ans << endl;
	getchar(); getchar(); return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<ll,pair<ll,ll>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

struct edge{
  ll to, cost, time;
};

ll n, m, s;
vector<ll> C(51), D(51);
vector<vector<edge>> G(50);
vector<vector<ll>> d(50, vector<ll>(2600, inf));


void dijkstra(ll start, ll silver) {
	priority_queue<PiP, vector<PiP>, greater<PiP>>que;
	d[start][silver] = 0;
	que.push({0, {start, silver}});
	while (!que.empty()) {
		PiP p = que.top(); que.pop();
		ll v = p.second.first, cnt = p.second.second;
		if (d[v][cnt] < p.first)continue;
        if(cnt + C[v] <= 2501){
            if(chmin(d[v][cnt+C[v]], d[v][cnt] + D[v])){
                que.push({d[v][cnt+C[v]], {v, cnt+C[v]}});
            }
        }
	    rep(i, G[v].size()) {
		    edge e = G[v][i];
            if(cnt < e.cost)continue;
		    if (chmin(d[e.to][cnt-e.cost], d[v][cnt] + e.time)) {
			    que.push({d[e.to][cnt-e.cost], {e.to, cnt-e.cost}});
			}
        }
	}
}

int main(){
    cin >> n >> m >> s;
    rep(i, m){
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        G[u-1].push_back({v-1, a, b});
        G[v-1].push_back({u-1, a, b});
    }
    rep(i, n)cin >> C[i] >> D[i];
    dijkstra(0, min(s, 2501LL));
    REP(i, n-1){
        ll ans = inf;
        rep(j, 2550)chmin(ans, d[i][j]);
        cout << ans << endl;
    }
}

Measured memory_bytes: 7456
#include <bits/stdc++.h>
using namespace std;
int main()
{
  double a,b,x,theta;
  cin>>a>>b>>x;
  theta=(a*a*b>2*x)?M_PI/2.0-atan(2*x/(a*b*b)):atan(2*(a*a*b-x)/(a*a*a));
  cout<<fixed<<setprecision(10)<<theta*180/(M_PI)<<endl;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
a = list(map(int,read().split()))

def update(a):
    b = [0]*n
    for ind,i in enumerate(a):
        left = max(0,ind-i)
        right = ind+i+1
        b[left] += 1
        if(right<n):
            b[right] -= 1

    for i in range(1,n):
        b[i] += b[i-1]

    return b

for i in range(k):
    a = update(a)
    if(sum(a) == n*n):
        break

print(' '.join(map(str,a)))

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

using namespace std;

const int MOD = 1e9 + 7;

int n, p[100][100],dp[1 << 21 + 1];

void add(int &a, int b) {
	a += b;
	
	if( a >= MOD) {
		a -= MOD;
	}
}


int main() {
	
	scanf("%d", &n);
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			scanf("%d",&p[i][j]);
		}
	}
	
	dp[0] = 1;
	
	for(int mask = 0; mask < (1 << n) - 1; mask++) {
		int i = __builtin_popcount(mask);
		
		for(int j = 0; j < n; j++) {
			if(p[i][j] && !(mask & (1 << j))) {
				
				add(dp[mask | (1 << j)], dp[mask]);
				//printf("%d %d %d %d %d %d %d\n",i, j, p[i][j],mask | (1 << j), mask, dp[mask], dp[mask | (1 << j)]);
			}
		}
	}
	//for(int i = 0; i < (1 << n) - 1; i++) {
//		printf("%d ",dp[i]);
	//}
	printf("%d",dp[(1 << n) - 1]);
	
	return 0;
}

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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


class UnionFind{
    public:
        UnionFind(int N) : parent(N), rank(N){
            for(int i = 0; i < N; i++){
                parent[i] = i;
                rank[i] = 1;
            }
        }

        int find(int n){
            if(parent[n] == n){
                return n;
            }
            return parent[n] = find(parent[n]);
        }

        void merge(int m, int n){
            int root_x = find(m);
            int root_y = find(n);
            if(root_x == root_y){
                return;
            }
            if(rank[root_x] < rank[root_y]){
                parent[root_x] = root_y;
            }else if(rank[root_x] > rank[root_y]){
                parent[root_y] = root_x;
            }else{
                parent[root_y] = root_x;
                rank[root_x]++;
            }
        }

        bool equivalent(int x, int y){
            return find(x) == find(y);
        }

    private:
        vector<int> parent;
        vector<int> rank;

};


ll N, M;
int A[100000], B[100000];
ll num[100000];
ll ans[100001];

signed main(){
    cin >> N >> M;
    REP(i, M){
        cin >> A[i] >> B[i];
        A[i]--; B[i]--;
    }
    UnionFind uf(N);
    REP(i, N) num[i] = 1;
    ans[M] = N * (N - 1) / 2;
    REP(i, M){
        int a = uf.find(A[M - 1 - i]);
        int b = uf.find(B[M - 1 - i]);
        if(uf.equivalent(A[M - 1 - i], B[M - 1 - i])){
            ans[M - 1 - i] = ans[M - i];
        }else{
            ans[M - 1 - i] = ans[M - i] - (num[a] * num[b]);
            ll sum = num[a] + num[b];
            num[a] = num[b] = sum;
        }
        uf.merge(A[M - 1 - i], B[M - 1 - i]);
    }
    REP(i, M){
        PRINT(ans[i + 1]);
    }
    return 0;
}

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
#define rep0(i, n) for (long long i = 0; i < (long long)(n); i++)
#define rep1(i,n) for(long long i=1;i<=(long long)(n);i++)
#define all(v) v.begin(),v.end()
#define Sort(v) sort(all(v))
#define Reverse(v) reverse(all(v))
#define Rsort(v) sort(all(v),greater)
#define pub(v) push_back(v)
#define pob(v) pop_back(v)
typedef long long ll;
typedef vector<ll> vel;
typedef vector<vector<ll>> vel2d;
typedef string str;
typedef pair<ll,ll> pal;
typedef vector<str> ves;
typedef vector<char> vech;

int main() {
    ll N,M; cin>>N>>M;
    vel L(M),R(M);
    rep0(i,M){cin>>L[i]>>R[i];}
    sort(all(L)); sort(all(R));
    reverse(all(L));
    if(L[0]>R[0]){cout<<0<<endl;}
    else{cout<<R[0]-L[0]+1<<endl;}
}


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

//vector<vector<ll>> C(4000, vector<int> (4000,0));
ll C[4000][4000];


ll nCk(ll n, ll k) {
  if(C[n][k] != 0) return C[n][k];  
  if (n == k || k == 0)
    return C[n][k] = 1;
  else {
    return C[n][k] = nCk(n - 1, k - 1)%mod + nCk(n - 1, k)%mod;
  }
}

int main()
{
   
    int n,k;
    cin>>n>>k;
    for(int i = 1; i <= k; i++){
        if (n - k + 1 < i || k < i){
            cout << 0 <<   endl;
            continue;
        } else { 
            cout << (nCk(k - 1, i - 1)%mod)*(nCk(n-k+1, i)%mod)%mod << endl;
        
        }
    
    }
    return 0;
}

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

using namespace std;

int main()
{
	int ans = 0;
	int dp[10005];
	int n, a, b;
	for (int i = 0; i <= 10000; i++) {
		int s[5];
		s[0] = i / 10000;
		s[1] = i % 10000 / 1000;
		s[2] = i % 1000 / 100;
		s[3] = i % 100 / 10;
		s[4] = i % 10;
		dp[i] = s[0] + s[1] + s[2] + s[3] + s[4];
	}
	cin >> n >> a >> b;

	for (int i = n; i > 0; i--) {
		if (dp[i] >= a && dp[i] <= b)
			ans += i;
	}
	cout << ans << endl;



	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(void){

  int N; cin >> N;
  long A[1000000];
  for(int i = 0 ; i < N + 1 ; i++) cin >> A[i];

  long long ans = 0;
  for(int i = 0 ; i < N ; i++){
    long input;   cin >> input;

    if(A[i] + A[i + 1] < input){
      ans = ans + A[i] + A[i + 1];
      A[i + 1] = 0;
    }else{
      ans += input;
      if(A[i] < input)
        A[i + 1] = A[i + 1] - (input - A[i]);

    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 2944
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
//#include<cctype>
#include<climits>
#include<iostream>
#include<string>
#include<vector>
#include<map>
//#include<list>
#include<queue>
#include<deque>
#include<algorithm>
//#include<numeric>
#include<utility>
//#include<memory>
#include<functional>
#include<cassert>
#include<set>
#include<stack>
#include<random>

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;

struct bunsu {
	int a;
	int b;
	bunsu() {}
	bunsu(int a, int b) : a(a), b(b) {}
	bool operator<(const bunsu& rhs) const {
		return a*rhs.b > rhs.a * b;
	}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    while (cin >> N) {
    	if (N==0) break;
    	vector<pair<bunsu, string> > vs;
    	for (int i = 0; i < N; i++) {
    		string name;
    		int p, a, b, c, d, e, f, s, m;
    		cin >> name >> p >> a >> b >> c >> d >> e >> f >> s >> m;
    		int money = f*m*s - p;
    		int time = a+b+c + m*(d+e);
    		vs.emplace_back(bunsu(money, time), name);
    	}
    	sort(vs.begin(), vs.end());
    	for (auto p : vs) {
    		cout << p.second << endl;
    	}
    	cout << "#" << endl;
    }
    return 0;
}

Measured memory_bytes: 3044
#include<stdio.h>
#include<string.h>

int main(void){
   char s[101];
   int count = 0;
   scanf("%s",s);

   for(int i = 0; i < strlen(s); i++){
      if(s[i] != s[strlen(s)-1-i]){
         count++;
      }
   }
   printf("%d\n", count / 2);
   return 0;
}


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

// clang-format off
template <typename T> T gcd(T a, T b) { return b == 0 ? a : gcd(b, a % b); }
template <typename T> T lcm(T a, T b) { return a * b / gcd(a, b); }
template <typename T> T clamp(T val, T min, T max) { return val < min ? min : (max < val ? max : val); }
char capitalize(char c) { return static_cast<char>(std::toupper(static_cast<unsigned char>(c))); }
// template <typename T> size_t max_index(T begin, T end) { return distance(begin, max_element(begin, end)); }
// template <typename T> size_t min_index(T begin, T end) { return distance(begin, min_element(begin, end)); }
// clang-format on

#define int long long
#define YES "YES"
#define NO "NO"
#define MOD 1000000000 + 7
#define forit(v) for (auto it = v.begin(); it != v.end(); ++it)

using namespace std;

map<int, int> mem;

int f(int i, int k) {
  if (i >= k) return 0;
  int key = i;
  int val;

  if (mem.count(i) > 0) {
    val = mem[i];
  } else {
    val = f(2 * i, k) + 1;
    mem.insert(make_pair(key, val));
  }

  return val;
}

signed main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int num = 0;
  // num = numeric_limits<int>::max();
  // num = numeric_limits<int>::min();
  bool flag = false;
  // flag = true;

  int n, k; cin >> n >> k;
  int s = 0;
  double p = 0.;

  for (int i = n; i > 0; --i) {
    if (i >= k) {
      p += 1. / (double)n; // p += (double)k / (double)n; break;
      
    } else {
      p += pow(0.5, f(i, k)) / (double)n;
    }
  }

  cout << setprecision(10)  << p << endl;
  
  // cout << num << endl;
  // cout << (flag ? YES : NO) << endl;

  return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>

int main(int argc, char const *argv[]) {
	char str[101];
	int n;
	int a[10001];

	fgets(str, 100, stdin);
	sscanf(str, "%d\n", &n);

	int i;
	int tail = 0;
	int res = 0;

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


	for (i = 0; i < n; i++) {
		while (a[i] % 2 == 0) {
			a[i] /= 2;
			res++;
		}
	}

	printf("%d\n", res);

	return 0;
}


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

int main() {
    long long N;
    cin >> N;
    vector<long long> d(N);

    for(long long i=0;i<N;i++) cin >> d[i];
    
    sort(d.begin(),d.end());
    long long minlim = d[N/2 - 1];
    long long maxlim = d[N/2];
    cout << maxlim - minlim << endl;
    return 0;
}

Measured memory_bytes: 1024
n,k=map(int,input().split())
S=input()

now=S[0]
cnt=1
A=[] #個数配列
for i in range(n-1):
    if S[i+1]==now:
        cnt+=1
    else:
        A.append(cnt)
        cnt=1
        now=S[i+1]
if cnt>0:
    A.append(cnt)
l=len(A)
    
if S[0]=="0":
    if l<=2*k:
        ans=n
    elif 2*k+1<=l<=2*k+2:
        ans=max(sum(A[:2*k]),sum(A[1:]))
    else:
        ans=max(sum(A[:2*k]),sum(A[1:2*k+2]))
        cnt=sum(A[1:2*k+2])
        for i in range((l-2*k-2)//2):
            cnt-=A[2*i+1]+A[2*i+2]
            cnt+=A[2*k+2*i+2]+A[2*k+2*i+3]
            ans=max(cnt,ans)
        if l%2!=0:
            ans=max(sum(A[l-2*k:]),ans)
else:
    if l<=2*k+1:
        ans=n
    else:
        ans=sum(A[:2*k+1])
        cnt=ans
        for i in range((l-2*k-1)//2):
            cnt-=A[2*i]+A[2*i+1]
            cnt+=A[2*k+2*i+1]+A[2*k+2*i+2]
            ans=max(cnt,ans)
        if l%2==0:
            ans=max(sum(A[l-2*k:]),ans)
print(ans)

Measured memory_bytes: 4672