akhauriyash/Code-Regression huggingface dataset:
import sys


def main():
    n, s = sys.stdin.read().split()
    n = int(n)

    left, right = 0, 0
    for char in s:
        if char == '(':
            right += 1 
            # これ以前に出現している')'の数が'('の数より多い可能せがあるのでleftを削ることはできないため、ペアになる可能性としての')'を追加
        elif char == ')':
            if right: 
                # rightがあるならこれより前に必ずペア未確定の'('が存在するのでrightの可能性を一つ削ってこれを代わりにその'('とペアにする
                right -= 1
            else: 
                # rightがない場合はペア未確定の'('がこれ以前に出現していないということので'('を追加してこれとペアにするしかない
                left += 1
    
    ans = '(' * left + s + ')' * right
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3188
#include<stdio.h>
int main(void)
{
	int a,b,c,d,e;
	int ans1,ans2;
	scanf("%d%d%d%d%d",&a,&b,&c,&d,&e);
	
	if(a<b)
		ans1=a;
	else
		ans1=b;
	
	if(ans1>c)
		ans1=c;
		
	if(d<e)
		ans2=d;
	else
		ans2=e;
	
	printf("%d\n",ans1+ans2-50);
}


Measured memory_bytes: 2700
a,b,k = map(int,input().split())
if 2*k < b - a + 1:
    for i in range(a,b+1)[:k]:
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
else:
    for i in range(a,b+1):
        print(i)

Measured memory_bytes: 3060
#include<stdio.h>
#include<string.h>

int main()
{
	int q,a,b,i,j,s;
	char str[1001];
	char meirei[8];
	char p[1000];
	
	scanf("%s",str);
	scanf("%d",&q);
	
	for(i=0;i<q;i++)
	{
		scanf("%s %d %d",meirei,&a,&b);
		if(meirei[2] == 'p'){
			scanf("%s",p);
			
			for(j=a;j<=b;j++){
				str[j]=p[j-a];
			}
		}else if(meirei[2] == 'v'){
			
			for(j=a;j<=(a+b)/2;j++){
				int temp = str[j];
				str[j] = str[b-(j-a)];
				str[b-(j-a)] = temp;
			}
		} else if(meirei[2] == 'i'){
			
			for(j=a;j<=b;j++){
				putchar(str[j]);
		
			}
			putchar('\n');
		}
	}
		
	return 0;
}


Measured memory_bytes: 2144
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
const int N = 1000000;


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

    if(n < 105)print(0);
    else if(n < 135)print(1);
    else if(n < 165)print(2);
    else if(n < 189)print(3);
    else if(n < 195)print(4);
    else print(5);
}

Measured memory_bytes: 384
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
 
int main(){
  int n;
  //while(1){
    cin >> n;
    int x[100] = {0}, y[100] = {0};
    for ( int i = 0; i < n; i++ ) cin >> x[i];
    for ( int i = 0; i < n; i++ ) cin >> y[i];
    double Dxy = 0;
    for ( int p = 1; p <= 3; p++) {
      long long dxy = 0; //intだとtestcase14でoverflow
      for ( int i = 0; i < n; i++ ) dxy += pow( fabs(x[i] - y[i]), p);
      Dxy = pow( dxy, 1.0/p);
      printf ("%lf\n", Dxy);
    }
    Dxy = 0;
    for ( int i = 0; i < n; i++ ) {
      Dxy = max(Dxy, fabs(x[i]-y[i]) );
    }
    printf ("%lf\n", Dxy);
     
    return 0;
 }


Measured memory_bytes: 3364
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce


def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

sys.setrecursionlimit(10000)

mod = 1000000007

