akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <iostream>
#include <utility>

using namespace std;

int main() {

	int DIAGONAL = 0;
	int TOP = 1;

	int N, W;
	scanf("%d %d", &N, &W);

	int C[N + 1][W + 1];
	int G[N + 1][W + 1];

	for (int i = 0; i <= W; ++i) {
		C[0][i] = 0;
		G[0][i] = DIAGONAL;
	}
	for (int i = 0; i <= N; ++i) {
		C[i][0] = 0;
	}

	pair<int, int> items[N + 1];

	for (int i = 1; i <= N; ++i) {
		int v, w;
		scanf("%d %d", &v, &w);
		items[i] = make_pair(v, w);
	}

	for (int i = 1; i <= N; ++i) {
		for (int w = 01; w <= W; ++w) {
			if (items[i].second <= w) {
				if (items[i].first + C[i - 1][w - items[i].second] > C[i - 1][w]) {
					C[i][w] = items[i].first + C[i - 1][w - items[i].second];
					G[i][w] = DIAGONAL;
				} else {
					C[i][w] = C[i - 1][w];
					G[i][w] = TOP;
				}
			} else {
				C[i][w] = C[i - 1][w];
				G[i][w] = TOP;
			}
		}
	}

	cout << C[N][W] << endl;

	return 0;
}

Measured memory_bytes: 11040
n, k = map(int, input().split())
p = list(map(int, input().split()))
tmp = 0.0
for i in range(k):
    tmp += (p[i]+1)/2
ans = tmp
for i in range(k, n):
    tmp += (p[i]-p[i-k])/2
    if ans < tmp:
        ans = tmp

print(ans)


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

typedef long long int int64;

void run(void){
  int n;
  scanf("%d",&n);
  int *x=(int *)calloc(n,sizeof(int));
  int i;
  for(i=0;i<n;i++) scanf("%d",x+i);
  int m;
  int64 k;
  scanf("%d%lld",&m,&k);
  int *s=(int *)calloc(n-1,sizeof(int));
  for(i=0;i<n-1;i++) s[i]=i;
  while(m--){
    int a;
    scanf("%d",&a);
    a-=2;
    int swap=s[a];
    s[a]=s[a+1];
    s[a+1]=swap;
  }
  int *t=(int *)calloc(n-1,sizeof(int));
  int *tmp=(int *)calloc(n-1,sizeof(int));
  for(i=0;i<n-1;i++) t[i]=i;
  while(k>0){
    if(k&1){
      for(i=0;i<n-1;i++) tmp[i]=s[t[i]];
      for(i=0;i<n-1;i++) t[i]=tmp[i];
    }
    for(i=0;i<n-1;i++) tmp[i]=s[s[i]];
    for(i=0;i<n-1;i++) s[i]=tmp[i];
    k>>=1;
  }
  int *y=(int *)calloc(n-1,sizeof(int));
  for(i=0;i<n-1;i++) y[i]=x[i+1]-x[i];
  for(i=0;i<n-1;i++) tmp[i]=y[t[i]];
  for(i=0;i<n-1;i++) y[i]=tmp[i];
  int64 ans=x[0];
  printf("%lld\n",ans);
  for(i=1;i<n;i++){
    ans+=y[i-1];
    printf("%lld\n",ans);
  }
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 3072
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define MOD 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(var) (var).begin(), (var).end()
#define MAXX 9000000000000000000
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pair<int,int> > 
#define vvpi vector<vector<pair<int,int> > >

struct comp
{	
	bool operator() (int a, int b) const
	{
		return a > b;
	}
};

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int n,m,i,j,x,y;
	cin >> n >> m;
	multiset<int, comp> arr;
	while(n--)
	{
		cin >> x;
		arr.insert(x);
	}

	// cout << m << endl;

	while(m--)
	{
		int x = *arr.begin();
		arr.erase(arr.begin());
		arr.insert(x / 2);
	}

	int ans = 0;

	for(auto it : arr)
	{
		ans += it;
	}

	cout << ans ;
	
	return 0;
}

Measured memory_bytes: 8220
n = int(input())
a = list(map(int, input().split()))

count = 0
while True:
    even = True
    for n in a:
        if n % 2 == 1:
            even = False
    if even:
        count += 1
        a = [i / 2 for i in a]
    else:
        break
print(count)


Measured memory_bytes: 2940
n,m=map(int,input().split())
ab=[]
cd=[]
for i in range(n):
    ab.append([int(j) for j in input().split()])
for i in range(m):
    cd.append([int(j) for j in input().split()])
a=[]
for i,j in ab:
    tmp=10**100
    ans=0
    k=1
    for x,y in cd:
        if tmp>abs(i-x)+abs(j-y):
            tmp=abs(i-x)+abs(j-y)
            ans=k
        k+=1
    a.append(ans)
