akhauriyash/Code-Regression huggingface dataset:
//%std
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N = 17, mod = 1e9 + 7;
void upd(int&a, int b) { a = (a + b) % mod; }
int fpow (int base, int v) {
	int tot = 1;
	for(; v; v >>= 1, base = 1LL * base * base % mod) if (v & 1) tot = 1LL * tot * base % mod;
	return tot;
}
int n, m, a[N], f[N][1 << N], fac[200004], invfac[200004], t, c[1 << N];
int C(int x, int y) { if (x < y) return 0; return 1LL * fac[x] * invfac[y] % mod * invfac[x - y] % mod; }
int main ()
{
	fac[0] = 1; rep(i, 1, 200000) fac[i] = 1LL * fac[i - 1] * i % mod;
	invfac[200000] = fpow(fac[200000], mod - 2);
	per(i, 199999, 0) invfac[i] = 1LL * invfac[i + 1] * (i + 1) % mod;
	scanf("%d%d", &n, &m); t = 1 << n;
	rep(i, 1, m) scanf("%d", &a[i]);
	sort (a + 1, a + m + 1, [](int x, int y) { return x > y; });
	f[0][0] = 1;
	rep(i, 1, m) per(S, (1 << n) - 1, 0) {
		upd(f[i][S], f[i - 1][S]);
		rep(k, 0, n - 1) if ((S >> k) & 1) {
			if (!f[i - 1][S ^ (1 << k)]) continue;
			upd(f[i][S], 1LL * f[i - 1][S ^ (1 << k)] * C(t - a[i] - (S ^ (1 << k)), (1 << k) - 1) % mod);
		}
	}
	c[0] = 1; rep(i, 1, (1 << n)) c[i] = c[i >> 1] * ((i & 1) ? -1 : 1);
	int ans = 0;
	rep(i, 0, (1 << n) - 1) {
		if (!f[m][i]) continue;
		int tot = t - 1 - i;
		rep(j, 0, n - 1) if (!(i & (1 << j))) f[m][i] = 1LL * f[m][i] * C(tot, 1 << j) % mod, tot -= (1 << j);
		upd(ans, 1LL * f[m][i] * (mod + c[i]) % mod);
	}
	rep (i, 0, n - 1) ans = 1LL * ans * fac[1 << i] % mod;
	printf ("%d\n", 1LL * ans * (1 << n) % mod);
	return 0;
}













Measured memory_bytes: 10496
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h1, m1, h2, m2, k;
    cin >> h1 >> m1 >> h2 >> m2 >> k;
    int sta = 60 * h1 + m1;
    int end = 60 * h2 + m2;
    int thr = end - k;
    int ans = thr - sta;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
// please, read the question correctly (do you need set or multiset)???
const int N=200010; //check the limits, dummy
int a[N];
int n, m, k;
bool fn(int x){
	int kk=k;
	for(int i=0; i<n; ++i){
		int tmp=(a[i]+x-1)/x;
		int tmp1=1;
		while(tmp1<tmp){
			kk-=min(tmp1, tmp-tmp1);
			if(kk<0)return 0;
			tmp1*=2;
		}
	}
	return 1;
}
int main(){
	// int t;
	// while(){
		scanf("%d%d",&n,&k);
		int mx=0;
		for(int i=0; i<n; ++i){
			scanf("%d",a+i);
			mx=max(mx, a[i]);
		}
		int st=1, nd=mx, md;
		while(st<nd){
			md=(st+nd)/2;
			if(fn(md)){
				nd=md;
			}
			else{
				st=md+1;
			}
		}
		cout<<nd<<endl;
	// }
}

Measured memory_bytes: 4540
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M;
    cin >> N >> M;
    string str;
    int P,penalty[N]={0},numOfAc=0,numOfPenalty=0;
    bool state[N]={0};
    for(int i=0; i<M; i++){
        cin >> P >> str;
        P--;
        if(state[P]==0){
            if(str.compare("AC")==0){
                state[P]=1;
            }else{
                penalty[P]++;
            }
        }
    }
    for(int i=0; i<N; i++){
        if(state[i]==1){
            numOfAc++;
            numOfPenalty+=penalty[i];
        }
    }
    cout << numOfAc << " " << numOfPenalty;
    return 0;
}


Measured memory_bytes: 768
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// 内部定数
#define D_KAT_MAX		100000									// 最大刀数

// 内部変数
static int siKCnt;												// 刀数
static int siNeed;												// 必要ダメージ
static int siShake;												// 振るダメージ最大
static int si1Throw[D_KAT_MAX];									// 投げダメージ

// 内部変数 - テスト用
#ifdef D_TEST
	static int siRes;
	static FILE *szpFpT, *szpFpA;
#endif

// ソート関数 - int降順
int
fSortFnc(
	const void *pzpVal1			// <I> 値１
	, const void *pzpVal2		// <I> 値２
)
{
	int *lipVal1 = (int *)pzpVal1;
	int *lipVal2 = (int *)pzpVal2;

	// 降順
	if (*lipVal1 >  *lipVal2) {
		return(-1);
	}
	else if (*lipVal1 < *lipVal2) {
		return(1);
	}

	return 0;
}

// 回数取得
int
fGetCnt(
)
{
	int i;

	// 投げダメージ
	for (i = 0; i < siKCnt; i++) {
		if (si1Throw[i] <= siShake) {	// 振るダメージ以下
			break;
		}

		// ダメージ
		siNeed -= si1Throw[i];

		// 必要値チェック
		if (siNeed <= 0) {
			return i + 1;
		}
	}

	// 振る回数
	int liCnt = (siNeed + siShake - 1) / siShake;

	return liCnt + i;
}

