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

std::vector<std::vector<int>> v;
map<pair<int,int>, int> emap;

std::vector<std::vector<int>> iig(int vn, int en) {
	std::vector<std::vector<int>> res(vn);
        for(int i = 0; i < en; i++) {
                int s, t;
                std::cin >> s >> t;
                s--; t--;
                res[s].push_back(t);
                res[t].push_back(s);
		emap.insert({{t, s}, i});
		emap.insert({{s, t}, i});
        }
        return res;
}

vector<int> ec;

void dfs(int a, int p=-1, int pc=-1) {
	int c = 0;
	for(int b: v[a]) {
		if (b == p) continue;
		if (c == pc) c++;
		ec[emap[{a, b}]] = c;
		dfs(b, a, c);
		c++;
	}
}




int main() {
	int n;
	cin >> n;
	v = iig(n, n-1);
	ec = vector<int>(n-1);
	int r = 0;
	for(int i = 0; i < n; i++) {
		if (v[i].size() > v[r].size()) r = i;
	}
	dfs(r);
	cout << v[r].size() << endl;
	for(int p: ec) {
		cout << p+1 << endl;
	}
}


Measured memory_bytes: 18944
#include <iostream>
#include <vector>
using namespace std;
typedef pair<int, int> P;
int n, w[100000];
vector<P> v[100000];
void f(int x, int y, int z){
    w[x]=z;
    for(int i=0;i<v[x].size();i++){
        int u=v[x][i].first;
        if(u!=y){
            if(v[x][i].second%2==0){
                f(u, x, z);
            }else{
                f(u, x, 1-z);
            }
        }
    }
}
int main(void){
    cin>>n;
    for(int i=0;i<n-1;i++){
        int a, b, c;
        cin>>a>>b>>c;
        a--;
        b--;
        c%=2;
        v[a].push_back(P(b, c));
        v[b].push_back(P(a, c));
    }
    fill(w, w+n, -1);
    f(0, -1, 0);
    for(int i=0;i<n;i++){
        cout<<w[i]<<endl;
    }
}


Measured memory_bytes: 9984
n,m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]

A = [-1] * n
no = 0
for i in range(m):
    C[i][0]-=1
    if A[C[i][0]] != -1 and A[C[i][0]] != C[i][1]:
        no = 1
    else:
        A[C[i][0]] = C[i][1]
# print(A)

if no == 1 or (A[0] == 0 and n > 1):
    print(-1)
else:
    # print("else")
    for i in range(n):
        if A[i] == -1:
            if (i == 0 and n>1):
                A[i] = 1
            else:
                A[i] = 0
    # print(A)
        
    print("".join([str(i) for i in A]))

Measured memory_bytes: 38460
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp11
{
    class Class20
    {
        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            Dictionary<int, int> A = new Dictionary<int, int>();
            bool[] Loop = new bool[N + 1];
            Loop[0] = true;
            for(int i = 1; i <= N; i++)
            {
                A.Add(i,int.Parse(Console.ReadLine()));
                Loop[i] = true;
            }
            int search = 1;
            int count = 0;
            while (search != 2)
            {
                if (Loop[search] == false)
                {
                    count = -1;
                    break;
                }
                Loop[search] = false;
                search = A[search];
                count += 1;
            }
            Console.WriteLine(count);
        }
    }
}


Measured memory_bytes: 21216
a, b, c, x, y = list(map(int, input().split()))

total1 = min(a+b, 2*c) * min(x, y)

if x > y:
  total1 += (x-y) * a
elif y > x:
  total1 += (y-x) * b

total2 = max(x, y) * 2*c

print(min(total1, total2))

Measured memory_bytes: 3060
//#include <bits/stdc++.h>
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>
#include <deque>
#include <set>
#include <stack>
#include <time.h>
 
using namespace std;
 
typedef long long ll;
const ll nmax = 1e9 + 7;
const ll MOD = 998244353;
const double PI = 2 * asin(1);

void display(vector <ll> A){
  for (int i = 0; i < A.size(); i++){
    cout << A[i];
    if (i != A.size() - 1) cout << " ";
  }
  cout << endl;
}

int main(){
  int N, K; ll S; cin >> N >> K >> S;

  vector <ll> A(N);

  for (int i = 0; i < K; i++){
    A[i] = S;
  }
  for (int i = K; i < N; i++){
    A[i] = 1e9;
    if (S == 1e9) A[i]--;
  }
  display(A);

  return 0;
}


Measured memory_bytes: 2944
/* vim:set foldmethod=marker: */
#include <bits/stdc++.h>
using namespace std;

//{{{
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define RREP(i,a,b) for(int i=(int)(a); i>=b; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,n,0)
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;

#define dump(x) (cerr << #x << "=" << x << endl)
template<class T> ostream& osContainer(ostream& os,T c) { os<<'[';for(decltype(c.begin()) it=c.begin();it!=c.end();it++)os<<*it<<',';os<<']';return os; }
template<class T> ostream& operator<<(ostream& os,const vector<T>& v) { return osContainer(os,v); }
template<class T> ostream& operator<<(ostream& os,const set<T>& s) { return osContainer(os,s); }
template<class T> ostream& operator<<(ostream& os,const multiset<T>& s) { return osContainer(os,s); }
template<class T,class S> ostream& operator<<(ostream& os,const map<T,S>& m) { return osContainer(os,m); }
template<class T,class S> ostream& operator<<(ostream& os,const multimap<T,S>& m) { return osContainer(os,m); }
template<class T1,class T2>
ostream& operator<<(ostream& os, const pair<T1,T2>& p){ os << '(' << p.first << ',' << p.second << ')'; return os; }

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


int minoverzero(vector<int>& v) {
    int a=10000000;
    int res = -1;
    for(int i=0; i < v.size(); i++){
        if (v[i] > 0 && v[i] < a){
            a = v[i];
            res = i;
        }
    }
    return res;
}

int maxleft(vector<int>& v) {
    int a = -1;
    int res = -1;
    for(int i = v.size()-1; i >= 0; i--) {
        if (a < v[i]) {
            a = v[i];
            res = i;
        }
    }

    return res;
}