for i in a:
    print(i)






Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct RMQ{
  int n;
  vector<int> dat;
  const int def=INT_MAX;
  RMQ(){}
  RMQ(int n_){init(n_);}
  void init(int n_){
    n=1;
    while(n<n_) n*=2;
    dat.clear();
    dat.resize(2*n-1,def);
  }
  void update(int k,int a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  int query(int a,int b,int k,int l,int r){
    if(r<=a||b<=l) return def;
    if(a<=l&&r<=b) return dat[k];
    else{
      int vl=query(a,b,k*2+1,l,(l+r)/2);
      int vr=query(a,b,k*2+2,(l+r)/2,r);
      return min(vl,vr);
    }
  }
  int query(int a,int b){
    return query(a,b,0,0,n);
  }
};
signed main(){
  int n,q;
  cin>>n>>q;
  RMQ rmq(n);
  for(int i=0;i<q;i++){
    int c,x,y;
    cin>>c>>x>>y;
    if(c) cout<<rmq.query(x,y+1)<<endl;
    else rmq.update(x,y);
  }
  return 0;
}
/*
verified on 2017/02/18
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_A
*/

Measured memory_bytes: 4932
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define per(i,a,b) for(int i =(b)-1;i>=(a);--i)
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef double db;
typedef vector<int> vi;
const int mod = 1e9 + 7;
const int maxn = 2e6 + 10;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int k,a,b;
	cin >> k >> a >> b;
	cout << (b/k > (a-1)/k ? "OK" : "NG");
	return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <map>
#include <cmath>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

#define rep(i, o) for (ll i = 0; i < (o);i++)
#define rep_s(i, o) for (int i = 1; i <= (o);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<(int)(b);i++)
#define NUM 1e5

typedef long long ll;
typedef unsigned long long ull;

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


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

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

int main() {
    ll n; 
    cin >> n;
    
    string ans = "";
    while (n >= 1)
    {
        if (n%26 == 0) { ans += char('`' + 26); n -= 1; }
        else ans += char('`' + (n % 26));
        // cout << ans << endl;
        n /= 26;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)


ll attack(ll x){
    if (x == 1)
        return 1;
    else
        return 1 + 2*attack(x/2);
}

int main()
{

#ifdef DEBUG
    cout << "DEBUG MODE" << endl;
    ifstream in("input.txt"); //for debug
    cin.rdbuf(in.rdbuf());    //for debug
#endif
    ll x;
    cin >> x;
    cout << attack(x) << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
class Program{
  private static char[][] c;
  static bool Check(int i,int j){
    bool f = false;
    try{f=f||c[i-1][j]=='#';}catch{}
    try{f=f||c[i+1][j]=='#';}catch{}
    try{f=f||c[i][j-1]=='#';}catch{}
    try{f=f||c[i][j+1]=='#';}catch{}
    return f;
  }
  static void Main(){
    string[] s = Console.ReadLine().Split(' ');
    int h=int.Parse(s[0]), w=int.Parse(s[1]);
    c = new char[h][];
    for (int i=0;i<h;i++)
      c[i]=Console.ReadLine().ToCharArray();
    bool ans=true;
    for (int i=0;i<h;i++){
      for (int j=0;j<w;j++){
        if (c[i][j]=='#'){
          ans = ans && Check(i,j);
        }
      }
    }
    Console.WriteLine(ans ? "Yes" : "No");
  }
}


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

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

    long long ans = 1e12;
    for (int i = 1; i <= 1e6; i++) {
        if (n % i == 0) {
            ans = min(ans, i + n / i - 2);
        }
    }

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

Measured memory_bytes: 384
#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define sort stable_sort
#define all(x) (x).begin(),(x).end()
#define rep(i,x) for (int (i)=(1);(i)<=(x);(i)++)
#define rep2(i,x) for (int (i)=(x);(i)>=(1);(i)--)
#define foreach(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
using namespace std;
int n,m,i,j,l,r,mid,ans;
string st;
char px[200005],py[200005];
int check(int x)
{
	int i;
	rep(i,m)
	{
		if (st[x]==px[i])
		{
			if (py[i]=='L') x--; else x++;
			if (x<1) return -1;
			if (x>n) return 1;
		}
	}
	return 0;
}
int solvel()
{
	int l=1,r=n+1,mid,ans=0;
	while (l<r)
	{
		mid=(l+r)/2;
		if (check(mid)==-1)
		{
			l=mid+1;
			ans=mid;
		}
		else r=mid;
	}
	return ans;
}
int solver()
{
	int l=0,r=n,mid,ans=n+1;
	while (l<r)
	{
		mid=(l+r+1)/2;
		if (check(mid)==1)
		{
			r=mid-1;
			ans=mid;
		}
		else l=mid;
	}
	return n+1-ans;
}
int main()
{
	cin>>n>>m>>st;st=" "+st;
	rep(i,m)
	{
		cin>>px[i]>>py[i];
	}
	cout<<max(0,n-solvel()-solver())<<endl;
	return 0;
}

Measured memory_bytes: 984
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> Pint;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
ll MOD  = 1000000007;
vector<int> dy = {0,0,1,-1};
vector<int> dx = {1,-1,0,0};

int main(void){
    cin.tie(0);
   	ios::sync_with_stdio(false);
   	int A, B;
   	cin >> A >> B;
   	
   	vector<vector<char>> mp(100, vector<char>(100));
   	for(int i = 0; i < 100; i++){
   	    for(int j = 0; j < 100; j++){
   	        if(i < 50){
   	            mp[i][j] = '.';
   	        }else{
   	            mp[i][j] = '#';
   	        }
   	    }
   	}
   	
   	for(int i = 0; i < B - 1; i++){
   	    mp[(i / 50) * 2][(i % 50) * 2] = '#';
   	}
   	for(int i = 0; i < A - 1; i++){
   	    mp[(i / 50) * 2 + 51][(i % 50) * 2] = '.';
   	}
   	cout << 100 << " " << 100 << endl;
   	for(int i = 0; i < 100; i++){
   	    for(int j = 0; j < 100; j++){
   	        cout << mp[i][j];
   	    }
   	    cout << endl;
   	}
}



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

int main(){
  int N,Y;
  std::cin>>N>>Y;
  int y=Y/1000, yen[3]={10,5,1};
  for(int i=0;i<=N;++i){
    for(int j=0;j<=N;++j){
      if(N-i-j<0)continue;
      int sum=yen[0]*i+yen[1]*j+yen[2]*(N-i-j);
      if(sum==y){
        std::cout<<i<<" "<<j<<" "<<N-i-j<<std::endl;
        return 0;
      }
    }
  }
  std::cout<<-1<<" "<<-1<<" "<<-1<<std::endl;
  return 0;
}



Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
using namespace std;
int N, K, h[100005], dp[100005];
int main() {
  scanf("%d %d", &N, &K);
  for(int i = 1; i <= N; ++i) {
    scanf("%d", &h[i]);
    dp[i] = 1e9;
  }
  dp[1] = 0;
  for(int i = 2; i <= N; ++i) {
    for(int k = 1; k < i && k <= K; ++k) {
      dp[i] = min(dp[i], dp[i-k]+abs(h[i]-h[i-k]));
    }
  }
  printf("%d\n", dp[N]);
}

Measured memory_bytes: 896
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        List<Integer> a = new ArrayList<>();
        while(true){
            if(a.contains(s))
            break;
            a.add(s);
            s = s%2 == 0 ? s/2 : s*3+1;
        }
        System.out.println(a.size()+1);
    }
}

Measured memory_bytes: 25172
S = input()

ans = ''
def dfs(i, s):
    val = sum([int(s[i*2:i*2+2]) for i in range(len(s)//2)])
    if (i == 4) and (val==7):
        global ans
        ans = s
        return True
    
    if (i==4) and (val!=7):
        return False
    
    if dfs(i+1, s + '+' + S[i]):
        return True
    
    if dfs(i+1, s + '-' + S[i]):
        return True

dfs(0, '')
print(ans[1:] + '=7')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 1e9 + 7;

int n;
vector<int> A; 
vector<int> ans;

int main()
{
	scanf("%d", &n);
	A.resize(n);
	rep(i, n) scanf("%d", &A[i]);
	
	rep(i, n) {
		int cpos = -1;
		rep(j, A.size())
		if(A[j] == j + 1) cpos = j;
		
		if(cpos == -1) {
			printf("-1\n");
			return 0;
		}
		ans.push_back(A[cpos]);
		A.erase(A.begin() + cpos); 
	}
	
	reverse(ans.begin(), ans.end());
	rep(i, ans.size()) printf("%d\n", ans[i]);
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cctype>
#include <chrono>
#include <cmath>
#include <cstdio>
#include <ctime>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*----------------------------------------*/

int main() {
  cin.tie(0); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  int n; cin >> n;
  vector<int> h(n); REP(i, n) cin >> h[i];
  vector<long long> dp(n, LINF);
  dp[0] = 0;
  REP(i, n-1) {
    if (i+1 <= n-1) dp[i+1] = min(dp[i+1], dp[i] + abs(h[i+1] - h[i]));
    if (i+2 <= n-1) dp[i+2] = min(dp[i+2], dp[i] + abs(h[i+2] - h[i]));
  }
  cout << dp[n-1] << '\n';
  return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
    using namespace std;
    #define MP ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    #define nl "\n"
    #define End return 0
    #define ll long long int
    #define mp make_pair
    #define pb push_back
    #define ull unsigned long long int
    #define pi acos(-1)
    #define forn(i,a,b) for (int i=a;i<=b;i++)
    int main()
    {
        int s,w;
        cin>>s>>w;
        if(w>=s) cout<<"unsafe"<<endl;
        else cout<<"safe"<<nl;
    End;
    }

Measured memory_bytes: 3640
#include<bits/stdc++.h>
using namespace std;
 
int n, m, ans;
 
int main()
{
    cin >> n >> m;
    for(int i = 1;i<=n;++i)
        for(int j = 1;j<=m;++j)
        {
            char x;
            cin >> x;
            if(x=='#')
                ++ans;
        }
    if(ans != n+m-1)
        cout << "Impossible";
    else
        cout << "Possible";
 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define FAST_IO   ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define Relocate freopen("./in.txt","r",stdin);freopen("./out.txt","w",stdout)
#define up(mi,a,b) for(mi=a;mi<=b;++mi)
#define down(mi,b,a) for(mi=b;mi>=a;--mi)
#define mfill(a,v) memset(a,v,sizeof(a))
#define INF 0x3f3f3f3f
#define MAX 1005
#define v_n 5005
#define LL long long
#define e_n 5000005
#define MOD 1000000007
#define eps 0.000000001
#define Blen 32
using namespace std;
vector<int> st[25];
int P[25];
int N, M;
bool ok(int status)
{
	for (int i = 1; i <= M; i++)
	{
		int cnt = 0;
		for (auto one : st[i])
		{
			if (status >> (one - 1)&1)
			{
				cnt++;
			}
		}
		if ((cnt & 1) != P[i])
		{
			return 0;
		}
	}
	return 1;
}
int main(void)
{
	int i, j, k;
	FAST_IO;
	//Relocate;
	cin >> N >> M;
	up(i, 1, M)
	{
		cin >> j;
		while (j--)
		{
			cin >> k;
			st[i].push_back(k);
		}
	}
	up(i, 1, M)
	{
		cin >> P[i];
	}
	int mm = (1 << N);
	int ans = 0;
	for (int i = 0; i < mm; i++)
	{
		if (ok(i))
		{
			//cout << i << endl;
			ans++;
		}
	}
	cout  << ans << endl;
	return 0;
}

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

using namespace std;

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
typedef long long LL;
int N;
LL C[11234];
LL S[11234];
LL F[11234];
int main(){
while(cin>>N){
REP(i,N-1)cin>>C[i]>>S[i]>>F[i];
REP(i,N-1){
LL now = S[i];
FOR(j,i,N-1){
if(now<S[j])now = S[j];
now+=F[j]-1;
now/=F[j];
now*=F[j];
now+=C[j];
}
cout<<now<<endl;
}
cout<<0<<endl;
}
return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <math.h>
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <numeric>
#include <stdio.h>
#include <vector>
#include <map>
#include <queue>

using namespace std;
typedef long long ll;

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {

    ll n;
    cin >> n;
    ll a[n];
    ll N = 0;
    rep(i,n){
        cin >> a[i];
        N = max(a[i],N);
    }
    ll R = N;
    rep(i,n){
        if(a[i]!=N){
            if(abs((N+1)/2-a[i])<=abs((N+1)/2-R)) R = a[i];
        }
    }
    cout << N << " " << R << endl;
    return 0;
}


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


int main()
{
        int n;
        cin >>n;
        bool ans = true;
       for(int i = 0; i< n; i++)
       {
               int a;
               cin >> a;

               if(a % 2 == 0)
               {
                       if(a % 3 != 0 && a % 5 != 0){
                               ans = false;
                               break;
                       }
               }

       }
        if(ans == true)
        {
                cout << "APPROVED" << endl;
        }
        else
        {
                cout << "DENIED" << endl;
        }
}


Measured memory_bytes: 256
def prime(n)
  f = Array.new(n+1, 0)
  i = 2
  while i * i <= n do
    if f[i] == 0
      k = i * i
      while k <= n do
        if f[k] == 0
          f[k] = i
        end
        k += i
      end
    end
    i += 1
  end
  primes =[]
  f.each.with_index(0) do |i, index|
    if i == 0 && index >= 2
      primes << index
    end
  end
  primes.size
end

while (n = gets.to_i) != 0 do
  puts prime(n)
end


Measured memory_bytes: 90560
import sys
from functools import reduce
import copy
import math
from pprint import pprint
import collections
import bisect


sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def int_inputs(num_of_input):
    ins = [int(input()) for i in range(num_of_input)]
    return ins


def solve(inputs):
    [s_num, c_num] = string_to_int(inputs[0])

    scc_num = 0

    if s_num * 2 <= c_num:
        scc_num += s_num
        c_num -= (s_num * 2)
        scc_num += c_num // 4
    else:
        scc_num += c_num // 2
        c_num -= c_num // 2
        # scc_num += c_num // 4
    return scc_num


def string_to_int(string):
    return list(map(int, string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main(){
  int h1, m1, h2, m2, k;

  cin >> h1 >> m1 >> h2 >> m2 >> k;
  int s1, s2;
  s1 = h1 * 60 + m1;
  s2 = h2 * 60 + m2;
  cout << s2 - s1 - k << endl;
  return 0;
}

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

using namespace std;
#define inf 1000000000
#define unvisited -1
#define visited 1
#define eps 1e-9
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define uint64 unsigned long long
#define FastSlowInput ios_base::sync_with_stdio(false); cin.tie(NULL);
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;

const int maxn = 2e5 + 5;

ll dp[maxn];
ll st[4*maxn];

int left(int n){return n<<1;}
int right(int n){return (n<<1) + 1;}

ll query(int node, int l, int r, int i, int j){
	if(l > r){return 0;}
	if(r < i || l > j){return 0;}
	if(i<= l && r <= j){return st[node];}
	int mid = (l+r)/2;
	ll ans1 = query(left(node), l, mid, i, j);
	ll ans2 = query(right(node), mid+1, r, i, j);
	return max(ans1, ans2);
}

void update(int node, int l, int r, int idx, ll val){
	if(r < idx || l > idx){return;}
	if(l == idx && r == idx){st[node] = val; return;}
	int mid = (l+r)/2;
	update(left(node), l, mid, idx, val);
	update(right(node), mid+1, r, idx, val);
	st[node] = max(st[left(node)], st[right(node)]);
}

int main(){
	int n,i,j;
	scanf("%d",&n);
	int h[maxn], a[maxn];

	for(i=0;i<n;i++){
		scanf("%d",&h[i]);
	}
	for(i=0;i<n;i++){
		scanf("%d",&a[i]);
	}
	for(i=0;i<n;i++){
		ll maks = query(1,1,n,1,h[i]-1);
		// printf("query dari 1 sampe %d\n",h[i]-1);
		ll nilaiSekarang = dp[h[i]];
		if(nilaiSekarang < maks + a[i]){
			nilaiSekarang = maks + a[i];
			// printf("i: %d maks: %lld nilaiSekarang: %lld diupdate di h: %d\n",i,maks,nilaiSekarang, h[i]);
			dp[h[i]] = nilaiSekarang;
			update(1,1,n,h[i], nilaiSekarang);
		}
	}
	printf("%lld\n",*max_element(dp+1, dp+n+1));
	return 0;
};

Measured memory_bytes: 9472
N = int(input())
s = [0]*N
num_ab_in = 0
num_hip_a = 0
num_head_b =0 
num_both = 0

for i in range(N):
    s[i] = input()
    slist= list(s[i])
    num_ab_in += s[i].count('AB')
    if slist[0] =='B':
        num_head_b +=1
    if slist[-1] =='A':
        num_hip_a +=1
    if slist[0] =='B' and slist[-1] =='A':
        num_both +=1

if num_both == num_head_b and num_both == num_hip_a and num_both !=0:
    ans = num_ab_in + num_both-1
else:
    ans = num_ab_in + min(num_head_b,num_hip_a)
print(ans)

Measured memory_bytes: 46040
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,a,b,c,d,e;
  cin>>n>>a>>b>>c>>d>>e;
  ll m = min({a,b,c,d,e});
  ll neck = n/m+(n%m ? 1 : 0);
  cout<<5+neck-1;
  return 0;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use std::{cmp::Reverse, collections::*};

#[allow(unused_imports)]
use proconio::{
    fastout, input,
    marker::{Chars, Usize1},
};

#[allow(unused_imports)]
use itertools::Itertools;

#[allow(unused_imports)]
use num::Integer;

#[fastout]
pub fn main() {
    input! {
        h: usize, w: usize, m: usize,
        grids: [(Usize1, Usize1); m],
    }

    let mut r = vec![0; h];
    let mut c = vec![0; w];
    let mut map = HashMap::new();
    for (gh, gw) in grids {
        r[gh] += 1;
        c[gw] += 1;
        map.entry(gh).or_insert(HashSet::new()).insert(gw);
    }
    let (mh, _) = r.iter().enumerate().max_by_key(|(_, x)| *x).unwrap();
    let (mw, _) = c.iter().enumerate().max_by_key(|(_, x)| *x).unwrap();
    if r[mh] > c[mw] {
        println!(
            "{}",
            (0..w)
                .map(|i| {
                    if r[mh] + c[i] == 0 {
                        0
                    } else {
                        r[mh] + c[i]
                            - if map.contains_key(&mh) && map[&mh].contains(&i) {
                                1
                            } else {
                                0
                            }
                    }
                })
                .max()
                .unwrap()
        );
    } else {
        println!(
            "{}",
            (0..h)
                .map(|i| {
                    if r[i] + c[mw] == 0 {
                        0
                    } else {
                        r[i] + c[mw]
                            - if map.contains_key(&i) && map[&i].contains(&mw) {
                                1
                            } else {
                                0
                            }
                    }
                })
                .max()
                .unwrap()
        );
    }
}


Measured memory_bytes: 73664
#include<iostream>

int main(){
    int i;
    int x;

    for(i=0;i<10000;i++){
    
        std::cin>>x;
    
        if(x==0){
            break;
        }
    
        std::cout<<"Case "<<i+1<<": "<<x<<std::endl;
    }

    return 0;
}


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

const long long mod = 1e9 + 7;
int n, m;
long long f[1002][1002]{0};
char a[1002][1002];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        string s;
        cin>>s;
        for (int j=1;j<=m;j++){
            a[i][j] = s[j-1];
            if (s[j-1] == '#') f[i][j] = -1;
            else f[i][j] = 0;
        }
    }
    f[1][1] = 1 % mod;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            if (i == 1 && j == 1) continue;
            if (f[i][j] == -1) continue;
            if (f[i-1][j] != -1) f[i][j] = (f[i-1][j] + f[i][j]) % mod;
            if (f[i][j-1] != -1) f[i][j] = (f[i][j-1] + f[i][j]) % mod;
        }
    }
    cout<<f[n][m];

}


Measured memory_bytes: 9088
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
using P = pair<int,int>;
const int INF = 1001001001;
int main()
{
    int h,n;
    cin >> h >> n;
    vector<int> dp(h+1,INF);
    dp[0] = 0;
    rep(i,n){
        int a,b;
        cin >> a >> b;
        rep(j,h+1){
            dp[min(j+a,h)] = min(dp[min(j+a,h)],dp[j]+b);
        }
    }
    cout << dp[h] << endl;

    return 0;
}

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

using namespace std;
using ll = long long;

int main() {
	int M;
	cin >> M;
	ll digit = 0;
	ll s = 0;
	for (int i = 0; i < M; i++) {
		ll d, c;
		cin >> d >> c;
		s += d * c;
		digit += c;
	}
	ll ans = (digit - 1) + ((s - 1) / 9);
	cout << ans << endl;
	return 0;
}

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

typedef long long ll;



using namespace std;
int main()
{
  ll n;
  cin >> n;
  
  string alphabet = "zabcdefghijklmnopqrstuvwxy";
  
  string tmp = "";
  
  while(n>0){
    tmp += alphabet[n % 26];
    if(n%26 == 0){
      n -= 26;
    }
    n /= 26;
  }
  
  for(int i=tmp.size()-1; i>=0; i--){
    cout << tmp[i];
  }
}

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

int main() {
  long long a,b,c,k; cin >> a >> b >> c >> k;
  if(k<=a){
    cout << k;
  }else if(k-a<=b){
    cout << a;
  }else{
    cout << a - (k - a - b);
  }
}


Measured memory_bytes: 3568
# include <bits/stdc++.h>
# define ll long long
using namespace std;
const ll N = 16, INF = 1e16;
ll dp[1 << N], group[1 << N], a[N][N], n;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> a[i][j];
        }
    }
    for(int mask = 0; mask < (1 << n); mask++){
        for(int i = 0; i < n; i++){
            for(int j = i + 1; j < n; j++){
                if(((mask >> i) & 1) && (mask >> j) & 1){
                    group[mask] += a[i][j];
                }
            }
        }
        dp[mask] = -INF;
    }
    dp[0] = 0; 
    for(int mask = 0; mask < (1 << n); mask++){
        int comp_mask = (1 << n) - mask - 1;
        for(int new_mask = comp_mask; new_mask; new_mask = (new_mask - 1) & comp_mask){
            int next_mask = new_mask ^ mask;
            dp[next_mask] = max(dp[next_mask], dp[mask] + group[new_mask]); 
        }
    }
    cout << dp[(1 << n) - 1] << endl;
}

Measured memory_bytes: 1280
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin >> n;
	int i;
	for (i=0;n>1;i++) {
		n=n/2;
	}
	for (;i>0;i--) {
		n=n*2;
	}
	cout << n << endl;
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>

int main() {
	int k = 0;
	char s[110], t[110]={0}, u[] = "...";
	char str3[110];
	int len;

	scanf("%d", &k);
	scanf("%s", s);
	len = strlen(s); 
		if (len > k) {
			for (int i = 0; i < k; i++)t[i] = s[i];
			sprintf(str3, "%s%s",t, u);
			printf("%s", str3);
		}
	if (len <= k) printf("%s", s);

	return 0;
}

Measured memory_bytes: 1736
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)

ll n,k;
int main(){
	scanf("%lld%lld",&n,&k);
	puts((n+1)/2>=k?"YES":"NO");
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int[] array = new int[10];
        for (int i = 0; i < array.length; i++) {
            array[i] = Integer.parseInt(sc.nextLine());
        }
        sc.close();

        Arrays.sort(array);

        System.out.println(array[9]);
        System.out.println(array[8]);
        System.out.println(array[7]);
    }

}

Measured memory_bytes: 17268
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod = 1000000007;
const int N = 100010;
vector<int> g[N];
int sum[N], ans;
void dfs(int u, int pre)
{
    sum[u] = 1;
    for (int i = 0; i < g[u].size(); i++)
    {
        int v = g[u][i];
        if (v != pre)
        {
            dfs(v, u);
            sum[u] += sum[v];
        }
    }
    if (sum[u] % 2 == 0)
    {
        if (u != 1)
            ans++;
    }
}
int main() 
{
    
    int n;

    while (~scanf("%d", &n))
    {
        if (n%10 == 9 || n/10 == 9)
            puts("Yes");
        else
            puts("No");
    }
   
    return 0;
}


Measured memory_bytes: 2560
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int a=Integer.parseInt(sc.next());
int b=Integer.parseInt(sc.next());
int c=Integer.parseInt(sc.next());
int d=Integer.parseInt(sc.next());
System.out.println(Math.min(a, b)+Math.min(c, d));
}}

