akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

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

typedef long long ll;
const ll MOD = 1e9 + 7;

std::set<ll> prime_factors(ll n) {
  std::set<ll> ret;

  ll tmp = n;
  for(ll i = 2; i * i <= n; ++i) {
    if(tmp % i == 0) {
      ret.insert(i);
    }
    while(tmp % i == 0) {
      tmp /= i;
    }
  }

  if(tmp > 1) ret.insert(tmp);
  return ret;
}

int main() {
  ll A, B;
  std::cin >> A >> B;

  auto ps1 = prime_factors(A);
  auto ps2 = prime_factors(B);

  ll cnt = 0;
  for(ll n : ps1) {
    if(ps2.find(n) != ps2.end()) ++cnt;
  }

  std::cout << cnt + 1 << '\n';
}


Measured memory_bytes: 256
def solve(n, m, a_list):
    cnt = 0
    if sum(a_list) % (4 * m) == 0:
        bar = sum(a_list) // (4 * m)
    else:
        bar = sum(a_list) // (4 * m) + 1
    for a in a_list:
        if a >= bar:
            cnt += 1
    if cnt >= m:
        return "Yes"
    else:
        return "No"


def main():
    n, m = map(int, input().split())
    a_list = list(map(int, input().split()))
    res = solve(n, m, a_list)
    print(res)


def test():
    assert solve(4, 1, [5, 4, 2, 1]) == "Yes"
    assert solve(3, 2, [300, 19, 1]) == "No"
    assert solve(12, 3, [4, 56, 78, 901, 2, 345, 67, 890, 123, 45, 6, 789]) == "Yes"


if __name__ == "__main__":
    test()
    main()


Measured memory_bytes: 3064
S=raw_input()
T=raw_input()

def hantei(S,T):
    ans=True
    if(len(S)!=len(T)):
        return False
    for i in range(0,len(T)):
        if(S[i]==T[i] or S[i]=='?'):
            pass
        else:
            ans=False
            break
    return ans

ans=list()
for i in range(0,len(S)):
    if(hantei(S[i:i+len(T)],T)):
        ans.append(S[0:i]+T+S[i+len(T):100])
if(len(ans)>0):
    ans=list(ans[-1])
    for i in range(0,len(ans)):
        if(ans[i]=='?'):
            ans[i]="a"
            
    ans="".join(ans)
    print(ans)
else:
    print("UNRESTORABLE")

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

int main(void) {
    int N,A,B,C,D;cin>>N>>A>>B>>C>>D;
    int X = (N % A == 0) ? (N / A) * B: ((N / A) + 1) * B;
    int Y = (N % C == 0) ? (N / C) * D: ((N / C) + 1) * D;
    cout << min(X, Y) << endl;
    return 0;
}


Measured memory_bytes: 3104
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

//constexpr long long int MOD = 1000000007;
constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr long double EPS = 1e-12;


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

	long long int H, W;
	cin >> H >> W;
	if (H == 1 || W == 1) {
		cout << 1 << endl;
		return 0;
	}
	cout << (H*W + 1) / 2 << endl;
}

Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! get {
    ([$t:ty] ; $n:expr) => {
        (0..$n)
        .map(|_| get!([$t])).collect::<Vec<_>>()
    };
    ($($t:ty),+ ; $n:expr) => {
        (0..$n).map(|_| get!($($t),+)).collect::<Vec<_>>()
    };
    ([$t:ty]) => {
        rl().split_whitespace()
        .map(|x| x.parse().unwrap())
        .collect::<Vec<$t>>()
    };
    ($t:ty) => {
        rl().parse::<$t>().unwrap()
    };
    ($($t:ty),*) => {
        {
            let line =rl();
            let mut iter = line.split_whitespace();
            ($(iter.next().unwrap().parse::<$t>().unwrap()),*)
        }
    };
}
fn rl() -> String {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).unwrap();
    line.trim().to_string()
}

fn main() {
    let mut n = get!(i32);
    let mut ans = 0;
    if n / 1000 == 2 {
        ans += 1;
    }
    n %= 1000;
    if n / 100 == 2 {
        ans += 1;
    }
    n %= 100;
    if n / 10 == 2 {
        ans += 1;
    }
    if n % 10 == 2 {
        ans += 1;
    }
    println!("{}", ans);
}


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

ans=0
for i in range(n):
  ans+=min(b[i],a[i]+a[i+1])
  n1=min(a[i],b[i])
  b[i]-=n1
  a[i+1]=max(0,a[i+1]-b[i]) 
  
print(ans)
  

Measured memory_bytes: 24196
import java.util.Scanner;

public class Main {
	public static void main (String[] args){
			Scanner sc = new Scanner(System.in);
			String[] section;
			String newstr = "";
			String line = sc.nextLine();
			if(line.indexOf("apple") != -1){
				section = line.split("apple");
				for(int i = 0; i < section.length; i++){
					section[i] = section[i].replace("peach", "apple");
					newstr += section[i];
					if(i != section.length - 1){newstr += "peach";}
				}
				if(line.lastIndexOf("apple") == line.length() - "apple".length()){
					newstr += "peach";
				}
			}else{
				newstr = line.replace("peach", "apple");
			}
			System.out.println(newstr);
			
	}
}

Measured memory_bytes: 12000
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <iterator>
#include <cmath>
#include <deque>
using namespace std;