// 実行メイン
int
fMain(
	int piTNo					// <I> テスト番号 1～
)
{
	int i;
	char lc1Buf[1024], lc1Out[1024];

	// データ初期化
	siShake = 0;												// 振るダメージ最大

	// テストファイルオープン
#ifdef D_TEST
	sprintf(lc1Buf, ".\\Test\\T%d.txt", piTNo);
	szpFpT = fopen(lc1Buf, "r");
	sprintf(lc1Buf, ".\\Test\\A%d.txt", piTNo);
	szpFpA = fopen(lc1Buf, "r");
	siRes = 0;
#endif

	// 刀数・必要ダメージ取得
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
	fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
	sscanf(lc1Buf, "%d%d", &siKCnt, &siNeed);

	// 振るダメージ最大・投げダメージ取得
	for (i = 0; i < siKCnt; i++) {
		int liVal;
#ifdef D_TEST
		fgets(lc1Buf, sizeof(lc1Buf), szpFpT);
#else
		fgets(lc1Buf, sizeof(lc1Buf), stdin);
#endif
		sscanf(lc1Buf, "%d%d", &liVal, &si1Throw[i]);

		// 振るダメージ最大
		if (siShake < liVal) {
			siShake = liVal;
		}
	}

	// 投げダメージ - ソート
	qsort(si1Throw, siKCnt, sizeof(int), fSortFnc);

	// 回数取得
	int liCnt = fGetCnt();

	// 結果セット
	sprintf(lc1Out, "%d\n", liCnt);

	// 結果表示
#ifdef D_TEST
	fgets(lc1Buf, sizeof(lc1Buf), szpFpA);
	if (strcmp(lc1Buf, lc1Out)) {
		siRes = -1;
	}
#else
	printf("%s", lc1Out);
#endif

	// テストファイルクローズ
#ifdef D_TEST
	fclose(szpFpT);
	fclose(szpFpA);
#endif

	// テスト結果
#ifdef D_TEST
	if (siRes == 0) {
		printf("OK %d\n", piTNo);
	}
	else {
		printf("NG %d\n", piTNo);
	}
#endif

	return 0;
}

int
main()
{

#ifdef D_TEST
	int i;
	for (i = D_TEST_SNO; i <= D_TEST_ENO; i++) {
		fMain(i);
	}
#else
	fMain(0);
#endif

	return 0;
}



Measured memory_bytes: 892
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private const long INFINITY = 9223372036854775807;
    public static void Main()
    {
        string s = NextString();
        Console.WriteLine(s.Substring(0,4)+" "+s.Substring(4));
    }
}

public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}


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

