akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main
{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int t=0,n=0;
        n=sc.nextInt();
        int a[]=new int[n];
        int dp[]=new int[n];
        for(int i=0;i<n;i++)
        {
            a[i]=sc.nextInt();
            dp[i]=1000000000;
        }
        
        dp[0]=0;
        for(int i=0;i<n;i++)
        {
            for(int j=1;j<=2;j++)
            {
                if(i+j<n)
           dp[i+j]=Math.min(dp[i+j],(dp[i]+Math.abs(a[i+j]-a[i])));
        }
    }
     System.out.println(dp[n-1]);
}
}

        

Measured memory_bytes: 49912
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
#include <cstring>
#include <bitset>
#include <stack>
using namespace std;
#define MP make_pair
#define PB push_back
const int INF=1e9;

int a,b,c,d,e,f,ans1,ans2;
double t;

int main()
{
	cin>>a>>b>>c>>d>>e>>f;
	a*=100;
	b*=100;
	t=-1.0;
	for (int i=0;i<=f;i+=a)
		for (int j=0;i+j<=f;j+=b)
			for (int k=0;i+j+k<=f;k+=c)
			{
				int curw=i+j; if (i+j==0) continue;
				if ((k+e-1)/e>(i+j)/100) break;
				int h=(min(f-curw-k,(curw/100)*e-k))/d*d;
				if (h<0) continue;
				if (curw+h+k==0) continue;
//				cout<<i<<" "<<j<<" "<<k<<" "<<h<<endl;
//				system("pause");
				double res=(double)(k+h)/(double)(curw+k+h);
				if (res>t)
				{
					t=res;
					ans1=curw+h+k;
					ans2=h+k;
				}
			}
	cout<<ans1<<" "<<ans2;
	return 0;
}

Measured memory_bytes: 256
/*ex9-1 B- バイナリハックイージー
ryo_1129*/

#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
//スタックの定義
typedef struct stack{
    int size;
    int count;
    char data[SIZE+1];
    char *top;
} stack;

void initialize_stack(stack *stk);
void push(stack *stk, char elem);
void back_space(stack *stk);
void print_display(stack *stk);

int main(void){
    stack stk;
    char str[SIZE+1];
    scanf("%s",str);
    //スタックを初期化
    initialize_stack(&stk);
    //スタックにデータを追加
    for (int i=0; str[i] != '\0'; i++ ){
        if (str[i] == 'B'){
            back_space(&stk);
        }else{
            push(&stk,str[i]);
        }
    }
    //出力
    print_display(&stk);
    return 0;
}

//スタックの初期化
void initialize_stack(stack *stk){
    stk->count = 0;
    stk->size = SIZE;
    stk->top = &(stk->data[0]);
}

//文字の追加
void push(stack *stk, char elem){
    if(stk->count >= stk->size){
        fprintf(stderr, "Error: stack overflow. (x=%c)\n", elem);
        exit(1);
    }
    else{
        stk->top++;
        *(stk->top) = elem;
        stk->count++;
    }
}

//バックスペース
void back_space(stack *stk){
    if(stk->count <= 0){
        return;
    }
    else{
        stk->top--;
        stk->count--;
    }
}

//ディスプレイの表示
void print_display(stack *stk){
    for(int i=1; i<= stk->count; i++){
        printf("%c", stk->data[i]);
    }
    putchar('\n');
}

Measured memory_bytes: 1596
result = 0
n, m = gets.chomp.split(' ').map(&:to_i)
data = []
m.times do
  a = gets.chomp.split(' ').map(&:to_i)
  data.push(a)
end
status = gets.chomp.split(' ').map(&:to_i)
result += 1 if status.all? { |s| s == 0 }
for j in 1..n
  stack = []
  init = [j]
  stack.push(init)
  while !stack.empty?
    ary = stack.pop()
    s = []
    data.each_with_index do |d, i|
      s.push(true) if (ary & d.slice(1, d.length - 1)).length % 2 == status[i]
    end
    result += 1 if s.length == m
    for i in ary[ary.length - 1]+1..n
      tmp = Marshal.load(Marshal.dump(ary))
      stack.push(tmp.push(i))
    end
  end
end
p result

Measured memory_bytes: 2044
#include<iostream>
#include<string>
using namespace std;
int main()
{
	//int pay = 0;
	//cin >> pay;
	//pay = pay % 1000;
	//if (pay > 0)
	//	pay = 1000 - pay;
	//cout << pay;
	int n = 0;
	int a=0, b=0, c=0, d = 0;
	string pig = "";
	cin >> n;
	for (int i = 0; i <= n; i++)
	{
		getline(cin, pig);
		if (pig == "AC")
			a++;
		else if (pig == "WA")
			b++;
		else if (pig == "TLE")
			c++;
		else if (pig == "RE")
			d++;
	 
	}
	cout << "AC x " << a << endl;
	cout << "WA x " << b << endl;
	cout << "TLE x " << c << endl;
	cout << "RE x " << d << endl;
    return 0;
}

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

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

string yn(bool f){return f?"Yes":"No";}
string YN(bool f){return f?"YES":"NO";}



signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout<<fixed<<setprecision(10);
	
	int con = 0;
	int N;
	vector<int> a;
	
	cin>>N;
	
	a.resize(N);
	
	for(int i = 0; i < N; i++){
		cin>>a[i];
		if(con + 1 == a[i]) con++;
	}
	
	if(con == 0) cout<<-1<<endl;
		else cout<<N - con<<endl;
	
	return 0;
}

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

bool func(ll cnt, ll A, ll B, const vector<ll> &hp){
    ll n = 0;
    for(ll i : hp){
        if(i>B*cnt) n += (i - B*cnt + (A-B) -1)/(A-B);
    }
    if( cnt >= n ) return true;
    else return false;
}

int main() {
    ll N, A, B; cin >> N >> A >> B;
    vector<ll> hp;
    for (int i = 0; i < N; i++)
    {
        int h; cin >> h;
        hp.push_back(h);
    }
    int ng = 0;
    int ok = 1000000001;
    while(abs(ok-ng)>1){
        int mid = (ok+ng)/2;
        if(func(mid, A, B, hp)) ok = mid;
        else ng = mid;
    }
    cout << ok << endl;   
}

