akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<iterator>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<cstdint>
#include<chrono>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
//typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);

using namespace std;



signed main() {

	int N, M, P;
	cin >> N >> M >> P;
	vector<int>A(M), B(M), C(M);
	rep(i, M)cin >> A[i] >> B[i] >> C[i];

	vector<vector<int>>graph(N), graphrev(N);

	rep(i, M) {
		A[i]--;
		B[i]--;
		C[i] = -(C[i] - P);

		graph[A[i]].push_back(B[i]);
		graphrev[B[i]].push_back(A[i]);
	}

	vector<int>BF(N, intmax);
	BF[0] = 0;

	rep(i, N - 1) {
		rep(j, M) {
			BF[B[j]] = min(BF[B[j]], BF[A[j]] + C[j]);
		}
	}

	stack<int>dfs1;
	vector<int>searched1(N);
	dfs1.push(0);
	while (!dfs1.empty()) {
		int x = dfs1.top();
		dfs1.pop();
		if (searched1[x])continue;
		searched1[x] = 1;
		for (int y : graph[x]) {
			dfs1.push(y);
		}
	}
	stack<int>dfsN;
	vector<int>searchedN(N);
	dfsN.push(N-1);
	while (!dfsN.empty()) {
		int x = dfsN.top();
		dfsN.pop();
		if (searchedN[x])continue;
		searchedN[x] = 1;
		for (int y : graphrev[x]) {
			dfsN.push(y);
		}
	}


	rep(i, M) {
		if (BF[B[i]] > BF[A[i]] + C[i]) {
			if (searched1[B[i]] != 0 && searchedN[B[i]] != 0) {
				cout << -1 << endl;
				return 0;
			}
		}
	}

	int answer = max<int>(-BF[N - 1], 0LL);

	cout << answer << endl;




	return 0;
}

Measured memory_bytes: 768
#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b;
    scanf("%lld%lld",&a,&b);
    b/=2;
    if(a>=b)
       printf("%lld\n",b);
    else
    {
        printf("%lld\n",a+(b-a)/2);
    }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int64_t i=0;i < (int64_t)(n);i++)
#define invrep(i,n) for(int64_t i=n-1;i >= 0;i--)
#define _GLIBCXX_DEBUG
using namespace std;

int main(){
  int64_t x,y,a,b,c;
    cin >> x >> y >> a >> b >> c;
  vector<int64_t> p(a),q(b),r(c);
  rep(i,a){
    cin >> p[i];
  }
  rep(i,b){
    cin >> q[i];
  }
  rep(i,c){
    cin >> r[i];
  }
  sort(p.begin(),p.end());
  reverse(p.begin(),p.end());
  sort(q.begin(),q.end());
  reverse(q.begin(),q.end());
  sort(r.begin(),r.end());
  priority_queue<
      int64_t,       
      vector<int64_t>,
      greater<int64_t>   // 昇順 (デフォルトはstd::less<T>)
    >que;
  rep(i,x){
    que.push(p[i]);
  }
  rep(i,y){
    que.push(q[i]);
  }
  rep(i,c){
    if(que.top() < r[i]){
      que.pop();
      que.push(r[i]);
    }
  }
  int64_t total = 0;
  while(!que.empty()){
    total += que.top();
    que.pop();
  }
  cout << total << endl;
  
  
    
}

Measured memory_bytes: 4724
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
s = sum(A)
K = [0] *(100000 + 1)
for i in A:
  K[i] += 1
for i in range(Q):
  B , C = map(int,input().split())
  s += (C - B) * K[B]
  K[C] += K[B]
  K[B] = 0
  print(s)

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

int N, a, ans, K;

int main()
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> a;
		if (a == K + 1)
			K++;
		else
			ans++;
	}

	cout << (K ? ans : -1) << endl;
}
	

Measured memory_bytes: 384
import sys
sys.setrecursionlimit(100000)

N = int(input())
d = {}
e = [[] for _ in range(N)]
dd = [-1]*N
for _ in range(N-1):
    u, v, w = list(map(int, input().split()))
    e[u-1].append(v-1)
    e[v-1].append(u-1)
    d[(u-1,v-1)]= d[(v-1,u-1)] = w

def dfs(i, _d):
    dd[i] = _d
    for c in e[i]:
        if dd[c]!=-1: continue
        dfs(c, _d+d[(i,c)])

dfs(0,0)
for _dd in dd:
    print(_dd%2)

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

#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

using namespace std;
typedef long long ll; typedef vector<int> VI; typedef pair<int, int> pii;
const int mod = (int)1e9 + 7;


int main()
{
	
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int sx,sy,tx,ty;
	cin >>sx >>sy >>tx >>ty;
	
	int dx=tx-sx, dy=ty-sy;

	rep(i,dx  ) cout <<"R";
	rep(i,dy+1) cout <<"U";
	rep(i,dx+1) cout <<"L";
	rep(i,dy+1) cout <<"D";
	cout <<"R";
	rep(i,dy)   cout <<"U";
	rep(i,dx+1) cout <<"R";
	rep(i,dy+1) cout <<"D";
	rep(i,dx+1) cout <<"L";
	cout << "U";
	return 0;

}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
    int n=0,count=1;
    char s[100001]={};
    scanf("%d %s",&n,s);
    for(int i=0;i<n-1;i++){
        if(s[i]!=s[i+1]) count+=1;
    }
    printf("%d",count);
    return 0;
}


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

int w,h,sum=0,umi[52][52];

int kesi(int a,int b){
  umi[a][b]=0;
  for(int dx=-1;dx<=1;dx++){
    for(int dy=-1;dy<=1;dy++){
      if(umi[a+dx][b+dy]==1){
        kesi(a+dx,b+dy);
      }
    }
  }
  return 0;
}