int main()
{
    if (fopen("input.txt", "r")) {
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    string s;
    cin >> n >> s;
    if (n & 1) {
        cout << "No\n";
        return 0;
    }
    bool flag = true;
    for (int i = 0; i != n / 2; ++i)
        if (s[i] != s[n / 2 + i]) {
            flag = false;
            break;
        }
    if (flag)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

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

const int MAX = 510000;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1; finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  int h, w, a, b;
  cin>>h>>w>>a>>b;
  COMinit();
  long long ans = COM(h + w - 2, h - 1);
  for (int i=1; i<=a; i++) {
    long long tmp1 = COM(h - i +  b - 1, b - 1);
    long long tmp2 = COM(i - 1 + w - b - 1, w - b - 1);
    ans -= tmp1 * tmp2 % MOD;
    if (ans < 0) {
      ans += MOD;
    }
  }
  cout<<ans<<endl;

}

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

int main(){
    int a, b;
    cin >> a >> b;
    if( a == b){
        rep(i,b) cout << a;
        cout << endl;
    }else{
        if(a > b) swap(a,b);
        rep(i,b) cout << a;
        cout << endl;
    }
}

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

template <typename T>
struct Edge { int src, dst; T cost;
    Edge(int dst, T cost) : src(-1), dst(dst), cost(cost) { }
    Edge(int src, int dst, T cost) : src(src), dst(dst), cost(cost) { }
};
template <typename T> using Edges = vector<Edge<T>>;
template <typename T> using WeightedGraph = vector<Edges<T>>;
template <typename T> using Matrix = vector<vector<T>>;

vector<int> ticket;
template <typename T>
vector<vector<T>> dijkstra(const WeightedGraph<T> &g, int s, int n) {
    const T INF = numeric_limits<T>::max();
    vector<vector<T>> dp(g.size(), vector<T>(1 << n, INF));
    using Pi = tuple<T, int, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    dp[s][0] = 0; que.emplace(dp[s][0], s, 0);
    while (!que.empty()) {
        T cost; int v, ts; tie(cost, v, ts) = que.top(); que.pop();
        if (dp[v][ts] < cost) continue;
        for (auto &e: g[v]) {
            int nv = e.dst; T nc = e.cost;
            for (int t = 0; t < n; t++) if (!(ts >> t & 1)) {
                T tmp = dp[v][ts] + nc / ticket[t];
                T &nxt = dp[nv][ts | 1 << t];
                if (nxt > tmp) {
                    nxt = tmp;
                    que.emplace(nxt, nv, ts | 1 << t);
                }
            }
        }
    }
    return dp;
}

int main() {
    const auto INF = numeric_limits<double>::max();
    int n, m, p, a, b;
    while (cin >> n >> m >> p >> a >> b, a--, b--, m) {
        ticket.resize(n);
        for (int &ti: ticket) cin >> ti;
        WeightedGraph<double> g(m);
        while (p--) {
            int x, y, z; cin >> x >> y >> z; x--, y--;
            g[x].emplace_back(y, z);
            g[y].emplace_back(x, z);
        }
        auto res = dijkstra(g, a, n)[b];
        double mi = *min_element(res.begin(), res.end());
        if (mi == INF) {
            cout << "Impossible" << endl;
        } else {
            cout << mi << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 4560
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int N = sc.nextInt();
        final int M = sc.nextInt();

        final int[] cities = new int[N];

        for (int i = 0; i < M; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            cities[a-1]++;
            cities[b-1]++;
        }

        for (int city: cities) {
            System.out.println(city);
        }
    }
}


Measured memory_bytes: 21588
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <sstream>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    int a,b;
    cin >> a >> b;
    int cnt = 0;
    rep2(i,a,b+1)
    {
        string s = to_string(i);
        if(s.substr(0,1)==s.substr(4,1)
            && s.substr(1,1)==s.substr(3,1))
            ++cnt;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
/* ex3_3
   seira3 */

#include<stdio.h>
#include<stdlib.h>

int main(void){
    int number, base; //変数宣言
    scanf("%d %d",&number,&base); //入力
    int count = 0; //割れた回数をカウントする変数を宣言
    while(number>0){ //割れた回数をカウントするwhile文
        number = number/base; //割る
        count++; //countに1を足す
    }
    printf("%d\n",count); //答えであるcountを出力
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<atcoder/dsu>
#define ll long long int
using namespace atcoder;
using namespace std;
 
int main(){
  int n, m;
  cin >> n >> m;
  
  dsu d(n);
  for (int i=0; i<m; i++){
  	int a, b;
    cin >> a >> b;
    a--; b--;
    d.merge(a, b);
  }
  
  cout << (int)d.groups().size() - 1 << endl;
}

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

typedef long long int ll;
typedef long double ld;

//****************************************************                
#define lp(var,start,end) for (ll var = start; var <end ; ++var)
#define rlp(var,start,end) for(ll var = start; var>=end ; var--)
#define pb push_back
#define mp make_pair
#define pf push_front
#define ff first
#define ss second
#define vll vector<ll>
#define pll pair<ll,ll> 
#define vpll vector<pll>
#define all(X) X.begin(),X.end()
#define endl "\n" //comment it for interactive questions
#define trace1(a) cerr << #a << ": " << a << endl;
#define trace2(a,b) cerr << #a << ": " << a << " " << #b << ": " << b << endl;
#define trace3(a,b,c) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << endl;
#define trace4(a,b,c,d) cerr << #a << ": " << a << " " << #b << ": " << b << " " << #c << ": " << c << #d << ": " << d << endl;
#define FAST_IO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
        //*******************************************************
//Some Functions

const ll MOD = (ll)1e9+7; //change it for other mods

ll powmod(ll a,ll b)
{
   ll res = 1;
   while(b > 0) {
      if(b & 1) res = (res * a) % MOD;
      a = (a*a)%MOD;
      b = b >> 1; 
  }
  return res % MOD;
}

void solve(ll testnum)
{
    ll n;
    cin >> n;
    vll a(n);
    for(ll i=0;i<n;i++) {
    	cin >> a[i];
    }
    ll ans = 0;
    for(ll i=1;i<n;i++) {
    	if(a[i] < a[i-1]) {
    		ans += (a[i-1] - a[i]);
    		a[i] = a[i-1];
    	}
    }
    cout << ans << "\n";
}

int main()
{
    FAST_IO;
    #ifdef STIO 
      freopen("input.txt" , "r", stdin);
      freopen("output.txt" , "w", stdout);
    #endif
    ll t = 1;
    // cin >> t;
    for (ll i = 1; i <= t; i++) {
        // cout << "Case #" << i << ": ";
        solve(i);
    }
}

Measured memory_bytes: 4716
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#define PI 3.141592653589793
#define MOD 1000000007

long int combination(long int n, long int r);

//qsort用、昇順
int compare_int(const void *a, const void *b)
{
	return *(int*)a-*(int*)b;
}

long int combination(long int n, long int r)
{
	if(r>n-r) r = n-r;
	if(r == 0) return 1;
	else if(r == 1) return n;
	return (combination(n-1, r) + combination(n-1, r-1));
	//大きくなるとき
	/*
	long int tmp1, tmp2, tmp3;
	tmp1 = combination(n-1, r);
	if(tmp1>=MOD) tmp1 = tmp1%MOD;
	tmp2 = combination(n-1, r-1);
	if(tmp2>=MOD) tmp2 = tmp2%MOD;
	tmp3 = tmp1+tmp2;
	if(tmp3>=MOD) tmp3 = tmp3%MOD;
	return (tmp3);
	*/
}


int main(){
	long int n, t;
	scanf("%ld%ld", &n, &t);
	long int time[n];
	long int ans=0;
	scanf("%ld", &time[0]);
	for(int i=1; i<n; i++){
		scanf("%ld", &time[i]);
		if(time[i]-time[i-1]>t) ans += t;
		else ans += time[i]-time[i-1];
		//printf("%ld\n", ans);
	}
	ans += t;
	
	printf("%ld\n", ans);
	
	return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

using namespace std;

#define f first
#define s second

typedef pair<int, int> P;
typedef pair<int, P> P2;

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

int W, H;
bool yoko[31][31];
bool tate[31][31];

int bfs(){
  int cnt = 1;
  set<P> check;
  queue<P2> que;
  que.push(P2(cnt, P(0, 0)));
  
  while(!que.empty()){
    P2 t = que.front();
    que.pop();
    if(check.find(P(t.s.f, t.s.s)) == check.end()){
      check.insert(P(t.s.f, t.s.s));
      if(t.s.f == W-1 && t.s.s == H-1) return t.f;
      for(int i = 0 ; i < 4 ; i++){
	P2 tmp = t;
	tmp.s.f += dx[i];
	tmp.s.s += dy[i];
	tmp.f++;
	if(tmp.s.f < 0 || tmp.s.f >= W || tmp.s.s < 0 || tmp.s.s >= H) continue;
	if(dx[i] == 1 && tate[t.s.s][t.s.f]) continue;
	if(dx[i] == -1 && tate[tmp.s.s][tmp.s.f]) continue;
	if(dy[i] == 1 && yoko[t.s.s][t.s.f]) continue;
	if(dy[i] == -1 && yoko[tmp.s.s][tmp.s.f]) continue;
	que.push(tmp);
      }
    }
  }
  return 0;
}


int main(){
  while(cin >> W >> H){
    if(W == 0 && H == 0) break;
    memset(tate, 0, sizeof(tate));
    memset(yoko, 0, sizeof(yoko));
    
    for(int i = 0 ; i < 2*H-1 ; i++){
      if(i % 2 == 0){
	for(int j = 0 ; j < W-1 ; j++){
	  cin >> tate[i/2][j];
	}
      }
      else{
	for(int j = 0 ; j < W ; j++){
	  cin >> yoko[i/2][j];
	}
      }
    }
    
    cout << bfs() << endl;
  }

  return 0;
}

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

typedef long long ll;
#define MOD = 1000000007;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define ALL(a) begin(a),end(a)
#define COUNTOF(a) (sizeof(a)/sizeof(a[0]))
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
template<class T> void cout_v(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << endl; }
template<class K, class V> void cout_v(map<K, V>& m)
{ for(auto it=m.begin();it!=m.end();it++)cout<<it->first<<":"<<it->second<<endl;}
template<class T> void cout_h(const vector<T>& c)
{ for (int i = 0; i < c.size(); i++) cout << c[i] << (i==c.size()-1?"\n":" "); }
template<class T> inline bool chmin(T& a, T b) {return a>b?a=b,true:false;}
template<class T> inline bool chmax(T& a, T b) {return a<b?a=b,true:false;}
inline int powi(int x,int y) {int p=1; while(y--) p*=x; return p;}
template<class T> inline bool is_overlap(const T& a, const T& b, const T& p, const T& q)
{ return p <=b && a <= q; }
#define SP << " " <<
#define FMT(a) #a<<":"<<a 
#define FMT2(a,b) #a<<":"<<a<<", "<<#b<<":"<<b 
#define FMT3(a,b,c) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c 
#define FMT4(a,b,c,d) #a<<":"<<a<<", "<<#b<<":"<<b<<", "<<#c<<":"<<c<<", "<<#d<<":"<<d 
#define ANS(a) cout<<a<<endl
void yes(bool f){cout<<(f?"yes":"no")<<endl;}
void Yes(bool f){cout<<(f?"Yes":"No")<<endl;}
void YES(bool f){cout<<(f?"YES":"NO")<<endl;}

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

    int N; cin >>N;
    vector<int> T(N); cin >> T;
    int M; cin >>M;

    int Tsum = accumulate(ALL(T), 0);

    int P, X;
    rep(i, M) {
        cin >> P >> X;
        cout << Tsum -  T[P-1] + X << endl;
    }
}


Measured memory_bytes: 256
module UnionFind

implicit none
integer,allocatable,dimension(:)::par
!parentより

contains

recursive function root(x) result(res)
integer :: x,res
if(par(x) /= x) par(x)=root(par(x))
res = par(x)
end function

subroutine unite(x,y)
integer :: x,y
x = root(x)
y = root(y)
if(x /= y) par(x) = y
end subroutine

end module UnionFind

use UnionFind

integer N,M
integer,allocatable,dimension(:)::p
integer x,y
integer ans
read*,N,M
allocate(p(N),par(N))
read*,p

!par初期化
do i=1,N
  par(i)=i
end do


do i=1,M
  read*,x,y
  call unite(x,y)
end do

ans=0
do i=1,N
  if(root(i)==root(p(i)))ans=ans+1
end do

print"(i0)",ans
end

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

int n;
vector<long long> v,a;
long long suma,sumb;

main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		long long x;
		scanf("%lld",&x);
		a.push_back(x);
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		long long x;
		scanf("%lld",&x);
		if(x>a[i])
		{
			ans++;
			suma+=a[i];
			sumb+=x;
		}
		else
		{
			v.push_back(a[i]-x);
		}
	}
	int ex=v.size()-1;
	sort(v.begin(),v.end());
	sumb-=suma;
	while(sumb>0&&ex>=0)
	{
		sumb-=v[ex];
		ex--;
		ans++;
	}
	if(sumb>0)
		printf("-1");
	else
		printf("%d",ans);
}

Measured memory_bytes: 2548
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define MOD 1000000007ULL;
#define rep(i,n) for(int i=0;i<n;i++)


int main() {
	ll X,K,D;
  	cin>>X>>K>>D;
  
  	if(X>0){
     	if(log(X)<log(K)+log(D)){
        	if((X/D)%2==K%2){
             	 cout<<X%D<<endl;
            }
          	else{
             	 cout<<abs(X%D-D)<<endl;
            }
        }
		else{
         	cout<<X-K*D<<endl; 
        }
      	return 0;
    }
  	else{
     	if(log(abs(X))<log(K)+log(D)){
         	 if((abs(X/D))%2==K%2){
             	 cout<<((-X)%D)<<endl;
            }
          	else{
             	 cout<<abs(((-X)%D)-D)<<endl;
            }
        }
      	else{
         	cout<<abs(X+K*D)<<endl; 
        }
      	return 0;
    }
}

Measured memory_bytes: 3836
N = int(input())
A = list(map(int, input().split()))

A.insert(0, 0)
A.append(0)

money = 0

for i in range(1, N + 2):
    money += abs(A[i] - A[i - 1])

for i in range(1, N + 1):
    s = money + abs(A[i - 1] - A[i + 1]) - (abs(A[i - 1] - A[i]) + abs(A[i] - A[i + 1]))
    print(s)

Measured memory_bytes: 20496
#include <vector>
#include <map>
#include <string>
#include <tuple>

using namespace std;

#define FOR(i,a,b) 

int N;
char S[50];


map<tuple<int, int, string>, long long> memo;
long long go(int L, int R, string suf)
{
	if (suf.size() > R-L) return 0;
	if (L == R) return suf.empty();

	auto entry = tuple<int, int, string>(L, R, suf);
	if (memo.find(entry) != memo.end()) return memo[entry];


	long long result = 0;
	if(!suf.empty())
	{
		if(S[L] == suf.back())
			result += go(L+1, R, suf.substr(0, suf.size() - 1));
		for(int i=L+1; i<R;++i)
			if(S[L] == S[i])
				result += go(L+1,i,string(S+i+1,S+R)+suf);
	}
	else
	{
		for(int i=L+1; i<R;++i)
			if(S[L] == S[i])
				result += 2*go(L+1,i,string(S+i+1,S+R));
	}
	return memo[entry] = result;
}


int main() {
	scanf("%d", &N);
	scanf("%s", S);
	printf("%lld\n", go(0,2*N,string()));
}

Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


N, X = map(int, input().split())
x = [0] + list(map(int, input().split()))


r = [0, 0]
rr = 0
for j in range(1, N+1):
    rr += x[j]
    r.append(rr)


def f(k):
    # debug("compute %s" % k)
    s = 0
    m = N // k + 1
    # s += 2*(r[N+1] - r[(m-1)*k])
    # for l in range(k):
    #     n = (N-l) // k
    #     s += x[l+k*n]*2
    s += 2*(r[N+1] - r[N-k+1])
    for i in range(1, m+1):
        # if k*(m-i+1) > N:
        #     t = r[N+1]
        # else:
        #     t = r[k*(m-i+1)]
        t = r[N-k*(i-1)+1]
        if N-k*i+1 < 0:
            u = 0
        else:
            u = r[N-k*i+1]
        s += (2*i+1)*(t-u)
    return s


# def f(k):
#     # debug("compute %s" % k)
#     s = 0
#     # m = N // k + 1
#     # s += 2*(r[N+1] - r[(m-1)*k])
#     for l in range(k):
#         n = (N-l) // k
#         s += x[l+k*n]*2
#         for i in range(1, n+2):
#             s += (2*i+1)*x[l+k*(n-i+1)]
#     return s


# def g(k):
#     s = 0
#     for l in range(k):
#         n = (N-l) // k
#         s += x[l+k*n]
#         for i in range(1, n+2):
#             if l+k*(n-i) < 0:
#                 y = 0
#             else:
#                 y = x[l+k*(n-i)]
#             s += ((i+1)**2)*(x[l+k*(n-i+1)] - y)
#     return s


candidates = [f(k) + k*X + N*X for k in range(1, N+1)]
debug(candidates)

# cand = [g(k) + k*X + N*X for k in range(1, N+1)]
# debug(cand)

ans = min(candidates)
print(ans)


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

using namespace std;

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

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

    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt++;
        if (a[i + 1] != a[i]) {
            ans += cnt / 2;
            cnt = 0;
        }
    }

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

Measured memory_bytes: 256
//agc003_a.cpp
//Sat Nov  3 09:58:48 2018

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#define INTINF 2147483647
#define LLINF 9223372036854775807
using namespace std;
using ll=long long;
typedef pair<int,int> P;

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

	int direction[4];
	fill(direction,direction+4,0);
	for (int i=0;i<s.size();i++){
		if (s[i]=='N'){
			direction[0]++;
		}else if (s[i]=='S'){
			direction[1]++;
		}else if (s[i]=='E'){
			direction[2]++;
		}else if (s[i]=='W'){
			direction[3]++;
		}
	}

	int flag = 0;
	if ((direction[0]>0 && direction[1]>0) ||
		(direction[0]==0 && direction[1]==0)
		){
		if ((direction[2]>0 && direction[3]>0) ||
			(direction[2]==0 && direction[3]==0)
			){
			flag = 1;
		}
	}

	if (flag == 1){
		cout << "Yes" << endl;
	}else {
		cout << "No" << endl;
	}

}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map.Entry;