Measured memory_bytes: 1400
type t = { v : int; w : int }

let solve n w d =
  let dp = Array.make (w + 1) 0 in
  for i = 0 to n - 1 do
    for j = d.(i).w to w do
      if dp.(j - d.(i).w) + d.(i).v > dp.(j) then
        dp.(j) <- dp.(j - d.(i).w) + d.(i).v;
    done
  done;
  dp.(w)

let () =
  let (n, w) = Scanf.scanf "%d %d " (fun n w -> n, w) in
  Array.init n (fun _ -> Scanf.scanf "%d %d " (fun v w -> { v; w }))
  |> solve n w |> Printf.printf "%d\n"

Measured memory_bytes: 2540
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define REP(i, n) FOR(i,0,n)

int N, Q;
constexpr int Nmax = 3000;
int A[Nmax];
lint dp[Nmax][Nmax];

constexpr lint MOD = 1000000007;
constexpr lint inv2 = (MOD + 1) / 2;

lint power(lint x, lint n)
{
    lint ans = 1;
    while (n>0)
    {
        if (n & 1) (ans *= x) %= MOD;
        (x *= x) %= MOD;
       n >>= 1;
    }
   return ans;
}


int main()
{
    cin >> N >> Q;
    REP(i, N) cin >> A[i];

    REP(i, N) REP(j, N) dp[i][j] = (A[i] > A[j]);

    REP(_, Q)
    {
        int X, Y;
        cin >> X >> Y;
        X--;
        Y--;
        REP(i, N) if (X != i and Y != i)
        {
            dp[i][X] = dp[i][Y] = (dp[i][X] + dp[i][Y]) * inv2 % MOD;
            dp[X][i] = dp[Y][i] = (dp[X][i] + dp[Y][i]) * inv2 % MOD;
        }
        dp[X][Y] = dp[Y][X] = (dp[X][Y] + dp[Y][X]) * inv2 % MOD;
    }

    lint ans = 0;
    REP(i, N) FOR(j, i + 1, N) ans += dp[i][j];
    cout << ans % MOD * power(2, Q) % MOD << endl;
}


Measured memory_bytes: 70528
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,s;
  cin >> N;
  vector<int> x(N);
  
  for(int i=0;i<N;i++)
    cin >> x.at(i);
  
  sort(x.begin(),x.end());
  reverse(x.begin(),x.end());
  
  for(int i=0;2*i<N;i++){
    s+=x.at(2*i);
    if(2*i+1<N)
      s-=x.at(2*i+1);
  }
  
  cout << s << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
	int N, A, B, C;
	scanf("%d\n%d %d\n%d\n", &N, &A, &B, &C);

	vector<int> D(N);
	for (int i = 0; i < N; ++i) {
		scanf("%d\n", &D[i]);
	}
	sort(D.rbegin(), D.rend());

	int price = A, calorie = C;
	int res = calorie / price;
	for (int i = 0; i < N; ++i) {
		price += B;
		calorie += D[i];
		int cur = calorie / price;
		if (res > cur) {
			break;
		}
		res = cur;
	}
	printf("%d\n", res);

	return 0;
}

Measured memory_bytes: 1032
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define lu unsigned long long int
#define pi pair<ll, ll>
#define pll pair<ll, ll>
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define mk make_pair
#define ve vector
#define vll ve<ll>
#define vpl ve<pll>
#define lr(n) for(ll i = 0; i < n; i++)
#define ltr(i, l, r) for (ll i = l; i <= r; i++)
#define rtl(i, l, r) for (ll i = r; i >= l; i--)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define be begin
#define sz(a) (ll)(a.size())
#define con continue
#define ret return
#define endl "\n"
const ll INF = 1e18;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// order_of_key(val): returns the number of values less than val
// find_by_order(k): returns an iterator to the kth largest element (0-based)

// ll gcd(ll a, ll b){
// 	return b == 0 ? a : gcd(b, a % b);
// }

ll mod = 1e9+7;

ll mult(ll x, ll y){
    ll rem=1;
    while(y){
        if(y&1){
            rem=(rem*x)%mod;
        }
        x=(x*x)%mod;
        y>>=1;
    }
    return rem;
}



void solve(ll T){
	ll n;
	cin>>n;
	ll a, b, c, d;
	ll ans = 0;
	ll x,y;
	cin>>x>>y;
	a = -x-y, b=-x+y, c=x-y, d=x+y;
	for(ll i=2;i<=n;i++){
		cin>>x>>y;
		ll tmp = max(x+y+a, max(x-y+b, max(-x+y+c, -x-y+d)));
		ans = max(ans, tmp);
		a = max(a, -x-y);
		b = max(b, -x+y);
		c = max(c, x-y);
		d = max(d, x+y);
	}
	cout << ans << "\n";
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// std::cout << std::unitbuf;
	ll T=1;
	// cin>>T;
	for(ll t=1;t<=T;t++){
		solve(t);
	}
	return 0;
}


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


int main()
{
	int h,w,n;
	cin >> h >> w >> n;
	int maxn = max(h,w);
	int t = n / maxn;
	if(n % maxn != 0)
		t++;
	cout << t << endl; 
    return 0;
}

Measured memory_bytes: 256
n = int(input())
p = []
for i in range(n):
    t,a = map(int, input().split())
    p.append((t,a))
q = [p[0][i] for i in range(2)]
for i in range(1, n):
    l = 0
    r = 10**18 + 1
    while l+1 < r:
        m = (l+r) //2 
        if any([p[i][j] * m < q[j] for j in range(2)]):
            l = m
        else:
            r = m
    for j in range(2):
        q[j] = r * p[i][j]

print(sum(q))

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

using namespace std;

char str[11];
int p,a=0,b=0,c=0,sum=0,m=0;
vector <int> Vecs,Veca;

