akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(void) {
	int N,M;
	cin >> N >> M;
	vector< pair<long long,long long> > data(N);
	for (int i = 0; i < N; ++i) {
		cin >> data[i].first >> data[i].second;
	}
	sort(data.begin(),data.end());
	long long res = 0;
	long long nod = 0;
	for (int i = 0; nod < M && i < N; ++i) {
		if (nod+data[i].second < M) {
			nod += data[i].second;
			res += data[i].first * data[i].second;
		}
		else {
			res += data[i].first * (M - nod);
			nod = M;
		}
	}
	cout << res << endl;
	return 0;
}


Measured memory_bytes: 1792
package main

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

func main() {
	n := splitIntStdin(" ")
	x := (n[0] + n[1] + 1) / 2.0
	fmt.Println(x)
}

/* template */
var sc = bufio.NewScanner(os.Stdin)

// 文字列を1行取得
func strStdin() (stringInput string) {
	sc.Scan()
	stringInput = sc.Text()
	stringInput = strings.TrimSpace(stringInput)
	return
}

// 整数値1つ取得
func intStdin() (num int) {
	stringInput := strStdin()
	num, _ = strconv.Atoi(strings.TrimSpace(stringInput))
	return
}

// 空白や空文字だけの値を除去したSplit()
func splitWithoutEmpty(stringTargeted string, delim string) (stringReturned []string) {
	stringSplited := strings.Split(stringTargeted, delim)

	for _, str := range stringSplited {
		if str != "" {
			stringReturned = append(stringReturned, str)
		}
	}
	return
}

// デリミタで分割して文字列スライスを取得
func splitStrStdin(delim string) (stringReturned []string) {
	// 文字列で1行取得
	stringInput := strStdin()
	// 空白で分割
	stringReturned = splitWithoutEmpty(stringInput, delim)
	return
}

// デリミタで分割して整数値スライスを取得
func splitIntStdin(delimiter string) (intAry []int) {
	// 文字列スライスを取得
	strAry := splitStrStdin(delimiter)

	// 整数スライスに保存
	for i := range strAry {
		num, err := strconv.Atoi(strAry[i])
		if err != nil {
			panic(err)
		}
		intAry = append(intAry, num)
	}
	return
}
/* template */

Measured memory_bytes: 640
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int H = sc.nextInt();
            int W = sc.nextInt();
            if(H==0 && W==0){
                break;
            }
            for(int i=0;i<H;i++){
                for(int j=0;j<W;j++){
                    System.out.print("#");
                }
                System.out.println();
            }
            System.out.println();
        }
    }
}


Measured memory_bytes: 36296
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,k;
ll ans=1;
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		if(i==1)
			ans*=1LL*k;
		else
			ans*=1LL*(k-1);
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,L,R;
string S, T;
const ll MOD = 998244353;
const ll INF = 1LL << 60;
typedef pair<ll,ll> P;

