akhauriyash/Code-Regression huggingface dataset:
/*Code by Codercjh*/
#include<bits/stdc++.h>
#define fr(i,a,b) for(int i=(a);i<=(b);++i)
#define rf(i,a,b) for(int i=(a);i>=(b);--i)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
typedef long long ll;
template<typename T>
inline void read(T &x){
	char c=getchar();T fh=0;bool f=false;
	while(!isdigit(c))f|=(c=='-'),c=getchar();
	while(isdigit(c))fh=(fh<<1)+(fh<<3)+(c^48),c=getchar();
	x=f?-fh:fh;
	return;
}
int n,k,c,cnt,ans;
char s[200005];
int l[200005],r[200005];
int main(){
    read(n),read(k),read(c);
	cin>>s+1; 
	fr(i,1,n)if(s[i]=='o')l[++cnt]=i,i+=c;
	int cnt1=k;
	rf(i,n,1){
		if(s[i]=='o')r[cnt1--]=i,i-=c;
		if(!cnt1)break;
	}
	fr(i,1,k)if(l[i]==r[i])printf("%d\n",l[i]);
	return 0;
}


Measured memory_bytes: 3200
/******************************************
*    AUTHOR:         julianferres         *
******************************************/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define DBG(x) cerr << #x << " = " << (x) << endl
#define esta(x,c) ((c).find(x) != (c).end())
#define RAYA cerr << "===============================" << endl

int main(){
    FIN;
    int n;
    cin >> n;
    vector<double> p(n, 0);
    forn(i, n) cin >> p[i];

    vector<double> dp(n + 1, 0), nex(n + 1, 0);

    dp[1] = p[0];
    dp[0] = 1 - p[0];

    forr(i,1,n){
        nex[0] = dp[0] * (1 - p[i]);
        forr(j, 1, n + 1) if (j <= i + 1)
            nex[j] = dp[j - 1] * p[i] + dp[j] * (1 - p[i]);
        forn(j, n + 1) dp[j] = nex[j];
    }
    double sum = 0;
    forn(i, n + 1) if (i > n - i) sum += dp[i];
    cout << fixed << setprecision(12) << sum << endl;
    

    return 0;
}



