akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 #include<functional>
 #include<utility>
 
 using namespace std;
 
 int main()
 {
   int up,down,front,back,left,right;
   cin>>up>>front>>right>>left>>back>>down;
   string com;
   cin>>com;
   for(int i=0;i<com.length();i++)
   {
     if(com[i]=='S')
     {
       int temp=down;
       down=front;
       front=up;
       up=back;
       back=temp;               
     }
     else if(com[i]=='W')
     {
       int temp=left;
       left=up;
       up=right;
       right=down;
       down=temp;     
     }
     else if(com[i]=='N')
     {
       int temp=front;
       front=down;
       down=back;
       back=up;
       up=temp;     
     }
     else
     {
       int temp=up;
       up=left;
       left=down;
       down=right;
       right=temp;   
     }        
   }
   cout<<up<<endl;
   //while(1);
   return 0;
 }

Measured memory_bytes: 3196
#include <iostream>
#include <fstream>
#include <algorithm>       // for next_permutation
#include <vector>
#include <queue>
#include <bits/stl_numeric.h>

#define DEBUG 0
#define REP(i, n) for (long long i = 0; i < (n); i++) 
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
static const ll MOD = 1000000007;
static const ll INF = 1000000000000000000LL;

const int MAX = 210000;

long long fac[MAX], finv[MAX], inv[MAX];

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

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {

    cin.tie(0);
    ios::sync_with_stdio(false);
    // 前処理
    COMinit();
    ll N, K;
    cin >> N >> K;
    vector <ll> a(N);

    REP(i, N)
    {
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    ll res = 0;

    for(int i = N - 1; i - (K-1) >= 0; --i)
    {
        if(a[i] < 0)
        {
            ll tmp = -a[i] * COM(i, K-1);
            tmp %= MOD;
            res -= tmp;
        }
        else
        {
            ll tmp = a[i] * COM(i, K-1);
            tmp %= MOD;
            res += tmp;
        }
        if(res < 0)
        {
            res += MOD;
        }
        else
        {
            res %= MOD;
        }
    }
    for(int i = 0; i + (K-1) < N; ++i)
    {
        if(a[i] < 0)
        {
            ll tmp = (-a[i] * COM(N-1-i,K-1) % MOD);
            res += tmp;
        }
        else
        {
            ll tmp = (a[i] * COM(N-1-i,K-1) % MOD);
            res -= tmp;
        }
        
        if(res < 0)
        {
            res += MOD;
        }
        else
        {
            res %= MOD;
        }
        
        
    }


    cout << res << endl;
}

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

using namespace std;

#define int long long
#define double long double 
const int MAX_N = 1e5 + 5;
const int MAX_L = 20; // ~ Log N
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;


typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef unordered_map<int,int> mii;
typedef unordered_map<char,int> mci;
typedef unordered_map<string,int> msi;

#define pb push_back
#define f first
#define s second 
 

void solve() {
    int n; cin>>n;
    vi A(n);
    for(int i=0;i<n;i++) cin>>A[i];

    vector<vvi> dp(n,vvi(n,vi(2))); 

    for(int i=0;i<n;i++) {
        dp[i][i][0] = A[i];
    }
    for(int i=0;i<n;i++) {
        dp[i][i][1] = -1*A[i];
    }

    for(int i=2;i<=n;i++) {
        for(int j=0;j<=n-i;j++) {
            int b = j;
            int e = j+i-1;
            dp[b][e][0] = max(A[b]+dp[b+1][e][1],A[e]+dp[b][e-1][1]);
            dp[b][e][1] = min(-A[b]+dp[b+1][e][0],-A[e]+dp[b][e-1][0]);
        }
    }
    cout<<dp[0][n-1][0]<<'\n';

}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //#ifdef LOCAL
     //   freopen("input.txt", "r", stdin);
       // freopen("output.txt", "w", stdout);
    //#endif

    int tc; tc=1;
    for (int t = 1; t <= tc; t++) {
        //cout << "Case #" << t  << ": ";
        solve();
    }
}

Measured memory_bytes: 495788
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define pii pair<int,int>
#define LL long long
using namespace std;

int main () {
    //clock_t start = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    int a[n+5];
    int m=0;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
    }
    int ans=0;
    for (int i=1;i<=n;i++) {
        if (m == 0) {
            ans++;
            m = a[i];
        } else if (a[i]<m) {
            ans++;
            m = a[i];
        }
    }
    cout << ans << endl;
    //cerr << fixed << setprecision(3) << (clock()-start)*1./CLOCKS_PER_SEC << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstdint>

std::uint64_t gcd(std::uint64_t a, std::uint64_t b) noexcept {
	if (a == b) { return a; }
	if (a == 0) { return b; }
	if (b == 0) { return a; }
	return gcd(b, a % b);
}
std::uint64_t lcm(std::uint64_t a, std::uint64_t b) noexcept {
	return ((a / gcd(a, b)) * b);
}