import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			final int N = sc.nextInt();
			final int SIZE = 1000000;
			
			int[] cnt = new int[SIZE + 1];
			for(int i = 0; i < N; i++) {
				cnt[sc.nextInt()]++;
			}
			
			
			int answer = 0;
			for(int i = 1; i <= SIZE; i++) {
				if(cnt[i] == 0) { continue; }
				
				if(cnt[i] == 1) {
					answer++;
				}
				
				for(int j = 2 * i; j <= SIZE; j += i) {
					cnt[j] = 0;
				}
			}
			
			System.out.println(answer);
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}


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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

ll A[100005];
ll B[100005];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    memset(B, 0, sizeof(B));
    ll mx = 0;
    REP(i, N) {
        cin >> A[i];
        B[A[i]]++;
        mx = std::max(mx, A[i]);
    }
    ll ans = 0;
    FOR(i, mx + 2, 1) {
        ans = std::max(ans, B[i - 1] + B[i] + B[i + 1]);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<functional>
#include<iomanip>
#include<cmath>
#include<queue>
#include<limits>
#include<cassert>
#include<set>
#include<tuple>
#include<map>
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
typedef long long ll;
using namespace std;

int main() {
	int R,G; cin >> R >> G;
	cout << 2*G - R << endl;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
)

func main(){
	reader := bufio.NewReader(os.Stdin)
	writer := bufio.NewWriter(os.Stdout)
	defer writer.Flush()

	var (
		S,ans string
		ok, C bool
		length int = 0
	)
	ok = true
	C = false

	fmt.Fscan(reader, &S)
	length = len(S)

	for i, c := range S {
		if i == 0 { 
			ok = ok && (c == 'A')
		} else {
			if 1 < i && i < length-1 && c == 'C' {
				ok = ok && !C
				C = true
			} else {
				ok = ok && (97 <= c && c <= 122)
			}
		}
	}


	if ok && C {
		ans = "AC"
	} else {
		ans = "WA"
	}

	fmt.Fprintln(writer, ans)
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<map>
#include<cstdio>
#define ll long long
#define lson (rt<< 1)
#define rson (rt<< 1 | 1)
#define gmid ((l+r)>> 1 )
using namespace std;

const int maxn=200050;

int a[maxn],n,m,k=0;

int main()
{
	cin>>n;
	ll ans=0;
	for(int i=1;i<=n;++i)
	  cin>>a[i];
	sort(a+1,a+n+1);
	m=n-1;
	while(m>0)
	  {
	  	  m--;
	  	  k++;
	  	  ans+=a[n-(k/2)];
	  	  //cout<<a[n-(k/2)]<<endl;
	  }
	cout<<ans<<endl;  
}


Measured memory_bytes: 4412
#include <cstdio>
#include <cmath>

double rad(double ang)
{
    return ang / 180.0 * acos(-1);
}

int main()
{
    double n, k;
    scanf("%lf %lf", &n, &k);
    printf("%.10f\n",
           n * sin(rad(180 / n)) * cos(rad(180 * k / n)) / cos(rad(180 * (k - 1) / n)));
    return 0;
}

Measured memory_bytes: 2880
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>

using namespace std;

#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define REV(i,n) for(ll (i) = (n) - 1;(i) >= 0;--i)
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {REP(WW,n)cerr << v[WW] << ' ';cerr << endl;}
#define SHOW2d(v,WW,HH) {REP(W_,WW){REP(H_,HH)cerr << v[W_][H_] << ' ';cerr << endl;}}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 998244353

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

void cal_score(vector<int> &c, vector<vector<int>> &s, int &score, vector<int> v, vector<int> &mai) {
	int n = v.size() - 1;
	score += s[n][v.back()];
	REP(i, 26)mai[i]++;
	mai[v.back()] = 0;
	REP(i, 26)score -= c[i] * mai[i];
}

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

	ll d;cin >> d;
	vector<int> c(26);REP(i, 26)cin >> c[i];
	vector<vector<int>> s(d, vector<int>(26));
	REP(i, d)REP(j, 26)cin >> s[i][j];

	vector<pair<int, pair<vector<int>, vector<int>>>> lis;
	REP(i, 26){
		vector<int> v(1, i);
		vector<int> mai(26, 0);
		int score = 0;
		cal_score(c, s, score, v, mai);
		lis.EB(score, MP(v, mai));
	}

	REP(i, d-1){
		sort(ALL(lis), greater<pair<int, pair<vector<int>, vector<int>>>>());
		lis.resize(min((int)lis.size(), 280));
		vector<pair<int, pair<vector<int>, vector<int>>>> now;

		for(auto seica: lis){
			REP(i, 26){
				vector<int> v = seica.SE.FI;v.PB(i);
				vector<int> mai = seica.SE.SE;
				int score = seica.FI;
				cal_score(c, s, score, v, mai);
				now.EB(score, MP(v, mai));
			}
		}

		lis = now;
	}

	sort(ALL(lis), greater<pair<int, pair<vector<int>, vector<int>>>>());
	REP(i, d){
		cout << (lis[0].SE.FI[i]+1) << endl;
	}


	return 0;
}


Measured memory_bytes: 27072
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int N=205;
int n,mrk[N],dep[N],ans;vector<int>E[N];queue<int>Q;
void dfs(int u,int c){
	mrk[u]=c;
	for(int v:E[u])
		if(!~mrk[v])dfs(v,c^1);
		else if(mrk[v]!=(c^1))puts("-1"),exit(0);
}
void bfs(int u){
	memset(dep,63,sizeof(dep));
	dep[u]=1;Q.push(u);
	while(!Q.empty()){
		int u=Q.front();Q.pop();
		for(int v:E[u])
			if(dep[v]>dep[u]+1)
				dep[v]=dep[u]+1,Q.push(v);
	}
	for(int i=1;i<=n;++i)ans=max(ans,dep[i]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			int x;scanf("%1d",&x);
			if(x)E[i].push_back(j);
		}
	memset(mrk,-1,sizeof(mrk));
	dfs(1,0);
	for(int i=1;i<=n;++i)bfs(i);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	static Main instance = new Main();

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		//入力値
		long A = scan.nextLong();
		long B = scan.nextLong();
		long C = scan.nextLong();
		long K = scan.nextLong();

		//WK変数
		long result = 0L;

		if (A >= K) {
			result = K;
		} else if (A + B >= K) {
			result = A;
		} else {
			result = A - (K - A - B);
		}

		//演算

		//結果出力
		System.out.println(result);
	}
}

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

