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

int main() {
  int n, m;
  cin >> n;
  vector<pair<int, int>> a(n - 1);
  for (auto& e : a) {
    cin >> e.first >> e.second;
    e.first--, e.second--;
  }
  cin >> m;
  vector<pair<int, int>> c(m);
  for (auto& e : c) {
    cin >> e.first >> e.second;
    e.first--, e.second--;
  }

  vector<vector<int>> d(n, vector<int>(n, 1e9)), ij2a(n, vector<int>(n)), next(n, vector<int>(n));
  for (int i = 0; i < n; i++) d[i][i] = 0;
  for (int i = 0; i < n - 1; i++) {
    d[a[i].first][a[i].second] = d[a[i].second][a[i].first] = 1;
    ij2a[a[i].first][a[i].second] = ij2a[a[i].second][a[i].first] = i;
  }
  for (auto& e : next) iota(e.begin(), e.end(), 0);
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (d[i][k] + d[k][j] < d[i][j]) {
          d[i][j] = d[i][k] + d[k][j];
          next[i][j] = next[i][k];
        }
      }
    }
  }

  vector<int> b(n - 1);
  for (int i = 0; i < c.size(); i++) {
    int p = c[i].first;
    while (p != c[i].second) {
      int p2 = next[p][c[i].second];
      b[ij2a[p][p2]] |= 1 << i;
      p = p2;
    }
  }
  // for (auto e : b) cerr << bitset<20>(e) << endl;

  vector<vector<ll>> dp(n, vector<ll>(1 << m));
  dp[0][0] = 1;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < (1 << m); j++) {
      dp[i + 1][j] += dp[i][j];
      dp[i + 1][j | b[i]] += dp[i][j];
    }
  }
  cout << dp[n - 1][(1 << m) - 1] << endl;
}


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

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            long N = long.Parse(Console.ReadLine());

            const int transportNum = 5;
            var limitNumList = new List<long>();
            for (int i = 0; i < transportNum; i++)
            {
                limitNumList.Add(long.Parse(Console.ReadLine()));
            }
            long bottleneckNum = limitNumList.Min();
            long bottleneckTime = N % bottleneckNum == 0 ? N / bottleneckNum : N / bottleneckNum + 1;
            Console.WriteLine(bottleneckTime + transportNum - 1);
        }
    }
}


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

using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

#define REP(i, l, n) for(int i=(l), i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(),(x).end()
#define pb push_back

