akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<string>
using namespace std;


struct Card{char suit, num;};


void bubbleSort(Card A[],int N){
    int flag = 1;
    Card tmp;
    int count=0;
    while (flag){
        flag= 0;
        for ( int j = N-1; j>0; j--){
            if (A[j].num < A[j-1].num){
                tmp = A[j];
                A[j] = A[j-1];
                A[j-1] = tmp;
                flag = 1;
            }
        }
    }
    for (int k=0; k < N-1; k++) cout << A[k].suit << A[k].num <<" ";
    cout << A[N-1].suit << A[N-1].num<< endl;
    cout << "Stable" << endl;
}


void SelectionSort(Card A[],int N){
    int minj;
    int sw = 0;
    for (int i =0; i < N; i++){
        minj = i;
        for (int j = i; j < N; j++){
            if (A[j].num < A[minj].num){
                minj = j;
            }
        }
        if (i !=minj){
            Card t = A[i];
            A[i] = A[minj];
            A[minj] = t;
        }
    }
    for (int i = 0; i < N-1; i++) cout << A[i].suit << A[i].num << " ";
    cout << A[N-1].suit << A[N-1].num << endl;
    ;
}

bool stableCheck(Card A1[], Card A2[], int N){
    for (int i = 0; i < N; i++){
        if(A1[i].suit != A2[i].suit){
            return false;
        }
    }
    return true;
}



int main(){
    int N;
    Card A1[100], A2[100];
    
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A1[i].suit >> A1[i].num;
    for (int i = 0; i < N; i++) A2[i] = A1[i];
    bubbleSort(A1,N);
    SelectionSort(A2,N);
    if (stableCheck(A1,A2,N)){
        cout << "Stable" << endl;
    }
    else{
        cout << "Not stable" << endl;
    }
}


Measured memory_bytes: 3128
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>
using namespace std;
void print(int x)
{
    switch (x) {
        case 0:
            cout << "10";
            break;
        case 1:
            cout << "11";
            break;
        case 2:
            cout << "00";
            break;
        case 3:
            cout << "01";
            break;
        default:
            break;
    }
    return;
}