void solve() {
    int K, T;
    cin >> K >> T;
    vector<int> a(T);
 
    rep(i, T) cin >> a[i];
 
    int mn = minoverzero(a);
    int mx = maxleft(a);
 
    while (mn != mx && mn != -1 && a[mx] > 0) {
        a[mn]--;
        a[mx]--;
        mn = minoverzero(a);
        mx = maxleft(a);
    }

    if (a[mx] > 0) {
        cout << a[mx] - 1 << endl;
    } else {
        cout << 0 << endl;
    }
}
 
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(12);
    solve();
}


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

int main() {
  int n, m;
  double sum = 0;
  cin >> n >> m;
  int p[n];
  for (int i = 0; i < n; ++i) {
    cin >> p[i];
    sum += p[i];
  }
  sort(p, p + n, greater<int>());
  double a = ((double)1/((double)4*(double)m))*(double)sum;
  if (p[m-1] >= a) {
    cout << "Yes";
  }
  else {
    cout << "No";
  }
}

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

using namespace std;
typedef long long int ll;
typedef pair<ll, ll > pi;  
typedef pair<pair<ll, ll >, ll > pii;  
vector<ll > vec;
vector<vector<ll > > vec2;
ll MOD = 1000000007;
ll INF = 1145141919454519;

int main() {

    ll N, K;
    cin >> N >> K;

    //入力
    priority_queue<pi > que;
    for(ll i = 0; i < N; i++){
        ll t, d;
        cin >> t >> d;
        que.push(make_pair(d, t));
    }
    //選んだネタとその個数を記録
    //mapで管理するのはよくないほんとよくない
    //map<ll, ll > mp;
    set<ll > st;
    //美味しいさが大きい順に選ぶ
    ll sum = 0;
    priority_queue<pi , vector<pi >, greater<pi > > kouho;
    for(ll i = 0; i < K; i++){
        ll t = que.top().second;
        ll d = que.top().first;
        que.pop();
        sum += d;

        if(st.find(t) != st.end()) kouho.push(make_pair(d, t));
        st.insert(t);

    }

    //選び直し，食べる寿司の種類を増やしてみた時，ポイントが増えますか？
    ll ans = sum + st.size() * st.size();
    for(ll i = 0; ; i++){
        if(kouho.empty() || que.empty()) break;

        ll t = que.top().second;
        ll d = que.top().first;
        que.pop();
        //cout << ans - (type * type) - kouho.top().first.first + d + (type+1) * (type+1) << endl;
        if(st.find(t) != st.end()) continue;
        if(!kouho.empty()){
            sum = sum - kouho.top().first + d;
            st.insert(t);
            kouho.pop();
        }
        ans = max(ans, (ll)(sum + st.size() * st.size()));
        // cout << t << " " << d << " " << ans << endl;
    }

    cout << ans << endl;

}


Measured memory_bytes: 5744
#include<bits/stdc++.h>
using namespace std;
int a, b, c;
int ansa, ansb;
int main() {
	while (scanf("%d,%d,%d", &a, &b, &c) != EOF) {

		if (pow(c, 2) == (pow(a, 2) + pow(b, 2))) {
			ansa++;
		} else if (a == b) {
			ansb++;
		}
	}
	cout << ansa << endl;
	cout << ansb << endl;
}

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

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

int main() {
  int w, h, n;
  cin >> w >> h >> n;

  int maxx = w;
  int minx = 0;
  int maxy = h;
  int miny = 0;

  int x, y, a;
  rep(i, n) { cin >> x >> y >> a;
    if (a == 1) minx = max(x, minx);
    if (a == 2) maxx = min(x, maxx);
    if (a == 3) miny = max(y, miny);
    if (a == 4) maxy = min(y, maxy);
  }

  int ans = (maxx - minx) * (maxy - miny);
  if (maxx <= minx || maxy <= miny) ans = 0;

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


Measured memory_bytes: 256
// 累積和
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define print(x) cout << x << endl;
using namespace std;
typedef long long ll;

int main()
{
    int N, K;
    cin >> N >> K;
    double P[N + 1] = {};
    for (int i = 1; i < N + 1; i++) {
        int p;
        cin >> p;
        P[i] += P[i - 1] + (1.0 + p) / 2.0;
    }

    double res = 0.0;

    for (int i = K; i < N + 1; i++) {
        res = max(res, P[i] - P[i - K]);
    }

    cout << fixed << setprecision(8) << res << endl;
    return 0;
}

Measured memory_bytes: 1792
mod=10**9+7
n,m=map(int,input().split())
x=list(map(int,input().split()))
y=list(map(int,input().split()))
xl=0
xt=0
yl=0
yt=0
for i in range(n-1):
  if i==0:
    for j in range(1,n):
      xt+=x[j]-x[i]
    xl=xt
  else:
    xt-=(x[i]-x[i-1])*(n-i)
    xl=(xl+xt)%mod
for i in range(m-1):
  if i==0:
    for j in range(1,m):
      yt+=y[j]-y[i]
    yl=yt
  else:
    yt-=(y[i]-y[i-1])*(m-i)
    yl=(yl+yt)%mod
print(xl*yl%mod)

Measured memory_bytes: 18576
#include <iostream>
#include <cstring>
#include <vector>
#include <map>
#include <string>
#include <algorithm>

 
using namespace std;

typedef long long ll;
typedef long double ld;
#define L(ID) ((ID*2)+1)
#define R(ID) ((ID*2)+2)
#define M(L,R) ((L+R)/2)
#define forr(start,end) for(int i = start; i < end; i++)
#define gap ' '
 
const int MAXN = 1e5 + 5;
int n, m, number;

ll largest(ll a, ll b){
	return (a<b)?b:a;
}
ll smallest(ll a, ll b){
	if(a < b)return a;
	return b;
}

int main(){
	cin >> n >> m;
	int cntA = 0, cntP = 0;
	map<int,string> a;
	string t;
	int b[MAXN+1];
	memset(b, 0, sizeof(b));
	for(int i = 0; i < m; ++i){
		cin >> number >> t;
		if(a[number] == "WA"){
			if(t == "AC"){
				a[number] = "AC";
				++cntA;
			}
			else{
				b[number]++;
			}
			continue;
		}
		if(a[number] == "AC"){
			continue;
		}
		if(t == "AC"){
			a[number] = "AC";
			++cntA;
		}
		else{
			a[number] = "WA";
			b[number]++;
		}
	}
	cout << cntA << " ";
	for(int i = 1; i <= n; ++i){
		if(a[i] == "AC"){
			cntP+=b[i];
		}
	}
	cout << cntP << endl;

    return 0;
}


Measured memory_bytes: 11520
import itertools

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

books = []

for _ in range(n):
    c = list(map(int, input().split()))
    books.append(c)

patern = []

for i in range(1, n+1):
    patern += itertools.combinations(range(n), i)

cost = 10**7


for j in patern:
    total = 0
    flag = 1
    for k in range(1,m+1):
        cnt = 0
        for l in list(j):
            cnt += books[l][k]
        if cnt < x:
            flag *= 0
    if flag == 1:
        for l in j:
            total += books[l][0]
        cost = min(cost, total)

if cost == 10**7:
    print(-1)
else:
    print(cost)

Measured memory_bytes: 9400
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
 
//priority_queue<long long, vector<long long>, greater<long long>> pq;

const double TL = 1.5 * CLOCKS_PER_SEC;
mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
#define clr(x, y) memset(x, y, sizeof(x))
#define forn(i, n) for (int i = 0; i < n; i++)
#define LL long long


const double pi = acos(-1.0);

int n;
int a[200005];

int main() {
  //auto start_clock = clock();
#ifdef LOCAL
  freopen("in", "r", stdin);
#endif
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    int w;
    scanf("%d", &w);
    a[w - 1] += 1;
  }
  for (int i = 0; i < n; i++) {
    printf("%d\n", a[i]);
  }

  
  //double r;
  //cin >> r;
  //cout << 2 * pi * r << endl;
  return 0;
}