ll gcd(ll a,ll b){return b ? gcd(b,a%b) : a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

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

char alpha[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};

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

int main(){
    ll n, k; cin >> n >> k;
    vector<int> plis(n);
    vector<ll> clis(n);
    ll ans = -1 * 1e15;
    REP(i, 0, n){cin >> plis[i]; plis[i]--;}
    REP(i, 0, n){cin >> clis[i];}
    REP(i, 0, n){
        ll key = i, count = 0;
        ll sum = 0, ck = k;
        while(1){
            key = plis[key];
            sum += clis[key];
            count++;
            if(key == i){
                break;
            }
        }
        if(sum > 0){
            sum *= max((ck / count)-1, 0LL);
            ck -= max((ck / count)-1, 0LL) * count;
            key = i;
            ans = max(ans, sum);
            REP(l, 0, ck){
                key = plis[key];
                sum += clis[key];
                ans = max(ans, sum);
            }
        }else{
            key = i;
            sum = 0;
            REP(l, 0, min(ck, n)){
                key = plis[key];
                sum += clis[key];
                ans = max(ans, sum);
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3692
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;
using ll = long long;

int main() {
    int k, n;
    int ans = 0;
    cin >> k >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
    }
    
    vector<int> d(n);
    for (int i = 1; i < n; i++) {
        d.at(i) = a.at(i) - a.at(i - 1);
    }
    d.at(0) = (k - a.at(n - 1)) + a.at(0);
    sort(d.begin(), d.end());
    for (int i = 0; i < n - 1; i++) {
        ans += d.at(i);
    }
    cout << ans << endl;
}

Measured memory_bytes: 4840
X, N = map(int, input().split())
lst = [0] * 102
p = list(map(int, input().split()))
for i in p:
    lst[i] += 1
if lst[X] == 0:
    print(X)
else:
    up = 1
    dn = 1
    while lst[X+up] == 1:
        up += 1
    while lst[X-dn] == 1:
        dn += 1
    if up >= dn:
        print(X-dn)
    else:
        print(X+up)

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

int main(){
	int a,b,c;
  	long count=0;
  	cin >> a >> b >> c;
  	if(a%2 != 0 || b%2 != 0 || c%2 != 0) {
      	cout << 0 << endl;
    	return 0; 
    }
  	if(a == b && b == c) {
      	cout << -1 << endl;
      	return 0;
    }
  	int s,t,u;
  	while(a%2 == 0 && b%2 == 0 && c%2 == 0) {
      	s = b/2+c/2;
      	t = a/2+c/2;
      	u = a/2+b/2;
      	a = s;b=t; c = u;
      	count++;
    }
  	cout << count <<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <stack>
#include <limits>
#include <array>
#include <unordered_map>
#include <unordered_set>
//#include <tuple>

using namespace std;

//constexpr long long mod = static_cast<long long>(1e9 + 7);


int main() {
    std::string str;
    std::cin >> str;
    int x, y;
    std::cin >> x >> y;
    std::vector<std::vector<bool>> dpx(str.size() + 1, std::vector<bool>(2 * str.size() + 1, false));
    std::vector<std::vector<bool>> dpy(str.size() + 1, std::vector<bool>(2 * str.size() + 1, false));
    int offset = str.size();
    auto itr = std::find(begin(str), end(str), 'T');
    if (itr == end(str)) {
        std::cout << (x == str.size() ? "Yes" : "No") << std::endl;
    } else {
        int turn = 0;

        dpx[itr - begin(str)][itr - begin(str) + offset] = true;
        dpy[itr - begin(str)][offset] = true;

        while (itr != end(str)) {
            ++itr;
            auto next = find(itr, end(str), 'T');
            if (turn == 0) {
                for (int i = 0; i < 2 * str.size() + 1; ++i)
                    dpx[next - begin(str)][i] = dpx[itr - begin(str) - 1][i];

                for (int i = 0; i < 2 * str.size() + 1; ++i) {
                    if (dpy[itr - begin(str) - 1][i]) {
                        dpy[next - begin(str)][i + next - itr] = true;
                        dpy[next - begin(str)][i - (next - itr)] = true;
                    }
                }
            } else {
                for(int i = 0; i < 2 * str.size() + 1; ++i)
                    dpy[next - begin(str)][i] = dpy[itr - begin(str) - 1][i];

                for(int i = 0; i < 2 * str.size() + 1; ++i) {
                    if (dpx[itr - begin(str) - 1][i]) {
                        dpx[next - begin(str)][i + next - itr] = true;
                        dpx[next - begin(str)][i - (next - itr)] = true;
                    }
                }
            }
            turn = (turn + 1) % 2;
            itr = next;
        }
        std::cout << (dpx.back()[x + offset] && dpy.back()[y + offset] ? "Yes" : "No") << std::endl;
    }

    return 0;
}


Measured memory_bytes: 32384
#include <iostream>
#include <vector>
#define rep(i, n)for(int i=0; i<n; i++)
using ll = long long int;
using namespace std;

int main(){
    int n, x, t;
    cin >> n >> x >> t;

    int ans = 0;
    if(n%x==0) ans = n/x*t;
    else ans = n/x*t+t;    

    cout << ans << endl;

    return 0;
}


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

int N, X;
int x[100010];

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

int main()
{
	cin >> N >> X;
	for (int i = 0; i < N; ++i)
		cin >> x[i];
	int D = abs(x[0] - X);
	for (int i = 1; i < N; ++i) {
		D = gcd(D, abs(x[i] - X));
	}
	cout << D << endl;
	return 0;
}

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

int main() {
  
  int n;
  cin >> n;
  
  int goukei = 0;
  vector<int> a(n);
  for ( int i = 0; i < n; i++){
    cin >> a[i];
    goukei += a[i];
  }
  
  if ( goukei % 10 != 0 ){
    cout << goukei << endl;
    return 0;
  }
  
  sort(a.begin(),a.end());
  
  for ( int i = 0; i < n; i++){
    if ( a[i] % 10 != 0 ){
      cout << goukei - a[i] << endl;
      return 0;
    }
  }
  
  cout << 0 << endl;
  
}

Measured memory_bytes: 3660
N, D = map(int, input().split())
items = []
for i in range(N):
    items.append(tuple(map(int, input().split())))
ans = 0
from itertools import combinations

for x in combinations([i for i in range(N)] , 2):
    tmp = 0
    for k in range(D):
        tmp += (items[x[0]][k] - items[x[1]][k]) ** 2
    if pow(tmp, 0.5) % 1 == 0:
        ans += 1
print(ans)


Measured memory_bytes: 3064
#include<iostream>
#include<sstream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cassert>
#define rep(i,n) for(int i=0;i<n;i++)
#define fr(i,c) for(__typeof (c.begin()) i=c.begin(); i!=c.end(); i++)
#define all(c) (c).begin(), (c).end()
#define mp make_pair
#define pb push_back
using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef long long ll;

struct S{
  char s[11];
  int x;
  bool operator<(const S &r)const{
    if(x!=r.x)return x>r.x;
    return strcmp(s,r.s)<0;
  }
};
S chara[100000];
int n,m,k,l;

vector<S> like, dislike;
ll calc(int m){
  ll need=0;
  if(dislike.size()<k-m+1)return 0;
  rep(i,m){
    //cerr<<"hoge: "<<dislike[k-m].x-like[i].x<<endl;
    need+=max(0,dislike[k-m].x-like[i].x+
    (strcmp(dislike[k-m].s,like[i].s)<0));
  }
  //cerr<<"m: "<<m<<" need: "<<need<<endl;
  return need;
}

int main(){
  while(scanf("%d%d%d%d",&n,&m,&k,&l),n){
    set<string> names;
    rep(i,n)scanf("%s%d",chara[i].s,&chara[i].x);
    rep(i,m){
      char in[11]; scanf("%s",in);
      names.insert(string(in));
    }
    like.clear(); dislike.clear();
    rep(i,n){
      if(names.count(chara[i].s))like.pb(chara[i]);
      else dislike.pb(chara[i]);
    }
    sort(all(like)); sort(all(dislike));
    //rep(i,dislike.size())cerr<<dislike[i].s<<" "<<dislike[i].x<<endl;
    
    int lo=0, hi=min(m,k)+1, mid;
    while(lo+1<hi){
      mid=(lo+hi)/2;
      if(calc(mid)<=l)lo=mid; else hi=mid;
    }
    printf("%d\n",lo);
  }
  return 0;
}

Measured memory_bytes: 9816
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>	// require sort next_permutation count __gcd reverse etc.
#include <cstdlib>	// require abs exit atof atoi 
#include <cstdio>		// require scanf printf
#include <functional>
#include <numeric>	// require accumulate
#include <cmath>		// require fabs
#include <climits>
#include <limits>
#include <cfloat>
#include <iomanip>	// require setw
#include <sstream>	// require stringstream 
#include <cstring>	// require memset
#include <cctype>		// require tolower, toupper
#include <fstream>	// require freopen
#include <ctime>		// require srand
#define rep(i,n) for(int i=0;i<(n);i++)
#define ALL(A) A.begin(), A.end()

using namespace std;

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

int main()
{
//	cut here before submit 
//	freopen ("testcase.RPN1", "r", stdin );
	string str = "";
	getline (cin, str );
	stack<ll> st;
	stringstream ss(str );
	string s;
	while (ss >> s ){
		if (isdigit (s[0] ) ){
			st.push (atoll (s.c_str() ) );
		}else{
			ll a = st.top(); st.pop();
			ll b = st.top(); st.pop();
			ll c = 0LL;
			char ope = s[0];
			switch (ope ){
				case '+': c = a + b; break;
				case '-': c = b - a; break;
				case '*': c = a * b; break;
			} // end switch
			st.push (c );
		} // end if
	} // end while

	if (!st.empty() ){
		cout << st.top() << endl;
	} // end if

	return 0;
}

Measured memory_bytes: 1216
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
int h,m,s;
string conv(int t){
	char str[100];
	sprintf(str,"%02d:%02d:%02d",t/60/60,(t/60)%60,t%60);
	return string(str);
}
void solve(){
	int time=(h*60+m)*60+s;
	int remain=60*60*2-time;
	cout<<conv(remain)<<endl;
	cout<<conv(remain*3)<<endl;

}
int main(){
	while(cin>>h>>m>>s){
		if(h==-1)break;
		solve();
	}

	return 0;
}

Measured memory_bytes: 0
using namespace std;
#include<string.h>
#include <sstream>
typedef long long int ll;
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <unordered_map>
#include <map>
//#define N 4
#include <stack>
#include <unordered_set>
#include <math.h>
#include <cstring>
#include <bitset>
#include <set>
#include <sstream>
#include <queue>
#define PI 3.14159265358979
#define mp make_pair
#define inf 1e9
//#define M 1000000007
#define M 8888888888
//#define N 1000000009

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int k;
	string s;
	cin >> k >> s;

	if (s.length() <= k) {
		cout << s << endl;
	} else {
		string res = "";
		for (int i = 0; i < k; i++) {
			res.push_back(s[i]);
		}
		cout << res << "..." << endl;
	}

}



Measured memory_bytes: 3644
#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;

ll rep_square(ll a, ll b) {
    // return a^b
    ll ans = 1;
    ll base = a;
    while (b != 0) {
        if (b & 1) {
            ans *= base;
            ans %= mod;
        }
        base = (base * base) % mod;
        b >>= 1;
    }
    return ans;
}

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

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

int main() {
source:
    ll n;
    cin >> n;
    ll a[n], b[n];
    ll zero_zero = 0;
    map<pair<ll, ll>, ll> map0, map1;

    rep(i, n) {
        cin >> a[i] >> b[i];

        if (a[i] == 0 && b[i] == 0) {
            zero_zero++;
            continue;
        } else if (a[i] == 0) {
            b[i] = 1;
            map1[make_pair(1, 0)]++;
            continue;
        } else if (b[i] == 0) {
            a[i] = 1;
            map0[make_pair(1, 0)]++;
            continue;
        }

        if (a[i] > 0 && b[i] > 0) {
            ll g = gcd(a[i], b[i]);
            a[i] /= g;
            b[i] /= g;
            map0[make_pair(a[i], b[i])]++;
        } else if (a[i] < 0 && b[i] < 0) {
            a[i] = -a[i];
            b[i] = -b[i];
            ll g = gcd(a[i], b[i]);
            a[i] /= g;
            b[i] /= g;
            map0[make_pair(a[i], b[i])]++;
        } else if (a[i] > 0 && b[i] < 0) {
            b[i] = -b[i];
            swap(a[i], b[i]);
            ll g = gcd(a[i], b[i]);
            a[i] /= g;
            b[i] /= g;
            map1[make_pair(a[i], b[i])]++;
        } else if (a[i] < 0 && b[i] > 0) {
            a[i] = -a[i];
            swap(a[i], b[i]);
            ll g = gcd(a[i], b[i]);
            a[i] /= g;
            b[i] /= g;
            map1[make_pair(a[i], b[i])]++;
        }
    }

    ll num = n - zero_zero;

    map<pair<ll, ll>, pair<ll, ll>> map_all;
    for (auto iter = map0.begin(); iter != map0.end(); iter++) {
        map_all[iter->first].first += iter->second;
    }
    for (auto iter = map1.begin(); iter != map1.end(); iter++) {
        map_all[iter->first].second += iter->second;
    }

    ll ans = 1;
    for (auto iter = map_all.begin(); iter != map_all.end(); iter++) {
        auto x = iter->first;
        auto y = iter->second;

        ll num0 = y.first, num1 = y.second;

        ll temp = (rep_square(2, num0) + rep_square(2, num1) - 1) % mod;

        ans = (ans * temp) % mod;
    }

    ans--;
    ans += zero_zero;
    ans = (ans + mod) % mod;

    cout << ans << endl;
}



Measured memory_bytes: 34692
#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[2005][2005];
vector<pair<long long,int> > v;
long long solve(int l,int r)  
//现在区间从l到r 还没有放数
{
	if (r<l) 	return 0;
	if (dp[l][r]!=-1) 	return dp[l][r];
	int i=l+n-r-1; //i 为 现在该放第 i 个数。那么它可能放在l的位置 或者 放在r的位置
	long long temp1,temp2;
	temp1 = v[i].first * abs(v[i].second-l)+ solve(l+1,r); 	//第i个数字放在l的位置
	temp2 = v[i].first * abs(v[i].second-r)+ solve(l,r-1);	//第i个数字放在r的位置
	return dp[l][r]= max(temp1,temp2);
}
int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		v.push_back({a,i});
	}
	//
	sort(v.rbegin(),v.rend());  //倒序排序
	memset(dp,-1,sizeof(dp));
	//这里有个贪心的思路，最大的数肯定尽量往两边放。
	printf("%lld",solve(0,n-1)); 
	
	
	return 0;
}


Measured memory_bytes: 35384
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;

pair<string, vector<string> > parse(string s)
{
	for(int i=0; i<s.size(); i++)
		if(!isalpha(s[i])) s[i] = ' ';
	
	s.erase(s.end() - 1);

	stringstream ss(s);
	string n;
 	ss >> n;

	string a;
	vector<string> res;
	while(ss >> a) { res.push_back(a); }
	
	return make_pair(n, res); 
}

bool vis[100];
set<string> ans;
void dfs(int u, map<string, int>& dic, vector<vector<string> >& graph)
{
	vis[u] = true;

	for(int i=0; i<graph[u].size(); i++) {
		string n = graph[u][i];
		if(dic.count(n)) {
			int v = dic[n];
			if(vis[v]) continue;
			dfs(v, dic, graph);
		}
		else ans.insert(n);
	}
}

int main()
{
	int N;
	while(cin >> N, N) {
		map<string, int> dic;
		vector<vector<string> > graph(N);

		for(int i=0; i<N; i++) {
			string s;
			cin >> s;

			pair<string, vector<string> > p = parse(s);
			string n = p.first;
			dic[n] = i;

			for(int j=0; j<p.second.size(); j++)
				graph[i].push_back(p.second[j]);
		}	

		memset(vis, 0, sizeof(vis));
		ans.clear();
		dfs(0, dic, graph);

		cout << ans.size() << endl;
	}
	
}

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

int main(){
  int N;
  cin >> N;
  vector<int> L(N), F(N), B(N);
  for(int i = 0; i < N; ++i) cin >> L[i];
  int t = 1;
  for(int i = 0; i < N; ++i){
    if(i > 0 and L[i] != L[i-1]) ++t;
    else t = 1;
    B[i] = t;
  }
  t = 1;
  for(int i = N-1; i >= 0; --i){
    if(i < N-1 and L[i] != L[i+1]) ++t;
    else t = 1;
    F[i] = t;
  }
  // cerr << "B : "; for(auto e : B) cerr << e << " "; cerr << endl;
  // cerr << "F : "; for(auto e : F) cerr << e << " "; cerr << endl;
  int ans = max(*max_element(B.begin(), B.end()),*max_element(F.begin(), F.end()));
  for(int i = 1; i < N; ++i){
    if(L[i] != L[i-1]) continue;
    int t = B[i-1]+F[i], s = 0;
    if(i-1-B[i-1] >= 0) s = max(s,B[i-1-B[i-1]]);
    if(i+F[i] < N) s = max(s,F[i+F[i]]);
    ans = max(ans,s+t);
  }
  cout << ans << endl;
}



Measured memory_bytes: 3864
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}
ll dist[200010] = {};
vector<ll> tree[200010];
void dfs(ll cur, ll par, ll d){
    dist[cur] = d;
    for(auto &e: tree[cur]){
        if(e == par) continue;
        dfs(e, cur, d+1);

    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    if(N == 1){
        print("First");
        return 0;
    }
    
    ll a[200010], b[200010];
    rep(i,0,N-1){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        tree[a[i]].push_back(b[i]);
        tree[b[i]].push_back(a[i]);
    }
    dfs(0, -1, 0);
    ll max_val = 0, max_pos = -1;
    rep(i,0,N){
        if(max_val < dist[i]){
            max_val = dist[i];
            max_pos = i;
        }
    }
    rep(i,0,N) dist[i] = 0;
    dfs(max_pos, -1, 0);
    max_val = 0;
    rep(i,0,N) max_val = max(max_val, dist[i]);
    if(max_val % 3 == 1){
        print("Second");
    }else{
        print("First");
    }



}

Measured memory_bytes: 25216
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int INF=1e9;
const double eps=1e-9;
const double pi=acos(-1.0);
const int maxn=2e5+10;
typedef long long ll;
struct node{
	int x,y;
};
struct node point[maxn];
int dp[maxn];
bool cmp(node t1,node t2){
	return t1.x<t2.x;
}
inline ll read(){
	ll x=0,flag=1;
	char ch=getchar();
	while(!isdigit(ch) && ch!='-')ch=getchar();
	if(ch=='-')flag=-1,ch=getchar();
	while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x*flag;
}
int main(){
	int i,j,k,m,n;
	int cnt=0;
	int x1,x2,y1,y2;
	x1=read();y1=read();x2=read();y2=read();
	if(x1>x2){swap(x1,x2);swap(y1,y2);}
	n=read();
	for(i=1;i<=n;i++){
		int x,y;
		x=read();y=read();
		if(x>max(x1,x2) || x<min(x1,x2))continue;
		if(y>max(y1,y2) || y<min(y1,y2))continue;
		point[++cnt].x=x;
		point[cnt].y=y;
	}
	if(x1==x2 && y1==y2){
		printf("%.15lf\n",0.0);
		return 0;
	}
	else if(x1==x2){
		int flag=0;
		for(i=1;i<=n;i++)
			if(point[i].x==x1 && point[i].y>min(y1,y2) && point[i].y<max(y1,y2)){
				flag=1;
				break;
			}
		if(flag)printf("%.15lf\n",1ll*abs(y1-y2)*100+10.0*pi-20.0);
		else printf("%.15lf\n",1ll*abs(y1-y2)*100.0);
		return 0;
	}
	else if(y1==y2){
		int flag=0;
		for(i=1;i<=n;i++)
			if(point[i].y==y1 && point[i].x>min(x1,x2) && point[i].x<max(x1,x2)){
				flag=1;
				break;
			}
		if(flag)printf("%.15lf\n",1ll*abs(x1-x2)*100.0+10.0*pi-20.0);
		else printf("%.15lf\n",1ll*abs(x1-x2)*100.0);
		return 0;
	}
	int len;
	sort(point+1,point+cnt+1,cmp);
	if((x1<x2 && y1<y2) || (x1>x2 && y1>y2)){
		dp[1]=point[1].y;
		len=1;
		if(cnt==0)len=0;
		int s,t;
		for(i=2;i<=cnt;i++){
			s=1;t=len;
			while(s<=t){
				m=(s+t)/2;
				if(point[i].y>dp[m])s=m+1;
				else t=m-1;
	        }
			dp[s]=point[i].y;
			if(s>len)len++;
		}
	}
	else{
		dp[1]=point[1].y;
		len=1;
		if(cnt==0)len=0;
		int s,t;
		for(i=2;i<=cnt;i++){
			s=1;t=len;
			while(s<=t){
				m=(s+t)/2;
				if(point[i].y<dp[m])s=m+1;
				else t=m-1;
	        }
			dp[s]=point[i].y;
			if(s>len)len++;
		}
	}
	double ans=1ll*abs(x2-x1)*100.0+1ll*abs(y2-y1)*100.0-1.0*(20-5*pi)*len;
	if(abs(x1-x2)==len-1)ans+=5.0*pi;
	else if(abs(y1-y2)==len-1)ans+=5.0*pi;
	printf("%.15lf\n",ans);
    return 0;
}


Measured memory_bytes: 2560
import java.io.*;
import java.math.*;
import java.util.*;
public class Main { 
 
	public static void main(String[] args) { 
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int N = I.nextInt();
		StringBuilder ans = new StringBuilder();
		int[] a = new int[N+1];
		int[] cnts = new int[N+1]; //How many balls total in boxes with numbers that are 
		//multiples of i
		int len = 0;
		for (int i = 1; i <= N; i++) a[i] = I.nextInt();
		for (int i = N; i >= 1; i--) {
			//for (int chk = 1; chk <= N; chk++) O.p(cnts[chk]+" ");
			//O.p("\n");
			int tot = 0;
			for (int next = i+i; next <= N; next+=i) {
				tot+=cnts[next];
			}
			if (tot%2!=a[i]) {
				cnts[i]++;
			}
		}
		for (int i = 1; i <= N; i++) {
			if (cnts[i]>0) {
				len++;
				ans.append(i+" ");
			} 
		}
		O.pln(len);
		O.pln(ans);
	}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());};
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
	}
}