Measured memory_bytes: 22996
//include
//------------------------------------------
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

// conversion
inline int
toInt(string s)
{
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}
template <class T>
inline string toString(T x)
{
    ostringstream sout;
    sout << x;
    return sout.str();
}

//math
template <class T>
inline T sqr(T x) { return x * x; }

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
const double EPS = 1e-10;
const double PI = acos(-1.0);

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

//debug
#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

int main()
{
    int X, A;
    cin >> X >> A;
    if (X < A)
        cout << 0 << endl;
    else
        cout << 10 << endl;
}

Measured memory_bytes: 256
import sys

N, X = list(map(int, sys.stdin.readline().strip().split(" ")))
L_list = list(map(int, sys.stdin.readline().strip().split(" ")))
d = 0
count = 1

for l in L_list:
    if d + l <= X:
        count += 1
        d += l
    else:
        break

print(count)

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <math.h>
#include <list>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
*/

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

	int n;
	cin >> n;
	vector<string> s(n);
	rep(i, n) cin >> s[i];

	// 最後がAで終わる　かつ　最初がBで始まるなら +1

	int aCnt = 0;
	int bCnt = 0;
	int baCnt = 0;
	int ans = 0;

	rep(i, n) {
		if (s[i][0] == 'B' && s[i][(int)s[i].size() - 1] == 'A') {
			baCnt++;
		}
		
		if (s[i][0] == 'B') bCnt++;
		if (s[i][(int)s[i].size() - 1] == 'A') aCnt++;
		
		Rep(j,1, (int)s[i].size()) {
			if (s[i][j - 1] == 'A' && s[i][j] == 'B') {
				ans++;
			}
		}
	}

	ans += min(aCnt, bCnt);

	if (aCnt == bCnt && bCnt == baCnt && aCnt != 0) ans--;

	// BA BA のときは1つしかできない
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 768
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;
using namespace std;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