using namespace std;
int main()
{
    long long n;
    cin >> n;
    string s;
    if (n == 0 | n == 1) {
        cout << n << endl;
        return 0;
    } else if (n > 0) {
        n -= 2;
        int digit;
        digit = static_cast<int>(log(3 * n + 4) / log(4));
        n -= static_cast<int>((pow(4, digit) - 4) / 3);
        cout << "1";
        while (digit != 0) {
            print(n / static_cast<int>(pow(4, digit - 1)));
            n %= static_cast<int>(pow(4, digit - 1));
            digit--;
        }
    } else if (n < 0) {
        n *= -1;
        n -= 3;
        int digit, flag = 0;
        digit = static_cast<int>(log((3 * n + 8) / 2) / log(4));
        if (n % 2 == 0) {
            n++;
            flag++;
        }
        n -= static_cast<int>((2 * pow(4, digit) - 8) / 3);
        cout << "1";
        n /= 2;
        while (digit != 0) {
            print(n / static_cast<int>(pow(4, digit - 1)));
            n %= static_cast<int>(pow(4, digit - 1));
            digit--;
        }
        if (flag == 0) {
            cout << "0";
        } else {
            cout << "1";
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  ll n;
  cin>>n;
  if(n%2==0){
    cout<<n<<endl;
  }else{
    cout<<n*2<<endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N;
	cin >> N;
    int X = 0; 
    int M = 0;
	vector<int>A(N);
	for(int i = 0; i < N; i++) {
	cin>>A[i];
	if (A[i]%2 == 0 && (A[i]%3 == 0 || A[i]%5 == 0)) {
       X++;
    }
    if (A[i]%2 == 0){
       M++;
    }
    }
    if(X == M){
      cout << "APPROVED" <<endl;
    }
    else {
      cout << "DENIED" <<endl;
    }
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include <iostream> 
#include <algorithm> 
#include<string>
#include<queue>
#include<utility>
#include<fstream>
#include<queue>
#include<set>
#include<stack>
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define I(a) scanf("%d",&a)
#define I2(a,b) scanf("%d%d",&a,&b)
#define I3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define L(a) scanf("%lld",&a)
#define L2(a,b) scanf("%lld%lld",&a,&b)
#define L3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define PI(a) printf("%d",a)
#define PL(a) printf("%lld",a)
#define PT(t) printf("Case %d: ",t)
#define PB push_back
#define x first
#define y second
#define xx first.first
#define xy first.second
#define yx second.first
#define yy second.second
#define SC scanf
#define PC printf
#define NL printf("\n")
#define SET(a) memset(a,0,sizeof a)
#define SETR(a) memset(a,-1,sizeof a)
#define SZ(a) ((int)a.size())-1
#define f(i,a,b) for(int i=a;i<=b; i++)
#define fr(i,a,b) for(int i=a;i<=b; i++)
#define frr(i,a,b) for(int i=a;i>=b; i--)
#define frv(i,a)  for(int i=0;i<a.size();i++)
#define pi 2.0*acos(0.0)
#define R(a) freopen(a, "r", stdin);
#define W(a) freopen(a, "w", stdout);
#define CB(x) __builtin_popcount(x)
#define STN(a) stringtonumber<ll>(a)
#define lol printf("BUG\n")
#define Endl "\n"
#define mk make_pair
using namespace std;
template <class T> inline T BM(T p, T e, T M)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p) % M;
        p = (p * p) % M;
    }
    return (T)ret;
}
template <class T> inline T gcd(T a, T b)
{
    if(b == 0)return a;
    return gcd(b, a % b);
}
template <class T> inline T mdINV(T a, T M)
{
    return BM(a, M - 2, M);
}
template <class T> inline T PW(T p, T e)
{
    ll ret = 1;
    for(; e > 0; e >>= 1)
    {
        if(e & 1) ret = (ret * p);
        p = (p * p);
    }
    return (T)ret;
}
 
 
template <class T>bool ISLEFT(T a, T b, T c)
{
    if(((a.xx - b.xx) * (b.yy - c.yy) - (b.xx - c.xx) * (a.yy - b.yy)) < 0.0)return 1;  //Uporer dike //A,b,c, x okkher ordera sorted
    else return 0;
}
 
 
typedef pair<int,int >P;
//////////////////////////
/////////////////////////

#define mx 100000
char ar[mx+2];
int dp1[mx+2][2];
int dp(int i, bool fl ){
    if(i == 0)return 0;
    int &ret = dp1[i][fl];
    if(ret!=-1)return ret;
    ret = mx *10;
    ret = (fl == (ar[i]-'0')?1:0)+ dp(i-1, fl ^1 );
    return ret;
}
int main(){
    scanf("%s", ar+1);
    int l = strlen(ar+1);
SETR(dp1);
cout<<min(dp(l,0),dp(l,1))<<endl;


    return 0;
}

Measured memory_bytes: 4224
from itertools import accumulate


def solve(n, q, s):
    m = [0]*n
    for i in range(1, n):
        if s[i-1:i+1] == 'AC':
            m[i] = 1

    accm = list(accumulate(m))

    for j in range(q):
        l, r = map(int, input().split())
        print(accm[r-1]-accm[l-1])


if __name__ == '__main__':
    n, q = map(int, input().split())
    s = input()
    solve(n, q, s)


Measured memory_bytes: 8736
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
typedef long long ll;
using namespace std;
void solve(){
  ll n, q, k; cin >> n;
  vector<vector<pair<ll, ll> > > v(n + 1);
  vector<ll> dis(n + 1);
  vector<bool> visited(n + 1);
  for(int i = 0; i < n - 1; i++){
    ll a, b, c; cin >> a >> b >> c;
    v[a].push_back(make_pair(b, c));
    v[b].push_back(make_pair(a, c));
  }
  cin >> q >> k;
  vector<ll> x(q), y(q);
  for(int i = 0; i < q; i++){
    cin >> x[i] >> y[i];
  }

  queue<ll> qu;
  qu.push(k);
  visited[k] = true;
  dis[k] = 0;
  while(qu.size() > 0){
    ll c = qu.front();
    qu.pop();
    for(int i = 0; i < v[c].size(); i++){
      ll nx = v[c][i].first;
      if(visited[nx] == false){
        qu.push(nx);
        visited[nx] = true;
        dis[nx] = dis[c] + v[c][i].second;
      }
    }
  }
  for(int i = 0; i < q; i++){
    cout << dis[x[i]] + dis[y[i]] << endl;
  }

  return;
}

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


Measured memory_bytes: 11648
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>

using namespace std;

#define rep(i,n) for(int i = 0;i < n;i++)
#define ull unsigned long long
#define int ull
#define ll int


ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while (n > 0) {
		if (n & 1)res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

const int B = 1e9 + 7;
const int mod = 0xffffffffffffffff;

signed main() {
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	vector<int> hash(n + 1, 0);
	hash[1] = s[0];
	for (int i = 2; i <= s.size(); i++) {
		hash[i] = (hash[i - 1] * B + s[i - 1]) % mod;
	}

	int l = 0, r = 1;
	set<int> se;
	rep(i, m) {
		string t;
		cin >> t;
		if (t == "R++") {
			r++;
		}
		if (t == "L++") {
			l++;
		}
		if (t == "R--") {
			r--;
		}
		if (t == "L--") {
			l--;
		}
		int val = (hash[r] - hash[l] * mod_pow(B, r - l, mod) + mod) % mod;
		se.insert(val);
	}
	cout << se.size() << endl;

	return 0;
}

Measured memory_bytes: 19488
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

int main(void) {
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> C(N);
  vector<vector<int>> P(2e5 + 1);
  rep(i, N) {
    cin >> C[i];
    P[C[i]].emplace_back(i);
  }

  vector<int64_t> DP(2e5 + 1, 0);
  const int64_t mod = 1e9 + 7;
  DP[0] = 1;
  rep(i, N) {
    DP[i + 1] = (DP[i + 1] + DP[i]) % mod;

    auto itr = lower_bound(P[C[i]].begin(), P[C[i]].end(), i);
    if (itr != P[C[i]].end()) {
      int pos = itr - P[C[i]].begin();
      if (pos == 0) continue;
      int j = P[C[i]][pos - 1];
      if (j + 1 < i) {
        DP[i + 1] = (DP[i + 1] + DP[j + 1]) % mod;
      }
    }
  }
  cout << DP[N] << endl;
  return 0;
}


Measured memory_bytes: 16368
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
const int N = 266666;
int n,k,a[N],l[N],r[N];set<int>out;
int q[N],F,R;set<Pii>Set;
void ins(int p){
	while(F!=R&&a[q[R-1]]>a[p])out.insert(q[R-1]),R--;
	q[R++]=p;out.erase(p);
}
void del(int p){
	if(F!=R&&q[F]==p)F++,out.insert(p);
}
void solve(int *l){
	rep(i,1,n)out.insert(i);F=0,R=0;
	rep(i,1,k-1)ins(i);
	rep(i,1,n-k+1){//[i,i+k-1]
		ins(i+k-1);
		set<int>::iterator it=out.lower_bound(i);
		if(it==out.end()||(*it)>i+k-1)l[i]=i+k;else l[i]=*it;
		del(i);
	}
}
int main() {
	read(n);read(k);
	rep(i,1,n)read(a[i]),a[i]++;
	solve(l);
	rep(i,1,n)a[i]=n-a[i]+1;reverse(a+1,a+n+1);solve(r);
	rep(i,1,n-k+1){
		int L=l[i],R=n-r[n-k+2-i]+1;
		if(L>R)Set.insert(Pii(1,0));
		else Set.insert(Pii(L,R));
	}
	cout<<SZ(Set);
//	rep(i,1,n)out.insert(i);F=0,R=0;
//	per()ins(i);
	return 0;
}


Measured memory_bytes: 21888
a= input()

N=int(a[0])

#d=[int(input()) for _ in range(N)]
d=str(input())

check=d[0]
res=[]
res.append(d[0])

for i in range(len(d)):
  if check != d[i]:
    res.append(d[i])
    check=d[i]
    
print(len(res))

Measured memory_bytes: 3956
import java.util.*;

public class Main {
	
	public static String[] kommaReader(String sc) {
		String line = sc;
		String[] array = line.split(",");
		return array;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		float count=0;
		long sum=0;
		long sumC=0;
		do{
			String t = sc.nextLine();
			if(t.equals("")) break;
			String[] temp = kommaReader(t);
			sum += Long.parseLong(temp[0])*Long.parseLong(temp[1]);
			sumC += Long.parseLong(temp[1]);
			count++;
		} while(sc.hasNextLine());
		System.out.println(sum);
		System.out.printf("%.0f%n",sumC/count);
	}

}

Measured memory_bytes: 12000
#include <bits/stdc++.h>
using namespace std;
 
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ld;
 
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 3;
 
#define _  %  MOD
#define __ %= MOD
 
#define      each(it,s)        for(auto it = s.begin(); it != s.end(); ++it)
#define      sortA(v)          sort(v.begin(), v.end())
#define      sortD(v)          sort(v.begin(), v.end(), greater<auto>())
#define      fill(a)           memset(a, 0, sizeof (a))
 
#define      swap(a,b)        {a=a+b;b=a-b;a=a-b;}
#define      rep(i, n)         for(ll i = 0; i < (n); ++i)
#define      repA(i, a, n)     for(ll i = a; i <= (n); ++i)
#define      repD(i, a, n)     for(ll i = a; i >= (n); --i)
#define watch(x) cout << (#x) << " is " << (x) <<endl
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
#define fbo find_by_order
#define ook order_of_key
 
ll gcd(ll a,ll b){if(b==0) return a; else return gcd(b,a%b);}
ll power(ll x,ll y){ll res=1; while(y>0){if(y&1) res=res*x;y=y>>1;x=x*x;}return res;} // modular exponent
 
int main()
{
    ios_base::sync_with_stdio(false); // don't use printf and scanf
    cin.tie(NULL); // cout<<fixed<<setprecision
   	ll d,t,s;
   cin>>d>>t>>s;
	if(d<=s*t) cout<<"Yes\n";
 	else cout<<"No\n";
	return 0;	
}
// JUST ASK YOURSELF DID YOU GIVE YOUR BEST ? ISSE ZYADA
// KUCH KAR BHI NAHI SAKTE !! ENJOY AND GIVE YOUR BEST!!



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

typedef long long ll;

#define pb push_back
#define rep(i, a, n) for(int i = (a); i < (n); i++)
#define dep(i, a, n) for(int i = (a); i >= (n); i--)
#define mod 1e9+7

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int n, t, maxs = 0, maxc = 0;
  cin >> n >> t;
  int a[n], b[n] = {};
  rep(i, 0, n) cin >> a[i];
  dep(i, n - 1, 0) {
    maxs = max(maxs, a[i]);
    b[i] = maxs;
  }
  maxs = 0;
  rep(i, 0, n) {
    if(b[i] - a[i] == maxs) maxc++;
    if(b[i] - a[i] > maxs) {
      maxs = b[i] - a[i];
      maxc = 1;
    }
  }

  cout << maxc << endl;
}


Measured memory_bytes: 1024
//
//  main.cpp
//  Cwork
//
//  Created by admin on 2015/05/22.
//  Copyright (c) 2015??´ admin. All rights reserved.
//

#include <iostream>
using namespace std;

void append(char fruit[100][100], int (&map)[100][100], int count, int i, int j, int h, int w){
    if(j != w -1){
        if(map[i][j+1] == 0 && fruit[i][j+1] == fruit[i][j]){
            map[i][j+1] = count;
            append(fruit, map, count, i, j+1, h, w);
        }
    }
    
    if(i != h - 1){
        if(map[i+1][j] == 0 && fruit[i+1][j] == fruit[i][j]){
            map[i+1][j] = count;
            append(fruit, map, count, i+1, j, h, w);
        }
    }
    
    if(j != 0){
        if(map[i][j-1] == 0 && fruit[i][j-1] == fruit[i][j]){
            map[i][j-1] = count;
            append(fruit, map, count, i, j-1, h, w);
        }
    }
    
    if(i != 0){
        if(map[i-1][j] == 0 && fruit[i-1][j] == fruit[i][j]){
            map[i-1][j] = count;
            append(fruit, map, count, i-1, j, h, w);
        }
    }

}


int main(int argc, const char * argv[]) {
    
    while(true){
        int H,W;
        cin >> H >> W;
        if(H == 0 && W == 0){
            break;
        }
        
        
        int count = 0;
        int map[100][100] = {};
        char fruits[100][100] = {};
        
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                cin >> fruits[i][j];
            }
        }
        
        
        for(int i=0;i<H;i++){
            for(int j=0;j<W;j++){
                if(map[i][j] != 0){
                    continue;
                }else{
                    count++;
                    map[i][j] = count;
                    append(fruits, map, count, i, j, H, W);
                }
                
            }
        }
        
        cout << count << endl;
    }
        return 0;
}

