akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = (ll)1e9 + 7;

struct UF {
  vector<int> parent_, rank_;

  UF(int N) : parent_(N + 5), rank_(N + 5, 0) {
    for (int i = 0; i <= N; ++i) {
      parent_[i] = i;
    }
  }

  int find_set(int x) {
    if (parent_[x] != x) {
      parent_[x] = find_set(parent_[x]);
    }
    return parent_[x];
  }

  void unite(int x, int y) {
    int sx = find_set(x), sy = find_set(y);
    if (sx == sy) { return; }
    if (rank_[sx] > rank_[sy]) {
      parent_[sy] = sx;
    }
    else {
      parent_[sx] = sy;
      if (rank_[sx] == rank_[sy]) {
        ++rank_[sy];
      }
    }
  }

  bool is_connected(int x, int y) {
    return find_set(x) == find_set(y);
  }
};

int main()
{
  int N, K, L; scanf("%d %d %d", &N, &K, &L);
  UF uf1(N + 5), uf2(N + 5);
  int a, b;
  for (int i = 0; i < K; ++i) {
    scanf("%d %d", &a, &b);
    uf1.unite(a, b);
  }
  for (int i = 0; i < L; ++i) {
    scanf("%d %d", &a, &b);
    uf2.unite(a, b);
  }
  vector<int> road(N + 5), rail(N + 5);
  map<pair<int, int>, int> freqs;
  for (int i = 1; i <= N; ++i) {
    road[i] = uf1.find_set(i);
    rail[i] = uf2.find_set(i);
    ++freqs[make_pair(road[i], rail[i])];
  }

  for (int i = 1; i <= N; ++i) {
    pair<int, int> p = make_pair(road[i], rail[i]);
    int cnt = freqs[p];
    if (i == 1) { printf("%d", cnt); }
    else { printf(" %d", cnt); }
  }
  printf("\n");
  return 0;
}


Measured memory_bytes: 16640
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

int main(){

  long long inf=10000000000;

  int v,e;
  cin >> v >> e;

  long long dp[v][v];
  for(int i=0;i<v;i++){
    for(int j=0;j<v;j++){
      dp[i][j]=inf;
    }
  }

  for(int i=0;i<e;i++){
    long long s,t,d;
    cin >> s >> t >> d;
    dp[s][t]=d;
  }

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

  for(int k=0;k<v;k++){
    for(int i=0;i<v;i++){
      for(int j=0;j<v;j++){
        if(dp[i][k]==inf || dp[k][j]==inf);
        else dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
      }
    }
  }

  int a=0;
  for(int i=0;i<v;i++)if(dp[i][i]<0)a++;

  if(a!=0)cout << "NEGATIVE CYCLE" << endl;
  else{
    for(int i=0;i<v;i++){
      if(dp[i][0]==inf)cout << "INF" ;
      else cout << dp[i][0] ;
      for(int j=1;j<v;j++){
        if(dp[i][j]==inf)cout << " "<<"INF" ;
        else cout << " " <<dp[i][j]; 
      }
      cout << endl;
    }
  }




}



