akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;

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

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

int main() {
	int n, k; scanf("%d%d", &n, &k);
	std::string s; cin >> s;

	std::vector<std::pair<char, int>> vec;
	for(int i = 0; i < s.size(); i++) {
		if(vec.empty() or vec.back().first != s[i]) vec.push_back({s[i], 1});
		else vec.back().second++;
	}
	
	std::vector<int> ss(vec.size() + 1, 0);
	for(int i = 0; i < vec.size(); i++) ss[i + 1] = ss[i] + vec[i].second;
	
	int ans = 0;
	for(auto v: vec) if(v.first == '1') ans = std::max(ans, v.second);
	for(int i = 0; i < vec.size(); i++) {
		if(vec[i].first == '1') continue;
		
		int to = std::min((int)ss.size() - 1, i + 2 * (k - 1) + 2);
		int tmp = 0;
		if(i) tmp = vec[i - 1].second;
		
		ans = std::max(ans, ss[to] - ss[i] + tmp);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 1652
import java.util.Scanner;
import java.util.stream.IntStream;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int n = scanner.nextInt();
			long t = scanner.nextLong();
			long[] a = IntStream.range(0, n).mapToLong(i -> scanner.nextLong()).toArray();
			System.out.println(IntStream.range(1, n).mapToLong(i -> Math.min(a[i] - a[i - 1], t)).sum() + t);
		}
	}
}


Measured memory_bytes: 62212
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

const int INF = 1 << 30;

int main() {
	int N, Ma, Mb;
	cin >> N >> Ma >> Mb;
	vector<int> A(N), B(N), C(N);
	for (int i = 0; i < N; i++)
		cin >> A[i] >> B[i] >> C[i];
	
	vector<vector<vector<int>>> dp(N+1,
		vector<vector<int>>(10*N+1,
			vector<int>(10*N+1)));
	for (int i = 0; i < N+1; i++) {
		for (int j = 0; j < 10*N+1; j++) {
			for (int k = 0; k <10*N+1; k++) {
				dp[i][j][k] = INF;
			}
		}
	}

	dp[0][0][0] = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 10*N; j++) {
			for (int k = 0; k < 10*N; k++) {
				if (j+A[i] > 10*N || k+B[i] > 10*N) continue;
				dp[i+1][j+A[i]][k+B[i]] = min(dp[i+1][j+A[i]][k+B[i]], dp[i][j][k] + C[i]);
				dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
			}
		}
	}

	int ans = INF;
	for (int i = 1; i <= 10*N; i++) {
		if (Ma*i > 10*N || Mb*i > 10*N) break;
		ans = min(ans, dp[N][Ma*i][Mb*i]);
	}
	if (ans == INF) ans = -1;
	cout << ans << endl;
}


Measured memory_bytes: 27264
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

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

    string s[50];
    for (int i = 0; i < h; i++)
        cin >> s[i];

    int di[8] = {1, 1, 1, 0, -1, -1, -1, 0};
    int dj[8] = {-1, 0, 1, 1, 1, 0, -1, -1};

    for (int i = 0; i < h; i++) {
        for (int j = 0 ; j < w; j++) {
            int cnt = 0;
            if (s[i][j] == '#') {
                cout << "#";
                continue;
            }
            for (int k = 0; k < 8; k++) {
                if (i + di[k] < 0 or i + di[k] >= h or j + dj[k] < 0 or j + dj[k] > w ) continue;
                if (s[i + di[k]][j + dj[k]] == '#') cnt++;
            }
            cout << cnt;
        }
        cout << endl;
    }

    return 0;
}


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

typedef long long ll;
const ll INF = 1 << 30;
ll ch[32][32];
ll sum[3][32];