int main(){
    vector<int> v;
    for(int i=0; i<5; i++){
        int tmp;
        cin>>tmp;
        v.push_back(tmp);
    }
    for(int i=0; i<5; i++){
        if(v[i]==0){
            cout<<i+1<<endl;
            return 0;
        }
    }

    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <numeric> //lcm
#include <iomanip> //double精度 setprecision


#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define all(vec) (vec).begin(),(vec).end()

#define debug(vec) for(auto v : vec) cout << v << " "; cout << endl;

#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cout << v << " "; cout << endl; } 

using namespace std;

typedef long long ll;

const ll INF = 1000000000; //10^10
//const ll MOD = 998244353;
const ll MOD = 1000000007;

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



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

	ll h,w,k; cin >> h >> w >> k;
	vector<vector<ll>> s(h, vector<ll>(w));
	rep(i,h) { 
	  string _s;
		cin >> _s;
	  rep(j,w) s[i][j] = (ll) _s[j] - '0';  
	}

	ll ans = INF;
	rep(i, pow(2,h-1)) {
	  ll ans0 = 0;
	  set<int> st;
		rep(j,h) if ((i >> j) % 2) st.insert(j);
		ans0 = st.size();
		
		vector<vector<ll>> sum(h + 1, vector<ll>(w + 1, 0));
		rep1(i, h) rep(j, w) {
			sum[i][j + 1] = sum[i][j] + s[i - 1][j];
		}
		rep1(j, w) rep(i, h) {
			if(st.find(i-1) == st.end()) sum[i + 1][j] += sum[i][j];
		}

		bool valid = true;
		st.insert(h - 1);
		map<int, int> diff;
		rep(j, w + 1) {
			bool line = false;
			for (auto l : st) {
				l++;
				if (sum[l][j] - diff[l] > k) {
					if (sum[l][j - 1] == 0) { valid = false; break; }
					//cout << "l = " << l << ",j = " << j << ", diff = " << diff[l] <<  endl;
					line = true;
				}
			}
			if (line) { 
				for (auto l : st) diff[l+1] = sum[l+1][j - 1];
			  ans0++;
			}
		}
			
		if (valid) chmin(ans, ans0);
		//cout << ans0 << endl; //
	}

	cout << ans << endl;
} 