Measured memory_bytes: 3184
#include <stdio.h>
int main(void) {
    int h,m,s,S;
    scanf("%d",&S);
    h=S/3600;
    S=S%3600;
    m=S/60;
    s=S%60;
    printf("%d:%d:%d\n",h,m,s);
     
    return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define re register
#define ll long long
#define ull unsigned long long
#define rep(i,a,b) for(re int i=a;i<=b;++i)
#define per(i,a,b) for(re int i=a;i>=b;--i)
template<typename T>
inline void read(T&x)
{
	x=0;
	char s=(char)getchar();
	bool f=false;
	while(!(s>='0'&&s<='9'))
	{
		if(s=='-')
			f=true;
		s=(char)getchar();
	}
	while(s>='0'&&s<='9')
	{
		x=(x<<1)+(x<<3)+s-'0';
		s=(char)getchar();
	}
	if(f)
		x=(~x)+1;
}
template<typename T>
inline void clear(T*a,int l,int r,int val)
{
	memset(&a[l],val,sizeof(T)*(r-l+1));
}
signed main()
{
	int a,b;
	read(a),read(b);
	printf("%d\n",a*b);
	return 0;
}



Measured memory_bytes: 3728
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<map>
#include<algorithm>
#include<set>
#include <stdexcept>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
int ceil(int a,int b){
    return (a+b-1)/b;
}
int main(void){
   int n,l;
   cin>>n>>l;
   string s[n];
   rep(i,n){
       cin>>s[i];
   }
   rep(i,n){
       for(int j=n-1;j>i;j--){
           string copy;
           if(s[j]<s[j-1]){
               copy=s[j-1];
               s[j-1]=s[j];
               s[j]=copy;
           }
        }
    }
    rep(i,n) cout<<s[i];
    cout<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using i64 = int_fast64_t;
#define rep(i, N) for(int (i) = 0; (i) < (N); (i)++)
#define all(v) (v).begin(), (v).end()
#define eb emplace_back

int main(){
    int N;
    cin >> N;
    vector<i64> X(N);
    rep(i, N) cin >> X[i];

    i64 ans = 1e18; 
    for(i64 p = 1; p <= 100; p++) {
        i64 sum = 0;
        for(auto x : X){
            sum += abs(x - p) * abs(x - p);
        }
        ans = min(ans, sum);
    }

    cout << ans << endl;

}



Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
bool p[9]={0,0,0,0,0,0,0,0,0};
long long res=0;
string a;
int n;
long long turn(){
	long long num1=0,num2=a[0]-'0';
	for(int i=0;i<n-1;i++){
		if(p[i]==0){
//			cout<<i<<" "<<a[i+1]<<endl;
			num2=num2*10+a[i+1]-'0';
		}else{
			num1+=num2;
			num2=a[i+1]-'0';
		}
	}
	num1+=num2;
//	cout<<" "<<num1<<endl;
	return num1;
}
long long k(int i){
	if(i==0){
		for(int j=0;j<2;j++){
			p[i]=j;
			res+=turn();
		}
		return 0;
	}
	for(int j=0;j<2;j++){
		p[i]=j;
		k(i-1);
	}
	return 0;
}
int main(){
	cin>>a;
	n=a.size();
	if(n==1){
		cout<<a;
		return 0;
	}
	k(n-2);
	cout<<res;
//	cout<<turn();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main(){

    int n;
    vector<int> x;
    vector<int> y;
    vector<int> h;
    int min_h = 1000000001;

    cin >> n;

    for(int i = 0; i < n; i++){
        int tmpx,tmpy,tmph;
        cin >> tmpx >> tmpy >> tmph;
        
        x.push_back(tmpx);
        y.push_back(tmpy);
        h.push_back(tmph);

        min_h = min(min_h,tmph);
    }

    bool discovered = true;

    for(int i = 0; i < 101; i++){
        for(int j = 0; j < 101; j++){
            for(int k = min_h; k < min_h + 201; k++){
                for(int l = 0; l < n; l++){
                    if(h[l] != max(0,k - abs(x[l] - i) - abs(y[l] - j))){
                        discovered = false;
                        break;
                    }
                }

                if(discovered){
                    cout << i << " " <<  j << " " << k << endl;
                    return 0;
                }else{
                    discovered = true;
                }
            }
        }
    }
    return 0;
}

Measured memory_bytes: 256
H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L,reverse=True)
L.insert(0,[0,0])
m+=1
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0

for i in range(1,N+1):
    t=0
    DP[i][0]=0
    for j in range(H+1):
        DP[i][j]=min(DP[i][j],DP[i-1][j])
        t=min(DP[i][j],DP[i-1][j])+L[i][1]
        DP[i][j+L[i][0]]=min(DP[i][j+L[i][0]],t)
    DP[i][H]=min(DP[i][H:-1])
print(min(DP[N][H:-1]))



Measured memory_bytes: 134152
private val scanner = java.util.Scanner(System.`in`)

private fun readInts(n: Int) = Array(n) { scanner.nextInt() }
private fun readLongs(n: Int) = Array(n) { scanner.nextLong() }
private fun readLineInts() = readLine()!!.split(" ").map { it.toInt() }.toTypedArray()
private fun readLineLongs() = readLine()!!.split(" ").map { it.toLong() }.toTypedArray()

fun main(args: Array<String>) {
    val (N, H, W) = readLineInts()

    var count = 0
    for (i in 0 until N) {
        val (a, b) = readLineInts()

        if (a >= H && b >= W) ++count
    }

    println(count)
}

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

#define IDX(c) ( c - 'a' )

using namespace std;

int main ( void )
{
	bool key[26] = { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1 };

	string str;
	while ( cin >> str, str != "#" ) {
		int cnt = 0,
			prev = key[IDX( str[0] )];

		for ( int i = 0; i < str.size(); ++i ) {
			cnt += prev != key[IDX( str[i] )];
			prev = key[IDX( str[i] )];
		}

		cout << cnt << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
#define rep(i , n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9;
using namespace std;
using ll = long long;
#include <bits/stdc++.h>
int main() {
    int n , a;
    cin >> n >> a;
    cout << n * n - a << endl;
}


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

int main()
{
	int n,k,s;
	cin>>n>>k>>s;
	for(int i=0;i<k;i++)
		cout<<s<<' ';
	for(int i=k;i<n;i++)
		if(s==1e9)cout<<1<<' ';
		else cout<<s+1<<' '; 
	return 0;
}


Measured memory_bytes: 1280
n, x = map(int, input().split())
l_list = [int(i) for i in input().split()]

d_prev = 0
count = 1

for i in l_list:
    di1 = d_prev + i
    if di1 > x:
        break
    else:
        d_prev = di1
        count +=1

print(count)


Measured memory_bytes: 2940
#include<stdio.h>
int main(){
			int check[501]={0};
		int list[10001][2]={0};
	int n,m,i,j,a,b,ans=0;
	while(1){
		scanf("%d",&n);
		for(i=0;i<=n;i++){
			check[i]=0;
		}
		ans=0;
		check[1]=1;
		scanf("%d",&m);
		if(n==0&&m==0)break;
		for(i=0;i<m;i++){
			scanf("%d%d",&list[i][0],&list[i][1]);
			if(list[i][0]==1){
				ans++;
				check[list[i][1]]=1;
			}
			else if(list[i][1]==1){
				ans++;
				check[list[i][0]]=1;
			}
		}
		for(i=0;i<m;i++){
			if(check[list[i][0]]==1&&check[list[i][1]]==0){
				check[list[i][1]]=2;
				ans++;
			}
			else if(check[list[i][0]]==0&&check[list[i][1]]==1){
				check[list[i][0]]=2;
				ans++;
			}
		}
		/*		for(i=1;i<=n;i++){
			printf("%2d",check[i]);
		}*/
		//printf("\n");
		printf("%d\n",ans);
	}
}


Measured memory_bytes: 2064
var lines = [];
var readline = require('readline');

var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', function (x) {
    lines.push(x);
});

rl.on('close', function () {
    var MOD = Math.pow(10,9)+7;

    var N = lines[0];
    var S = lines[1].split("");
    var result = 1;
    var alphabet = Array(26).fill(0);

    for (var i = 0; i < N; i++) {
        var tmp = S[i].charCodeAt() -97;
        alphabet[tmp]++;
    }

    for (var i = 0; i < 26; i++) {
        result = result * (alphabet[i] + 1);
        result = result % MOD;
    }
    console.log(result - 1);
});

Measured memory_bytes: 22600
def solve(N, Y):
    # 全探索
    for gosen in range(0, N + 1):
        for man in range(0, N - gosen + 1):
            sen = N - gosen - man
            if man * 10000 + gosen * 5000 + sen * 1000 == Y:
                return man, gosen, sen
    return -1, -1, -1


N, Y = map(int, input().split())
man, gosen, sen = solve(N, Y)
print(int(man), int(gosen), int(sen))

Measured memory_bytes: 3064
#include<stdio.h>
int main(){
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c)!=EOF){
        if(a==b)
            printf("%d\n",c);
        else if(a==c)
            printf("%d\n",b);
        else if(b==c)
            printf("%d\n",a);

    }
    return 0;
}


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