int main()
{
    cin >> str;
    p = strlen(str);

    for (int i=0; i<p; i++)
    {
        Vecs.push_back(str[i]-48);
    }

    for (int j=0;j<p-2;j++)
    {
        a = 0;
        b = 0;
        c = 0;
        sum = 0;
        a += Vecs[j];
        b += (a*10)+Vecs[j+1];
        c += (b*10)+Vecs[j+2];

        sum = abs(753-c);
        Veca.push_back(sum);
    }
    sort(Veca.begin(),Veca.end());
    cout << Veca[0] << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i, n) for (int i=0; i<n; ++i)
#define all(obj) (obj).begin(),(obj).end()
using namespace std;
typedef long long ll;
long long GCD(long long x, long long y) { return y ? GCD(y, x%y) : x; }

int main(){
    int N;
    string S, T;
    cin >> N >> S >> T;
    rep(i, N){
        cout << S[i] << T[i];
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 3632
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main(){
  var len int
  var line string
  if sc.Scan(){
    tmp := sc.Text()
    len, _ = strconv.Atoi(tmp)
  }
  if sc.Scan() {
    line = sc.Text()
  }

  if len % 2 != 0 {
    fmt.Println("No")
    os.Exit(0)
  }

  halfLen := len / 2
  for i := 0; i < halfLen; i++ {
    if line[i] != line[i + halfLen] {
      fmt.Println("No")
      os.Exit(0)
    }
  }
  fmt.Println("Yes")
  os.Exit(0)
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <cstdio>
 
using namespace std;
 
typedef long long lli;
 
const lli N = 1e5;
 
lli n, m, s[N], t[N], p[N], sum[2][N];
 
main(){
  cin >> n >> m;
  for(lli i=0;i<n;i++) cin >> s[i] >> t[i];
  for(lli i=0;i<m;i++) cin >> p[i];
  sort(p, p+m);
  fill(sum[0], sum[2], 0);
  for(lli i=0;i<m-1;i++){
    for(lli j=0;j<2;j++) sum[j][i+1] = sum[j][i];
    sum[i%2][i+1] += p[i+1] - p[i];
    //sum[0][i+1] = sum[0][i] + ((i % 2 == 0) ? (p[i + 1] - p[i]) : 0);
    //sum[1][i+1] = sum[1][i] + ((i % 2 == 1) ? (p[i + 1] - p[i]) : 0);
  }
  lli ans = 0;
  for(lli i=0;i<n;i++){
    lli tmp = 0;
    bool f = false;
    if(s[i] > t[i]){
      swap(s[i], t[i]);
      f = true;
    }
    lli l = upper_bound(p, p+m, s[i]) - p;
    lli r = upper_bound(p, p+m, t[i]) - p;
    if(l >= r) tmp += t[i] - s[i];
    else{
      r--;
      if(f){
        tmp += t[i] - p[r];
        if((r - l) % 2) tmp += p[l] - s[i];
        tmp += sum[r%2][r] - sum[r%2][l];
      }else{
        tmp += p[l] - s[i];
        if((r - l) % 2) tmp += t[i] - p[r];
        tmp += sum[1-l%2][r] - sum[1-l%2][l];
      }
    }
    ans += tmp;
  }
  cout << ans << endl;
}

Measured memory_bytes: 5084
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		try (Scanner s = new Scanner(System.in)) {
			int n = s.nextInt();
			int l = s.nextInt();
			String[] array = new String[n];
			for (int i = 0; i < n; i++) {
				array[i] = s.next();
			}
			Arrays.sort(array);
			StringBuilder sb = new StringBuilder();
			for (String str : array) {
				sb.append(str);
			}
			System.out.println(sb);
		}
	}
}


Measured memory_bytes: 20180
import sys
from math import cos, sqrt, pi

read = sys.stdin.read
readline = sys.stdin.readline

A, B, H, M = map(int, read().split())
deg = abs(360 / 60 * M - 360 / 12 / 60 * (M + 60 * H))
answer = sqrt(A ** 2 + B ** 2 - 2 * A * B * cos(deg / 180 * pi))
print(answer)


Measured memory_bytes: 9384
fun main(args:Array<String>){
    val (h,w)=readInts()
    val pic=(1..h).map{ readLine()!!}
    pic.forEach{
        println(it)
        println(it)
    }
}

fun readString() = readLine()!!
fun readStrings() = readString().split(" ")
fun readInt() = readString().toInt()
fun readInts() = readStrings().map { it.toInt() }
fun readLongs() = readStrings().map { it.toLong() }
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)

Measured memory_bytes: 38336
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T, class U> using Pa = pair<T, U>;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;

class UnionFind{
private:
    vec<int> p,s;
    int cnt;
public:
    UnionFind(){}
    UnionFind(int N):cnt(N),s(N,1),p(N){
        iota(p.begin(),p.end(),0);
    }
    int find(int x){
        if(p[x]==x) return x;
        else return p[x] = find(p[x]);
    }
    void unite(int x,int y){
        x = find(x); y = find(y);
        if(x==y) return;
        if(s[x]>s[y]) swap(x,y);
        p[x] = y;
        s[y] += s[x];
        cnt--;
    }
    bool is_same_set(int x,int y) {return find(x)==find(y);}
    int size(int x) {return s[find(x)];}
    int compnents_number(){return cnt;}
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N,M,K;
    cin >> N >> M >> K;
    vec<ll> C(N);
    vvec<int> col(N+1);
    for(int i=0;i<N;i++){
        cin >> C[i];
        col[C[i]].push_back(i);
    }
    struct edge{
        int a,b;
        ll c;
    };
    vec<edge> E(M);
    for(int i=0;i<M;i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--; b--;
        E[i] = {a,b,c};
    }
    sort(E.begin(),E.end(),[](edge& e1,edge& e2){
        return e1.c<e2.c;
    });
    UnionFind uf(N);
    for(int i=1;i<=K;i++){
        int n = col[i].size();
        for(int j=0;j+1<n;j++) uf.unite(col[i][j],col[i][j+1]);
    }
    ll ans = 0,cnt = 0;
    for(auto& e:E){
        if(!uf.is_same_set(e.a,e.b)){
            ans += e.c;
            cnt++;
            uf.unite(e.a,e.b);
        }
        if(cnt==K-1) break;
    }
    cout << (cnt!=K-1? -1:ans) << "\n";
}