int main()
{
	int n;
	std::cin >> n;

	std::uint64_t T = 1;
	for (int i = 0; i < n; i++) {
		std::uint64_t Ti;
		std::cin >> Ti;
		T = lcm(T, Ti);
	}

	std::cout << T << std::endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;
string alp="abcdefghijklmnopqrstuvwxyz";

int main(){
    int H,W,A,B;
    cin >> H >> W >> A >> B;
    rep(i,H){
        if (i<B){
            rep(j,W){
                if (j<A){
                    cout << 0;
                }
                else {
                    cout << 1;
                }
                if (j==W-1){
                    cout << endl;
                }
            }
        }
        else {
            rep(j,W){
                if (j<A){
                    cout << 1;
                }
                else {
                    cout << 0;
                }
                if (j==W-1){
                    cout << endl;
                }
            }
        }
    }
}


Measured memory_bytes: 1280
#include<iostream>
#include<array>

int main()
{ 
	std::array<int,13> exp5;

	int Five =5;

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

		exp5[i] = Five;

		Five *= 5;
	}

	int n;

	while(1)
	{
		std::cin >> n;
		
		if(n==0)
		{
			break;
		}

		int count = 0;
	
		for(size_t i=0; i<exp5.size(); ++i)
		{
			count += n/exp5[i];
		}
		
		std::cout << count << '\n';

	}
}

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

ll nC2(ll n) {
    return n*(n-1)/2;
}

int main() {

    //
    ll N;
    cin >> N;
    vector<ll> A(N);
    for (ll i=0; i<N; i++) {
        cin >> A[i];
    }

    // maxAを求める
    vector<ll> A_temp = A;
    sort(A_temp.begin(),A_temp.end());
    ll maxA = A_temp[N-1];

    // countベクトル（ベクトルAのi番目の数が何個あるか）
    vector<ll> count(maxA,0);
    for (ll i=0; i<N; i++) {
        count[A[i]-1]++;
    }
    /*
    cout << endl;
    for (ll i=0; i<maxA; i++) {
        cout << count[i] << endl;
    }
    cout << endl;
    */
    ll N_pair = 0;     // 全組み合わせ
    for (ll i=0; i<maxA; i++) {
        N_pair += nC2(count[i]);
    }
    /*
    cout << N_pair << endl;
    cout << endl;
    */
    vector<ll> k(N,N_pair);
    for (ll i=0; i<N; i++) {
        k[i] -= nC2(count[A[i]-1]) - nC2(count[A[i]-1]-1);
    }
    
    //
    for (ll i=0; i<N; i++) {
        cout << k[i] << endl;
    }
    
}

Measured memory_bytes: 9568
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
    long long A,B,C,X,Y,ans;
    scanf("%lld%lld%lld%lld%lld",&A,&B,&C,&X,&Y);
    ans=(1LL<<60);
    for(long long i=0;i<=max(X,Y);i++)
        ans=min(ans,2*i*C+max(0LL,X-i)*A+max(0LL,Y-i)*B);
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int a, b;
char out[100][100];

int main() {
	cin >> a >> b;
	rep (i, 100) rep (j, 100) out[i][j] = i < 50 ? '#' : '.';
	rep (i, a - 1) {
		out[i / 50 * 2][i * 2 % 100] = '.';
	}
	rep (i, b - 1) {
		out[i / 50 * 2 + 51][i * 2 % 100] = '#';
	}
	cout << 100 << " " << 100 << endl;
	rep (i, 100) {
		rep (j, 100) cout << out[i][j];
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,a) for(int i = 0 ; i < a ; i ++)
int main(void){
	int h[10];
	rep(i,10)cin>>h[i];
	sort(h,h+10);
	rep(i,3)cout<<h[10-i-1]<<endl;
}

Measured memory_bytes: 1176
#include <iostream>
#include <ios> 
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;
//const int MAX=;

int main(){
	string S;
  	cin>>S;
	int l=(int)S.length();
	int f=0,exA=0,exC=0,small=0;
	if(S[0]=='A')exA=1;
	int count=0;
	for(int i=2;i<=l-2;i++){
		if(S[i]=='C')count++;
	}
	if(count==1)exC=1;
	int smc=0;
	rep(i,l){
		int y=0;
		for(int j='a';j<='z';j++){
			if(S[i]==j)y=1;
		}
		smc+=y;
	}
	if(smc==l-2)small=1;
	f=exA*exC*small;
	if(f)cout<<"AC";
	else cout<<"WA";
}

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

#define fi first
#define se second
#define pb push_back
#define mod(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,a,b) for(int i = a; i < b; i++)
#define forr(i,a,b) for(int i = a; i >= b; i--)
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int maxn = 1000000;

ll power(ll a,ll b,ll mod){
	ll res = 1;
	while(b){
		if(b&1)res = ((res%mod)*(a%mod))%mod;
		b >>= 1;
		a = ((a%mod)*(a%mod))%mod;
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll x; cin >> x;
	ll ac = 0;
	forn(i,1,maxn){
		ll add = ((power(10,i-1,x))*(7%x))%x;
		ac = ((ac%x)+(add%x))%x;
		if(ac < 0)ac += x;
		if(ac == 0){
			cout << i << '\n';
			return 0;
		}
	}
	cout << "-1\n";
	return 0;
}
/*
__builtin_mul_overflow(x,y,&x)
-fsplit-stack
*/


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

int main() {
    long long N, K;
    cin >> N >> K;
    vector <long long> H(N);
    long long sum=0;
    for (long long i=0; i<N; i++) {
        cin >> H.at(i);
        sum += H.at(i);
    }
    sort(H.begin(), H.end());
    for (long long i=0; i<min(K,N); i++) {
        sum -= H.at(N-1-i);
    }
    cout << sum << endl;
}

Measured memory_bytes: 1792
using System;
using System.Collections.Generic;
using System.Linq;

public class Hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine());
        var ss = new string[n];
        for (int i = 0; i < ss.Length; ++i)
            ss[i] = Console.ReadLine();

        int count = 0;
        int b = 0;
        int a = 0;
        int ba = 0;

        for (int i = 0; i < ss.Length; ++i)
        {
            var s = ss[i];
            var prev = ' ';
            var isB = false;
            for (int j = 0, length = s.Length; j < length; ++j)
            {
                var c = s[j];
                switch (c)
                {
                    case 'B':
                        switch (prev)
                        {
                            case 'A':
                                ++count;
                                break;
                            case ' ':
                                isB = true;
                                break;
                        }
                        break;
                }
                prev = c;
            }
            if (prev == 'A')
            {
                if (isB)
                    ++ba;
                else
                    ++a;
            }
            else if (isB)
                ++b;
        }

        if (b > a)
        {
            var tmp = b;
            b = a;
            a = tmp;
        }

        var adder = b + ba;
        if (a == 0 && ba > 0)
            --adder;

        Console.WriteLine(count + adder);
    }
}


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