int ans=0;
long n;

void check(long x){
  if(x>n){
    return ;
  }
  vector<int> l(10,0);
  long y=x;
  while(y!=0){
    l.at(y%10)++;
    y/=10;
  }
  if(l.at(3)!=0&&l.at(5)!=0&&l.at(7)!=0){
    ans++;
  }
}
      
  

void dfs(long x){
  check(x);
  if(x<=1000000000){
    dfs(10*x+3);
    dfs(10*x+5);
    dfs(10*x+7);
  }
}

int main() {
  cin >> n;
  dfs(0);
  cout <<ans;
  
}

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

class Main{
    public static void main(String[] args) throws IOException {
        
        BufferedReader r = 
        new BufferedReader(new InputStreamReader(System.in));
        
        int[] a;
        a = new int[10];
        for (int i = 0; i < 10; i++){
            String s = r.readLine();
            a[i] = Integer.valueOf(s);
        }
        Arrays.sort(a);
        for (int i = 9; i >6; i--){
            System.out.println(a[i]);
        }            
    }
}

Measured memory_bytes: 16996
import itertools

N, K = list(map(int, input().split()))

mans = []
for i in range(1, N+1):
    mans.append(i)

hasmans=[]
for ii in range(K):
    d = int(input())
    hasmans.append(list(map(int, input().split())))

hasmans = itertools.chain.from_iterable(hasmans)

print(len(list(set(mans) - set(hasmans))))

Measured memory_bytes: 9160
package main

import (
	"fmt"
	"math"
)

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

	var min float64 = 1000000000
	var p int
	for i := 1; i <= n; i++ {
		var num int
		fmt.Scan(&num)
		var result = math.Abs(float64(t) - float64(num)*0.006 - float64(a))
		if result < min {
			min = result
			p = i
		}
	}

	fmt.Println(p)
}


Measured memory_bytes: 512
// #define DEBUGGING
#include <bits/stdc++.h>
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
// namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif
using namespace std;

V<TLL> ans;

bool solve() {
    ll N, K;
    cin >> N >> K;
    V<pair<ll, PLL>> AB;
    V<ll> C(N);
    auto push_ab = [&](ll a, ll b) { AB.emplace_back(a + b, PLL(a, b)); };
    iota(ALL(C), K + 2 * N);
    ll l1 = K, l2 = K + N;
    ll r1 = K + N - 1, r2 = K + 2 * N - 1;
    if(N % 2 == 0) {
        push_ab(l1, r2);
        l1++;
        r2--;
    }

    ll len = r2 - l2 + 1;
    ll cur1 = l1 + len / 2;
    ll cur2 = r2;
    while(l2 <= cur2) {
        if(cur1 < l1) cur1 = r1;
        push_ab(cur1, cur2);
        cur1--;
        cur2--;
    }

    sort(ALL(AB));
    for(ll i = 0; i < N; i++) {
        ll ab = AB[i].first;
        ll a, b;
        tie(a, b) = AB[i].second;
        if(ab > C[i]) return false;
        ans.emplace_back(a, b, C[i]);
    }

    return true;
}

int main() {
    bool ok = solve();
    if(ok) {
        for(auto &&ele : ans) {
            ll a, b, c;
            tie(a, b, c) = ele;
            cout << a << ' ' << b << ' ' << c << endl;
        }
    } else {
        cout << -1 << endl;
    }
    return 0;
}


Measured memory_bytes: 9456
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

const int maxn = 22;
const int maxm = 151111;
double dp[maxn][maxm];
int a[maxn];

double rat (int x, int y) {
	return 1.0 * abs (x - y) / x;
}

int main () {
	int n, i, j, k;
	double ans, Min;
	while (~scanf ("%d", &n)) {
		for (i = 1; i <= n; ++i) scanf ("%d", &a[i]);
		memset (dp, 0x7f, sizeof (dp));
		for (i = 1; i < maxm; ++i) {
			dp[1][i] = rat(a[1], i);
		}
		for (i = 2; i <= n; ++i) {
			//Min = dp[0][0];
			for (j = 1; j < maxm; ++j) {
				for (k = 1; k * j < maxm; ++k) {
					dp[i][k * j] = min (dp[i][k * j], max(dp[i-1][j], rat (a[i], k * j)));
					//printf ("%lf %lf %lf\n", dp[i][k * j], dp[i-1][j], rat (a[i], k * j));
					//Min = min (Min, dp[i][k * j]);
				}
			}
			//printf ("Min: %lf\n", Min);
		}
		ans = dp[n][1];
		for (j = 1; j < maxm; ++j) {
			ans = min (ans, dp[n][j]);
		}
		printf ("%.12lf\n", ans);
	}
	return 0;
}