int main(){
string a,b;
  cin >> a >> b;
  if (a.size()==b.size()){
  for (int i=0;i<a.size();i++){
  cout <<a.at(i) <<b.at(i);
  }
  cout <<endl;
  }
  else {
  for(int i=0;i<b.size();i++){
  cout <<a.at(i)<<b.at(i);
  }
  cout <<a.at(a.size()-1)<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Forenska(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
#define GREATER(x) x,vector<x>,greater<x>
#define randIn(L,R) (((LL)rand()*rand())%(R-L)+L)
#define __lcm(a,b) ((a)/__gcd(a,b)*(b))
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pLL;
typedef vector<int> vec;
typedef vector<LL> vecL;
typedef vector<pii> vecP;
typedef vector<pLL> vecPL;
typedef vector<string> vecS;
typedef vector<vec> mat;
typedef complex<double> point;
const long double PI=3.14159265358979323846264338327950288419716939937510582097;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
const long double EPS=1e-10;
int read()
{
    int x=0;
    char ch=' ';
    bool flag=false;
    while(ch<'0' || ch>'9')
    {
        if(ch=='-')flag=true;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return flag?-x:x;
}
const int MAX_N=123;
bool flag[MAX_N];
int main()
{
	flag[0]=true;
	rep(i,0,100)
	{
		if(flag[i])
		{
			flag[i+4]=flag[i+7]=true;
		}
	}
	puts(flag[read()]?"Yes":"No");
	return 0;
}



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

using ll = int64_t;
#define int ll

#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, b) FOR(i, 0, b)
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(x) x.begin(), x.end()

using pi = pair<int, int>;
using vi = vector<int>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  REP(i, (int)v.size()) {
    if (i) os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

ll read() {
  ll i;
  scanf("%" SCNd64, &i);
  return i;
}

void printSpace() { printf(" "); }

void printEoln() { printf("\n"); }

void print(ll x, int suc = 1) {
  printf("%" PRId64, x);
  if (suc == 1) printEoln();
  if (suc == 2) printSpace();
}

string readString() {
  static char buf[3341000];
  scanf("%s", buf);
  return string(buf);
}

char *readCharArray() {
  static char buf[3341000];
  static int bufUsed = 0;
  char *ret = buf + bufUsed;
  scanf("%s", ret);
  bufUsed += strlen(ret) + 1;
  return ret;
}

template <class T, class U>
void chmax(T &a, U b) {
  if (a < b) a = b;
}

template <class T, class U>
void chmin(T &a, U b) {
  if (b < a) a = b;
}

template <class T>
T Sq(const T &t) {
  return t * t;
}

const int mod = 1e9 + 7;

int n, x[100], y[100], h[100];

signed main() {
  cin >> n;
  tuple<int, int, int> g;
  REP(i, n) {
    cin >> x[i] >> y[i] >> h[i];
    if (h[i] >= 1) g = make_tuple(x[i], y[i], h[i]);
  }
  REP(i, 101) {
    REP(j, 101) {
      int tmp_h = get<2>(g) + abs(get<0>(g) - i) + abs(get<1>(g) - j);
      if (h == 0) continue;
      bool flag = true;
      REP(k, n) {
        int tmp_hh = tmp_h - abs(x[k] - i) - abs(y[k] - j);
        chmax(tmp_hh, 0);
        if (tmp_hh != h[k]) {
          flag = false;
          break;
        }
      }
      if (flag == true) {
        cout << i << " " << j << " " << tmp_h << endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)

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

    vector<int> A(3);
    REP(i, 3) cin >> A[i];

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

    int ans = 0;
    REP(i, 2){
        ans += abs(A[i] - A[i + 1]);
    }
    cout << ans << endl;

    return 0;
}


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

typedef pair<int, int> pii;
typedef long long ll;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

#ifdef LOCAL
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else 
#define dump(x) true
#endif

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }

template<class T, class U> bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } return 0; }
template<class T, class U> bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } return 0; }

template<class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	os<<"{";
	rep(i, v.size()) {
		if (i) os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

const int INF = TEN(9);

int dp[2010][2010];
int pos[2][2010];
int num[2][4010][2010];

int main() {
	int N; cin >> N;
	V<pii> vec;
	rep(i, N * 2) {
		char c; int a;
		cin >> c >> a;
		--a;
		bool f = (c == 'B');
		vec.eb(f, a);
		pos[f][a] = i;
	}

	rep(c, 2) {
		rep(i, N) {
			int p = pos[c][i];
			for (int j = 0; j <= i; ++j) {
				++num[c][p][j];
			}
		}

		rep(i, N * 2) {
			rep(j, N) {
				num[c][i+1][j] += num[c][i][j];
			}
		}
	}

	cerr << vec << endl;

	rep(i, 2010) {
		rep(j, 2010) {
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;

	for (int i = 0; i <= N; ++i) {
		for (int j = 0; j <= N; ++j) {
			if (i < N) { //put W
				int p = pos[0][i];
				int val = num[0][p][i + 1] + num[1][p][j];

				chmin(dp[i+1][j], dp[i][j] + val);
			}
			if (j < N) { //put W
				int p = pos[1][j];
				int val = num[0][p][i] + num[1][p][j + 1];

				chmin(dp[i][j+1], dp[i][j] + val);
			}
		}
	}
	cout << dp[N][N] << endl;

	return 0;
}

Measured memory_bytes: 79104
#include <numeric>
#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
#include <functional>
#include <queue>
#include <string>
#include <bitset>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <set>
#include <algorithm>
#include <tuple>
#include <sstream>

using namespace std;

#ifdef LOCAL
#define logv(a) {cerr << #a << " = "; for (auto& e : a) {cerr << e << " ";} cerr << "\n";}
#define logvp(a) {cerr << #a << " = "; for (auto& e : a) {cerr << "(" << e.first << ", " << e.second << ") ";} cerr << "\n";}
#define logvv(a) {cerr << #a << " = \n"; for (auto& r : a) { for (auto& e : r) {cerr << e << " ";} cerr << "\n";} }
#define logvf(a, field) {cerr << #a"."#field << " = \n"; for (auto& e : a) { cerr << e.field << " ";} cerr << "\n"; }
#define logs(a) cerr << #a << " = " << (a) << "\n";
#define logss(a, b) cerr << #a << " = " << (a) << ", " << #b << " = " << (b) << "\n";
#define logp(a) cerr << #a << " = " << "(" << a.first << ", " << a.second << ")" << "\n";
#define cond(pred, stmt) if (pred) { stmt }
#else
#define logv(a)
#define logvp(a)
#define logvv(a)
#define logvf(a, field)
#define logs(a)
#define logss(a, b)
#define logp(a)
#define cond(pred, stmt)
#endif

#define forn(a, e) for (int a = 0; a < (int)e; a++)
#define forr(a, s, e) for (int a = s; a < (int)e; a++)

using i64 = long long;

template<typename T>
using Pair = array<T, 2>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    i64 n;
    while (cin >> n) {
        cout << n * n * n << endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define rep(i,n) for(i=0;i<n;i++)
int max(int a,int b){
    if(a<b) a=b;
    return a;
}
int main(){
    long int i,n,m;
    scanf("%ld%ld",&n,&m);
    int h[100010],ma[100010];
    for(i=1;i<=n;i++){
        scanf("%d",&h[i]);
        ma[i]=0; //n個の0
    }
    rep(i,m){
        int a,b;
        scanf("%d%d",&a,&b);
        ma[a]=max(ma[a],h[b]);//展望台aに繋がる展望台の最大値が残る
        ma[b]=max(ma[b],h[a]);
    }
    int ans=0;
    for(i=1;i<=n;i++){
        if(ma[i]<h[i]) ans++;
    }
    printf("%d",ans);
}

Measured memory_bytes: 2516
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



#n=int(input())
n,m=list(map(int,input().split()))
a=(m-2*n)/2
b=(4*n-m)/2

if a<0 or b<0 or int(a)!=a or int(b)!=b:
    print("No")
    exit()

else:
    print("Yes")

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

using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 
#define REP(i, n) for (int i = 0; i < (n); i++)

int main(int argc, char const *argv[])
{
    int a,b;
    cin >> a >> b;
    if (a<=8&&b<=8) cout << "Yay!\n";
    else cout << ":(\n";
    return 0;
}

Measured memory_bytes: 256
import sys


class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def _root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self._root(x) == self._root(y)

    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1


def main():
    n, q = map(int, sys.stdin.buffer.readline().split())
    U = UnionFind(n)
    for x in sys.stdin.buffer.readlines():
        t, u, v = map(int, x.split())
        if t:
            if U.find(u, v):
                print(1)
            else:
                print(0)
        else:
            U.union(u, v)


if __name__ == "__main__":
    main()


Measured memory_bytes: 21884
#include<iostream>
using namespace std;
int main(){
	int n;
	cin>>n;
	int a[n+1],b[n+1];
	for(int i=1;i<=n;i++){
	cin>>a[i];//3
	b[a[i]]=i;//
	}
	for(int i=1;i<=n;i++)
	cout<<b[i]<<' ';
	return 0;
}

Measured memory_bytes: 1536
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::io::{BufWriter, Write};

// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn dist(a: (f64, f64), b: (f64, f64)) -> f64 {
    let ret = (a.0 - b.0).powf(2.0) + (a.1 - b.1).powf(2.0);
    return ret.powf(0.5);
}

fn solve() {
    input!(
        n: usize,
        xy: [(f64, f64); n],
    );

    let mut d: f64 = 0.0;

    let mut base: f64 = 1.0;

    for i in 1..n {
        base *= i as f64;
    }

//    println!("{}", base);

    for i in 0..n {
        for j in 0..i {
            d += base * dist(xy[i], xy[j]) * 2.0;
        }
    }

    println!("{}", d / base / n as f64);
}

fn main() {
    let stack_size = 1 << 28;
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


Measured memory_bytes: 8572
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;

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

	cin >> N >> M >> K;
	vector<long long int>place(N);
	vector<long long int>dir(N);
	vector<long long int>ans(N);
	long long int dif = 0;
	for (int i = 0; i < N; i++) {
		cin >> place[i] >> dir[i];
		place[i] += MOD*M;
		if (dir[i] == 1) {
			ans[i] = place[i] + K;
			dif += ans[i] / M - place[i] / M;
			ans[i] %= M;
		}
		else {
			ans[i] = place[i] - K;
			dif += ans[i] / M - place[i] / M;
			ans[i] %= M;
		}
	}
	sort(ans.begin(), ans.end());
	for (int i = 0; i < N; i++) {
		cout << ans[(i + dif+N*MOD*100) % N] << endl;
	}
	return 0;
}


Measured memory_bytes: 3584
a, b, c = map(int, input().split())

if a > b:
    tmp = b
    b = a
    a = tmp

if b > c:
    tmp = c
    c = b
    b = tmp

if a > b:
    tmp = b
    b = a
    a = tmp

print(a,b,c)

# sortを使って解く -> Presentation error となってしまう。。
"""
A = list(map(int, input().split()))
A.sort()
for a in A:
    print(a, end=' ')
"""



Measured memory_bytes: 5608
N, W = [int(i) for i in input().split()]
weight, value = [], []

for i in range(N):
    w, v = [int(i) for i in input().split()]
    weight.append(w); value.append(v);
weight.append(0)
value.append(0)

dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if (j-weight[i] >= 0):
            dp[i+1][j] = max(dp[i+1][j], dp[i][j-weight[i]] + value[i])
        dp[i+1][j] = max(dp[i+1][j], dp[i][j])

print(dp[N][W])

Measured memory_bytes: 171656
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005,M=1e9+7;
int n,m,f[N],g[N],ans;
char s[N];
signed main(){
	scanf("%lld%lld",&n,&m);
	scanf("%s",s+1);
	if (s[1]=='R'){
		for (int i=1;i<=m;i++){
			if (s[i]=='R')s[i]='B';
			else s[i]='R';
		}
	}
	int l=0,mi=0;
	for (int i=1;i<=m;i++)
		if (s[i]=='R'){
			l=i-1;
			break;
		}
	if (!l){
		f[0]=g[0]=1;
		for (int i=1;i<=n;i++){
			f[i]=g[i-2];
			g[i]=(g[i-1]+f[i])%M;
		}
		for (int i=2;i<=n;i++)(ans+=i*f[n-i])%=M;
		printf("%lld\n",(ans+1)%M);
		return 0;
	}
	mi=l+!(l%2);
	for (int i=1,j=1;i<=m;i=j){
		while (j<=m&&s[j]=='B')j++;
		if (j>m)break;
		if ((j-i)&1)mi=min(mi,j-i);
		while (j<=m&&s[j]=='R')j++;
	}
	if (n%2==1){
		puts("0");
		return 0;
	}
	mi=(mi+1)/2;
	n/=2;
	f[0]=g[0]=1;
	for (int i=1;i<=n;i++){
		f[i]=(g[i-1]-(i-mi-1<0?0:g[i-mi-1])+M)%M;
		g[i]=(g[i-1]+f[i])%M;
	}
	for (int i=1;i<=mi;i++)(ans+=i*2*f[n-i])%=M;
	printf("%lld\n",ans);
}

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

int N,x[100001],y[100001],t[100001],T,X,Y;

int main(void){
    cin >>N;
    for(int i=1;i<=N;i++) cin >> t[i] >> x[i] >> y[i];
    
    rep(i,N){
        int dl=abs(x[i+1]-x[i]) + abs(y[i+1]-y[i]);
        int dt=t[i+1]-t[i];
        if(dt<dl || dt%2 != dl%2){cout << "No" << endl;return 0;}
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI 3.141592653589793238462643383279502884L
#define make_unique(vec) vec.resize(distance(vec.begin(),unique(vec.begin(),vec.end())))
#define Sort(vec) sort(vec.begin(),vec.end())
#define RSort(vec) sort(vec.rbegin(),vec.rend())
#define endl "\n"
#define tr1(i) cout<<i<<endl;
#define tr2(i,j) cout<<i<<" "<<j<<endl;
#define tr3(i,j,k) cout<<i<<" "<<j<<" "<<k<<endl;
#define vvi vector<vector<int> > 
#define vvl vector<vector<ll> >
#define all(st) st.begin(),st.end()
#define vpl vector<pair<ll,ll> >
#define vpi vector<pair<int,int> >
#define pi pair<int,int>
#define pl pair<ll,ll>
#define al vector<list<int> >
#define vs vector<string>
#define vb vector<bool>
#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define rep(i,l,r) for(int i=l;i<r;i++)
#define repit(st) for(auto it=st.begin();it!=st.end();it++)
#define ull unsigned long long int
#define eb emplace_back
#define pb push_back
#define ll long long int
#define minf -(1e18)
#define inf 1e18
#define f first
#define se second
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds; 
ll mi(ll n,ll m){ll pw=n%m;ll ex=m-2;ll ans=1;while(ex){if(ex&1) ans = ans*pw%m;pw = pw*pw%m;ex>>=1;}return ans%mod;}
ll pw(ll a,ll n){ll pw=a;ll ex=n;ll ans=1;while(ex){if(ex&1) ans = ans*pw;pw = pw*pw;ex>>=1;}return ans;}
ll pwm(ll a,ll n){ll pw=a%mod;ll ex=n;ll ans=1;while(ex){if(ex&1) ans = ans*pw%mod;pw = pw*pw%mod;ex>>=1;}return ans%mod;}
template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }
template<typename T> using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
//st.order_of_key(num)->number of elements <=num
//st.find_by_order(i)->iterator of ith element in sorted order starting from zero
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll max(ll a,ll b){return a>b?a:b;}
ll min(ll a,ll b){return a<b?a:b;}
ll Abs(ll x){return x>0?x:(-x);}
ll Ceil(ll a,ll b){return a/b+(a%b!=0);}
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define mkp make_pair
//#define d double
//#define int long long int
//Binary_Search->dp->greedy
void solve(){
	ll n,s;
	cin>>n>>s;
	vl vec(n);
	cin>>vec;
	vvl dp(n,vl(3001));
	ll ans=0;
	dp[n-1][0]=1;
	ll md=998244353;
	dp[n-1][vec[n-1]]=1;
	for(int i=n-2;i>=0;i--){
		dp[i][vec[i]]=dp[i+1][vec[i]]+(n-i);
		for(int j=0;j<=3000;j++){
			if(j==vec[i]) continue;
			dp[i][j]=dp[i+1][j]%md;
			if(j>=vec[i]){
				dp[i][j]+=dp[i+1][j-vec[i]];
				dp[i][j]%=md;
			}
		}
	}
	for(int i=0;i<n;i++) ans+=dp[i][s],ans%=md;
	cout<<ans<<endl;
 
 
}
int32_t main(){
int t=1;
//scanf("%d",&t);
while(t--){
	solve();
}
}   

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

class Program
{
    static void Main()
    {
        string[] arr = Console.ReadLine().Split(' ');
        int H = int.Parse(arr[0]);
        int A = int.Parse(arr[1]);
        int cnt = 0;

        while(0 < H)
        {
            cnt++;
            H -= A;
        }

        Console.WriteLine(cnt);
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

typedef long long int64;

int main(void){
    int64 N;
    cin>>N;
    if(N==2){
        cout<<"0"<<endl;
        return 0;
    }
    int64 ans=0;
    double n=sqrt(N);
    for(int64 i=1;i<n;i++){
        if(N%i==0){
            if(!(i-N/i==1||N/i-i==1)){
                ans+=N/i-1;
            }
            
        }
    }

    cout<<ans<<endl;
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main()
{
    int l,r,d,s,i;
    s = 0;
    scanf("%d %d %d",&l,&r,&d);
    for(i = l;i <= r;i++){
        if(i % d == 0){
            s++;
        }
    }
    printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 1680
#include<bits/stdc++.h>
using namespace std;
int main(void){
	int n;
	double ave;
	double box[1001];
	int i;
	double sum;
	double x;
	while(1){
		cin>>n;
		if(n==0)	break;
		ave=0;
		for(i=0;i<n;i++){
			cin>>box[i];
			ave+=box[i];
		}
		ave=(double)ave/n;
		sum=0;
		for(i=0;i<n;i++){
			sum+=(double)pow(box[i]-ave,2);
		}
		x=(double)sqrt(sum/n);
		printf("%.10f\n",x);
	}
}


Measured memory_bytes: 3212
using System;
using System.Linq;

namespace ALDS1_9B{
    public class Program{
        public static void Main(string[] args){
            var sr = new StreamReader();
            //---------------------------------
            var H = sr.Next<int>();
            var A = new[]{0}.Concat(sr.Next<int>(H)).ToArray();

            Action<int> maxHeapify = null;
            maxHeapify = i =>{
                var l = 2 * i;
                var r = l + 1;

                var maxi = i;
                if(l <= H && A[l] > A[maxi]) maxi = l;
                if(r <= H && A[r] > A[maxi]) maxi = r;
                if(maxi == i) return;

                Ex.Swap(ref A[i], ref A[maxi]);
                maxHeapify(maxi);
            };

            for(var i = H / 2; i >= 1; i--) maxHeapify(i);
            Console.WriteLine(" " + string.Join(" ", A.Skip(1).Select(x => x.ToString()).ToArray()));
            //---------------------------------
        }
    }

    public class Ex{
        public static void Swap<T>(ref T left, ref T right){
            var tmp = left;
            left = right;
            right = tmp;
        }
    }

    public class StreamReader{
        private readonly char[] _c = {' '};
        private int _index = -1;
        private string[] _input = new string[0];

        public T Next<T>(){
            if(_index == _input.Length - 1){
                _index = -1;
                while(true){
                    string rl = Console.ReadLine();
                    if(rl == null){
                        if(typeof(T).IsClass) return default(T);
                        return (T)typeof(T).GetField("MinValue").GetValue(null);
                    }
                    if(rl != ""){
                        _input = rl.Split(_c, StringSplitOptions.RemoveEmptyEntries);
                        break;
                    }
                }
            }
            return (T)Convert.ChangeType(_input[++_index], typeof(T), System.Globalization.CultureInfo.InvariantCulture);
        }

        public T[] Next<T>(int x){
            var ret = new T[x];
            for(var i = 0; i < x; ++i) ret[i] = Next<T>();
            return ret;
        }

        public T[][] Next<T>(int y, int x){
            var ret = new T[y][];
            for(var i = 0; i < y; ++i) ret[i] = Next<T>(x);
            return ret;
        }
    }
}

Measured memory_bytes: 75412
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000
#define int long long
vector<int> vec;
vector<int> G[51];
bool dfs(int u, int v, int p = -1) {
    //cout << u << " " << v << " " << p << endl;
    if(u == v) {
        vec.push_back(u);
        return true;
    }
    for(auto to: G[u]) {
        if (to == p) continue;
        if(dfs(to, v, u)) {
            vec.push_back(u);
            return true;
        }
    }
    return false;
}
int c[51][51] = {};
signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    int a[51], b[51];
    rep(i, N - 1) {
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        c[a[i]][b[i]] = i;
        c[b[i]][a[i]] = i;
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    int v[21], u[21];
    int M; cin >> M;
    rep(i, M) {
        cin >> v[i] >> u[i];
        v[i]--; u[i]--;
    }
    int ans = 0;
    rep(bit, (1 << M)) {
        int S = 0;
        rep(i, M) {
            if (bit & (1 << i)) {
                vec.clear();
                dfs(v[i], u[i]);
                rep(j, (int)(vec.size()) - 1) {
                    S |= (1LL << c[vec[j]][vec[j + 1]]);
                }
                //cout << "*" << vec.size() << endl;
            }
        }
        int cnt1 = __builtin_popcountll(bit);
        int cnt2 = __builtin_popcountll(S);
        if(cnt1 % 2 == 0) ans += (1LL << (N - 1 - cnt2));
        else ans -= (1LL << (N - 1 - cnt2));
        //cout << bitset<16>(bit) << " " << bitset<16>(S) << endl;
    }
    cout << ans << endl;


    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <stack>
using namespace std;
#define debug(x) std::cerr << #x << " = " << (x) << std::endl
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;
const int MAXN = 25;

map<PII, int> pos;

int n, ans;
int x[MAXN+5], y[MAXN+5];
bool vis[MAXN + 5];
int dp[70000], cnt[70000][400];

int gcd(int x, int y){
	if(y == 0) return x;
	else return gcd(y, x % y);
}

PII solve(int x_1, int x_2, int y_1, int y_2){
	int dx = x_1 - x_2; int dy = y_1 - y_2;
	if(dx == 0){ return PII(-1, 0);}
	else if(dy == 0){return PII(0, -1);}
	else if(dx < 0 && dy > 0){
		int Gcd = gcd(-dx, dy);
		dx /= Gcd; dy /= Gcd;
	}
	else if(dx > 0 && dy < 0){
		int Gcd = gcd(dx, -dy);
		dx = -(dx / Gcd); dy = -(dy / Gcd);
	}
	else{
		dx = abs(dx), dy = abs(dy);
		int Gcd = gcd(dx, dy);
		dx /= Gcd; dy /= Gcd;
	}
	return PII(dx, dy);
}

int main(){
	scanf("%d", &n);
	int ans = 0;
	for(int i = 1; i <= n; i++) scanf("%d %d", &x[i], &y[i]);
	int tot = 0;
	for(int i = 1; i <= n; i++)
		for(int j = i + 1; j <= n; j++) {
			PII tmp = solve(x[i], x[j], y[i], y[j]);
			if(!pos[tmp]) pos[tmp] = ++tot;
		}
	for(int i = 0; i < (1 << n); i++) {
		int cnt1 = 0;
		for(int j = 1; j <= n; j++) vis[j] = 0;
		for(int j = 0; j < n; j++)
			if(i & (1 << j)) vis[j + 1] = 1, cnt1++;
		if(!(cnt1 & 1)) {
			for(int v1 = 1; v1 <= n; v1++)
				for(int v2 = v1 + 1; v2 <= n; v2++)
					if(!vis[v1] && !vis[v2]) {
						int p = i;
						p |= (1 << (v1 - 1));
						p |= (1 << (v2 - 1));
						int c = pos[solve(x[v1], x[v2], y[v1], y[v2])];
						if(dp[i] + cnt[i][c] >= dp[p]) {
							for(int r = 1; r <= tot; r++) cnt[p][r] = cnt[i][r];
							cnt[p][c] += 1;
							dp[p] = dp[i] + cnt[i][c];
						}
					}
		}
	}
	printf("%d\n", dp[(1 << n) - 1]);
	return 0;
}


Measured memory_bytes: 101780
#include<algorithm>
#include<cstdio>
using namespace std;
int n,p,t,a[100005];
bool bz;
bool cmp(int a,int b){return a>b;}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for (;a[p+1]>=p+1;p++);
	for (;a[p+t]>=p;t++); 
	if (((a[p]-p+1)&1) && (t&1)) bz=1;
	printf(bz?"Second":"First");
	return 0;
}


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

int main()
{
  int n,k;
  cin>>n>>k;
  ll h[n+1],dp[n+1];
  for(int i=1;i<=n;i++)cin>>h[i];
  dp[1]=0;
  dp[2]=abs(h[1]-h[2]);
  for(int i=3;i<=n;i++){
    ll cost=LLONG_MAX;
    for(int j=1;j<=k;j++){
      if(i-j<=0)break;
      else cost=min(cost,dp[i-j]+abs(h[i-j]-h[i]));
    }
    dp[i]=cost;
  }
  cout<<dp[n]<<endl;
}

Measured memory_bytes: 1792
class Graph
  attr_accessor :vertexes

  def initialize
    @vertexes = {}
  end

  def register(index, weights)
    @vertexes[index] = Vertex.new(index, weights, self)
  end

  def find(index); @vertexes[index]; end

  def each; @vertexes.each{ |_, v| yield v }; end

  def prim
    min_costs = Hash.new{ | h, k | h[k] = Float::INFINITY }
    min_costs[0] = 0

    while true
      min_cost = Float::INFINITY
      selected_vertex = nil
      self.each do | v |
        if !v.selected? && min_costs[v.index] < min_cost
          selected_vertex = v
          min_cost = min_costs[v.index]
        end
      end

      break if selected_vertex.nil?

      selected_vertex.select!

      self.each do | v |
        next if v.selected? || !selected_vertex.neighbor?(v)

        if selected_vertex.cost(v) < min_costs[v.index]
          min_costs[v.index] = selected_vertex.cost(v)
          v.parent = selected_vertex
        end
      end

    end
    sum = 0
    self.each{ | v | sum += v.parent.cost(v) if v.parent }
    sum
  end

  def dijkstra(start)
    min_costs = Hash.new{ | h, k | h[k] = Float::INFINITY }
    min_costs[start] = 0

    while true
      min_cost = Float::INFINITY
      selected_vertex = nil
      self.each do | v |
        if !v.selected? && min_costs[v.index] < min_cost
          selected_vertex = v
          min_cost = min_costs[v.index]
        end
      end

      break if selected_vertex.nil?

      selected_vertex.select!

      self.each do | v |
        next if v.selected? || !selected_vertex.neighbor?(v)

        if min_cost + selected_vertex.cost(v) < min_costs[v.index]
          min_costs[v.index] = min_cost + selected_vertex.cost(v)
          v.parent = selected_vertex
        end
      end

    end
    min_costs
  end

end


class Vertex
  attr_accessor :index, :parent, :graph

  def initialize(index, weights, graph)
    # @index: 頂点を識別するindex
    # @index_cost_map: 繋がってる辺とコストの対応を示す.
    #                  {1=>2}なら頂点1にコスト2で接続.
    # @selected: 確定済み頂点か示すフラグ.
    @index = index
    @index_cost_map = weights.map.with_index{ | e, i |
      e == -1 ? nil : [i, e]
    }.compact!.to_h
    @selected = false
		@graph = graph
  end

  def neighbors
    @neighbors ||= @index_cost_map.keys.map{ | i | @graph.find(i) }
  end

  def neighbor?(other)
    @index_cost_map.key?(other.index)
  end

  def cost(other)
    @index_cost_map[other.index]
  end

  def selected?;  @selected; end

  def select!; @selected = true; end

end

n = gets.to_i
graph = Graph.new
n.times do
  weights = Array.new(n){ -1 }
  vals = gets.split.map(&:to_i)
  index = vals.shift
  k = vals.shift
  k.times do
    vertex = vals.shift
    cost = vals.shift
    weights[vertex] = cost
  end
  graph.register(index, weights)
end

graph.dijkstra(0).each{ | k, v | puts "#{k} #{v}" }



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

#define M 1046527
#define L 14

char Hash[M][L];

int getChar(char ch)
{
    if (ch == 'A')
        return 1;
    if (ch == 'C')
        return 2;
    if (ch == 'G')
        return 3;
    if (ch == 'T')
        return 4;
    return 0;
}

long long getKey(char str[])
{
    long long sum = 0;
    int p = 1;
    for (int i = 0; i < strlen(str); i++)
    {
        sum += p * (getChar(str[i]));
        p *= 5;
    }
    return sum;
}

int h1(int key) { return key % M; }
int h2(int key) { return 1 + (key % (M - 1)); }

int find(char str[])
{
    long long key;
    key = getKey(str);
    for (int i = 0;; i++)
    {
        int h;
        h = (h1(key) + i * h2(key)) % M;
        if (strcmp(Hash[h], str) == 0)
            return 1;
        else if (strlen(Hash[h]) == 0)
            return 0;
    }
    return 0;
}

int insert(char str[])
{
    long long key = getKey(str);
    for (int i = 0;; i++)
    {
        int h;
        h = (h1(key) + i * h2(key)) % M;
        if (strlen(Hash[h]) == 0)
        {
            strcpy(Hash[h], str);
            return 0;
        }
    }
    return 0;
}

int main()
{
    int num;
    cin >> num;
    char str[L];
    char command[7];
    for (int i = 0; i < num; i++)
    {
        cin >> command >> str;
        if (command[0] == 'i')
        {
            insert(str);
        }
        else if (command[0] == 'f')
        {
            if (find(str))
            {
                cout << "yes" << endl;
            }
            else
            {
                cout << "no" << endl;
            }
        }
    }
}



Measured memory_bytes: 17356
#include <stdio.h>

int main() {
	int a, b, max;

	scanf("%d%d", &a, &b);
	max = a + b;
	if (max < a - b)
		max = a - b;
	if (max < a * b)
		max = a * b;
	printf("%d\n", max);
	return 0;
}


Measured memory_bytes: 128
def solve(X, Y, p, q, r):
    red_apples = sorted(p, reverse=True)[: X]
    green_apples = sorted(q, reverse=True)[: Y]
    white_apples = sorted(r)

    ret = 0
    while red_apples and green_apples:
        if not white_apples or (white_apples[-1] < red_apples[-1] and white_apples[-1] < green_apples[-1]):
            return ret + sum(red_apples) + sum(green_apples)

        ret += white_apples.pop(-1)
        if red_apples[-1] < green_apples[-1]:
            red_apples.pop(-1)
        else:
            green_apples.pop(-1)


    if not red_apples:
        while green_apples and white_apples and (green_apples[-1] < white_apples[-1]):
            ret += white_apples.pop(-1)
            green_apples.pop(-1)
        return ret + sum(green_apples)

    else:
        while red_apples and white_apples and (red_apples[-1] < white_apples[-1]):
            ret += white_apples.pop(-1)
            red_apples.pop(-1)
        return ret + sum(red_apples)

if __name__ == '__main__':
    X, Y, A, B, C = map(int, input().split())
    p = list(map(int, input().split()))
    q = list(map(int, input().split()))
    r = list(map(int, input().split()))
    print(solve(X, Y, p, q, r))

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

#define NDEBUG
#include <cassert>


typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define eb  emplace_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair

#define PQ(T) priority_queue<T>
#define RPQ(T) priority_queue<T,vector<T>,greater<T>>

template<class T> inline void amin(T & a, T const & b) { a = min(a, b); }
template<class T> inline void amax(T & a, T const & b) { a = max(a, b); }

inline ll square(ll x) { return x * x; }
inline ll gcd(ll a, ll b) { while(a) swap(a, b%=a); return b; }
template <typename T>
inline T mod(T a, T b) { return ((a % b) + b) % b; }


vi l;
int N,A,B,C;
vi x;
vi pat;

int calc(int a,int b,int c){
    vi iota(3); rep(i,3) iota[i]=i;
    int best = INT_MAX;
    do{
        int mp = 0;
        mp += abs(x[iota[0]] - pat[a]);
        mp += abs(x[iota[1]] - pat[b]);
        mp += abs(x[iota[2]] - pat[c]);
        amin(best, mp);
    } while (next_permutation(ALL(iota)));
    return best;
}

int solve() {
    int P=1<<N;
    pat.resize(P);
    rep(p,P){
        int mp = 0;
        for(int i=0;i<N;++i){
            int b = 1<<i;
            if(p&b){
                mp += l[i];
            }
        }
        pat[p] = mp;
    }

    int best = INT_MAX;
    rep1(a,P-1) {
        int ap = __builtin_popcount(a);
        if (ap > N-2) continue;
        rep1(b,P-1) {
            if (a & b) continue;
            int ab = a|b;
            int abp = __builtin_popcount(ab);
            if (abp > N-1) continue;
            rep1(c,P-1) {
                if (ab & c) continue;
                int abc = ab|c;
                int abcp = __builtin_popcount(abc);
                int tmp = calc(a,b,c);
                int mp = 10 * (abcp-3) + tmp;
                amin(best, mp);
            }
        }
    }
    return best;
}

int main() {
    cin >> N >> A >> B >> C;
    x = vi{ A, B, C };
    l.resize(N);
    rep(i,N) cin >> l[i];
    cout << solve() << endl;
    return 0;
}


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

std::set<int> enum_div(int n) {
	std::set<int> divs = {1, n};
	for(int i = 2 ; i*i <= n ; ++i) {
		if(n%i == 0) {
			divs.insert(i);
			divs.insert(n/i);
		}
	}
	return divs;
}

int main() {
  int N, M; std::cin >> N >> M;
  std::set<int> factor = enum_div(M);
  for (auto it = factor.rbegin(); it != factor.rend(); ++it) {
    if((*it) <= (M/N)) {
      std::cout << *it << std::endl;
      return 0;
    }
  }
}


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

int main() {
  string s;
  cin >> s;
  if(s == "ABC"){
      cout << "ARC" << endl;
  }
  else{
      cout << "ABC" << endl;
  }
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
typedef long long int ll;

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n; cin >> n;
	map<string,int> mp;
	string s;
	for(int i=0;i<n;i++){
		cin >> s;
		mp[s]++;
	}
	int q; cin >> q;
	int t=0;
	while(q--){
		cin >> s;
		if(mp[s]==0){
			cout << "Unknown " << s << endl;
		}
		else{
			if(!t){
				cout << "Opened";
			}
			else{
				cout << "Closed";
			}
			cout << " " << "by " << s << endl;
			t^=1;
		}
	}
}


Measured memory_bytes: 3248
while True:
    a,op,b=input().split()
    a=int(a)
    b=int(b)
    import math
    if op=="?":
        break
    if op=="+":
        print(math.floor(a+b))
    elif op=="-":
        print(math.floor(a-b))
    elif op=="*":
        print(math.floor(a*b))
    elif op=="/":
        print(math.floor(a/b))



Measured memory_bytes: 5664
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>
#include <string>
#define int long long
#define REP(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define mp make_pair
#define Pii pair< int, int > 
#define Pid pair< int, double > 
#define Pdd pair< double, double > 
#define MOD 998244353
#define EPS 0.00000001

using namespace std;

signed main() {
    int n,s;
    cin >> n >> s;
    vector<int> a(n);
    REP(i,n) cin >> a.at(i);
    vector<vector<int> > dp(3001, vector<int>(n+1));
    dp[0][0] = 1;
    for(int i = 1; i < n+1; i++) {
        dp[0][i] = ((i + 1) * (i + 2) / 2) % MOD;
    }
    for(int i = 1; i < 3001; i++) {
        //j = 1
        if (i == a[0]) dp[i][1] = 1;
        for(int j = 2; j < n+1; j++) {
            dp[i][j] = (dp[i][j-1] * 2 - dp[i][j-2] + MOD) % MOD;
            if (i >= a[j-1]) dp[i][j] = (dp[i][j] + dp[i - a[j-1]][j-1] - dp[i - a[j-1]][j-2] + MOD) % MOD;
        }
    }
    /*
    REP(i,10) {
        REP(j,n+1) {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    */
    cout << dp[s][n] % MOD << "\n";
    return 0;
}

Measured memory_bytes: 72192