const int MAX_N=1e5+10;
const int INF=1e9+10;

int K,N,M,dist[MAX_N];
vector <pair<int,int> > g[MAX_N];
priority_queue <pair<int,int> > Q;

void get_dijk(){
	for(int i=0;i<MAX_N;i++) dist[i]=INF;
	dist[1]=1;
	Q.push(make_pair(-dist[1],1));
	while(Q.size()){
		int val=-Q.top().first,x=Q.top().second;
		Q.pop();
		if(dist[x]<val) continue;
		for(int i=0;i<g[x].size();i++){
			int cost=g[x][i].first,to=g[x][i].second;
			if(dist[to]>cost+dist[x]){
				dist[to]=cost+dist[x];
				Q.push(make_pair(-dist[to],to));
			}
		}
	}
}

int main(){
	cin>>K;
	for(int i=1;i<K;i++){
		g[i].push_back(make_pair(0,i*10%K));
		g[i].push_back(make_pair(1,(i+1)%K));
	}
	get_dijk();
	cout<<dist[0]<<endl;
	return 0;
}

Measured memory_bytes: 6780
#70
#ALDS1_2_C
n=int(input())
*temp,=input().split()
a=temp[:]
b=temp[:]
for i in range(n):
    for j in range(n-1):
        if a[j][1]>a[j+1][1]:
            a[j],a[j+1]=a[j+1],a[j]

for i in range(n):
    m=i
    for j in range(i,n):
        if b[m][1]>b[j][1]:
            m=j
    if i!=m:
         b[m],b[i]=b[i],b[m]

print(*a)
print('Stable')
print(*b)
if a==b:
    print('Stable')
else:
    print('Not stable')


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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string S;
    cin>>S;
    if(S.size()>=4&&S.substr(0,4)=="YAKI")cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 256
n, k = map(int, input().strip().split())
arr = [int(i) for i in input().strip().split()]
maxi = s = (sum(arr[0:k]) + k) / 2
for i in range(1, n - k + 1):
  s += (arr[i + k - 1] - arr[i - 1]) / 2
  if s > maxi: maxi = s
print(maxi)

Measured memory_bytes: 24676
n=int(input())
a=list(map(int,input().split()))
a.sort()
e=[1]*(10**6+1)
from collections import Counter
d=Counter(a)
ans=0
for i in a:
  if d[i]==1 and e[i]==1:ans+=1
  if e[i]==1:
    for j in range(i,10**6+1,i):e[j]=0
print(ans)


Measured memory_bytes: 43564
var i,j,k,m,n,b:longint;
a:array[1..100000]of longint;
s,st:ansistring;
begin
  read(k,m,n);
  for i:=1 to k do
  begin
    read(a[i]);
    if (a[i]<m) or (a[i]>=n) then inc(b);

  end;
  writeln(b);
end.

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define mod 1000000007
#define f(i,a,b) for(ll i=a;i<b;i++)
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ii pair<ll,ll>
#define vii vector<ii>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define MAX 1e9
 
ll modpow(ll base, ll exp, ll modulus) {base %= modulus;ll result = 1;while (exp > 0) {if (exp & 1) result = (result * base) % modulus;base = (base * base) % modulus;exp >>= 1;}return result;}
const ld pi=acos(-1);

bool check(ll d,ll m){ll cnt=0;ll prod=1;
    while(d){
        ll dig=d%10;prod*=dig;
        if(dig>=2)cnt++;
        d=d/10;
    }
    if(cnt==2 && prod<=m)return 1;
    else return 0;
}
int main(){
    IOS;
    ll m,d;cin>>m>>d;ll ans=0;ll x=22;
    while(x<=d){
        if(check(x,m))ans++;
        x++;
    }
    cout<<ans;
    return 0;
}   

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define forn(low,high,i) for(i = low;i < high;i++)
#define forrev(high,low,i) for(i = high; i >= low;i--)
#define trace(x) cerr << #x << ": " << x << " " << endl;
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define line cout << __LINE__;
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
#define dbg2(a,b) cerr << #a << " = " << a << " " << #b << " = " << b << '\n';        
#define debug(x) cerr << __LINE__ << ' ' << #x << " = " << x << '\n';
#define dln cerr << '\n';
#define dsp cerr << ' ';
#define pln cout << '\n';
#define psp cout << ' ';

