akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdlib>
typedef long long ll;

int main() {
    ll N;
    scanf("%d", &N);
    N = abs(N);
    ll Ans = 0;
    ll maximum = 0;
    ll couutnup = 0;
    while (maximum < N){
        couutnup++;
        maximum += couutnup;
        Ans++;
    }
    std::cout << Ans << std::endl;
    return 0;
}

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

bool isSosu(int N)
{
    for (int i = 2; i < N; i ++) {
        if (N % i == 0) {
            return false;
        }
    }
    
    return true;
}

int main(void) {
    int X;
    
    cin >> X;
    
    for (int i = X;; i ++) {
        if (isSosu(i) == true) {
            cout << i << endl;
            return 0;
        }
    }
    
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <string>
#include <cstring>
#include <list>
#include <unordered_set>
#include <tuple>
#include <cmath>
#include <limits>
#include <type_traits>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <set>
#include <bitset>
#include <regex>
#include <random>
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define rep(i,n)for(ll i=0;i<n;++i)
#define exout(x) printf("%.10f\n", x)
const double pi = acos(-1.0);
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX_N = 201010;

//最大公約数
ll gcd(ll x, ll y) {
	return y ? gcd(y, x % y) : x;
}

ll lcm(ll x, ll y) {
	if (x == 0 || y == 0)return 0;
	return (x / gcd(x, y) * y);
}

ll dx[4] = { 0,0,-1,1 };
ll dy[4] = { -1,1,0,0 };
ll ans[110][110];
bool flag[2][110];

//long longしか使わない
//素数は1より大きい
//lower_boundは指定したkey以上の要素の一番左のイテレータをかえす
//upper_boundは指定したkeyより大きい要素の一番左のイテレータをかえす
int main() {
	string s, t;
	cin >> s >> t;
	ll n = s.length();
	ll m = t.length();
	ll ans = INF;
	rep(i, n-m+1) {
		ll res = 0;
		rep(j, m) {
			if (s[i + j] != t[j])res++;
		}
		ans = min(ans, res);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3620
h,w = map(int,input().split())
c = [list(map(int,input().split())) for i in range(10)]
a = [list(map(int,input().split())) for i in range(h)]
 
len_c = len(c)

#ワーシャルフロイド
for k in range(len_c):
  for i in range(len_c):
    for j in range(len_c):
      c[i][j] = min(c[i][j], c[i][k]+c[k][j])
 
ans =0
for i in range(h):
  for j in range(w):
    if a[i][j]==-1:
      ans += 0
    else:
      ans += c[a[i][j]][1]
      
print(ans)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vd=vector<double>;
using vvd=vector<vd>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using vs=vector<string>;
#define rep(i,n) range(i,0,n)
#define range(i,a,n) for(int i=a;i<n;i++)
#define all(a) a.begin(),a.end()
#define LINF    	((ll)1ll<<60)
#define INF     	((int)1<<30)
#define EPS     	(1e-9)
#define MOD     	(1000000007)
#define fcout(a)	cout<<setprecision(a)<<fixed
#define fs 			first
#define sc			second
#define PI			3.141592653589793

template<class S,class T>ostream& operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s; a=0;} return os;}

int main(){
	cin.tie(0);
   	ios::sync_with_stdio(false);
	
	int n;
	cin>>n;
	if(n==1){
	    cout<<"Hello World"<<endl;
	}else{
	    int a,b;
	    cin>>a>>b;
	    cout<<a+b<<endl;
	}
	return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {
    public static final long mod = (long)1e9+7;
    public static final long INF = Long.MAX_VALUE/10;
    public static final int inf = Integer.MAX_VALUE/10;

    static void solve(InputReader in, PrintWriter out){
        int k = in.ni();
        dfs(1000000);
        out.println((k/2)*((k+1)/2));
    }
    public static void dfs(long i){
        if(i!=0)dfs(i-1);
        return;
    }
    public static void main(String[] args) throws Exception{
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        solve(in, out);
        out.close();
    }
    public static class InputReader{
        private BufferedReader br;
        private StringTokenizer st;
        public InputReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }
        public String ns(){
            if(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (Exception e){
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }
        public long nl(){
            return Long.parseLong(ns());
        }
        public int ni(){
            return Integer.parseInt(ns());
        }
        public Double nd(){
            return Double.parseDouble(ns());
        }
        public int[] ni(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        public long[] nl(int n){
            long[] a = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = nl();
            }
            return a;
        }
        public double[] nd(int n){
            double[] a = new double[n];
            for (int i = 0; i < n; i++) {
                a[i] = nd();
            }
            return a;
        }
    }
}

Measured memory_bytes: 77012
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M,i;
  cin>>N;
  cin>>M;
  int j=0;
  int sum=0;
    while(j<M){
      cin>>i;
      j++;
      sum+=i;
    }
  if(N-sum>=0){
  cout<<N-sum<<endl;
  }
  else{
  cout<<-1<<endl;
  }
}

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

using namespace std;
typedef long long ll;

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

int main(void) {
	ll n, m, g, ans, i, a, b;
	string s, t;
	cin >> n >> m >> s >> t;
	g = gcd(n, m);
	a = n / g;
	b = m / g;
	for (i = 0; i < g; i++) {
		if (s[i * a] != t[i * b]) {
			printf("-1\n");
			return 0;
		}
	}
	ans = n * m / g;
	cout << ans << "\n";
	return 0;
}

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

int main() {
    int a; cin >> a;
    int A, B, C, D; A = a / 1000; B = a / 100 - 10 * A; C = (a % 100 - a % 10) / 10; D = a % 10;
    //cout << A << " " << B << " " << C << " " << D << endl;
    if (A + B + C + D == 7){
        cout << A << "+" << B << "+" << C << "+" << D << "=7" << endl;
    }
    else if (A + B + C - D == 7) {
        cout << A << "+" << B << "+" << C << "-" << D << "=7" << endl;
    }
    else if (A + B - C + D == 7) {
        cout << A << "+" << B << "-" << C << "+" << D << "=7" << endl;
    }
    else if (A - B + C + D == 7) {
        cout << A << "-" << B << "+" << C << "+" << D << "=7" << endl;;
    }
    else if (A + B - C - D == 7) {
        cout << A << "+" << B << "-" << C << "-" << D << "=7" << endl;;
    }
    else if (A - B + C - D == 7) {
        cout << A << "-" << B << "+" << C << "-" << D << "=7" << endl;;
    }
    else if (A - B - C + D == 7) {
        cout << A << "-" << B << "-" << C << "+" << D << "=7" << endl;
    }
    else {
        cout << A << "-" << B << "-" << C << "-" << D << "=7" << endl;
    }
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
	static int n;

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(br.readLine());

		int x[][] = new int[n][2];
		int y[][] = new int[n][2];

		for (int i = 0; i < n; i++) {
			String str[] = br.readLine().split(" ");

			x[i][0] = Integer.parseInt(str[0]);
			y[i][0] = Integer.parseInt(str[1]);
			x[i][1] = i;
			y[i][1] = i;
		}

		Arrays.sort(x, (a, b) -> Integer.compare(a[0], b[0]));
		Arrays.sort(y, (a, b) -> Integer.compare(a[0], b[0]));

		PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
		for (int i = 0; i < n - 1; i++) {
			pq.add(new int[] { Math.abs(x[i][0] - x[i + 1][0]), x[i][1], x[i + 1][1] });
			pq.add(new int[] { Math.abs(y[i][0] - y[i + 1][0]), y[i][1], y[i + 1][1] });
		}

		UnionFind uf = new UnionFind(n);
		long answer = 0;
		while (!pq.isEmpty()) {
			int d[] = pq.poll();
			if (uf.same(d[1], d[2]))
				continue;
			uf.union(d[1], d[2]);
			answer += d[0];
		}
		System.out.println(answer);
	}
}

class UnionFind {
	int[] parent; // インデックスにとノードを対応させ、そのルートノードのインデックスを格納
	int[] rank; // parentと同様に、木の高さを格納

	public UnionFind(int size) {
		this.parent = new int[size];
		this.rank = new int[size];

		for (int i = 0; i < size; i++) {
			makeSet(i);
		}
	}

	public void makeSet(int i) {
		parent[i] = i;
		rank[i] = 0; // 集合の高さ
	}

	public void union(int x, int y) {
		int xRoot = find(x);
		int yRoot = find(y);

		// xが属する木の方が大きい場合
		if (rank[xRoot] > rank[yRoot]) {
			parent[yRoot] = xRoot; // yの親をxに更新

		} else if (rank[xRoot] < rank[yRoot]) {
			parent[xRoot] = yRoot;

		} else if (xRoot != yRoot) {
			parent[yRoot] = xRoot;
			rank[xRoot]++; // 同じ高さの木がルートの子として着くから大きさ++;
		}
	}

	// 引数の属する木のルートのidを返す
	public int find(int i) {
		if (i != parent[i]) {
			parent[i] = find(parent[i]);
		}
		return parent[i];
	}

	// 同じ木に属しているか
	public boolean same(int x, int y) {
		return find(x) == find(y);
	}
}

Measured memory_bytes: 58112
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <map>
using namespace std;
#define LL long long
const int maxn = 1e6+33;
const int mod = 1e9+7;

int main()
{
    int a[4];
    for(int i=1;i<=3;i++) scanf("%d",&a[i]);
    sort(a+1,a+1+3);
    printf("%d\n",a[3]-a[1]);

    return 0;
}


Measured memory_bytes: 256
{-
高橋君は最初 A 枚、青木君は最初 B 枚のクッキーを持っています。 二人は、高橋君からはじめて交互に、以下の操作を繰り返します。
自分が持っているクッキーの枚数が奇数なら、自分が持っているクッキーを 1 枚食べ、偶数なら何もしない。その後、自分が持っているクッキーの半分を相手に渡す。
合計 K 回の操作を行った後の、高橋君と青木君が持っているクッキーの枚数をそれぞれ求めてください。
-}

import Data.Monoid

main :: IO ()
main = do
  [a, b, k] <- (read <$>) . words <$> getLine
  let
    loop a' b' 0 = (a', b') :: (Int, Int)
    loop a' b' k' =
      if (k - k') `mod` 2 == 0
        then
          if a' `mod` 2 == 0
            then loop (a' `div` 2) (b' + (a' `div` 2)) (k' - 1)
            else loop ((a' - 1) `div` 2) (b' + ((a' - 1) `div` 2)) (k' - 1)
        else
          if b' `mod` 2 == 0
            then loop (a' + (b' `div` 2)) (b' `div` 2) (k' - 1)
            else loop (a' + ((b' - 1) `div` 2)) ((b' - 1) `div` 2) (k' - 1)
    (a'', b'') = loop a b k
  putStrLn $ (show a'') <> " " <> (show b'')

Measured memory_bytes: 508
const input = require('fs').readFileSync('/dev/stdin', 'utf8')
const seqSetStr = input.split('\n').slice(1)
const seqSet = seqSetStr.map(setStr => setStr.split(' '))
const aSeq = seqSet.map(set => +set[0])
const bSeq = seqSet.map(set => +set[1])
const sum = aSeq.reduceRight((sum, a, i) => {
  const b = bSeq[i]
  const currentA = a + sum
  const diff = currentA % b
  return diff > 0 ? currentA + (b - diff) - a : sum
}, 0)

console.log(sum)


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

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)(a.size())
#define endl "\n"

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

    return gcd(b, a%b);
}

const ll L = 1e5+5;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    ll N;
    cin >> N;

    ll cnt = 0;

    for(ll i=1; i<=N; i++)
    {
        ll dig = 0;

        ll num = i;

        while(num)
        {
            num/=10;
            dig++;
        }

        if(dig&1)
        {
            cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long,long long> ii; 	
typedef complex<long double> com;

const ll mod = 1e9+7;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    ll d,n;
    cin >> d >> n;
    if (n == 100){
        n++;
    } 
    cout << n;
    for (int z=0;z<d;z++){
        cout << "00";
    } cout << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
string divide[]={"dream","dreamer","erase","eraser"};
int main(){//切れるタイミングを確定させるために反転しておく
    string s;cin >> s;
    reverse(s.begin(),s.end());//逆順にする
    for(int i=0;i<4;i++) reverse(divide[i].begin(),divide[i].end());
    bool can=true;
    for(int i=0;i<s.size();){//iは切れたら更新
        bool can2=false;//４つのうちどれかで切れたらtrue
        for(int j=0;j<4;j++){//divideを一つずつ試す
            string d=divide[j];
            if(s.substr(i,d.size())==d){//分割できればcan2を更新
                can2=true;
                i+=d.size();
            }
        }//どれでも切れなかったら
        if(!can2){
            can=false;
            break;
        }
    }//canをfalseにすることなく生き残れたら
    if(can) cout << "YES" << endl;
    else cout << "NO" << endl;

}


Measured memory_bytes: 512
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n,m = iim()
l = []
for i in range(n):
    l.append(iil())

l.sort()
#print(l)
cost = 0
num = 0
for item in l:
    num += item[1]
    cost += item[0]*item[1]
#    print(num,cost)
    if num >= m:
        cost -= (num-m)*item[0]
        print(cost)
        exit()



Measured memory_bytes: 27764
N = int(input())

robos = []
for i in range(N):
    x, l = map(int, input().split())
    robos.append((x + l, x - l))

robos.sort()

kosuu = 0
maenomigi = -100000000000000000000000
for migi, hidari in robos:
    # ok
    if maenomigi <= hidari:
        maenomigi = migi
        kosuu += 1

print(kosuu)


Measured memory_bytes: 56460
#include<iostream>
#include<stdio.h>
//#include <bits/stdc++.h>
#include<vector>
#include<float.h>
#include<iomanip>
#include<algorithm>
#include<string>
#include<cstring>
#include<math.h>
#include<cmath>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include <cassert>
#include <cmath>
#include<cstdint>

#define INF 1e9
#define rep(i,n)for(int i=0;(i)<(int)(n);i++)
#define REP(i,a,b)for(int i=(int)(a);(i)<=(int)(b);i++)
#define VEC(type, c, n) std::vector<type> c(n);for(auto& i:c)std::cin>>i;
#define vec(type,n) vector<type>(n)
#define vvec(m,n) vector<vector<int>> (int(m),vector<int>(n))
#define ALL(a)  (a).begin(),(a).end()

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using P = pair<int,int>;

vector<int>bitSearch(int bit,int n){
    vector<int>S;
    rep(i,n)if(bit&(1<<i))S.push_back(i);
    return S;
}


int d[3] = {-1,0,1};
int main(){
   int a,b,c;cin>>a>>b>>c;
   if(b-a==c-b)cout<<"YES";
   else cout<<"NO";
}



Measured memory_bytes: 256
/*
 * 152 C 
 */

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

int
main(int argc, char **argv)
{
  int d_flag = 0;
  int n;
  int *a;
  int cnt = 0;
  int i;
  int min;

  if (argc == 2)
    d_flag = 1;

  scanf("%d", &n);
 
  a = (int *) malloc(n * sizeof(int));
  for (i = 0; i < n; i++)
    scanf("%d", a + i);

  if (d_flag) {
    for (i = 0; i < n; i++)
      printf("a[%d] = %d\n", i, a[i]);
  }

  min = a[0];
  for (i = 0; i < n; i++) {
    if (a[i] <= min) {
      cnt++;
      min = a[i];
    }
  }

  printf("%d\n", cnt);
}


Measured memory_bytes: 896
#include "bits/stdc++.h"
using namespace std;
int x,n,p[110];
bool vis[210];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>x>>n;
	for(int i=0;i<n;i++)
	{
		cin>>p[i];
		vis[p[i]]=1; 
	}
	for(int i=0;i<=x;i++)
	{
		if(!vis[x-i])
		{
			cout<<x-i<<endl;
			break;
		}
		if(!vis[x+i])
		{
			cout<<x+i<<endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 3636
s = input()
n = len(s)
dp = [0]*n
if s[0] in 'ATGC':
    dp[0]=1
for i in range(1,len(s)):
    if s[i] in 'ATGC':
        dp[i]=1
    if s[i-1]!=0 and dp[i]!=0:
        dp[i]+=dp[i-1]
print(max(dp))

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

//type
#define ll long long
typedef pair<int, int> P;
//定数
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007    //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange
//略記
#define PB push_back //挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素
#define Z class
// OTHER
// xの二乗を返す (関数テンプレート版)
template <typename T>
T square(T x) { return x * x; }
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))
// loop
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= ll(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= ll(b); i--)
#define FORA(i, I) for (const auto &i : I)

// vector
#define ALL(x) x.begin(), x.end()

// output
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define isYES(x) printf("%s\n", (x) ? "YES" : "NO")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
#define ln cout << '\n'
template <Z A>
void pr(A a)
{
  cout << a;
  ln;
}
template <Z A, Z B>
void pr(A a, B b)
{
  cout << a << ' ';
  pr(b);
}

// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

int main(){
    int N;
    cin >> N;
    string S;
    cin >> S;
    for(int i=0; i<S.size(); i++){
        int a = S[i] - 'A';
        a = (a+N) % 26;
        S[i] = 'A' + a;
    }
    cout << S << endl;
    return 0;
}


Measured memory_bytes: 3648
N = int(input())

def main():
    graph = []
    for i in range(1, N+1):
        for j in range(i+1, N+1):
            if i+j == N//2*2+1:
                continue
            graph.append([i, j])
    print(len(graph))
    for i, j in graph:
        print(i, j)

if __name__ == "__main__":
    main()

Measured memory_bytes: 4124
import java.io.IOException;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.io.PrintWriter;

@SuppressWarnings("unchecked")
public class Main {
    public static void main(String[] args) throws IOException {
        final String s;

        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            s = reader.readLine();
        }

        PrintWriter out = new PrintWriter(System.out);

        final String[] sl = s.split(" ");
        int N = Integer.parseInt(sl[0]);
        int M = Integer.parseInt(sl[1]);

        // 1回の試行にかかる時間 ÷ 全ACする確率
        out.println((1900 * M + 100 * (N - M)) * (int)Math.pow(2, M));

        out.flush();
    }
}


Measured memory_bytes: 21204
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <random>
using namespace std;

#define rep(i, N) for (int i=0; i<N; ++i)
#define llong long long

template <typename T, int size0>
void fill(T (&a)[size0], T value)
{
	fill_n(a, size0, value);
}
template <typename T, int size0, int size1>
void fill(T (&a)[size0][size1], T value)
{
	fill_n(a[0], size0 * size1, value);
}
template <typename T, int size0, int size1, int size2>
void fill(T (&a)[size0][size1][size2], T value)
{
	fill_n(a[0][0], size0 * size1 * size2, value);
}

const int MAX_N = 100;
const int MAX_W = 1e+5;
int N;
int W;
llong w[MAX_N];
llong v[MAX_N];
llong dp[MAX_N][MAX_W];

llong solve(int n, int weight)
{
	if (n == N) return 0LL;
	if (dp[n][weight] != -1LL) return dp[n][weight];

	if (weight + w[n] <= W)
	{
		llong max_value = max(solve(n+1, weight), v[n] + solve(n+1, weight + w[n]));
		return dp[n][weight] = max_value;
	}
	else
	{
		return dp[n][weight] = solve(n+1, weight);
	}
}

int main ()
{
	cin >> N;
	cin >> W;
	rep(i, N)
	{
		cin >> w[i];
		cin >> v[i];
	}
	fill(dp, -1LL);

	cout << solve(0, 0) << endl;

	return 0;
}

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

using namespace std;

#define ll long long

int main(){
  int h, w;
  int a, b;
  cin >> h >> w >> a >> b;
  for(int i = 1; i <= h; i++){
    for(int j = 1; j <= w; j++){
      if(i <= b && j <= a) {cout << 0;}
      else if(i > b && j > a) {cout << 0;}
      else {cout << 1;}
    }
    cout << '\n';
  }
  
  return 0;
}

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

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
//using namespace __gnu_pbds;

const double pi = 3.141592653589793;

#define xx          first
#define yy          second
#define mp          make_pair
#define intl        long long
#define filein      freopen("input.txt", "r", stdin)
#define fileout     freopen("output.txt", "w", stdout)
#define debug       cout << "YES" << endl
#define what_is(x)  cout << #x << " is " << x << endl
#define pb          push_back
#define pii         pair<int, int>

//find_by_order(int) and order_of_key(int)
//typedef tree < intl , null_type ,less<intl>,rb_tree_tag,tree_order_statistics_node_update > ordered_set;
const int M = 345678;

int ara[190];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //filein;
    int n;
    cin >> n;
    for( int i = 0; i < n; i++ ) cin >> ara[i];
    intl ans = 1, odd = 1;
    for( int i = 0; i < n; i++ )
    {
        int x = 3, o = 0;
        if( ara[i]%2 == 0) o += 2;
        else o++;
        odd *= o;
        ans *= x;
    }
    //what_is(ans);
    cout << ans - odd << endl;
    return 0;
}


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

bool no[10];
int main() {
    int n, k, t;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < k; i++) {
        scanf("%d", &t);
        no[t] = true;
    }
    while (true) {
        t = n;
        bool ok = true;
        while (t && ok) {
            if (no[t % 10]) ok = false;
            t /= 10;
        }
        if (ok) return printf("%d", n), 0;
        n++;
    }
}

Measured memory_bytes: 256
n, m = list(map(int, input().split()))
c = list(map(int, input().split()))
DP = [n for i in range(n + 1)]
DP[0] = 0
for cost in c:
    for i in range(cost, n + 1):
        DP[i] = min(DP[i], DP[i - cost] + 1)
print(DP[n])


Measured memory_bytes: 7636
k, n = gets.chomp.split(" ").map(&:to_i)
a = gets.chomp.split(" ", n).map(&:to_i)

a.sort!

max = k - a[a.length - 1] + a[0]
(n-1).times do |i|
  if max < a[i + 1] - a[i]
    max = a[i + 1] - a[i]
  end
end
p k - max

Measured memory_bytes: 18288
import java.io.*;
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int count = 0;
		HashSet<Integer> set = new HashSet<>();
		for(int i=0;i<n;i++){
			int a = in.nextInt();
			if(set.contains(a)) count++;
			else set.add(a);
		}
		System.out.println(n-(count + (count % 2 == 0 ? 0 : 1)));
	}
}