Measured memory_bytes: 26000
#include<iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<climits>
#include<algorithm>
using namespace std;

int main(void)
{
	int N, K;
	cin >> N >> K;

	vector<int> x(N);
	for(int i=0; i<N; i++)
		cin >> x[i];

	int ret = INT_MAX;
	int left = lower_bound(x.begin(), x.end(), 0) - x.begin();
	int right = N - left;
	for(int i=0; i<=K; i++){
		int l, r, t;
		l = i;
		r = K - l;
		if(l > left || r > right)
			continue;

		// lrr
		t = 0;
		if(l != 0)
			t += abs(x[left-l]) * 2;
		if(r != 0)
			t += x[left + r - 1];
		ret = min(ret, t);

		// rll
		t = 0;
		if(r != 0)
			t += x[left + r - 1] * 2;
		if(l != 0)
			t += abs(x[left-l]);
		ret = min(ret, t);
		
	}

	cout << ret << endl;

	return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
int n,m,res;
vector < int > adj[10];
bool V[10];
void dfs(int ver,int cnt){
	if(cnt==n){
		res++;
		return;
	}
	int xb;
	for(xb=0;xb<adj[ver].size();xb++){
		if(!V[adj[ver][xb]]){
			V[adj[ver][xb]]=1;
			dfs(adj[ver][xb],cnt+1);
			V[adj[ver][xb]]=0;
		}
	}
}
int main(){
	cin>>n>>m;
	int xb,x2,a,b;
	for(xb=0;xb<m;xb++){
		cin>>a>>b;
		a--;b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
	V[0]=1;
	dfs(0,1);
	cout<<res;
	return 0;
}

Measured memory_bytes: 256
N=int(input())
d={}
l=map(int,input().split())
for i in l:
  if not i in d:
    d[i]=1
  else:
    d[i]+=1
cnt=0
for i in d.items():
  if i[0]>i[1]:
    cnt+=i[1]
  elif i[0]<i[1]:
    cnt+=i[1]-i[0]
print(cnt)


Measured memory_bytes: 23284
#include <iostream>
using namespace std;
int N, K;
int GCD(int a, int b)
{
    int r = a % b;
    while(r != 0)
    {
        a = b;
        b = r;
        r = a % b;
    }
    return b;
}

void Read()
{
    int Max = 0;
    cin >> N >> K;
    int gcd;
    for(int i = 1; i <= N; i++)
    {
        int x;
        cin >> x;
        if(i == 1)
            gcd = x;
        else
            gcd = GCD(gcd, x);
        Max = max(Max, x);
    }
    if(Max < K || K % gcd != 0)
        cout << "IMPOSSIBLE\n";
    else
        cout << "POSSIBLE\n";
}
int main()
{
    Read();
    return 0;
}


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

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;

int main(void) {
  int scan; // scanf result
  int n; // to input 
  int m; // to input 
  int *a;
  int all;
  int result;

  scan = scanf("%d", &n);
  scan = scanf("%d", &m);
  a = (int *)malloc(sizeof(int) * (n + 1));
  for (int i=0; i<n; i++) {
    scan = scanf("%d", &a[i]);
  }

  all = 0;
  for (int i=0; i<n; i++) {
    all += a[i];
  }

  result = 0;
  for (int k=0; k<n; k++) {
    if ((a[k] * 4 * m) >= all)
      result += 1;
  }

  if (result >= m)
    printf("Yes");
  else
    printf("No");

  return (0);
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, k; cin >> n >> k;
  V<> a(n); for (int i = 0; i < n; ++i) cin >> a[i];
  sort(begin(a), end(a));
  int res = 2e9;
  for (int i = 0; i + k - 1 < n; ++i) {
    res = min(res, a[i + k - 1] - a[i]);
  }
  cout << res << '\n';
}

Measured memory_bytes: 640
# coding: utf-8
# 日本語を入力できるようにするために上記一文が必要

x = int(input())
remainder_list = []
alphabet_list = "a b c d e f g h i j k l m n o p q r s t u v w x y z".split()
if x <= 26:
        remainder_0 = x
        remainder_list.append(remainder_0)
else:
        while x / 26 > 0:
                remainder = x % 26
                if remainder == 0:
                        remainder = 26
                        remainder_list.append(remainder)
                        x = x // 26 - 1
                else:
                        remainder_list.append( remainder)
                        x = x // 26

remainder_list.reverse()
ans =""
for i in remainder_list:
        ans += alphabet_list[i-1]
print(ans)

Measured memory_bytes: 9052
#include <bits/stdc++.h>
#define ll long long
#define f(i, a, b) for(ll i = a; i <= b; ++i)
#define ff(i, a, b) for(ll i = a; i < b; ++i)
#define F(i, a, b) for(ll i = a; i >= b; --i)
#define FF(i, a, b) for(ll i = a; i > b; --i)
#define x first
#define y second
#define X real()
#define Y imag()
using namespace std;
typedef complex<ll> P;
typedef pair<ll, ll> ii;
typedef tuple<ll, ll, ll> iii;

const ll N = 1e3+7;
ll n, num = 0, f[2], d[35];
ii a[N];

void solve(ll x, ll y){
	cout<<"\n";
	f(i,1,num){
		if(abs(x) > abs(y)){
			if(x > 0) cout <<"R", x-=d[i];
			else cout <<"L", x+=d[i];
		}else{
			if(y > 0) cout <<"U", y-=d[i];
			else cout <<"D", y+=d[i];
		}
	}
}

signed main(){
//	freopen("PERFECT1.inp","r",stdin);
//	freopen("PERFECT1.out","w",stdout);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	f(i,1,n){
		cin >> a[i].x >> a[i].y;
		f[(a[i].x+a[i].y)%2] ++;
	}
	if(f[0]&&f[1]){
		cout <<"-1";
		return 0;
	}
	F(i,30,0) d[++num] = (1<<i);
	if(f[0]) d[++num] = 1;
	cout << num <<"\n";
	f(i,1,num) cout << d[i] <<" ";
	f(i,1,n) solve(a[i].x, a[i].y);
}


Measured memory_bytes: 256
import java.lang.reflect.Array;
import java.util.*;

/**
 * Created by Santa.
 */
public class Main {

  static int N;
  static int K;
  static long Q;
  static int A;
  static int B;
  static long C;
  static double min = 9999999;
  static long ans = 0;

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    int[] map = new int[5];

//    int A = scanner.nextInt();
//    int B = scanner.nextInt();
//    int C = scanner.nextInt();
//    int D = scanner.nextInt();
//    int E = scanner.nextInt();

    for (int i = 0; i < 5; i++) {

      map[i] = scanner.nextInt();
    }
    int ans = 0;
    int min = 10;
    for (int i = 0; i < 5; i++) {
      if(map[i] % 10 != 0){
        min = Math.min(min,map[i] % 10);
        ans += map[i] / 10 + 1;
      }else{
        ans += map[i] / 10;
      }

    }

    System.out.println(ans * 10 - 10 + min);







  }


}


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