Measured memory_bytes: 2608
package main

import "fmt"

func main() {
	var x int
	fmt.Scan(&x)
	for a := -200; a <= 200; a++ {
		for b := -200; b <= 200; b++ {
			if a*a*a*a*a-b*b*b*b*b == x {
				fmt.Printf("%d %d\n", a, b)
				return
			}
		}
	}
}


Measured memory_bytes: 1816
#include<bits/stdc++.h>
using namespace std;
int n,a,b,dp[200][100][100];
int f(int x,int y,int z){
    if(x>=2*n)return 1;
    if(dp[x][y][z]!=-1)return dp[x][y][z];
    int ret=0;
    if(x%2==0){
        if(y-1>=0){
            ret=max(ret,2-f(x+1,y-1,z));
        }
        if(y+1<n&&y+1!=z){
            ret=max(ret,2-f(x+1,y+1,z));
        }
    }
    else{
        if(z-1>=0&&z-1!=y){
            ret=max(ret,2-f(x+1,y,z-1));
        }
        if(z+1<n){
            ret=max(ret,2-f(x+1,y,z+1));
        }
    }
    return dp[x][y][z]=ret;
}
int main(){
    scanf("%d %d %d",&n,&a,&b);
    memset((dp),-1,sizeof(dp));
    int res=f(0,a-1,b-1);
    if(res==0)puts("Borys");
    else if(res==1)puts("Draw");
    else puts("Alice");
    return 0;
}

Measured memory_bytes: 8064
import scala.collection.mutable
 
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N = sc.nextInt()
  val hashMap = mutable.Map[Int, Int]()
  for (_ <- 2 to N) {
    val a = sc.nextInt()
    val count = hashMap.getOrElse(a, 0)
    hashMap.update(a, count + 1)
  }
  1.to(N).foreach(i => println(hashMap.getOrElse(i, 0)))
}

Measured memory_bytes: 79068
n=int(input())
a=[int(i) for i in input().split()]

a.sort()

ans1=max(a)
ans2=0
b=0
c=0
lb=[]
lc=[]

if ans1%2==0:
    b=ans1/2
    c=ans1/2