int main() {
	ll n, c;
	cin >> n >> c;
	for (ll i = 0; i < c; i++) {
		for (ll j = 0; j < c; j++) {
			ll now; cin >> now;
			ch[i][j] = now;
		}
	}
	for (ll i = 0; i < n; i++) {
		for (ll j = 0; j < n; j++) {
			ll now; cin >> now; now--;
			ll now1 = (i + j) % 3;
			sum[now1][now]++;
		}
	}

	ll ans = INF;
	for (ll i = 0; i < c; i++) {
		for (ll j = 0; j < c; j++) {
			for (ll k = 0; k < c; k++) {
				ll sum1 = 0;
				if (i == j || j == k || k == i) continue;
				
				for (ll l = 0; l < 3; l++) {
					for (ll m = 0; m <= c; m++) {
						if (l == 0) sum1 += sum[l][m] * ch[m][i];
						else if (l == 1) sum1 += sum[l][m] * ch[m][j];
						else sum1 += sum[l][m] * ch[m][k];
						
					}
				}
				ans = min(ans, sum1);
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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

int main(){
    int n,k;
    cin >> n >> k;
    vector<int> h(n);
    for(int i = 0;i < n;i++) cin >> h[i];
    sort(h.begin(),h.end());
    set<int> g;
    for(int i;i < n - k + 1;i++){
        g.insert(h[i + k - 1] - h[i]);
    }
    cout << *begin(g) << endl;
    return 0;
}

Measured memory_bytes: 4480
#include<stdio.h>
#include<stdlib.h>

#define nummax 100
#define arrmax 99
int top=0,S[1000];

void push(int);
int pop();

int main()
{
  int i,num,x,y;
  char moji[nummax];


  while(scanf("%s",moji)!= EOF )
    { 
	  if( moji[0] == '+' )
	    {
	     x = pop();
	     y = pop();
	     push(x+y);
	    }
	  else if( moji[0] == '-' )
	    {
	     x = pop();
	     y = pop();
	     push(y-x);
	    }
	  else if( moji[0] == '*')
	    {
	     x = pop();
	     y = pop();
	     push(x*y);
	    } 
	  else
	    {
	      num = atoi(moji);
	      push(num);
	    }
    }  
  printf("%d\n",pop());

  return 0;
}

void push(int x)
{
  top++;
  S[top] = x;
}

int pop(void)
{
  top--; 
  return S[top+1];
}

Measured memory_bytes: 548
#include<bits/stdc++.h>
using namespace std;
int n,q;
int a[5][5];
bool k[5][5],ans;
int main() {
	for(int i=1;i<=3;i++) 
		for(int j=1;j<=3;j++) scanf("%d",&a[i][j]);
	cin>>n;
	while(n--) {
		cin>>q;
		for(int i=1;i<=3;i++)
			for(int j=1;j<=3;j++) if(a[i][j]==q) k[i][j]=1;
	}
	for(int i=1;i<=3;i++) if(k[i][1]&&k[i][2]&&k[i][3]) ans=1;
	for(int i=1;i<=3;i++) if(k[1][i]&&k[2][i]&&k[3][i]) ans=1;
	if(k[1][1]&&k[2][2]&&k[3][3]) ans=1;
	if(k[1][3]&&k[2][2]&&k[3][1]) ans=1;
	if(ans) cout<<"Yes";
	else cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}


class UnionFind{
  vector<int> par,siz;
  //0-indexed
  void init(int n){
    component = n;
    par.resize(n);
    for(int i=0;i<n;++i)par[i]=i;
    siz.resize(n,1);
    msiz = 1;
  }
public:
  int msiz,component;
  UnionFind(int n_){init(n_);}
  int root(int x){
    if(par[x]==x)return x;
    return par[x] = root(par[x]);
  }
  void unite(int x,int y){
    x = root(x);
    y = root(y);
    if(x==y)return;
    siz[y] += siz[x];
    siz[x] = 0;
    par[x] = y;
    msiz = max(msiz,siz[y]);
    component--;
  }
  int size(int x){
    return siz[root(x)];
  }
  bool same(int x,int y){
    return root(x)==root(y);
  }
};


int main(){

  ll N,M;
  cin >> N >> M;

  UnionFind uf(N+1);

  FOR(i,0,M){
    ll a,b;
    cin >> a >> b;
    uf.unite(a,b);
  }

  cout << uf.msiz << endl;


}



Measured memory_bytes: 4736
#include <iostream>
#include<vector>
#include<queue>
#include<bits/stdc++.h>
#define ll long long
using namespace std;
//void dfs(vector<ll> &vt,vector<ll> &pt,vector<vector<ll>>&v,ll i)
//{
    
//}
int main(){
    ll n,m;
    cin>>n>>m;
    vector<vector<ll> >v(n+1);
    for(ll i=0;i<m;i++)
    {
        ll t,k;
        cin>>t>>k;
        v[t].push_back(k);
        v[k].push_back(t);
    }
    vector<ll>vt(n+1,0);
    vector<ll>pt(n+1,0);
    vector<ll>lt(n+1,INT_MAX);
    lt[1]=0;
    //dfs(vt,pt,v,1);
    queue<ll>q;
    q.push(1);
    
    while(!q.empty())
    {
        ll top=q.front();
        q.pop();
        if(vt[top]==0)
        {
            vt[top]=1;
            for(ll j=0;j<v[top].size();j++)
            {
                ll p=v[top][j];
                if(vt[p]==0)
                {
                    q.push(p);
                    if(lt[p]>lt[top]+1)
                    {
                        lt[p]=lt[top]+1;
                         pt[p]=top;
                    }
                }
            }
        }
    }
    for(ll i=1;i<=n;i++)
    {
        if(vt[i]==0)
        {
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
    for(ll i=2;i<=n;i++)
      cout<<pt[i]<<endl;
    
     return 0;
}


Measured memory_bytes: 14724
//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)


int main(){
	fast;
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	if(b>0 && d>0)
		cout<<max(a*c,b*d);
	else{
		if(b<=0){ 
			if(c<0)
				cout<<a*c;
			else
				cout<<b*c;
		}
		else if(d<=0){
			if(a<0)
				cout<<a*c;
			else
				cout<<a*d;
		}

	}
}





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

int main() {
	ios_base::sync_with_stdio( false );

	int N;
	cin >> N;

	int64_t t = 1;
	int64_t a = 1;

	for( int i = 0; i < N; ++i ) {
		int T, A;
		cin >> T >> A;

		int64_t n = max( (t + T-1) / T, (a + A-1) / A );
		t = n * T;
		a = n * A;
	}

	cout << (t+a) << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int W,H,x,y,r;
    cin>>W>>H>>x>>y>>r;
    if((x-r>=0)&&(y-r>=0)&&(x+r)<=W&&(y+r)<=H) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


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

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back

void solve() {
  vector<int> w, k;
  rep(i,10) {
    int t; cin>>t;
    w.pb(t);
  }
  rep(i,10) {
    int t; cin>>t;
    k.pb(t);
  }
  sort(w.begin(), w.end(), greater<int>());
  sort(k.begin(), k.end(), greater<int>());
  int sw = 0, sk = 0;
  rep(i,3) {
    sw += w[i]; sk += k[i];
  }
  cout<<sw<<" "<<sk<<endl;
}

int main (int argc, char const* argv[]) {
  solve();
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>


#define fs first
#define sc second

using namespace std;


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


int main(){
    int n;
    cin >> n;
    ll b[1010];
    for(int i = 0; i < n-1; i++){
        cin >> b[i];
    }

    ll res = b[0];
    for(int i = 1; i < n-1; i++){
        res += min(b[i], b[i-1]);
    }
    res += b[n-2];

    cout << res << endl;


    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cctype>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#define LL long long
#define ULL unsigned  long long
#define maxn (LL)1e5
#define INF 0x3f3f3f3f
#define inf 0x7fffffff
#define PI  acos(-1.0)
#define pb push_back
#define re register LL
const double eps = 0.0000001;
using namespace std;
typedef pair<LL,LL> pii;
inline LL sgn(double x)
{
    return (x > eps) - (x < -eps);
}
const LL N=1e6+2;
const LL mod=1e9+7;
int f[2010];
LL mul(LL a,LL b,LL mod)
{
    LL ans=0;
    for(;b;b>>=1)
    {
        if(b&1)
        {
            ans=ans+a%mod;
        }
        a=a*2%mod;
    }
    return ans%mod;
}
int main()
{
   int n;
   LL k;
   cin>>n>>k;
   for(int i=1;i<=n;i++)
       cin>>f[i];
   int num1=0;
   for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
           if(f[i]>f[j]) num1++;
   int num=0;
   for(int i=1;i+1<=n;i++)
       for(int j=i+1;j<=n;j++)
       if(f[j]<f[i]) num++;
   cout<<(LL)(mul((LL)num,k,mod)+mul((LL)k*(k-1)/2,(LL)num1,mod))%mod;
}



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

using namespace std;

int main() {
  string s; cin >> s;
  int cnt_1 = 0, cnt_2 = 0;
  for(int i = 0; i < s.size(); i += 2) if(s[i] != '0') cnt_1++;
  for(int i = 1; i < s.size(); i += 2) if(s[i] != '1') cnt_1++;
  for(int i = 0; i < s.size(); i += 2) if(s[i] != '1') cnt_2++;
  for(int i = 1; i < s.size(); i += 2) if(s[i] != '0') cnt_2++;
  if(cnt_1 < cnt_2) cout << cnt_1 << endl;
  else cout << cnt_2 << endl;
  return 0;
}

Measured memory_bytes: 512
n,m=map(int, input().split())
p=[1]*(n+1)
c=[]
for i in range(m):
  pi,x =map(int, input().split())
  c.append([i+1, pi, x, 0])
  #p[pi].append(x)
#for i in range(n):
# p[i]=sorted(p[i])
x_order = sorted(c, key=lambda e: e[2])
for e in x_order:
  e[3] = p[e[1]]
  p[e[1]] += 1

i_order = sorted(x_order)

for e in i_order:
  id=e[1]*1000000+e[3]
  print(str(id).zfill(12))


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

bool judge(int x){
    if(x == 2)return true;
    if(x <= 1 || x%2 == 0)return false;

    for (int i = 3; i*i <= x; i+=2){
        if(x%i == 0)return false;
    }

    return true;
}

int main() {
    int n; cin >> n;
    int ans = 0;
    rep(i, n){
        int x; cin >> x;
        if(judge(x)){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3084
#include<cstdio>
#include<utility>
#include<algorithm>
using namespace std;
using ll = long long;

int main(){
	int N;
	scanf("%d", &N);
	pair<int, int> P[N + 1];
	int A[N + 1];
	for (int i = 1; i <= N; ++i){
		scanf("%d", A + i);
		P[i] = make_pair(i - A[i], i);
	}
	sort(P+1, P+N+1);
	ll ans = 0;
	for (int i = 1; i < N; ++i){
		int right = distance(P, upper_bound(P+1, P+N+1, make_pair(i + A[i], N)));
		int left = distance(P, lower_bound(P+1, P+N+1, make_pair(i + A[i], i + 1)));
		ans += right - left;
	}
	printf("%lld\n", ans);
	return 0;
}

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

bool compare(pair<long long,long long> a,pair<long long,long long> b){
  return a.first<b.first;
}
int main(){
  int N;
  long long K;
  pair<long long,long long> arr[100000];
  cin>>N>>K;
  for(int i=0;i<N;i++){
    long long a,b;
    cin>>a>>b;
    arr[i].first=a;
    arr[i].second=b;
  }
  sort(arr,arr+N,compare);
  for(int i=0;i<N;i++){
    if(K<=arr[i].second) {
      printf("%lld",arr[i].first);
      break;
    }
    else K-=arr[i].second;
  }
}


Measured memory_bytes: 1792
buf[20000];char*p=buf;
W,w;
main(){
	read(0,buf,10200);
	while(*p>32)p+=1;
	for(p+=1;*p>10;p+=1)w=w*10+*p-48;W=w+=1;
	for(;w;w-=1)putchar_unlocked('#');
	for(;*p>0;p+=1){
		if(*p==10)putchar_unlocked('#'),putchar_unlocked(10),putchar_unlocked('#');
		else putchar_unlocked(*p);
	}
	for(;W;W-=1)putchar_unlocked('#');
}

Measured memory_bytes: 128
#![allow(unused_imports)]
use std::io::{ self, Write };
use std::str::FromStr;
use std::cmp::{ min, max };
use std::collections::{ BinaryHeap, VecDeque };

#[allow(unused_macros)]
macro_rules! trace {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($var), $var);
    };
    ($($args:expr),*) => {
        let _ = writeln!(&mut std::io::stderr(), ">>> {} = {:?}", stringify!($($args),*), ($($args),*));
    };
}

#[allow(unused_macros)]
macro_rules! put {
    ($var:expr) => {
        let _ = writeln!(&mut std::io::stdout(), "{}", $var);
    };
    ($var:expr, $($args:expr),*) => {
        let _ = write!(&mut std::io::stdout(), "{} ", $var);
        put!($($args),*);
    };
}

const M: usize = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let mut cs = vec![0; n];
    {
        let mut m = 0;
        let mut last = 0;
        for _ in 0..n {
            let c: usize = sc.cin();
            if c != last {
                last = c;
                cs[m] = c;
                m += 1;
            }
        }
        while cs.len() > m {
            cs.pop();
        }
    }

    // trivial case
    {
        let mut count = vec![0; 200002];
        let mut uniq = true;
        for &c in cs.iter() {
            count[c] += 1;
            if count[c] > 1 {
                uniq = false;
                break;
            }
        }
        if uniq {
            put!(1);
            return;
        }
    }

    // trace!(cs);
    let mut f = vec![0; cs.len() + 1];
    f[0] = 1;
    // f[i] = f(0..i)
    let mut e = vec![0; cs.iter().max().unwrap() + 2];
    // e[i] = sum f(0..k-1) where cs[k] == i
    for i in 1 .. cs.len() + 1 {
        let alphabet = cs[i-1];
        f[i] = e[alphabet] + f[i-1];
        e[alphabet] += f[i-1];
        f[i] %= M;
        e[alphabet] %= M;
        // println!("ends with {} is {}", alphabet, e[alphabet]);
        // trace!(f);
        // trace!(e);
    }
    // trace!(f);
    // trace!(e);
    put!(f[f.len() - 1]);
}

#[allow(dead_code)]
struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn reserve(&mut self) {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
    }
    fn cin<T: FromStr>(&mut self) -> T {
        self.reserve();
        match self.buffer.pop_front().unwrap().parse::<T>() {
            Ok(a) => a,
            Err(_) => panic!("parse err")
        }
    }
}


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

typedef long long ll;
using namespace std;

int main(){
 int N,M; cin >> N >> M;
  vector<int> X(M); for(int i = 0; i < M; i++){ cin >> X[i];}
  sort(X.begin(),X.end());
  if( N >= M){ cout << 0 << endl;} //needs to be ended
  else{
    vector<ll> dist( M - 1);
    for(int i = 0; i < M - 1; i++){
      dist[i] = X[i+1] - X[i];}
    sort(dist.begin(),dist.end());int sum = 0;
    
    for(int i = 0; i < M - N; i++){
      sum += dist[i];}
    
    cout << sum << endl;}
  
  return 0;}
      


Measured memory_bytes: 1408
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE BinaryLiterals #-}
{-# LANGUAGE MultiWayIf #-}
{-# LANGUAGE NumDecimals #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE TupleSections #-}

import Control.Applicative
import Control.Arrow
import Control.Monad
import Control.Monad.ST

import Data.Char
import Data.List
import Data.Maybe

import qualified Data.ByteString.Char8 as B

import Data.Array.ST.Safe
import Data.STRef

import Debug.Trace
import Text.Printf

readInt = readLn :: IO Int
readInteger = readLn :: IO Integer
readInts = map ( fst . fromJust . B.readInt ) . B.words <$> B.getLine
readIntegers = map ( fst . fromJust . B.readInteger ) . B.words <$> B.getLine

which a b f = if f then a else b
mp [ a, b ] = ( a, b )

modifyArray a i f = writeArray a i =<< f <$> readArray a i

main = ( readLn :: IO Double ) >>= printf "%.5f\n" . ( * 3.1415 ) . ( * 2 )

Measured memory_bytes: 3988
import java.io.*;

public class Main {

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

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        String o = reader.readLine();
        String e = reader.readLine();

        char[] oc = o.toCharArray();
        char[] ec = e.toCharArray();


        boolean isO = oc.length > ec.length;


        PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));

        for (int i = 0; i < ec.length; i++) {
            writer.print(oc[i]);
            writer.print(ec[i]);
        }

        if (isO) writer.print(oc[oc.length-1]);

        writer.close();

    }
}


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

using namespace std;

int n;

int main()
{
    int sum = 0;
    cin >> n;
    if(n == 0){
        for(int i = n; i <= 1; i ++){
            sum = sum + i;
        }
        cout << sum;
        return 0;
    }for(int i = 1; i <= n; i ++){
            sum = sum + i;
    }
    cout << sum;
    return 0;
}

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

long long N, M;
map<long long, long long> have;

int main(){
	cin >> N;
	for(long long i = 0; i < N; i++){
		long long tmp;
		cin >> tmp;
		have[tmp]++;
	}

	cin >> M;
	for(long long i = 0; i < M; i++){
		long long tmp;
		cin >> tmp;
		if(have[tmp] > 0){
			have[tmp]--;
		}else{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}


Measured memory_bytes: 12800
#include <stdio.h>

int main(void) {
	int a, b, c, i, n, tmp;
	scanf ("%d", &n);
	while (n!=0){
		scanf ("%d %d %d", &a, &b, &c);
		if (a<b) {
			tmp = a;
			a = b;
			b = tmp;
		}
		if (b<c) {
			tmp = b;
			b = c;
			c = tmp;
		}
		if (a<b) {
			tmp = a;
			a = b;
			b = tmp;
		}
		if (a*a == b*b + c*c) {
			printf ("YES\n");
		} else {
			printf ("NO\n");
		}
		n--;
	}
	return 0;
}

Measured memory_bytes: 0
#include<stdio.h>
#include<stdlib.h>
int main(void){
    int a,b,c;
    int tmp;

    scanf("%d %d %d", &a, &b, &c);
    if(a > b){
        tmp = a;
        a = b;
        b=tmp;
    } 
    
    if(b > c){
        tmp = b;
        b = c;
        c = tmp;
    }

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

    printf("%d %d %d\n", a,b,c);
    return 0; 
}


Measured memory_bytes: 2128
fun main(args: Array<String>) {
    val N = readLine()!!.toLong()

    if (N == 0L) {
        println(0)
        return
    }

    val sb = StringBuilder()
    var r = N
    var k = 0
    if (N > 0) {
    } else {
        r = -N
        k = 1
    }

    while (r > 0) {
        if (r and 1L == 1L) {
            sb.append(1)
            if (k % 2 == 0) {
                r--
            } else {
                r++
            }
        } else {
            sb.append(0)
        }
        k++
        r /= 2
    }

    println(sb.reverse().toString())
}


Measured memory_bytes: 31620
from fractions import gcd
from bisect import insort

N,x = map(int, input().split())
X = list(map(int, input().split()))


X.sort()
insort(X, x)
diff = []
for a,b in zip(X, X[1:]):
    diff.append(b - a)

ans = diff[0]
for num in diff[1:]:
    ans = gcd(ans, num)

print(ans)


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

using namespace std;

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

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

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

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

const ll MOD=1000000007ll;
// const ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	// cout<<setprecision(10)<<fixed;
	int n;
	ll a[334][334];
	cin>>n;
	REP(i, n){
		REP(j, n){
			cin>>a[i][j];
		}
	}
	ll ans=0;
	REP(i, n){
		FOR(j, i+1, n){
			ll mi=1e18;
			REP(k, n){
				if(k==i || k==j){
					continue;
				}
				CHMIN(mi, a[i][k]+a[k][j]);
			}
			if(mi<a[i][j]){
				cout<<-1<<'\n';
				return 0;
			}
			if(mi>a[i][j]){
				ans+=a[i][j];
			}
		}
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<fstream>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<math.h>

#define FIO ios_base::sync_with_stdio(0);  cin.tie(0);
#define PI 3.14159265358979323846
#define mod 1000000007
#define ll long long
#define vll vector<long long>  

#define all(c) c.begin(), c.end()

// Used to traverse in any STL container with iterators
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

// Find whether element is present in given container or not
#define present(container, element) (container.find(element) != container.end())

// Finds whether element in present container is present in vector or not
#define cpresent(container, element) (find(all(container),element) != container.end())

using namespace std;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    FIO
    
    int n;
    cin>>n;
    int arr[n][3];
    for(int i=0;i<n;i++){
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }

    int dp[n][3];
    dp[0][0] = arr[0][0];
    dp[0][1] = arr[0][1];
    dp[0][2] = arr[0][2];
    for(int i=1;i<n;i++){
        dp[i][0] = max(dp[i-1][1], dp[i-1][2]) + arr[i][0];
        dp[i][1] = max(dp[i-1][0], dp[i-1][2]) + arr[i][1];
        dp[i][2] = max(dp[i-1][1], dp[i-1][0]) + arr[i][2];
    }
    cout<< max(max(dp[n-1][0], dp[n-1][1]), dp[n-1][2])<<endl;

    
}

Measured memory_bytes: 5508
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*

fun main(args: Array<String>) {
    val sc = FastScanner(System.`in`)

    val h = sc.nextInt()
    val n = sc.nextInt()
    val s = Array(n) { Spell(sc.nextInt(), sc.nextInt()) }
    val inf = 1e9.toInt()

    val dp = Array(h + 1) { inf }
    dp[h] = 0

    for (i in h downTo 0) {
        for (x in 0 until n) {
            val next = if (i - s[x].damage > 0) (i - s[x].damage) else 0 
            dp[next] = if (dp[next] < dp[i] + s[x].cost) dp[next] else dp[i] + s[x].cost 
        }
    }

    println(dp[0])
}

data class Spell(val damage: Int, val cost: Int)

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

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

        return st.nextToken()
    }

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

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<long long> num(K, 0);
  // num[x] = K で割って余る数が1以上N以下に何個あるか
  for (int i = 1; i <= N; i++) num[i % K]++;
  long long ans = 0;
  rep(a, K) {
    int b = (K - a) % K;
    int c = (K - a) % K;
    if ((b + c) % K != 0) continue;
    ans += num[a] * num[b] * num[c];
  }
  cout << ans << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll minn=1e18+7;
const int maxn=1e5+7;
ll s[maxn];
int main(){
    ll n,a,b,i;
    ll sum=0;
    cin>>n>>a>>b;
    for(i=1;i<=n;i++){
        cin>>s[i];
    }
    for(i=2;i<=n;i++){
        sum+=min((s[i]-s[i-1])*a,b);
    }
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
 
using namespace std;

typedef long long ll;
typedef long double ld;
 
#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int, int>
#define Point Vect
#define no {cout << "No\n"; return;}

const int N = 1e5 + 7;

int a[N];

 void solve() {
    int x, k;
    cin >> x >> k;
    cout << min(x % k, k - x % k);
 }

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
int vis[15];
bool check(int num)
{
    while(num)
    {
        if(vis[num%10]) return 0;
        num/=10;
    }
    return 1;
}
int main()
{
    int n,k,d;
    scanf("%d%d",&n,&k);
    for(int i = 1;i<=k;++i)
        scanf("%d",&d),vis[d] = 1;
    for(int i = n;i<=100000000;i++)
    {
        if(check(i))
        {
            printf("%d\n",i);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
using namespace std;

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

typedef long long ll;


ll N, M;
ll ans;

int main() {
  cin >> N >> M;

  ll t = 1900*M + 100*(N-M);
  ll pw = 1;
  REP(i, M) { pw *= 2; }
  ans = t*pw;

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){int n;long long s=0;long h=0;cin>>n;vector<long>a(n);
           for(int i=0;i<n;i++){cin>>a.at(i);if(h>a.at(i))s+=(h-a.at(i));else h=a.at(i);}
cout<<s<<endl;}

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

#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,n) FOR(i,0,n)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using mii = map<int, int>;
using msi = map<string, int>;
using pii = pair<int, int>;

struct Edge {
    int to;     // 辺の行き先
    int weight; // 辺の重み
    Edge(int t, int w) : to(t), weight(w) { }
};
using Graph = vector<vector<Edge>>;

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

int d[20][20];

int main()
{
    ios::sync_with_stdio(false);
    int H,W;
    cin >> H >> W;
    string s[20];
    REP(i, H) cin >> s[i];

    int ans = 0;

    REP(sy, H) REP(sx, W) REP(gy, H) REP(gx, W) {
        REP(i, H) REP(j, W) d[i][j] = 1e9;
        queue<pii> que;
        que.push(pii(sy, sx));
        d[sy][sx] = 0;
        if(s[sy][sx] == '#' || s[gy][gx] == '#') continue;

        while(!que.empty()) {
            pii v = que.front();
            que.pop();
            if(v.first == gy && v.second == gx) break;
            REP(i, 4) {
                int y = v.first + dy[i], x = v.second + dx[i];
                if(y >= 0 && y < H && x >= 0 && x < W && s[y][x] != '#' && d[y][x] == 1e9) {
                    d[y][x] = d[v.first][v.second] + 1;
                    que.push(pii(y, x));
                }
            }
        }
        ans = max(ans, d[gy][gx]);
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <vector>
using namespace std;

bool isPali(const string &s) {
  for(int i = 0; i < s.size()-1-i; ++i) {
    if(s[i] != s[s.size()-1-i]) return false;
  }
  return true;
}

string toString(const int &i) {
  char buff[128];
  sprintf(buff, "%d", i);
  return string(buff);
}

int main() {
  vector<int> pari;
  for(int i = 1; ; ++i) {
    if(isPali(toString(i))) {
      pari.push_back(i);
      if(i >= 10000) break;
    }
  }
  int n;
  cin >> n;
  int ans = -1;
  for(int i = 0; i < pari.size(); ++i) {
    if(ans == -1 || abs(n-pari[i]) < abs(n-ans)) {
      ans = pari[i];
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1264
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> pairs;

#define MOD 998244353


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

bool primeNumber(ll n){
    if(n < 2) return false;
    else{
        for(ll i = 2; i * i <= n; i++){
            if(n % i == 0) return false;
        }
        return true;
    }
}



 
int main(){
    string s;
    cin>>s;
    ll q;
    cin>>q;
    string t;
    for(ll qi = 0; qi<q; qi++){
        ll ty;
        cin>>ty;
        if(ty == 1){
            swap(s,t);
        }else{
            ll f;char c;
            cin>>f>>c;
            if(f == 1){
                t += c;
            }else{
                s += c;
            }
        }
    }
    reverse(t.begin(),t.end());
    t += s;
    cout<<t<<endl;
    return 0;
}
 
    
    



Measured memory_bytes: 1128
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;
import java.util.concurrent.CountDownLatch;

public class Main {
	public static char[][] maze;
	public final static int INF = 1000000;
	public final static int[] dx = { 0, 1, 0, -1 };
	public final static int[] dy = { 1, 0, -1, 0 };
	public static int gx;
	public static int gy;
	public static int h, w, n;
	public static int[][] d;
	public static Pair pair = null;
	public static int ans = 0;

	public static void main(String[] args) {
		read();
		for (int i = 1; i <= n; i++) {
			ans += bfs(i);
		}
		System.out.println(ans);
	}

	public static int bfs(int count) {
		init(count);

		Queue<Pair> queue = new ArrayDeque<Pair>();
		queue.add(pair);

		while (!queue.isEmpty()) {
			Pair p = queue.poll();
			// if goal
			if (p.i == gx && p.j == gy) {
				return d[p.i][p.j];
			}
			// move
			for (int k = 0; k < 4; k++) {

				int nx = p.i + dx[k];
				int ny = p.j + dy[k];

				// check it is enable to move
				if (0 <= nx && nx < h && 0 <= ny && ny < w) {
					if (maze[nx][ny] != 'X' && d[nx][ny] == INF) {
						// add distance +1
						queue.add(new Pair(nx, ny));
						d[nx][ny] = d[p.i][p.j] + 1;
					}
				}
			}

		}
		return 0;
	}

	public static void init(int goal) {
		String start = String.valueOf(goal - 1);
		if (goal == 1) {
			start = "S";
		}
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				d[i][j] = INF;
				// search "start"
				if (String.valueOf(maze[i][j]).equals(start)) {
					pair = new Pair(i, j);
					// start of distance = 0
					d[i][j] = 0;
				}

				// search "goal"
				if (String.valueOf(maze[i][j]).equals(String.valueOf(goal))) {
					gx = i;
					gy = j;
				}

			}
		}

	}

	public static void read() {
		Scanner s = new Scanner(System.in);
		h = s.nextInt();
		w = s.nextInt();
		n = s.nextInt();
		d = new int[h][w];
		maze = new char[h][w];
		for (int i = 0; i < h; i++) {
			maze[i] = s.next().toCharArray();
		}

	}
}

class Pair {
	int i, j;

	public Pair(int i, int j) {
		this.i = i;
		this.j = j;
	}

}

Measured memory_bytes: 298440
#include <iostream>

void leapYear(int, int);
int main()
{
  int check1 = 0;
    while (true) {
        int a, b;
        std::cin >> a >> b;
        if (a == 0 && b == 0) {
            break;
        }
        if (check1 == 1) {
            std::cout << std::endl;
        }
        check1 = 1;
        leapYear(a, b);
    }
    return 0;
}
void leapYear(int a, int b)
{
    int check2 = 0;
    for (int year = a; year <= b; ++year) {
      if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0) {
            std::cout << year <<std::endl;
            check2 = 1;
      }
    }
    if (check2 == 0) {
        std::cout << "NA" <<std::endl;
    }
}

Measured memory_bytes: 1164
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<math.h>
using namespace std;
const double Pi=3.1415926;
int n,m,k;
int main()
{
	double r;
	cin >> r;
	cout <<2*r*Pi<<endl;
}

Measured memory_bytes: 3776
#include <iostream>

int main(){
   std::string S, T;
   std::cin >> S >> T;

   int count = 0;
   for(int i=0; i<S.size(); ++i){
      bool flag = true;
      for(int j=0; j<T.size(); ++j){
	 int index = i + j;
	 if(index>S.size()-1) index -= S.size();
	 if(S[index]!=T[j]) flag = false;
      }
      if(flag) ++count;
   }

   if(count>0) std::cout << "Yes" << std::endl;
   else std::cout << "No" << std::endl;
}


Measured memory_bytes: 256
from collections import defaultdict
from itertools import product, groupby
from math import pi
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10


def main():
    n, m = map(int, input().split())
    print((n - 1) * (m - 1))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
N = int(input())
A = [int(input()) for _ in range(N)]
if 2 not in A:
    print(-1)
    exit()
now = 1
count = 0
past = []
while True:
    if now == 2:
        print(count)
        exit()
    if count >= N:
        print(-1)
        exit()
    count += 1
    now = A[now - 1] 

Measured memory_bytes: 7084
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); i++) 
#define all(v) begin(v),end(v)
using ll = long long;

int main() {
  int a,b,m;cin>>a>>b>>m;
  vector<int> A(a),B(b);
  int aa=1e9,bb=1e9;
  rep(i,a){
    cin>>A[i];
    aa=min(aa,A[i]);
  }
  rep(i,b){
    cin>>B[i];
    bb=min(bb,B[i]);
  }
  int cnt1=aa+bb;
  rep(i,m){
    int x,y,c;cin>>x>>y>>c;
    x--;y--;
    int cnt2=A[x]+B[y]-c;
    cnt1=min(cnt1,cnt2);
  }
  cout<<cnt1<<endl;
}

Measured memory_bytes: 4032
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
  long long X, K, D;
  cin >> X >> K >> D;
  long long rep = abs(X) / D;
  if (rep >= K) {
    cout << abs(X) - D*K << endl;
    return 0;
  }
  X = abs(X) - D*rep;
  K -= rep;
  if ((K%2)==1) {
    cout << abs(X-D) << endl;
    return 0;
  } else {
    cout << X << endl;
    return 0;
  }
}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>

using namespace std;

int main(){
    int N;
    cin >> N;
    vector<int> V(N);
    vector <int> C(N);
    for(int i = 0; i < N; i++){
        cin >> V[i];
    }
    for(int i = 0; i < N; i++){
        cin >> C[i];
    }
    int sum = 0;
    for(int i = 0; i < N; i++){
        if (V[i] - C[i] > 0) {
            sum += V[i] - C[i];
        }
    }
    
    cout << sum << endl;
    

    return 0;
}

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

#define REP(i,n) for(int i=0; i < (n); ++i)
#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)

using ll = long long;
#define INF 1e9


struct UnionFind{
  vector<int> parent, rank;
  vector<ll> graph_size;
  UnionFind(int size){
    parent = vector<int>(size);
    rank = vector<int>(size, 1);
    graph_size = vector<ll>(size, 1);
    REP(i, size){
      parent[i] = i;
    }
  }

  void Union(int x, int y){
    int xRoot = find(x);
    int yRoot = find(y);
    if(rank[xRoot] > rank[yRoot]){
      parent[yRoot] = xRoot;
      graph_size[xRoot] += graph_size[yRoot];
    }
    else if(rank[xRoot] < rank[yRoot]){
      parent[xRoot] = yRoot;
      graph_size[yRoot] += graph_size[xRoot];
    }
    else{
      parent[yRoot] = xRoot;
      rank[xRoot]++;
      graph_size[xRoot] += graph_size[yRoot];
    }
  }

  int find(int x){
    if( x != parent[x]){
      return find(parent[x]);
    }
    return x;
  }
  int get_size(int x){
    return graph_size[find(x)];
  }
  bool same(int x, int y){
    return find(x) == find(y);
  }
};


int main(){ 
  int N, M;
  cin >> N >> M;
  vector<int> A(M), B(M);
  REP(i, M){
    cin >> A[i] >> B[i];
    A[i]--, B[i]--;
  }
  UnionFind uf(N);
  ll cost = (ll)N *(N-1) / 2;
  vector<ll> ans(M);
  REPR(i, M-1){
    ans[i] = cost;
    int aRoot = uf.find(A[i]), bRoot = uf.find(B[i]);
    if(aRoot == bRoot){
      continue;
    }
    else{
      cost -= uf.graph_size[aRoot] * uf.graph_size[bRoot];
      uf.Union(aRoot, bRoot);
    }
  }
  REP(i, M){
    cout << ans[i] << endl;
  }


  return 0;
}



Measured memory_bytes: 4480
// https://atcoder.jp/contests/abc131/tasks/abc131_b

#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define REP(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define REPR(i, n) for (int(i) = (n); (i) >= 0; (i)--)
#define FOR(i, m, n) for (int(i) = (m); (i) < (n); i++)
#define FORR(i, m, n) for (int(i) = (n); (i) >= (m); i--)
#define rep(...) _overload3(__VA_ARGS__, FOR, REP, )(__VA_ARGS__)
#define repr(...) _overload3(__VA_ARGS__, FORR, REPR, )(__VA_ARGS__)
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
#define INF 1e9
#define ALL(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

int main()
{
  int N, L, score, minS = INF, sum = 0;
  cin >> N >> L;
  rep(i, 1, N + 1)
  {
    score = L + i - 1;
    sum += score;
    if (abs(score) < abs(minS))
      minS = score;
  }

  cout << sum - minS << '\n';

  return 0;
}


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

int recFrog2(int arr[], int n, int i, int k, int mem[]) {

	if (i == n - 1)
		return 0;
	if (i >= n)
		return INT_MAX;
	if (mem[i] != -1)
		return mem[i];
	int count = INT_MAX;
	for (int jump = 1; jump <= k; jump++) {
		if (i + jump < n)
			count = min(count, abs(arr[i + jump] - arr[i]) + recFrog2(arr, n, i + jump, k, mem));
	}

	return mem[i] = count;

}


int main() {
	int n, k;
	cin >> n >> k;
	int arr[100005];

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	int mem[100005];
	memset(mem, -1, sizeof mem);

	cout << recFrog2(arr, n, 0, k, mem);



	return 0;
}

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

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

    
    int n;
    cin >> n;
    
    cout << n * n * n << endl;

    return 0;
}

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

ll MOD = 1e9 + 7;

int main() {
  int N, M;
  cin >> N >> M;
  if (abs(N - M) >= 2) {
    cout << 0 << endl;
    return 0;
  }
  ll ans = (N - M == 0 ? 2 : 1);
  for (ll i = 1; i <= N; i++) ans = ans * i % MOD;
  for (ll i = 1; i <= M; i++) ans = ans * i % MOD;
  cout << ans % MOD << endl;
}

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

int main(){
  int n,m,ans;
  int a[10010],b[10010];

  cin >> n >> m;
  for(int i=0;i<n;i++)cin >> a[i] >> b[i];

  ans = m;
  if(m<0){
    cout << 0 << endl;
    return 0;
  }

  for(int i=0;i<n;i++){
    m += a[i] - b[i];
    if(m<0){
      cout << 0 << endl;
      return 0;
    }
    ans = std::max(ans,m);
  }
  cout << ans << endl;
}

Measured memory_bytes: 1236
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef vector<pii> VP;
typedef vector<string> VS;
typedef priority_queue<int> PQ;
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; }
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//priority_queue<int,vector<int>, greater<int> > q2;

vector<VI>G;
VI A;
int N;
VI ans, dp;

void dfs(int now, int pa) {

	int tmp = *LB(dp, A[now]);
	*LB(dp, A[now]) = A[now];
	ans[now] = LB(dp, INF) - dp.begin();
	
	fore(to, G[now]) {
		if (to != pa)dfs(to, now);
	}
	*LB(dp, A[now]) = tmp;
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	G.resize(N);
	A.resize(N);
	ans.resize(N);
	dp.resize(N + 10,INF);

	REP(i, N)cin >> A[i];
	REP(i, N - 1) {
		int a, b; cin >> a >> b;
		a--; b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	dfs(0, -1);



	REP(i, N)cout << ans[i] << '\n';
	return 0;
}



Measured memory_bytes: 30276
n = gets.to_i
nums = gets.split.map(&:to_i)
maximum = nums.max
minimum = nums.min
answers = []
if maximum.abs > minimum.abs
  (0..n - 2).each do |index|
    while nums[index] > nums[index + 1]
      max_index = nums.index(nums.max)
      nums[index + 1] += nums[max_index]
      answers << [max_index + 1, index + 2]
    end
  end
else
  (n - 1).downto(1) do |index|
    while nums[index - 1] > nums[index]
      min_index = nums.index(nums.min)
      nums[index - 1] += nums[min_index]
      answers << [min_index + 1, index]
    end
  end
end

puts answers.size
answers.each { |answer| puts answer.join(" ") }


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

int main() {
	int n; scanf("%d", &n);
	
	std::vector<int> a(1 + n, 0);
	
	for (int i = 0; i < n - 1; i++) {
		int t; scanf("%d", &t);
		a[t]++;
	}
	
	for (int i = 1; i <= n; i++) {
		printf("%d\n", a[i]);
	}
	
	return 0;
}


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

template <class t>
using vc = vector<t>;
template <class t>
using vvc = vector<vector<t>>;
typedef long long ll;
typedef vc<int> vi;
typedef vvc<int> vvi;
typedef pair<int, int> pi;

#define uset unordered_set
#define umap unordered_map

#define endl "\n"

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define bg begin()
#define ed end()

#define all(a) a.bg, a.ed

template <class t, class u>
ostream &operator<<(ostream &os, const pair<t, u> &p) {
    return os << "( " << p.first << ", " << p.second << " )";
}

template <class t>
ostream &operator<<(ostream &os, const vc<t> &v) {
    os << "[ ";
    for (int i = 0; i < v.size(); i++) {
        os << v[i];
        if (i != v.size() - 1) {
            os << ", ";
        }
    }
    return os << " ]";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    // cout << fixed << setprecision(18);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    // Solution

    string o, e;
    cin >> o >> e;
    int to = min(o.size(), e.size());
    for (int i = 0; i < to; i++) {
        cout << o[i] << e[i];
    }
    if (o.size() > e.size()) {
        cout << o.back();
    }
}


Measured memory_bytes: 3640
import itertools

n, m = map(int, input().split())
my_set = set()

for i in range(m):
    a, b = map(int, input().split())
    my_set.add(a * 10 + b)
    my_set.add(b * 10 + a)

ret = 0
for item in itertools.permutations(range(1, n + 1)):
    is_ok = True
    if item[0] != 1:
        is_ok = False
    for i in range(len(item)-1):
        a, b = item[i], item[i+1]
        if a * 10 + b in my_set:
            continue
        else:
            is_ok = False
    if is_ok:
        ret += 1

print(ret)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define ll long long
#define ld long double 
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace :: std;


const ll  maxn=1e5+500;
const ll inf=2e18+7;

ll dp[maxn];
ll a[maxn];
ll parminn[maxn];
int main(){
    fill(dp,dp+maxn,inf);
    ll n,e,t;
    cin>>n>>e>>t;
    t*=2;
    e*=2;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        a[i]*=2;
    }
    ll p=0;
    dp[0]=0;
    for(ll i=1;i<=n;i++){
        while(p+1<i && a[i]-a[p+1]>=t/2){
            p++;
        }
        if(p==0){
            dp[i]=t;
        }else{
            dp[i]=min(dp[p]+t,parminn[p]+a[i]*2);
        }
        parminn[i]=min(parminn[i-1],dp[i-1]-a[i]*2);
    }
    cout<<(dp[n]+e)/2;
}

Measured memory_bytes: 2560