bool isACGT(const char c){ return (c=='A' || c=='C' || c=='G' || c=='T'); }

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string s; cin >> s;
    
    int num=0;
    int num_max=0;
    for(uint i=0; i<s.size(); ++i){
        if(isACGT(s[i])){ ++num; }else{ num=0; }
        num_max = max(num, num_max);
    }
    cout << num_max << endl;
    
    return 0;
}

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

int main() {
    string S; cin >> S;
    for (int i = S.size() - 2; i > 0; i -= 2) {
        string S_edited = S.substr(0, i);
        if (S_edited.substr(0, S_edited.size() / 2) == S_edited.substr(S_edited.size() / 2, S_edited.size() / 2)) {
            cout << S_edited.size() << endl;
            break;
        }
    }
}


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

int main(){
    int H,W;
    cin>>H>>W;
    vector<vector<char>> table(H+2,vector<char>(W+2,'.'));
    for(int i=1;i<H+1;i++){
        for(int j=1;j<W+1;j++){
            cin>>table.at(i).at(j);
        }
    }
    bool ans=true;
    for (int i = 1; i < H+1; i++){
         for(int j = 1;j < W+1; j++){
             if(table.at(i).at(j)=='#'){
                 if(table.at(i-1).at(j)=='.'&&table.at(i+1).at(j)=='.'&&table.at(i).at(j-1)=='.'&&table.at(i).at(j+1)=='.'){
                     ans=false;
                     break;
                 }
             }
        }
    }
    if(ans){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9 +7;
const ll MAXN = 1e6 + 5;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,a[1005],cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(x%2==0) a[++cnt]=x;
	}
	bool flag=0;
	for(int i=1;i<=cnt;i++){
		if(a[i]%3!=0 && a[i]%5!=0) flag=1;
	}
	if(flag) cout<<"DENIED";
	else cout<<"APPROVED";
	return 0;
}