typedef unordered_map<int,int> umi;
typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int inf = 1e9;
const ll INF = 1e18;
const ll mod = 1e9 + 7;

clock_t time_p = clock();

void ktj(){
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (float)(time_p)/CLOCKS_PER_SEC << "\n";
}
const ll N = 2e5 + 5;
ll dp[N];
vl g[N];
void dfs(ll v, ll p){
  if(p != -1){
    dp[v] += dp[p];
  }
  for(auto x : g[v]){
    if(x != p){
      dfs(x, v);
    }
  }
}
int main(){
  fastio

  ll n, i, j, k, q;

  cin >> n >> q;

  for(i = 1; i < n; i++){
    ll u, v;
    cin >> u >> v;
    g[u].pb(v); g[v].pb(u);
  }

  while(q--){
    ll u, v;
    cin >> u >> v;
    dp[u] += v;
  }

  dfs(1, -1);

  for(i = 1; i <= n; i++){
    cout << dp[i] << ' ';
  }
  cout << '\n';

  ktj();
}


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

int dp[100005];
vector<int> g[100005];
void dfs(int u, int p){
 	int res = 0;
 	for(int i=0;i<g[u].size();i++){
 		int v = g[u][i];
 		if(v == p) continue;
 		dfs(v, u);
 		res ^= dp[v]+1;
 	}
 	dp[u] = res;
}

int main(){
	int N;
	scanf("%d", &N);
	for(int i=0;i<N-1;i++){
		int a, b;
		scanf("%d%d", &a, &b);
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(1, 0);
	if(dp[1] != 0) printf("Alice\n");
	else printf("Bob\n");
}

Measured memory_bytes: 13952
import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long A = sc.nextLong();
		String B = sc.next();
		sc.close();
		int B100 = 0;
		B100 += Integer.parseInt(B.substring(0, 1)) * 100;
		B100 += Integer.parseInt(B.substring(2, 3)) * 10;
		B100 += Integer.parseInt(B.substring(3, 4)) * 1;
		System.out.println((long) A * B100 / 100);
	}
}


Measured memory_bytes: 35516
/*
 ╔═══╦═══╦═══╗
 ║╔═╗║╔══╩╗╔╗║
 ║║░║║╚══╗║║║║
 ║║░║║╔══╝║║║║
 ║╚═╝║╚══╦╝╚╝║
 ╚══╗╠═══╩═══╝
 ░░░╚╝░░░░░░░░
 */

#include <bits/stdc++.h>
#define ll					long long
#define MOD					1000000007
#define MAX					1e9
#define MIN                 -1e9
#define PI					acos(-1.0)
#define vi					vector<int>
#define vii					vector<vi>
#define vll					vector<ll>
#define mid(s,e)			(s+(e-s)/2)

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
template<typename T>
void printVec(const T &v, char sep=' ') {for (auto &i: v) cout << i << sep;}
template<typename T>
void printVecPair(const T &v, char sep=' ') {for (auto &i: v) cout << i.first <<" " << i.second<< sep;}


#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else

#define debug(x...)
#endif
int v[110],w[110];
vector<vector<ll>> dp;
int N,W; 
ll solve(int i, ll cp) {
		if(i==0 || cp <= 0)
				return 0;
		ll& ans = dp[i][cp];
		if(ans != -1) return ans;
		if(w[i-1] > cp) return ans = solve(i-1,cp);
		return ans = max(solve(i-1,cp),v[i-1] + solve(i-1,cp-w[i-1]));
}



int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0);
	scanf("%d%d",&N,&W);
	dp.resize(N+1,vector<ll>(W+1,-1));

	for(int i=0;i<N;i++) {
			scanf("%d%d",w+i,v+i);
	}
	cout<<solve(N,W);
	return 0;
}






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

#define int long long

string s;
int n;
int k;
int memo[100010][2][4];

int dp(int i, int f, int nk){
    if(i == n){
        if(nk == k){
            return 1;
        }else{
            return 0;
        }
    }

    if(memo[i][f][nk] != -1) return memo[i][f][nk];

    int ans = 0;
    int fin = f == 1 ? s[i]-'0' : 9;

        for(int j = 0;j <= fin;j++){
            if(j == 0){
                ans += dp(i+1, f == 1 && j == fin, nk); 
            }else{
                if(nk < k){
                    ans += dp(i+1, f == 1 && j == fin, nk+1); 
                }

            }
        }

    return memo[i][f][nk] = ans;
}


signed main(){
    cin >> s;
    cin >> k;
    n = s.size(); 
    memset(memo, -1, sizeof(memo));

    cout << dp(0, 1, 0) << endl;

    return 0;
}



Measured memory_bytes: 6528
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int r = Integer.parseInt(sc.next());
        if(n < 10) {
            r += 100 * (10-n);
        }
        System.out.println(r);
    }
}

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