int main(){
    int n;
    cin >> n;
    int pt1=0,pt2=0;
    while(n--){
        string a,b;
        cin >> a >> b;
        if(a>b) pt1+=3;
        else if(a<b) pt2+=3;
        else{
            pt1++;
            pt2++;
        }
    }
    cout << pt1 << " " << pt2 << endl;
    return 0;
}


Measured memory_bytes: 3228
// guruguru
// * frank_c1
// * 2017 / 11/ 07

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn = (int)(1e5) + 5;
LL D[maxn], U[maxn];
int a[maxn];

int main() {
	int n, m, dt = 0; LL ret = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]); --a[i];
		if (i > 1) {
			int u = a[i - 1], v = a[i]; 
			if (u > v) ret += v + 1, dt++; else ret += (v + m - u) % m;
			D[(u + 1) % m]++; D[(v + 1) % m]--; U[(v + 1) % m] += (v + m - u) % m;
		}
	} LL mi = ret; 
	for (int i = 1; i < m; ++i) {
		ret += U[i]; ret -= dt; dt += D[i]; mi = min(mi, ret); 
	}
	return printf("%lld\n", mi), 0;
}

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

//sort(v.rbegin(), v.rend(), [](auto& x, auto& y){return x[1] < y[1];});
typedef long long ll;


int main(){
    ll N,M,A,b=0,r=0;
    cin >> N >> M;

    map<ll, ll> v;

    for (int i=0;i<N;++i){
        cin >> A;
        b=(A + b)%M;
        v[b];
        v[b]+=1;
    }

    for (auto x = v.begin();x != v.end();++x){
        if (x->first==0) r += x->second;
        r += x->second*(x->second-1)/2;
    }
    
    cout << r << endl;


}

Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair< ll, ll > Pi;
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep2(i,n) for(int i=1;i<=(n);i++)
#define rep3(i,i0,n) for(int i=i0;i<(n);i++)
#define pb push_back
#define mod 1000000007
const ll INF = 1LL << 60;
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; }
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}
#define all(x) x.begin(), x.end()
#define mp make_pair
bool compare(Pi a, Pi b) {
    if(a.first != b.first){
        return a.first < b.first;
        
    }else{
        return a.second < b.second;
    }
}

bool compareg(Pi a, Pi b) {
    if(a.second != b.second){
        return a.second > b.second;
        
    }else{
        return a.first > b.first;
    }
}


bool In_map(ll y,ll x,ll h,ll w){
    if(y<0 || x<0 || y>=h || x>=w){
        return 0;
    }else{
        return 1;
    }
}
const vector<ll> dx{1,0,-1,0};
const vector<ll> dy{0,1,0,-1};