Measured memory_bytes: 256
def createDice(n):
    dice = []
    for _ in range(n):
        numbers = list(map(int, input().split()))
        dice.append(Dice(numbers))

    return dice

class Dice:
    def __init__(self, numbers):
        self.dice = {"上" :numbers[0],
                     "下":numbers[5], 
                     "前":numbers[1],
                     "後":numbers[4],
                     "左":numbers[3],
                     "右":numbers[2]
                    }

    def query(self):
        return [self.dice["上"], self.dice["下"], self.dice["前"], self.dice["後"], self.dice["左"], self.dice["右"]]

    def rotate_x(self):
        U, D, F, B = [self.dice["上"], self.dice["下"], self.dice["前"], self.dice["後"]]
        self.dice["上"] = F
        self.dice["前"] = D
        self.dice["下"] = B
        self.dice["後"] = U

    def rotate_y(self):
        U, D, L, R = [self.dice["上"], self.dice["下"], self.dice["左"], self.dice["右"]]
        self.dice["上"] = R
        self.dice["下"] = L
        self.dice["左"] = U
        self.dice["右"] = D

    def rotate_z(self):
        F, R, B, L = [self.dice["前"], self.dice["右"], self.dice["後"], self.dice["左"]]
        self.dice["前"] = R
        self.dice["右"] = B
        self.dice["後"] = L
        self.dice["左"] = F

    def set_position(self, position_seq):
        self.ans = []
        self.up = position_seq[0]
        self.front = position_seq[2]
        
        for i in range(6):
            self.search()
            if i == 2:
                self.rotate_y()
            else:
                self.rotate_x()
        
        return self.ans
    
    def search(self):
        # print("goal:上", self.up, ":", self.dice["上"])
        if self.dice["上"] == self.up:
            for _ in range(4):
                # print("goal:前|上 ", self.front, ":", self.dice["前"], "|", self.dice["上"], "→", self.dice["右"])
                if self.dice["前"] == self.front:
                    self.ans.append(self.query())
                    break
                self.rotate_z()