using namespace std;

typedef long long int ll;
typedef long double ld;

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
	int n, a[30];
	
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}
	
	int ans = 0;
	for(int i = 2; i < n; i++){
		vector<int> vec;
		for(int j = 0, k = i - 1; j < 3; j++){
			vec.push_back(a[k++]);
		}
		
		sort(vec.begin(), vec.end());
		if(a[i] == vec[1]) {
			ans++;
		}
	}
	
	cout << ans << endl;
	
	return 0;
}




Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <locale>
#include <iostream>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

using ll = long long;
using ld = long double;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> int len(const T &x) { return x.size(); }

template<typename T>
vector<T> table(int n, T v) { return vector<T>(n, v); }

template <class... Args>
auto table(int n, Args... args) {
  auto val = table(args...);
  return vector<decltype(val)>(n, move(val));
}

struct yes_no : numpunct<char> {
  string_type do_truename()  const { return "YES"; }
  string_type do_falsename() const { return "NO"; }
};

template <typename Cost>
struct Edge {
  int from, to;
  Cost cost;
  Edge(int s, int t, Cost c) : from(s), to(t), cost(c) {}
};

template<typename Cost> using Graph = vector<vector<Edge<Cost>>>;

template <typename Cost>
void add_edge(Graph<Cost> &g, int from, int to, Cost cost) {
  g[from].emplace_back(from, to, cost);
}

template <typename Cost>
vector<Cost> bfs01(const Graph<Cost> &g, int s, Cost zero = 0) {
  vector<Cost> d(g.size(), 100000000);
  d[s] = zero;
  using P = pair<Cost,int>;
  deque<P> que;
  que.push_back(P(zero, s));
  while (!que.empty()) {
    P top = que.front(); que.pop_front();
    Cost dist = top.first; int v = top.second;
    if (d[v] < dist) continue;
    for (const auto &e: g[v]) {
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        if (e.cost) que.push_back(P(d[e.to], e.to));
        else que.push_front(P(d[e.to], e.to));
      }
    }
  }
  return d;
}

void solve(ll N, vector<ll> a, vector<ll> b) {
  Graph<int> g(N);
  REP(i,N-1) {
    add_edge(g, a[i] - 1, b[i] - 1, 1);
    add_edge(g, b[i] - 1, a[i] - 1, 1);
  }
  vector<int> d1 = bfs01(g, 0);
  vector<int> d2 = bfs01(g, N - 1);
  int s1 = 0, s2 = 0;
  REP(i,N) {
    if (d1[i] <= d2[i]) ++s1; else ++s2;
  }
  if (s1 > s2) cout << "Fennec" << endl;
  else cout << "Snuke" << endl;
}

int main() {
  locale loc(locale(), new yes_no);
  cout << boolalpha << setprecision(12) << fixed;
  cout.imbue(loc);
	ll N;
	scanf("%lld", &N);
	vector<ll> b((N-1)-1+1);
	vector<ll> a((N-1)-1+1);
	for (int i = 0 ; i <= (N-1)-1 ; i++) {
	  scanf("%lld", &a[i]);
	  scanf("%lld", &b[i]);
	}
	solve(N, a, b);
	return 0;
}