int main() {
    ll N;
    cin>>N;
    vector<Pi>ab(N);
    vector<Pi>cd(N);
    rep(i,N){
        ll a,b;
        cin>>a>>b;
        ab[i] = mp(a,b);
    }

    rep(i,N){
        ll a,b;
        cin>>a>>b;
        cd[i] = mp(a,b);
    }

    sort(all(ab),compareg);
    sort(all(cd),compare);

    ll ans = 0;
    rep(i,N){
        rep(j,N){
            if(ab[i].first < cd[j].first && ab[i].second <cd[j].second){
                ab[i].first = INF;
                cd[j].first = -INF;
                //cout<<i<<" "<<j<<endl;
                ans++;
                break;
            }
        }
    }

    cout << ans<<endl;
    return 0;
    

}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
using loop = int;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(loop (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(loop (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(loop (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(loop (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause") //comment out this on AOJ.
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
constexpr ld pi = 3.1415926535897932;
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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    int n, m; cin >> n >> m;
    VI a(n), b(n), c(m), d(m);
    FOR(i, 0, n)cin >> a[i] >> b[i];
    FOR(i, 0, m)cin >> c[i] >> d[i];

    FOR(i, 0, n) {
        int num = -1, dis = INF;
        FOR(j, 0, m) {
            if (chmin(dis, abs(a[i] - c[j]) + abs(b[i] - d[j]))) {
                num = j + 1;
            }
        }
        cout << num << "\n";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
int a[3][107];
int f[3][107];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=2;i++)
		for (int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	f[1][1]=a[1][1];
	for (int i=1;i<=2;i++)
		for (int j=1;j<=n;j++)
			if (i!=1||j!=1)
			{
				if (i>1) f[i][j]=max(f[i][j],f[i-1][j]+a[i][j]);
				if (j>1) f[i][j]=max(f[i][j],f[i][j-1]+a[i][j]);
			}
	printf("%d\n",f[2][n]);
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
const int N=405;
const int MOD=998244353;
int n;
int a[N],b[N];
long long ksm(long long a,long long b)
{
	long long res=1;
	while(b)
	{
		if(b&1) res=res*a%MOD;
		a=a*a%MOD,b>>=1;
	}
	return res;
}
long long fac[N];
void init(int n=400)
{
	fac[0]=1;
	for(int i=1;i<=n;i++)
		fac[i]=fac[i-1]*i%MOD;
	return;
}
long long q[N][N][N];
int sa,sb;
long long c[N][N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i],&b[i]),sa+=a[i],sb+=b[i];
	init();
	q[0][0][0]=1;
	for(int i=1;i<=n;i++)
	{
		long long p=a[i]*ksm(sa,MOD-2)%MOD,fac=MOD-1;
		for(int l=0;l<b[i];l++,fac=fac*ksm(l,MOD-2)%MOD*p%MOD)
			for(int j=0;j<=sa;j++)
				for(int k=l;k<=sb;k++)
					q[i][j][k]=(q[i][j][k]+fac*q[i-1][j][k-l]%MOD)%MOD;
		for(int j=a[i];j<=sa;j++)
			for(int k=0;k<=sb;k++)
				q[i][j][k]=(q[i][j][k]+q[i-1][j-a[i]][k])%MOD;
	}
	for(int i=0;i<=sa;i++)
		for(int j=0;j<=sb;j++)
			c[i][j]=(-q[n][i][j]+MOD)%MOD;
	c[sa][0]=(c[sa][0]+1)%MOD;
	long long ans=0;
	for(int i=0;i<=sa;i++)
		for(int j=0;j<=sb;j++)
		{
			long long p=i*ksm(sa,MOD-2)%MOD;
			long long f=ksm(ksm((1-p+MOD)%MOD,MOD-2),j+1)*fac[j]%MOD;
			ans=(ans+c[i][j]*f%MOD)%MOD;
		}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 513948
n = int(input())
t = list(map(int,input().split()))
m = int(input())
px = [0]*m

for i in range(0,m):
  px[i] = input().split()
  
x = []
#print(px)
tmp = [0]*m

for i in range(0,m):
  tmp = t[:]
  #temp = t[int(px[i][0])-1]
  tmp[int(px[i][0])-1] = int(px[i][1])
  #print(tmp)
  #t[int(px[i][0])-1] = temp
  x.append(sum(tmp))
  
#print(x)

for i in x:
  print(i)


Measured memory_bytes: 38384
#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

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

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

namespace io{
	const int L = (1 << 20) + 1;
	
	char buf[L], *S , *T, c;
	 
	char getchar() {
		if(__builtin_expect(S == T, 0)) {
			T = (S = buf) + fread(buf, 1, L, stdin);
			return (S == T ? EOF : *S++);
		}
		return *S++;
	}
	
	int inp() {
		int x = 0, f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	unsigned inpu()
	{
		unsigned x = 0; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar());
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x;
	}
	
	ll inp_ll() {
		ll x = 0; int f = 1; char ch;
		for(ch = getchar(); !isdigit(ch); ch = getchar())
			if(ch == '-') f = -1;
		for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
		return x * f;
	}
	
	char B[25], *outs=B+20, *outr=B+20;
	template<class T>
	inline void print(register T a,register char x=0){
		if(x) *--outs = x, x = 0;
		
		if(!a)*--outs = '0';
		else 
			while(a)
				*--outs = (a % 10) + 48, a /= 10;
		
		if(x)
			*--outs = x;
		
		fwrite(outs, outr - outs , 1, stdout);
		outs = outr;
	}
};

using io :: print;
using io :: inp;
using io :: inpu;
using io :: inp_ll;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

const int MAXN = 510;
const int MOD = 998244353;
const int INF = 1000000010;

int a[MAXN][MAXN];

vector<tuple<int, int, int, int> > ans;

void add(int x1, int y1, int x2, int y2)
{
	a[x1][y1] --;
	a[x2][y2] ++;
	ans.emplace_back(x1, y1, x2, y2);
}

int main()
{
	
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
			cin >> a[i][j];
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= m; ++ j)
		{
			if (a[i][j]%2 == 1)
			{
				if (j < m)
					add(i, j, i, j+1);
				else if (i < n)
					add(i, j, i+1, j);
			}
		}
	cout << ans.size() << endl;
	for (auto p : ans)
	{
		int a, b, c, d;
		tie(a, b, c, d) = p;
		printf("%d %d %d %d\n", a, b, c, d);
	}
	
	return 0;
}


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

int main() {
    int n, k;
    int l[60];
    cin >> n >> k;
    for(int i = 0; i < n; ++i) cin >> l[i];
    
    sort(l, l + n, greater<int>());
    
    int ans = 0;
    for(int i = 0; i < k; ++i) ans += l[i];
    
    cout << ans << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO.Compression;
using System.IO.Pipes;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            var R = ReadInt();

            WriteLine(2 * R * PI);
        }

        private static string Read() { return ReadLine(); }
        private static string[] Reads() { return (Read().Split()); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }
    }
}


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

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

Node treeMinimum(Node x){
  while(x->left != NIL){
    x = x->left;
  }
  return x;
}

Node treeMaximum(Node x){
  while(x->right != NIL){
    x = x->right;
  }
  return x;
}

Node treeSearch(Node u, int k){
  if(u==NIL || k==u->key) return u;
  if(k < u->key) return treeSearch(u->left,k);
  else  return treeSearch(u->right,k);
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);
  y = x->parent;
  while(y!=NIL && x==y->right){
    x = y;
    y = y->parent;
  }
    return y;
  
}

void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y
  
  if(z->left == NIL || z->right == NIL) y=z;
  else y=treeSuccessor(z);
  if(y->left != NIL) x=y->right;
  else x=y->right;
  if(x != NIL) x->parent=y->parent;
  if(y->parent == NIL) root=x;
  else if(y == y->parent->left) y->parent->left=x;
  else y->parent->right=x;
  if(y != z) z->key=y->key;
}

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  
  while(x != NIL){
    y=x;
    if(z->key < x->key) x=x->left;
    else x=x->right;
  }
    z->parent=y;
    if(y == NIL) root = z;
    else if(z->key < y->key) y->left=z;
    else y->right=z;
  
}

void inorder(Node u){
  if(u != NIL){
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
  }  
}
  
void preorder(Node u){
  if(u != NIL){
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
  }
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}



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

public class Main {
    public static void main(String[] str) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for (int i=0;i<N;i++) arr[i] = scan.nextInt();

        Arrays.sort(arr);
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i: arr) {
            max = Math.max(max, i);
            min = Math.min(min, i);
        }

        int mincost = Integer.MAX_VALUE;
        for (int i=min;i<=max;i++) {
            int total = 0;
            for (int j: arr) total += (i - j) * (i - j);
            if (total > mincost) break;
            mincost = total;
        }
        System.out.println(mincost);
    }
}


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