FLAG = 0
n = int(input())
dice = createDice(n)

for i in range(n-1):
    for j in range(i+1, n):
        next_dice = dice[j].query()
        next_dice_seq = dice[j].set_position(next_dice)
        nice_dice_seq = dice[i].set_position(next_dice)
        # print("サイコロ", i, ":", nice_dice_seq)
        # print("サイコロ", j, ":", next_dice_seq)
        # print()

        for k in range(len(nice_dice_seq)):
            for l in range(len(next_dice_seq)):
                FLAG += (nice_dice_seq[k] == next_dice_seq[l])

if FLAG > 0:
    print('No')
else:
    print('Yes')


Measured memory_bytes: 5800
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parent = [i for i in range(n)]
        self.rank = [1]*n
        self.size = [1]*n
    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def unite(self, x, y):
        x = self.find(x); y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                self.parent[x] = y
                self.size[y] += self.size[x]
            else:
                self.parent[y] = x
                self.size[x] += self.size[y]
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
    def is_same(self, x, y):
        return self.find(x) == self.find(y)
    def group_size(self, x):
        return self.size[self.find(x)]
n, m = map(int, input().split())
x = [0]*m; x[m-1] = n*(n-1)//2; uf = UnionFind(n)
a = [0]*m; b = [0]*m
for i in range(m):
    a[i], b[i] = map(int, input().split())
    a[i] -= 1; b[i] -= 1