Measured memory_bytes: 10696
#include<bits/stdc++.h>
using namespace std;
using ll = long long; 
using ull = unsigned long long;
using V = vector<int>;
using VV = vector<vector<int>>;
using VVV = vector<vector<vector<int>>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VVVL = vector<vector<vector<ll>>>;
template<class T> using pq = priority_queue<T>;
template<class T> using P = pair<T, T>;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define REP(i,k,n) for(int i=(k);i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define output(x,y) cout << fixed << setprecision(y) << x << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
const ll MOD = 1e9 + 7;
const ll BetsuMOD = 998244353;
ll upper = MOD + MOD;
ll under = -upper;
ll UPPER = MOD * MOD;
ll UNDER = -MOD * MOD;
const long double pi = 3.141592653589793;
int main() { // 問題文はしっかり読め!!!
	int n;
	cin >> n;
	V cnt(100000, 0);
	rep(i, n) {
		int a;
		cin >> a;
		a--;
		cnt[a]++;
	}
	int e = 0, o = 0; // 偶数ならば他を1つ巻き込む、奇数ならば自分で1まで減らせる
	rep(i, 100000) {
		if (cnt[i]) {
			if (cnt[i] % 2) o++;
			else e++;
		}
	}
	while (e) {
		if (e == 1) {
			e--;
		}
		else {
			e -= 2, o += 2;
		}
	}
	cout << o << endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.*;
public class Main{
        public static void main(String args[]){
                Scanner sc= new Scanner(System.in);
                String s = sc.next();
                int count=0;
                for(int i=0, j=s.length()-1; i<j;i++,j--){
                  if(s.charAt(i)!=s.charAt(j))
                  count++;
                }
                System.out.println(count);
        }
}


Measured memory_bytes: 21844
program main
implicit none
integer :: n, m
integer , allocatable :: l(:), r(:)
integer :: i

read(*,*) n, m
allocate(l(m))
allocate(r(m))
do i = 1, m
read(*,*) l(i), r(i)
end do
write(*,'(i0)') max(-maxval(l)+minval(r)+1,0)

end program main


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
#include <complex>
#include <cstdio>

using namespace std;
//std::ios::sync_with_stdio(false);
//std::cin.tie(0);
const long long MOD = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
typedef vector<ll> VLL;
typedef vector<VLL> VVLL;
//typedef boost::multiprecision::cpp_int bigint;

VVLL G;
ll N,M;
vector<vector<pll>> mind;

void bfsfrom(ll s) {
	queue<ll> que;
	mind[s][s] = pll(0,s);
	que.push(s);
	while (!que.empty()) {
		ll cur = que.front();
		que.pop();
		for (ll child : G[cur]) {
			if (mind[s][child].first == -1) {
				mind[s][child] = pll(mind[s][cur].first + 1, cur);
				que.push(child);
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	cin >> N >> M;
	G.resize(N);
	for (ll m = 0; m < M; m++) {
		ll s, t;
		cin >> s >> t;
		s--; t--;
		G[s].push_back(t);
	}
	mind.resize(N, vector<pll>(N,pll(-1,-1)));
	for (ll n = 0; n < N; n++) {
		bfsfrom(n);
	}
	ll ansd = 10000;
	ll anss, anst;
	for (ll s = 0; s < N; s++) {
		for (ll t = s + 1; t < N; t++) {
			if (mind[s][t].first == -1 || mind[t][s].first == -1)continue;
			if (ansd > mind[s][t].first + mind[t][s].first) {
				anss = s, anst = t;
				ansd = mind[s][t].first + mind[t][s].first;
			}
		}
	}
	if (ansd == 10000) {
		cout << -1 << "\n";
		return 0;
	}
	ll cur = anst;
	set<ll> ans;
	ans.insert(anst);
	while (cur != anss) {
		cur = mind[anss][cur].second;
		ans.insert(cur);
	}
	cur = anss;
	while (cur != anst) {
		cur = mind[anst][cur].second;
		ans.insert(cur);
	}
	cout << ans.size() << "\n";
	for (ll c : ans) {
		cout << c+1 << "\n";
	}
	return 0;
}

Measured memory_bytes: 16000
#include<iostream>
#include <cstring>
using namespace std;
int main()
{
    int n, x, y=0;
    cin>>n;
    x=n*800;
    if(n>=15)
        for(int i=15; i<=n; ++i)
            {
                if(i%15==0)
                    y+=200;
                else
                    continue ;
            }

    cout<<x-y;
    return 0;
}

Measured memory_bytes: 256
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    job = [[] for i in range(m+1)]
    for i in range(n):
        a,b = map(int,ipt().split())
        if a <= m:
            job[a].append(-b)
    ma = 0
    hq = []
    for i in range(m+1):
        for j in job[i]:
            hpq.heappush(hq,j)
        if hq:
            ma += hpq.heappop(hq)
    print(-ma)

    return None

if __name__ == '__main__':
    main()


Measured memory_bytes: 87332
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define si size()
#define bk back()
#define popb pop_back()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define endl "\n"
#define lb lower_bound
#define ub upper_bound
#define emp empty()
#define beg begin()
#define en end()
#define ump unordered_map
#define forl(i,a,n) for(int i=a;i<n;i++)
#define rfor(i,n,a) for(int i=n;i>=a;i--)
#define fore(i,a,n) for(int i=a;i<=n;i++)
#define len length()
#define ld long double
const int mod=1e9+7;
int main()
{
    int n;
    cin>>n;
    ld arr[n+1];
    forl(i,1,n+1) cin>>arr[i];
    ld dp[n+1][n+1];
    forl(i,0,n+1)forl(j,0,n+1) dp[i][j]=0;
    dp[0][0]=1;
    forl(i,1,n+1)
    {
        forl(j,0,n+1)
        {
            if(j-1>=0)dp[i][j]+=dp[i-1][j-1]*arr[i];
            dp[i][j]+=dp[i-1][j]*(1-arr[i]);
        }
    }
    ld ans=0;
    forl(i,0,n+1)
    {
        if(i>n-i)
        {
            ans+=dp[n][i];
        }
    }

    cout<<setprecision(10)<<fixed<<ans<<endl; 
   

}

Measured memory_bytes: 140928
def lcs():
    x = raw_input()
    y = raw_input()
    a, b = len(x), len(y)
    x1 = [0 for k in range(b+1)]
    for i in xrange(a):
        e = x[i]
        x2 = x1+[]
        for j in xrange(b):
            if e == y[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1] < x1[j]:
                x1[j+1] = x1[j]
    print max(x1)
 
n = input()
for i in xrange(n):
    lcs()

Measured memory_bytes: 6504
import math

N, M  = map(int, input().split())

MOD = 10**9+7

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

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

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

    return arr

fact = factorization(M)

ans = 1
if M == 1:
  print(1)

else:


  for i in range(len(fact)):
    ans *= ( math.factorial(N-1+fact[i][1]) ) // ( (math.factorial(N-1)) * (math.factorial(fact[i][1])) ) % MOD
    ans = ans%MOD

  print(ans)


Measured memory_bytes: 115036
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

using namespace std;

#define fori(x) for (int i = 0; i < x; ++i)
#define forj(x) for (int j = 0; j < x; ++j)

typedef long long ll;

const int INF = 2e9 + 5;
const int alength=100100;

int main() {
	int n;ll k;
	cin>>n>>k;
	map<ll,ll> m;
	fori(n){
		int a,b;
		cin>>a>>b;
		auto itr=m.find(a);
		if(itr!=m.end()){
			m[a]+=b;
		}else{
			m[a]=b;
		}
	}

	for(auto a:m){
		k-=a.second;
		if(k<=0){
			cout<<a.first<<endl;
			return 0;
		}
	}
}

Measured memory_bytes: 7584
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        init();

        int N = nextInt();
        int[] nums = new int[N];
        long[] occurrences = new long[N + 1];
        long[] includeAll = new long[N + 1];
        long[] excludeOne = new long[N + 1];

        for (int i = 0; i < N; i++) {
            nums[i] = nextInt();
            occurrences[nums[i]]++;
        }

        for (int i = 0; i < occurrences.length; i++) {
            includeAll[i] = chooseN2(occurrences[i]);
            if (occurrences[i] > 0) excludeOne[i] = chooseN2(occurrences[i] - 1);
        }

        long sumIncludeAll = Arrays.stream(includeAll).sum();

        for (int num : nums) {
            System.out.println(sumIncludeAll - includeAll[num] + excludeOne[num]);
        }
    }

    private static long chooseN2(long n) {
        return (n * (n - 1))/2;
    }

    //Input Reader
    private static BufferedReader reader;
    private static StringTokenizer tokenizer;

    private static void init() {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
    }

    private static String next() throws IOException {
        String read;
        while (!tokenizer.hasMoreTokens()) {
            read = reader.readLine();
            if (read == null || read.equals(""))
                return "-1";
            tokenizer = new StringTokenizer(read);
        }

        return tokenizer.nextToken();
    }

    private static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
}


Measured memory_bytes: 78852
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define all(x)    (x).begin(),(x).end()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  vector<int> a(5);
  int k;
  rep(i,5) cin>>a[i];
  cin>>k;
  bool flag = true;
  for(int i=0;i<5;i++)
    for(int j=i+1;j<5;j++)
      if(a[j] - a[i] > k) flag = false;
  string s = flag ? "Yay!" : ":(";
  cout << s << endl;
}



Measured memory_bytes: 256
import math

A, B = map(int, input().split())


ans = -1

for i in range(1, 1251):
    
    a = int(math.floor(i * 0.08))
    b = int(math.floor(i * 0.1))

    if (a == A and b == B):
        ans = i
        break

print(ans)

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int64 N, Q;
	cin >> N >> Q;
	vector<int64> c(N), res(Q), cnt(N, 0);
	REP(i, N) {
	  cin >> c[i];
	  c[i]--;
	}
	using T = tuple<int64, int64, int64>;
	vector<T> q(Q);
	REP(i, Q) {
	  int64 l, r;
	  cin >> l >> r; l--;
	  q[i] = T(l, r, i);
	}
	sort(all(q), [](T a, T b) {
	  int64 la, ra, _a, lb, rb, _b;
	  tie(la, ra, _a) = a;
	  tie(lb, rb, _b) = b;
	  return (la / 1000 == lb / 1000) ? ra < rb : la < lb;
	});
	int64 l = 0, r = 0;
	int64 ret = 0;
	REP(i, Q) {
	  int64 ll, rr, id;
	  tie(ll, rr, id) = q[i];
	  while (r < rr) {
	    if (cnt[c[r]] == 0) ret++;
	    cnt[c[r++]]++;
	  }
	  while (l > ll) {
	    if (cnt[c[l-1]] == 0) ret++;
	    cnt[c[--l]]++;
	  }
	  while (l < ll) {
	    if (cnt[c[l]] == 1) ret--;
	    cnt[c[l++]]--;
	  }
	  while (r > rr) {
	    if (cnt[c[r-1]] == 1) ret--;
	    cnt[c[--r]]--;
	  }
	  res[id] = ret;
	}
	REP(i, Q) {
	  cout <<  res[i] << endl;
	}
}


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

int main(){
    int n, m; cin >> n >> m;
    vector<int> cnt(n,1);
    vector<int> red(n,0);
    red[0] = 1;
    for(int i=0; i<m; i++){
        int x, y; cin >> x >> y; x--; y--;
        if(red[x] == 1){
            red[y] = 1;
            if(cnt[x] == 1){
                red[x]--;
            }
        }
        cnt[x]--;
        cnt[y]++;
    }
    int ans = 0;
    for(auto& v:red){
        ans += v;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define pii pair<int,int>
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf (int)50000000000 //5･10^10
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
int n,m;
int par[100010],ranked[100010],size[100010];
void init(int n) {
  rep(i,n) {
    par[i]=i;
    ranked[i]=0;
    size[i]=1;
  }
}

int root(int x) {
  if(par[x]==x) return x;
  return par[x]=root(par[x]);
}

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

void unite(int x,int y) {
  x=root(x);
  y=root(y);
  if(x==y) return;
  if(ranked[x]<ranked[y]) {
    par[x]=y;
    size[y]+=size[x];
  }
  else {
    par[y]=x;
    if(ranked[x]==ranked[y]) ranked[x]++;
    size[x]+=size[y];
  }
}

signed main() {
  cin>>n>>m;
  int Max=n*(n-1)/2;
  vector<pii>vec(m);
  vector<int>ans(m+1);
  rep(i,m) {
    int a,b;
    cin>>a>>b;
    vec[i].F=a;
    vec[i].S=b;
  }
  vrever(vec);
  init(n);
  ans[0]=Max;
  rep(i,m) {
    int a=vec[i].F,b=vec[i].S;
    if(!same(a,b)) {
      Max-=size[root(a)]*size[root(b)];
      unite(a,b);
    }
    ans[i+1]=Max;
  }
  vrever(ans);
  rep(i,m) cout<<ans[i+1]<<endl;
}

Measured memory_bytes: 6016
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		
		int n = in.nextInt();
		int l = in.nextInt();
		int s = 0;
		int z;
		for(int i = 1; i <= n; i++)
		{
			z = l + i - 1;
			s += z;
		}
		
		
		int max = Integer.MAX_VALUE;
		int res = -1;
		for(int i = 1; i <= n; i++)
		{
			int tmp = s - (l + i - 1);
			int cur = Math.abs(s - tmp);
			
			if(cur < max)
			{
				res = i;
				max = cur;
			}
		}
		
		out.println((s - (l + res - 1)));
		out.close();
	}
	
	static class InputReader
	{
		BufferedReader reader;
		StringTokenizer tokenizer;
		
		public InputReader(InputStream stream)
		{
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}
		
		public String next()
		{
			while(tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					tokenizer = new StringTokenizer(reader.readLine());
				}
				catch(IOException e)
				{
					throw new RuntimeException(e);
				}
			}
			
			return tokenizer.nextToken();
		}
		
		public int nextInt()
		{
			return Integer.parseInt(next());
		}
	}
}