int main(){
  while(cin >> w >> h&&w&&h){
    r(i,h){
      r(j,w){
        cin >> umi[i][j];
      }
    }
    r(i,h){
      r(j,w){
        if(umi[i][j]==1){
          sum++;
          kesi(i,j);
        }
      }
    }
    cout<<sum<<endl;
    sum=0;
  }
}


Measured memory_bytes: 3216
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[] a = sc.next().toCharArray();
		char[] b= sc.next().toCharArray();
		for(int i = 0; i < 3; i++) {
			if(a[2-i] != b[i]) {
				System.out.println("NO");
				return;
			}
		}
		System.out.println("YES");
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,n,m) for (int i = (n); i <= (m); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

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

    Graph g(n+1);
    rep(i,m) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    vector<int> current, next;
    vector<int> ans(n+1, 0);
    current.push_back(1);
    ans[1] = 1;
    int visited = 1;

    while (!current.empty()) {
        for (auto i: current) {
            for (auto j: g[i]) {
                if (ans[j] == 0) {
                    next.push_back(j);
                    ans[j] = i;
                    visited++;
                }
            }
        }
        current.swap(next);
        next.clear();
    }

    if (visited==n) {
        cout << "Yes" << endl;
        rep2(i,2,n) { cout << ans[i] << endl; }
    } else {
        cout << "No" << endl;
    }
    return 0;
}


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

int main(){
  set<char> s;
  int N;
  cin >> N;
  for(int i=0;i<N;i++){
    char c;
    cin >> c;
    s.insert(c);
  }
  if(s.size()==3){
    cout << "Three" << endl;
  }else{
    cout << "Four" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
S = []; T = []
for x in range(1, int(N**.5)+1):
    if N % x == 0:
        S.append(x)
        if x*x < N:
            T.append(N//x)
T.reverse()
S += T
M = len(S)
U = []

MOD = 10**9 + 7
ans = 0
v = 0
for i in range(M):
    x = S[i]
    v = pow(K, (x+1)//2, MOD)
    for j in range(i):
        y = S[j]
        if x % y == 0:
            v -= U[j]
    U.append(v % MOD)
    ans = (ans + (v * x if x & 1 else v * (x//2))) % MOD
print(ans)

Measured memory_bytes: 3064
//
//  main.cpp
//

#include <algorithm>
#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

using ll = long long;
using ull = unsigned long long;

int main(int argc, char* argv[]) {
    int N, A, B;
    cin >> N >> A >> B;
    cout << min(N * A, B) << endl;
}



Measured memory_bytes: 888
from collections import deque

s = input()
q = int(input())

deq = deque(s)
rev = False

for _ in range(q):
    query = input().split()
    t = query[0]
    if t == "1":
        rev = not rev
        continue
    f = query[1]
    c = query[2]
    if not rev and f == "2" or rev and f == "1":
        deq.append(c)
    else:
        deq.appendleft(c)
if rev:
    deq = reversed(deq)
print("".join(deq))


Measured memory_bytes: 8820
#include <iostream>
#include <string>
#define rep(i, a, b) for(int i = a; i < b; i++)
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  int sum = 0;
  rep(i, 0, c) {
    if(a <= b) {
      sum++;
      b -= a;
    }
  }
  cout << sum << "\n";
}


Measured memory_bytes: 3636
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int lislis[1003000];
int main(){
    while(1){
        int N,M;
        cin>>N>>M;
        if(N==0&&M==0)break;
        int lis[1002]={0};
        for(int i=1;i<=N;i++)cin>>lis[i];
        for(int i=0;i<1003000;i++)lislis[i]=0;
        for(int i=0;i<=N;i++){
            for(int j=0;j<=N;j++)lislis[i*(N+1)+j]=lis[i]+lis[j];
        }
        sort(lislis,lislis+((N+1)*(N+1)));
        lislis[(N+1)*(N+1)]=lislis[(N+1)*(N+1)-1];
        int maxans=0;
        for(int i=0;i<(N+1)*(N+1);i++){
            int l=0,r=(N+1)*(N+1),mid=(l+r)/2;
            for(int j=0;j<30;j++){
                if(lislis[i]+lislis[mid]<=M)l=mid;
                else r=mid;
                mid=(l+r)/2;
            }
            /*
            printf("[%d] [%d][%d][%d]\n",i,l,mid,r);
            */
            if(lislis[i]+lislis[l]<=M)maxans=max(maxans,lislis[i]+lislis[l]);
        }
        /*
        for(int i=0;i<20;i++)printf("[%d]",lis[i]);
        puts("");
        for(int i=0;i<30;i++)printf("[%d]",lislis[i]);
        puts("");
        */
        cout<<maxans<<endl;
    }
    return 0;
}

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


int main()
{
    string a,b;
    cin>>a>>b;
    long long int count =0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]!=b[i])
            count++;
    }
    cout<<count<<endl;


}


Measured memory_bytes: 3860
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 10000000000000000
#define MOD 1000000007
typedef pair<int, int> P;

bool prime(int n) {
	for (int i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int mod_pow(int n, int p, int m) {
	if (p == 0) return 1;
	if (p % 2 == 0) {
		int t = mod_pow(n, p / 2, m);
		return (t * t) % m;
	}
	return n * mod_pow(n, p - 1, m) % m;
}
int extGCD(int a, int b, int& x, int& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int modinv(int a, int m) {
	int b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

int a[200005], ans[200005], cnt[200005], ans2;

signed main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = n; i >= 1; i--) {
		if (cnt[i] % 2 == a[i]) {
			ans[i] = 0;
		}
		else {
			ans[i] = 1;
			ans2++;
			int now = 1;
			while (now* now <= i) {
				if (i % now == 0) {
					cnt[now]++;
					if (now * now != i) {
						cnt[i / now]++;
					}
				}
				now++;
			}
		}
	}
	cout << ans2 << endl;
	rep(i, n) {
		if (ans[i + 1] == 1) {
			cout << i + 1 << " ";
		}
	}
	cout << endl;

	return 0;
}

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

using ll = long long;
using ld  = long double;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
const int INF=1e9+7;
const ll LINF=9223372036854775807;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld EPS = 1e-10; //微調整用（EPSより小さいと0と判定など）

int ii() { int x; if (scanf("%d", &x)==1) return x; else return 0; }
long long il() { long long x; if (scanf("%lld", &x)==1) return x; else return 0; }
string is() { string x; cin >> x; return x; }
char ic() { char x; cin >> x; return x; }
void oi(int x) { printf("%d ", x); }
void ol(long long x) { printf("%lld ", x); }
void od_nosp(double x) { printf("%.15f", x); } // 古い問題用
void od(double x) { printf("%.15f ", x); }
// long doubleで受け取り、fをLfなどに変えて出力すると、変な数値が出る
// それをなんとかするには独自の出力を作らなければならなそう
void os(const string &s) { printf("%s ", s.c_str()); }
void oc(const char &c) { printf("%c ", c); }
#define o_map(v){cerr << #v << endl; for(const auto& xxx: v){cout << xxx.first << " " << xxx.second << "\n";}} //動作未確認
void br() { putchar('\n'); }

// #define gcd __gcd //llは受け取らない C++17~のgcdと違うので注意
// int lcm(int a, int b){return a / gcd(a, b) * b;}
#define begin_end(a) a.begin(),a.end() //sort(begin_end(vec));
#define REP(i,m,n) for(ll i=(ll)(m) ; i < (ll)(n) ; i++ )
#define DREP(i,m,n) for(ll i=(ll)(m) ; i > (ll)(n) ; i-- )
#define rep(i,n) REP(i,0,n)
#define m_p(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define p_b push_back
#define SZ(x) ((int)(x).size) //size()がunsignedなのでエラー避けに


// coutによるpairの出力（空白区切り）
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << " " << p.second << ")";}
// coutによるvectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << " "; //"\t"に変えるとTabで見やすく区切る
  }
  return s;
}
// coutによる多次元vectorの出力（空白区切り）
template<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i] << endl;
  }
  return s;
}