Measured memory_bytes: 45736
#include<bits/stdc++.h>
using namespace std;
const int maxn=110000;
int n;
int but[maxn][2];
int main()
{
	scanf("%d",&n);
	int num;
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&num);
		but[num][i%2]++;
	}
	int ma=0,mb=0,ans=0;
	for(int i=1;i<=100000;i++)
	{
		ans=max(ans,but[i][1]+ma);
		ans=max(ans,but[i][0]+mb);
		ma=max(ma,but[i][0]);
		mb=max(mb,but[i][1]);
	}
	printf("%d\n",n-ans);
	return 0;
}

Measured memory_bytes: 1024
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

N = int(input())
*A, = map(int, input().split())
dinic = Dinic(N+2)

INF = 10**18

su = 0
for x in range(1, N+1):
    a = A[x-1]
    if a > 0:
        su += a
        dinic.add_edge(0, x+1, a)
    elif a < 0:
        dinic.add_edge(x+1, 1, -a)

for x in range(1, N+1):
    for y in range(x+x, N+1, x):
        dinic.add_edge(y+1, x+1, INF)

print(su - dinic.max_flow(0, 1))

Measured memory_bytes: 3444
N = gets.to_i
A = N.times.map { gets.to_i }

max_idx = -1
max_val = -1
second_val = -1
A.each_with_index do |a, idx|
  if a > max_val
    second_val = max_val
    max_val = a
    max_idx = idx
  elsif a == max_val || a > second_val
    second_val = a
  end