Measured memory_bytes: 8832
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int main(){
	int n, w, h, s, t;
	while(true){
		cin >> n;
		if(n == 0)break;
		cin >> w >> h;
		vector<vector<int>>a(w,vector<int>(h));
		for(int i = 0; i < w; ++i){
			for(int j = 0; j < h; ++j){
				a[i][j]=0;
			}
		}
		for(int i = 0; i < n; ++i){
			cin >> s >> t;
			a[s-1][t-1] = 1;
		}
		cin >> s >> t;
		int ans = 0;
		for(int i = 0; i <= w-s; ++i){
			for(int j = 0; j <= h-t; ++j){
				int count = 0;
				for(int k = i; k < i+s; ++k){
					for(int l = j; l < j+t; ++l){
						if(a[k][l]==1){
							count++;
							//cout << k << ", " << l << " / ";
						}
					}
				}
				ans = max(ans,count);
				//cout /*<< i << ", "<< j << ": " << count*/ << endl;
			}
		}
		cout << ans << endl;
	}
}


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

int main() {
  int a, b, c, d;
  cin >> a  >> b >> c >> d;
  int l = a + b;
  int r = c + d;
  if (l < r) {
    cout << "Right";
  }else if(l > r){
    cout << "Left";
  }else{
  	cout << "Balanced";
  }
}

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

int main(void){
    int n,sum=0,max=0;
    cin >> n;
    for(int i=0;i<n;++i){
        int a;
        cin >> a;
        if(max<a) max = a;
        sum += a;
    }
    cout << sum-max/2 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
double dp[2001][2000];
int main() {
  int n,m,i,j,k;
  while(cin>>n>>m&&n){
    string s;
    cin>>s;
    memset(dp,0,sizeof(dp));
    dp[0][0]=1;
    for(i=0;i<m;i++)for(j=0;j<n;j++)for(k=1;k<=6;k++)dp[i+1][(j+k)%n]+=dp[i][j]/6;
    double ans=0;
    for(j=0;j<n;j++){
      double sum=0;
      for(i=0;i<n;i++)sum+=dp[m][i]*(s[(j+i)%n]=='R');
      ans=max(ans,sum);
    }
    printf("%.10f\n",ans);
  }
  return 0;
}


Measured memory_bytes: 34492
w = gets.to_i
n = gets.to_i
data = Array.new
w.times{|i|
	data << i+1
}
n.times{|i|
	wide = gets
	ab = wide.split(",")
	a = ab[0].to_i - 1
	b = ab[1].to_i - 1
	safe = data[a]
	data[a] = data[b]
	data[b] = safe
}
w.times{|i|
	p data[i]
}

Measured memory_bytes: 6108
a, b, c = map(int, input().split())
k = int(input())

for i in range(k):
    if a < b and b < c:
        print("Yes")
        exit()
    elif a >= b:
        b = b * 2
    elif b >= c:
        c = c * 2

if a < b and b < c:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 9172
#include<stdio.h>
 
#define N 500001
 
int h,i,A[N];
 
void maxHeapify(int);
void buildMaxHeap(void);
 
int left(int);
int right(int);
int main()
{
 
  scanf("%d",&h);
 
  for(i=1;i<=h;i++){
 
    scanf("%d",&A[i]);
 
  }
 
  buildMaxHeap();
 
  for(i=1;i<=h;i++){
 
    printf(" %d",A[i]);
 
  }
 
  printf("\n");
 
  return 0;
}
int left(int i)
{
  return 2*i;
}
 
int right(int i)
{
  return 2*i+1;
}
 
void maxHeapify(int i){
  int l,r,largest,tmp;
 
  l=left(i);
  r=right(i);
 
  if(l<=h && A[l]>A[i]) largest=l;
 
  else largest=i;
 
  if (r<=h && A[r]>A[largest]){
  
    largest=r;
 
  }
 
  if (largest!=i){
 
    tmp=A[i];
    A[i]=A[largest];
    A[largest]=tmp;
 
    maxHeapify(largest);
  }
}
 
void buildMaxHeap(void){
  for(i=h/2;i>=1;i--){
    maxHeapify(i);
  }
}

Measured memory_bytes: 2552
#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main(){
    string T; cin >> T;
    vector<vector<int>> dp(T.size(), vector<int>(2, -1));
    vector<vector<int>> prev(T.size(), vector<int>(2, -1));
    if(T[0] == 'P' || T[0] == '?') dp[0][0] = 0;
    if(T[0] == 'D' || T[0] == '?') dp[0][1] = 1;
    for(int i=1;i<T.size();i++){
        if(T[i] == 'P' || T[i] == '?'){
            for(int j=0;j<2;j++){
                if(dp[i][0] < dp[i-1][j]){
                    dp[i][0] = dp[i-1][j];
                    prev[i][0] = j;
                }
            }
        }
        if(T[i] == 'D' || T[i] == '?'){
            for(int j=0;j<2;j++){
                if(dp[i-1][j] != -1 && dp[i][1] < dp[i-1][j] + 2 - j){
                    dp[i][1] = dp[i-1][j] + 2 - j;
                    prev[i][1] = j;
                }
            }
        }
    }
    int p = (dp.back()[0] < dp.back()[1] ? 1 : 0);
    for(int i=T.size()-1;i>=0;i--){
        T[i] = "PD"[p];
        p = prev[i][p];
    }
    cout << T << endl;
}

Measured memory_bytes: 25304
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <cstring>
#include <utility>
#include <vector>
#include <climits>
#include <cstdio>
#include <cmath>
#include <unordered_map>
using namespace std;



void solve()
{
	int n;
	cin>>n;
	int arr[n],dp[n];
	for(int i=0;i<n;i++) {cin>>arr[i];}
	dp[0]=0;
	dp[1]=abs(arr[1]-arr[0]);
	for(int i=2;i<n;i++)
	{
		dp[i]=min(dp[i-1]+abs(arr[i]-arr[i-1]),dp[i-2]+abs(arr[i]-arr[i-2]));
	}
	cout<<dp[n-1]<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    solve();
    return 0;
}

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

const int MAXN = 100;
const int MAXK = 1e5;

int ara[MAXN+7];
int n,k;
vector<vector<int>> dp(MAXK+7,vector<int>(2,-1));