else:
    b=(ans1+1)/2
    c=b-1

for i in a:
    if abs(i-b)<abs(ans2-b):
        ans2=i
    if abs(i-c)<abs(ans2-c):
        ans2=i

print(str(ans1)+" "+str(ans2))



Measured memory_bytes: 14052
#include <stdio.h>
int main(void){
    int x, a, b;
    
    scanf("%d %d %d",&x, &a, &b);
    
    if(a>=b){
        printf("delicious\n");
    }else if(a<b && b-a>x){
        printf("dangerous\n");
    }else{
        printf("safe\n");
    }
 
 
    return 0;   
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <limits>
#include <vector>
#include <map>
#include <cmath>
#include <limits>
#include <iomanip>
#include <queue>
#include <string.h>
#include <bitset>

#define ll long long int
#define ld long double
#define rep(i,n) for(int i = 0;i < n;i++)
#define rep1(i,n) for(int i = 1;i < n;i++)
#define co(x) cout << x << endl
#define cosp(x) cout << x << " "
#define all(x) x.begin(),x.end()
#define allr(x) x.begin(),x.end(),greater<int>()
#define P pair<ll,ll>
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1ll << 60
#define PI 3.14159265359

using namespace std;

int main(){
	
  int n;
  cin >> n;
  vector<pair<int,int> > vec(n);
  int tmp;
  rep(i,n){
    cin >> tmp;
    vec[i] = mp(tmp,i);
  }
  sort(vec.begin(),vec.end());

  rep(i,n){
    cout << vec[i].second+1 << " ";
  }
  cout << endl;

	return 0;
}


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

using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
	REP(i, v.size()) { if (i)os << " "; os << v[i]; }return os;
}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
	REP(i, v.size()) { if (i)os << endl; os << v[i]; }return os;
}

const ll INF = 1LL << 60;
ll MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;

#define int long long

inline void my_io() {

	std::ios::sync_with_stdio(false);

	std::cin.tie(0);

	cout << fixed << setprecision(10);

}

signed main() {
	ll n, k;
	ll ans = INF;

	cin >> n >> k;

	vector<ll> v(n, 0);

	REP(i, n) {
		cin >> v[i];
	}

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

	REP(i, n - k + 1) {
		ans = min(ans, v[i + k - 1] - v[i]);
	}

	cout << ans << endl;
}

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

using namespace std;

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

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

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

	int a, b;cin >> a >> b;
	string aa = "";REP(i, b)aa += (char)('0' + a);
	string bb = "";REP(i, a)bb += (char)('0' + b);

	if(aa < bb)cout << aa << endl;
	else cout << bb << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;
using P=pair<ll,ll>;
#define MOD 1000000007ll
#define INF 1000000000ll
#define EPS 1e-10
#define FOR(i,n,m) for(ll i=n;i<(ll)m;i++)
#define REP(i,n) FOR(i,0,n)
#define DUMP(a) REP(d,a.size()){cout<<a[d];if(d!=a.size()-1)cout<<" ";else cout<<endl;}
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) sort(ALL(v));v.erase(unique(ALL(v)),v.end());
#define pb push_back

ll n,m;
vector<vector<P>> g;

ll dfs(ll idx,vector<ll> &used) {
	if(idx==n) {
		ll ret=0;
		REP(i,n) ret+=used[i];
		if(ret==INF) return 0;
		else return ret;
	}
	if(used[idx]==0) return dfs(idx+1,used);
	vector<ll> tmp(n); REP(i,n) tmp[i]=used[i];
	used[idx]=0;
	ll ret=dfs(idx+1,used);
	used[idx]=INF;
	FOR(i,idx+1,n) used[i]=0;
	REP(i,g[idx].size()) {
		if(g[idx][i].first>idx) {
			used[g[idx][i].first]=-1;
			continue;
		}
		if(used[g[idx][i].first]==0) continue;
		used[idx]=min(used[idx],g[idx][i].second);
		used[g[idx][i].first]=min(used[g[idx][i].first],g[idx][i].second);
	}
	REP(i,n) if(tmp[i]==0) used[i]=0;
	ret=max(ret,dfs(idx+1,used));
	REP(i,n) used[i]=tmp[i];
	return ret;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin>>n>>m;
	g.assign(n,vector<P>(0));
	REP(i,m) {
		ll u,v,f;
		cin>>u>>v>>f;
		u--;
		v--;
		g[u].pb(P(v,f));
		g[v].pb(P(u,f));
	}
	REP(i,n) sort(ALL(g[i]));
	vector<ll> used(n,-1);
	cout<<dfs(0,used)<<endl;
	return 0;
}



Measured memory_bytes: 3320
package main

import (
	"fmt"
	"math"
)

func max(nums ...int) int {
	if len(nums) == 0 {
		panic("funciton max() requires at least one argument.")
	}
	res := nums[0]
	for i := 0; i < len(nums); i++ {
		res = int(math.Max(float64(res), float64(nums[i])))
	}
	return res
}

func main() {
	var n, W int
	fmt.Scan(&n, &W)
	w := make([]int, n)
	v := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&w[i], &v[i])
	}
	dp := make([][]int, n+1)
	dp[0] = make([]int, W+1)

	// solve
	for i := 0; i < n; i++ {
		dp[i+1] = make([]int, W+1)

		for j := 1; j <= W; j++ {
			if j-w[i] >= 0 {
				dp[i+1][j] = max(dp[i+1][j], dp[i][j-w[i]]+v[i])
			}
			dp[i+1][j] = max(dp[i+1][j], dp[i][j])
		}
	}
	fmt.Println(dp[n][W])
}


Measured memory_bytes: 81408
#pragma region header
#include <bits/stdc++.h>
using namespace std;

#define CPP_CAT(x,y) CPP_CAT_I(x,y)
#define CPP_CAT_I(x,y) x ## y
//#define CPP_STR(x) CPP_STR_I(x)
//#define CPP_STR_I(args...) #args
//#define ASSERT(expr...) assert((expr))

using i8 = int8_t;
using u8 = uint8_t;
using i16 = int16_t;
using u16 = uint16_t;
using i32 = int32_t;
using u32 = uint32_t;
using i64 = int64_t;
using u64 = uint64_t;
using f32 = float;
using f64 = double;
//using f80 = __float80;

constexpr i64 INF = 1'010'000'000'000'000'017LL;
constexpr i64 MOD = 1'000'000'007LL;
constexpr f64 EPS = 1e-12;
constexpr f64 PI = 3.14159265358979323846;
constexpr char EL[] = "\n";