int main() {
    cin>>N;
    vec l(N);
    rep(i,N) cin>>l[i];
    sort(ALL(l));
    ll sum = 0;
    rep(i,N){
        reps(j, i + 1, N){
            ll mini = abs(l[i] - l[j]), maxi = l[i] + l[j];
            ll num = lower_bound(ALL(l), maxi) - upper_bound(ALL(l), mini);
            if(mini < l[i] && l[i] < maxi) --num;
            if(mini < l[j] && l[j] < maxi) --num;
            //cout<<i<<' '<<j<<' '<<num<<endl;
            sum += num;
        }
    }
    cout<<sum/3<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

int main() {
    int D, N;
    cin >> D >> N;
    if (D == 0){
        if (N == 100)cout << 101;
        else cout << N;
    } else if (D == 1){
        if (N == 100)cout << 10100;
        else cout << N * 100;
    } else {
        if (N == 100)cout << 1010000;
        else cout << N * 10000;
    }

	return 0;
}

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

#define MAXN (410)
#define MAXM (100010)

int n, m;
std::pair<int, int> act[MAXM];
std::bitset<MAXN> s[MAXN];

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++ i){
		scanf("%d%d", &act[i].first, &act[i].second);
	}
	for(int i = 1; i <= n; ++ i){
		s[i][i] = 1;
		for(int j = m; j >= 1; -- j){
			int x = act[j].first, y = act[j].second;
			bool xin = s[i][x];
			bool yin = s[i][y];
			if( xin &&  yin) s[i].reset();
			if( xin && !yin) s[i].set(y) ;
			if(!xin &&  yin) s[i].set(x) ;
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++ i){
		for(int j = i + 1; j <= n; ++ j){
			if(s[i].any() && s[j].any()){
				std::bitset<MAXN> now = s[i] & s[j];
				ans += now.none();
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(int i=num, i##_len=(n); i<i##_len; ++i)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define print(x) (cout << (x) << endl)
#define pb push_back
#define mp make_pair
#define sz(x) int(x.size())
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
#define fs first
#define sc second
// 多倍長
#include <boost/rational.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using boost::rational;
using boost::multiprecision::cpp_int;

const int INF = 1e9;
const ll LLINF = 1e16;
const ll MOD = 1e9+7;
template<class T> inline void add(T &a, T b){a = ((a+b) % MOD + MOD) % MOD;};

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}
 
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
 

// 指定した文字cが文字列に何文字入ってるか
ll stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c);
}


// 割り算の切り上げ処理
template<typename T>
T rp(T a, T b) {
  return (a + b - 1) / b;
}

// 桁和
template<typename T>
T digsum(T n) {
    T res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}

// 回文判定
bool kai (string s) {
    string t{s};
    reverse(begin(t), end(t));
    return s == t;
}

using pint = pair<int, int>;
using pll = pair<ll, ll>;


vector<string> split(const string &s, char delim) {
    vector<string> elems;
    string item;
    for (char ch: s) {
        if (ch == delim) {
            if (!item.empty())
                elems.push_back(item);
            item.clear();
        }
        else {
            item += ch;
        }
    }
    if (!item.empty())
        elems.push_back(item);
    return elems;
}




int main(void)
{
    cout.tie(0);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    string s;
    ll q;
    cin >> s >> q;
    int flag = 1;
    deque<char> d;
    rep(i, sz(s)) d.pb(s[i]);
    rep(i, q){
        int qu;
        cin >> qu;
        if(qu == 1) flag = 1 - flag;
        else {
            int f;
            char c;
            cin >> f >> c;
            if(f == 1){
                if(flag) d.push_front(c);
                else d.push_back(c);
            } else {
                if(flag) d.push_back(c);
                else d.push_front(c);
            }
        }
    }
    if(!flag) reverse(all(d));
    for(auto c : d){
        cout << c;
    }
    cout << endl;


}


Measured memory_bytes: 4004
def main():
    s = input()
    ans = ""
    for i in range(len(s)):
        if s[i] == "0":
            ans += "0"
        elif s[i] == "1":
            ans += "1"
        elif s[i] == "B":
            if ans == "":
                pass
            else:
                ans = ans[:-1]
    print(ans)



if __name__ == "__main__":
    main()

Measured memory_bytes: 38256
#include <iostream>
#include <algorithm>
#include <cstdlib>

int x, a, b;
int main(void){
    std::cin >> x >> a >> b;

    if(std::abs(x-a) < std::abs(x-b)){
        std::cout << "A" << std::endl;
    }else{
        std::cout << "B" << std::endl;
    }
}


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

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll a, b, c; cin >> a >> b >> c;
  if(c-a-b > 0 && (c-a-b)*(c-a-b) > 4*a*b){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include<algorithm>
#include<functional>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#include<climits>

#define all(c) (c).begin(), (c).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb(e) push_back(e)
#define mp(a, b) make_pair(a, b)
#define fr first
#define sc second

typedef unsigned long long UInt64;
typedef long long Int64;

const int INF=100000000;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

using namespace std;

typedef pair<int ,int > P;

void solve(int n)
{
	vector<P> vec;
	rep(i,n)
	{
		int p,d1,d2;
		cin>>p>>d1>>d2;
		vec.pb(P(d1+d2,p));
	}

	sort(all(vec),greater<P>());

	vector<P>::iterator it = vec.begin();

	cout<<it->sc<<" "<<it->fr<<endl;

}

int main()
{
	int n;
	while(cin>>n)
	{
		if(n==0) return 0;

		solve(n);
	}
		return 0;
}

Measured memory_bytes: 1328
#include <bits/stdc++.h>
using namespace std;
const long double PI = 3.141592653589793;
const long double DEL = 1e-10;
const int mod =  1000000007;

#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mpq priority_queue<int,vector<int>,greater<int>>
#define deb(a) cerr << #a << ": " << a << endl
#define vvpii vector<vector<pair<int,int>>>
#define ftt cin>>t;for(int tt=1;tt<=t;++tt)
#define Rev(v) reverse(v.begin(),v.end())
#define Sort(v) sort(v.begin(),v.end())
#define mem(a,b) memset(a,b,sizeof(a))
#define forr(i,a,b) for(i=a;i<=b;i++)
#define umii unordered_map<int,int>
#define vpii vector<pair<int,int>>
#define all(a) a.begin() , a.end()
#define vvi vector<vector<int>>
#define pq priority_queue<int>
#define sqr(a) (((a) * (a)))
#define double long double
#define dbg cout<<"\nhi\n"
#define pii pair<int,int>
#define mii map<int,int>
#define vb vector<bool>
#define vi vector<int>
#define int long long
#define nl cout<<"\n"
#define pb push_back
#define sp <<" "<<
#define ss second
#define ff first
inline void read(int &x)
{
      int c = getchar();
      x = 0;
      int neg = 0;
      for(; ((c<48 || c>57) && c != '-'); c = getchar());
      if(c=='-')
      {
            neg = 1;
            c = getchar();
      }
      for(; c>47 && c<58 ; c = getchar())
      {
            x = (x<<1) + (x<<3) + c - 48;
      }
      if(neg)
      {
            x = -x;
      }
}
int fpow(int x, int n)
{
    int res = 1;
    while(n){
          if(n&1){
                res = res * x % mod;
          }
          x = x * x % mod;
          n>>=1;
    }
    return res;
}
int gcd(int a,int b)
{
    if(b == 0)
    {
          return a;
    }
    return gcd(b,a % b);
}
void sieve(int n)
{
      bool prime[1000006];
      memset(prime, true, sizeof(prime));
      int rootn = (int)sqrt(n);
      for (int p = 2; p <= rootn; p++)
      {
            if (prime[p] == true)
            {
                  for (int i = p*p; i <= n; i += p)
                  {
                        prime[i] = false;
                  }
            }
      }
      prime[1] = 0;
}
const int N = 100050;
int cnt, sum, mid, mx, mn, ans, a[N], b[N];
int n, m, d, i, j, k, l, p, q, r, t, w, x, y, z;
bool f, f1, f2;
string s;

//******************************************* CHECK CONSTRAINTS **************************************************

int check(int i,int j,int k)
{
      vi v = {i,j,k};
      Sort(v);
      return v[2] < v[0] + v[1];
}

int32_t main()
{     fio;
      cin>>x>>k>>d;
      x = abs(x);
      if(x >= __int128(k)*d)
      {
            cout<<x-k*d;
      }
      else
      {
            if(d<=x)
            {
            k-=x/d;
            if(k&1)
            {
                  cout<<d-(x%d);
            }
            else
            {
                  cout<<x%d;
            }
            }
            else
            {
                  if(k&1)
                  {
                        cout<<d-x;
                  }
                  else
                  {
                        cout<<x;
                  }
            }
      }
     
}
/*
 10 10 10
 */


Measured memory_bytes: 3572
import sys
from operator import itemgetter, attrgetter
N = int(input())
AB = []
for _ in range(N):
  AB.append(tuple(map(int, input().split())))
AB.sort(key = itemgetter(1))

Asum = 0
for i in range(N):
  Asum += AB[i][0]
  if Asum > AB[i][1]:
    print("No")
    sys.exit()
print("Yes")

Measured memory_bytes: 31832
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Scanner;

public class Main {

  public static void main(String[] args)  {

    //Scanner cin = new Scanner(new FileReader("input.txt"));
    Scanner cin = new Scanner (System.in);
    int max = cin.nextInt();
    int mul = cin.nextInt();


    if (mul%2==0){
      int start = mul/2;
      int time = max/start;
      long res = 0;
      if (time%2==0){
        res = (long)Math.pow((time/2),3)*2;
      }
      else {
        res = (long)Math.pow(time/2+1,3)+(long)Math.pow(time/2,3);
      }
      if (res<=Integer.MAX_VALUE)
        System.out.println((int)res);
      else
        System.out.println(res);
    }

    else {
      int time = max / mul;
      long res = (long)Math.pow(time,3);

      if (res<=Integer.MAX_VALUE)
        System.out.println((int)res);
      else
        System.out.println(res);
    }

  }

}

Measured memory_bytes: 22612
#include <stdio.h>

int w, h, n;
int x[100];
int y[100];
int a[100];
int map[100][100];

int main(void)
{
	int i, j, k;
	int x1, x2, y3, y4;
	int w_end, h_end;

	scanf("%d %d %d", &w, &h, &n);
	x1 = 0;
	x2 = w;
	y3 = 0;
	y4 = h;

	for (i = 0; i < n; i++) {
		scanf("%d %d %d", &x[i], &y[i], &a[i]);
	}

	for (i = 0; i < n; i++) {
		for (i = 0; i < n; i++) {
			switch (a[i]) {
			case 1:
				if (x[i] > x1) {
					x1 = x[i];
				}
				break;
			case 2:
				if (x[i] < x2) {
					x2 = x[i];
				}
				break;
			case 3:
				if (y[i] > y3) {
					y3 = y[i];
				}
				break;
			case 4:
				if (y[i] < y4) {
					y4 = y[i];
				}
				break;
			}
		}
	}

	w_end = x2 - x1 > 0 ? x2 - x1 : 0;
	h_end = y4 - y3 > 0 ? y4 - y3 : 0;

	printf("%d\n", w_end * h_end);

	return 0;
}


Measured memory_bytes: 128
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

s = input()

if int(s[0:4]) <= 2019:
    if int(s[5:7]) <= 4:
        if int(s[8:]) <= 30:
            print("Heisei")
            exit()

print("TBD")


Measured memory_bytes: 8964
num_1 , num_2 = input().split()
num_1 = int(num_1)
num_2 = int(num_2)

if (num_1 > 0) and (num_2 > 0):
    print("Positive")

elif ((num_1 > 0) and (num_2 < 0)) or ((num_1 < 0) and (num_2 > 0)):
    print("Zero")

elif (num_1 < 0)and (num_2 < 0):
    if ((num_1 - num_2)%2) == 0:
        print("Negative")
    else:
        print("Positive")


Measured memory_bytes: 3060
N = int(input()) 
e=[0]*(N+1)
for i in range(2, N+1):
    cur = i
    for j in range(2, i+1):
        while cur % j == 0:
            e[j] += 1
            cur //= j
def num(m):
    return len(list(filter(lambda x: x >= m-1, e)))
print(num(75) + num(25) * (num(3) - 1) + num(15) * (num(5) - 1)+ num(5) * (num(5) - 1) * (num(3) - 2) // 2) 

Measured memory_bytes: 38512
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>

using namespace std;

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

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

	double sum = 0;
	for (auto x: a) {
		sum += 1.0 / x;
	}
	double ans = 1.0 / sum;
	printf("%.9f\n", ans);
	return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

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

ll mod(ll a){
  return (a % 1000000007);
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}



int main(){
  string sa,sb,sc; cin >> sa >> sb >> sc;
  ll nowa,nowb,nowc; nowa = 0; nowb = 0; nowc = 0;
  char nowturn = 'a'; char ans = '0';
  
  while(ans == '0'){
    

    
    if(nowturn == 'a'){
      if(nowa == sa.size()){
        ans = 'A';
        break;
      }
      
      nowturn = sa[nowa];
      nowa++;
      continue;
    }
    
    else if(nowturn == 'b'){ 
      if(nowb == sb.size()){
        ans = 'B';
        break;
      }
      
      nowturn = sb[nowb];
      nowb++;
      continue;
      
     
    }
    
    else{ 
      
      if(nowc == sc.size()){
        ans = 'C';
        break;
      }
      
      nowturn = sc[nowc];
      nowc++;
      continue;
      
     
    }
    
  }
  
  
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
tmp = input().split()
b = []
ans = []

for i in range(N):
  b.append(tmp[i])
  
for index, item in enumerate(b):
  if int(item) > index+1:
    print('-1')
    exit()
  dist = index + 1 - int(item)
  ans.insert(index-dist, int(item))

for i in range(len(ans)):
  print(ans[i])

Measured memory_bytes: 3064
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.nextLine();
		char[] c = new char[3];
		c = n.toCharArray();
		for(int i = 0; i < 3; i++) {
			if(c[i] == '1')c[i] = '9';
			else if(c[i] == '9')c[i] = '1';
			System.out.print(c[i]);
		}
	}
}

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

int main(){
  int n;
  cin >> n;
  int t,a;
  cin >> t >> a;
  int ans,res;
  res = 100000000;
  for(int i=0; i<n; i++){
    int d;
    int x;
    cin >> x;
    d = abs(a*1000-(t*1000-x*6));
    if(res>d){
      res = d;
      ans = i+1;
    }
  }
  cout << ans << endl;
  return 0;
}


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

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin>>n;
  while(n--){
    int x;
    cin>>x;
    if(x%2==0 && x%3!=0 && x%5!=0){
      cout<<"DENIED"<<'\n';
      return 0;
    }
  }
  cout<<"APPROVED"<<'\n';
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(ll i=0;i<(n);i++)
template<typename T =ll> using v = vector<T>;
template<typename T =ll> using vv = v<v<ll>>;
template<typename T> T chmin(T &a,T b) {return a=min(a,b);}
template<typename T> T chmax(T &a,T b) {return a=max(a,b);}
const ll INF = (ll)1e9;

void a(){
    ll x,y,z;
    cin >> x >> y >> z;
    swap(x,y);
    swap(x,z);
    cout << x<< ' ' << y<< ' ' << z;
}

void b(){

}

void c(){

}

void d(){

}

int main(){
    a();
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
pair<double,double> a[10];
vector<int> cal;
int main(){
    int n;
    double ans=0,c=1;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].first>>a[i].second;
        c*=(i);
        cal.push_back(i);
    }
    do{

        for(int i=0;i<n-1;i++){
            double k = sqrt(pow(a[cal[i]].first-a[cal[i+1]].first,2)+pow(a[cal[i]].second-a[cal[i+1]].second,2));
            ans+=k;
            //cout<<cal[i]<<' ';
        }
        //cout<<'\n';
    }while(next_permutation(cal.begin(),cal.end()));
    printf("%.8f",ans/c);


}


Measured memory_bytes: 256
N,W = map(int, input().split())

import numpy as np
dp = np.full(N*1000+1, W+1, dtype=int)
dp[0] = 0

for n in range(N):
  w,v = map(int, input().split())
  dp[v:] = np.minimum(dp[:-v]+w, dp[v:])

print(np.max(np.where(dp <= W)))

Measured memory_bytes: 14900
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(a,b,c) for (int a=b;a<=c;a++)
#define per(a,b,c) for (int a=b;a>=c;a--)
#define go(u) for (int o=ft[u],v;v=E[o].t;o=E[o].n)
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> par;
const int P=1000000007; 
const int N=4000010;
LL inv[N],s1[N],s2[N],f[2010][2010];
int n,k;
void upd(LL &x,LL y){x=(x+y)%P;}
LL C(LL n,LL m){return s1[n]*s2[m]%P*s2[n-m]%P;}
int main(){
	scanf("%d%d",&n,&k);
	inv[1]=1;
	rep(i,2,n*k) inv[i]=inv[P%i]*(P-P/i)%P;
	s1[0]=s2[0]=1;
	rep(i,1,n*k) s1[i]=s1[i-1]*i%P,s2[i]=s2[i-1]*inv[i]%P;
	if (k==1) return puts("1"),0;
	--k;
	f[0][0]=1;
	rep(i,0,n) rep(j,0,i){
		LL s=i*k+j,fx=f[i][j];
		upd(f[i+1][j],fx*C(s+k-1,k-1)%P*(n-i));
		upd(f[i][j+1],fx);
	}
	printf("%lld\n",f[n][n]);
	return 0;
}


Measured memory_bytes: 124032
/******************************\
*  Everyone has a different way of thinking, so God Created us
Hope You Respect My Way..,Thank You ):  *
*                            *
*   Created by : Murad   *
\******************************/
//std::transform(s1.begin(), s1.end(), s1.begin(),::tolower);
#include<bits/stdc++.h>
using namespace std;
#define pi 3.1415926536
#define forn(i,a,b)for(int i=a;i<b;i++)
#define LL long long
#define MP make_pair
#define ff first
#define ss second
#define INF 2147483647
#define _INF -2147483647
#define pq priority_queue
#define MM multimap
#define PB push_back
#define ipair pair<int,int>
#define lpair pair<LL,LL>
#define MAXN 100004
#define El3zba ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define modd 1000000007
LL MMIN(LL a, LL b)
{
	if (a <= b)
		return a;
	else
		return b;
}
LL MMAX(LL a, LL b) {
	if (a >= b)
		return a;
	else
		return b;
}
int main()
{
	El3zba;
	int a, b;
	cin >> a >> b;
	if (b == 1)return cout << 0 << endl, 0;
	int now = a;
	int ans = 1;
	while (now < b)
	{
		now += a - 1;
		ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
L = int(input())
  
ret = []
count = 0
for i in range(19, 0, -1) :
    while L - (1 << (i - 1)) >= 0 :
        ret.append((i, count))
        count += 1 << (i - 1)
        L -= 1 << (i - 1)

N = ret[0][0]
M = len(ret) + 2 * (N - 1)

print(N + 1, M)
for i in range(1, N) :
    print(i, i + 1, 0)
    print(i, i + 1, 1 << (i - 1))
for r in ret :
    print(r[0], N + 1, r[1])

Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> A;
    A.reserve(n);
    for (int i = 0; i < n; ++i) {
        int a;
        cin >> a;
        A.push_back(a);
    }
    vector<vector<int>> G(n);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    vector<int> seen(n);
    vector<int> r;
    auto dfs = [&A, &G, &seen] (int i) {
        stack<int> q;
        seen[i] = 1;
        q.push(i);
        int ans = i;
        while (!q.empty()) {
            int v = q.top();
            q.pop();
            if (A[ans] > A[v]) {
                ans = v;
            }
            for (int w : G[v]) {
                if (!seen[w]) {
                    seen[w] = 1;
                    q.push(w);
                }
            }
        }
        return ans;
    };

    for (int i = 0; i < n; ++i) {
        if (!seen[i]) {
            r.push_back(dfs(i));
        }
    }

    int cc = r.size();
    if (2 * cc - 2 > n) {
        cout << "Impossible" << endl;
    } else if (cc == 1) {
        cout << 0 << endl;
    } else {
        long long ans = 0;
        for (int v : r) {
            ans += A[v];
            seen[v] = 0;
        }
        priority_queue<int, vector<int>, greater<int>> q;
        for (int i = 0; i < n; ++i) {
            if (seen[i]) {
                q.push(A[i]);
            }
        }
        for (int i = 0; i < cc - 2; ++i) {
            ans += q.top();
            q.pop();
        }
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 7168
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<stack>
#include<queue>
#include<algorithm>
#include<set>
#include<vector>
#include<cmath>
#define lmid l,m,rt<<1
#define rmid m+1,r,rt<<1|1
#define LL long long
#define rl r-l+1
using namespace std;
int main()
{
    int n;
    scanf("%d",&n);
    int ans=1;
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        int temp=i;
        int res=0;
        while(temp)
        {
            if(temp%2==0)
            {
                res++;
                temp/=2;
            }
            else break;
        }
        if(res>=sum)
        {
            sum=res;
            ans=i;
        }
    }
    cout<<ans<<endl;
}


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

int main(){
    int i = 0;
    int cnt = 0;
    char *S = malloc(sizeof(char)*200005);
    char *T = malloc(sizeof(char)*200005);
    scanf("%s", S);
    scanf("%s", T);
    while (S[i]){
        if (S[i] != T[i]){
            cnt++;
        }
        i++;
    }
    printf("%d", cnt);
    return 0;
}

Measured memory_bytes: 2116
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
	int a, b,sum=0;
	cin >> a >> b;
	if (a > b) {
		sum = a;
		a--;
	}
	else if (a < b) {
		sum = b;
		b--;
	}
	else {
		sum = a;
		a--;
	}
	sum += max(a, b);
	cout << sum << endl;
	

}

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

int bin[45], k[45], N;
long se(int key, bool small){
    if(key<0) return 0;
    long mul=1;
    for(int i=0; i<key; ++i) mul *= 2;
    if(small) return max(bin[key], N-bin[key])*mul+se(key-1, true);
    else{
        if(k[key]==0) return bin[key]*mul+se(key-1, false);
        else{
            if(bin[key]*2<N){
                return max(bin[key]*mul+se(key-1, true), (N-bin[key])*mul+se(key-1, false));
            }
            else return bin[key]*mul+se(key-1, true);
        }
    }
}
int main() {
	long K, A;
	cin >> N >> K;
	for(int i=0; K>0; ++i){
	    k[i]=K%2;
	    K /= 2;
	}
	for(int i=0; i<N; ++i){
	    cin >> A;
	    for(int j=0; A>0; ++j){
	        bin[j] += A%2;
	        A /= 2;
	    }
	}
	cout << se(44, false) << endl;
	return 0;
}


Measured memory_bytes: 256
import collections
H, W = map(int, input().split())
As = collections.defaultdict(int)
for _ in range(H):
    for a in input():
        As[a] += 1
flag = True
if H%2 == 0 and W%2 == 0:
    for i in As.values():
        if i % 4 != 0:
            flag = False
            break
elif H%2 == 0:
    odd = 0
    for i in As.values():
        if i%2 == 1:
            odd += 1
    if odd:
        flag = False
    else:
        four = 0
        for i in As.values():
            four += i//4
        if four >= H*(W-1)//4:
            flag = True
        else:
            flag = False
elif W%2 == 0:
    odd = 0
    for i in As.values():
        if i%2 == 1:
            odd += 1
    if odd:
        flag = False
    else:
        four = 0
        for i in As.values():
            four += i//4
        if four >= W*(H-1)//4:
            flag = True
        else:
            flag = False
else:
    odd = 0
    even = 0
    for i in As.values():
        if i%2 == 0:
            even += 1
        else:
            odd += 1
    if odd >= 2:
        flag = False
    else:
        four = 0
        for i in As.values():
            four += i//4
        if four >= (H*W-(H+W-1))//4:
            flag = True
        else:
            flag = False
if flag:
    print('Yes')
else:
    print('No')
    

Measured memory_bytes: 3316
#include <iostream>
#include <stdio.h>
using namespace std;
int main(){
    int a,b,d,r;
    double f;
    cin>>a>>b;
    d=a/b;
    r=a%b;
    f=(a*1.0)/(b*1.0);
    cout<<d<<" "<<r<<" ";
    printf("%.8lf\n", f);
    return 0;
}


Measured memory_bytes: 3220
///╔══╗
///╚╗╔╝
///╔╝╚(¯`v´¯)
///╚══╝`.¸.´farzin


#include <bits/stdc++.h>

#define int int64_t
#define pb push_back
#define ibsws ios_base::sync_with_stdio
#define gcd __gcd
#define s second
#define f first
typedef std::pair<int,int> pii ;

using namespace std;

const int N=1e5+1e2;
int n,dp[N],h[N];

int32_t main(){
	ibsws(true==false);
	cin>>n;
	for(int i=0;i<n;i++){
        cin>>h[i];
	}
	dp[1]=abs(h[0]-h[1]);
	for(int i=2;i<n;i++){
        dp[i]=min(dp[i-1]+abs(h[i-1]-h[i]),dp[i-2]+abs(h[i-2]-h[i]));
	}
	cout<<dp[n-1];
}


Measured memory_bytes: 1792
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    a = input()
    if a.isupper():
        print('A')
        return
    print('a')
    return


if __name__ == '__main__':
    main()

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

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    int abcd[4];
    string s;
    cin >> s;

    for(int i=0; i<4; i++){
        abcd[i] = (int)(s[i] - '0');
    }

    int result[8] = {abcd[0], abcd[0], abcd[0], abcd[0], abcd[0], abcd[0], abcd[0], abcd[0]};
    //cout << result[3] << endl;

    for(int i=0; i<8; i++){
        if(i%2){
            result[i] -= abcd[1];
        }else{
            result[i] += abcd[1];
        }if((i>>1) % 2){
            result[i] -= abcd[2];
        }else{
            result[i] += abcd[2];
        }
        if((i>>2) % 2){
            result[i] -= abcd[3];
        }else{
            result[i] += abcd[3];
        }

    }

    int ans_num;
    for(int i=0; i<8; i++){
        if(result[i] == 7){
            ans_num = i;
            break;
        }
    }

    cout << abcd[0];
    if(ans_num % 2){
        cout << '-';
    }else{
        cout << '+';
    }
    cout << abcd[1];
    if((ans_num >> 1) % 2){
        cout << '-';
    }else{
        cout << '+';
    }
    cout << abcd[2];
    if((ans_num >> 2) % 2){
        cout << '-';
    }else{
        cout << '+';
    }
    cout << abcd[3] << "=7" << '\n';


    return 0;
}

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

ll n, m, p, v;
ll a[MAX], b[MAX];

int main()
{
    cin >> n >> m >> v >> p;
    for(ll i = 1; i <= n; ++i){
        scanf("%lld", &a[i]);
    }
    sort(a+1, a+n+1, greater<ll>());
    for(ll i = 1; i <= n; ++i){
        b[i] = b[i-1]+a[i];
    }
    ll ans = p, s = 0, all = m*(v-1), sum = 0, r = 1;
    for(ll i = 1; i < p; ++i){
        sum = sum+a[i];
    }
    for(ll i = p+1; i <= n; ++i){
        while(a[i]+m < a[r]) sum -= a[r], r++;
        if(r > p) break;
        s = (a[i]+m)*(i-r)-b[i-1]+b[r-1]+(n-i)*m;
        if(s+m*(r-1)+sum-a[i]*(p-r) >= all){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 5120
#include <stdio.h>
#include <string.h>
int main()
{
  char s[102];
  int c=0,i,j;
  while((scanf("%s",s))!=EOF){
    i = 0; j = strlen(s)-1;
    while(i<j){
      if(s[i] != s[j]) break;
      i++;j--;
    }
    if(i>=j) c++;
  }
  printf("%d\n",c);
  return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a , b;
    cin >> a >> b;
    int e[50] = {0};
    for ( int i = 0 ; i < b ; i++ ) {
        int x;
        cin >> x;
        e[x]++;
        cin >> x;
        e[x]++;
    }
    for ( int i = 1 ; i <= a ; i++ ) cout << e[i] << endl;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N],p[N];
bool prime(int x)
{
	if(x==2)return true;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)return false;
	}
	return true;
}
int main()
{
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
int t=2;
p[0]=2,p[1]=3;
	for(int i=2;i<=1e5+1000;i++){
			a[i]=i;
	if(i%2==0||i%3==0)a[i]=0;
	}
	for(int i=2;i<=1e5+1000;i++)
	{
		if(a[i]==0)continue;
		if(prime(i))
		{
			p[t++]=i;
			for(int j=i*2;j<=1e5+1000;j++)
			{
				if(j%a[i]==0)a[j]=0;
			}

		}
	}
	int n;
	cin>>n;
	for(int i=0;i<=t;i++)
	{
		if(p[i]>=n)
		{
			cout<<p[i];
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 4076
#include <bits/stdc++.h>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
#define sz(s) (int)(s.size())
#define vecprint(v) rep(i,0,v.size()-1)cout << v[i] << " ";cout << endl;
#define arrprint(v,n) rep(i,0,n-1)cout << v[i] << " ";cout << endl;
#define matprint(v,n,m) rep(i,0,n-1){rep(j,0,m-1){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;
typedef long long ll;
typedef pair<int,int> P;
template<typename T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; //小さいものから取り出す

struct edge{
    int to;
    int no;
};


int main(){
    int n;
    cin >> n;
    vector<P> to[n];
    // vector<P> e(n-1);
    queue<P> q;
    rep(i,0,n-2){
        int a,b;
        cin >> a >> b;
        a--;b--;
        // e[i] = make_pair(a,b);
        to[a].push_back(make_pair(b,i));
        to[b].push_back(make_pair(a,i));
    }
    int k = 0;
    rep(i,0,n-1){
        k = max(k,sz(to[i]));
    }
    vector<int> ans(n-1,-1);
    q.push(make_pair(0,-1));
    while(!q.empty()){
        P p = q.front();q.pop();
        int c = (p.second + 1) % k;
        for(auto v : to[p.first]){
            if(ans[v.second] != -1)continue;
            ans[v.second] = c;
            q.push(make_pair(v.first, c));
            c = (c+1) % k;
        }
    }

    cout << k << endl;
    rep(i,0,n-2)cout << ans[i]+1 << endl;
//  printf("%.10f\n",ans);

    return 0;
}

Measured memory_bytes: 7040
function main() {
  const n = parseInt(input.shift(), 10);
  const prices = input.map(function(x) {
    return parseInt(x, 10);
  });
  let max = -1000000000;
  let min = prices[0];
  for (let i = 1; i < prices.length; i++) {
    min = Math.min(min, prices[i - 1]);
    max = Math.max(max, prices[i] - min);
  }
  console.log(max);
}

var input = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', function(chunk) {
  input += chunk;
});
process.stdin.on('end', function() {
  input = input.split('\n');
  input.pop();
  main();
});

Measured memory_bytes: 42296
import java.util.Scanner;

public class Main { public static void main(String...args){
        Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int t = 0; int[] A = new int[N];
        for(int i=0;i<N;i++){
            A[i] = sc.nextInt();
            t = t + A[i];
        } int count = 0;
        for(int i=0;i<N;i++){ if (A[i] >= (t * 0.25/ M)) count++;}
        if(count>=M) System.out.println("Yes");
        else System.out.println("No"); }
}

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

using namespace std;

using LL = long long;
using ULL = unsigned long long;
using PII = pair<int, int>;
using PIL = pair<int, LL>;
using PLL = pair<LL, LL>;
// const LL mod = 1e9 + 7;

#define mem(a, b) memset(a, b, sizeof(a))
#define REP(i, a) for (int i = 0; i < a; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define ALL(a) a.begin(), a.end()

inline void quickread() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout << fixed << setprecision(10);
}

inline void print_vector(vector<int> &A){
    for (auto&& x : A){
        cout << x << " ";
    }
    cout << endl;
}

inline void print_array(const int A[], int n) {
    REP(i, n) {
        if (i < n - 1) {
            cout << A[i] << " ";
        } else {
            cout << A[i] << endl;
        }
    }
}

struct uf {
    int count;
    vector<int> id;
    vector<int> size;
    int max_size = 1;

    void init(int n) {
        count = n;
        id.assign(n, 0);
        size.assign(n, 0);

        REP(i, n) {
            id[i] = i;
            size[i] = 1;
        }
    }

    int find(int x) {
        while (x != id[x]) x = id[x];
        return x;
    }

    bool connected(int p, int q) {
        return find(p) == find(q);
    }

    void united(int p, int q) {
        p = find(p);
        q = find(q);

        if (!connected(p, q)) {
            if (size[p] < size[q]) {
                id[p] = q;
                size[q] += size[p];
            } else {
                id[q] = p;
                size[p] += size[q];
            }
        }

        max_size = max(max_size, size[p]);
        max_size = max(max_size, size[q]);
    }
};

inline void solve() {
    int n, m;
    cin >> n >> m;

    uf uf;
    uf.init(n);

    int a, b;

    REP(i, m) {
        cin >> a >> b;
        uf.united(a-1, b-1);
    }

    cout << uf.max_size << endl;
}

int main() {
    // freopen("input.txt", "r", stdin);
    quickread();
    int t = 1;
    // cin >> t;

    for (int _ = 0; _ < t; _++) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 4784
/*
 _ _ _   _    _   _    _   _ _ _   _    _   _ __ _   __       __
|  _ _| | |  | | | |  | | |  _  | | |  | | |  __  | |   \   /   |
| |_ _  | |__| | | |  | | | |_| | | |__| | | |__| | | |\ \_/ /| |
|_ _  | |  __  | | |  | | |  _ <  |  __  | |  __  | | | \   / | |
 _ _| | | |  | | | |__| | | |_| | | |  | | | |  | | | |  \_/  | |  _   _   _
|_ _ _| |_|  |_| |_ __ _| |_ _ _| |_|  |_| |_|  |_| |_|       |_| |_| |_| |_|

*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fi first
#define se second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(a) cout << #a << " = " << a << " ";
#define endl "\n"
const int MOD=1e9 + 7;
const int N=1000100;
template<typename T> istream &operator>>(istream &is, vector<T> &vec){  
                                                        for (auto &v : vec) is >> v; return is; }
#define dbg(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << endl;

void solve(){
    long n;
    cin>>n;
    set<long> s;
    for(int i=0;i<n;i++){
        long x; cin>>x;
        s.insert(x);
    }
    if(s.size()==n){
        cout<<"YES\n";
    } else {
        cout<<"NO\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long int t = 1;
    // cin>>t;
    for (long int tt = 1; tt <= t; tt++) {
        solve();
    }
    return 0;
}


Measured memory_bytes: 13040
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstring>
#include <numeric>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define F0(i,n) for (int i = 0; i < n; i++)
#define F1(i,n) for (int i = 1; i <= n; i++)
#define CL(a,x) memset(x, a, sizeof(x));
#define SZ(x) ((int)x.size())
const double eps = 1e-10;
const double pi = acos(-1.0);
const int inf = 1000000009;
int i, j, k, m, n, l;
int ans;
const int N = 100005;
int a[N];
 
void solve() {
    ll A = 2, B = 2;
    for (int i = n - 1; i >= 0; i--) {
        int x = a[i];
        ll C = A / x * x;
        if (C < A) C += x;
        if (C > B) {
            cout << -1 << endl;
            return;
        }
        ll D = B / x * x;
        if (D < A) {
            F0(i, n) cout << a[i] << " "; cout << endl;
            throw 12;
        }
        A = C;
        B = D + x - 1;
    }
    cout << A << " " << B << endl;
}
 
void test() {
    n = rand()%4+1;
    F0(i, n) a[i] = rand()%10+2;
    solve();
}
 
int main() {
	//while (1) test();
	while (cin >> n) {
	    F0(i, n) scanf("%d", &a[i]);
	    solve();
	}
	
	return 0;
}

Measured memory_bytes: 640
//abc065_d.cpp
//Tue May 12 21:20:38 2020

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define INTINF 2147483647
#define LLINF 9223372036854775807
#define MOD 1000000007

using namespace std;
using ll=long long;
typedef pair<ll,ll> P;

//Union-Find木
int par[100100]; //親
int treerank[100100]; //木の深さ

//n要素で初期化
void init(int n){
	for (int i=0;i<n;i++){
		par[i] = i;
		treerank[i] = 0;
	}
}

//木の根（親）を見つける
int find (int x){
	if (par[x] == x){
		return x;
	} else {
		return par[x] = find(par[x]);
	}
}

//xとyの属する集合の併合
void unite(int x, int y){
	x = find(x);
	y = find(y);
	if (x == y) {
		return;
	} 

	if (treerank[x] < treerank[y]){
		par[x] = y;
	} else {
		par[y] = x;
		if (treerank[x] == treerank[y]){
			treerank[x]++;
		}
	}
}

//xとyが同じグループに属するか判定
bool same(int x, int y){
	return find(x) == find(y);
}


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

	P x[n],y[n];
	for (ll i=0;i<n;i++){
		ll tmp1,tmp2;
		cin >> tmp1 >> tmp2;
		x[i] = P(tmp1,i);
		y[i] = P(tmp2,i);
	}

	sort(x,x+n);
	sort(y,y+n);

	P roadind[2*n-2];
	P cost[2*n-2];
	for (ll i=1;i<n;i++){
		roadind[2*(i-1)] = P(x[i-1].second,x[i].second);
		cost[2*(i-1)] = P(x[i].first-x[i-1].first,2*(i-1));
		roadind[2*(i-1)+1] = P(y[i-1].second,y[i].second);
		cost[2*(i-1)+1] = P(y[i].first-y[i-1].first,2*(i-1)+1);
	}

	sort(cost,cost+2*n-2);

	init(n);
	ll ans = 0;
	for (ll i=0;i<2*n-2;i++){
		ll useind = cost[i].second;
		ll from = roadind[useind].first;
		ll to = roadind[useind].second;
//		cout << from << " " << to << " " << useind << endl;
		if (!same(from,to)){
			ans += cost[i].first;
			unite(from,to);
		}
	}

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

Measured memory_bytes: 10368
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn=10005;

int n,m;
bool vis[maxn];
vector<int>G[maxn];
vector<int>ans;

void dfs(int u) {
    vis[u]=1;
    for (int v:G[u])
        if (!vis[v]) dfs(v);
    ans.pb(u);
}

int main() {
    cin>>n>>m;
    for (int i=0;i<m;i++) {
        int u,v; cin>>u>>v;
        G[u].pb(v);
    }
    for (int i=0;i<n;i++)
        if (!vis[i]) dfs(i);
    for(auto it=ans.rbegin(); it!=ans.rend();it++) cout <<*it << endl;
}


Measured memory_bytes: 3896
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<numeric>
#include<map>
#include<unordered_map>
#include<queue>
#include<deque>
 
using namespace std;
using ll=long long;
#define rep(i,n)  for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()

#define MOD 1000000007

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

    rep(i, s.size()){
        char out = s[i] + n;
        if(out > 'Z')out-=26;
        cout << out;
    }

}

Measured memory_bytes: 256
#include "iostream"
#include "vector"
using namespace std;

int calc( vector<int> v, int temp1 )
{
    // 最小値探し
    for( auto i : v ) 
    {
        if( 0 != i ) temp1 = min( temp1, i );
    }

    int temp2 = temp1;

    // 剰余する
    for( int i=0 ; i < v.size() ; i++ ) 
    {
        if( 0 == v[i] ) continue;

        if( 0 != (v[i] % temp1) )
        {
            temp2 = v[i] % temp1;
        }
    }

    // 更に探し求める
    if( temp1 != temp2 ) return calc( v, temp2 );

    // 終わり
    return temp2;
}

int main()
{
    int N; cin >> N;
    vector<int> v;

    // ロード
    for( int i=0 ; i<N ; i++ )
    {
        int temp; cin >> temp;
        v.push_back( temp );
    }

    // 出力
    cout << calc( v, 1000000000 ) << endl;

    return 0;
}


Measured memory_bytes: 5880
/*input
3 8
3 30
4 50
5 60
*/
/**
    Author: Kristopher Paul
    Date Created: 11-01-2020
    Contest Name:
                _/    _/   _/_/_/_/   _/   _/_/_/_/
               _/  _/     _/    _/   _/   _/
              _/_/       _/_/_/_/   _/   _/_/_/_/
             _/  _/     _/  _/     _/         _/
            _/    _/   _/    _/   _/   _/_/_/_/
**/
#include<bits/stdc++.h>
#include<stdio.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int ll
#define pb push_back
#define INF 1e18
#define MOD 1000000007
//#define MOD 998244353
#define mp make_pair
const double PI=3.141592653589793238462643383279502884197169399375105820974944;
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define umap unordered_map
#define pii pair<int,int>
#define F first
#define S second
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define itr :: iterator it
#define all(v) v.begin(),v.end()
#define WL(t) while(t--)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define out(x) cout << #x << " is " << x << endl
#define FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

//Uncomment for File I/O
/*
#define cin fin
#define cout fout

ifstream fin("input.in");
ofstream fout("input.out");
*/

using namespace std;
//using namespace __gnu_pbds;

//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> pbds; // set
//typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> pbds; // multiset

int ModExp(int x,int y,int m){
    int res = 1;
    x = x % m;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % m;

        y = y>>1;
        x = (x*x) % m;
    }
    return res;
}

void solve(){
    int n,k;
    cin >> n >> k;
    int w[n],v[n];
    int dp[n][k+1];
    FOR(i,0,n){
        cin >> w[i] >> v[i];
        FOR(j,0,k+1){
            dp[i][j] = 0;
        }
    }
    FOR(j,0,k+1){
        if(j >= w[0]){
            dp[0][j] = v[0];
        }
        FOR(i,1,n){
            if(j >= w[i]){
                remax(dp[i][j],dp[i-1][j-w[i]]+v[i]);
            }
            remax(dp[i][j],dp[i-1][j]);
        }
    }
    cout << dp[n-1][k] << endl;
}

signed main(){
    FastIO;
    int t = 1;
//    cin >> t;
    WL(t){
        solve();
    }
}



Measured memory_bytes: 78336
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

int main(){
  int n,i,j,s,m;
  scanf("%d",&n);
  int a[n];
  for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  s=0;
  m=0;
  
  for(i=0;i<n-1;i++){
    if(a[i]==a[i+1]){
      s=s+1;
      a[i+1]=n+1;
    }
  }
    
    printf("%d",s);
}
  

Measured memory_bytes: 128
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_C main
#include "bits/stdc++.h"
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
// functions
bool second_smaller(const pii& left, const pii& right) {
    return left.second < right.second;
}
#endif


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

    int N, K; cin >> N >> K;
    vi x(N); REP(i, N) cin >> x[i];
    vi l, r;

    REP(i,N-K+1) {
        l.push_back(x[i]);
        r.push_back(x[i + K - 1]);
    }

    int ans = INF;
    REP(i,N-K+1) {
        int d = min(abs(l[i]) + abs(r[i] - l[i]), abs(r[i]) + abs(l[i] - r[i]));
        ans = min(ans, d);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1276