for i in range(m-1, 0, -1):
    if uf.is_same(a[i], b[i]): x[i-1] = x[i]
    else:
        x[i-1] = x[i]-uf.group_size(a[i])*uf.group_size(b[i])
        uf.unite(a[i], b[i])
print(*x, sep="\n")

Measured memory_bytes: 24972
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
#define ll long long
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rep1(i, n) FOR(i, 1, n+1)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define whole(x) (x).begin(),(x).end()
#define rwhole(x) (x).rbegin(), (x).rend()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define P pair<int, int>
#define debug(var) cerr << "[" << #var << "] " << var << '\n'
template<typename T1, typename T2>
bool chmax(T1 &a,T2 b){if(a<b){a=b;return true;}else return false;}
template<typename T1, typename T2>
bool chmin(T1 &a,T2 b){if(a>b){a=b;return true;}else return false;}
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define pr(s) cout << (s) << '\n'
const ll mod = 1000000007;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
const int INF = 1001001001;
const ll INFll = 1E+18;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string s;
    cin >> s;
    int n = s.size();
    bool ok = true;
    if (s[n-1]=='1') ok = false;
    if (s[0]=='0') ok = false;
    
    rep(i, n-1) {
        if (s[i]!=s[n-2-i]) ok = false;
    }
    if (!ok) {
        pr(-1);
        return 0;
    }
    int before = 0;
    vector<P> edge;
    rep(i, n-1) {
        int now = i + 1;
        edge.eb(before, now);
        if (s[i]=='1') before = now;
    }
    for (auto p: edge) {
        cout << p.fi+1 << " " << p.se+1 << "\n";
    }
    return 0;
}