Measured memory_bytes: 384
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto S = readln.chomp.to!(dchar[]);
    auto T = readln.chomp.to!(dchar[]);
    foreach (i; 0..S.length) {
        S = S[1..$] ~ S[0];
        if (S == T) {
            writeln("Yes");
            return;
        }
    }
    writeln("No");
}

Measured memory_bytes: 380
#include<bits/stdc++.h>
using namespace std;
int m,d;
int main(){
    scanf("%d%d",&m,&d);
    int ans=0;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=d;j++){
            if(j>=10&&(j/10)>=2&&(j%10)>=2){
                if((j/10)*(j%10)==i)ans++;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
AB = [LIST() for _ in range(N)]
AB.sort(key=lambda x:-x[0])
print(AB[0][0]+AB[0][1])


Measured memory_bytes: 33376
function parse_numbers(s)
    pieces = split(s, ' ', keepempty=false)
    map(pieces) do piece
        parse(Int64, piece)
    end
end

n = parse(Int64, readline();)
A = parse_numbers(readline();)

total = 0
max = A[1]

for i in 2:n
    if A[i] < max
        global total += max - A[i]
    else
        global max = A[i]
    end
end

println(total)

Measured memory_bytes: 201364
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		double ans = 0;
		for (int i = 0; i < n; i++) {
			double x = sc.nextDouble();
			String u = sc.next();
			if (u.equals("JPY")) {
				ans += x;
			} else {
				ans += x * 380000.0;
			}
		}
		System.out.println(ans);
		sc.close();

	}
}