Measured memory_bytes: 4608
#include <iostream>

using namespace std;

int n, a[100005][3], dp[100005][3];

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1 ; i <= n ; ++i){
	cin >> a[i][0] >> a[i][1] >> a[i][2];
}
for(int i = 1 ; i <= n ; ++i){
	for(int j = 0 ; j < 3 ; ++j){
		for(int v = 0 ; v < 3 ; ++v){
			if(j == v)
				continue;
			dp[i][j] = max(dp[i][j], dp[i - 1][v]);
		}
		dp[i][j] += a[i][j];
	}
}
cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << endl;

return 0;
}



Measured memory_bytes: 2560
N, S = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0]*(S+1) for _ in range(N+1)]
dp[0][0] = 1
mod = 998244353


for i in range(N):
  a = A[i]
  for j in range(S+1):
    if j >= a:
      dp[i+1][j] += dp[i][j-a] + dp[i][j]*2
      dp[i+1][j] %= mod
    else:
      dp[i+1][j] += dp[i][j]*2 
      dp[i+1][j] %= mod

print(dp[N][-1]%mod)

Measured memory_bytes: 132608
#include<bits/stdc++.h>
#include <math.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main() {
int N;
  cin >>N;
  int count=0;
  if((N !=2) &&(N !=1)) {
  while(N>0) {
    if(N-3>=3) {
N=N-3;
      count++;
    }
    if (N-3<3) {
      count++;
      break;
    }
  }
  cout << count << endl;
  }
  
  else if ((N==2) || (N==1)) {
    cout << 0 << endl;
  }
  
  
  
}
  

Measured memory_bytes: 256
import java.util.*;
public class Main{

  public static void main(String[] args){
      int MOD = 1000000007;
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      if(Math.abs(n - m) > 1) {
        System.out.println(0);
        return;
      }
      long sum = 1;
      sum = fac(sum, n);
      sum = fac(sum, m);
      if(Math.abs(n - m) == 0)
        sum = sum * 2 % MOD;
      System.out.println(sum);
  }

  private static long fac(long sum, int n) {
      int MOD = 1000000007;
      while(n > 1) {
        sum = sum * n % MOD;
        n--;
      }
      return sum;
  } 
}


Measured memory_bytes: 21844
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int a[200001], b[200001];

int main() {
  int N, M;
  int i, j, tmp;
  scanf ("%d", &N);
  
  for (i=1;i<=N;i++) {
      scanf("%d", &a[i]);
  }
  
  for (i=N;i>0;i--) {
    tmp = 0;
    for (j=N/i;j>1;j--) {
        tmp ^= b[i*j];
    }
    b[i] = tmp ^ a[i];
  }
  
  M = 0;
  for (i=1;i<=N;i++) {
    M += b[i];
  }
  
  printf("%d\n", M);
  
  for (i=1;i<=N;i++) {
    if (b[i]==1) printf("%d ", i);
  }
  return 0;
}




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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}


struct UnionFind {
  vector<int> data;
  UnionFind(int size) : data(size, -1) { }
  bool unionSet(int x, int y) {
    x = root(x); y = root(y);
    if (x != y) {
      if (data[y] < data[x]) swap(x, y);
      data[x] += data[y]; data[y] = x;
    }
    return x != y;
  }
  bool findSet(int x, int y) {
    return root(x) == root(y);
  }
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  int size(int x) {
    return -data[root(x)];
  }
};