#define FOR(i, start, end) for(i64 i = (start), CPP_CAT(i,xxxx_end)=(end); i < CPP_CAT(i,xxxx_end); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(f,c,...) (([&](decltype((c)) cccc) { return (f)(std::begin(cccc), std::end(cccc), ## __VA_ARGS__); })(c))
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());

template<typename T = i64>
T IN() { T x; cin >> x; return (x); }

template<typename C>
i64 SIZE(const C& c) { return static_cast<i64>(c.size()); }
template<typename T, size_t N>
i64 SIZE(const T(&)[N]) { return static_cast<i64>(N); }

template<typename T, typename U, typename Comp = less<>>
bool chmax(T& xmax, const U& x, Comp comp = {}) {
	if (comp(xmax, x)) {
		xmax = x;
		return true;
	}
	return false;
}
template<typename T, typename U, typename Comp = less<>>
bool chmin(T& xmin, const U& x, Comp comp = {}) {
	if (comp(x, xmin)) {
		xmin = x;
		return true;
	}
	return false;
}

void print() {
	cout << EL;
}
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
	cout << head;
	if (sizeof...(tail) != 0) cout << " ";
	print(forward<Tail>(tail)...);
}
template <class T>
void print(vector<T> &vec) {
	for (auto& a : vec) {
		cout << a;
		if (&a != &vec.back()) cout << " ";
	}
	cout << EL;
}
template <class T>
void print(vector<vector<T>> &df) {
	for (auto& vec : df) {
		print(vec);
	}
}

struct ProconInit {
	static constexpr int IOS_PREC = 15;
	static constexpr bool AUTOFLUSH = false;

	ProconInit() {
		cin.tie(nullptr);
		ios::sync_with_stdio(false);
		cout << fixed << setprecision(IOS_PREC);
		if (AUTOFLUSH)
			cout << unitbuf;
	}
} PROCON_INIT;
#pragma endregion

signed solve()
{
	auto c1 = IN<string>();
	auto c2 = IN<string>();
	auto c3 = IN<string>();
	print(c1.substr(0,1) + c2.substr(1, 1) + c3.substr(2, 1));
	return 0;
}

#ifndef LOCALCODE
signed main()
{
	return solve();
}
#endif


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

using namespace std;

typedef long long LL;

const int N = 100003;

int n, m, a[N];
char s[N];

int main()
{
    cin>> n;
    if (n & 1) cout << n / 2 + 1 << endl;
    else cout << n / 2 << endl;
    return 0;
}

Measured memory_bytes: 256
import math

a, b, x = map(int, input().split())
c = x/a
if c > a*b/2:
  c = a*b - c
  d = c*2 / a
  e = math.atan(d/a)
else:
  d = c*2 / b
  e = math.atan(b/d)
print(math.degrees(e))

Measured memory_bytes: 3060
from collections import Counter
n = int(input())
s = str(input())

ans = 0
for i in range(1,n):
    tmp1 = Counter(s[:i]).keys()
    tmp2 = Counter(s[i:]).keys()

    same = set(tmp1) & set(tmp2)

    if len(same) > ans:
        ans = len(same)

print(ans)


Measured memory_bytes: 3316
//AUTHOR:BlackBox Inc.//
#include<bits/stdc++.h>
#include<unordered_map>
#include<tr1/unordered_map>
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vlli vector<long long int>
#define vvi vector<vector<int>>
#define endl "\n"
#define vpii vector<pair<int,int>>
#define vs vector<string>
#define lin1(x) ll int x; x = scan();
#define lin2(x,y) ll int x, y; x = scan(), y = scan();
#define lin3(x,y,z) ll int x, y, z; x = scan(), y = scan(), z = scan();
#define pb(x) push_back(x)
#define makep(x,y) make_pair(x,y)
#define mx(a,b) (a)>(b)?(a):(b)
#define mn(a,b) (a)<(b)?(a):(b)
#define fori(s,e) for(i=s;i<=e;i++)
#define forj(s,e) for(j=s;j<=e;j++)
#define fork(s,e) for(k=s;k<=e;k++)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define brep(i,s,e) for(int i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x));
#define bits1(x) __builtin_popcount(x)
#define pi 3.14159265358979323846264338327950
#define MOD7 1000000007
#define MOD9 1000000009
#define cn cin>>
#define co cout<<
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using namespace std::tr1;

int main()
{


long long a,b,c,d,e,f,g,h;


cin>>a>>b;

if (a+b>=24)
{
	/* code */
	cout<<(a+b)-24;
}
else
cout<<a+b<<endl;

return 0;
}

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define ll long long
using namespace std;
vector<int> a,b, c;
int main()
{
    int x, y, z;
    int k;
    cin >> x >> y >> z;
    cin >> k;
    vector<ll> a(x), b(y), c(z);
    rep(i, x) cin >> a[i];
    rep(i, y) cin >> b[i];
    rep(i, z) cin >> c[i];
    vector<ll> ab;
    rep(i, x){
        rep(j,y){
            ab.push_back(a[i] + b[j]);
        }
    }
    sort(ab.begin(),ab.end());
    reverse(ab.begin(),ab.end());
    vector<ll> abc;
    rep(i,min(k,(int)ab.size())){
        rep(j,z){
            abc.push_back(ab[i] + c[j]);
        }
    }
    sort(abc.begin(), abc.end());
    reverse(abc.begin(), abc.end());
    rep(i,k){
        cout << abc[i] << endl;
    }

}

Measured memory_bytes: 43240
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long lint;

int idx;
int prime[5761455];
bool sieve[10002];
bool sieveBig[1000002];

void segmentSieve(lint a, lint b)
{
	memset(sieveBig, 0, sizeof(sieveBig));
	if (a == 1) sieveBig[0] = true;
	for (int i = 2; (lint)i * i < b; i++){
		if (sieve[i]){
			for (int j = max(2ll, (a + i - 1) / i) * i; (lint)j < b; j += i) sieveBig[j - a] = true;
		}
	}
	
	for (int i = 0; i < b - a; i++){
		if (!sieveBig[i]){
			prime[idx++] = (lint)i + a;
		}
	}
}