using namespace std;

int a[111];

int main(){
   // freopen("input.txt", "r", stdin);
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%d", a + i);
    }
    int ans = 0;
    for (int i = 1; i <= 10000; i++){
        bool flag = false;
        for (int j = 0; j < n; j++){
            if (a[j] > 0) {
                a[j]--;
                flag = true;
            }
            else {
                if (flag){
                    break;
                }
            }
        }
        if (flag)
            ans++;
    }
    printf("%d\n", ans);
    return 0;
}


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

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

struct Edge{
    int to,weight;
    Edge(int t,int w) : to(t), weight(w){}
};

using Edges = vector<Edge>;
using Graph = vector<Edges>;

class Tree{
    public:
        Tree(int size) : mGraph(size), mMemo(size) {}
        void add_edge(int s, int t, int w = 1){
            mGraph[s].emplace_back(t,w);
            mGraph[t].emplace_back(s,w);
        }

        // diameter of a tree
        pair<int,int> dfs(int v, int pv){
            pair<int,int> ret(0,v);
            for(Edge nv : mGraph[v]){
                if(nv.to == pv) continue;
                pair<int,int> tmp = dfs(nv.to,v);
                if(chmax(ret.first,tmp.first + nv.weight)){
                    ret.second = tmp.second;
                }
            }
            return ret;
        }

        int diameter(){
            pair<int,int> s = dfs(0,-1);
            pair<int,int> t = dfs(s.second,-1);
            return t.first;
        }
        //

        // height of a tree
        int dfs_memo(int v,int e){
            if(mMemo[v][e].weight >= 0) return mMemo[v][e].weight;
            mMemo[v][e].weight = mGraph[v][e].weight;
            int nv = mMemo[v][e].to;
            for(int ne = 0; ne < mMemo[nv].size(); ++ne){
                if(mMemo[nv][ne].to == v) continue;
                mMemo[v][e].weight = max(mMemo[v][e].weight, dfs_memo(nv,ne) + mGraph[v][e].weight);
            }
            return mMemo[v][e].weight;
        }

        vector<int> height(){
            mMemo = mGraph;
            // init memo
            for(int i = 0; i < mMemo.size(); ++i){
                for(int j = 0; j < mMemo[i].size(); ++j){
                    mMemo[i][j].weight = -1;
                }
            }
            //
            for(int i = 0; i < mMemo.size(); ++i){
                for(int j = 0; j < mMemo[i].size(); ++j){
                    if(mMemo[i][j].weight < 0){
                        mMemo[i][j].weight = dfs_memo(i,j);
                    }
                }
            }

           // calc result
           vector<int> ret(mMemo.size());
           for(int i = 0; i < mMemo.size(); ++i){
               for(int j = 0; j < mMemo[i].size(); ++j){
                   ret[i] = max(ret[i],mMemo[i][j].weight);
               }
           }
           return ret;
        }

    private:
        Graph mGraph;
        Graph mMemo;
};

int main(){
    int n,s,t,w;
    cin >> n;
    Tree tree(n);
    for(int i = 0; i < n-1; ++i){
        cin >> s >> t >> w;
        tree.add_edge(s,t,w);
    }
    auto ret = tree.height();
    for(int r : ret) cout << r << '\n';
    return 0;
}


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

using lint = long long int;
using pint = pair<int, int>;
using plint = pair<lint, lint>;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)

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

    cout << n*n <<"\n";

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define MAX 100005
#define OUT -1
struct Node{
  int p;
  int l;
  int r;
};
 
void depth(int,int);
void print(int);
//using namespace std;
 
struct Node T[MAX];
int n, A[MAX];
 