Measured memory_bytes: 25172
#include <stdio.h>
#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

int n, a[100000]; long long s[200000];

inline int reader()
{
	int ret = 0;

	while (true)
	{
		char c = getchar();

		if (c == '\n') break;

		ret = (ret << 1) + (ret << 3) + c - 48;
	}

	return ret;
}

long long sum(int l, int r)
{
	return s[r] - s[l];
}

int main()
{
	n = reader();

	for (int i = 0; i < n; i++) a[i] = reader();

	s[0] = 0; for (int i = 1; i < 2 * n; i++) s[i] = s[i - 1] + a[(i - 1) % n];

	long long ret = 0, sums = s[n];

	for (int i = 0; i < n; i++)
	{
		int posr1 = lower_bound(s, s + 2 * n, s[i] + sums / 3) - s;
		int posr2 = lower_bound(s, s + 2 * n, s[i] + sums * 2 / 3) - s;

		ret = max(ret, min({ sum(i, posr1), sum(posr1--, posr2), sum(posr2, i + n) }));
		ret = max(ret, min({ sum(i, posr1), sum(posr1, posr2), sum(posr2, i + n) }));
	}

	printf("%lld\n", ret);

	return 0;
}

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

typedef struct List {
	struct List *next;
	int data, dist;
} Queue;