int calc(int sum,int turn){
	int &now=dp[sum][turn];
	if(now!=-1) return now;
	for(int i=0;i<n;i++){
		if(sum-ara[i]==0){
			return now=turn;
		}
		if(sum-ara[i]>0){
			int x=calc(sum-ara[i],(turn^1) );
			if(x==turn) return now=turn;
		}
	}
	return now=(turn^1);
}

int main(){
	scanf("%d %d",&n,&k);
	for(int i=0;i<n;i++){
		scanf("%d",&ara[i]);
	}
	string out[]={"First","Second"};
	int ans = calc(k,0);
	cout<<out[ans];
}

Measured memory_bytes: 11904
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define cyes cout<<"YES"<<endl
#define cno cout<<"NO"<<endl
#define sp <<" "<<
#define CST(x) cout<<fixed<<setprecision(x)
#define PI 3.14159265359
#define MOD 1000000007
using namespace std;
using ll = long long;
using ld = long double;
using Graph = vector<vector<int>>;
using que_a = priority_queue<int, vector<int>, greater<int> >;
using que_d = priority_queue<int>;
using pint = pair<int,int>;

int main(){

    int h,w;

    while(true){
        
        cin >> h >> w;
        if(h == 0 && w == 0) return 0;
        
        rep(i,w){
            cout << '#';
        }
        cout << endl;

        rep(i,h-2){
            cout << '#';
            rep(j,w-2) cout << '.';
            cout << '#' << endl;
        }
        rep(i,w){
            cout << '#';
        }
        cout << endl;

        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3100
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var spl   = input.ReadLine().Split(' ');
        var n     = int.Parse(spl[0]);
        var x     = int.Parse(spl[1]);
        var ary = ToIntArray(input.ReadLine(), n);

        Array.Sort(ary);
        int count = 0;

        for(int i=0; i<n-1; i++) {
            var a = ary[i];
            if(x >= a) {
                x -= a;
                count++;
            }
        }

        if(x == ary[n-1]) count++;

        return count;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }

}


Measured memory_bytes: 13140
while True:
    m, f, r = map(int, input().split())
    
    if m == f == r == -1:
        break
    elif m == -1 or f == -1 or m + f < 30:
        print('F')
    elif 80 <= m+f:
        print('A')
    elif 65 <= m+f:
        print('B')
    elif 50 <= m+f or r >=50:
        print('C')
    elif 30 <= m+f:
        print('D')


Measured memory_bytes: 5592
#include<stdio.h>
#include<algorithm>
#include<numeric>
int main()
{
	int m,n,p[10000],i,d;
	while(scanf("%d%d",&n,&m),m)
	{
		for(d=i=0;i<n;++i)scanf("%d",&p[i]);
		std::sort(p,p+n);
		for(i=n-m;i>=0;i-=m)d+=p[i];
		printf("%d\n",std::accumulate(p,p+n,0)-d);
	}
	return 0;
}

Measured memory_bytes: 0
_ = Int(readLine()!)!
let AN = readLine()!.split(separator: " ").compactMap { Int($0) }
let Q = Int(readLine()!)!
let BCQ: [(Int, Int)] = (1...Q).map { _ in
    let bc = readLine()!.split(separator: " ").compactMap { Int($0) }
    return (bc[0], bc[1])
}

var dict = [Int: Int]()
for an in AN {
    if dict[an] == nil {
        dict[an] = 1
    } else {
        dict[an]! += 1
    }
}

var sum = dict.reduce(0) { $0 + ($1.key * $1.value) }
for bc in BCQ {
    if dict[bc.0] != nil {
        let diff = (bc.1 - bc.0) * dict[bc.0]!
        sum += diff

        if dict[bc.1] != nil {
            dict[bc.1]! += dict[bc.0]!
        } else {
            dict[bc.1] = dict[bc.0]
        }
        dict[bc.0] = 0
    }
    print(sum)
}


Measured memory_bytes: 15156
#include<iostream>
using namespace std;
int main(){
	
	int x,y,z=0;
	cin>> x>>y;
	if (x>=0&&y>=0){
		
		if(x+y>=24)
		  z=(x+y)-24;
		  	
			  else
			  z=x+y;
			  
			  }
			  cout<<z;
	return 0;
}

Measured memory_bytes: 256
H,N = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

# dp[i]: 体力iにするための最小魔力
dp = [float("inf")] * (H + 1)

# 初期条件
dp[H] = 0

for i in range(H, -1, -1):
    for a, b in AB:
        HP = max(0, i - a)
        dp[HP] = min(dp[HP], dp[i] + b)

print(dp[0])

Measured memory_bytes: 43996
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,K;
  cin >> N >> K;
  vector<int> h(N);
  for (int i = 0; i < N; i++) {
    cin >> h[i];
  }
  sort(h.begin(),h.end());
  int mi = h[N-1];
  for (int i = 0; i < N-K+1; i++) {
    if (mi > h[K-1+i] - h[i]) {
      mi = h[K-1+i] - h[i];
    }
  }
  cout << mi;
  
}

Measured memory_bytes: 640
'use strict';
console.log(function(args){
  const tmp = args.trim().split(' ').map(a=>a|0);
  const A = tmp[0], B = tmp[1], C = tmp[2];
  let X = tmp[3], Y = tmp[4];
  let total = 0;
  if ( A+B > 2*C ) {
    let Z = Math.min(X,Y);
    total += Z*2*C;
    X = X - Z; Y = Y - Z;
  }
  if ( ( X > 0 && A > 2*C ) || ( Y > 0 && B > 2*C ) ) {
    total += X*2*C;
    total += Y*2*C;
  } else {
    total += X*A;
    total += Y*B;
  }
  return total.toString();
}(require('fs').readFileSync('/dev/stdin', 'utf8')));


Measured memory_bytes: 7372
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define pii pair<ll,ll>
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());

int main()
{
  FAST/**/
   
   ll x;
   cin>>x;
   cout<<(!x);
   
   
   return 0;        
}  

  
          
   