int main(){
  int i,j,d,v,c,l,r;
  scanf("%d",&n);
  for(i = 0; i < n; i++){
    T[i].r = OUT;
    T[i].l = T[i].r;
    T[i].p = T[i].l;
  }
  for(i = 0; i < n; i++){
    scanf("%d",&v);
    scanf("%d",&d);
    for(j = 0; j < d; j++){
      scanf("%d",&c);
    if(j == 0){
      T[v].l = c;
    }
    else{
      T[l].r = c;
    }
    l = c;
    T[c].p = v;
    }
  }
  for(i = 0; i < n; i++){
    if(T[i].p == OUT){
      r = i;
    }
  }
  depth(r,0);
  for(i = 0; i < n; i++){
    print(i);
  }
  return 0;
}// end of main func
 
void depth(int u, int p){
  A[u] = p;
  if(T[u].r != OUT){
    depth(T[u].r,p);
  }
  if(T[u].l != OUT){
    depth(T[u].l , p+1);
  }
}//end of depth func
 
void print(int u){
int i,c;
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].p);
  printf("depth = %d, ",A[u]);
  if(T[u].p == OUT){
    printf("root, ");
  }
  else if(T[u].l == OUT){
    printf("leaf, ");
  }
  else{
    printf("internal node, ");
  }
  printf("[");
  for(i = 0, c = T[u].l; c != OUT; i++, c = T[c].r){
    if(0 < i){
      printf(", ");
    }
    printf("%d",c);
  }
  printf("]\n");
}//end of print func

Measured memory_bytes: 6396
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)
#define REPIT(i,x) for(auto i{(x).begin()}; i != (x).end(); i++) 

#define PB push_back
#define MP make_pair
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef double dbl;
typedef vector<bool> Vb;
typedef vector<char> Vc;
typedef vector<double> Vd;
typedef vector<int> Vi;
typedef vector<ll> Vl;
typedef vector<string> Vs;
typedef vector<vector<int>> VVi;
typedef vector<vector<ll>> VVl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }
inline void YES() { cout << "YES" << endl; } inline void Yes() { cout << "Yes" << endl; }
inline void NO() { cout << "NO" << endl; } inline void No() { cout << "No" << endl; }

const int inf = 1 << 30;
const ll linf = 1LL << 60;
const int MOD = 1000000007;

VVi vx;
int n, d;

int main()
{
	cin >> n >> d;
	vx.resize(n, Vi(d));

	REP(i, n)
		REP(j, d)
		cin >> vx[i][j];

	int ans = 0;
	REP(i, n -1)
		for (int j = i + 1; j < n; ++j)
		{
			int sq = 0;
			REP(k, d)
				sq += (vx[i][k] - vx[j][k]) * (vx[i][k] - vx[j][k]);

			int rt = (int)sqrt(sq);

			if (sq == rt * rt)
				++ans;
		}

	cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n;
long long dfs(long long  i){
  if(i==1)
    return 1;
  else if(i==0)
    return 0;
  return i*dfs(i-1);
}
  int main(){  
  cin>>n;
  cout<<dfs(n)<<endl;
  return 0;
  
}

Measured memory_bytes: 3012
#include<stdio.h>
#include<stdlib.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)

ll a[20010];
ll b[20010];
main(){
	int n;
	scanf("%d",&n);
	rep(i,0,n){
		int t;
		scanf("%d",&t);
		a[--t]=i+1;
	}
	rep(i,1,n){
		if(a[i]<=a[i-1]){
			b[i]-=(a[i-1]+1)-a[i];
			a[i]+=(a[i-1]+1)-a[i];
		}
		if(b[i]>=b[i-1]){
			a[i]+=b[i]-(b[i-1]-1);
			b[i]-=b[i]-(b[i-1]-1);
		}
	}
	
	rep(i,0,n)printf("%lld%c",a[i],i==n-1?'\n':' ');
	rep(i,0,n)printf("%lld%c",b[i]-b[n-1]+1,i==n-1?'\n':' ');
	return 0;
}

Measured memory_bytes: 768
#include<iostream>
#include<string>
using namespace std ;
using str = string ;

void print(str s,int a,int b){
    for(int i=a;i<=b;i++) cout << s.at(i) ;
    cout << endl ;
}

void rev(str &s,int a,int b){
    str t ;
    for(int i=a;i<=b;i++){
        t += s.at(i) ;
    }
    for(int i=a;i<=b;i++){
        s.at(i) = t.at(b-i) ;
    }
}

void rep(str &s,int a,int b,str u){
    for(int i=a;i<=b;i++) s.at(i) = u.at(i-a) ;
}

int main(){
    str s ; cin >> s ;
    int n ; cin >> n ;
    str t,u ; int a,b ; 
    for(int i=0;i<n;i++){
        cin >> t >> a >> b ;
        if(t=="print") print(s,a,b) ;
        else if(t=="reverse") rev(s,a,b) ;
        else{
            cin >> u ;
            rep(s,a,b,u) ;
        }
    }
}


Measured memory_bytes: 3208
#include <stdio.h>

int main(void) {
	int a[9],i,j,c=0;
	for(i=0;i<9;i++){
		scanf("%d",&a[i]);
	}
	int n;
	scanf("%d",&n);
	int b[n];
	for(i=0;i<n;i++){
		scanf("%d",&b[i]);
		for(j=0;j<9;j++){
			if(a[j]==b[i])a[j]=0;
		}
	}
	for(i=0;i<7;i+=3){
		if(a[i]==a[i+1]&&a[i]==a[i+2])c=1;
	}
	for(i=0;i<3;i++){
		if(a[i]==a[i+3]&&a[i]==a[i+6])c=1;
	}
	if(a[0]==a[4]&&a[0]==a[8])c=1;
	if(a[2]==a[4]&&a[2]==a[6])c=1;
	
	if(c==1)printf("Yes");else printf("No");
	

	// your code goes here
	return 0;
}



Measured memory_bytes: 128