Measured memory_bytes: 21204
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#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())

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

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

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

  int N, W;
  while(cin>>N>>W,N){
	VI hist(20,0);
	int num = 0, height = 0;
	REP(i,N){
	  int x; cin >> x;
	  height = max(height, ++hist[x/W]);
	  num = max(num, x/W);
	}
	double ans = 0;
	for(int i=0;i<num;++i){
	  ans += (num - i)*1.0 / num * (hist[i]*1.0 / height);
	}
	ans += 0.01;
	printf("%.6lf\n", ans);
  }
  
  return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = int(A); I < int(B); ++I)
#define FORR(I,A,B) for(ll I = int((B)-1); I >= int(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //ai>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //ai>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll n;
	cin >> n;
	vector<ll> a(n,0);
	FOR(i,0,n)cin >> a[i];
	ll q;
	cin >> q;
	ll b,e,k;
	FOR(j,0,q){
		cin >> b >> e >> k;
		ll ans = 0;
		FOR(i,b,e){
			if(a[i]==k)ans++;
		}
		cout << ans << endl;
	}
}



Measured memory_bytes: 3184
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	a := getNextInt(scanner)
	b := getNextInt(scanner)
	c := getNextInt(scanner)
	k := getNextInt(scanner)
	if ok(a, b, c, k) {
		fmt.Fprintln(writer, "Yes")
		return
	}
	fmt.Fprintln(writer, "No")
}