Measured memory_bytes: 384
import fractions
import operator
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=0):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        """
        # size 以上である最小の 2 冪
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._tree = [default for _ in range(self._size * 2 - 1)]
        self._fn = fn

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param int value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size


N = int(input())
A = list(map(int, input().split()))

st = SegmentTree(size=N, fn=fractions.gcd, default=0)
for i, a in enumerate(A):
    st.set(i, a)

ans = 0
for i in range(N):
    ans = max(ans, fractions.gcd(st.get(0, i) or 0, st.get(i + 1, N) or 0))
print(ans)


Measured memory_bytes: 102248
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 105;
const int P = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int power(int x, ll y) {
	if (y == 0) return 1;
	int tmp = power(x, y / 2);
	if (y % 2 == 0) return 1ll * tmp * tmp % P;
	else return 1ll * tmp * tmp % P * x % P;
}
void update(int &x, int y) {
	x += y;
	if (x >= P) x -= P;
}
ll cnt; int dp[MAXN];
int n, ans, a[MAXN], b[MAXN];
int main() {
	read(n), ans = 1;
	for (int i = 1; i <= n; i++) {
		read(a[i]);
		if (a[i] == 1) {
			cnt += 1;
			a[i] = 0;
		}
	}
	for (int i = 1; i <= n; i++) {
		int Max = max(a[i - 1], a[i + 1]);
		if (a[i] > Max) {
			cnt += a[i] - Max;
			a[i] = Max;
		}
	}
	ans = power(2, cnt);
	for (int i = 1; i <= n - 1; i++) {
		b[i] = min(a[i], a[i + 1]);
		if (b[i]) b[i]--;
	}
	dp[0] = 1;
	for (int i = 0; i <= n - 1; i++) {
		for (int j = i + 1; j <= n; j++) {
			static int c[MAXN];
			memset(c, 0, sizeof(c));
			for (int k = i + 1, Min = min(b[k], b[i]); k <= j - 1; k++, chkmin(Min, b[k]))
				chkmax(c[k], Min);
			for (int k = j - 1, Min = min(b[k], b[j]); k >= i + 1; k--, chkmin(Min, b[k]))
				chkmax(c[k], Min);
			ll cnt = 0;
			for (int k = i + 1; k <= j - 1; k++) {
				c[k] = b[k] - c[k];
				if (c[k] - c[k - 1] > 0) cnt += c[k] - c[k - 1];
			}
			if (b[i] == 0 && (b[j] != 0 || i != j - 1)) cnt++;
			update(dp[j], 1ll * dp[i] * power(2, cnt) % P);
			if (b[j] == 0) break;
		}
	}
	writeln(1ll * ans * dp[n] % P);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <utility>


auto input() {
	int H, W;
	std::cin >> H >> W;

	auto table = std::vector<std::string>(H);
	for(int i = 0; i < H; ++i) {
		std::string buff;
		std::cin >> buff;
		table[i] = std::move(buff);
	}

	return table;
}


auto sweep(const std::vector<std::string>& table) {
	auto dist = table;

	auto countBombs = [&](int r, int c) -> int {
		int cnt {};
		for(int i = r - 1; i <= r + 1; ++i){
			if(i < 0 || i >= dist.size())
				continue;
			for(int j = c - 1; j <= c + 1; ++j) {
				if(j < 0 || j >= dist[0].size())
					continue;
				if(table[i][j]=='#')
					++cnt;
			}
		}

		return cnt;
	};

	for(int i = 0; i < dist.size(); ++i) {
		for(int j = 0; j < dist[0].size(); j++) {
			if(table[i][j] == '.') {
				dist[i][j] = std::to_string(countBombs(i,j))[0];
			}
		}
	}

	return dist;
}



void process() {
	auto table = input();

	auto ret = sweep(table);

	for(auto&& e : ret)
		std::cout << e << std::endl;
}


int main() {
	process();
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>

using namespace std;

void dfs(int y, int x, int **map, int num, int n);
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int main()
{
	int n, r, c, size, m, o, angle, **map, **temp, f1, f2, f3, f4, tmp;
	//一行目入力(n, m)
	scanf("%d %d",&n, &m);
	map = new int *[n];
	temp = new int *[n];
	for(f1 = 0; f1 < n; f1++)
	{
		map[f1] = new int [n];
		temp[f1] = new int [n];
	}
	//グリッド情報入力
	for(f1 = 0; f1 < n; f1++)
	{
		for(f2 = 0; f2 < n; f2++)
		{
			scanf("%d",&map[f1][f2]);
		}
	}
	//シュミレーション開始
	for(f1 = 1; f1 <= m; f1++)
	{
		scanf("%d",&o);
		switch(o)
		{
			//回転
			case 0:
				scanf("%d %d %d %d",&r, &c, &size, &angle);
				r--; c--; size--;
				for(f2 = 1; f2 <= angle / 90; f2++)
				{
					//コピー
					for(f3 = r; f3 <= r + size; f3++)
					{
						for(f4 = c; f4 <= c + size; f4++)
						{
							temp[f3][f4] = map[f3][f4];
						}
					}
					//代入
					for(f3 = r; f3 <= r + size; f3++)
					{
						for(f4 = c; f4 <= c + size; f4++)
						{
							map[f3][f4] = temp[r + (c + size - f4)][f3 + (c - r)];
						}
					}
				}
			break;
			//反転
			case 1:
				scanf("%d %d %d",&r, &c, &size);
				r--; c--; size--;
				for(f3 = r; f3 <= r + size; f3++)
				{
					for(f4 = c; f4 <= c + size; f4++)
					{
						map[f3][f4] = (map[f3][f4] == 0) ? 1 : 0;
					}
				}
			break;
			//左シフト
			case 2:
				scanf("%d", &r);
				r--;
				tmp = map[r][0];
				for(f2 = 1; f2 < n; f2++)
				{
					map[r][f2-1] = map[r][f2];
				}
				map[r][n-1] = tmp;
			break;
			//右シフト
			case 3:
				scanf("%d", &r);
				r--;
				tmp = map[r][n-1];
				for(f2 = n-2; f2 >= 0; f2--)
				{
					map[r][f2+1] = map[r][f2];
				}
				map[r][0] = tmp;
			break;
			//島反転
			case 4:
				scanf("%d %d", &r, &c);
				r--; c--;
				tmp = map[r][c];
				dfs(r, c, map, tmp, n);
			break;
		}
	}
	//出力
	for(f1 = 0; f1 < n; f1++)
	{
		for(f2 = 0; f2 < n; f2++)
		{
			if(f2 < n - 1)
				printf("%d ",map[f1][f2]);
			else
				printf("%d",map[f1][f2]);
		}
		printf("\n");
	}
	return 0;
}

void dfs(int y, int x, int **map, int num, int n)
{
	int f1, nx, ny;
	map[y][x] = (num == 1) ? 0 : 1;
	for(f1 = 0; f1 < 4; f1++)
	{
		nx = x + dx[f1];
		ny = y + dy[f1];
		if(nx >= 0 && nx < n && ny >= 0 && ny < n && map[ny][nx] == num)
		{
			dfs(ny, nx, map, num, n);
		}
	}
}

Measured memory_bytes: 1200
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <utility>
using namespace std;
using ll = long long;

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

  map<pair<string, string>, ll> mp;

  for(int i=0; i< (1 << n); i++){
    string red = "", blue = "";
    for(int b=0; b < n; b++){
      if((i >> b) & 1){
        red += s[b];
      }
      else{
        blue += s[b];
      }
    }
    mp[{red, blue}]++;
  }

  ll ans = 0;

  for(int i=0; i< (1 << n); i++){
    string red = "", blue = "";
    for(int b=0; b < n; b++){
      if((i >> b) & 1){
        red += s[2 * n - b - 1];
      }
      else{
        blue += s[2 * n - b - 1];
      }
    }
    ans += mp[{red, blue}];
  }
 
  cout << ans << endl;

  return 0;
}

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

#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define INT_MAX_HALF (INT_MAX / 2)
#define EPS (1e-10)

using namespace std;
typedef long long ll;

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

    vector<ll> h(n);

    rep(i, n){
        cin >> h[i];
    }

    map<ll,int> ma;
    map<ll,int> mb;
    map<ll,int> mc;
    map<ll,int> md;

    rep(i, n){
        ll a,b,c,d;
        a = h[i] + i;
        b = i - h[i];
        c = h[i] - i;
        d = -1 * h[i] - i;

        ma[a]++;
        mb[b]++;
        mc[c]++;
        md[d]++;
    }

    ll ans = 0;

    for(auto tmp : ma){
        ll i = tmp.first;
        ll c = tmp.second;

        ans += c * mb[i];
    }

    for(auto tmp : mc){
        ll i = tmp.first;
        ll c = tmp.second;

        ans += c * md[i];
    }

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


Measured memory_bytes: 73428
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>//sort,reverse
#include<utility>//pair
#include<queue>//queue,priority_queue
#include<deque>//double_ended queue
using namespace std;
typedef pair<int,int> P;//Pでpair<-,->を表す。
typedef long long LL; 
LL MOD=1000000007;

/*ここから*/
int V;//頂点の個数
vector<int> e[2000010];//iから出る辺
int t[2000010];//親情報の記録媒体
int h[2000010];
bool h_flg[2000010];

//すでにある辺と頂点の情報から木の作成
void Tree(int s){//sは一番根元
    for(int i=1;i<=V;i++){
        t[i]=i;//初期情報
    }
    queue <int> q;
    q.push(s);
    while(!q.empty()){
        int from;
        from=q.front();
        q.pop();
        while(!e[from].empty()){
            int to;
            to=e[from].back();
            e[from].pop_back();
            if(to!=t[from]){
                t[to]=from;
                q.push(to);
            }
        }
    }
}

void height(int s){
    if(t[s]==s){h[s]=1;h_flg[s]=true;}
    else{
        if(!h_flg[t[s]]){height(t[s]);}
        h[s]=h[t[s]]+1;
        h_flg[s]=true;
    }
}

/*ここまで*/
int main()
{ 
    int n;
    cin>>n;
    V=n;
    for(int i=0;i<V-1;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    Tree(1);
    for(int i=0;i<2000010;i++){
        h[i]=0;
        h_flg[i]=false;
    }
    for(int i=1;i<=V;i++){
        height(i);
    }
    //for(int i=1;i<=V;i++){cout<<h[i]<<endl;}
    int ans[n+1];
    int cnt1=0;
    int cnt2=0;
    int b1=0;
    int b2=0;
    if(n%3==0){b1=n/3;b2=n/3;}
    else if(n%3==1){b1=n/3+1;b2=n/3;}
    else{b1=n/3+1;b2=n/3+1;}
    for(int i=1;i<=n;i++){
        if(h[i]%2==1){
            cnt1++;
            if(cnt1<=b1){ans[i]=1;}
            else{ans[i]=3;}
        }
        else{
            cnt2++;
            if(cnt2<=b2){ans[i]=2;}
            else{ans[i]=3;}
            }
    }
    if(cnt1<b1){
        int x=cnt1;
        cnt1=0;
        cnt2=0;
        int cnt3=x;
        for(int i=1;i<=n;i++){
            if(ans[i]==1){ans[i]=3*x;x--;}
            else{
                if(cnt1<b1){ans[i]=3*cnt1+1;cnt1++;}
                else if(cnt2<b2){ans[i]=3*cnt2+2;cnt2++;}
                else{ans[i]=cnt3*3+3;cnt3++;}
            }
        }
    }
    else if(cnt2<b2){
        int x=cnt2;
        cnt1=0;
        cnt2=0;
        int cnt3=x;
        for(int i=1;i<=n;i++){
            if(ans[i]==2){ans[i]=3*x;x--;}
            else{
                if(cnt1<b1){ans[i]=3*cnt1+1;cnt1++;}
                else if(cnt2<b2){ans[i]=3*cnt2+2;cnt2++;}
                else{ans[i]=cnt3*3+3;cnt3++;}
            }
        }
    }
    else{
        cnt1=0;cnt2=0;
        int cnt3=0;
        for(int i=1;i<=n;i++){
            if(ans[i]==1){ans[i]=cnt1*3+1;cnt1++;}
            else if(ans[i]==2){ans[i]=cnt2*3+2;cnt2++;}
            else{ans[i]=cnt3*3+3;cnt3++;}
        }
    }
    for(int i=1;i<n;i++){
        cout<<ans[i]<<' ';
    }
    cout<<ans[n]<<endl;
    return 0;
}

Measured memory_bytes: 70132
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long

  /* code */


int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,d;
  cin>>n>>d;
  ll res=n/(2*d+1);
  if(n%(2*d+1)>0)
  cout<<res+1<<'\n';
  else
  cout<<res<<'\n';
  return 0;
}


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

signed main()
{

  int w, h, x, y;
  scanf("%d %d %d %d", &w, &h, &x, &y);

  double W = (double)w;
  double H = (double)h;
  double X = (double)x;
  double Y = (double)y;

  int flg = 0;
  if( (X == W / 2.0) && (Y == H / 2.0) ) flg = 1;
  double ans = ( W * H ) / 2.0;
  printf("%lf", ans);
  putchar(' ');
  printf("%d\n", flg);

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  int a,b,c,d;
  cin >> a >> b >> c >>d;
  int l = a + b;
  int r = c + d;
  if(l > r){
    cout << "Left" << endl;
  } else if (l == r) {
    cout << "Balanced" << endl;
  } else {
    cout << "Right" << endl;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iomanip>
#include <vector>
#include <cstdio>
#include <float.h>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <stack>
#include <functional>
 
using namespace std;
 
#define endl '\n'
#define MOD 1000000007
#define INF 1ll<<30
#define MAX 100010
#define eps 1e-11
#define bit_max 1ll<<32
#define _USE_MATH_DEFINES



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  // 	freopen("input.txt","r",stdin);
  // 	freopen("output.txt","w",stdout);
	int n;
	cin>>n;
	string a ;
	cin>>a;
	int q;
	long long int mc[n+5];
	mc[0] = 0;
	for(int i=0;i<n;i++)
	{
		mc[i+1] = mc[i] + (a[i]=='M');
	}
	cin>>q;
	for(int i=0;i<q;i++)
	{
		long long int k;
		cin>>k;
		long long int d=0;
		long long int dm = 0;
		long long int ans = 0;
		for(int j=0;j<n;j++)
		{
			if(j-k>=0)
			{
				if(a[j-k] == 'D')
				{
					d--;
					dm = dm - (mc[j] - mc[j-k+1]);
				}

			}
			if(a[j]=='D')
			{
				d++;
			}
			if(a[j]=='M')
			{
				dm = dm + (d);
			}
			if(a[j]=='C')
			{
				ans = ans+dm;
			}
		}
		cout<<ans<<endl;
	}
	return 0 ;
}


Measured memory_bytes: 9116
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repp(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];
    int ans = 0, r = 0, u;
    rep(i, 0, n){   
        u = (a[i] + r) / 2;
        ans += u;
        if(a[i] != 0 && (a[i] + r) % 2) r = 1;
        else r = 0;
        // cout << ans << ' ' << r << endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int main(void) {
  int n;
  cin >> n;
  vector<int> v(n + 1);
  int ans = 0;
  for (int i = 1; i <= n; i += 2) {
    int c = 0;
    for (int j = 1; j <= i; j++) {
      if (i % j == 0)
        c++;
    }
    if (c == 8)
      ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef __LOCAL
    #define DBG(X) cout << #X << " = " << (X) << endl;
    #define SAY(X) cout << (X) << endl;
    #include <filesystem>
    namespace fs = std::filesystem;
#else
    #define DBG(X)
    #define SAY(X)
#endif

using namespace std;

using ll = long long int;
using ull = unsigned long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int dx[]={1, 0, -1, 0, 1,-1, 1,-1};
int dy[]={0, 1, 0, -1, 1, 1,-1,-1};
const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);
static mt19937 _g(time(nullptr));
 
inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const map<T, S> p) { for (auto el : p) cout << "[" << el.first << ";" << el.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }
void chmin(long long &a, long long b) { if (a > b) a = b; }

int N;
vector<ll> A;
void input(){
    fast_io();
    #ifdef __LOCAL
        fs::path __p = __FILE__;
        fs::path __input, __output;
        __input = __output = __p.parent_path();
        __input += string("/input/") + string(__p.stem()) + string(".txt");
        __output += string("/output/") + string(__p.stem()) + string(".txt");
        freopen(__input.c_str(), "r", stdin);
        freopen(__output.c_str(), "w", stdout);
    #endif
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        ll a;
        cin >> a;
        A.push_back(a);
    }
}

ll cost(int i, int j, const vector<ll> &a){
    if(j==0 || j==4) return a[i];
    else if(j==1 || j==3){
        if(a[i]%2==1) return 1;
        if(a[i]==0) return 2;
        else return 0;
    }
    else {
        if(a[i]%2==0) return 1;
        else return 0;
    }
}

int solve(){
    vector<vector<ll> > dp(N+1,vector<ll>(5,1e8));
    for (int j = 0; j < 5; j++) dp[0][j]=0;
    
    for (int i = 0; i < N; i++)
        for (int j = 0; j < 5; j++)
            for (int t = j; t < 5; t++)
                chmin(dp[i+1][t],dp[i][j]+cost(i,t,A));

    ll ans=1e8;
    for (int j = 0; j < 5; j++)
        chmin(ans,dp[N][j]);
        
    cout << ans << endl;
    
    return 0;
}   

int main()
{
    input();
    solve();
    return 0;
}


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

using namespace std;
long long pd[3][1001];
int main()
{
    long long n,i,j;
    cin>>n;
    for(i=1;i<=2;i++)
        for(j=1;j<=n;j++)
        {
            cin>>pd[i][j];
            pd[i][j]+=max(pd[i-1][j],pd[i][j-1]);
        }
    cout<<pd[2][n];

    return 0;
}


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

int main(int argc, char const *argv[]) {
    int a;
    string s;
    cin >> a >> s;

    if (a < 3200) {
        cout << "red" << endl;
    } else {
        cout << s << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>

typedef long long int ll;

int main()
{
	int ans=1, num;
	bool check = false;
	char a, tw[200];
	ll K, count=0;
	std::string S, d;
	std::cin >> S;
	scanf("%lld", &K);
	for(int i=0; i<K; i++){
		num = S[i] - '0';
		if(num != 1){
			ans = num;
			break;
		} 
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    r = ii()
    if r < 1200:
        print('ABC')
    elif r < 2800:
        print('ARC')
    else:
        print('AGC')


if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
def count(n, ls, c = 0):
    next_ls = [0]*n
    for i in range(n):
       next_ls[i] = ls.count(ls[i])
    if ls == next_ls:
        return c, ls
    else:
        return count(n, next_ls, c+1)

    
while True:
   n = input()
   if n == 0:
       break
   ls = map(int, raw_input().split())
   a = count(n, ls)
   print a[0]
   print ' '.join(map(str, a[1]))

Measured memory_bytes: 4232
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define hell 1000000007
#define PI 3.14159265358979323846
using namespace std;
ll expo(ll base,ll p)
{
    if(p==0ll)
        return 1ll;
if(p%2==0)
    return expo((base*base)%hell,p/2);
else
    return (base*expo((base*base)%hell,p/2))%hell;
}
ll fac[1000005],inv[1000005];
void cal()
{
    fac[0]=1;
    for(ll i=1;i<=1000000;i++)
        fac[i]=(fac[i-1]*i)%hell;
    inv[1000000]=expo(fac[1000000],hell-2);
    for(ll i=99999;i>=0;i--)
        inv[i]=(inv[i+1]*(i+1))%hell;
}
ll ncr(ll n,ll r)
{
    return (((fac[n]*inv[r])%hell)*inv[n-r])%hell;
}
int main()
{
   ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    //int c=0;
    while(t--) {
     ll n,i,j,q,s=0,l,r;
     cin>>n;
     if(n<3)
        {
            cout<<0;
            return 0;
        }
     ll dp[n+1],pre[n+1];
     for(i=0;i<3;i++)
     {
         dp[i]=0;
         pre[i]=0;
     }
     for(i=3;i<=n;i++)
        dp[i]=1;
     for(i=3;i<=n;i++)
     {
         dp[i]=(dp[i]+pre[i-3])%hell;
         pre[i]=pre[i-1]+dp[i];
     }
     cout<<dp[n];
    }

}


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

public class Prime{
    public static void Main()
    {
        int n = int.Parse(Console.ReadLine());
         
        var primeFactors = PrimeFactors(n);
         
        string output = primeFactors.Count() == 0 
                        ? n.ToString() 
                        : string.Join(" ", primeFactors.Select (f => f.ToString()).ToArray()); //AOJ??¨
                        //:string.Join(" ", primeFactors);
        Console.WriteLine("{0}: {1}", n, output);
    }
     
    public static IEnumerable<int> PrimeFactors(int n)
    {
        int i = 2;
        int tmp = n;
         
        while (i <= tmp)
        {
            if(tmp % i == 0){
                tmp /= i;
                yield return i;
            }else if(i*i > n){
                i = int.MaxValue; //???????????????
                yield return tmp;
			}else{
                i++;
            }
        }
    }
}

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

int main(){
  int A, B, C, D;
  int L, R;

  cin >> A >> B >> C >> D;
  L = A + B;
  R = C + D;

  if(L>R){
    cout << "Left\n";
  }else if(L == R){
    cout << "Balanced\n";
  }else if(L<R){
    cout << "Right\n";
  }

  return 0;
}

Measured memory_bytes: 256
import math

def main():
    s = input()
    k = int(input())
    cnt = 0
    if (len(s) == 0):
        cnt = 0
    elif (len(s) == 1):
        cnt = math.floor(k/2)
    elif (len(s) == 2):
        if (s[0] == s[1]):
            cnt = k
        elif (s[0] != s[1]):
            cnt = 0
    else:
        l = list()
        prev = ''
        for c in s:
            if(c == prev):
                l[-1][1] += 1
            else:
                l.append([c, 1])
                prev = c
        if (len(l) == 1):
            cnt += l[0][-1] * k // 2
        elif (len(l) == 2):
            cnt += l[0][-1] // 2
            cnt += l[1][-1] // 2
            cnt *= k
        else:
            edge1 = l[0]
            edge2 = l[-1]
            mid = l[1:-1]
            for e in mid:
                cnt += e[1] // 2 * k
            if (edge1[0] == edge2[0]):
                cnt += (edge1[1] + edge2[1]) // 2 * (k-1)
            else:
                cnt += (edge1[1]) // 2 * (k-1)
                cnt += (edge2[1]) // 2 * (k-1)
            cnt += edge1[1] // 2
            cnt += edge2[1] // 2

    print(cnt, end='')


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        String ans = "";
        for (int i = 0; i < Math.max(a, b); i++) {
            ans += Math.min(a, b);
        }
        System.out.println(ans);
        sc.close();
    }
}

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

#define CPP_STR(x) CPP_STR_I(x)
#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_STR_I(args...) #args
#define CPP_CAT_I(x,y) x ## y

using i8  = int8_t;
using u8  = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;

using f32 = float;
using f64 = double;

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define REPS(i, n) for(i64 i = 1; i <= n; ++i)
#define RREP(i, n) for(i64 i = n - 1; i >= 0 ; --i)
#define RREPS(i, n) for(i64 i = n; i >= 1; --i)

#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))

#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define pb push_back
#define mp make_pair
#define F first
#define S second

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }

template<typename T, size_t N>
i64 SIZE(const T (&)[N]) { return static_cast<i64>(N); }


struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


#define MAX_N 200'000
i64 K, N;
i64 A[MAX_N + 1];

int main() {
    cin >> K >> N;
    REP(i, N) cin >> A[i];
    A[N] = K + A[0];

    i64 maxd = 0;
    REP(i, N) {
        chmax(maxd, abs(A[i + 1] - A[i]));
    }

    i64 ans = K - maxd;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
const int MOD=1000000007;
#define endl "\n"
#define fst first
#define snd second
const int UNDEF = -1;
const int INF=1<<30;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
typedef pair<ll,ll> pll;typedef vector<ll> vll;typedef pair<int,int> pii;typedef vector<int> vi;typedef vector<vi> vvi;
#ifdef ONLINE_JUDGE
#define assert(...) /* nothing */
#endif
#define DEBUG_CAT
#ifdef DEBUG_CAT
#define dbg(...)   printf( __VA_ARGS__ )
#else 
#define dbg(...)   /****nothing****/
#endif
vector<string> a;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
const int mn=1e3+2;
int vdist[mn][mn];
void solve(long long xn, long long yn, vector<string> A){
	for (int x=0;x<mn;x++) for (int y=0;y<mn;y++) vdist[x][y]=INF;
	a=A;
	queue<pii> q;
	for (int x=0;x<xn;x++) for (int y=0;y<yn;y++) {
		//printf("%c\n",a[x][y]);
		if (a[x][y]=='#') {q.push(MP(x,y)); vdist[x][y]=0;}
	}
	while(!q.empty()) {
		pii p=q.front(); q.pop(); int x=p.fst,y=p.snd;
		int d=vdist[x][y];
		//printf("%d %d:%d\n",x,y,d);
		for (int k=0;k<4;k++) {
			int nx=x+dx[k],ny=y+dy[k];
			if (0<=nx&&nx<xn&&0<=ny&&y<yn) {
				if (vdist[nx][ny]==INF) {
					vdist[nx][ny]=d+1;
					q.push(MP(nx,ny));
				}
			}
		}
	}
	int ans=0;
	for (int x=0;x<xn;x++) for (int y=0;y<yn;y++) chkmax(ans,vdist[x][y]);
	printf("%d\n",ans);
}

int main(){	
	long long W;
	long long H;
	scanf("%lld",&H);
	vector<string> A(H-1+1);
	scanf("%lld",&W);
	for(int i = 0 ; i <= H-1 ; i++){
		cin >> A[i];
	}
	solve(H, W, A);
	return 0;
}



Measured memory_bytes: 14480
def c_GoHome(X):
    """
    1+2+...+n>=Xとなる最小のnがわかれば、時刻nで到達できる。
    (時刻iに右に跳ぶか、なにもしないかのどちらかを行う)
    左辺はn(n+1)/2なので、n^2+n-2X=0の正の解を切り上げたものが求める解である。
    よって、方程式を解いて、n_min=ceil( (-1+√(1+8X))/2 )を得られる。
    """
    import math
    n = math.ceil((-1 + math.sqrt(1 + 8 * X)) / 2)
    return n

X = int(input())
print(c_GoHome(X))

Measured memory_bytes: 3060
W = []
K = []

for i in range(10):
    W.append(int(input()))

for i in range(10):
    K.append(int(input()))

W.sort(reverse=True)
K.sort(reverse=True)

print(W[0] + W[1] + W[2] , K[0] + K[1] + K[2])


Measured memory_bytes: 5600
#include <iostream>
#include <stdlib.h>
#include <vector> //vector
#include <algorithm> //sort()
#include <numeric>
#include <tuple>

#define rep(i, n) for(int i=0; i<(int)(n);i++)
#define all(x) (x).begin(), (x).end()
#define debug(a) cout << "debug (" #a "):" << endl << (a) << endl;

typedef uint64_t ulint;
typedef int64_t lint;

using namespace std;

template<class T> inline bool chmin(T& a, T b);
template<class T> inline bool chmax(T& a, T b);
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v);

template<class T> lint sum(vector<T> a);
template<class T> double ave(vector<T> a);

lint n,m;
lint a,b,c,d;
lint i,j,k;

int main(){
//////////////////////////////////////////////////////

    cin >> n >> a >> b;

    //cout << "1213123" << endl;

    if( n* a > b)
    {
        cout << b << endl;
    }
    else
    {
        cout << n*a << endl;
    }
    

   // cout << (    ((n*a)>b)?b:(n*a) )<< endl;

//////////////////////////////////////////////////////
// Ctrl + Opt + N to make
    return 0;
}


//最小化用関数
template<class T> inline bool chmin(T& a, T b)
{
    if (a > b) 
    {
        a = b;
        return true;
    }
    return false;
}

//最大化関数
template<class T> inline bool chmax(T& a, T b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}


// vectorprint用
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";
	}
	return s;
}

// //合計
// template<class T> lint sum(vector<T> a)
// {
//     return std::accumulate(a.begin(), a.end(), 0);
// }


// //平均
// template<class T> double ave(vector<T> a)
// {
//     return std::accumulate(a.begin(), a.end(), 0.0) / a.size();
// }


Measured memory_bytes: 256
int main(){
int a,b,c,i,j;
scanf("%d",&j);
for (i=1;i<=j;i++) {
scanf("%d %d %d",&a,&b,&c);
if (a*a+b*b==c*c || b*b+c*c==a*a || c*c+a*a==b*b) {printf("YES\n");}
else {printf("NO\n");}
}
return 0;
}

Measured memory_bytes: 576
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert>
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

ostream& operator << (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << " ";
    return a;
}

#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << "\n";
    const int INF = 8e18;
//    const int mod = 2600000069;
    const int p = 10;
//    const ld PI = 3.1415926535;
#else
    #define dbg(x)
    const int INF = 8e18;
//    const int mod = 2600000069;
    const int p = 179;
//    const ld PI = 3.1415926535;
#endif

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> a[i];
    }
    vector<int> cnt(n, 0);
    for (int i = 0; i < n - 1; i++) {
        cnt[a[i] - 1]++;
    }
    for (int i = 0; i < n; i++) {
        cout << cnt[i] << "\n";
    }

}
/*

*/


Measured memory_bytes: 6368
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,l;cin>>n>>l;
  string s[110];
  for(int i=0;i<n;i++)cin>>s[i];
  sort(s,s+n);
  string t;
  for(int j=0;j<n;j++){
    t+=s[j];
  }
  cout<<t<<endl;
}

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

using namespace std;

int main(){
  string cmd,str,str2;
  int n,a,b;
  cin >> str;
  cin >> n;
  for(int i=0;i < n;i++){
    cin >> cmd;
    if(cmd == "print"){
      cin >> a >> b;
      cout << str.substr(a,b-a+1) << endl;
    }else if(cmd == "replace"){
      cin >> a >> b >> str2;
      str.replace(a,b-a+1,str2);
    }else if(cmd == "reverse"){
      cin >> a >> b;
      string tmp = str.substr(a,b-a+1);
      string tmp1 = tmp;
      for(int j=0;j < tmp.size();j++) tmp[j] = tmp1[tmp.size()-j - 1];
      for(int j=0;j < tmp.size();j++) str[a + j] = tmp[j];
    }
  }
  return 0;
}


Measured memory_bytes: 3228
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int up[4]={0, -1, 0, 1};
int lr[4]={1, 0, -1, 0};

int main(){
  int h, w, k;
  cin >> h >> w >> k;
  int x1, y1, x2, y2;
  cin >> x1 >> y1 >> x2 >> y2;
  x1--; y1--; x2--; y2--;
  vector<string> s(h);
  rep(i, h){
    cin >> s[i];
  }
  queue<P> Q;
  Q.push(P(x1, y1));
  vector<vector<int> > ans(h, vector<int>(w, -1));
  ans[x1][y1]=0;
  while(!Q.empty()){
    P p=Q.front();Q.pop();
    int qx=p.first, qy=p.second;
    rep(i, 4){
      repo(j, k){
        int nx=qx+lr[i]*j, ny=qy+up[i]*j;
        if(nx<0 || nx>=h || ny<0 || ny>=w || s[nx][ny]=='@')break;
        if(ans[nx][ny]!=-1 && ans[nx][ny]<=ans[qx][qy])break;
        if(ans[nx][ny]!=-1)continue;
        ans[nx][ny]=ans[qx][qy]+1;
        Q.push(P(nx, ny));
      }
    }
  }
  cout << ans[x2][y2] << endl;
  return 0;
}


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

using namespace std;

typedef long long ll;

class UnionFind {
public:
    vector <ll> par; // 各元の親を表す配列
    vector <ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz) : par(sz), siz(sz, 1LL) {
        for (ll i = 0; i < sz; ++i) par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz) {
        par.resize(sz);
        siz.assign(sz, 1LL);  // resize だとなぜか初期化されなかった
        for (ll i = 0; i < sz; ++i) par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x) { // 根の検索
        while (par[x] != x) {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool isSame(ll x, ll y) { // 連結判定
        return root(x) == root(y);
    }

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


int main()
{    
    ll n, m;
    cin >> n >> m;
    vector<ll>a;
    vector<ll>b;
    int temp1, temp2;
    for (int i = 0; i < m; i++) {
        cin >> temp1 >> temp2;
        a.push_back(temp1);
        b.push_back(temp2);
    }

    UnionFind ob(n);

    vector<ll> ans;
    ll  num = n * (n - 1) / 2;


    for (int i = m-1; i >= 0; i--) {
        ans.push_back(num);
        if (ob.root(a[i]-1) != ob.root(b[i]-1)) {
            num -= ob.size(a[i]-1) * ob.size(b[i]-1);
        }
        ob.merge(a[i]-1, b[i]-1);
    }

    for (int i = m - 1; i >= 0; i--) {
        cout << ans[i] << endl;
    }
    
    
    return 0;
}

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

using namespace std;

typedef long long ll;
const int N=2e5+5;
int main()
{
    ll a[N],n,ans;
    cin >> n;
    bool flag=0;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
        if(a[i]>i) flag=1;
        if(i>1)
        {
            if(a[i]>a[i-1]+1) flag=1;
        }
    }
    ll ma=a[n-1];
    if(flag) printf("-1\n");
    else
    {
        ans=a[n-1];
        for(int i=n-2;i>=0;i--)
        {
            if(a[i]+1==a[i+1]) continue;
            ans+=a[i];
        }
        cout << ans << endl;
    }
}


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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const ld eps = 1e-9;
const ll MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

template<typename T1, typename T2>
ostream& operator<<(ostream &os, const pair<T1, T2> p) {
  os << p.first << ":" << p.second;
  return os;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int h, w, K; cin >> h >> w >> K;
  vector<string> in(h);
  for(int i=0;i<h;++i) {
    cin >> in[i];
  }

  vvi a(h, vi(w));
  for(int i=0;i<h;++i) {
    for(int j=0;j<w;++j) {
      a[i][j] = in[i][j] - '0';
    }
  }

  vvi su(w, vi(h+1));
  for(int i=0;i<w;++i) {
    for(int j=0;j<h;++j) {
      su[i][j+1] = su[i][j] + a[j][i];
    }
  }

  int mi = INF;
  for(int i=0;i<1<<h;++i) {
    vi kugiri;
    for(int j=0;j<h-1;++j) {
      int val = (i>>j)&1;
      int valnxt = (i>>(j+1))&1;
      if(val != valnxt) kugiri.push_back(j+1);
    }
    vector<P> p;
    if(SZ(kugiri) == 0) {
      p.push_back({0, h});
    } else {
      p.push_back({0, kugiri[0]});
      for(int j=0;j<SZ(kugiri)-1;++j) {
        p.push_back({kugiri[j], kugiri[j+1]});
      }
      p.push_back({kugiri.back(), h});
    }
    
    int cnt = 0;
    bool ok = true;
    vi val(SZ(p), 0);
    for(int i=0;i<w;++i) {
      vi nxt1(SZ(p));
      vi nxt2 = val;
      bool ok1 = true, ok2 = true;
      for(int j=0;j<SZ(p);++j) {
        nxt1[j] = su[i][p[j].second] - su[i][p[j].first];
        nxt2[j] += nxt1[j];
        ok1 &= nxt1[j] <= K;
        ok2 &= nxt2[j] <= K;
      }
      if(ok2) val = nxt2;
      else if(ok1) {
        cnt++;
        val = nxt1;
      } else {
        ok = false;
        break;
      }
    }

    if(!ok) {
      continue;
    } else {
      mi = min(mi, cnt + SZ(p) - 1);
    }
  }
  cout << mi << endl;

}


Measured memory_bytes: 384
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 5;
ll f[maxn], inv[maxn];
ll fastPow(ll base, ll expo, ll mod)
{
    ll ans = 1;
    while (expo > 0)
    {
        if (expo & 1)
            ans = ans * base % mod;
        base = base * base % mod;
        expo >>= 1;
    }
    return ans % mod;
}
void init(int n)
{
    f[0] = 1;
    for (int i = 1; i <= n; ++i)
        f[i] = f[i - 1] * i % mod;
    inv[n] = fastPow(f[n], mod - 2, mod);
    for (int i = n - 1; i >= 0; --i)
        inv[i] = inv[i + 1] * (i + 1) % mod;
}
ll C(ll n, ll m)
{
    if (n < m)
        return 0;
    else
        return f[n] * inv[m] % mod * inv[n - m] % mod;
}
int main(void)
{
    int n, k;
    scanf("%d%d", &n, &k);
    ll ans = 0;
    init(n);
    for (int i = 0; i <= min(n - 1, k); ++i)
    {
        // printf("%d %d\n", C(n, i), C(n + i - 1, i));
        ans = (ans + C(n, i) * C(n - 1, i) % mod) % mod;
    }
    printf("%lld\n", ans);

    return 0;
}

Measured memory_bytes: 3328
#![allow(unused_imports)]
#![allow(clippy::many_single_char_names)]

// language: Rust(1.42.0)
// check available crates on AtCoder at "https://atcoder.jp/contests/language-test-202001"
// My Library Repo' is at "https://github.com/Loptall/prcn_lib"

/*
    そう甘くはないんだな〜w
*/

// from std...
use std::cmp::{
    max, min, Ordering,
    Ordering::{Equal, Greater, Less},
    Reverse,
};
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
use std::convert::TryInto;
use std::mem::swap;
use std::num::{NonZeroU32, ParseIntError};
use std::ops::{
    Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign,
    Index, IndexMut, Mul, MulAssign, Neg, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
    SubAssign,
};
use std::process::exit;
use std::{f32, f64, i128, i16, i32, i64, i8, isize, u128, u16, u32, u64, u8, usize};

// Dep' crates are...
use itertools::*;
use itertools_num::*;
use lazy_static::lazy_static;
use maplit::{btreemap, btreeset, hashmap, hashset};
use num_bigint::{BigInt, BigUint};
use num_complex::Complex;
use num_integer::{binomial, gcd, lcm, multinomial, Integer};
use num_rational::Rational;
use num_traits::{clamp, one, pow, zero, Num, NumAssignOps, NumOps, One, Pow, Zero};
use permutohedron::Heap;
use proconio::{
    fastout, input, is_stdin_empty,
    marker::{Bytes, Chars, Isize1, Usize1},
};
use rand::random;

pub const MOD10E9_7: usize = 1000000007;
pub const MOD99_: usize = 998244353;
pub const MAX: usize = std::usize::MAX;
pub const PI: f64 = f64::consts::PI;
pub const A: u8 = 65;

// code...
// #[fastout]
fn main() {
    input! {
        n: usize,
        mut f: [usize; n]
    }

    f.sort();

    let mut heap = BinaryHeap::new();
    heap.push(f.pop().unwrap());

    let mut ans = 0usize;

    for _ in 1..n {
        let p = f.pop().unwrap();
        ans += heap.pop().unwrap();
        heap.push(p);
        heap.push(p);
    }

    println!("{}", ans);
}



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

int main() {
  int n;
  long long d;
  int cnt = 0;
  std::cin >> n >> d;
  long long x, y;
  for (int i = 0; i < n; i++) {
    std::cin >> x >> y;
    if (x*x + y*y <= d*d)
      cnt++; 
  }

  std::cout << cnt;
  
}

Measured memory_bytes: 3640