//最大値、最小値の更新。更新したor等しければtrueを返す
template<typename T>
bool chmax(T& a, T b){return (a = max(a, b)) == b;}
template<typename T>
bool chmin(T& a, T b){return (a = min(a, b)) == b;}

//4近傍（上下左右） rep(i, 2) にすると右・下だけに進む
vector<int> dx_4 = {1, 0, -1, 0};
vector<int> dy_4 = {0, 1, 0, -1};

// -------- template end - //


// - library ------------- //



// --------- library end - //


int main(){

  ll n, m, d;
  cin >> n >> m >> d;

  ld ans;
  if (d==0){
    ans = ld(m-1) / n;
  }
  else if (n - d - d <= 0){
    ans = ld(m-1) / n; // d==0 のときと結果は同じ
  }
  else{
    // n-2d >= 1
    ans = ld((n-d-d)*2 + (d+d)) / n * (m-1) / n;
  }

  od_nosp(ans);

}

Measured memory_bytes: 3724
#include <bits/stdc++.h>
using namespace std;
template<typename T> struct Dinitz{
	int n, source, sink;
	vector<vector<T>> adj;
	struct edge {
		int u;
		T flow, cap;
	};
	vector<edge> edges;
	Dinitz(int n, int source, int sink): n(n), source(source), sink(sink), adj(n) {}
	int add_edge(int a, int b, T abcap, T bacap = 0) {
		int result = edges.size();
		adj[a].push_back(edges.size());
		edges.push_back({b, 0, abcap});
		adj[b].push_back(edges.size());
		edges.push_back({a, 0, bacap});
		return result;
	}
	vector<int> mindist, position;
	bool bfs() {
		queue<int> q;
		fill(mindist.begin(), mindist.end(), INT_MAX / 2);
		mindist[source] = 0;
		q.push(source);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (int edid: adj[v]) {
				edge &ed = edges[edid];
				if (ed.flow < ed.cap && mindist[ed.u] > mindist[v] + 1) {
					mindist[ed.u] = mindist[v] + 1;
					q.push(ed.u);
				}
			}
		}
		return mindist[sink] < n;
	}
	T dfs(int v, T maxf) {
		if (v == sink) return maxf;
		for (int &pos = position[v]; pos < (int)adj[v].size(); ++pos) {
			int edid = adj[v][pos];
			edge &ed = edges[edid], &reved = edges[edid ^ 1];
			if (ed.flow < ed.cap && mindist[ed.u] == mindist[v] + 1) {
				T f = dfs(ed.u, min(maxf, ed.cap - ed.flow));
				if (f > 0) {
					ed.flow += f;
					reved.flow -= f;
					return f;
				}
			}
		}
		return 0;
	}
	T maxflow() {
		T result = 0;
		mindist.resize(n);
		position.resize(n);
		while (bfs()) {
			T extra;
			fill(position.begin(), position.end(), 0);
			do {
				extra = dfs(source, numeric_limits<T> :: max());
				result += extra;
			} while (extra > 0);
		}
		return result;
	}
};
struct union_find{
	static const int DEFAULT = 200200;
	vector<int> parent;
	int N, num_comps;
	union_find(int N = DEFAULT) : N(N) {
		clear();
	}
	void clear(){
		num_comps = N;
		parent.assign(N, -1);
	}
	int find(int u){
		return (parent[u] < 0) ? u : parent[u] = find(parent[u]);
	}
	bool is_connected(int u, int v){
		return find(u) == find(v);
	}
	bool join(int u, int v){
		u = find(u);
		v = find(v);
		if (u != v){
			num_comps--;
			if (parent[u] > parent[v])
				swap(u, v);
			parent[u] += parent[v];
			parent[v] = u;
		}
		return u != v;
	}
	int size(int u){
		return -parent[find(u)];
	}
	int comps(){
		return num_comps;
	}
};
const int maxn = 100100;
int a[2][maxn], t[2][maxn], nds;
int main(){
	int n; cin >> n;
	union_find uf(n);
	for(int rot = 0; rot < 2; rot++){
		for(int i = 0; i < n; i++){
			cin >> a[rot][i];
			uf.join(i, a[rot][i]);
		}
		for(int i = 0; i < n; i++) if(i == uf.find(i)) t[rot][i] = nds++;
		for(int i = 0; i < n; i++) t[rot][i] = t[rot][uf.find(i)];
		uf.clear();
	}
	int source = nds++, sink = nds++;
	Dinitz<int> dinic(nds, source, sink);
	int ans = n;
	for(int i = 0; i < n; i++){
		if(a[0][i] == i && a[1][i] == i) ans--;
		else if(a[1][i] == i) dinic.add_edge(source, t[0][i], 1);
		else if(a[0][i] == i) dinic.add_edge(t[1][i], sink, 1);
		else {
			dinic.add_edge(t[1][i], t[0][i], 1);
			if(a[0][i] == a[1][i]){
				dinic.add_edge(t[0][i], t[1][i], 1);
			}
		}
	}
	cout << ans - dinic.maxflow() << endl;
	return 0;
}