Measured memory_bytes: 51144
#include<stdio.h>
#define min(a,b) (a)<(b)?(a):(b)
int main(void)
{
  int a,b,k;
  scanf("%d%d%d",&a,&b,&k);
  for(int i=min(a,b);i<=a||i<=b;i--){
    if(a%i==0&&b%i==0){
      k--;
    }
    if(k==0){
      printf("%d",i);
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

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


    return 0;
}

Measured memory_bytes: 888
#include <stdio.h>
int main(void)
{
 int W,H,x,y,r;
 scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);
 
 if(H>=y+r&&W>=x+r&&x-r>=0&&y-r>=0){
 printf("Yes\n");
 }
 else{
 printf("No\n");
 }
 return 0;
}

Measured memory_bytes: 584
#include <iostream>
#include <set>
#include <vector>
#include <string>
#include <algorithm>
#include <iterator>
#include <map>
#include <utility>
#include <list>
#include <climits>
#include <bitset>
#include <numeric>

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define repi(i, n) for(auto i = (n).begin(); i != (n).end(); i++)
#define in_arr(type, a, n) copy_n(istream_iterator<type>(cin), n, (a).begin());
#define ll long long int

int main(){
    ll a;
    cin >> a;
    cout << (a - 1) / 11 * 2 + (a - (a - 1) / 11 * 11 <= 6 ? 1 : 2) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include <cstdlib>
#include <vector>
#include <utility>

using namespace std;

int main()
{
	vector<pair<int, int> > team;
	int n, min[4], sec[4], Sec, name;
	
	while(1){
		cin >> n;

		if(n == 0)    break;

		for (int i = 0; i < n; i++){
			cin >> name;

			cin >> min[0] >> sec[0] >> min[1] >> sec[1] >> min[2] >> sec[2] >> min[3] >> sec[3];

			Sec = 0;

			for (int j = 0; j < 4; j++){
				Sec += ((min[j] * 60) + sec[j]);
			}

			team.push_back(make_pair(Sec, name));
		}

		sort(team.begin(), team.end());

		cout << team[0].second << endl << team[1].second << endl << team[n-2].second << endl;
	
		team.clear();
	}

	return 0;
}

Measured memory_bytes: 1304
#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
#from collections import deque
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[[i] for i in range(N-1)]
A_sort =sorted(A)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A_sort[i].append((a,b))             #色を出力するため
A_sort.sort(key=lambda x:x[1])
#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
aa=[]
hq_none =heapq.heapify(aa)
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理,dequeで高速？
for i in range(1,N+1):
    heapq.heapify(color_node[i])
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A_sort[i][1] #i番目の辺とつながっている頂点
    if color_node[n_a] ==[]:
        color =0
    else:
        color =(color_node[n_a][0]) -1
    while True:
        #color +=1
        q,color =divmod(color,(-1)*color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            #color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            A_sort[i].append((-1)*color+1)     #辺の色を出力用に決める。1～color_max,A_sortに入れて、再度ソート
            heapq.heappush(color_node[n_a],color)    #前の頂点に使った色を追加、
            heapq.heappush(color_node[n_b],color)    #heapqの最大値出したいので*(-1)

            break
        else:
            color -=1      
#出力
print(color_max)
A_sort.sort()
for i in A_sort:
    print(i[2])

Measured memory_bytes: 122724
//
// Created by Sotetsu KOYAMADA on 2020/03/02.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

bool find(int target, const std::vector<int> &v)
{
    int l = 0, r = v.size(), m;
    while (r - l > 1)
    {
        m = l + (r - l) / 2;
        if (v[m] > target) {
            r = m;
        } else {
            l = m;
        }
    }
    return v[l] == target;
}

int main()
{
    int n, q;
    std::set<int> s;
    std::vector<int> t;

    std::cin >> n;
    int tmp;
    for (int i = 0; i < n; ++i) {
        std::cin >> tmp;
        s.insert(tmp);
    }
    std::cin >> q;
    for (int i = 0; i < q; ++i) {
        std::cin >> tmp;
        t.push_back(tmp);
    }

    std::sort(t.begin(), t.end());

    int ans = 0;
    for (std::set<int>::iterator it = s.begin(); it != s.end(); ++it) {
        if (find(*it, t)) ++ans;
    }
    std::cout << ans << std::endl;
}


Measured memory_bytes: 7936
def main():
    from builtins import int, map, list, print, len
    from collections import deque
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = sys.stdin.readline
    input_list = (lambda: input().rstrip().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    K = input_number()
    cnt = [0]
    queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

    def check():
        now = 0
        while len(queue) > 0 and cnt[0] < K:
            now = queue.popleft()
            cnt[0] += 1
            x = now % 10
            num_ls = [x - 1, x, x + 1]
            for num in num_ls:
                if num < 0 or num > 9: continue
                queue.append(now * 10 + num)
        print(now)
    check()


if __name__ == '__main__':
    main()


Measured memory_bytes: 12396
#!/usr/bin/env python3

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


ans = 0
for num in reversed(range(1, max(h)+1)):
    # print("num", num)
    # print(h)
    count = 0
    for j in range(0, n-1):
        if h[j] == num and h[j+1] < num:
            count += 1
        if h[j] == num:
            h[j] = num-1
    if h[-1] == num:
        count += 1
        h[-1] = num-1
    ans += count

print(ans)


Measured memory_bytes: 3064
A, B = gets.split(' ').map(&:to_i)
i = 0

for a in 1..(A - 1)
  for b in 1..31
    if a == b
      i += 1
    end
  end
end

for b in 1..B
  if A == b
    i += 1
  end
end

puts i

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    vector<int> vec(n);
    map<int,int> ma,ma1;
    for(int i=0;i<n;++i)
    {
        cin>>vec[i];
        ma[vec[i]]=0;
        ma1[vec[i]]++;
    }
    sort(vec.begin(),vec.end());
    int hi=vec[n-1];
    int ans=0;
    for(int i=0;i<n;++i)
    {
        if(ma[vec[i]]==0)
        {
        if(ma1[vec[i]]==1)
        ans++;
        int j=1;
        while(j*vec[i]<=hi)
        {
            if(ma.find(j*vec[i])!=ma.end())
            {
            ma[j*vec[i]]=1;
            }
            j++;
        }
        }
        
    }
    cout<<ans<<"\n";
    
}


Measured memory_bytes: 22568
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
bool serch(std::vector<int>&nums)
{
	const int length = nums.size();
	static int found_hand = 0;
	switch (found_hand)
	{
	case 0:
		int pair[2];
		for (int i = 0; i < length - 1; i++)
		{
			for (int j = i + 1; j < length; j++)
			{
				if (nums[i] == nums[j])
				{
					pair[0] = nums[i];
					pair[1] = nums[j];
					nums.erase(nums.begin() + j);
					nums.erase(nums.begin() + i);
					found_hand++;
					if (serch(nums))
					{
						return true;
					}
					else
					{
						nums.push_back(pair[0]);
						nums.push_back(pair[1]);
						std::sort(nums.begin(), nums.end());
						found_hand--;
					}
				}
			}
		}
		break;
	default:
		int trio[3];
		for (int i = 0; i < length - 2; i++)
		{
			for (int j = i + 1; j < length - 1; j++)
			{
				for (int k = j + 1; k < length; k++)
				{
					if (nums[i] == nums[j] && nums[j] == nums[k] || nums[j] == nums[i] + 1 && nums[k] == nums[j] + 1)
					{
						trio[0] = nums[i];
						trio[1] = nums[j];
						trio[2] = nums[k];
						nums.erase(nums.begin() + k);
						nums.erase(nums.begin() + j);
						nums.erase(nums.begin() + i);
						found_hand++;
						if (found_hand == 5 || serch(nums))
						{
							found_hand = 0;
							return true;
						}
						else
						{
							nums.push_back(trio[0]);
							nums.push_back(trio[1]);
							nums.push_back(trio[2]);
							std::sort(nums.begin(), nums.end());
							found_hand--;
						}
					}
				}
			}
		}
		break;
	}
	return false;
}
int main()
{
	for (std::string str; std::cin >> str;)
	{
		std::vector<int>ans;
		ans.reserve(9);
		std::vector<int>nums;
		nums.reserve(14);
		std::vector<int>appearance_count(9, 0);
		for (auto i : str)
		{
			const int foo = static_cast<int>(i - '0');
			nums.push_back(foo);
			appearance_count[foo]++;
		}
		for (int i = 1; i <= 9; i++)
		{
			if (appearance_count[i] == 4)
			{
				continue;
			}
			auto nums_copy = nums;
			nums_copy.push_back(i);
			std::sort(nums_copy.begin(), nums_copy.end());
			if (serch(nums_copy))
			{
				ans.push_back(i);
			}
		}
		if (ans.size() == 0)
		{
			std::cout << '0';
		}
		else
		{
			for (int i = 0; i < ans.size(); i++)
			{
				if (i != 0)
				{
					std::cout << ' ';
				}
				std::cout << ans[i];
			}
		}
		std::cout << std::endl;
	}
	return 0;
}


Measured memory_bytes: 3180
#include <math.h>

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
#define PI 3.14159265359
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define SIZE_OF_ARRAY(array) (sizeof(array) / sizeof(array[0]))

int main() {
  int A, B;
  cin >> A >> B;

  cout << max(A + B, max(A - B, A * B)) << endl;

  return 0;
}


Measured memory_bytes: 256
import sys
import math
import bisect

def solve(A, B, C):
    n = len(A)
    ans = sum(B)
    for i in range(n):
        if i < n - 1 and A[i] + 1 == A[i+1]:
            ans += C[A[i]-1]
    return ans

def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    print(solve(A, B, C))

if __name__ == "__main__":
    main()


Measured memory_bytes: 3064
n=int(input())

A=[int(i) for i in input().split()]

flg=1
for num in A:
    if num < 0:
        flg*=(-1)
        
B=[abs(i) for i in A]

if flg==1:
    print(sum(B))
else:
    print(sum(B)-2*sorted(B)[0])

Measured memory_bytes: 14412
import java.util.*;

class Main {
    public static void main(String args[]) {
        Scanner inp = new Scanner(System.in);
        do_(inp);
        inp.close();
    }
    public static void do_(Scanner inp) {
        int a = inp.nextInt();
        int b = inp.nextInt();
        if (a < b) System.out.println(0);
        else System.out.println(10);
    }
}


Measured memory_bytes: 21844
while 1:
    n=list(map(int,input().split()))
    if n[0]==0:break
    a=0
    for i in range(n[0],n[1]+1):
        b=i
        while b%5==0: b/=5
        while b%3==0: b/=3
        while b%2==0: b/=2
        if b==1:a+=1
    print(a)

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

typedef long long ll;

const ll Inf = 9000000000000000000ll;

int T;
ll n;
ll a, b, c, d;
map <ll, ll> M;

ll Solve(ll x)
{
    if (x == 0) return 0;
    if (x == 1) return d;
    map <ll, ll>::iterator it = M.find(x);
    if (it == M.end()) {
        ll res = Inf;
        if (x <= Inf / d) res = x * d;
        res = min(res, a + Solve(x / 2) + (x % 2) * d);
        if (x / 2 + 1 < x)
            res = min(res, a + Solve(x / 2 + 1) + (2 - x % 2) * d);
        res = min(res, b + Solve(x / 3) + (x % 3) * d);
        if (x / 3 + 1 < x)
            res = min(res, b + Solve(x / 3 + 1) + (3 - x % 3) * d);
        res = min(res, c + Solve(x / 5) + (x % 5) * d);
        if (x / 5 + 1 < x)
            res = min(res, c + Solve(x / 5 + 1) + (5 - x % 5) * d);
        M.insert(make_pair(x, res));
        return res;
    }
    return it->second;
}

int main()
{
    scanf("%d", &T);
    while (T--) {
        scanf("%lld", &n);
        scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
        M.clear();
        printf("%lld\n", Solve(n));
    }
    return 0;
}


Measured memory_bytes: 4948
import java.util.*;

public class Main{
	
	private void doit(){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			String s = sc.next();
			while(s.length() > 0){
				int prevlen = s.length();
				s = s.replaceAll("mmewe", "me").replaceAll("emeww", "ew");
				if(s.length() == prevlen){
					break;
				}
			}
			System.out.println(s.equals("mew") ? "Cat" : "Rabbit");
		}
	}
	

	private void debug(Object... o) {
		System.out.println("debug = " + Arrays.deepToString(o));
	}

	public static void main(String[] args) {
		new Main().doit();
	}
}

Measured memory_bytes: 21544
#include <iostream>
#include <stdint.h>
#include <string>
#include <utility>
#include <map>
#include <algorithm>

using namespace::std;

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

	string str;
	cin >> str;

	map<pair<string, string>, int> mp;
	map<pair<string, string>, int> mq;

	for (int i = 0; i < (1 << N); i++)
	{
		string u = "";
		string v = "";

		for (int j = 0; j < N; j++)
		{
			if (i & (1 << j))
				u.push_back(str[j]);
			else
				v.push_back(str[j]);
		}

		reverse(v.begin(), v.end());
		mp[make_pair(u, v)]++;
	}

        for (int i = 0; i < (1 << N); i++)
        {
                string u = "";
                string v = "";

                for (int j = 0; j < N; j++)
                {
                        if (i & (1 << j))
                                u.push_back(str[N + j]);
                        else
                                v.push_back(str[N + j]);
                }
		
		reverse(v.begin(), v.end());
		mq[make_pair(v, u)]++;
        }

	int64_t ans = 0;
	for (map<pair<string, string>, int>::iterator it = mp.begin(); it != mp.end(); it++)
	{
		pair<string, string> s = it->first;
		int64_t x = it->second;
		int64_t y = mq[s];

		ans += x * y;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 103424
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cstring>
#include <climits>
using namespace std;
#define ll long long
#define FOR(i,n) for(int i=0;i<n;i++)
#define sz(x) (int)(x.size())
#define all(x) (x).begin(),(x).end()
template<typename tp> void read(tp &x) {cin >> x;}
template<typename tp, typename... Args> void read(tp& x, Args&... args) {read(x);read(args...);}
const int mxN = (int)1e5,INF = (int)1e9,MOD = (int)1e9+7;

void solve()
{
	int n;
	read(n);
	int a[n][3];
	FOR(i,n) read(a[i][0],a[i][1],a[i][2]);
	int dp[n][3];//dp[i][j] max happy sum if he select the jth activity in the ith day
	FOR(i,3) dp[0][i] = a[0][i];
	for(int i=1;i<n;i++)
	{
		dp[i][0] = a[i][0] + max(dp[i-1][1],dp[i-1][2]);
		dp[i][1] = a[i][1] + max(dp[i-1][0],dp[i-1][2]);
		dp[i][2] = a[i][2] + max(dp[i-1][1],dp[i-1][0]);
	}
	cout << max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int test = 1;
	//read(test);
	while(test--)
		solve();
	return 0;
}



Measured memory_bytes: 5968
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

int main(int argc, void **argv)
{
	int N;
	long long A[100000];
	unsigned long long sum = 0;
	int count = 0;

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%lld", &A[i]);
		if( A[i] < 0 ) count++;
	}

	if( count % 2 == 0 )
	{
		for (int i = 0; i < N; i++)
		{
			unsigned long long abs;
			abs = A[i] >= 0 ? A[i] : -A[i];
			sum += abs;
		}
	}
	else
	{
		unsigned long long min = 1 * 1000 * 1000 * 1000;

		for (int i = 0; i < N; i++)
		{
			unsigned long long abs;
			abs = A[i] >= 0 ? A[i] : A[i] * -1;
			sum += abs;
			min = min > abs ? abs : min;
		}

		sum -= min * 2;
	}

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

	return 0;
}

Measured memory_bytes: 896
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
static const int VMAX = 10000;
int NV, NE;

class DisjointSet {
public:
  vector<int> rank, parent;
  int nset;
  DisjointSet() {}
  DisjointSet(int size) {
    rank.resize(size);
    parent.resize(size);
    nset = size;
    for (int i = 0; i < size; i++) {
      rank[i] = 0;
      parent[i] = i;
    }
  }
  void unite(int x, int y) { link(find_set(x), find_set(y)); }
  void link(int x, int y) {
    if (rank[x] < rank[y]) {
      parent[x] = y;
    } else {
      parent[y] = x;
      if (rank[x] == rank[y]) {
        rank[x]++;
      }
    }
    nset--;
  }
  int find_set(int x) {
    if (x != parent[x]) {
      parent[x] = find_set(parent[x]);
    }
    return parent[x];
  }
  bool same(int x, int y) { return find_set(x) == find_set(y); }
};

struct Edge {
  int x1, x2, weight;
  bool operator<(const Edge &right) const { return weight < right.weight; }
};

int main() {
  cin >> NV >> NE;
  vector<Edge> edges;
  for (int i = 0; i < NE; i++) {
    int s, t, w;
    cin >> s >> t >> w;
    edges.push_back(Edge{s, t, w});
  }
  auto ds = DisjointSet(NV);
  sort(edges.begin(), edges.end());

  int sum = 0;
  for (auto e : edges) {
    if (!ds.same(e.x1, e.x2)) {
      ds.unite(e.x1, e.x2);
      sum += e.weight;
      if (ds.nset == 1)
        break;
    }
  }
  cout << sum << endl;
}

Measured memory_bytes: 4552
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct UnionFind
{
    vector<ll> par;
    vector<ll> rank;
    vector<ll> sz;
    UnionFind(ll n) : par(n), rank(n), sz(n)
    {
        for(ll i = 0; i < n; i++)
        {
            par[i] = i;
            rank[i] = 0;
            sz[i] = 1;
        }
    }
    ll root(ll x)
    {
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }
    void unite(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        if(x == y) return;
        if(rank[x] < rank[y])
        {
            par[x] = y;
            sz[y] += sz[x];
        }
        else
        {
            par[y] = x;
            sz[x] += sz[y];
            if(rank[x] == rank[y]) rank[x]++;
        }
    }
    bool same(ll x, ll y)
    {
        return root(x) == root(y);
    }
    ll size(ll x)
    {
        x = root(x);
        return sz[x];
    }
};

int main()
{
    ll n, m;
    cin >> n >> m;
    struct edge { ll from; ll to;};
    vector<edge> d(m);
    for(ll i = 0; i < m; i++)
    {
        ll a, b;
        cin >> d[i].from >> d[i].to;
    }


    vector<ll> ans;
    ll count = n * (n-1) / 2;
    ans.push_back(count);

    UnionFind tree(n+1);
    for(ll i = m -1; i >= 0; i--)
    {
        edge e = d[i];
        ll x = e.from;
        ll y = e.to;
        if(!tree.same(x, y))
        {
            int px = tree.size(x);
            int py = tree.size(y);
            tree.unite(x, y);

            count = count - px*py;
        }

        ans.push_back(count);
    }
    for(ll i = m-1; i >=0; i--)
    {
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 6132
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  VI ps(n);
  FOR(p, ps) {
    cin >> p;
  }
  VI rev(n+1);
  REP(i,0,n) {
    rev[ps[i]] = i + 1;
  }
  multiset<int> pos = {0, 0, n + 1, n + 1};
  ll ans = 0;
  for (int i = n; i >= 1; i--) {
    int p = rev[i];
    auto it = pos.lower_bound(p);
    ll r1 = *it;
    ll r2 = *++it;
    --it;
    ll l1 = *--it;
    ll l2 = *--it;
    ans += i * ((p - l1) * (r2 - r1) + (r1 - p) * (l1 - l2));
    pos.insert(p);
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 5760
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPA(i,n) for(int i=1;i<(n);++i)
#define MOD ((int)1e9 + 7)
#define INF ((int)1e9)
#define ALL(x) (x).begin(),(x).end()
#define ctoi(x) (x - 'a') 
#define CTOI(x) (x - 'A')
using namespace std;
int main(){
    string str;
    cin >> str;
    if(str=="ani"){
        cout << "square1001" << endl;
    }else{
        cout << "e869120" << endl;
    }
    return 0;
}



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

#define REP(i ,n) for(int i=0 ;i < n; i++)
#define REPB(i ,n) for(int i=n; i >= 0; i--)
#define FOR(i ,m ,n) for(int i=m; i < n; i++)
#define FORB(i, m, n) for(int i=m; i>= m; i--)
#define ll long long
#define pb push_back
#define popb pop_back
#define debug(i) cout << i << endl
using namespace std;
int main(){
  int a,b;
  int count[5] = {};
  int ans = 0;
  REP(i,3){
      cin >> a >> b;
      FOR(j,1,5){
         if(a == j || b == j) count[j]++;
        }
    }
    REP(i,5){
        if(count[i] >= 2) ans++;
        if(ans == 2){
            cout << "YES" << endl;
            return 0;
          }
      }

    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using ll=long long;
using namespace std;
#define rep_i(i, n) for (int i = 0; i < (n); ++i)
#define rep_ll(i, n) for (long long i = 0; i < (n); ++i)
#define r_rep_i(i, start, end) for (int i = (start); i < (end); ++i)
#define r_rep_ll(i, start, end) for (long long i = (start); i < (end); ++i)
#define debug_vi(v) copy((v).begin(), (v).end(), ostream_iterator<int>(cout, " "));
#define debug_vll(v) copy((v).begin(), (v).end(), ostream_iterator<long long>(cout, " "));
#define debug_vd(v) copy((v).begin(), (v).end(), ostream_iterator<double>(cout, " "));
#define sort_v(v) sort((v).begin(), (v).end()); //昇順
#define d_sort_vi(v) sort((v).begin(), (v).end(), greater<int>()); //降
#define d_sort_vd(v) sort((v).begin(), (v).end(), greater<double>()); //昇順
#define say(t) cout << (t) << endl;
#define sum_vi(v) accumulate((v).begin(), (v).end(), 0);
#define sum_vll(v)accumulate((v).begin(), (v).end(), 0LL);

ll gcd(ll a, ll b) { return b?gcd(b, a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a, b)*b;}
const int IINF=(1<<30);
const ll LLINF = 1LL<<60;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n; cin >> n;
  vector<int> hoge(n);
  vector<int> fuga(n);
  rep_i(i, n){
    cin >> hoge[i];
    fuga[i] = hoge[i];
  }
  sort_v(fuga);
  int a = fuga[n/2];
  int b = fuga[(n/2) - 1];
  
  rep_i(i, n){
    if(hoge[i] < a){
      cout << a << endl;
    }else{
      cout << b << endl;
    }
  }
}

Measured memory_bytes: 3840