akhauriyash/Code-Regression huggingface dataset:
{-# OPTIONS_GHC -Wall #-}

readInt :: String -> Int
readInt = read

process :: [Int] -> String -> [Int]
process (r:l:xs) "+" = l+r : xs
process (r:l:xs) "-" = l-r : xs
process (r:l:xs) "*" = l*r : xs
process xs s         = readInt s : xs

main :: IO ()
main = do
    tokens <- fmap words getLine
    let ans = head $ foldl process [] tokens
    print ans



Measured memory_bytes: 4096
package main

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

func main() {
	var n int
	fmt.Scan(&n)

	scanner := bufio.NewScanner(os.Stdin)
	vs := strToIntSlice(scanLine(scanner))
	cs := strToIntSlice(scanLine(scanner))

	sumDiff := 0
	for index := 0; index < n; index++ {
		if vs[index] > cs[index] {
			sumDiff += vs[index] - cs[index]
		}
	}

	fmt.Println(sumDiff)
}

func scanLine(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func strToIntSlice(line string) []int {
	strSlice := strings.Split(line, " ")

	var intSlice []int
	for _, str := range strSlice {
		intValue, _ := strconv.Atoi(str)
		intSlice = append(intSlice, intValue)
	}

	return intSlice
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rep1(i, n) for(int i=1; i<=n; i++)
#define all(v) v.begin(), v.end()
using pint = pair<int, int>;
using tint = tuple<int, int, int>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef int64_t lint;
constexpr double PI=3.14159265358979323846;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;

lint mod = 1000000007;
struct mint {
  lint x; // typedef long long ll;
  mint(lint 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(lint 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, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

int main() {
	int N, K;
	cin >> N >> K;
	vector<lint> v(N);
	rep(i, N) {
		cin >> v.at(i);
	}

	lint b=0, c=N-1, x, y, z;
	mint a=1;
	sort(all(v));
	if ((int(v.at(N-1)) <= 0 && K%2 == 1) || N == K) {
		rep(i, K) {
			a *= v.at(N-1-i);
		}
		std::cout << a << '\n';
		return 0;
	}
	rep(i, K) {
		if (i != K-1 && v.at(b)*v.at(b+1) > v.at(c)*v.at(c-1)) {
			a *= v.at(b);
			a *= v.at(b+1);
			b+=2;
			i++;
		} else {
			a *= v.at(c);
			c--;
		}
	}
	cout << a << '\n';
}


Measured memory_bytes: 4760
n = int(input())
s = input()

# 一匹目、二匹目について4通り試す
# 羊:True, 狼:False
from itertools import product
for tf in product([True, False], repeat=2):
    tf = list(tf)
    for i in range(1, n):
        if s[i] == 'o':
            if tf[i]:
                tf.append(tf[i-1])
            else:
                tf.append(not tf[i-1])
        else:
            if tf[i]:
                tf.append(not tf[i-1])
            else:
                tf.append(tf[i-1])

    if tf[0] == tf[-1]:
        tf.pop(-1)
        flag = False
        if s[0] == 'o':
            if tf[0]:
                if tf[-1] == tf[1]:
                    flag = True
            else:
                if tf[-1] != tf[1]:
                    flag = True
        else:
            if tf[0]:
                if tf[-1] != tf[1]:
                    flag = True
            else:
                if tf[-1] == tf[1]:
                    flag = True

        if flag:
            for i in range(n):
                if tf[i]:
                    tf[i] = 'S'
                else:
                    tf[i] = 'W'
            print(''.join(tf))
            exit()

print(-1)

Measured memory_bytes: 93612
package main

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

func out(x ...interface{}) {
	fmt.Println(x...)
}

var sc = bufio.NewScanner(os.Stdin)

func getInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getString() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	sc.Split(bufio.ScanWords)

	N := getInt()
	a := make(map[int]int)
	for i := 0; i < N; i++ {
		n := getInt()
		a[n]++
	}

	k := len(a)

	//out(a, k)
	if k%2 == 0 {
		k--
	}

	out(k)
}


Measured memory_bytes: 6784
def main():
    H, W = map(int, input().split())
    m = []
    m.append([True] * (W + 2))
    for _ in range(H):
        m.append([True] + [c == '#' for c in input()] + [True])
    m.append([True] * (W + 2))
    queue = []
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if m[i][j]:
                queue.append((i, j))
    ans = -1
    while queue:
        ans += 1
        tmp = []
        for x, y in queue:
            if not m[x - 1][y]:
                m[x - 1][y] = True
                tmp.append((x - 1, y))
            if not m[x + 1][y]:
                m[x + 1][y] = True
                tmp.append((x + 1, y))
            if not m[x][y - 1]:
                m[x][y - 1] = True
                tmp.append((x, y - 1))
            if not m[x][y + 1]:
                m[x][y + 1] = True
                tmp.append((x, y + 1))
        queue = tmp
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 108712
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <algorithm>
using namespace std;
#define ll long long
const double EPS = 1e-10;
const ll MOD = 7+(1e+9);

int main(){
  ll n;
  cin>>n;
  vector<ll>v(n,0);
  for(ll i=0;i<n;i++){
    cin>>v[i];
  }
  ll ans=1;
  for(ll i=1;i<n;i++){
    ll f=0;
    for(ll j=0;j<i;j++){
      if(v[i]<v[j])f++;
    }
    if(f==0)ans++;
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 256
#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 MOD 1000000007ULL;
#define rep(i,n) for(int i=0;i<n;i++)


vector< pair<ll,ll> > prime_factorize(ll N){
 	vector<pair<ll,ll>> res;
  	for(ll a=2;a*a<=N;++a){
     	if(N%a!=0) continue;
      	ll ex=0;
      	
      	while(N%a==0){
         	++ex;
          	N/=a;
        }
      	res.push_back({a,ex});
    }
  
  	if(N!=1) res.push_back({N,1});
  	return res;
}

int main() {
	ll N;
  	cin>>N;
  	ll count=0;
  	vector<pair<ll,ll>> res;
  	res= prime_factorize(N);
  	for(auto x:res){
      	ll sum=0;
      	for(ll j=1;j*(j+1)/2<=x.second;j++){
          	 count++;
        }
      	
    }
  	cout<<count<<endl;
}

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

int main() {
  int N, out = 100;
  cin >> N;
  
  for (int i = 0; i < N; i++) {
    int a_i;
    cin >> a_i;
    int k = 0;
    
    while ((a_i % 2) == 0) {
      a_i /= 2;
      k += 1;
    }
    
    if (k == 0) {
      out = 0;
      break;
    }
    
    else if (k < out)
      out = k;
    
  }
  
  cout << out << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main(){
	cin >> a >> b;
	if(a.size() > b.size())
		cout<<"GREATER";
	else if(a.size() < b.size())
		cout<<"LESS";
	else if(a == b)
		cout<<"EQUAL";
	else if(a.size() == b.size()){
		if(a > b)
			cout<<"GREATER";
		else
			cout<<"LESS";
		}

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main()
{
  string s;
  int i,j,c;
  cin >> s;
  i = 0;
  j = s.length()-1;
  c = 0;
  while(i<=j){
    if(i == j && (s[i] == 'i' || s[i] == 'w'));
    else if(s[i] == 'i' && s[j] == 'i');
    else if(s[i] == 'w' && s[j] == 'w');
    else if(s[i] == '(' && s[j] == ')');
    else if(s[i] == ')' && s[j] == '(');
    else c++;
    i++;
    j--;
  }
  cout << c << endl;
  return 0;
}

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

const int N = 4e6 + 5;

int n, x, sum;
bitset<N> a;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	a.set(0);

	while(n-- > 0) {
		cin >> x;
		sum += x;
		a |= (a << x);
	}

	sum = (sum + 1) / 2;
	for (int i = sum; i < N; ++i) if (a[i]) {
		cout << i << endl; return 0;
	}
}

Measured memory_bytes: 1792
import scala.io.{StdIn => in}

object Main extends App {
  val n = in.readInt
  val w = in.readLine.split(" ").map(_.toInt)

  var res = Int.MaxValue
  for(i <- 1 until n) {
    val a = w.take(i).sum
    val b = w.drop(i).sum
    if((a-b).abs < res) res = (a-b).abs
  }

  val ans = res
  println(ans)
}

Measured memory_bytes: 25548
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(), a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;

const int mx = 100005;
int N, M;
int color[mx];
vector<int> graph[mx];

bool dfs(int v, int c){
    color[v] = c;
    for(int i : graph[v]){
        if(color[i] == c)return false;
        if(color[i] == 0 and !dfs(i, -c))return false;
    }
    return true;
}

int main(){

    cin >> N >> M;
    rep(i, M){
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    if(dfs(0, 1)){
        ll white = 0, black = 0;
        rep(i, N){
            if(color[i] == 1)white++;
            else black++;
        }
        cout << white * black - M << endl;
    } else {
        ll ans = N;
        cout << ans * (ans - 1) / 2 - M << endl;
    }

}

Measured memory_bytes: 6528
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define LOOP(i) while(i--)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto pitr=c.begin();pitr!=c.end();++pitr){cout<<*pitr;if(next(pitr,1)!=c.end())cout<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	int N=in();
	auto A=vecin<ll>(N);
	REP(i,N){
		A[i] -= i+1;
	}

	sort(ALL(A));

	ll B=A[N/2];
	ll S=0;
	REP(i,N){
		S += abs(A[i]-B);
	}

	out(S);
	return 0;
}


Measured memory_bytes: 1792
parseInt(x) = parse(Int, x)
parseMap(x::Array{SubString{String},1}) = map(parseInt, x)

function main()
    S = chomp(readline())
    zs = 0
    os = 0
    for s in S
        if s == '0'
            zs += 1
        else
            os += 1
        end
    end 
    ans = 2 * min(zs, os)
    return ans
end


println(main())

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

int main()
{
    int N, Q;
    string S;
    vector<set<int> > pls; //アルファベットごとに集合を持つ

    cin >> N >> S >> Q;

    // 初期化
    pls.assign(26, set<int>({600000}));
 
    //はじめの文字列をそれぞれカウント
    REP(i, N){
        pls[S[i]-'a'].insert(i);
    }

    REP(i, Q){
        int id;
        cin >> id;

        //変換クエリの場合
        if(id == 1){
            int a;
            char new_c;
            cin >> a;
            a--;
            cin >> new_c;
            char old_c = S[a];
            S[a] = new_c;
            pls[old_c - 'a'].erase(a);
            pls[new_c - 'a'].insert(a);
        }
        //カウントクエリの場合
        else{
            int l, r;
            cin >> l >> r;
            l--;
            r--;
            int ans = 0;
            for(int j=0; j<26; j++){
                if (pls[j].empty()) continue;
                int lid = *pls[j].lower_bound(l); //l以上が現れるの最小のインデックス
                // int rid = *pls[j].lower_bound(r); //l以上が現れるの最小のインデックス
                if(lid <= r){
                    ans++;
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 24196
n,m = map(int,input().split())
ans = 1
for i in range(1, int(m**0.5)+1):
    if m % i == 0:
        if m // i >= n:
            ans = max(ans, i)
        if m // (m//i) >= n:
            ans = max(ans, m//i)

print(ans)


Measured memory_bytes: 38640
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>
#include <cmath>

using namespace std;
typedef long long ll;
ll mod = 1e9+7;
//ll mod = 998244353;
#define rep(i,n) for(int i = 0; i < (n); ++i)

int main() {
    int s;
    cin >> s;
    int cnt = 0;
    vector<int> dp(s+1, 0);
    dp[0] = 1;
    rep(i, s) {
        for (int j = 3; j <= s; ++j) {
            int idx = i + j;
            if (idx > s) break;
            dp[idx] = (dp[idx] + dp[i]) % mod;
        }
    }
    cout << dp[s] << endl;
    return 0;
}


Measured memory_bytes: 3624
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String S = sc.next();
		
		int black = 0;
		int white = 0;
		
		for(int i = 0; i < N; i++) {
			if(S.charAt(i) == '.') {
				white++;
			} 
		}
		
		int min = white;
		
		for(int i = 0; i < N; i++) {
			if(S.charAt(i) == '#') {
				black++;
			} else {
				white--;
			}
			min = Math.min(min, black + white);
		}
		System.out.println(min);
	}
}


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

#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int lli;
typedef pair<int, int> P;

int main() {
    int n;
    cin >> n;
    int v[n];
    int c[n];
    REP(i, n) {
        cin >> v[i];
    }
    REP(i, n) {
        cin >> c[i];
    }
    int ans = 0;

    REP(i, n) {
        if (v[i] - c[i] > 0)
            ans += v[i] - c[i];
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
s = int(input())
a = [s]
idx = 0
while True:
    a.append(a[idx] / 2 if a[idx] % 2 == 0 else 3 * a[idx] + 1)
    if a[:-1].count(a[len(a) - 1]) == 1:
        print(idx + 2)
        break
    idx += 1

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long
using pi=pair<int,int>;
signed main(){
    int k,a,b;
    cin>>k>>a>>b;
    cout << (a % k == 0 || b % k == 0 || a / k != b / k ? "OK" : "NG");
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
#define drep(i,cc,n) for(int i=(cc);i<=(n);++i)
#define rep(i,n) drep(i,0,n-1)
#define drrep(i,cc,n) for(int i=(cc);i>=(n);--i)
#define rrep(i,n) drrep(i,0,n-1)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,v.size())if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define arrprint(v,n) rep(i,n)if(i==0)cout << v[i];else cout << " " << v[i]; cout << endl;
#define matprint(v,n,m) rep(i,n){rep(j,m){cout << v[i][j] << " ";}cout << endl;}
#define SORT(v) sort(v.begin(), v.end())
#define REV(v) reverse(v.begin(), v.end())
using namespace std;
const int mod=1000000007;
const int INF=1001001001;
using ll = long long;
using P = pair<int,int>;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

int main(){
    int h,w,k;
    cin >> h >> w >> k;
    vector<vector<char>>c(h,vector<char>(w));
    rep(i,h)rep(j,w)cin >> c[i][j];
    // vector<int> row(h), col(w);
    // rep(i,h)rep(j,w)if(c[i][j] == '#'){row[i]++;col[j]++;}
    int ans = 0;
    rep(i,(1<<h))rep(j,(1<<w)){
        int cnt = 0;
        rep(ii,h)rep(jj,w)if((c[ii][jj] == '#') && (i&(1<<ii)) && (j&(1<<jj)))cnt++;
        // cout << i << " " << j <<  " " << (1<<h) << endl;
        // if(i == 3 && j == 4)cout << cnt << endl;
        if(cnt == k){
            ans++;
            // cout << i << " " << j << endl;
        }
    }

    cout << ans << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 3636
D={}
R=range(8)
def f1(i,p):
  dp=0
  if i==0 and p%4<3: dp=1
  elif i==1 and p%4>0: dp=-1
  elif i==2 and p<4: dp=4
  elif i==3 and p>3: dp=-4
  return dp
  
def f():
  global D
  D={tuple(R):0}
  SP=[R]
  while SP:
    a=SP.pop(0)
    c=D[tuple(a)]
    p=a.index(0)
    for i in range(4):
      dp=f1(i,p)
      if dp==0: continue
      x=a[:]
      x[p],x[p+dp]=x[p+dp],x[p]
      tx=tuple(x)
      if tx in D: continue
      SP.append(x)
      D[tx]=c+1
  return

import sys
f()
A=[]
for x in sys.stdin:
  A=map(int,x.split(" "))
  print D[tuple(A)]

Measured memory_bytes: 7672
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define Red ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define F first
#define S second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
typedef long long ll;

const int inf = int(1e9);
const int mod = inf + 7;
using namespace std;
const int N = 5e5 + 555;
int dp[N];
void solve()
{
	int n, k;
	cin >> n >> k;
	int a[n];
	rep(i, n) cin >> a[i], dp[i] = inf;
	dp[0] = 0;
	for(int i = 0; i < n; ++i){
		for(int j = max(0, i - k); j < i; ++j){
			dp[i] = min(dp[j] + abs(a[i] - a[j]), dp[i]);
		}
	}
	cout << dp[n - 1];
}

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

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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

struct UnionFind{
  vector<int> v;
  UnionFind(int n) : v(n, -1) {}
  void init(){ for(int i = 0;i < (int)v.size();i++)v[i]=-1; }
  int find(int x) { return v[x] < 0 ? x : v[x] = find(v[x]); }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (-v[x] < -v[y]) swap(x, y);
    v[x] += v[y]; v[y] = x;
    return true;
  }
  bool root(int x) { return v[x] < 0; }
  bool same(int x, int y) { return find(x) == find(y); }
  int size(int x) { return -v[find(x)]; }
};

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

  ll n,m;
  vector<P> es;
  cin>>n>>m;
  rep(i,m){
    int a,b;
    cin>>a>>b;
    a--;b--;
    es.push_back(P(a,b));
  }
  ll crt=n*(n-1)/2;
  vector<ll> res;
  res.push_back(crt);
  UnionFind uf(n);
  for(int i=m-1;i>=1;i--){
    if(!uf.same(es[i].fi,es[i].se)){
      crt-=uf.size(es[i].fi)*uf.size(es[i].se);
      uf.unite(es[i].fi,es[i].se);
    }
    res.push_back(crt);
  }
  reverse(all(res));
  rep(i,res.size())cout<<res[i]<<endl;

  return 0;
}


Measured memory_bytes: 5104
// Ver19.03
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF (1 << 29) * 2
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  int a, b;
  scanf("%d%d", &a, &b);
  puts(a == b ? "Yes" : "No");
}

Measured memory_bytes: 256
#-*- coding:utf-8 -*-

S = input()
s1 = S[:2]
s2 = S[2:]
i1 = int(s1)
i2 = int(s2)

YYMM = False
MMYY = False

if 1 <= i1 <= 12:
    MMYY = True
if 1 <= i2 <= 12:
    YYMM = True

if YYMM and MMYY:
    print("AMBIGUOUS")
elif YYMM:
    print("YYMM")
elif MMYY:
    print("MMYY")
else:
    print("NA")




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

// 総数を1000000007で割った余り
const long long mod = 1e9 + 7;

using ll  = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define ull unsigned long long
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vc vector<char>
#define vs vector<string>
#define vpii vector<pii>
#define vpll vector<pll>

#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; i++)
#define rep1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; i++)
#define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));
#define pb push_back
#define mp make_pair

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

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

void printVec(vector<int>& vec) {
    for (auto& e : vec) {
        cout << e << " ";
    }
    cout << endl;
}

const string YES = "Yes";
const string NO  = "No";

int func(long long n) {
    // cout << fixed << setprecision(8);

    int ans = 0;
    for (int i = 1; i <= 9; i++) {
        for (int j = 1; j <= 9; j++) {
            ans = i * j;
            if (ans == n) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;

    return 0;
}

int main() {
    long long N;
    scanf("%lld", &N);

    func(N);

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<list>
#include<set>
#include<string>
using namespace std;
int gcd(int a, int b) {
	int c = a % b;
	while (c != 0) {
		a = b;
		b = c;
		c = a % b;
	}
	return b;
}
struct UnionFind {
	vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

	UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
		for (int i = 0; i < N; i++) par[i] = i;
	}

	int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
		if (par[x] == x) return x;
		return par[x] = root(par[x]);
	}

	void unite(int x, int y) { // xとyの木を併合
		int rx = root(x); //xの根をrx
		int ry = root(y); //yの根をry
		if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
		par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
	}

	bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};
typedef long long ll;

ll M = 1000000007;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)

ll mpow(ll x, ll n) {
	ll ans = 1;
	while (n != 0) {
		if (n & 1) ans = ans * x % M;
		x = x * x % M;
		n = n >> 1;
	}
	return ans;
}
ll comb(ll a, ll b) {
	if (a == 0 && b == 0)return 1;
	if (a < b || a < 0)return 0;
	ll tmp = ifac[a - b] * ifac[b] % M;
	return tmp * fac[a] % M;
}
// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a) {
	long long b = M, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= M;
	if (u < 0) u += M;
	return u;
}
vector<vector<ll>> mul(vector<vector<ll>> a,vector<vector<ll>> b,int n){
	int i,j,k,t;
	vector<vector<ll>> c(n);
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			t = 0;
			for (k = 0; k < n; k++)
				t = (t + a[i][k]*b[k][j] % M)%M;
			c[i].push_back(t);
		}
	}
	return c;
}
int main() {
	ll n, i,j, dp1[222222], dp2[222222], a[222222],p[222222],p2[222222],rp2[222222],rp[222222],ca, ans;
	stack<ll> s;
	cin >> n;
	for (i = 0; i < n; i++)
		cin >> a[i];
	dp1[n] = 0;
	dp1[n - 1] = 0;
	for (i = 0; i < n - 1; i++) {
		rp[i] = 0;
		ca = a[i];
		while (ca < a[i + 1]) {
			ca *= 4;
			rp[i]++;
		}
		p2[i] = -1;
		ca = a[i];
		while (ca <= a[i + 1]) {
			ca *= 4;
			p2[i]++;
		}
	}
	for (i = 1; i < n; i++) {
		p[i] = 0;
		ca = a[i];
		while (ca < a[i - 1]) {
			ca *= 4;
			p[i]++;
		}
		rp2[i] = -1;
		ca = a[i];
		while (ca <= a[i - 1]) {
			ca *= 4;
			rp2[i]++;
		}
	}
	for (i = n - 2; i >= 0; i--) {
		dp1[i] = dp1[i + 1];
		for (j = 0; j < p[i + 1];j++) {
			if (s.empty()) {
				dp1[i] += (n - i - 1)*2;
			}
			else {
				dp1[i] += (s.top() - i)*2;
				s.pop();
			}
		}
		for(j=0;j<p2[i];j++)
			s.push(i);
	}
	while (!s.empty())
		s.pop();
	dp2[0] = 1;
	for (i = 1; i <n; i++) {
		dp2[i] = dp2[i - 1]+1;
		for (j = 0; j < rp[i - 1]; j++) {
			if (s.empty()) {
				dp2[i] += i * 2;
			}
			else {
				dp2[i] += (i-s.top()) * 2;
				s.pop();
			}
		}
		for (j = 0; j < rp2[i]; j++)
			s.push(i);
	}
	ans = dp1[0];
	for (i = 0; i < n; i++)
		ans = min(ans, dp1[i + 1] + dp2[i]);
	cout << ans << endl;
}

Measured memory_bytes: 16768
import           Control.Applicative

data HMS = HMS { h :: Int, m :: Int, s :: Int }

instance Show HMS where
  show o = show (h o) ++ ":" ++ show (m o) ++ ":" ++ show (s o)

toHMS n = HMS h m s
  where h = div n 3600
        m = div n 60 - h * 60
        s = mod n 60

main = do
  n <- readLn
  putStrLn $ show $ toHMS n



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
int main(){int n,a[100002];long t=0;scanf("%d",&n);for(int i=1;i<= n;i++)scanf("%d",&a[i]),t+=abs(a[i]-a[i-1]);t+=abs(a[n]);for(int i=1;i<=n;i++)printf("%ld\n",t-abs(a[i]-a[i-1])-abs(a[i+1]-a[i])+abs(a[i+1]-a[i-1]));}



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

int main(){
    int N;
    long long power=1;
    cin >> N;
    for(int i=1;i<=N;i++){
        power *= i;
        if(power > 100000007)power %= 1000000007;
    }
    cout << power;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pi pair<int, int>
#define pl pair<ll, ll>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9+ 7;
const int INF = numeric_limits<int>::max() - 1e8;
const ll INFLL = numeric_limits<ll>::max() - 1e17;

signed main() {
    int N;
    cin >> N;
    vector<vector<vector<ll>>> dp(N + 1, vector<vector<ll>>(2, vector<ll>(3, -INFLL)));
    dp[0][1][0] = 0;
    for (int i = 0; i < N; i++) {
        ll A;
        cin >> A;
        for (int j = 0; j < 3; j++) {
            dp[i + 1][0][j] = max(dp[i + 1][0][j], dp[i][1][j] + A);
            dp[i + 1][1][j] = max(dp[i + 1][1][j], dp[i][0][j]);
            if (j + 1 < 3) dp[i + 1][1][j + 1] = max(dp[i + 1][1][j + 1], dp[i][1][j]);
        }
    }
    if (N % 2 == 0) cout << max(dp[N][1][0], dp[N][0][1]) << endl;
    else cout << max(dp[N][0][2], dp[N][1][1]) << endl;
}


Measured memory_bytes: 33104
#define NDEBUG
NDEBUG


#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <memory>
#include <random>

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


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


using namespace std;

/// caide keep
bool __hack = std::ios::sync_with_stdio(false);
/// caide keep
auto __hack1 = cin.tie(nullptr);


namespace template_util {
    

    constexpr int bytecount(uint64_t x) {
        return x ? 1 + bytecount(x >> 8) : 0;
    }

    /// caide keep
    template<int N>
    struct bytetype {
        
    };

    /// caide keep
    template<>
    struct bytetype<4> {
        
    };

    /// caide keep
    template<>
    struct bytetype<3> {
        
    };

    /// caide keep
    template<>
    struct bytetype<2> {
        
    };

    /// caide keep
    template<>
    struct bytetype<1> {
        
    };

    /// caide keep
    template<>
    struct bytetype<0> {
        
    };

    /// caide keep
    template<uint64_t N>
    struct minimal_uint : bytetype<bytecount(N)> {
    };
}


template<class T>
T next(istream& in) {
    T ret;
    in >> ret;
    return ret;
}

template<class T>
vector<T> next_vector(istream& in, size_t n) {
    vector<T> ret(n);
    for (size_t i = 0; i < n; ++i) {
        ret[i] = next<T>(in);
    }
    return ret;
}


int solveSmart(vector<int>& v) {
    sort(all(v));
    reverse(all(v));
    int count = v.size()-1;
    FOR(i, v.size()) {
        if (i + 1 > v[i]) {
            count = i-1;
            break;
        }
    }
    int up = v[count] - count;
//    dbg(count, v[count]);
    int right = 1;
    for (int i = count + 1; i < v.size(); ++i) {
        if (v[i] <= count) {
            break;
        } else {
            right++;
        }
    }
//    dbg(up, right);
    if (up % 2 && right % 2) {
        return 0;
    }
    return 1;
}

void solve(istream& in, ostream& out) {
    int n = next<int>(in);
    vector<int> v = next_vector<int>(in, n);
    if (solveSmart(v)) {
        out << "First\n";
    } else {
        out << "Second\n";
    }
}


int main() {
    solve(cin, cout);
    return 0;
}



Measured memory_bytes: 768
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    n = S()
    n1 = n[::-1]
    for i in range(len(n)):
        if n1[i] != n[i]:
            print("No")
            return
    print("Yes")
    return

#B
def B():
    a, b, c, d = LI()
    ans = [0 for i in range(101)]
    ans[a] += 1
    ans[b] -= 1
    ans[c] += 1
    ans[d] -= 1
    for i in range(100):
        ans[i+1] += ans[i]
    print(ans.count(2))
#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()


Measured memory_bytes: 39792
n = int(input())
w = list(map(int,input().split()))
# s1とs2の差の絶対値の最小値が最小になる部分を中心として考えれば良い
# wの最大値と最小値を順々に足したものを比較すれば良い
s1 = []
s2 = []

while len(w)>0:
  if sum(s1) <= sum(s2):
    s1.append(w.pop(0))
  else:
    s2.append(w.pop(-1))
print(abs(sum(s1)-sum(s2)))

    

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int d = sc.nextInt();
		
		int[][] x = new int[n][d];
		for (int i = 0; i < n; i++)
			Arrays.setAll(x[i], idx -> sc.nextInt());
		
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				double dis = calcDis(x[i], x[j]);
				if (dis == (int) dis) cnt++;
			}
		}
		
		System.out.println(cnt);
		
		sc.close();
	}
	
	static double calcDis(int[] y, int[] z) {
		double sum = 0;
		for (int i = 0; i < y.length; i++) {
			sum += (y[i] - z[i]) * (y[i] - z[i]);
		}
		
		return Math.sqrt(sum);
	}
	
}




Measured memory_bytes: 32216
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    int64_t N, A, B;
    cin >> N >> A >> B;
    int64_t sa = abs(A-B);
    if (A == B) {
        cout << 0 << endl;
    } else if (sa % 2 == 0) {
        cout << sa / 2 << endl;
    } else {
        int64_t min_ = min(A, B);
        int64_t max_ = max(A, B);
        if (sa == 1) {
            int64_t haiboku_idoukyori = N - min_;
            cout << min(haiboku_idoukyori, max_ - 1) << endl;
        } else {
        int64_t hikukazu = min_ - 1;
        int64_t tasukazu = N - max_;
        int64_t to_one_idoukyori = min_ + (max_ - hikukazu - 1) / 2;
        int64_t to_max_idoukyori = tasukazu + ((N - (min_ + tasukazu) - 1) / 2) + 1;
        cout << min(to_one_idoukyori, to_max_idoukyori) << endl;
        }
    }
    return 0;
}

Measured memory_bytes: 3616
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<cstring>

using namespace std;
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const ll LLINF = 1LL<<60;
#define P pair<int, int>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define print(x) cout << (x) << endl

class mint {
    long long x;
public:
    mint(long long 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 {
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res*=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 {
        mint res(*this);
        return res/=a;
    }

    friend ostream& operator<<(ostream& os, const mint& m){
        os << m.x;
        return os;
    }
};
/* -- template -- */

ll gcd(ll a, ll b) {
    if(b == 0)return a;
    return gcd(b, a % b);
}
ll lcs(ll a, ll b){
    if (b > a)swap(a, b);
    return a * b / gcd(a, b);
}

int main() {
    int N, M; cin >> N >> M;
    ll a[N];rep(i, N)cin >> a[i], a[i]/=2;
    ll a_gcd = a[0];
    rep(i, N){
        a_gcd = lcs(a_gcd, a[i]);
        if(a_gcd > M){
            cout << 0 << endl;return 0;
        }
    }
    ll ans = (((M / a_gcd) % 2) ? 1 + M / (a_gcd * 2) : M / (a_gcd * 2));
    int count = -1;
    rep(i, N) {
        int tempcount = 0;
        while(a[i] % 2 == 0){
            a[i] /= 2;
            ++tempcount;
        }
        if(count == -1)count = tempcount;
        else if(count != tempcount){ans = 0;}
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;

main() {
    int64_t n, m;
    cin >> n >> m;

    vector<int64_t> s(n), t(m);
    for (auto&& ss : s) {
        cin >> ss;
    }

    for (auto&& tt : t) {
        cin >> tt;
    }

    constexpr auto M = 1000000007;

    vector<vector<int64_t>> dp(n + 1, vector<int64_t>(m + 1));
    vector<vector<int64_t>> dp2(n + 1, vector<int64_t>(m + 1));
    vector<vector<int64_t>> dp3(n + 1, vector<int64_t>(m + 1));
    for (auto i : irange(0L, n + 1)) {
        dp[i][0] = 1;
        dp2[i][0] = (i == 0 ? 1 : 0);
        dp3[i][0] = 1;
    }
    for (auto j : irange(0L, m + 1)) {
        dp[0][j] = 1;
        dp2[0][j] = 1;
        dp3[0][j] = (j == 0 ? 1 : 0);
    }
    for (auto i : irange(0L, n)) {
        for (auto j : irange(0L, m)) {
            auto f = (s[i] == t[j] ? dp[i][j] : 0);
            dp[i + 1][j + 1] = (dp[i][j] + dp2[i + 1][j] + dp3[i][j + 1] + f) % M;
            dp2[i + 1][j + 1] = (dp2[i + 1][j] + f) % M;
            dp3[i + 1][j + 1] = (dp3[i][j + 1] + f) % M;
        }
    }

    #if 0
    for (auto i : irange(0L, n + 1)) {
        for (auto j : irange(0L, m + 1)) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

    for (auto i : irange(0L, n + 1)) {
        for (auto j : irange(0L, m + 1)) {
            cout << dp2[i][j] << " ";
        }
        cout << endl;
    }

    for (auto i : irange(0L, n + 1)) {
        for (auto j : irange(0L, m + 1)) {
            cout << dp3[i][j] << " ";
        }
        cout << endl;
    }
    #endif

    cout << dp[n][m] << endl;
}

Measured memory_bytes: 94336
N= int(input())
v_list = list(map(int, input().split()))
c_list = list(map(int,input().split()))
v_list = [i-j  for(i,j) in zip(v_list,c_list)]
s=[x for x in v_list if x>0]

print(sum(s))


#print(mount_list[1]*(mount_list[2]//mount_list[0]))


Measured memory_bytes: 2940
class PQ
  attr_reader :heap, :sum

  def initialize(a)
    @heap = a.dup
    @sum = @heap.inject(0,:+)
    (@heap.size/2).downto(0){|i|
      sift_up(i)
    }
  end

  def sift_up(pos)
    last = @heap.size
    start = pos
    new_item = @heap[start]
    child = pos * 2 + 1
    while child < last
      right = child + 1
      child = right if right < last && @heap[child] >= @heap[right]
      @heap[pos] = @heap[child]
      pos = child
      child = pos * 2 + 1
    end
    @heap[pos] = new_item
    sift_down(start, pos)
  end

  def sift_down(start, pos)
    new_item = @heap[pos]
    while pos > start
      parent = (pos - 1) / 2
      parent_item = @heap[parent]
      break if new_item >= parent_item
      @heap[pos] = parent_item
      pos = parent
    end
    @heap[pos] = new_item
  end

  def [](i)
    @heap[i]
  end

  def to_a
    @heap
  end

  def empty?
    @heap.empty?
  end

  def push(item)
    @heap << item
    @sum += item
    sift_down(0, @heap.size-1)
    self
  end

  def <<(item)
    push(item)
  end

  def pop
    last_item = @heap.pop
    if @heap.empty?
      @sum -= last_item if last_item
      return last_item
    end
    res = @heap[0]
    @heap[0] = last_item
    sift_up(0)
    @sum -= res
    res
  end

  def push_pop(item)
    if @heap[0] < item
      @sum += item - heap[0]
      item, heap[0] = heap[0], item
      sift_up(0)
    end
    item
  end
end

def f(a, b)
  pq = PQ.new(a)
  [pq.sum] + (0...N).map{|i|
    pq.push_pop(b[i])
    pq.sum
  }
end

GC.disable
N = gets.to_i
car, mid, cdr = gets.split.map(&:to_i).each_slice(N).to_a
p f(car.sort, mid).zip(f(cdr.map{|v|-v}.sort, mid.map{|v|-v}.reverse).reverse).map{|a, b| a + b }.max


Measured memory_bytes: 38920
def check(T, p, n, k):
    i = 0
    
    for j in range(k):
        s = 0
       
        while(s+T[i] <= p):
            s += T[i]
            i += 1
            if i == n:
                return n
    
    return i

n, k = [int(x) for x in input().split()]
T = []
for i in range(n):
    T.append(int(input()))

left, right = 0, 100000 * 10000

while(right - left > 1):
    mid = int((left + right) / 2)
    if (check(T, mid, n, k) >= n):
        right = mid
    else:
        left = mid

print(right)

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


//-- ソート --//

void f_sort(int[] , int);


int main(void)
{
	//パイプの本数
	int h_paipu[65000] = {0};
	int h_zyoint[65000] = {0};

	while (true)
	{
		//入力変数
		int n = 0;
		//2数(貪欲方で使う)
		unsigned int no = 0;
		unsigned int yes = 0;

		cin >> n;

		if (n == 0)	{	return 0;	}

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

		//ジョイントのインデックス
		int zyoint_index = n - 1;

		for (int i = 0; i < zyoint_index; i++)
		{
			cin >> h_zyoint[i];
		}

		//ジョイントをソート
		f_sort(h_zyoint , zyoint_index);

		int count = 0;

		while (yes >= no && n > 1)
		{
			no = 0;
			yes = 0;

			//ジョイントをつなげなかった場合
			for (int i = 0; i < n; i++)
			{
				no += h_paipu[i];
			}
			no *= n;

			//パイプを繋げる
			h_paipu[n - 2] += h_paipu[n - 1];
			//ジョイントもつなげる
			h_paipu[n - 2] += h_zyoint[count++];
			//1本減ってしまった
			n--;

			//forで回して計算する
			for (int i = 0; i < n; i++)
			{
				yes += h_paipu[i];
			}
			yes *= n;
		}

		if (yes > no)
		{
			cout << yes << endl;
		}
		else
		{
			cout << no << endl;
		}
	}

	return 0;
}




//*****----- ソート -----*****//

void f_sort(int h_zyoint[] , int n)
{
	sort(h_zyoint , h_zyoint + n);

	for (int i = 0; i < n / 2; i++)
	{
		int tmp = h_zyoint[i];
		h_zyoint[i] = h_zyoint[n - i - 1];
		h_zyoint[n - i - 1] = tmp;
	}
}

Measured memory_bytes: 1688
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <cstring>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>
#include <cctype>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;

int main(){
  int N, M;
  cin >> N >> M;
  cout << N*(N-1)/2 + M*(M-1)/2 << endl;
}


Measured memory_bytes: 888
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second
#define endl "\n"

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef pair<ll, ll> P;

int main(){
    ll a, v, b, w, t;
    cin >> a >> v >> b >> w >> t;
    if(a > b)   swap(a, b);
    if(v <= w){
        cout << "NO" << endl;
        return 0;
    }

    if(b - a <= (v - w) * t){
        cout << "YES" << endl;
    }
    else{
        cout << "NO" << endl;
    }


    return 0;
}


Measured memory_bytes: 3636
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#define MIN_INT -2147483648
#define MAX_INT 2147483647
#define MIN_LONG -9223372036854775808L
#define MAX_LONG 9223372036854775807L
#define PI 3.141592653589793238462643383279502884L

#define long long long int

using std::vector;
using std::map;
using std::set;
using std::string;
using std::pair;
using std::cin;
using std::cout;
using std::cerr;

// @author: pashka

vector<int> E;
int n;

vector<int> mul(vector<int> a, vector<int> b) {
    vector<int> res(n);
    for (int i = 0; i < n; i++) {
        res[i] = a[b[i]];
    }
    return res;
}

vector<int> pow(vector<int> a, int k) {
    vector<int> res = E;
    while (k > 0) {
        if (k % 2 == 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        k /= 2;
    }
    return res;
}


int main() {
    std::ios::sync_with_stdio(false);

    int k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i]; a[i]--;
    }
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i]; b[i]--;
    }

    vector<int> A(n);
    vector<int> B(n);
    for (int i = 0; i < n; i++) {
        A[a[i]] = i;
        B[b[i]] = i;
    }

    E.resize(n);
    for (int i = 0; i < n; i++) E[i] = i;

    vector<int> res;
    if (k < 10) {
        for (int i = 1; i < k; i++) {
            vector<int> c = mul(b, A);
            vector<int> C = mul(a, B);
            a = b; A = B;
            b = c; B = C;
        }
        res = a;
    } else {
        vector<int> left, right, mid;
        left = mul(b, mul(A, mul(B, a)));
        right = mul(A, mul(b, mul(a, B)));

        left = pow(left, (k + 1) / 6);
        right = pow(right, (k - 2) / 6);

        if (k % 6 == 2) {
            mid = b;
        } else if (k % 6 == 3) {
            mid = mul(b, A);
        } else if (k % 6 == 4) {
            mid = mul(b, mul(A, B));
        } else if (k % 6 == 5) {
            mid = B;
        } else if (k % 6 == 0) {
            mid = mul(a, B);
        } else if (k % 6 == 1) {
            mid = mul(b, mul(a, B));
        }
        res = mul(left, mul(mid, right));
    }
    
    for (int i = 0; i < n; i++) {
        cout << res[i] + 1 << " ";
    }
    cout << "\n";
    return 0;
}

Measured memory_bytes: 5960
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define REP(i,a,b) for(int i=(a); i<(b); i++)
int main() {
	int k; char s[107]; scanf("%d%s", &k, s);
	int l=strlen(s);
	if(l<=k) puts(s);
	else {
		s[k]=s[k+1]=s[k+2]='.', s[k+3]=0;
		puts(s);
	}
}


Measured memory_bytes: 1660
<?php
$f = fopen( 'php://stdin', 'r' );
$line = fgets( $f );
$items = array_map('intval', explode(" ",$line));
$votes = array_map('intval', explode(" ",fgets($f)));
sort($votes);
if($votes[$items[0]-$items[1]]>=(1/(4*$items[1]))*array_sum($votes)){
	echo "Yes";
} else {
	echo "No";
}
?>

Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
#define ll long long
int main(){
    Hello
    string s;
    cin >> s;
    if(s[0] == 'R' && s[0] == s[1] && s[1] == s[2]) cout << 3;
    else if((s[0] == s[1] && s[0] == 'R') || (s[1] == s[2] && s[1] == 'R')) cout << 2;
    else if(s[0] == 'R' || s[1] == 'R' || s[2] == 'R') cout << 1;
    else cout << 0;
    return 0;
}

Measured memory_bytes: 3656