Measured memory_bytes: 13484
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
#define MOD 10007
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef vector<llong> V;

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


class UnionFind {
    public:
        //親の番号を格納する。親だった場合は -(その集合のサイズ)
        vector<int> Parent;
    
        //作るときはParentの値を全て-1にする
        //こうすると全てバラバラになる
        UnionFind(int N) {
            Parent = vector<int>(N, -1);
        }
    
        //Aがどのグループに属しているか調べる
        int root(int A) {
            if (Parent[A] < 0) return A;
            //親を探索したらそれを自身の親に書き換える。経路圧縮。
            return Parent[A] = root(Parent[A]);
        }
    
        //自分のいるグループの頂点数を調べる
        int size(int A) {
            return -Parent[root(A)];//親をとってきたい]
        }
    
        //AとBをくっ付ける
        bool unite(int A, int B) {
            //AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
            A = root(A);
            B = root(B);
            if (A == B) {
                //すでにくっついてるからくっ付けない
                return false;
            }
    
            //大きい方(A)に小さいほう(B)をくっ付けたい
            //大小が逆だったらひっくり返しちゃう。
            if (size(A) < size(B)) swap(A, B);
    
            //Aのサイズを更新する
            Parent[A] += Parent[B];
            //Bの親をAに変更する
            Parent[B] = A;
    
            return true;
        }
};
 
int main() {
	llong N, M;
	cin >> N >> M;
    V A(M),B(M);
    REP(i,M){
        cin >> A[i] >> B[i];
        A[i]--;
        B[i]--;
    }

    UnionFind uni(N);

    V ans(M);
    ans[M-1]=N*(N-1)/2;

    FORR(i,M-1,1){
        ans[i-1]=ans[i];
        //根が違う、つまり違うグループだったらつなげる
        if(uni.root(A[i]) != uni.root(B[i])){
            ans[i-1] -= (llong)(uni.size(A[i]) * uni.size(B[i]));
            uni.unite(A[i],B[i]);
        }
    }

    REP(i,M){
        cout << ans[i] << endl;
    }


}


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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

const int N_MAX = pow(10,6);

// factorial(階乗)の計算

ll fac[N_MAX+1] ={};

ll c_fac(int n) {
  if (fac[n]!=0) return fac[n];
  if (n==0) return fac[n]=1;
  return fac[n] = (c_fac(n-1)*n)%MOD;
}

// inverse(逆元)の計算

ll inv(ll a,ll m) {
  ll b = m, x = 1, y = 0;
  while (b!=0) {
    ll d = a/b;
    a -= b*d; swap(a, b);
    x -= y*d; swap(x, y);
  }
  return x>=0 ? x : x+m;
}

// combinataionの計算

ll nck(ll n, ll k) { 
  c_fac(n);
  if (n<k) return 0;
  ll nume = fac[n];
  ll deno = ( inv(fac[n-k],MOD) * inv(fac[k],MOD) ) % MOD;
  return ( nume * deno ) % MOD;
}