void solve() {
    int N;
    cin >> N;
    vector<pll> A(N);
    map<pii, int> M;
    for (int i = 0; i < N; i++) {
        ll x, y;
        cin >> x >> y;
        A[i] = {x, y};
        M[{x, y}] = i;
    }
    if (N == 1) {
        cout << 1 << endl;
        return;
    }

    ll ans = 1e18;
    ll e = 1e9;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            vector<int> flag(N);
            UnionFind uf(N);
            ll dx = A[i].first - A[j].first;
            ll dy = A[i].second - A[j].second;
            
            for (int k = 0; k < N; k++) {
                if (flag[k]) continue;
                flag[k] = 1;
                int nx = A[k].first, ny = A[k].second;
                while(M.find({nx + dx, ny + dy}) != M.end()) {
                    flag[M[{nx + dx, ny + dy}]] = 1;
                    uf.unionSet(k, M[{nx + dx, ny + dy}]);
                    nx += dx;
                    ny += dy;
                }
            }
            set<int> s;
            for (int k = 0; k < N; k++) {
                s.insert(uf.root(k));
            }
            ans = min(ans, (ll)s.size());
        }
    }
    cout << ans << endl;
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

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

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define repb(i, n) for (ll i = (n)-1; i >= 0; i--)
#define rep(i, n) repd(i, 0, n)

using namespace std;

using ll = long long;
using ul = unsigned long long;
using ld = long double;
ll mod = 1000000007;

int main() {
    ll n, k;
    cin >> n >> k;
    ll p[n];
    rep(i, n) { cin >> p[i]; }
    sort(p, p + n);

    ll ans = 0;
    rep(i, k) { ans += p[i]; }
    cout << ans << endl;

    return 0;
}



Measured memory_bytes: 3612
//Solution by Zhusupov Nurlan
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef map<string , int> MSI;
typedef vector<int> VI;
typedef pair<int, int> PII;

#define endl '\n'
#define pb(x) push_back(x)
#define sqr(x) ((x) * (x))
#define F first
#define S second
#define SZ(t) ((int) t.size())
#define len(t) ((int) t.length())
#define base LL(1e9 + 7)
#define fname ""
#define sz 1000 * 1000
#define EPS (1e-8)
#define INF ((int)1e9 + 9)
#define mp make_pair

LL n, k, x, ans, f[sz];
pair <LL, LL> s[sz];

LL get(LL v) {
  LL res = 0;
  for (int i = v; i >= 0; i = ((i + 1) & i) - 1)
    res += f[i];
  return res;
}

void upd(LL v) {
  for (int i = v; i <= n; i |= i + 1)
    f[i]++;
}

int main()
{
//    freopen(fname"in", "r", stdin);
//    freopen(fname"out", "w", stdout);

  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    x -= k;
    s[i] = mp(s[i - 1].F + x, i);
  }

  sort(s, s + n + 1);
  for (int i = 0; i <= n; i++) {
    ans += get(s[i].S);
    upd(s[i].S);
  }
  cout << ans;
}


Measured memory_bytes: 8448
#include <iostream>
#include <memory>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>

typedef long long ll;

using namespace std;

int main() {
  ll x,y=0,m=100;
  cin>>x;
  while(true){
    y++;
    m+=m/100;
    if(m>=x)break;
  }
  cout<<y<<endl;
}


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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;

const int MOD = 1000000007;

long long gcd(long long a, long long b) {
    long long tmp;
    if (a < b) {
        tmp = a;
        a = b;
        b = tmp;
    }

    long long r;
    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

int main() {
    int N;
    long long X;
    cin >> N >> X;
    long long x;
    cin >> x;
    long long ans = abs(X - x);
    for (int i = 1; i < N; i++) {
        cin >> x;
        ans = gcd(ans, abs(X - x));
    }
    cout << ans << endl;
}

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

#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, n, m) for (int i = n; i < m; i++)
#define ll long long int

using namespace std;

int main()
{
  int n;
  cin >> n;
  pair<string, pair<int, int>> sp[105]; // score, 何番目にいたか
  REP(i, n)
  {
    string s;
    int p;
    cin >> s >> p;
    sp[i] = make_pair(s, make_pair(p, i + 1));
  }

  sort(sp, sp + n);

  int i = 0;
  string city = sp[0].first;

  vector<pair<int, int>> vp;

  bool flag = true;

  while (i < n && flag)
  {
    flag = false;
    while (sp[i].first == city && i < n)
    {
      flag = true;
      vp.push_back(sp[i].second);
      i++;
    }
    city = sp[min(i, n - 1)].first;

    sort(vp.begin(), vp.end(), greater<pair<int, int>>());
    REP(k, vp.size())
    {
      cout << vp[k].second << endl;
    }
    vp.clear();
  }
}


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;ll ans;
char s[maxn];
map<pair<string,string > ,int > t;

void dfs1(int x,string a,string b) {
    if(x==n+1) {t[mp(a,b)]++;return ;}
    dfs1(x+1,a+s[x],b),dfs1(x+1,a,s[x]+b);
}

void dfs2(int x,string a,string b) {
    if(x==n) {ans+=t[mp(a,b)];return ;}
    dfs2(x-1,a+s[x],b),dfs2(x-1,a,s[x]+b);
}

int main() {
    read(n);scanf("%s",s+1);
    dfs1(1,"","");
    dfs2(2*n,"","");
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 84992
def main():
    N,K = [int(x) for x in input().split()]
    prob = 0
    for i in range(N):
        dice=i+1
        coin = 0
        while dice < K:
            dice *= 2
            coin += 1
        prob += float(1/N) * 0.5**coin
    print(prob)

if __name__ == '__main__':
    main()

Measured memory_bytes: 39280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX=100005;
int main()
{
  long long int t,n,a,r,ans,x=0;
  scanf("%lld",&n);
  if(n%1000) x=1000-(n%1000);
  printf("%lld\n",x);
 /* int neg,pos,zer;
  while(t--){
    neg=pos=zer=0;
    scanf("%d",&n);
    a=(n-1)/2;
    
    for(int i=0;i<n;i++) scanf("%d",&ar[i]);
    for(int i=1;i<n-1;i++){
      if(ar[i]>ar[i-1]){
        if(ar[i]<ar[i+1]) ar[i+1]*=-1;
      }
      if(ar[i]<ar[i-1]){
        if(ar[i]>ar[i+1]) ar[i+1]*=-1;
      }
    }
      
    
    
    printf("%lld\n",ans);
     
  }*/
  
    
    return 0;
}

Measured memory_bytes: 3808
import java.util.Scanner;

class Dice {
    int dn[] = new int[6];

    Dice(int d[]) {
        for (int i = 0; i < 6; i++) {
            dn[i] = d[i];
        }
    }

    void turnN() {
        int x = dn[0];
        dn[0] = dn[1];
        dn[1] = dn[5];
        dn[5] = dn[4];
        dn[4] = x;
    }

    void turnS() {
        int x = dn[0];
        dn[0] = dn[4];
        dn[4] = dn[5];
        dn[5] = dn[1];
        dn[1] = x;
    }

    void turnW() {
        int x = dn[0];
        dn[0] = dn[2];
        dn[2] = dn[5];
        dn[5] = dn[3];
        dn[3] = x;
    }

    void turnE() {
        int x = dn[0];
        dn[0] = dn[3];
        dn[3] = dn[5];
        dn[5] = dn[2];
        dn[2] = x;
    }

    int ans(int[][] h,int n) {
        if (h[n][1] == dn[2] || h[n][1] == dn[3])
            turnW();
        while (h[n][1] != dn[1])
            turnS();
        while (h[n][0] != dn[0])
            turnW();
        return dn[2];
    }

}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num[] = new int[6];
        for (int i = 0; i < 6; i++) {
            num[i] = sc.nextInt();
        }
        Dice d1 = new Dice(num);
        int q = sc.nextInt();
        int hint[][] = new int[q][2];
        for (int i = 0; i < q; i++) {
            for (int j = 0; j < 2; j++) {
                hint[i][j] = sc.nextInt();
            }
            System.out.println(d1.ans(hint,i));
        }
    }
}