int main()
{
	int i, N, a[100001];
	scanf("%d", &N);
	for (i = 1; i <= N; i++) scanf("%d", &(a[i]));
	
	int flag[100001] = {0, 1};
	Queue q[100001], *p, *tail = &(q[1]);
	tail->next = NULL;
	tail->data = a[1];
	tail->dist = 0;
	for (p = tail; p != NULL; p = p->next) {
		if (flag[p->data] == 0) {
			flag[p->data] = 1;
			q[p->data].next = NULL;
			q[p->data].data = a[p->data];
			q[p->data].dist = p->dist + 1;
			tail->next = &(q[p->data]);
			tail = tail->next;
			if (p->data == 2) break;
		}
	}
		
	if (p != NULL) printf("%d\n", tail->dist);
	else printf("-1\n");
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 4072
def mod_fact(n, mod):
    ans = 1
    for i in range(2, n + 1):
        ans = ans * i % mod
    return ans

mod = 10 ** 9 + 7

N, M = map(int, input().split())

if N == M:
    print(2 * mod_fact(N, mod) ** 2 % mod)
elif abs(N - M) == 1:
    print(mod_fact(min(M, N), mod) ** 2 * max(M, N) % mod)
else:
    print(0)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;

#define INF (i64)(1e18)
#define MOD (i64)(1e9+7)
#define REP(i, n) for(i64 i = 0; i < (n); i++)
#define RREP(i, n) for(i64 i = (n)-1; i >= 0; i--)
#define RANGE(i, a, b) for(i64 i = (a); i < (b); i++)
#define RRANGE(i, a, b) for(i64 i = (b)-1; i >= (a); i--)
#define ALL(v) (v).begin(), (v).end()
#define SIZE(v) ((i64)(v).size())
template<class T> inline void chmax(T &a, const T &b) { if (a < b) a = b; }
template<class T> inline void chmin(T &a, const T &b) { if (a > b) a = b; }

struct UnionFind {
  vector<i64> par, sz;
  UnionFind(i64 n) : par(n), sz(n, 1) {
    REP(i, n) par[i] = i;
  }
  i64 root(i64 x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(i64 x, i64 y) {
    i64 rx = root(x), ry = root(y);
    if (rx == ry) return;
    if (size(rx) < size(ry)) swap(rx, ry);
    par[ry] = rx;
    sz[rx] += sz[ry];
  }
  i64 size(i64 x) {
    return sz[root(x)];
  }
  bool same(i64 x, i64 y) {
    return root(x) == root(y);
  }
};

int main() {
  i64 n, m;
  cin >> n >> m;
  vector<i64> a(m), b(m);
  REP(i, m) {
    cin >> a.at(i) >> b.at(i);
    a[i]--;
    b[i]--;
  }

  UnionFind uf(n);
  i64 memo = n*(n-1)/2;
  vector<i64> ans(m);
  RREP(i, m) {
    ans[i] = memo;
    if (uf.same(a[i], b[i])) continue;
    memo -= uf.size(a[i])*uf.size(b[i]);
    uf.unite(a[i], b[i]);
  }
  for(auto& x : ans) cout << x << endl;

  return 0;
}


Measured memory_bytes: 7188
#!/usr/bin/env python

n = int(input())
a = list(map(int, input().split()))

ans = 1000100
ch = 0 
for ch in range(min(a), max(a)+1):
    tmp = 0 
    for i in range(n):
        tmp += (a[i]-ch)**2
    if tmp <= ans:
        ans = tmp 
print(ans)


Measured memory_bytes: 9168
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>

using namespace std;

int main(){
	int count=0;
	string S;
	cin >> S;
	for(int i=0; i<S.size()-1; i++){
		if(S[i]!=S[i+1])
		count+=1;
	}
	cout << count << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<ll>::iterator sit;
typedef map<ll,ll>::iterator mit;

char br[2001][2001];
int b[2001][2001];
int a[2001][2001];


int L[2111];
int R[2111];
int solve(vi &vec)
{
	int n = vec.size();
	L[0] = 0;
	stack<ii> S;
	S.push(mp(vec[0],0));
	for(int i=1;i<n;i++)
	{
		while(!S.empty()&&S.top().fi>=vec[i])
		{
			S.pop();
		}
		if(S.empty()) L[i]=0;
		else L[i]=S.top().se+1;
		S.push(mp(vec[i],i));
	}
	while(!S.empty()) S.pop();
	S.push(mp(vec[n-1],n-1));
	R[n-1]=n-1;
	for(int i=n-2;i>=0;i--)
	{
		while(!S.empty()&&S.top().fi>=vec[i])
		{
			S.pop();
		}
		if(S.empty()) R[i]=n-1;
		else R[i]=S.top().se-1;
		S.push(mp(vec[i],i));
	}
	int ans=0;
	for(int i=0;i<n;i++)
	{
		ans=max(ans,(R[i]-L[i]+2)*vec[i]);
	}
	return ans;
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>br[i][j];
		}
	}
	for(int i=1;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(br[i][j]==br[i-1][j])
			{
				b[i-1][j]=1;
			}
			else
			{
				b[i-1][j]=0;
			}
		}
	}
	/*
	for(int i=1;i<n;i++)
	{
		for(int j=1;j<m;j++)
		{
			if(b[i][j]==b[i][j-1])
			{
				a[i-1][j-1]=1;
			}
			else
			{
				a[i-1][j-1]=0;
			}
		}
	}
	R=n-1;C=m-1;
	cout<<maxRectangle(a)<<'\n';
	*/
	for(int i = 0; i < n - 1; i++)
	{
		a[i][m-1] = 1;
		for(int j = m - 2; j >= 0; j--)
		{
			if(b[i][j]==b[i][j+1]) a[i][j]=a[i][j+1]+1;
			else a[i][j]=1;
			//cerr<<i<<' '<<j<<' '<<a[i][j]<<' '<<b[i][j]<<' '<<b[i][j+1]<<'\n';
		}
	}
	int ans = 0;
	for(int i = 0; i < m; i++)
	{
		vi vec;
		for(int j = 0; j < n - 1; j++)
		{
			vec.pb(a[j][i]);
		}
		ans=max(ans,solve(vec));
	}
	ans=max(ans,max(n,m));
	cout<<ans<<'\n';
}