Measured memory_bytes: 3648
#pragma region Macros

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
ostream &operator<<(ostream &out, vector<T> const &v) {
    for (auto &&a : v) out << a << " ";
    out << endl;
    return out;
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {
    int K, N;
    cin >> K >> N;
    vi a(N);
    REP(i, N) {
        cin >> a[i];
    }
    int diff = 0;
    sort(ALL(a));
    REP(i, N - 1) {
        chmax(diff, abs(a[i] - a[i + 1]));
    }
    chmax(diff, K - a[N - 1] + a[0]);
    cout << K - diff;
}

#pragma region main
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


Measured memory_bytes: 4740
int main(int argc, const char * argv[]) {

    int a, b; //縦，横
    int s, r; //面積，周の長さ
    
    //標準入力
    scanf("%d %d", &a, &b);
    
    //面積
    s = a*b;
    //周の長さ
    r = a*2 + b*2;
    
    //標準出力
    printf("%d %d\n", s, r);
    
    return 0;
}


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

public class Main {
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] ARRAY = new int[N];

        for (int i = 0; i < N; i++) {
            ARRAY[i] = scanner.nextInt();
        }

        int[] ballArray = new int[N];
        for (int i = N; i > 0; i--) {
            int bairitu = 2;
            int count= 0;
            while ((i * bairitu) <= N) {
                if (ballArray[i * bairitu - 1] == 1) {
                    count++;
                }
                bairitu++;
            }

            if (ARRAY[i-1] == 1) {
                if (count % 2 == 0) {
                    ballArray[i-1] = 1;
                }
            } else {
                if (count % 2 == 1) {
                    ballArray[i-1] = 1;
                }
            }
        }

        List<Integer> resultList = new ArrayList<>();
        for (int i=0; i<N; i++) {
            if (ballArray[i] == 1) {
                resultList.add(i+1);
            }
        }

        StringBuilder sb = new StringBuilder();
        System.out.println(resultList.size());
        for (Integer result : resultList) {
            sb.append(result).append(" ");
        }
        System.out.println(sb.toString());
    }
}

Measured memory_bytes: 75488
from collections import deque

s = deque(input())
reverse = 0
q = int(input())

for _ in range(q):
  query = input()
  if query == '1':
    reverse = 1 - reverse
  else:
    _,f,c = query.split()
    if f == '1':
      if reverse:
        s.append(c)
      else:
        s.appendleft(c)
    else:
      if reverse:
        s.appendleft(c)
      else:
        s.append(c)
        
  
if reverse:
  s.reverse()

print(''.join(s))

Measured memory_bytes: 8692
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!

#include <bits/stdc++.h>
using namespace std;

#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;

// ------------------------------------------------------------------------------------------------

string s;

void func() {
    cin >> s;
    if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) {
        cout << "Bad" << endl;
    } else {
        cout << "Good" << endl;
    }
}

int main() {
    fast_io; cout.precision(32);
    ll t = 1; // cin >> t;
    for (ll i = 1; i <= t; i++) {
        func();
    }
}


Measured memory_bytes: 256
using System;
using System.Linq;

public class Test
{
	public static void Main()
	{
		var line0 = Console.ReadLine().Split(new char[]{' '}).Select(c => Int32.Parse(c)).ToArray();
		var x = line0[0];
		var n = line0[1];
		if (n == 0)
		{
			Console.WriteLine(x);
		}
		else
		{
		var line1 = Console.ReadLine().Split(new char[]{ ' '}).Select(c => Int32.Parse(c)).ToArray();
		var found = false;
		var offset = 0;
		while(!found)
		{
			var x0 = x + offset;
			var x1 = x - offset;
			if (!line1.Any(a => x1 == a))
			{
				found = true;
				Console.WriteLine(x1);
			}
			else if (!line1.Any(a => x0 == a))
			{
				found = true;
				Console.WriteLine(x0);
			}
			offset++;
		}
		}
	}
}


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

int main() {
  int n, l;
  cin >> n >> l;
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    cin >> s.at(i);
  }
  sort(s.begin(), s.end());
  for (string t : s) {
    cout << t;
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<iostream>
#define MAX_NUM 100000

bool test(int p,int n,int k,int w[]){
    int track = p;
    int i = 0,j = 0;
    while(j != n){
        if(track >= w[j]){
            track -= w[j];
            j++;
        }else{
            track = p;
            i++;
            if(i == k) return false;
        }
    }
    return true;
}

int main(){
    int n,k,max=0;
    int w[MAX_NUM] = {};
    std::cin >> n >> k;
    for(int i=0;i<n;i++){
        std::cin >> w[i];
        if(max<w[i]){
            max = w[i];
        }
    }
    //std::cout << max << "から" << "調べます\n";
    int left=max;
    if(test(left,n,k,w)){
        std::cout << left << '\n';
        return 0;
    }else{
        //std::cout << max << "でテスト:失敗\n";
    }
    int t;
    int right = max*n;
    int min;
    while(left <= right){
        t = (left+right)/2;
        //std::cout << left << ' ' << right << ' ' << t << "でテスト:";
        if(test(t,n,k,w)){
            //std::cout << "成功-->" << t << '\n';
            min = t;
            right = t-1;
        }else{
            //std::cout << "失敗\n";
            left = t+1;
        }
    }
    std::cout << min << '\n';
    
    return 0;
}



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

int main ()
{
  	const long long INF = 1LL << 60;

	long long dp[100010];

  	for (int i = 0; i < 100010; i++)
	{
		dp[i] = 1LL;
	}

	dp[0] = 0;
	int n;
  	cin >> n;
  	vector<int> height(n);
  	for (int i = 0; i < n; i++)
    {
    	cin >> height[i];
    }
  	for (int i = 1; i < n; i++)
    {
    	dp[i] =  dp[i - 1] + abs(height[i] - height[i - 1]);
      	if(i > 1)
        {
        	dp[i] = min(dp[i - 2] + abs(height[i] - height[i - 2]), dp[i]);
        }
    }
  	cout << dp[n-1] << endl;
}


Measured memory_bytes: 1536
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep1(i,n) for (int i = 1; i <= n; ++i)
template<typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;

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

  int n; cin >> n;
  vector<P> ans;
  int minus = n;
  if(n % 2 == 1) --minus;

  for(int i = 1; i <= n; ++i) {
    for(int j = i + 1; j <= n; ++j) {
      if(j == minus) continue;
      ans.push_back({i,j});
    }
    --minus;
  }

  cout << ans.size() << endl;
  for(auto a : ans) {
    cout << a.first << " " << a.second << endl;
  }
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,&a[n]);
  cout<<a[n-1]-a[0]<<endl;
  return 0;
}