Measured memory_bytes: 26392
#include <iostream>
#include <stack>
#define REP(i, a, n) for(int i = (a); i < (n); i++)
using namespace std;

string S;

int and3(int s1, int s2) {
  if(s1 == 2 && s2 == 2) return 2;
  if(s1 == 0 || s2 == 0) return 0;
  return 1;
}

int or3(int s1, int s2) {
  if(s1 == 0 && s2 == 0) return 0;
  if(s1 == 2 || s2 == 2) return 2;
  return 1;
}

int calc(int p, int q, int r) {
  stack<char> stk;

  REP(i, 0, S.length()) {
    if(S[i] == '(' || S[i] == '-' || S[i] == '*' || S[i] == '+') stk.push(S[i]);
    if(('0' <= S[i] && S[i] <= '2') || ('P' <= S[i] && S[i] <= 'R')) {
      int d;
      if('0' <= S[i] && S[i] <= '2') d = S[i] - '0';
      if(S[i] == 'P') d = p;
      if(S[i] == 'Q') d = q;
      if(S[i] == 'R') d = r;
      while(!stk.empty() && stk.top() == '-') {
        stk.pop();
        d = 2 - d;
      }
      stk.push(d);
    }
    if(S[i] == ')') {
      int s2 = stk.top(); stk.pop();
      int op = stk.top(); stk.pop();
      int s1 = stk.top(); stk.pop();
      stk.pop();
      int d;
      if(op == '*') d = and3(s1, s2);
      if(op == '+') d = or3(s1, s2);
      while(!stk.empty() && stk.top() == '-') {
        stk.pop();
        d = 2 - d;
      }
      stk.push(d);
    }
  }

  return stk.top();
}

int main(void) {
  while(cin >> S, S != ".") {
    int cnt = 0;
    REP(p, 0, 3) REP(q, 0, 3) REP(r, 0, 3) if(calc(p, q, r) == 2) cnt++;
    cout << cnt << endl;
  }

  return 0;
}

Measured memory_bytes: 3120
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1005;
const int maxm = 7005;

int a[N], b[N], c[N], d[N], e[N], f[N];
vector <int> vx, vy;
int dx[] = {0, 0, -1, 1}, dy[] = {-1, 1, 0, 0};
bool vis[maxm][maxm], ma[maxm][maxm];

int get_x(int val){
    return lower_bound(vx.begin(), vx.end(), val) - vx.begin();
}

int get_y(int val){
    return lower_bound(vy.begin(), vy.end(), val) - vy.begin();
}

int main(){
    int n, m; scanf("%d%d", &n, &m);
    vx.push_back(-1.1e9), vx.push_back(0);
    vy.push_back(-1.1e9), vy.push_back(0);
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i];
        vx.push_back(a[i]), vx.push_back(b[i]);
        vy.push_back(c[i]);
    }

    for(int i = 0; i < m; i++){
        cin >> d[i] >> e[i] >> f[i];
        vy.push_back(e[i]), vy.push_back(f[i]);
        vx.push_back(d[i]);
    }

    sort(vx.begin(), vx.end()), vx.erase(unique(vx.begin(), vx.end()), vx.end());

    sort(vy.begin(), vy.end()), vy.erase(unique(vy.begin(), vy.end()), vy.end());


    for(int i = 0; i < n; i++){
        a[i] = get_x(a[i]), b[i] = get_x(b[i]), c[i] = get_y(c[i]);
        for(int j = a[i]*2 - 1; j < 2 * b[i]; j++)
            ma[j][2*c[i] - 1] = true;
    }

    for(int i = 0; i < m; i++){
        d[i] = get_x(d[i]), e[i] = get_y(e[i]), f[i] = get_y(f[i]);
        for(int j = e[i]*2-1; j < f[i]*2; j++)
            ma[2*d[i]-1][j] = true;
    }

    int sx = get_x(0)*2 - 1, sy = get_y(0)*2 - 1;

    queue<pair<int, int>> qu;
    qu.push({sx, sy}), vis[sx][sy] = true;
    ll ans = 0;
    bool flag = false;
    while(!qu.empty()){
        int ux = qu.front().first, uy = qu.front().second; qu.pop();
        if(ux == maxm-1 || uy == maxm-1 || ux == 0 || uy == 0){
            flag = true;
            break;
        }
        if(ux % 2 == 0 && uy % 2 == 0){
            int x = ux / 2, y = uy / 2;
            ans += 1ll * (vx[x + 1] - vx[x]) * (vy[y + 1] - vy[y]);
        }
        for(int i = 0; i < 4; i++){
            int xx = ux + dx[i], yy = uy + dy[i];
            if(xx >= maxm || xx < 0 || yy >= maxm || yy < 0 || ma[xx][yy] || vis[xx][yy]) continue;
            qu.push({xx, yy});
            vis[xx][yy] = true;
        }
    }
    if(flag) printf("INF\n");
    else printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 89080