Measured memory_bytes: 35456
#include <iostream>
#include <stdio.h>

using namespace std;

int main(void){
  int a_1 = 2;
  int x;
  int s = 0;

  while(scanf("%d", &x) != EOF ){
    if(x == 1){
      printf("%d\n", a_1);
    }else{

      s += a_1;
      for(int i = 2; i <= x; i++){
        s += i;
      }
      printf("%d\n", s);
    }
    s = 0;
  }

  return 0;
}


Measured memory_bytes: 3176
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int mod = 1e9+7;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  mint sum = 0;
  rep(i,n) cin >> a[i], sum += a[i];
  mint res = 0;
  for (int i = 0; i < n; i++) {
    res += (sum - a[i]) * a[i];
  }
  cout << res / 2 << endl;
  return 0;
}


Measured memory_bytes: 3996
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	if((a+b)%3==0||a%3==0||b%3==0)
		printf("Possible\n");
	else
		printf("Impossible\n");

	return 0;
}

Measured memory_bytes: 256
use std::io::Read;

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

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

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();
    let mut abs_array: Vec<isize> = Vec::new();
    let mut minus_count: usize = 0;
    for _ in 0..n {
        let a: isize = iterator.next().unwrap().parse().unwrap();
        if a < 0 {
            minus_count += 1;
            abs_array.push(-a);
        } else {
            abs_array.push(a);
        }
    }

    if minus_count % 2 == 0 {
        let ans: isize = abs_array.iter().sum();
        return ans.to_string();
    }

    abs_array.sort();

    let mut ans: isize = -abs_array[0];
    for i in 1..n {
        ans += abs_array[i];
    }
    return ans.to_string();
}


Measured memory_bytes: 8444
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a.at(i);
	for (int i = 0; i < n; i++) {
		if (a.at(i) % 2 == 1) continue;
		else {
			if (a.at(i) % 3 == 0 || a.at(i) % 5 == 0)continue;
			else {
				cout << "DENIED" << endl;
				return 0;
			}
		}
	}
	cout << "APPROVED" << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[]args) {
		Scanner sc = new Scanner(System.in);
		
		for(;;) {
			int input_num = sc.nextInt();
			if(input_num == 0) break;
			int count = 0;
			List<String> step_list = new ArrayList<String>();
			for(int i = 0; i < input_num; i++) {
				step_list.add(sc.next());
			}
			
			for(int i =0; i < input_num-1; i++) {
				String step = step_list.get(i);
				switch(step) {
					case "lu":
						if(step_list.get(i+1).equals("ru")) count++;
						break;
					case "ru":
						if(step_list.get(i+1).equals("lu")) count++;
						break;
					case "ld":
						if(step_list.get(i+1).equals("rd")) count++;
						break;
					case "rd":
						if(step_list.get(i+1).equals("ld")) count++;
						break;
				}
			}
			System.out.println(count);
		}
	}
}



Measured memory_bytes: 38152