Measured memory_bytes: 256
/*ILTH      ILTH            ILTHILTHILTH    ILTH        ILTH
  ILTH      ILTH                ILTH        ILTH        ILTH
  ILTH      ILTH                ILTH        ILTHILTHILTHILTH
  ILTH      ILTH                ILTH        ILTH        ILTH
  ILTH      ILTHILTHILTH        ILTH        ILTH        ILTH

  */
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
const int maxN=100005;

typedef pair<ll, int> pii;
ll n,ans[maxN];
pii a[maxN];
void sinhtest(){
    srand(time(0));
    ofstream cout("a.inp");
    cout << "10\n";
    for (int i=1; i<=10; ++i) cout << rand()%10+1 << " ";
}
int main()
{
    //sinhtest();
    //ifstream cin("a.inp");
    //ofstream cout("a.out");
    cin >> n;
    for (int i=1; i<=n; ++i){
        cin >> a[i].fi;
        a[i].se=i;
    }
    sort(a+1, a+n+1);
    int mins=n+1;
    for (int i=n; i>=1; --i){
        mins=min(mins,a[i].se);
        if (a[i].fi==a[i-1].fi) continue;
        ans[mins]+=(a[i].fi-a[i-1].fi)*(n-i+1);
    }
    for (int i=1; i<=n; ++i) cout << ans[i] << "\n";
    return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
const int N=100005;
struct edge{
	int u,v;
	long long w;
}e[N<<2];
int num[N],fa[N],cnt=0,n,m,ans=0;
long long sumw[N];
bool cmp(edge a,edge b){return a.w<b.w;}
void add_edge_information(int u,int v,long long w){e[++cnt]=(edge){u,v,w};}
int find(int u){return u==fa[u] ? u: fa[u]=find(fa[u]);}
void combine(int u,int v){
	fa[u]=v;
	sumw[v]+=sumw[u];
	num[v]+=num[u];
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&sumw[i]);
	int a,b;
	long long c;
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&a,&b,&c);
		add_edge_information(a,b,c);
	}
	for(int i=1;i<=n;i++) fa[i]=i;
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v;
		int fa1=find(u),fa2=find(v);
		if(fa1!=fa2) combine(fa1,fa2);
		num[fa2]++;
		if(sumw[fa2]>=e[i].w) ans+=num[fa2],num[fa2]=0;
	}
	printf("%d\n",m-ans);
} 

Measured memory_bytes: 4352
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class disjointset{
  public:
    vector<int>rank,parent,sz;
    disjointset(){}
	disjointset(int size){
    	rank=parent=sz=vector<int>(size+1);
        for(int i=0;i<=size;i++)rank[i]=0,parent[i]=i,sz[i]=1;
	}
    int root(int n){return (parent[n]==n?n:parent[n]=root(parent[n]));}
    void unite(int x,int y){
        x=root(x);y=root(y);
        if(x!=y){
            if(rank[x]>rank[y])parent[y]=x,sz[x]+=sz[y];
            else parent[x]=y,sz[y]+=sz[x];
            if(rank[x]==rank[y])rank[root(x)]++;
        }
    }
    bool same(int x,int y){return root(x)==root(y);}
    int size(int n){return sz[root(n)];}
};
int main(){
    int n,m;
    cin>>n>>m;
    disjointset ds(n);
    vector<int>a(m),b(m);
    vector<long long>ans(m);
    for(int i=0;i<m;i++)cin>>a[i]>>b[i];
    ans[0]=(long long)n*(n-1)/2;
    for(int i=m-1;i>0;i--){
        if(ds.same(a[i],b[i]))ans[m-i]=ans[m-i-1];
        else ans[m-i]=ans[m-i-1]-(long long)ds.size(a[i])*ds.size(b[i]);
        ds.unite(a[i],b[i]);
    }
    reverse(ans.begin(),ans.end());
    for(auto x:ans)cout<<x<<endl;
    return 0;
}

Measured memory_bytes: 4096
x, n = map(int, input().split())
p = list(map(int, input().split()))
mem = []
mind = 100
for i in range(-100, 200):
    if i not in p:
        t = abs(x-i)
        if t < mind:
            mem.append([i, t])
            mind = t
mem = sorted(mem, key=lambda x: (x[1], x[0]))
print(mem[0][0])


Measured memory_bytes: 9096
#define _CRT_SECURE_NO_DEPRECATE
#include<bits/stdc++.h>
#define Rint register int
#define MP make_pair
#define fi first
#define se second
#define PB push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii; // 注意必要时改类型
typedef vector<int> vi;
const int MOD = 1e9 + 7;
const int N = 3e3 + 1;
inline int mod(int x) {
	return x % MOD;
}


int n;
// dp[i][j] 截止到前i个 有j个正面的概率
// dp[i+1][j+1] += dp[i][j] * p[i+1]
// dp[i+1][j] += dp[i][j] * (1 - p[i+1])
double p[N], dp[N][N];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
#ifdef _DEBUG
	int tt = clock();
	// freopen("in.txt", "r", stdin);
#endif 

	cin >> n;
	for (Rint i = 1; i <= n; ++i)
		cin >> p[i];
	dp[0][0] = 1;
	for (Rint i = 1; i <= n; ++i) 
		dp[i][0] = dp[i - 1][0] * (1 - p[i]);
	for (Rint i = 1; i <= n; ++i) {
		for (Rint j = 1; j <= n; ++j) {
			dp[i][j] += dp[i - 1][j - 1] * p[i];
			if (j == 1) continue;
			dp[i][j - 1] += dp[i - 1][j - 1] * (1 - p[i]);
		}
	}
	double ans = 0;
	for (Rint i = n / 2 + 1; i <= n; ++i) {
		ans += dp[n][i];
	}
	printf("%.10lf", ans);