#include <iostream>
using namespace std;
const int MAX_N = 110;
int i, j, minj, n, x, cnt, k, f, a[MAX_N];
bool flag = 0;
void selectionSort(int A[MAX_N], int N) { // N??????????´??????????0-?????????????????????A
	cnt = 0;
	f = 0;
	for (i = 0; i < N; ++i) {
		minj = i;
		flag = 0;
		for (j = i; j < N; ++j) {
			flag = 0;
			if (A[j] < A[minj]) {
				minj = j;
				f++;
			}
		}

		if (f != 0) {
			x = A[i];
			A[i] = A[minj];
			A[minj] = x;
			cnt++;

		}

		f = 0;

	}
	for (k = 0; k < N - 1; ++k) {
		cout << A[k] << " ";
	}
	cout << A[N - 1] << endl;
	cout << cnt << endl;
}
int main() {

	cin >> n;
	for (j = 0; j < n; ++j) {
		cin >> a[j];
	}
	selectionSort(a, n);
	return 0;
}

Measured memory_bytes: 3084
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    var s = sc.nextLine()
    var ok = true
    do {
        ok = false
        if (s.endsWith("eraser")) {
            s = s.removeSuffix("eraser")
            ok = true
        } else if (s.endsWith("erase")) {
            s = s.removeSuffix("erase")
            ok = true
        } else if (s.endsWith("dreamer")) {
            s = s.removeSuffix("dreamer")
            ok = true
        } else if (s.endsWith("dream")) {
            s = s.removeSuffix("dream")
            ok = true
        }
    } while (ok)
    println(if (s.length == 0) "YES" else "NO")
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}

Measured memory_bytes: 114600
/**
 *    author:  math2do
 *    created: 21.11.2019 17:7:56
**/

#include <bits/stdc++.h>

using namespace std;

char a[3001];
char b[3001];
char str[3001];
int at = 0;

vector <vector <int>> dp;
vector <vector <int>> st;

void build(int i, int j, int na, int nb) {
  if (i == na) return;
  if (j == nb) return;

  int which = st[i][j];
  if (which == 0) {
    str[at++] = a[i];
    build(i + 1, j + 1, na, nb);
  } else if (which == 1) {
    build(i + 1, j, na, nb);    
  } else{
    build(i, j + 1, na, nb);    
  } 
}

int solve(int i, int j, int na, int nb) {
  if (i == na) return 0;
  if (j == nb) return 0;
  if (dp[i][j] != -1) return dp[i][j];
  int ans = 0;
  if (a[i] == b[j]) {
    ans = max(ans, 1 + solve(i + 1, j + 1, na, nb));
    st[i][j] = 0;
  } else {
    int exa = solve(i + 1, j, na, nb);
    int exb = solve(i, j + 1, na, nb);
    if (exa > exb) {
      st[i][j] = 1;
    } else {
      st[i][j] = 2;
    } 
    ans = max(ans, exa);
    ans = max(ans, exb);
  }
  return dp[i][j] = ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  #ifdef LOCAL
    freopen("lcs.in", "rt", stdin);
  #endif
  scanf("%s", a);
  scanf("%s", b);

  int na = strlen(a);
  int nb = strlen(b);
  dp.resize(na);
  st.resize(na);

  for (int i = 0; i < na; i++) {
    dp[i].resize(nb);
    st[i].resize(nb);
    fill(dp[i].begin(), dp[i].end(), -1);
    fill(st[i].begin(), st[i].end(), -1);
  } 

  solve(0, 0, na, nb);
  build(0, 0, na, nb);
  str[at++] = '\0';

  printf("%s", str);
  return 0;
}


Measured memory_bytes: 71296
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
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; }
const long long INF = 1LL << 60;
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int  main(){
int n;cin >> n;
vector<ll>h(n+10);
for(int i=0;i<n;i++)cin >> h.at(i);
vector<ll>dp(n+10,INF);
dp.at(0)=0;
for(int i=0;i<n;i++){
    chmin(dp.at(i+1),dp.at(i)+abs(h.at(i)-h.at(i+1)));
    chmin(dp.at(i+2),dp.at(i)+abs(h.at(i)-h.at(i+2)));
}
cout << dp.at(n-1)<<endl;
}



Measured memory_bytes: 1792
#include<iostream>
#include<string>
using namespace std;
int main(){
	int w;
	while(true){
	cin>>w;
	if(w==-1)
		break;
	int count=0;
	count+=1150;
	for(int i=10;i<min(20,w);i++)
		count+=125;
	for(int i=20;i<min(30,w);i++)
		count+=140;
	for(int i=30;i<w;i++)
		count+=160;
	cout<<4280-count<<endl;
	}
    return 0;
}
 

Measured memory_bytes: 1160
INF = 10 ** 18
n, m = map(int, input().split())
c = list(map(int, input().split()))
dp = [INF] * (n + 1)
dp[0] = 0
for i in range(m):
    for j in range(c[i], n + 1):
        dp[j] = min(dp[j], dp[j - c[i]] + 1)

print(dp[n])


Measured memory_bytes: 7520
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define pd(a,n) for(int i=0;i<n;i++)cout<<a[i]<<((i==n-1)?"\n":" ")
#define pdd(a,n,m)for(int i=0;i<m;i++)pd(a,m)
#define mp make_pair
#define pb push_back
#define ll __int64
#define __int64 long long
#define P pair<int,int>
#define PP pair<P,int>

int n,k;
ll x[1111];