end

N.times do |idx|
  if idx == max_idx
    puts second_val
  else
    puts max_val
  end
end


Measured memory_bytes: 4860
#![allow(unused_imports)]
#![allow(unused_variables)]
#![allow(non_snake_case)]
#![allow(dead_code)]
#![allow(deprecated)]

use std::cell::{Cell, Ref, RefCell, RefMut};
use std::cmp::{max, min, Ordering};
use std::collections::*;
use std::fmt::{Debug, Formatter, Write as FmtWrite};
use std::io::{stderr, stdin, BufRead, Write};
use std::mem::{replace, swap};
use std::ops::*;
use std::rc::Rc;
use std::usize;

const MOD_10_9_7: u64 = 1_000_000_007;
const INF: i64 = 1_000_000_000_000;
const MIN_INF: i64 = -1_000_000_000_000;

/// FYI: https://github.com/vain0x/scan-bench
#[allow(unused_macros)]
macro_rules! read {
    ([$t:ty] ; $n:expr) =>
        ((0..$n).map(|_| read!([$t])).collect::<Vec<_>>());
    ($($t:ty),+ ; $n:expr) =>
        ((0..$n).map(|_| read!($($t),+)).collect::<Vec<_>>());
    ([$t:ty]) =>
        (rl().split_whitespace().map(|w| w.parse().unwrap()).collect::<Vec<$t>>());
    ($t:ty) =>
        (rl().parse::<$t>().unwrap());
    ($($t:ty),*) => {{
        let buf = rl();
        let mut w = buf.split_whitespace();
        ($(w.next().unwrap().parse::<$t>().unwrap()),*)
    }};
}