#ifdef _DEBUG
	cerr << "\nTIME = " << clock() - tt << endl;
	tt = clock();
#endif

	return 0;
}


Measured memory_bytes: 70656
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define ld long double
constexpr int MAXN = 1e2;
constexpr int MAXK = 1e5;

int N, K, a[MAXN+5], DP[MAXK+5];

int f(int cur){
    if(cur < a[0]) return 0;
    if(DP[cur] != -1) return DP[cur];
    DP[cur] = 0;
    for(int i = N-1; i >= 0; i--){
        if(cur - a[i] >= 0 && !f(cur-a[i])) DP[cur] = 1;
    }
    return DP[cur];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for(int i = 0; i < N; i++) cin >> a[i];
    memset(DP, -1, sizeof(DP));
    cout << ((f(K) == 1) ? "First" : "Second");
}

Measured memory_bytes: 8612
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
using namespace std;
int main(){
	double a,b,x;
	cin >>a>>b>>x;
	double y=(2*x/a/a)-b;
	if (y>=0){
		double ans = atan2(b-y,a);
		cout <<setprecision(12)<<rad_to_deg(ans);
	}
	else{
		double h = 2*x/a/b;
		double ans = atan2(b,h);
		cout <<setprecision(12)<<rad_to_deg(ans);
	}
}

Measured memory_bytes: 256
n, m = map(int, input().split())
d = {0: 1}
asum = 0
ans = 0
for a in map(int, input().split()):
    asum = (asum + a) % m
    if asum in d:
        ans += d[asum]
        d[asum] += 1
    else:
        d[asum] = 1
print(ans)

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

int main() {
  int H, W;
  cin >> H >> W;
  string s;
  rep(i, 0, H) {
    cin >> s;
    cout << s << endl << s << endl;
  }
  getchar();
}

Measured memory_bytes: 3624
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>

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

using namespace std;
using llng = long long;
using vi = vector<int>;
using vvi = vector<vector<int> >;
using vll = vector<llng>;
using vs = vector<string>;

int main() {
    /* Declaration & Initialization */
    int N; cin >> N;
    int A, flg;
    REP(i,N) {
        cin >> A;
        if (A % 2) flg += 1;
    }
    if (flg % 2) cout << "NO" << endl;
    else cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Map;
import java.util.Scanner;

public class Main {
	final static String aa = "aa";
	final static String a = "a";
	final static String bb = "bb";
	final static String b = "b";
	static Map<String, String> my;
	static Map<String, String> mn;


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int r = sc.nextInt();
		int g = sc.nextInt();
		int b = sc.nextInt();
		int rgb = r * 100 + g * 10 + b;

		System.out.println((rgb % 4 == 0) ? "YES" : "NO");

		return;
	}

}


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

const int Maxn = 200005;

int n;
int a[Maxn];

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


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = s; i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << endl;
#define CFYN(n) cout << ( (n) ? "YES":"NO") << endl;
#define OUT(n) cout << (n) << endl;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;

int main(void)
{
    IOS
    int n; cin >> n;
    vector<int> t(n+1), x(n+1), y(n+1);
    REP(i,n) {
        cin >> t[i+1] >> x[i+1] >> y[i+1];
    }
    
    bool ans = true;
    REP(i,n) {
        int d = abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);
        if (t[i+1] - t[i] < d) ans = false;
        if ((t[i+1] - t[i]) % 2 != d % 2) ans = false;
        if (!ans) break;
    }

    ATYN(ans)

    return 0;
}

Measured memory_bytes: 1408
N=int(input())
S=input()
s_lst=[]
s_dic={0:'A',1:'B',2:'C',3:'D',4:'E',5:'F',6:'G',7:'H',8:'I',9:'J',10:'K',11:'L',12:'M',13:'N',14:'O',15:'P',16:'Q',17:'R',18:'S',19:'T',20:'U',21:'V',22:'W',23:'X',24:'Y',25:'Z'}

for s in S:
    for k,d in s_dic.items():
        if s==d and k+N<=25:
            buf=s_dic[k+N]
            s_lst.append(buf)
            break
        elif s==d and k+N>25:
            buf=s_dic[k+N-26]
            s_lst.append(buf)
            break
v=''
for s in s_lst:
    v+=s
print(v)

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

int main() {
	// your code goes here
	long long k,x;
	
	cin>>k>>x;
	if (k*500>=x)
	{
		cout<<"Yes"<<endl;
	}
	else
	{
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def has_vacant(l, r, l_g, r_g):
    if l_g == r_g:
        if (r-l)%2 == 1:
            return True
    if l_g != r_g:
        if (r-l)%2 == 0:
            return True
    return False


def interact(l, r, l_g, r_g):
    m = (l+r)//2
    print(m)
    g = input()
    if g == 'Vacant':
        return
    if has_vacant(l, m, l_g, g):
        return interact(l, m, l_g, g)
    if has_vacant(m, r, g, r_g):
        return interact(m, r, g, r_g)


def solve():
    """
    0 1 2 3 4 5 6 7 8
    M       M     
    """
    N = read_int()
    l, r = 0, N-1
    print(l)
    l_g = input()
    if l_g == 'Vacant':
        return
    print(r)
    r_g = input()
    if r_g == 'Vacant':
        return
    interact(l, r, l_g, r_g)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 61924
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args) {
        long N = sc.nextLong();
        String S = sc.next();
        long R = 0;
        long G = 0;
        long B = 0;
        for(int i = 0; i < N; i++){
          if(S.charAt(i) == 'R'){
            R++;
          }else if(S.charAt(i) == 'G'){
            G++;
          }else if(S.charAt(i) == 'B'){
            B++;
          }
        }
        long ans = R*G*B;
        for (int i = 0; i < N-2; i++) {
          for (int j = i + 1; j < N-1; j++) {
            int k = 2*j-i;
            if (k >= N) {
                continue;
            }
            if(S.charAt(i) != S.charAt(j) && S.charAt(i) != S.charAt(k) && S.charAt(j) != S.charAt(k)){
                ans--;
            }
          }
        }
        System.out.println(ans);
      }
}


Measured memory_bytes: 36996