"""
# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]

# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""

if __name__ == "__main__":
    K = int(sys.stdin.readline())
    o = K // 2
    e = K - o
    print(o * e)

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

int main(){
    ll n; cin >> n;
    vector<ll> ans(n+1);
    for(ll x=1;x<=sqrt(n)+1;x++){
        for(ll y=1;y<=sqrt(n)+1;y++){
            for(ll z=1;z<=sqrt(n)+1;z++){
                ll cal=x*x+y*y+z*z+x*y+y*z+z*x;
                if(1<=cal && cal<=n){
                    ans[cal]++;
                }
            }
        }
    }
    for(ll i=1;i<=n;i++) cout << ans[i ] << endl;
    return 0;
}

Measured memory_bytes: 3720
import java.util.*;
class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String f =sc.nextLine();
    String a = sc.nextLine();
    int c=0;
    for(int i=0;i<3;i++){
      if(f.charAt(i)==a.charAt(i)) c++;
    }
    System.out.println(c);
  }
}

Measured memory_bytes: 23764
#include <bits/stdc++.h>
#include <iomanip> 
using namespace std; 
#define rep(i,a,b)		for(long int i=a;i<=b;i++)
#define MOD 1e9+7

long long int n;
int main() 
{ 
	ios::sync_with_stdio(false);
    cin.tie(NULL);  
    
    
	cin>>n;
	cout<<((int)sqrt(n)*(int)sqrt(n));
}
	

Measured memory_bytes: 3652
import collections

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

vlist1=[vlist[2*i] for i in range(n//2)]
vlist2=[vlist[2*i+1] for i in range(n//2)]
#print(vlist1)
#print(vlist2)

vc1=collections.Counter(vlist1).most_common()
vc2=collections.Counter(vlist2).most_common()
#print(vc1)
#print(vc2)

if vc1[0][0]!=vc2[0][0]:
  print(n-vc1[0][1]-vc2[0][1])
elif len(vc1)==1 and len(vc2)==1:
  print(n//2)
elif len(vc1)==1:
  print(n//2-vc2[1][1])
elif len(vc2)==1:
  print(n//2-vc1[1][1])
else:
  if vc1[0][1]>vc2[0][1]:
    print(n-vc1[0][1]-vc2[1][1])
  elif vc1[0][1]<vc2[0][1]:
    print(n-vc1[1][1]-vc2[0][1])
  else:
    max_2nd=max(vc1[1][1],vc2[1][1])
    print(n-vc1[0][1]-max_2nd)

Measured memory_bytes: 21084
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    string s;
    cin>>s;
    if(s=="ABC"){
        cout<<"ARC"<<endl;
    }else{
        cout<<"ABC"<<endl;
    }
}


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

#define FOR(i, a, b) for (long long i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define RREP0(i, n) for (int i = (n)-1; i >= 0; --i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define RREP1(i, n) for (int i = (n); i >= 1; --i)
#define pow10(n) int(1e##n + n)

typedef long long LL;
typedef pair<int, int> P;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
long double eps = 1.0E-14;
const LL mod = LL(1e9) + 7;

void solve()
{
    int N, K;
    cin >> N >> K;
    LL sum = 0;
    FOR (k, K, N + 2)
    {
        LL lower = k * (k - 1) / 2;
        LL upper = k * (2 * N - k + 1) / 2;
        sum += upper - lower + 1;
        sum %= mod;
    }
    std::cout << sum << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(20);
    solve();
    return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
const int nax=1e5+5;
vector<vector<int> > adj(nax);
int mul(int a,int b)
{
    return ((1LL)*a*b)%mod;
}
pair<int,int > dfs(int u,int p)
{
    pair<int,int> ans={1,1};
    if(adj[u].size()==1&&adj[u][0]==p) return ans;//if leaf
    for(auto v: adj[u])
    {
        pair<int,int> cur;
        if(v==p) continue;
       cur= dfs(v,u);
       ans.first=mul(ans.first,((cur.first+cur.second)%mod));
       ans.second=mul(ans.second,cur.first);
    }
  //  cout<<ans.first<<" "<<ans.second<<endl;
    return ans;
}
int main()
{

int n;
cin>>n;
for(int i=0;i<n-1;i++)
{
    int x,y;
    cin>>x>>y;
    adj[x].push_back(y);
    adj[y].push_back(x);

}
pair<int,int >ans=dfs(1,-1);
cout<<(ans.first+ans.second)%mod;


}

Measured memory_bytes: 12672
#include <iostream>
#include <cassert>
#include <vector>
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <string>
#include <sstream>
#include <iterator>
#include <map>
#include <algorithm>
#include <memory>
#include <iomanip>
#include <limits>
#include <typeinfo>
 
#include <stdio.h>
#include <string.h>
 
 
using namespace std;
 
int main(int argc, char* argv[])
{
	unsigned long long H,W;
	unsigned long long i;
	unsigned long long ans1,ans2,ans3,ans4,answrk;
	unsigned long long Smax,Smin;
	unsigned long long S1,S2,S3;
	unsigned long long amari;
 
	cin >> H >> W;
	
	if(H % 3 != 0){
		amari = 1;
	}else{
		amari = 0;
	}

	//1
	S1 = (H / 3 + amari) * W;
	S2 = (H / 3) * W;
	S3 = (H / 3) * W;
	Smax=max(S1,max(S2,S3));
	Smin=min(S1,min(S2,S3));
	ans1 = Smax-Smin;
 
	//3
	S1 = (W / 3 + amari) * H;
	S2 = (W / 3) * H;
	S3 = (W / 3) * H;
	Smax=max(S1,max(S2,S3));
	Smin=min(S1,min(S2,S3));
	ans3 = Smax-Smin;
 
	// 2
	answrk = numeric_limits<unsigned long long>::max();
	for(i=1 ; i <= H / 2 + 1; i++){
		S1 = i * W;
		S2 = (H - i) * (W / 2);
		S3 = (H - i) * (W - (W / 2));
		Smax=max(S1,max(S2,S3));
		Smin=min(S1,min(S2,S3));		
		if(answrk>Smax-Smin){
			answrk=Smax-Smin;
		}
	}
	ans2=answrk;
 
	// 4
	answrk = numeric_limits<unsigned long long>::max();
	for(i=1 ; i <= W / 2 + 1; i++){
		S1 = i * H;
		S2 = (W - i) * (H / 2);
		S3 = (W - i) * (H - (H / 2));
		Smax=max(S1,max(S2,S3));
		Smin=min(S1,min(S2,S3));		
		if(answrk>Smax-Smin){
			answrk=Smax-Smin;
		}
	}
	ans4=answrk;
 
	cout << min(ans1,min(ans2,min(ans3,ans4))) << endl;
 
	return 0;
}


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

string s,t;
int sum;

int main(){
	cin>>s>>t;
	int n = s.length();
	for(int i = 0;i < n;i++){
		if(s[i] != t[i]){
			cout<<"No"<<endl;
			break;
		}else{
			sum++;
		}
	}
	if (sum == n){
		cout<<"Yes"<<endl;
	}
}


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

using namespace std;

int64_t calc(std::vector<int64_t> as) {
  int64_t const n = as.size();
  if (n == 1) {
    return 0;
  }
  for (int64_t i = 0; i < n; ++i) {
    as[i] -= i + 1;
  }
  std::sort(as.begin(), as.end());
  int64_t const b_min = as.front();
  int64_t const b_max = as.back();
  int64_t const b_mid = as[n / 2];
  int64_t sad_mid = 0;
  for (int64_t i = 0; i < n; ++i) {
    sad_mid += std::abs(as[i] - b_mid);
  }
  if (sad_mid == 0) {
    return 0;
  }
  int64_t ret = sad_mid;
  auto const over_b_mid_itr = std::upper_bound(as.begin(), as.end(), b_mid);
  auto over_b_itr = over_b_mid_itr;
  int64_t over_b_idx = over_b_itr - as.begin();
  int64_t b = b_mid + 1;
  for (; b <= b_max; ++b) {
    int64_t const sad = ret + over_b_idx - (n - over_b_idx);
    if (sad == 0) {
      return 0;
    }
    if (sad > ret) {
      break;
    }
    ret = sad;
    over_b_itr = std::upper_bound(as.begin(), as.end(), b);
    over_b_idx = over_b_itr - as.begin();
  }
  if (ret == sad_mid) {
    auto ge_b_itr = std::lower_bound(as.begin(), as.end(), b_mid);
    int64_t ge_b_idx = ge_b_itr - as.begin();
    b = b_mid - 1;
    for (; b >= b_min; --b) {
      int64_t const sad = ret + (n - ge_b_idx) - ge_b_idx;
      if (sad == 0) {
        return 0;
      }
      if (sad > ret) {
        break;
      }
      ret = sad;
      ge_b_itr = std::lower_bound(as.begin(), as.end(), b);
      ge_b_idx = ge_b_itr - as.begin();
    }
  }
  return ret;
}

int main() {
  int64_t n;
  std::cin >> n;
  std::vector<int64_t> as(n);
  for (int64_t i = 0; i < n; ++i) {
    std::cin >> as[i];
  }
  std::cout << calc(as) << std::endl;
  return 0;
}


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

int main(){
  
  string a,b;
  cin >> a >> b;
  
  if( a > b ){
    
    cout << ">" << endl;
    
  }
  
  else if( a == b ){
    
    cout << "=" << endl;
    
  }
  
  else{
    
    cout << "<" << endl;
    
  }
  
}


Measured memory_bytes: 3600
import numpy as np
#n = int(input())
#n, m = map(int, input().split())
#for i in range(n):

T = input()
n = len(T)
S = ''
#PDとDDは同じ
for i in range(n):
    if T[i] == '?':
        S += 'D'
    else:
        S += T[i]
print(S)  

Measured memory_bytes: 27452
#include<iostream>

using namespace std;

int main(){

    string S;
    cin>> S;

    string ans;
    for(int i=0; i<S.size(); i++){
        if(S[i]=='B'){
            if(!ans.empty()){
                ans.pop_back();
            }
        }else{
            ans+=S[i];
        }
    }

    cout<< ans<< endl;

    return 0;
}


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

#define fi first
#define se second

const int N = 500500;
const int Q = 1 << 21;
const long long mod = 1e9 + 7;

using namespace std;

int n;
int a[N];
int d[N];
int s[N];
vector < int > v[Q];

void add(int &x, int y)
{
        x += y;
        if(x >= mod){
                x -= mod;
        } else if(x < 0){
                x += mod;
        }
}

vector < int > compute(vector < int > &g)
{
        vector < int > res;

        int S = 0, T = 0;
        for(int x: g){
                d[x] = 1;
                add(d[x], 1ll * S * s[x] % mod);
                add(d[x], T);
                add(T, - 1ll * d[x] * s[x] % mod);
                add(S, d[x]);
                res.push_back(d[x]);
        }
        return res;
}

int main()
{
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        //freopen("teleports.in", "r", stdin);
        //freopen("teleports.out", "w", stdout);
        ios_base::sync_with_stdio(0);

        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
                a[i] ^= a[i - 1];
                v[a[i]].push_back(i);
                s[i] = s[i - 1] + (a[i] == 0);
        }

        int res = 0;
        for(int i = 1; i < Q; i++){
                if(v[i].empty() || a[n] != 0){
                        continue;
                }

                auto f = compute(v[i]);
                for(int x: f){
                        add(res, x);
                }
        }
        if(a[n] != 0){
                auto f = compute(v[a[n]]);
                add(res, f.back());
        }
        else{
                int C = 1;
                for(int i = 1; i < v[0].size(); i++){
                        add(C, C);
                }
                add(res, C);
        }
        cout << res << "\n";
}


Measured memory_bytes: 64884
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
int MOD=1000000007;
struct Node{
    int no;
    int par;
    vector<Node*> child;
    void build(int i){
        no=i;
        par=i;
    }
};
struct Tree{
    int n;
    vector<Node> node;
    Tree(int k){
        n=k;
        node.resize(n+1);
        for(int i=1;i<=n;++i){
            node[i].build(i);
        }
    }
    void input(int k){
        for(int i=0;i<k;++i){
            int a,b;cin>>a>>b;
            node[a].child.push_back(&node[b]);
            node[b].child.push_back(&node[a]);
        }
    }
    void BFS(int s,int& res){
        queue<Node> que;
        int k=res;
        que.push(node[s]);
        while(!que.empty()){
            Node buf=que.front();que.pop();
            int num=buf.child.size();
            int cnt=0;
            for(int i=0;i<num;++i){
                if(buf.child[i]->no!=buf.par){
                    if(buf.par==buf.no)res*=k-1-cnt;
                    else res*=k-2-cnt;
                    res%=MOD;
                    //printf("no=%lld, res=%lld\n",buf.child[i]->no,res);
                    buf.child[i]->par=buf.no;
                    que.push(*buf.child[i]);
                    ++cnt;
                }
            }
        }
    }
    void DFS(Node& node){
        if(node.child.size()==1&&node.par!=node.no){
            return;
        }
        else{
            int num=node.child.size();
            for(int i=0;i<num;++i){
                if(node.child[i]->no!=node.par){
                    DFS(*node.child[i]);
                }
            }
        }
    }
};
signed main(){
    int n,k;cin>>n>>k;
    Tree tree(n);
    tree.input(n-1);
    int res=k;
    tree.BFS(1,res);
    cout<<res<<"\n";
    return 0;
}

Measured memory_bytes: 16228
import java.util.*;
import java.io.PrintWriter;
public class Main{
	static long mod=1000000007;
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int k=sc.nextInt();
		long ans=0;
		long[] kk=new long[k+1];
		for(int i=k; i>=1; i--){
			kk[i]=modpow(k/i,n);
			for(int j=2; j<=k/i; j++){
				kk[i]=(kk[i]-kk[i*j]+mod)%mod;;
			}
			ans=(ans+kk[i]*i)%mod;
		}
		System.out.println(ans);
	}
	static long modpow(long left,long right){
		long ans=1;
		while(right>0){
			if((right&1)==1){
				ans*=left;
			}
			right>>=1;
			left*=left;
			ans%=mod;
			left%=mod;
		}
		return ans;
	}
}


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

typedef long long ll;
typedef pair<int,int> ii;

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	stack<char> stk;
	char ch;
	while(cin>>ch) {
		if(ch=='B') {
			if(!stk.empty()) stk.pop();
		} else stk.push(ch);
	}
	string ret;
	while(!stk.empty()) ret+=stk.top(), stk.pop();
	reverse(ret.begin(), ret.end());
	cout << ret << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
ll n, m;
char a[1005][1005];
string s[5][12] =
{
	{
	    "aacd",
        "bbcd",
        "cdaa",
        "cdbb"
	}
    ,
	{
	    "aabba",
        "bcc.a",
        "b..cb",
        "a..cb",
        "abbaa"
    }
    ,
	{
	    "aacd..",
        "bbcd..",
        "..aacd",
        "..bbcd",
        "cd..aa",
        "cd..bb"
	}
    ,
    {
        "aabbcc.",
        "dd.dd.a",
        "..d..da",
        "..d..db",
        "dd.dd.b",
        "..d..dc",
        "..d..dc"
    }
};
int main()
{
    cin>>n;
    if(n <= 2)
    {
        cout<<-1<<endl;
        return 0;
    }
    if(n == 3)
    {
        cout<<"aa.\n";
        cout<<"..b\n";
        cout<<"..b\n";
        return 0;
    }
    ll cnt = n - n / 4 * 4 + 4;
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < n; j++)
        {
            a[i][j] = '.';
        }
    }
    for(ll i = 0; i < cnt; i++)
    {
        for(ll j = 0; j < cnt; j++)
        {
            a[i][j] = s[cnt - 4][i][j];
        }
    }
    for(; cnt < n; cnt += 4)
    {
        for(ll i = 0; i < 4; i++)
        {
            for(ll j = 0; j < 4; j++)
            {
                a[i + cnt][j + cnt] = s[0][i][j];
            }
        }
    }
    for(ll i = 0; i < n; i++)
    {
        for(ll j = 0; j < n; j++)
        {
            printf("%c", a[i][j]);
        }
        puts("");
    }
    return 0;
}


Measured memory_bytes: 2176
import java.util.*;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while(in.hasNext()){
			int n = in.nextInt();
			if(n == 0) break;
			int xmax=0,xmin=0,ymax=0,ymin=0;
			ArrayList<Integer> x = new ArrayList<Integer>();
			ArrayList<Integer> y = new ArrayList<Integer>();
			x.add(0);
			y.add(0);
			for(int i=1; i<n; i++){
				int id = in.nextInt();
				switch(in.nextInt()){
				case 0:
					x.add(x.get(id)-1);
					y.add(y.get(id));
					break;
				case 1:
					x.add(x.get(id));
					y.add(y.get(id)-1);
					break;
				case 2:
					x.add(x.get(id)+1);
					y.add(y.get(id));
					break;
				case 3:
					x.add(x.get(id));
					y.add(y.get(id)+1);
					break;
				}
				xmax = Math.max(xmax, x.get(i));
				xmin = Math.min(xmin, x.get(i));
				ymax = Math.max(ymax, y.get(i));
				ymin = Math.min(ymin, y.get(i));
				
			}
			System.out.println((xmax-xmin+1)+" "+(ymax-ymin+1));
		}
		
	}

}

Measured memory_bytes: 12000
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <numeric>
#include <map>
#include <iomanip>
#include <queue>

using namespace std;    
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
const bool DEBAG = false;

vector< vector<char> > data;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

ll H, W;


struct Grid
{
    int h;
    int w;
    int depth;

    Grid(int h, int w, int depth){
        this->h = h;
        this->w = w;
        this->depth = depth;
    }
};


int search( int sh, int sw ){

    queue<Grid> que;
    Grid g(sh, sw, 0);
    que.push(g);

    const int INF = 1000000;

    vector< vector<int> > used(H);
    for(int i = 0; i < H; i++) used[i].resize(W);
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            used[i][j] = INF;
        }
    }

    while ( !que.empty() )
    {

        Grid g = que.front();
        que.pop();
        if( used[ g.h ][ g.w ] != INF ) continue;
        used[g.h][g.w] = g.depth;
        for(int i = 0; i < 4; i++){
            int nx = g.h + dx[i];
            int ny = g.w + dy[i];
            int depth = g.depth + 1;
            if(nx < 0 || nx >= H) continue;
            if(ny < 0 || ny >= W) continue;
            if( data[nx][ny] == '#' ) continue;
            if( used[nx][ny] != INF ) continue;
            que.push ( Grid( nx, ny, depth ) );
        }

    }
    
    int ret = 0;
    for(int i = 0; i < H; i++ ){
        for(int j = 0; j < W; j++){
            if(data[i][j] == '.') ret = max( ret, used[i][j] ); 
        }
    }
    return ret;

}


int main(){

    cin >> H >> W;

    data.resize(H);
    for(int i = 0; i < H; i++) data[i].resize(W);

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            cin >> data[i][j];
        }
    }


    int ans = 0;
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            if( data[i][j] == '.' ) ans = max(  ans, search(i, j) );
            //if(ans == 10) cout << i << j << endl;
        }
    }
    cout << ans << endl;



}


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

// m以上の大きい数n個でsを作る場合の数
int solve(int n, int s, int m){
  if(n == 1){
    if(0 <= s && s <= 9 && s >= m) return 1;
    else return 0;
  }

  int ans = 0;
  for(int i=m; i<=9; i++) ans += solve(n-1, s-i, i+1);
  return ans;
}

int main(){
  int n, s;

  while(true){
    cin >> n >> s;
    if(n == 0 && s == 0) break;
    cout << solve(n, s, 0) << endl;;
  }
}
  
  


Measured memory_bytes: 3104
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}

#define int ll
int dp[5][60000] = {};
void solve() {
	dp[0][0] = 1;
	for (int i = 1; i*i < 60000; ++i) {
		for (int q = 0; q < 4; ++q) {
			for (int j = 0; j + i * i < 60000; ++j) {
				dp[q + 1][i * i + j] += dp[q][j];
			}
		}
	}
	while (true) {
		int n;
		cin >> n;
		if (n == 0) return;
		int ans = 0;
		REP(q, 5) {
			ans += dp[q][n];
		}
		cout << ans << endl;
	}
}
#undef int
int main() {
	init();
	solve();
}


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

int main(){
    int n;
    cin >> n;
    vector<int> d(n);
    rep(i,n){
        cin >> d[i];
    }
    sort(d.begin(), d.end());

    int a, b;
    rep(i,n){
        if(i==n/2-1){
            a = d[i];}
        if(i==n/2+1-1){
            b = d[i];
        }
    }
    cout << b - a ;
    return 0;
}

Measured memory_bytes: 640
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))
A.sort()
T = [A[0]]
for i in range(1,len(A)):
  if A[i]//A[0] != 0:
    T.append(A[i])
  else:
    pass

ans = A[0]
for i in range(len(T)):
  ans = gcd(ans,T[i])
print(ans)

Measured memory_bytes: 16244
#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define ITR(i,b,e) for(auto i=(b);i!=(e);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,begin(v),end(v)) os<<*i<<(i==end(v)-1?"":"\n"); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,begin(v),end(v)) is>>*i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
    is>>p.first>>p.second; return is; }
template <class T> bool chmax(T &a,const T &b) {if(a<b) {a=b;return 1;} return 0;}
template <class T> bool chmin(T &a,const T &b) {if(b<a) {a=b;return 1;} return 0;}
template <class T> using heap = priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

signed main() {
    string x,y;
    cin>>x>>y;
    if(x>y) cout<<">"<<endl;
    else if(x<y) cout<<"<"<<endl;
    else cout<<"="<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1010];
int t[30],n,m,c1,c2;
int main()
{
	scanf("%d%d",&n,&m);
	memset(t,0,sizeof(t));
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			t[s[j]-'a']++;
	}
	c1=c2=0;
	for(int i=0;i<=25;i++)
	{
		if(t[i]&1){c1++;t[i]--;}
		if(t[i]%4==2){c2++;t[i]-=2;}
		//cout<<t[i]<<endl;
	}
	if(n&1) swap(m,n);
	//cout<<n<<' '<<m<<endl;
	if((n%2==1)&&(m%2==1))
	{
		if((c1==1)&&(c2<=(n+m-2)/2))puts("Yes");
		else puts("No");
	}else 
	if(m%2==1)
	{
		if(c1==0&&c2<=(n/2)) puts("Yes");
		else puts("No");
	}
	else 
	{
		if(c1==0&&c2==0) puts("Yes");
		else puts("No");
	}
	
	return 0;
}

Measured memory_bytes: 256
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。ノード番号は１から開始なのでn+1個。
        # par[x]<0の時そのノードは根で、par[x]の絶対値はグループのサイズ
        self.parents = [-1] * (n+1)

    # 親の親の...を辿って根を見つける
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 再度検索する時に手間がかからないよう根を繋ぎかえる
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # xの属するグループとyの属するグループを併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return True

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # xが属するグループのサイズを返す
    def size(self, x):
        x = self.find(x)
        return -self.parents[x]

n, m, k = map(int, input().split())
friend = [list(map(int, input().split())) for _ in range(m)]
block = [list(map(int, input().split())) for _ in range(k)]

already = [0]*n
uf = UnionFind(n)

for a, b in friend:
    uf.union(a, b)
    already[a-1] += 1
    already[b-1] += 1

ans = [uf.size(x) - already[x-1] - 1 for x in range(1, n+1)]

for a, b in block:
    if uf.same(a, b):
        ans[a-1] -= 1
        ans[b-1] -= 1

print(*ans)

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

int main(void){
    int n, l, tmp_max, tmp_min, res = 0;
    cin >> n >> l;
    vector<int> v(n);
    for (int i = 0; i < n; i ++){
        v[i] = l + i;
    }

    tmp_max = *max_element(v.begin(), v.end());
    tmp_min = *min_element(v.begin(), v.end());

    for (int i = 0; i < n; i ++)
        res += v[i];

    if (tmp_max >= 0 && tmp_min <= 0)
        res = res;
    else if (tmp_max < 0)
        res -= tmp_max;
    else if (tmp_min > 0)
        res -= tmp_min;

    cout << res << endl;
}


Measured memory_bytes: 256
#include<cstdio>
using namespace std;
int n;
struct point{
    double x,y;
    point(double x=0,double y=0):x(x),y(y){}
}p[4];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        for(int j=0;j<4;++j){
            scanf("%lf%lf",&(p[j].x),&(p[j].y));                                                  //1.double要用%lf
        }
        point tp1(p[0].x-p[1].x,p[0].y-p[1].y),tp2(p[2].x-p[3].x,p[2].y-p[3].y);
        if((tp1.x*tp2.y-tp1.y*tp2.x-0)==0){
            printf("2\n");
        }else if((tp1.x*tp2.x+tp1.y*tp2.y)==0){
            printf("1\n");
        }else{
            printf("0\n");
        }
    }
    return 0;
}


Measured memory_bytes: 2736
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

ll comb_count(int n, int m) {
  if (m == 0)
    return 1;
  if (n == 0)
    return 0;
  return (n * comb_count(n - 1, m - 1) / m);
}

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

  int n;
  string s;
  cin >> n >> s;

  map<char, int> mp;
  rep(i, 0, s.size()) mp[s[i]]++;

  ll r = mp['R'], g = mp['G'], b = mp['B'];
  ll ans = r * g * b;
  rep(i, 0, n) {
    rep(j, 0, n) {
      if (i - j < 0 || i + j >= n)
        break;
      if (s[i] != s[i - j] && s[i - j] != s[i + j] && s[i] != s[i + j])
        ans--;
    }
  }

  cout << ans << endl;
}


Measured memory_bytes: 3632
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**3
eps = 1.0 / 10**10
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    while True:
        w,d = LI()
        if w == 0:
            break
        a = sorted(LI())
        b = sorted(LI())
        ai = 0
        bi = 0
        r = 0
        while ai < w or bi < d:
            if ai >= w:
                r += sum(b[bi:])
                break
            if bi >= d:
                r += sum(a[ai:])
                break
            if a[ai] == b[bi]:
                r += a[ai]
                ai += 1
                bi += 1
            elif a[ai] < b[bi]:
                r += a[ai]
                ai += 1
            else:
                r += b[bi]
                bi += 1
        rr.append(r)

    return '\n'.join(map(str, rr))


print(main())




Measured memory_bytes: 9028
from collections import defaultdict


n, m = map(int, input().split())
h = list(map(int, input().split()))
e = [list(map(int, input().split())) for _ in range(m)]

graph = defaultdict(list)

for dep, dest in e:
    graph[dep].append(dest)
    graph[dest].append(dep)

cnt = 0
for node in range(1, n+1):
    if graph[node]:
        flag = True
        for v in graph[node]:
            if h[node-1] <= h[v-1]:
                flag = False
                break
        if flag:
            cnt += 1
    else:
        cnt += 1

print(cnt)





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

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define ll long long
#define ldb long double 
#define db double
#define str string

#define fr first
#define se second
#define lb lower_bound 
#define ub upper_bound 
#define pb push_back
#define mpr make_pair

#define pi pair<int,int>
#define pll pair<ll,ll>
#define pdb pair<db,db>
#define pldb pair<ldb,ldb>

#define vi vector<int>
#define vll vector<ll>
#define vdb vector<db>
#define vldb vector<ldb>
#define vpi vector< pi >
#define vpll vector< pll >

#define mi map<int,int>
#define mll map<ll,ll>
#define mdb map<db,db>
#define mldb map<ldb,ldb>


#define forr(a,b) for (int i = (a); i < (b); ++i)
#define rrof(a,b) for (int i = (b)-1; i >= (a); --i)

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

const int md = 1e9+7;
const int MX = 2e5+5;
const ll INF = 1e18; 
const ldb PI = 4*atan((ldb)1);

ll power(ll a,ll n)
{
 ll res=1;
 while(n)
{
 if(n%2)
  res*=a;
  a*=a;
  n/=2;
}
return res;
}

ll abst(ll a)
{
 return ((a<0)?(-1*a):(a));
}

int main()
{
    fast;
    ll h,n;
    cin>>h>>n;
    vpll v;
    for(int i=0;i<n;i++)
    {
        ll x,y;
        cin>>x>>y;
        v.pb({x,y});
    }
    ll dp[20001];
    dp[0]=0;
    for(int i=1;i<=h;i++)
    {
        dp[i]=1e12;
        for(int j=0;j<n;j++)
        {
            ll p=max((ll)0,i-v[j].fr);
            dp[i]=min(dp[i],dp[p]+v[j].se);
        }
    }
    cout<<dp[h]<<"\n";
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>
int cnt;

void is(int k) {
    int a1=k/10000;
    int a2=(k/1000)%10;
    int a4=(k/10)%10;
    int a5=k%10;
    if(a1==a5 && a2==a4) cnt++;
}

int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    for(int i=a; i<=b; i++) {
        is(i);
    }
    printf("%d", cnt);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define N 16
#define oo (1<<29)
using namespace std;
int n,m,G[N][N],f[1<<N][N],S[1<<N],sum;
int main()
{
	int i,j,k,l,x,y,z;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&x,&y,&z);
		x--,y--,G[x][y]=G[y][x]=z,sum+=z;
	  }
	for(i=0;i<(1<<n);i++)
		for(j=0;j<n;j++)
			if((i>>j)&1)
				for(k=j+1;k<n;k++)
					if((i>>k)&1)
						S[i]+=G[j][k];
	for(i=0;i<(1<<n);i++)
		for(j=0;j<n;j++) f[i][j]=-oo;
	for(i=0;i<(1<<n);i++)
		if(i&1) f[i][0]=S[i];
	for(i=1;i<(1<<n);i++)
		for(j=0;j<n;j++)
			if((i>>j)&1)
				for(k=i;k;k=(k-1)&i)
					if(k&1)
						for(l=0;l<n;l++)
							if(((k>>l)&1)&&((~k>>j)&1)&&G[l][j])
								f[i][j]=max(f[i][j],f[k][l]+G[l][j]+S[i^k]);
	cout<<sum-f[(1<<n)-1][n-1];
	return 0;
}


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

using namespace std;

int main()
{
    int n,a[100];
    cin >> n;
    for(int i = 0;i<n;i++)  cin >> a[i];
    int Ans = 0;
    for(int i = 0;i<n;i++){
        for(int j = i + 1;j<n;j++){
            Ans+=a[i]*a[j];
        }
    }
    cout << Ans;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define pb push_back
#define all(v) v.begin(),v.end()
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	string s,t,ta="";
	cin>>s>>t;
	sort(all(s));
	sort(all(t));
	rep(i,t.size())ta+=t[t.size()-1-i];
	if(s<ta)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

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

using namespace std;

typedef long long ll;

const int MAX_N = 1e5 + 10;

int N;
ll A[MAX_N], B[MAX_N], ans = LLONG_MAX;
pair<ll, int> seq[MAX_N * 2];
ll sum[MAX_N];
vector<int> pos[MAX_N];

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) scanf("%lld%lld", &A[i], &B[i]);
    ans = min(ans, accumulate(A + 1, A + N + 1, 0ll));
    ans = min(ans, accumulate(B + 1, B + N + 1, 0ll));
    for (int i = 1; i <= N; i++) seq[i] = make_pair(A[i], i);
    for (int i = 1; i <= N; i++) seq[N + i] = make_pair(B[i], i);
    sort(seq + 1, seq + 2 * N + 1);
    for (int i = 1; i <= 2 * N; i++) pos[seq[i].second].push_back(i);
    for (int i = 1; i <= 2 * N; i++) sum[i] = sum[i - 1] + seq[i].first;
    for (int i = 1; i <= N; i++) {
        int x = N;
        if (pos[i][0] > x || pos[i][1] > x) x--;
        if (pos[i][0] > x && pos[i][1] > x) x--;
        ll res = sum[x];
        for (int j : pos[i])
            if (j > x) res += seq[j].first;
        ans = min(ans, res);
    }
    printf("%lld\n", ans);
}


Measured memory_bytes: 11136
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;

#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(a) (a).begin(),(a).end()
#define PI 3.141592653589793238
#define INF 1050000000

using vi = vector<int>;


int main() {

	int A, B,C;

	cin >> A >> B >> C;

	if (A - B > C) {
		cout << 0 << endl;
	}
	else {
		cout << C-(A-B) << endl;
	}

	return 0;
}

Measured memory_bytes: 256
N = int(input())
s_t = []
for _ in range(N):
    s, t = input().split()
    s_t.append((s, int(t)))

X = input()

time = 0
sleeping = False
for s, t in s_t:
    if sleeping:
        time += t
    if s == X:
        sleeping = True

print(time)


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

#define MAX 100000

class DisjointSet{
public:
  vector<int> rank,p;

  DisjointSet() {}
  DisjointSet(int size){
    rank.resize(size,0);
    p.resize(size,0);
    for(int i=0;i<size;i++) makeSet(i);
  }

  void makeSet(int x){
    p[x]=x;
    rank[x]=0;
  }

  bool same(int x,int y){
    return findSet(x)==findSet(y);
  }

  void unite(int x,int y){
    link(findSet(x),findSet(y));
  }

  void link(int x,int y){
    if(rank[x]<rank[y]){
      p[y]=x;
    }else{
      p[x]=y;
      if(rank[x]==rank[y]){
        rank[y]++;
      }
    }
  }

  int findSet(int x){
    if(x!=p[x]){
      p[x]=findSet(p[x]);
    }
    return p[x];
  }
};

class Edge{
public:
  int source,target,cost;
  Edge(int source=0,int target=0,int cost=0):
  source(source),target(target),cost(cost){}
  bool operator < (const Edge &e) const{
    return cost < e.cost;
  }
};

int kruskal(int N,vector<Edge> edges){
  int totalCost=0;
  sort(edges.begin(),edges.end());
  DisjointSet dset=DisjointSet(N+1);

  for(int i=0;i<N;i++) dset.makeSet(i);

  int source,target;
  for(int i=0;i<edges.size();i++){
    Edge e=edges[i];
    if(!dset.same(e.source,e.target)){
      // MST.push_back(e);
      totalCost+=e.cost;
      //cout<<totalCost<<endl;
      dset.unite(e.source,e.target);
    }
  }
  return totalCost;
}

struct Node{
  int x,y,id;
} node[MAX+1];
int cmpx(Node a,Node b){
  return a.x<b.x;
}
int cmpy(Node a,Node b){
  return a.y<b.y;
}
int main(){
  int n;
  int source,target;

  cin>>n;

  vector<Edge> edges;
  for(int i=0;i<n;i++){
    cin>>node[i].x>>node[i].y;
    node[i].id=i;
    //edges.push_back(Edge(source,target,cost));
  }
  sort(node,node+n,cmpx);
  for(int i=1;i<n;i++){
    //cout<<abs(node[i-1].x-node[i].x)<<endl;
    edges.push_back(Edge(node[i-1].id,node[i].id,node[i].x-node[i-1].x));
    //edges.push_back(Edge(node[i].id,node[i-1].id,abs(node[i-1].x-node[i].x)));
  }
  sort(node,node+n,cmpy);
  for(int i=1;i<n;i++){
    //cout<<abs(node[i-1].y-node[i].y)<<endl;
    edges.push_back(Edge(node[i-1].id,node[i].id,node[i].y-node[i-1].y));
    //edges.push_back(Edge(node[i].id,node[i-1].id,abs(node[i-1].y-node[i].y)));
  }

  cout<<kruskal(n,edges)<<endl;

  return 0;
}


Measured memory_bytes: 7536
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define rep(i, s, n) for (int i = s; i < n; i++)
#define rrep(i, s, n) for (int i = (n)-1; i >= (s); i--)
#define all(a) a.begin(),a.end()
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const long long MOD = 1000000007, INF = 1e17;
 
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)

template<class T>inline bool chmax(T& a,T b){if(a<b){a=b;return true;}return false;}
template<class T>inline bool chmin(T& a,T b){if(a>b){a=b;return true;}return false;}

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...));
}
template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}
template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
	for(auto &e:t) fill_v(e,v);
}
//******************************************************************************

struct UF{
	vector<int>par,sz;
	void init(int n){
		par.resize(n);
		sz.resize(n);
		for(int i=0;i<n;i++){
			par[i]=i;
			sz[i]=1;
		}
	}
	int find(int x){
		return x==par[x]?x:par[x]=find(par[x]);
	}
	void unite(int x,int y){
		x=find(x);y=find(y);
		if(x==y)return;
		sz[x]+=sz[y];
		par[y]=x;
	}
	bool same(int x,int y){
		return find(x)==find(y);
	}
	int size(int x){
		return sz[find(x)];
	}
};

signed main()
{
	//IOS();
	int N,M;
	cin>>N>>M;
	UF uf;
	uf.init(N);
	rep(i,0,M){
		int a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		uf.unite(a,b);
	}
	vector<int>used(N,0);
	int ans = 0;
	rep(i,0,N){
		if(used[uf.find(i)]==0){
			used[uf.find(i)]=1;
			ans++;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 2688
N,M = map(int,input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]
ans = False
for i in range(N-M+1):
    for j in range(N-M+1):
        flag = True
        for k in range(M):
            for l in range(M):
                if A[i+k][j+l]!=B[k][l]:
                    flag = False
                    break
            if not flag:
                break
        if flag:
            ans = True
            break
    if ans:
        break
print('Yes' if ans else 'No')

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

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

int h, w;
char s[15][15];
int pos[15];
bool can[15][15];
bool dp[1 << 12];

int main() {
	scanf("%d %d", &h, &w);
	rep(i, h) scanf("%s", s[i]);
	rep(i, h) pos[i] = i;
	srand(1278007);
	rep(tme, 300000) {
		rep(i, w) rep(j, w) {
			bool ok = 1;
			rep(k, h) if (s[pos[k]][i] != s[pos[h - 1 - k]][j]) {
				ok = 0; break;
			}
			can[i][j] = ok;
		}
		memset(dp, 0, sizeof(dp));
		dp[0] = 1;
		rep(mask, 1 << w) if (dp[mask]) {
			rep(i, w) if (!(mask >> i & 1)) {
				rep(j, w) if (i != j && !(mask >> j & 1)) {
					dp[mask | 1 << i | 1 << j] |= can[i][j];
				}
			}
		}
		if (w & 1) {
			rep(i, w) if (dp[((1 << w) - 1) ^ 1 << i] && can[i][i]) {
				puts("YES"); return 0;
			}
		} else {
			if (dp[(1 << w) - 1]) {
				puts("YES"); return 0;
			}
		}
		random_shuffle(pos, pos + h);
	}
	puts("NO");
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,cc,n) for(int i=cc;i<n;++i)
#define lrep(i,cc,n) for(long long i=cc;i<n;++i)
#define rrep(i,cc,n) for(long i=cc;i>n;--i)
using ll = long long;

int main() {
   vector<vector<int>> v(3, vector<int>(3));
   rep(i, 0, 3){
       rep(j, 0, 3){
           cin >> v[i][j];
       }
    }
    if(v[0][2]-v[0][1] == v[1][2]-v[1][1] && v[1][2]-v[1][1] == v[2][2]-v[2][1]){
        if(v[0][1]-v[0][0] == v[1][1]-v[1][0] && v[1][1]-v[1][0] == v[2][1]-v[2][0]){
             cout << "Yes" << endl;
             return 0;
        }
    }
    cout << "No" << endl;
}

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

int main() {
    int N;
    cin >> N;
    long long A[N], B[N];
    
    for (int i=0; i<N; i++){
        cin >> A[i];
        B[i] = A[i]-i-1;
    }
    sort(B, B+N);
    long long b = B[N/2];

    long long res=0;
    for (int i=0; i<N; i++){
        res += abs(B[i] - b);
    }
    
    cout << res << endl;
}


Measured memory_bytes: 3328
n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
import sys
input=sys.stdin.readline
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))


Measured memory_bytes: 282504
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Abc169C
    {
        public static void Main()
        {
            var ab = Console.ReadLine().Split(' ').ToArray();
            long a = long.Parse(ab[0]);
            long b = (long)(double.Parse(ab[1]) * 100 + 0.5);
            Console.WriteLine(a * b / 100);
        }
    }
}

Measured memory_bytes: 28020
h,w,a,b=map(int,input().split())
l=[[] for i in range(h)]
mode=True
for i in range(h):
  if i>=b:
    mode=False
  for j in range(w):
    if mode:
      if j<a:l[i].append("1")
      else:l[i].append("0")
    else:
      if j<a:l[i].append("0")
      else:l[i].append("1")
for li in l:
  print("".join(li))

Measured memory_bytes: 12788
#!/usr/bin/env python3
from collections import defaultdict, Counter
N, M = map(int, input().split())
edge = [[] for _ in range(N + 1)]
cnt_dict = defaultdict(int)

for _ in range(M):
    a, b = map(int, input().split())
    edge[a].append(b)
    cnt_dict[a] += 1
    edge[b].append(a)
    cnt_dict[b] += 1

ans = 0
while True:
    cnt = Counter(cnt_dict).most_common()
    if cnt[-1][1] > 1:
        break
    elif cnt[-1][1] == 1:
        ans += 1
        key = cnt[-1][0]
        cnt_dict[key] = float("inf")
        for i in range(1, N + 1):
            if key in set(edge[i]):
                cnt_dict[i] -= 1
                edge[i].remove(key)
    else:
        break
print(ans)

Measured memory_bytes: 3444