fn rl() -> String {
    let mut buf = String::new();
    stdin().read_line(&mut buf).unwrap();
    buf.trim_right().to_owned()
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let (n, m) = read!(usize, usize);
    let mut list: Vec<(usize, usize, usize)> = Vec::with_capacity(m);
    for i in 0..m {
        let input = read!(usize, usize);
        list.push((i, input.0, input.1));
    }

    list.sort_by(|x, y| {
        if x.1 != y.1 {
            x.1.cmp(&y.1)
        } else {
            x.2.cmp(&y.2)
        }
    });

    let mut numbered = Vec::with_capacity(m);
    let mut pref_number = list.first().unwrap().1;
    let mut city_birth_order = 0;
    for &city in &list {
        if pref_number == city.1 {
            city_birth_order += 1;
        } else {
            pref_number = city.1;
            city_birth_order = 1;
        }
        numbered.push((
            city.0,
            format!("{:>06}{:>06}", &pref_number, &city_birth_order),
        ));
    }

    numbered.sort_by_key(|x| x.0);

    for ans in &numbered {
        println!("{}", ans.1);
    }
}


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

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

using namespace std;

pair<int,int> hb(const vector<int> &l, const vector<int> &r, int K) {
  int hit = 0;
  int blow = 0;
  REP(i,K) if (l[i] == r[i]) ++hit;
  vector<int> cnt(11,0);
  REP(i,K) ++cnt[l[i]];
  REP(i,K) if(cnt[r[i]]) ++blow;
  return make_pair(hit, blow-hit);
}