int main()
{
	for (int i = 3; i <= 10000; i += 2) sieve[i] = true;
	sieve[2] = true;
	
	for (int i = 3; i <= 10000; i += 2){
		if (sieve[i]){
			for (int j = i * 3; j <= 10000; j += 2 * i) sieve[j] = false;
		}
	}
	
	for (int i = 0; i < 100; i++) segmentSieve(1000000 * i + 1, 1000000 * (i + 1) + 1);
	
	
	//int N;
	//scanf("%d", &N);
	
	//for (int i = 0; i < N; i++){
		int a, b;
		while (scanf("%d", &b) == 1){
		    int *low = upper_bound(prime, prime + 5761455, 0) - 1, *up = upper_bound(prime, prime + 5761455, b) - 1;
		    printf("%d\n", up - low);
                }
	//}
	
	
	return (0);
}

Measured memory_bytes: 24520
#include <iostream>
#include <string>
#include <stack>
#include <cctype>
#include <algorithm>
#include <vector>
using namespace std;
const double PI = 3.14159265358979323846;




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

	if (s == "ABC") {
		cout << "ARC" << endl;
	}
	else {
		cout << "ABC" << endl;
	}*/

	int N, K;
	cin >> N >> K;
	vector<bool> snukes = vector<bool>(N, false);
	for (int i = 0; i < K; i++) {
		int d;
		cin >> d;

		for (int j = 0; j < d; j++) {
			int A;
			cin >> A;
			snukes[A - 1] = true;
		}
	}

	int length = snukes.size();
	int count = 0;
	for (int i = 0; i < length; i++) {
		if (!snukes[i]) {
			count++;
		}
	}

	cout << count << endl;
	return 0;
}

Measured memory_bytes: 3628
def sieve(n):
	p=[True for i in range(n+1)]
	p[0]=p[1]=False
	for i in range(2,n+1):
		if p[i]==True:
			for j in range(i*i,n+1,i):
				p[j]=False
	return p

def solve(n):
		if n<2:return 0
		c=1
		for i in range(3,n+1,2):
			if p[i]==1:
				c+=1
		return c

p=sieve(1000000)
while True:
	try:
		n = int(input())
		print(solve(n))
	except EOFError:
		break

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

#include <algorithm>
using namespace std;
struct Fast {
    Fast() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} fast;

long long mod = 1000000007;

long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return (t * t) % mod;
    } else {
        return (modpow(m, n - 1) * m) % mod;
    }
}
int power(long long x, long long y, long long p) {
    long long res = 1;  // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0) {
        // If y is odd, multiply x with result
        if (y & 1) res = (res * x) % p;

        // y must be even now
        y = y >> 1;  // y = y/2
        x = (x * x) % p;
    }
    return res;
}

long long modInverse(long long n, long long p) { return power(n, p - 2, p); }

long long nCrModPFermat(long long n, long long r, long long p) {
    if (r == 0) return 1;
    long long fac[n + 1];
    fac[0] = 1;
    for (long long i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % p;

    return (fac[n] * modInverse(fac[r], p) % p * modInverse(fac[n - r], p) % p) % p;
}

void yes() {
    cout << "Yes" << endl;
    exit(0);
}
void no() {
    cout << "No" << endl;
    exit(0);
}
#define REP(i, n) for (long long i = 0; i < (n); i++)

signed main() {
    long long n, k, ans = 0;
    cin >> n >> k;
    cout << nCrModPFermat(n + k - 1, k - 1, mod) << endl;
}


Measured memory_bytes: 3204
#include <stdio.h>
int main(){
  int n, count, ac=0, wa=0, tle=0, re=0;
  char s[100];
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%s", &s);
    if (strcmp(s, "AC")==0) ac+=1;
    if (strcmp(s, "WA")==0) wa+=1;
    if (strcmp(s, "TLE")==0) tle+=1;
    if (strcmp(s, "RE")==0) re+=1;
  }
  printf("AC x %d\n", ac);
  printf("WA x %d\n", wa);
  printf("TLE x %d\n", tle);
  printf("RE x %d\n",re);
  return 0;
}

Measured memory_bytes: 1700
//Only the Creator has given me strength!

#include<cstdio>

#include<sstream>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<algorithm>

#include<set>

#include<queue>

#include<stack>

#include<list>

#include<iostream>

#include<fstream>

#include<numeric>

#include<string>

#include<vector>

#include<cstring>

#include<map>

#include<iterator>

#include<bitset>

typedef long long ll;

#define pi 3.1415926535897931159979635

#define pb push_back

#define vctr vector < int >

#define vvtr vector < vctr >

using namespace std;

ll mod=1e7+7;

void fastio() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

}

int main() {

    fastio();

    int n,a,b,cnt=0,an=0;

    cin>>n;

    while(n--) {

        cin>>a>>b;

        if(a==b) cnt++;

        else cnt=0;

        if(cnt==3) an=1;

    }

    if(an==1) cout<<"Yes\n";

    else cout<<"No\n";

    return 0;

}

Measured memory_bytes: 3040
from itertools import accumulate
n = int(input())
l = list(map(int,input().split()))
l1 = [] #odd *-1
l2 = [] #even *-1
ans = []
for i in range(n):
    if i%2:l1.append(-1*l[i])
    else:l1.append(l[i])
for j in range(n):
    if j%2:l2.append(l[j])
    else:l2.append(-1*l[j])

a = [0]+list(accumulate(l2[::-1]))
b = [0]+list(accumulate(l1))
c = [0]+list(accumulate(l1[::-1]))
d = [0]+list(accumulate(l2))
for k in range(n):
    if k%2:
        ans.append(a[~k]+b[k])
    else:
        ans.append(c[~k]+d[k])

print(' '.join(map(str,ans)))



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

const ll mod = 1e9 + 7;

int main()
{
	ios_base::sync_with_stdio(false);

	int n;
	string s;
	cin >> n >> s;
	vector<vector<ll>> dp(n, vector<ll> (n, 0));
	for (int i = 0; i < n; i++)
		dp[0][i] = 1;
	for (int i = 1; i < n; i++)
	{
		vector<ll> pref(n + 1, 0);
		pref[1] = dp[i - 1][0];
		for (int j = 1; j < n; j++)
			pref[j + 1] = (pref[j] + dp[i - 1][j]) % mod;
		for (int j = 0; j < n; j++)
		{
			if (s[i - 1] == '<')
			{
				dp[i][j] = pref[j + 1] % mod;
			}
			else
			{
				dp[i][j] = (pref[n - i + 1] - pref[j + 1] + mod) % mod;
			}
		}
	}
	cout << dp[n - 1][0];

	return 0;
}