func ok(a, b, c, k int) bool {
	if k == 0 {
		return b > a && c > b
	}
	return ok(a<<1, b, c, k-1) || ok(a, b<<1, c, k-1) || ok(a, b, c<<1, k-1)
}


Measured memory_bytes: 1820
from collections import deque
H, W = map(int, input().split())
sH, sW = map(int, input().split())
sH, sW = sH - 1, sW - 1
gH, gW = map(int, input().split())
gH, gW = gH - 1, gW - 1
stage = []
scores = []
for _ in range(H):
    stage.append(list(input()))
    scores.append([float('inf')] * W)
scores[sH][sW] = 0
moveA_q = deque()
moveB_q = deque()
moveA_q.append([sW, sH])
moveB_q.append([sW, sH])
dx_list = [0, 1, 0, -1]
dy_list = [1, 0, -1, 0]
while moveA_q or moveB_q:
    if scores[gH][gW] != float('inf'):
        break
    # 移動AでBFS
    while moveA_q:
        x, y = moveA_q.pop()
        moveB_q.append([x, y])
        for dx, dy in zip(dx_list, dy_list):
            nx, ny = x + dx, y + dy
            if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                continue
            # if scores[ny][nx] == float('inf'):
            if scores[ny][nx] > scores[y][x]:
                scores[ny][nx] = scores[y][x]
                moveA_q.append([nx, ny])


    # 移動bで動けるマスをmodeA_qに格納
    while moveB_q:
        x, y = moveB_q.pop()
        for dx in range(-2, 3):
            for dy in range(-2, 3):
                nx, ny = x + dx, y + dy
                if nx < 0 or W <= nx or ny < 0 or H <= ny or stage[ny][nx] == '#':
                    continue
                # if scores[ny][nx] == float('inf'):
                if scores[ny][nx] > scores[y][x]:
                    moveA_q.append([nx, ny])
                    scores[ny][nx] = scores[y][x] + 1

# print(*scores,sep='\n')
if scores[gH][gW] == float('inf'):
    print(-1)
else:
    print(scores[gH][gW])

Measured memory_bytes: 178636