int main(){
  cin>>n;
  rep(i,n)cin>>x[i];

  ll p=0,tmp=10000000;
  for(ll i=0;i<=1000000;i++){
    ll cnt=0;
    rep(j,n)cnt+=(x[j]-i)*(x[j]-i);
    if(tmp>cnt){
      tmp=cnt;
      p=i;
    }
  }

  cout<<tmp<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    int n, m;
    cin >> n >> m;
    vec h(n);
    rep(i, n) cin >> h[i];
    vec g[100010];
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int res = 0;

    rep(i, n) {
        bool f = true;
        for (auto&& v : g[i]) {
            if (h[i] <= h[v]) {
                f = false;
            }
        }
        if (f) res++;
    }

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

Measured memory_bytes: 8800
s = str(input())
k = int(input())

def func(s, k):
    ans = 0
    n = len(s)
    s_list = list(s)
    for i in range(n - 1):
        if s_list[i] == s_list[i + 1]:
            ans += 1
            s_list[i + 1] = str(i + 1)
    ans *= k
    if s_list[0] == s_list[n - 1]:
        ans += k - 1
    return ans

ans1 = func(s, k)
s_inv = ''.join(list(reversed(s)))
ans2 = func(s_inv, k)

if len(s) % 2 == 1:
    check = True
    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            pass
        else:
            check = False
            break
    if check:
        ans3 = len(s) * k // 2
    else:
        ans3 = ans1
else:
    ans3 = ans1

print(min(ans1, ans2, ans3))

Measured memory_bytes: 3064
import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
h = LIST()
mh = max(h)
cnt = 0
for i in range(1,mh+1):
    for j in range(n):
        if j == 0:
            flag = cnt_area = 1 if h[j] >= i else 0
        elif flag == 0 and h[j] >= i:
            flag = 1
            cnt_area += 1
        else:
            flag = (h[j] >= i)
    cnt += cnt_area

print(cnt)

Measured memory_bytes: 10080
using System;
class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine()); //トレーニング回数
        long power=1;
        for (int i=1; i <= N; i++)
        {
            power *= i;
            power %=  (long)1e9 + 7;
        }
        Console.WriteLine(power);
    }
}

Measured memory_bytes: 13140
#include <cctype>
#include <functional>
#include <iostream>
#include <string>
#include <cassert>

using namespace std;

struct Node {
    int value = 0;
    Node* left = nullptr;
    Node* right = nullptr;
    Node(int v, Node* l, Node* r)
        : value{v}
        , left{l}
        , right{r}
    {
    }
};

int main()
{
    string a;
    cin >> a;
    string b;
    cin >> b;

    auto parse = [](const string& str) {
        int i = 0;
        auto value = [&i, &str]() {
            assert(str[i] == '[');
            ++i;
            auto begin = i;
            while (isdigit(str[i])) {
                ++i;
            }
            auto end = i - 1;
            assert(str[i] == ']');
            return stoi(str.substr(begin, end - begin + 1));
        };

        function<Node*()> p = [&p, &i, &str, &value]() -> Node* {
            assert(str[i] == '(');
            if (str[i + 1] == ')') {
                i += 2;
                return nullptr;
            }
            ++i;
            auto l = p();
            auto v = value();
            ++i;
            auto r = p();
            ++i;
            return new Node{v, l, r};
        };
        auto ll = p();
        auto vv = value();
        ++i;
        auto rr = p();
        return new Node{vv, ll, rr};
    };

    function<void(Node*)> pp = [&pp](Node* n) {
        if (n) {
            cout << "(";
            pp(n->left);
            cout << ")";
            cout << '[' << n->value << ']';
            cout << "(";
            pp(n->right);
            cout << ")";
        }
    };

    function<Node*(Node*, Node*)> f = [&f](Node* l, Node* r) {
        auto ll = l->left && r->left ? f(l->left, r->left) : nullptr;
        auto rr = l->right && r->right ? f(l->right, r->right) : nullptr;
        return new Node{l->value + r->value, ll, rr};
    };

    auto t1 = parse(a);
    auto t2 = parse(b);
    auto r = f(t1, t2);
    pp(r);
    cout << endl;
}

Measured memory_bytes: 3240
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair<ll, ll>
#define F first
#define S second
const int MOD = 1000000007;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }
//sort(all(x))とするとソートできるよ
// 10^x は pow(10,(x)) 
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)


struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<int> siz; // 素集合のサイズを表す配列(1 で初期化)

    UnionFind(int N) : par(N), siz(N, 1){ //最初は全てが根であるとして初期化 、頂点数N
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        siz[ry] += siz[rx];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }

    int size(int x) { // 素集合のサイズ
        return siz[root(x)];
    }
};

struct Edge {
    int a;
    int b;
};

int main(){
    int N,M;cin >> N >> M;
    vector<Edge> g;
    vector<LL> ans(M);
    rep(i,M){
        int c,d;cin >> c >> d;
        c--;d--;
        g.push_back((Edge){c,d});
    }
    
    UnionFind uni(N);
    
    for(int i = M-1;i >= 0;--i){
        int u = g[i].a;
        int v = g[i].b;
        if(uni.same(u,v)){
            ans[i] = 0;
            continue;
        }
        else{
            LL s = uni.size(u);
            LL t = uni.size(v);
            ans[i] = s*t;
            uni.unite(u,v);
        }
    }

    LL sum = 0;
    rep(i,M){
        sum += ans[i];
        cout << sum << endl;
    }

}



Measured memory_bytes: 3700
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define all(a) (a).begin(), (a).end()
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
const int MOD = 1e9+7;
const ll LINF = 1e18;
const int INF = 1e9;
ll A, B, C, D, E, F, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;