Measured memory_bytes: 73724
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T>
T pow_ (T x, T n, T M){
    uint64_t u = 1, xx = x;
    while (n > 0){
        if (n&1) u = u * xx % M;
        xx = xx * xx % M;
        n >>= 1;
    }
    return static_cast<T>(u);
};

template <class T> class Factorial {
    T mod;
    vector<uint64_t> facts, factinv;

public:
    Factorial(int n, T mod) : facts(static_cast<u32>(n+1)), factinv(static_cast<u32>(n+1)), mod(mod) {
        facts[0] = 1;
        for (int i = 1; i < n+1; ++i) facts[i] = facts[i-1]*i % mod;
        factinv[n] = pow_(facts[n], static_cast<uint64_t>(mod - 2), static_cast<uint64_t>(mod));
        for (int i = n-1; i >= 0; --i) factinv[i] = factinv[i+1] * (i+1) % mod;
    }

    T fact(int k) const {
        if(k >= 0) return static_cast<T>(facts[k]);
        else return static_cast<T>(factinv[-k]);
    }

    T operator[](const int &k) const {
        if(k >= 0) return static_cast<T>(facts[k]);
        else return static_cast<T>(factinv[-k]);
    }

    T C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return static_cast<T>(facts[p]*  factinv[q] % mod * factinv[p-q] % mod);
    }

    T P(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return static_cast<T>((facts[p] * factinv[p-q]) % mod);
    }

    T H(int p, int q) const {
        if(p < 0 || q < 0) return 0;
        return static_cast<T>(q == 0 ? 1 : C(p+q-1, q));
    }
};