vector<int> search(const vector<int> &v, const vector<tuple<vector<int>,int,int>> &hint, int l) {
  if (v.size() == l) {
    REP(i,hint.size()) {
      vector<int> hi;
      int h,b;
      tie(hi,h,b) = hint[i];
      if (hb(v,hi,l) != make_pair(h,b)) return vector<int>();
    }
    return v;
  } else {
    vector<int> vv(l,11);
    REP(i,v.size()) vv[i]=v[i];
    REP(i,hint.size()) {
      vector<int> hi;
      int h,b,hv,bv,hvv,bvv;
      tie(hi,h,b) = hint[i];
      tie(hvv,bvv) = hb(vv,hi,l);
      if(hvv>h||bvv>b) return vector<int>();
      int rem = h-hvv + b-bvv;
      if (rem > l-v.size()) return vector<int>();
    }
    vector<int> cnt(10);
    REP(i,v.size()) ++cnt[v[i]];
    vector<int> ans;
    REP(i,10){
      if(cnt[i]==0) {
        auto cp = v;
        cp.push_back(i);
        auto res = search(cp,hint,l);
        if (res.empty()) continue;
        if (ans.empty())
          ans = res;
        else
          throw "hoge";
      }
    }
    return ans;
  }
}

int main() {
  while(1){
    int l,h;
    cin>>l>>h;
    if(!l) break;
    vector<tuple<vector<int>,int,int>> hint;
    REP(i,h) {
      string tr;
      int hit, blow;
      cin>>tr>>hit>>blow;
      vector<int> trv(l);
      REP(j,l) trv[j] = tr[j]-'0';
      hint.emplace_back(trv,hit,blow);
    }
    vector<int> v;
    try{
      auto ans = search(v, hint, l);
      if (ans.empty()) {
        cout << "NO"<< endl;
      }else {
        for(auto i:ans) cout<<i;
        cout<<endl;
      }
    }catch(...){
      cout<<"NO"<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1300
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>*/
 
#define pb push_back
#define mp make_pair
#define sz(s) ((int)(s.size()))
#define all(s) s.begin(), s.end()
#define rep(i, a, n) for (int i = a; i <= n; ++i)
#define per(i, n, a) for (int i = n; i >= a; --i)
#define onlycin ios_base::sync_with_stdio(false); cin.tie(0) 
using namespace std;
// using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
/*typedef tree<
pair < int, int >,
null_type,
less< pair < int, int > >,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
// find_by_order() order_of_key()
const int MAXN = (int)5e5+228;
const char nxtl = '\n';
const int mod = (int)1e9+7;
const double eps = (double)1e-7;
template<typename T> inline bool updmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<typename T> inline bool updmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

string s;

int main() {
	#ifdef accepted
		freopen(".in", "r", stdin);
		freopen(".out", "w", stdout);
	#endif
	onlycin;
	bool ok = 1;
	int a, b; cin >> a >> b;
	cin >> s;
	ok &= (s[a] == '-');
	rep(i, 0, a-1) {
		if(!isdigit(s[i])) ok = 0;
	}
	rep(i, a+1, b+a) {
		if(!isdigit(s[i])) ok = 0;
	}
	if(!ok) cout << "No\n";
	else cout << "Yes\n";
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L
#define MOD 1000000007
//setprecision(15)

int main() {
	int N; cin >> N;
	vector<int> v(N);
	rep(i, N) {
		int tmp; cin >> tmp; tmp *= -1;
		v[i] = tmp;
	}
	sort(v.begin(), v.end());
	int ans = 0;
	int cnt = 0;
	for (auto it = v.begin(); it != v.end(); it++) {
		if (cnt % 2 == 0) {
			ans += -(*it); cnt++;
		} else {
			ans -= -(*it); cnt++;
		}
	}
	cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef complex<double> P;
typedef pair<int,int> pii;
#define REP(i,n) for(ll i=0;i<n;++i)
#define REPR(i,n) for(ll i=1;i<n;++i)
#define FOR(i,a,b) for(ll i=a;i<b;++i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define MOD (ll)(1e9+7)
#define ADD(a,b) a=((a)+(b))%MOD
#define FIX(a) ((a)%MOD+MOD)%MOD

int main(){
  REPR(i,10)REPR(j,10){
    printf("%dx%d=%d\n",i,j,i*j);
  }
  return 0;
}

Measured memory_bytes: 1096
#include <bits/stdc++.h>
#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define pf push_front
#define sec second
#define sz(x) ((int)(x).size())
#define ALL( c ) (c).begin(), (c).end()
#define gcd(a,b) __gcd(a,b)
#define mem(x,n) memset(x,n,sizeof(x))
#define endl "\n"
using namespace std;


int main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  string s;
  cin >> s;
  char now = 'A';
  string ans;
  rep(i,sz(s)){
    if (s[i] == now) {
      ans += now;
      if (now == 'A') {
        now = 'Z';
      }else{
        now = 'A';
      }
    }
  }
  bool flag = ans[sz(ans) - 1] == 'Z';
  if (!flag) {
    string new_ans;
    rep(i,sz(ans)-1){
      new_ans += ans[i];
    }
    ans = new_ans;
  }
  
  if (sz(ans) > 0) {
    cout << ans << endl;
  }else{
    cout << -1 << endl;
  }
  return 0;
}

Measured memory_bytes: 1196
#include <iostream>

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

int main(){
    string x;
    cin >> x;
    ll snum = 0;
    ll ans = x.size();
    REP(i, x.size()){
        if(x.at(i) == 'S'){
            snum++;
        }else if(snum > 0){
            ans -= 2;
            snum--;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
import sys, math

if(__name__ == "__main__"):

    A, B, C = map(int, input().strip().split() )
    """
    A: r, B: g, C: b
    b > g > r
    C > B > A
    """
    K = int( input().strip() )

    times = 0
    while(A >= B):
        B *= 2
        times += 1
    while(B >= C):
        C *= 2
        times += 1
    if(times <= K):
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 9180
n = int(input())
li = list(map(int,input().split()))
licumsum = 0
for i in range(n):
    licumsum += li[i]
asum = 0
for i in range(n):
    asum += li[i]*(licumsum - li[i])
    if asum >= (10**9 + 7)*2:
        asum = asum % ((10**9 + 7)*2)
if asum//2 >= 10**9 + 7:
    print(asum//2-(10**9+7))
else:
    print(asum//2)

Measured memory_bytes: 94096
#import sys
#input=sys.stdin.read
#*x,=map(int, input().split("\n"))
x=[int(input()) for _ in range(5)]
tmp=100
for i in range(5):
    if x[i]%10:
        tmp = min(tmp,x[i]%10)
        x[i]//=10
        x[i]*= 10
        x[i]+=10
ans= sum(x)
if tmp<100:
    ans-=10
    ans+=tmp
print(ans)
    


Measured memory_bytes: 9036
#include <iostream>

using namespace std;


int main(){
    int N;
    cin >> N;
    int ans = 0;
    for(int i = 1; i <= N; i++){
        if(i % 2 == 0) continue;
        int count = 0;
        for(int j = 1; j <= i; j++){
            if(i % j == 0){
                count++;
            }
        }
        if(count == 8){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll          long long
#define pll         vector< pair<ll ,ll> >
#define vll         vector<ll>
#define vi          vector<int>
#define hell        1000000007
#define rep(i,a,b)  for(ll i=a;i<b;i++)
#define pb          push_back
#define F           first
#define S           second
#define mp          make_pair
#define all(v)      v.begin(), v.end()
#define lb          lower_bound  //value not less than(>=)
#define ub          upper_bound  //value greater than(>)
#define bs          binary_search
#define pcont(v)    for(auto it:v) cout<<it<<" ";cout<<endl
#define ret(x)      return cout << x,0;
#define pi          pair<ll,pair<ll,ll> >
int const MAX = 1e5 + 5;
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
    ll n,k;
    cin >> n >> k;
    ll a[n];
    rep(i,0,n) cin >> a[i];

    n--,k--;
    ll ans=n/k;
    if(n%k) ans++;
    cout << ans;


}


Measured memory_bytes: 1024
import java.util.Scanner;

public class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()){
			int p = scan.nextInt();
			for(int i = 0;i < 2;i++){
				int t = scan.nextInt();
				if(t < p){
					p = t;
				}
			}
			int j = scan.nextInt();
			int jj = scan.nextInt();
			System.out.println(p+((j < jj)?j:jj)-50);
		}
	}
}

Measured memory_bytes: 17180
#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque

n = int(input())
a = [int(v) for v in input().split()]

for v in a:
    if v % 2 == 0:
        if (v % 3) != 0 and (v % 5) != 0:
            print("DENIED")
            exit()

print("APPROVED")


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

class UnionFind
{
private:
    vector<int> par;
    vector<int> rank;
    vector<int> sz;

public:
    UnionFind(int n) : par(n), rank(n, 0), sz(n, 1) {
        iota(par.begin(), par.end(), 0);
    }

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

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;

        if (rank[x] < rank[y]) {
            par[x] = y; sz[y] += sz[x];
        } else {
            par[y] = x; sz[x] += sz[y];
            if (rank[x] == rank[y]) rank[x]++;
        }
    }

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

    int size(int x) {
        return sz[find(x)];
    }
};

int main()
{
    int n, m; cin >> n >> m;
    vector<int> a(m), b(m);
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
    }

    UnionFind uf(n);
    vector<ll> ans(m);

    for (int i = m - 1; i >= 0; i--) {
        if (i == m - 1) {
            ans[i] = (ll)n * (n - 1) / 2;
        } else {
            if (uf.same(a[i+1], b[i+1])) {
                ans[i] = ans[i+1];
            } else {
                ans[i] = ans[i+1] - uf.size(a[i+1]) * uf.size(b[i+1]);
                uf.unite(a[i+1], b[i+1]);
            }
        }
    }

    for (int i = 0; i < m; i++) {
        cout << ans[i] << '\n';
    }
    return 0;
}

Measured memory_bytes: 4096
<?php
  list($d) = explode(" ", trim(fgets(STDIN)));

  if($d == '25'){
    echo 'Christmas';
    exit;
  }else if($d == '24'){
    echo 'Christmas Eve';
    exit;
  }else if($d == '23'){
    echo 'Christmas Eve Eve';
    exit;
  }else if($d == '22'){
    echo 'Christmas Eve Eve Eve';
    exit;
  }

Measured memory_bytes: 15704
#include<stdio.h>

int main(void){
    long long int N,M,ans=0;
    scanf("%lld %lld",&N,&M);
    ans = N*M-(N*2+M*2-4);
    if(ans < 0){
        ans = 0 - ans;
    }
    printf("%lld\n",ans);
    return 0;
}


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

int main(){
	int a,b;
	cin >> a >> b;
	if(a == b){
		cout << a+b << endl;
	}else{
		int c = max(a,b);
		cout << c+c-1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
using namespace std;
int n,m=1e9,num;
int read()
{
	int x=0,f=1;
	char ch=getchar();
	for(;!isdigit(ch);f=(ch=='-')?-1:1,ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x*f;
}
int cha(int x)
{
	int ans=0;
	while(x) ans+=x%10,x/=10;
	return ans;
}
int main()
{
	n=read();
	for(int i=1;i<=n/2+1;++i)
	  {
	  	int a1=i,a2=n-i;
	  	m=min(cha(a1)+cha(a2),m);
	  }
	printf("%d",m);
	return 0;
}

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

#define DEBUG(x) cout << "DEBUG>" << #x << ":" << x << endl;
#define REP(i,n) for(long long i=0;i<(n);i++)
#define FOR(i,a,b) for(long long i=(a);i<=(b);i++)

int main() {
  int N;
  cin >> N;
  vector<int> A(N);
  REP(i, N) {
    cin >> A[i];
  }
  while(true) {
    sort(A.begin(), A.end());
    REP(i, N-1) {
      if(A[i+1] % A[0] == 0) {
        A[i+1] = A[0];
      } else {
        A[i+1] = A[i+1] % A[0];
      }
    }
    int c = count(A.begin(), A.end(), A[0]);
    if(c == A.size()) break;
  }
  cout << A[0] << endl;
  return 0;
}


Measured memory_bytes: 640
//#include<stdio.h>
//int main() {
//	long long X, cnt = 0, ans = 0;
//	scanf("%lld", &X);
//	while (X>=0) {
//		if (cnt == 0)
//		{
//			X -= 6;
//			ans++;
//			cnt = 1;
//		}
//		else
//		{
//			X -= 5;
//			ans++;
//			cnt = 0;
//		}
//	}
//	printf("%lld\n", ans);
//
//	return 0;
//}

#include<stdio.h>
int main() {
	long long X, a = 0, b = 0, ans = 0;
	scanf("%lld", &X);
	a = X / 11;
	ans += 2 * a;
	b = X % 11;
	if (b > 0 && b <= 6)
	{
		ans += 1;
	}
	else if (b > 6 && b < 11)
	{
		ans += 2;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 128
def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2,r+1):
      pivot = denominator[p - 1]
      if pivot > 1:
          offset = (n - r) % p
          for k in range(p-1,r,p):
              numerator[k - offset] /= pivot
              denominator[k] /= pivot

  result = 1
  for k in range(r):
      if numerator[k] > 1:
          result *= int(numerator[k])

  return result

N = int(input())
s = {}
h = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e':11, 'f':13, 'g':17,'h':19,'i':23,'j':29,'k':31,'l':37,'m':41,'n':43,'o':47,'p':53,'q':59,'r':61,'s':67,'t':71,'u':73,'v':79,'w':83,'x':89,'y':97,'z':101}
for i in range(N):
    total = 1
    chs = list(input())
    for j in range(10):
        total *= h[chs[j]]
    s[total] = s.get(total, 0) + 1

cnt = 0
for v in s.values():
    if v < 2: continue
    a = cmb(v, 2)
    cnt += a

print(int(cnt))

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

#define N 2000

int r[N], a[N], w[N], t[N];
int dp[N+1][N+1][2];

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

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

  vector<int> order(n);
  iota(order.begin(), order.end(), 0);

  sort(order.begin(),order.end(),[&](int i,int j){
    return r[i]+t[i] > r[j]+t[j];
  });

  for(int i = 0; i <= 2000; i++) {
    for(int j = 0; j <= 2000; j++) {
      dp[i][j][0] = dp[i][j][1] = -1e9;
    }
  }

  dp[0][2000][0] = 0;

  for(int i = 0; i < n; i++){
    int k = order[i];

    int to2 = t[k];
    dp[i][to2][1] = max(dp[i][to2][1], a[k]);

    for(int j = 2000; j >= 0; j--){
      int to = min(j - r[k], t[k]);
      if (to >= 0) {
        dp[i][to][1] = max(dp[i][to][1], dp[i][j][0] + a[k]);
        dp[i][to][1] = max(dp[i][to][1], dp[i][j][1] + w[k]);
      }
    }

    for(int j=0; j <= 2000; j++) {
      dp[i+1][j][0] = max(dp[i][j][0], dp[i][j][1]);
    }
  }

  int ans = 0;

  for(int i=1; i<=2000; i++) {
    ans = max(ans, dp[n][i][0]);
  }

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 34484
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))

count = 0
for j in A:
    count += B[j-1]

#print(count)

for z in range(N-1):
    if A[z+1]- A[z] == 1:
        zz = A[z]
        count += C[zz-1]

print(count)
    
    


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

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

	vector<int> Nums;
	int now = 1;
	int cnt = 0;
	for (int i = 0; i < N; i++) {
		if (S[i] == (char)('0' + now)) {
			cnt++;
		}
		else {
			Nums.push_back(cnt);
			now = 1 - now;
			cnt = 1;
		}
	}
	Nums.push_back(cnt);

	if (Nums.size() % 2 == 0) {
		Nums.push_back(0);
	}

	vector<int> sum(Nums.size() + 1, 0);
	for (int i = 0; i < Nums.size(); i++) {
		sum[i + 1] = sum[i] + Nums[i];
	}

	int add = 2 * K + 1;
	int left = 0;
	int right = 0;
	int ans = 0;
	for (int i = 0; i < Nums.size(); i+=2) {
		left = i;
		right = min(i + add, (int)Nums.size());
		int tmp = sum[right] - sum[left];
		ans = max(ans, tmp);
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 1272
N,D,A=map(int,input().split())
XH=[]
inf=float("inf")
for i in range(N):
    X,H=map(int,input().split())
    if H%A==0:
        H//=A
    else:
        H=H//A+1
    XH.append([X,H])
XH.sort()
XH=[[-inf,0]]+XH

L=0
lst=[0]*(N+1)
S=[0]*(N+1)
lst[1]=XH[1][1]
S[1]=lst[1]

for R in range(2,N+1):
    r=XH[R][0]
    l=r-2*D
    while XH[L][0]<l:
        L+=1
    lst[R]=max(0,XH[R][1]-(S[R-1]-S[L-1]))
    S[R]=lst[R]+S[R-1]
    
print(S[-1])

Measured memory_bytes: 82264
H,W,K=map(int,input().split())
l =[[0],[1]]
for i in range(2,W):
    for n,j in enumerate(l):
        if j[-1] < i-1:
            l.append(j+[i])
m =[0]*(W+1)
for i in l:
    for j in i:
        m[j]+=1
m[0]=0
wa =len(l)
ans=[{i:0 for i in range(W+2)} for _ in range(H+1)]
ans[0][1]=1
for i in range(H):
    for j in range(1,W+1):
        ans[i+1][j] = (wa-m[j-1]-m[j])*ans[i][j] +m[j-1]*ans[i][j-1]+m[j]*ans[i][j+1]
if W ==1:
    print(1)
else:
    print(ans[H][K]%(10**9+7))


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

int main()
{
  int a;
  cin >> a;
  string s;
  cin >> s;
  if(a >= 3200)
  {
    cout << s << endl;
  }
  else
  {
    cout << "red" << endl;
  }
  return 0;
}

Measured memory_bytes: 256