int main() {
  int X, Y; cin >> X >> Y;
  if ((X+Y)%3!=0) { cout << 0 << endl; return 0; }
  if (X>Y*2||X*2<Y) { cout << 0 << endl; return 0; }
  int count = (X+Y)/3;
  X -= count; Y -= count;
  ll result = nck(count, X);
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 16768
#include <iostream>
#define f(i,j,k) for(int i=j;i<k;i++)
using namespace std;
int v[100][100];
int V;
int main(){
    int E,s,t,d;
    int inf=2000000000;
    cin>>V>>E;
    f(i,0,V){
        f(j,0,V){
            if(i==j){
                v[i][j]=0;
            }
            else{
                v[i][j]=inf;
            }
        }
    }
    f(i,0,E){
        cin>>s>>t>>d;
        v[s][t]=d;
    }
    f(k,0,V){
       f(i,0,V){
           f(j,0,V){
               if(v[i][k]!=inf&&v[k][j]!=inf){
                   v[i][j]=min(v[i][j],v[i][k]+v[k][j]);
               }
           }
       } 
    }
    f(i,0,V){
        if(v[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }
    
    f(i,0,V){
        f(j,0,V){
            if(j){
                cout<<" ";
            }
            if(v[i][j]>=inf){
                cout<<"INF";
            }
            else{
                cout<<v[i][j];
            }
        }
        cout<<endl;
    }
    
    return 0;
}



Measured memory_bytes: 3160
#include <stdio.h>


int main()
{

	int i;
	int D, N;

	scanf("%d %d", &N,&D);

	if (N % (2 * D + 1) == 0) {
		printf("%d", N / (2 * D + 1));
	}
	else {
		printf("%d", (N / (2 * D + 1) + 1));
	}

	return 0;


}

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

#define MAXN (200010)
#define ll long long

int n, T;
int t[MAXN];

int main(){
	scanf("%d%d", &n, &T);
	for(int i = 1; i <= n; ++ i){
		scanf("%d", t + i);
	}
	ll ans = 0;
	for(int i = 2; i <= n; ++ i){
		ans += std::min(t[i] - t[i - 1], T);
	}
	ans += T;
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main()
{
	long long n,i,k,s1=0;
	string s;
	cin>>s;
	n=s.length();
	for(int i=0;i<n;i++)
	{
		s1=s1+s[i]-'0';
	}
	if(s1%9==0)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
	
}

Measured memory_bytes: 3736
#include <bits/stdc++.h> 
using namespace std;
const long long int INF = INT64_MAX;
const long long int Mod = 1000000007;
using ll = long long int; /*long long int は64bit*/
using vi = vector<int>;using Vi = vector<long long int>;using matrix = vector<vector<ll> >;using Pair = pair<ll,ll>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define rep(i,N) for(long long int i=0;i<N;i++) 
#define rev(i,N) for(long long int i=N-1;i>=0;i--) /*N-1からスタート*/
#define np nullptr
template<class T,class T2>bool chmax(T &former, const T2 &b) { if (former<=b) { former=b; return true; } return false; }
template<class T,class T2>bool chmin(T &former, const T2 &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; } /*sqrt(x)は平方根*/
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) /*降順↓でVをソート*/
#define fill(x,num) memset(x,num,sizeof(x));
template<class T1,class T2>bool p_compare(const pair<T1,T2> fir,const pair<T1,T2> sec){ return fir.second < sec.second; }
bool p_comp(const Pair fir,const Pair sec){return p_compare<ll,ll>(fir,sec);}
template<class T1,class T2>bool pcompare(pair<T1,T2> fir,pair<T1,T2> sec){ return !p_comp(fir,sec); }
bool pcomp(const Pair fir,const Pair sec){return pcompare<ll,ll>(fir,sec);}
/*sort(all(v),p_compare<ll,ll> 又は p_comp)で↑ソート , pcompは↓ソート*/

//////////////////////////^^ *Emile ^^^//////////////////////////////////////////////////////
//Snipet -> Caps Lock

ll a,b;

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>a>>b;
    ll ans = 0;
    if(a>b){
        ans += a;
        a--;
    }else{
        ans += b;
        b--;
    }
    ans += max(a,b);
    cout<<ans<<endl;
    return 0;
}

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

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

using namespace std;

#define debug(x) cout<<(#x)<<"="<<(x)<<", ";
#define debug1(x) debug(x) cout<<'\n';
#define debug2(x1, x2) debug(x1) debug(x2) cout<<'\n';
#define debug3(x1, x2, x3) debug(x1) debug(x2) debug(x3) cout<<'\n';
#define debug4(x1, x2, x3, x4) debug(x1) debug(x2) debug(x3) debug(x4) cout<<'\n';
#define debug5(x1, x2, x3, x4, x5) debug(x1) debug(x2) debug(x3) debug(x4) debug(x5) cout<<'\n';

#define fcout cout<<fixed<<setprecision(15)
#define repp(i,j,k) for(int i=j; i<k; ++i)
#define rep(i,j) repp(i,0,j)
#define rrep(i,j,k) for(int i=j; i>=k; --i)
#define all(x) (x).begin(), (x).end()
#define sort(x) sort(x.begin(), x.end())
#define lb(x,val) lower_bound(x.begin(), x.end(), val)
#define ub(x,val) upper_bound(x.begin(), x.end(), val)
#define pb(x) emplace_back(x);

typedef long long int lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef vector<int> vi;
typedef vector<lli> vl;
typedef tuple<int, int, lli> tiil;

//const lli M=998244353ll;
const lli M=1000000007ll;
const double D=1.0;

int main(){
	fast_io
	int k; cin>>k;
	int e=0,o=0;
	repp(i,1,k+1){
		if(i&1) o++;
		else e++;	
	}
	cout<<(o*e);
	return 0;
}

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

int main(){
	int p[3], j[2];
	int ans = 0;
	for(int i=0; i < 3; i++) cin >> p[i];
	for(int i=0; i < 2; i++) cin >> j[i];
	sort(p, p+3);
	sort(j, j+2);
	cout << p[0] + j[0] - 50 << endl;
}

Measured memory_bytes: 1180
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

fn main() {
    input!{
      n: usize,
      z: i64,
      w: i64,
      aa: [i64; n],
    }
    let mut ans = (aa[n-1] - w).abs();
    if n>=2 {
        ans = max((aa[n-1]-aa[n-2]).abs(), ans);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
using namespace std;
#define inf 0x3f3f3f
typedef long long ll;
const int maxn = 15;
ll x;
int main(){
	cin >> x;
	ll ans = (x / 500)*1000; 
	x %= 500;
	ans += (x/5)*5;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
/* Simplicity and Goodness */

#include <bits/stdc++.h>
using namespace std;
#define scn(n) scanf("%d",&n)
#define lscn(n) scanf("%lld",&n)
#define lpri(n) printf("%lld ",n)
#define pri(n) printf("%d ",(int)n)
#define prin(n) printf("%d\n",(int)n)
#define lprin(n) printf("%lld\n",n)
#define deb(x) cout << #x << ' ' << x << '\n'
#define rep(i,ini,n) for(int i=ini;i<(int)n;i++)
#define per(i,ini) for(int i=ini;i>=0;i--)
#define tc int tt; scn(tt); while(tt --)
#define pb push_back
#define mp make_pair
#define F first
#define S second
using ll = long long;
const int inf = INT_MAX;
const int ninf = INT_MIN;
const int mod = 998244353;
const int N = 1e5+2;

vector <int> v[N];
vector <int> ht(N);

int main()
{
    int n, m;
    scn(n); scn(m);

    rep(i, 1, n+1)
    scn(ht[i]);

    rep(i, 0, m)
    {
    	int a, b;
    	scn(a); scn(b);

    	v[a].pb(b);
    	v[b].pb(a);
    }

    int cnt = 0;

    rep(i, 1, n+1)
    {
    	bool ok = 1;

    	rep(j, 0, v[i].size())
    	if(ht[i] <= ht[v[i][j]])
    	ok = 0;

    	cnt += ok;
    }

    prin(cnt);

    return 0;
}

Measured memory_bytes: 8944
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int n, pos;
vector<int> pre, in, post;

void rec(int l, int r) {
  if ( l >= r ) return;
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(), in.end(), root));
  rec(l, m);
  rec(m + 1, r);
  post.push_back(root);
}

void solve() {
  pos = 0;
  rec(0, pre.size());
  for ( int i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << post[i];
  }
  cout << endl;
}

int main() {
  int k;
  cin >> n;

  for ( int i = 0; i < n; i++ ) {
    cin >> k;
    pre.push_back(k);
  }

  for ( int i = 0; i < n; i++ ) {
    cin >> k;
    in.push_back(k);
  }

  solve();

  return 0;
}


Measured memory_bytes: 3164
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <cmath>
#include <algorithm>
#include <queue>
#include <time.h>

using namespace std;

#define INT_MAX 2147483647
typedef long long ll;
typedef unsigned int UINT;

ll gcd(ll m, ll n);		//最大公倍数
ll lcm(ll m, ll n);		//最小公倍数

int main(void) {

	int ans;

	int s, t;
	cin >> s >> t;
	t = 2 * t + 1;

	ans = s / t;
	if (s%t != 0) ans++;

	cout << ans << endl;

	return 0;

}

// 2番目から3要素だけ抜き出した部分文字列を取得する
//std::string result = s.substr(2, 3);  

#if 1
//最大公倍数
ll gcd(ll m, ll n)
{
	ll temp;
	while (m % n != 0)
	{
		temp = n;
		n = m % n;
		m = temp;
	}
	return n;
}

//最小公倍数
ll lcm(ll m, ll n)
{
	return m * n / gcd(m, n);
}
#endif

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

int main() {
  int N;
  
  vector<int> vec(10001);
  cin >> N;
  for(int i=1;i<=200;++i){
    for(int j=1;j<=200;++j){
      for(int k=1;k<=200;++k){
          int s = pow(i+j,2) + pow(j+k,2) + pow(k+i,2);
        if(s%2 == 0){
          s /= 2;
          if(s <= 10001){
            vec.at(s-1) += 1;
          }
        }
      }
    }
  }

  for(int i=0;i<N;++i){
    cout << vec.at(i) << endl;
  }
  return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
using namespace std;

int main() {
    int n, k;
    int ans = 0;

    cin >> n >> k;

    if (k > 1) {
        ans = n-k;
    } else {
        ans = 0;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define me(a,b) memset(a,b,sizeof(a))
#define INIT() std::ios::sync_with_stdio(false)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>P;
const int MAX_N=200000+5;
const int MAX_M=100000+5;
const int INF=0x7fffffff;
const int inf=1000000000;
const double EPS=1e-6;
const ull base=123;
const ll mod=1e9+7;
const double pi=4*atan(1.0);
char s[MAX_N];
int main()
{
    scanf("%s",s);
    int i;
    for(i=0;i<3;i++)
    {
        if(s[i]=='R')
            s[i]='S';
        else
        {
            s[i]='R';
        }
        
    }
    int ans=0;
    int sum=0;
    if(s[0]=='S')
    {
        if(s[1]=='S')
        {
            if(s[2]=='S')
            {
                cout<<3<<endl;
            }
            else
            {
                cout<<2<<endl;
            }
        }
        else
        {
            cout<<1<<endl;
        } 
    }
    else
    {
        if(s[1]=='S')
        {
            if(s[2]=='S')
            cout<<2<<endl;
            else
            {
                cout<<1<<endl;
            }
        }
        else
        {
            if(s[2]=='S')
            cout<<1<<endl;
            else
            {
                cout<<0<<endl;
            }
            
        }
        
    }
   // system("pause");
    
}

Measured memory_bytes: 3760
#include<bits/stdc++.h>
using namespace std;
typedef int64_t ll;
typedef long double ld;
const ll MOD=1000000007;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define change(a,b) do{ll c=a; a=b; b=c;}while(0)
long long gcd(long long a,long long b){
    ll gcdmax=max(a,b);
    ll gcdmin=min(a,b);
    while(true){
        if(gcdmax%gcdmin==0)break;
        else gcdmax%=gcdmin;
        change(gcdmin,gcdmax);
    }
    return gcdmin;
}
ll powerup(ll N,ll P,ll M){
    if(P==0)return 1;
    else if(P%2==0){
        ll t=powerup(N,P/2,M);
        return t*t%M;
    }
    else return N*powerup(N,P-1,M)%M;
}
int main()
{
  ll A[32]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  ll K;
  cin>>K;
  cout<<A[K-1]<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int maxn = 105 ;
const int inf = 0x3f3f3f3f ;
int n , m ;
char s[25][25] ;
int d[405][405] ;
void up(int i , int j)
{
	int u = (i - 2) * m + j ;
	int now = (i - 1) * m + j ;
	d[u][now] = d[now][u] = 1 ;
}
void down(int i , int j)
{
	int dow = i * m + j ;
	int now = (i - 1) * m + j ;
	d[dow][now] = d[now][dow] = 1 ;
}
void left(int i , int j)
{
	int now = (i - 1) * m + j ;
	int l = (i - 1) * m + j - 1 ;
	d[l][now] = d[now][l] = 1 ;
}
void right(int i , int j)
{
	int now = (i - 1) * m + j ;
	int r = (i - 1) * m + j + 1 ;
	d[r][now] = d[now][r] = 1 ;
}
void budong(int i , int j)
{
	int now = (i - 1) * m + j ;
	d[now][now] = 0 ;
}
void add(int i , int j)
{
	if(s[i][j] == '#')  return ;
	if(s[i - 1][j] == '.')
	   up(i , j) ;	
	if(s[i + 1][j] == '.')
	   down(i , j) ;
	
	if(s[i][j - 1] == '.')
	   left(i , j) ;
	
	if(s[i][j + 1] == '.')
	   right(i , j) ;
	
	budong(i , j) ;
}
void floyd()
{
	int ans = 0 ;
	for(int k = 1 ; k <= 400 ; k ++)
	for(int i = 1 ; i <= 400 ; i ++)
	for(int j = 1 ; j <= 400 ; j ++)	 
		d[i][j] = min(d[i][j] , d[i][k] + d[k][j]) ;
	for(int i = 1 ; i <= 400 ; i ++)
	  for(int j = 1 ; j <= 400 ; j ++)
	    if(d[i][j] != inf)  ans = max(ans , d[i][j]) ;      
	printf("%d\n" , ans) ;
}
int main()
{
	scanf("%d%d" , &n , &m) ;
	for(int i = 1 ; i <= n ; i ++)
	  scanf("%s" , s[i] + 1) ;
	memset(d , inf , sizeof(d)) ;
	for(int i = 1 ; i <= n ; i ++)
	  for(int j = 1 ; j <= m ; j ++)
	    add(i , j) ; 
	floyd() ;
	return 0 ;    
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define mod 1000000007
#define F first
#define S second
#define P pair<long long,long long>
#define all(a) a.begin(),a.end()
#define INF 1000000000000000
#define endl '\n'
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    vector<int> h(n);
    rep(i,n)cin>>h.at(i);
    int ans=0;
    rep(i,n){
        bool can=true;
        for(int j=0; j<i; j++){
            if(h.at(i)<h.at(j))can=false;
        }
        if(can)ans++;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#ifndef LOCAL
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#else
#include <iostream>
#include <iomanip> 
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <memory>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#endif
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

template<typename T> void setmax(T& x, T y) {x = max(x, y);}
template<typename T> void setmin(T& x, T y) {x = min(x, y);}
#define fix(a) fixed << setprecision(a)
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
#define len(V) (int)V.size()
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define endl '\n'


void solve(){
  int n;
  cin >> n;
  vector<double> a(n);
  forn(i,n) {
    cin >> a[i];
  }
  sort(all(a));
  for (int i = 1; i < n; i++){
    a[i] = (a[i-1] + a[i]) / 2;
  }
  cout << fix(5) << a[n-1];
}

int main() {
  ios::sync_with_stdio(false);
  int t = 1;
  // cin >> t;
  forn(i, t){
    solve();
  }
}

/* 

1
322123


n - 1
0 ... (n-1) [res ... res] S - (n-1) ... S


 */

Measured memory_bytes: 256
#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() {
  double n, m, d, ans = 0;
  cin >> n >> m >> d;
  if (d == 0)
    ans = 1 / n;
  else
    ans = 2 * (n - d) / n / n;

  printf("%.20f", ans * (m - 1));
  return 0;
}


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

using ll = long long;
#define int long long
using P = pair<int, int>;

#define LOG(variable) cout << #variable":\t" << (variable) << endl
#define LOGCON(i, container) for(int (i) = 0; (i) < (container).size(); ++(i)) cout << (i) << ":\t" << (container)[(i)] << endl
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(i, r, n) for (int i = (r); i < (n); ++i)
#define REPR(i, n) for(int i = (n); i >= 0; --i) // from n to 0
#define REPRS(i, n, r) for(int i = (n); i >= (r); --i) // from n to r
#define REPOBJ(itr, obj) for(auto itr = (obj).begin(); itr != (obj).end() ; ++itr)
#define REPROBJ(itr, obj) for(auto itr = (obj).rbegin(), e = (obj).rend(); itr != e; ++itr)
#define COUTB(x) cout << (x) << "\n"
#define COUTS(x) cout << (x) << " "
#define PB push_back
#define SORT(obj) sort((obj).begin(), (obj).end())
#define SORTR(obj) sort((obj).begin(), (obj).end(), greater<>())
#define ALL(obj) (obj).begin(), (obj).end()
#define MOD 1000000007
#define PI (acos(-1))
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= MOD; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime MOD
  mint inv() const { return pow(MOD-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
template<typename T = int>
T in() {T a; cin >> a; return a;}
/***** MAIN *****/
signed main() {
  int n = in();
  map<int, int> mp;
  REP(i,n) {
    int tmp; cin >> tmp;
    ++mp[tmp];
  }
  cout << mp.size();
  cout << "\n";
  return 0;
}
/***** MAIN *****/


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

using namespace std;


int main(){
	long long int N;
	cin >> N;
	map<pair<long long int, long long int>, long long int>count;

	vector<pair<long long int, pair<long long int, long long int>>>A, B;

	for( size_t i = 0; i < N; i++ ){
		long long int a, b;
		cin >> a >> b;
		auto ab = make_pair(a, b);

		A.push_back(make_pair(a + b, ab));
		B.push_back(make_pair(b + a, ab));

		count[ab]++;
	}

	sort(A.rbegin(), A.rend());
	sort(B.rbegin(), B.rend());


	bool turn = true;
	auto ap = A.begin(), bp = B.begin();

	long long int Asum = 0, Bsum = 0;

	while( ap < A.end() && bp < B.end() ){
		if( turn ){
			if( count[( *ap ).second] == 0 ){
				ap++;
				continue;
			}

			count[( *ap ).second]--;
			Asum += ( *ap ).second.first;
			ap++;

		} else{
			if( count[( *bp ).second] == 0 ){
				bp++;
				continue;
			}

			count[( *bp ).second]--;
			Bsum += ( *bp ).second.second;
			bp++;
		}
		turn = !turn;
	}
	cout << Asum - Bsum << endl;
}


Measured memory_bytes: 11872
N = int(input())
L = [[int(l) for l in input().split()] for _ in range(N)]

L1 = [0]*N
L2 = [0]*N
for i in range(N):
    L1[i] = L[i][0]+L[i][1]
    L2[i] = L[i][0]-L[i][1]

L1.sort()
L2.sort()
print(max(L1[-1]-L1[0], L2[-1]-L2[0]))

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

int main()
{  
    double a,b,c,d;
	cin>>a>>b>>c>>d;

	double e=(a-c)*(a-c)+(b-d)*(b-d);
	e=sqrt(e);
	
	//cout<<e<<endl;
	printf("%.5f",e);
	cout<<endl;
    
	return 0;
}


Measured memory_bytes: 3212
// よくあるやつ 2500まで調べる必要はなく、Kまででいい
package main

import "fmt"

var k, s int

func main() {
	fmt.Scan(&k, &s)
	ans := 0
	for x := 0; x <= k; x++ {
		for y := 0; y <= k; y++ {
			z := s - (x + y)
			if z < 0 || k < z {
				continue
			}
			ans += 1
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define N 101
#define M 100001
int a[N], f[M] = {-1}, n, m;
int search(int num) {
    if (f[num]) return f[num];
    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (a[i] <= num && search(num - a[i]) == -1) flag = true;
    return f[num] = (flag ? 1 : -1);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    puts(search(m) == 1 ? "First" : "Second");
    return 0;
}

Measured memory_bytes: 5376
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>
#define repd(i,a,b) for (int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define inf 2000000007
#define mp make_pair
#define pb push_back
typedef long long ll;
using namespace std;
template <typename T>
inline void output(T a, int p) {
    if(p) cout << fixed << setprecision(p)  << a << "\n";
    else cout << a << "\n";
}
// end of template



// Minimum Cost Flow
struct node {int cost, pos;};
struct edge {int to, cap, cost, rev;};
bool operator < (const node &a, const node &b){
    return a.cost > b.cost;
}

class MinCostFlow {
    
public:
    int V; // ??????????????°
    vector<vector<edge>> G;
    vector<int> h, dist, preV, preE; // ??????????????£?????????????????¢?????´?????????????????´?????????
    
    MinCostFlow(int V) : V(V), G(V), h(V), dist(V), preV(V), preE(V) {}
    
    void add_edge(int from, int to, int cap, int cost) {
        G[from].pb({to, cap, cost, (int)G[to].size()});
        G[to].pb({from, 0, -cost, (int)G[from].size() - 1});
    }
    
    int calc(int s, int t, int f){
        int ret = 0;
        
        h.assign(V, 0);
        while(f > 0) {
            dist.assign(V, inf);
            priority_queue<node> pq;
            pq.push({0, s});
            dist[s] = 0;
            while(!pq.empty()){
                node p = pq.top(); // cost, pos
                pq.pop();
                int d = p.cost;
                int v = p.pos;
                if(dist[v] < d) continue;
                rep(i, G[v].size()){
                    edge &e = G[v][i];
                    if(e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        preV[e.to] = v;
                        preE[e.to] = i;
                        pq.push({dist[e.to], e.to});
                    }
                }
            }
            if(dist[t] == inf) return -1;
            rep(v, V) h[v] += dist[v];
            
            int d = f;
            
            for(int v = t; v != s; v = preV[v]){
                d = min(d, G[preV[v]][preE[v]].cap);
            }
            f -= d;
            ret += d * h[t];
            for(int v = t; v != s; v = preV[v]){
                edge &e = G[preV[v]][preE[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return ret;
    }
    
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    // source code
    int V, E, F;
    cin >> V >> E >> F;
    MinCostFlow mcf(V);
    rep(i, E){
        int u, v, c, d;
        cin >> u >> v >> c >> d;
        mcf.add_edge(u, v, c, d);
    }
    
    output(mcf.calc(0, V - 1, F), 0);
    
    
    return 0;
}

Measured memory_bytes: 3144