int main() {
    int p;
    cin >> p;
    Factorial<int> f(p-1, p);
    vector<int> v(p), ans(p);
    for (auto &&i : v) scanf("%d", &i);
    for (int i = 0; i < p; ++i) {
        if(!v[i]) continue;
        (ans[0] += 1) %= p;
        int k = 1;
        for (int j = 0; j < p; ++j) {
            int x = f.C(p-1, j)*k%p;
            if(j%2) (ans[p-1-j] += x) %= p;
            else (ans[p-1-j] += p-x) %= p;
            (k *= i) %= p;
        }

    }
    for (int j = 0; j < p; ++j) {
        if(j) cout << " ";
        cout << ans[j];
    }
    puts("");

    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(){
  int N,H,L=0,Old_H,T=0;
  scanf("%d",&N);
  scanf("%d",&Old_H);
  for(int i=2;i<=N;i++){
    scanf("%d",&H);
    if(Old_H>=H){
      T++;
      if(L<T) L=T;
    }else{
      T=0;
    }
    Old_H=H;
  }
  printf("%d\n",L);
  return 0;
}

Measured memory_bytes: 1708
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <vector>

int main(void)
{
    int N, H;
    std::cin >> N >> H;
    typedef std::pair<int, int> sword;
    std::vector<sword> a(N);
    for(int i=0; i<N; ++i)
    {
        std::cin >> a[i].first >> a[i].second;
    }
    std::sort(a.begin(), a.end(), [](sword &a, sword &b){return b.second < a.second;});
    auto s_max = max_element(a.begin(), a.end(), [](sword &a, sword &b){return a.first < b.first;})->first;
    int count = 0;
    for(auto &v : a)
    {
        if(v.second < s_max)
            break;
        H -= v.second;
        ++count;
        if(H <= 0)
            break;
    }
    if(H > 0)
    {
        count += (H + s_max - 1)/s_max;
    }
    std::cout << count << std::endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;

class UnionFind{
public:
    vector<int> par;
    vector<int> siz;
    UnionFind(int sz_): par(sz_), siz(sz_, 1){
        for(int i = 0;i < sz_;i++)par[i] = i;
    }
    void init(int sz_){
        par.resize(sz_);
        siz.assign(sz_,1);
        for(int i = 0;i < sz_;i++)par[i] = i;
    }
    int root(int x){
        while(par[x] != x){
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(int x,int y){
        x = root(x);
        y = root(y);
        if(x == y)return false;
        if(siz[x] < siz[y])swap(x,y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
    bool issame(int x,int y){
        return root(x) == root(y);
    }
    int size(int x){
        return siz[root(x)];
    }
};

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

    vector<pair<int,int>> vx(n);
    vector<pair<int,int>> vy(n);

    for(int i = 0;i < n;i++){
        int x,y;
        cin >> x >> y;
        vx[i] = make_pair(x,i);
        vy[i] = make_pair(y,i);
    }

    sort(vx.begin(),vx.end());
    sort(vy.begin(),vy.end());

    priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> que;
    for(int i = 0;i < n-1;i++){
        int d = vx[i+1].first - vx[i].first;
        que.push(make_tuple(d,vx[i].second,vx[i+1].second));
    }
    
    for(int i = 0;i < n-1;i++){
        int d = vy[i+1].first - vy[i].first;
        que.push(make_tuple(d,vy[i].second,vy[i+1].second));
    }


    ll ans = 0;
    UnionFind uf(n);
    while(que.size()){
        int d,s,t;
        tie(d,s,t) = que.top();
        que.pop();

        if(uf.issame(s,t))continue;
        uf.merge(s,t);
        ans += d;
    }

    cout << ans << endl;
}


Measured memory_bytes: 8000
N, K = gets.split(' ').map(&:to_i)
A = gets.split(' ').map(&:to_i)

k = A.push(K).max.to_s(2).length
dgt = []
k.times do |i|
  cnt = 0
  N.times do |j|
 	 cnt += 1 if ((1 << i) & A[j]) != 0
  end
  dgt.push(cnt)
end
dgt.concat([0, 0])

cand = []
k.times do |n|
  next if ((K & (1 << n)) == 0) && n >= 1
  x = 0
  (n + 1).upto(k) do |m|
    if (K & (1 << m)) == 0
      x += 2 ** m * dgt[m]
    else
      x += 2 ** m * (N - dgt[m])
    end
  end
  x += 2 ** n * dgt[n]
  if n >= 0
    0.upto(n - 1) do |m|
      x += 2 ** m * [dgt[m], N - dgt[m]].max
 	end
  end
  cand.push(x)
end
y = 0
0.upto(k) do |m|
  if K & (1 << m) == 0
    y += 2 ** m * dgt[m]
  else
	y += 2 ** m * (N - dgt[m])
  end
end
cand.push(y)

puts cand.max

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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
using ll = long long;
string char_to_string(char val) {
  return string(1, val);
}
int char_to_int(char val) {
  return val - '0';
}
template<class T> inline bool chmin(T& a, T b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
template<class T> inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int vector_finder(std::vector<ll> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

int main() {
  int N; cin >> N;
  vector<ll> a(N); REP(i, N) cin >> a[i];
  map<ll, ll> m;
  REP(i, N) {
    m[a[i]]++;
  }
  ll ans = 0;
  for(auto x : m) {
    if(x.first != x.second) {
      if(x.first > x.second) ans += x.second;
      else ans = ans + abs(x.second - x.first);
    }
  }
  cout << ans << endl;
}

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

int main() {
  int A, B, C, K;
  cin >> A >> B >> C >> K;
  if (A>=K)
    cout << K << endl;
  else if (A+B >= K)
    cout << A << endl;
  else
    cout << 2*A + B - K << endl;
}


Measured memory_bytes: 3624
#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <string>
#include <cmath>

#define rep(i, x, n) for (int i = x; i < n; i++)
using namespace std;
const long long INF = 1LL << 60;

int main()
{
    int l;
    string S;
    cin >> l >> S;
    int tl = l / 2;
    string t1 = S.substr(0, tl);
    string t2 = S.substr(tl);
    // cout << t1 << endl;
    // cout << t2 << endl;
    if (t1 == t2)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <stdio.h>
int main(){
	int a[10];
	int i,I;
	int tmp;
	for(i=0;i<10;i++)
	{
		scanf("%d", &a[i]);
	}
	for(i=0;i<10;i++)
	{
		for(I=0;I<10;I++)
		{
			if(a[i]>a[I])
			{
				tmp=a[i];
				a[i]=a[I];
				a[I]=tmp;
			}
		}
	}
	for(i=0;i<3;i++)
	{
		printf("%d\n", a[i]);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
//#include <ext/numeric>
#define oo 0x3f3f3f3f
#define long long long

using namespace std;
//using namespace __gnu_cxx;


int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0), cout.precision(9), cout << fixed;

    string str;
    cin >> str;
    long ans = 0;
    for (int i = 0; i < (1 << ((int)str.size() - 1)); ++i) {
        long x = str[0] - '0';
        for (int j = 0; j < (int)str.size() - 1; ++j) {
            if (i & (1 << j)) {
                ans += x;
                x = 0;
            }
            x = x * 10 + str[j + 1] - '0';
        }
        ans += x;
    }

    cout << ans << '\n';

    return 0;
}


Measured memory_bytes: 3600
#include <algorithm>
#include <array>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>

#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

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

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

    N = (N * (N-1)) / 2;
    M = (M * (M-1)) / 2;

    cout << N+M << endl;

    return 0;
}


Measured memory_bytes: 256
import java.util.*;



class Main {
	Scanner sc = new Scanner(System.in);

	int n;
	public void run() {
		while(sc.hasNext()){
			String str=sc.next();
			String[] strs=str.split(",");
			P[] pos=new P[4];
			for(int i=0;i<4;i++){
				double x=Double.parseDouble(strs[2*i]);
				double y=Double.parseDouble(strs[2*i+1]);
				pos[i]=new P(x,y);
			}
			boolean ok=true;

			int ccw0=P.ccw(pos[0],pos[1],pos[2]);

			for(int i=1;i<4;i++){
				int ccw=P.ccw(pos[i],pos[(i+1)%4],pos[(i+2)%4]);
				if(ccw0*ccw<0){
					ok=false;break;
				}
			}
			ln(ok?"YES":"NO");
		}
	}

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

	public static void pr(Object o) {
		System.out.print(o);
	}

	public static void ln(Object o) {
		System.out.println(o);
	}

	public static void ln() {
		System.out.println();
	}
}

class P{
	double x;
	double y;
	P(double _x,double _y){
		x=_x;
		y=_y;
	}

	public static double dot(P a,P b){
			return a.x*b.x+a.y*b.y;
	}
	public static  double cross(P a,P b){
		return a.x*b.y-a.y*b.x;
	}
	public P a(P a){
		return new P(x+a.x,y+a.y);
	}
	public P s(P a){
		return new P(x-a.x,y-a.y);
	}

	public double norm(){
		return Math.sqrt(x*x+y*y);
	}

	public static int ccw(P a,P b,P c){
		if(P.cross(b.s(a),c.s(a))>Double.MIN_NORMAL){
			return 1;
		}
		if(P.cross(b.s(a),c.s(a))<-Double.MIN_NORMAL){
			return -1;
		}
		if(P.dot(b,c)<-Double.MIN_NORMAL)return 2;
		if(b.norm()<c.norm()-Double.MIN_NORMAL)return -2;
		return 0;
	}
}

Measured memory_bytes: 11000
#include <bits/stdc++.h>
#define REP(i, x, y) for (ll i = x; i <= y; i++)
#define BIT(t) (1ll << t)
#define PER(i, y, x) for (ll i = y; i >= x; i--)
#define vll vector<ll>
#define vvll vector<vector<ll>>
#define pll pair<ll, ll>
#define SIZE(v) ll(v.size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end());
using namespace std;
typedef long long ll;
//        ios::sync_with_stdio(false);
//        cin.tie(nullptr);

ll const MOD = 998244353;
ll mod_p(ll x, ll y) {
       x %= MOD;
       y %= MOD;
       return (x + y + MOD) % MOD;
}

ll mod_m(ll x, ll y) {
       x %= MOD;
       y %= MOD;
       return x * y%MOD;
}

ll mod_pow(ll x, ll t) {
       x %= MOD;
       if (t == 0) {
               return 1;
       }
       else {
               ll v = mod_pow(x, t / 2);
               if (t % 2 == 0) {
                       return v * v % MOD;
               }
               else {
                       return v * v%MOD * x %MOD;
               }
       }
}

ll mod_inv(ll x) {
       return mod_pow(x, MOD - 2);
}

int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;
  vvll dp(c+1, vll(d+1));
  dp[a][b] = 1;
  REP(x,a,c){
    REP(y,b,d){
      if(x == a && y == b) {continue;}
      ll t1 = mod_m(dp[x][y-1], x);
      ll t2 = mod_m(dp[x-1][y], y);
      ll t3 = mod_m(mod_m(x-1, y-1), dp[x-1][y-1]);
      dp[x][y] = mod_p(mod_p(t1, t2), -t3);
    }
  }
  cout << dp[c][d] << endl;
}

Measured memory_bytes: 73660