int main()
{
    cin >> N;
    vector<pair<int, int>> dd(N);
    for (int i = 0; i < N; i++) 
    {
        cin >> dd[i].first >> dd[i].second;
        if (dd[i].first == dd[i].second)
        {
            A++;
        }
        else
        {
            A=0;
        }
        if(A == 3)
        {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
        
        

    
    return 0;
}

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

using namespace std;

int main()
{
	int a, b, c, x, y, r = 1000000000, z;
	cin >> a >> b >> c >> x >> y;
	
	for (int i = 0; i <= 2 * max(x, y); i++)
	{
		z = i * c + a * (i >= 2 * x ? 0 : (2 * x - i) / 2 + (2 * x - i) % 2) + b * (i >= 2 * y ? 0 : (2 * y - i) / 2 + (2 * y - i) % 2);
		r = min(r, z);
	}	
	
	cout << r;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fst first
#define snd second
const ll mod = 1000000007;
const ll INF = mod * mod;

int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << max(a*b, c*d) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
void selectionSort(int A[], int N) {
	int minj, sw = 0, tmp, j, k;
	for (int i = 0; i < N - 1; i++)
	{
		minj = i;
		for (j = i; j < N; j++)
		{
			if (A[j] < A[minj]) {
				minj = j;
			}
		}
		tmp = A[i];
		A[i] = A[minj];
		A[minj] = tmp;
		if (i != minj) sw++;
	}

	for (k = 0; k < N; k++)
	{
		if (k > 0) printf(" ");
		printf("%d", A[k]);
	}
	printf("\n%d\n", sw);
}


int main() {
	int N, i, j;
	int A[100];

	scanf("%d", &N);
	for (i = 0; i < N; i++) scanf("%d", &A[i]);

	selectionSort(A, N);

	return 0;
}


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

int main(void)
{
	stack<int> s;
	int n;
	while(cin >> n){
		if(n)
			s.push(n);
		else if(n == 0 && !s.empty()){
			cout << s.top() << endl;
			s.pop();
		}
	}

	return 0;
}

Measured memory_bytes: 3044
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
	return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
	o<<"{";
	for(const T& v:vc) o<<v<<",";
	o<<"}";
	return o;
}
using ll = long long;
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
int dp[100001][3];
int main(){
	int N;
	cin>>N;
	rep(i,N){
		int a[3];
		rep(j,3) cin>>a[j];
		rep(j,3) rep(nj,3) if(j!=nj){
			chmax(dp[i+1][nj],dp[i][j]+a[nj]);
		}
	}
	int ans = 0;
	rep(j,3) chmax(ans,dp[N][j]);
	cout<<ans<<endl;
}

Measured memory_bytes: 1408
N = gets.to_i

cs, ss, fs = [], [], []
(N-1).times do |i|
    cs[i], ss[i], fs[i] = gets.split.map(&:to_i)
end

N.times do |i|
    now = 0
    (i...(N-1)).each do |j|
        if now < ss[j]
            now = ss[j]
        else
            now = ss[j] + ((now - ss[j] - 1)/fs[j] + 1) * fs[j]
        end
        now += cs[j]
    end
    puts now
end

Measured memory_bytes: 1788
n = int(input())
l = list(map(int,input().split()))

num = max(l)+1
rcd = [0 for _ in range(num)] # indexを数列Aと読み替え可能な配列として初期化

for v in l: # 重複する配列を区別するため各要素数をカウントして...
    rcd[v] += 1

unq = []
for w in range(num): # 1個の場合は重複がない要素として'unq'に集約
    if rcd[w] == 1:
        unq.append(w)
#print(unq)

rcd = [0 for _ in range(num)] # 再度初期化
#l = set(l)
for x in l: # 自身以外の約数の有無を確認 ※ここでは重複を考慮しない
    for y in range(2*x, num, x): # ※自身を約数としてカウントしない工夫！
        rcd[y] = 1 # 自身以外の約数がある場合は'1'が代入される
#print(rcd)

ans = 0
for z in unq: # 'unq'の中で...
    if rcd[z] == 0: # 自身以外に約数を持たない要素のみを...
        ans += 1 # カウント
print(ans)


Measured memory_bytes: 42368
class stack:
    def __init__(self):
        self.s=[0 for _ in range(250)]
        self.top=0


    def push(self,x):
        self.s[self.top]=int(x)
        if(self.top< len(self.s)):
            self.top=self.top+1
        else:
            print('over flow')

    def pop(self):
        val=self.s[self.top-1]
        if (self.top > 0):
            self.top=self.top-1
        else:
            print('under flow')
        return val

inputs=input().split()
#print(inputs)
s=stack()
for _ in inputs:
    if _ !='+' and _ != '-' and _ !='*':
        s.push(_)
        #print(s.s)
    elif _ =='+':
        x=s.pop()+s.pop()
        s.push(x)
        #print(s.s)
    elif _ == '-':
        x=-s.pop()+s.pop()
        s.push(x)
        #print(s.s)
    elif _=='*':
        x=s.pop()*s.pop()
        s.push(x)
        #print(s.s)

print(s.pop())










Measured memory_bytes: 5612
#include<bits/stdc++.h>
#define ll long long
#define  vi vector<int>
#define pb push_back
//#define int long long
#define boost ios_base::sync_with_stdio(false);	cin.tie(0);	cout.tie(0)
#define pi pair<int,int>
#define F first
#define S second
using namespace std;

//int mod=(int)(1e9+7);

void solve()
{
 ll n,m;
 cin>>n>>m;
 ll x=0;
 for(int i=0;i<m;i++)
 {
   ll t;cin>>t;
   x+=t;
 }

 cout<<max(-1LL,n-x);

}

signed main()
{ boost;
 //cout<<fixed<<setprecision(14 );
 // int t;cin>>t;
  //for(int i=1;i<=t;i++)
  solve();
 // cout<<"Case #"<<i<<": "<<solve()<<endl;

return 0;
}

Measured memory_bytes: 3596
from sys import stdin
N = int(input())
A = [int(x) for x in stdin.readline().split(' ')]

cnt = 0
for i in range(0, N):
    minj = i
    for j in range(i, N):
        if (A[minj] > A[j]):
            minj = j
    if (minj != i):
        A[minj], A[i] = (A[i], A[minj])
        cnt += 1

print(' '.join(map(str, A)))
print(cnt)



Measured memory_bytes: 5608
N, K = map(int, input().split())
ans = 0
for i in range(1,N+1):
    n = i
    count = 0    
    while n<K:
        n=2*n
        count += 1
    #print(count)
    ans += (1/2)**count
ans = (1/N)*ans
print(ans)
    

Measured memory_bytes: 2940