Measured memory_bytes: 4508
def bingo_search(CARD):
    for i in range(3):
        # 横一列そろったか否か
        if CARD[i][0] == '☓' and CARD[i][1] == '☓' and CARD[i][2] == '☓':
            return True

    for j in range(3):
        # 縦一列そろったか否か
        if CARD[0][j] == '☓' and CARD[1][j] == '☓' and CARD[2][j] == '☓':
            return True

    # ななめ一列そろったか否か
    if CARD[0][0] == '☓' and CARD[1][1] == '☓' and CARD[2][2] == '☓':
            return True

    # ななめ一列そろったか否か
    if CARD[0][2] == '☓' and CARD[1][1] == '☓' and CARD[2][0] == '☓':
            return True

    return False



A1 = list(input().split())
A2 = list(input().split())
A3 = list(input().split())
A = [A1, A2, A3]  #Bingoカードが完成
#print(A)

N = int(input())
for i in range(N):
    flag = False
    b = input()
    for j in range(3):
        for k in range(3):
            if A[j][k] == b:
                A[j][k] = '☓'
                flag = True
                break
        if flag == True:
            break
#print(A)

if bingo_search(A):
    print("Yes")

else:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define SPEED ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define endl '\n'
#define vi vector<ll>
#define vb vector<bool>
#define mii map<ll, ll>
#define pii pair<ll, ll>
#define pb push_back
#define fi first
#define se second
// #define mod 1000000007
// ll dp[][]
ll power(ll a, ll b){
    ll res = 1;
    while(b!=0){
        if(b&1){
            res *= a; 
        }
        a = (a * a);
        b = (b / 2);
    }
    return res;
}
int main(){
    SPEED;
    ll n, i, sum = 0;
    cin>>n;
    vi v(n), dp;
    for(i=0;i<n;i++){
        cin>>v[i];
    }
    dp.pb(0);
    dp.pb(abs(v[0]-v[1]));
    for(i=2;i<n;i++){
        dp.pb(min(dp[i-1]+abs(v[i]-v[i-1]), dp[i-2]+abs(v[i]-v[i-2])));
    }
    cout<<dp[n-1]<<endl;
    return 0;
}

Measured memory_bytes: 2168
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 2222222222222222222LL;
const ll mod = 1000000007LL;


ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222


ll a[22], b[22];



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


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

  rep(i, n) ans += max(0LL, a[i] - b[i]);
  cout << ans << endl;



  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int len;
char String[100020];

int Check(void);

int main(void) {
	
	scanf("%s", String);
	for (len = 0; String[len]; len++);
	if (len == 2) { 
		if (String[0] == String[1]) printf("%d %d\n", 1, 2); 
		else printf("-1 -1\n");
	}
	else if (Check()) printf("%d %d\n", -1, -1);
	
	return 0;
}

int Check(void) {

	int i;

	if (String[0] == String[1]) {
		printf("%d %d\n", 1, 3);
		return 0;
	}
	
	for (i = 0; i < len - 2; i++) {
		if (String[i] == String[i+2] || String[i+1] == String[i+2]) {
			printf("%d %d\n", i+1, i+3);
			return 0;
		}
	}

	return 1;
}

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

const int mxD = 110, mxN = 1e4 + 5, mod = 1e9 + 7;
string K;
int D, n;
vector<int> digits;
ll dp[mxN][mxD][2];

ll rec(int idx, int sum, int flag) {
	if (idx == n) {
		if (sum % D == 0) {
			return 1;
		}
		return 0;
	}
	if (dp[idx][sum][flag] != -1) {
		return dp[idx][sum][flag];
	}
	int limit = (flag == 1)? digits[idx] : 9;
	ll ans = 0;
	for (int i = 0; i <= limit; i++) {
		if (i == digits[idx]) {
			ans = (ans + rec(idx + 1, (sum + i) % D, flag)) % mod;
		} else {
			ans = (ans + rec(idx + 1, (sum + i) % D, 0)) % mod;
		}
	}
	return dp[idx][sum][flag] = ans;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> K >> D;
	n = (int) K.length();
	for (char it : K) {
		digits.push_back(it - '0');
	}
	memset(dp, -1, sizeof(dp));
	ll ans = rec(0, 0, 1);
	ans = (ans - 1 + mod) % mod;
	cout << ans;
	
	return 0;
}


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

int main() {
  int n;
  int k;
  cin >> n >> k;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a.at(i);
  }
  int res = 0;
  int right = 0;
  while (true) {
    if (res == 0)
      right += k;
    else
      right += k - 1;
    res++;
    if (right >= n) break;
  }
  cout << res;
}


Measured memory_bytes: 640
N = int(input())
p = list(map(int, input().split()))

# p_i != i なる要素p_iの数をkとするとき、
# k<=2 であるときに限り1回以下のスワップでpを昇順にできる
# k=0 のとき、最初からpは昇順
# k=1 にはならない
# k=2 のとき p_i != i である2つの要素を1回スワップすることでpを昇順にできる

q = list(range(1, N+1))

k = 0
for i in range(N):
  if p[i] != q[i]: k += 1
    
if k <= 2: print('YES')
else: print('NO')

Measured memory_bytes: 9080
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <tuple>
#include <set>
#include <queue>
#include <numeric>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<pair<int, int>> jobs(n);
	for (int i = 0; i < n; ++i) {
		cin >> jobs[i].second >> jobs[i].first;
	}
	sort(jobs.begin(), jobs.end());
	int time = 0;
	bool pos = true;
	for (int i = 0; i < n; ++i) {
		time += jobs[i].second;
		if (time > jobs[i].first) pos = false;
	}
	if (pos) cout << "Yes\n";
	else cout << "No\n";
	return 0;
}

Measured memory_bytes: 1792