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

using namespace std;

#define End exit(0)
#define LL long long
#define mp make_pair
#define SZ(x) ((int) x.size())
#define GO cerr << "GO" << endl
#define DE(x) cout << #x << " = " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

void proc_status()
{
	freopen("/proc/self/status","r",stdin);
	string s; while(getline(cin, s)) if (s[2] == 'P') { cerr << s << endl; return; }
}

template<typename T> inline T read() 
{
	register T x = 0;
	register char c; register int f(1);
	while (!isdigit(c = getchar())) if (c == '-') f = -1;
	while (x = (x << 1) + (x << 3) + (c ^ 48), isdigit(c = getchar()));
	return x * f;
}

template<typename T> inline bool chkmin(T &a,T b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a,T b) { return a < b ? a = b, 1 : 0; }

const int maxN = 5000 + 2;
const int mod = 1e9 + 7;

vector<int> adj[maxN + 2];
int g[maxN + 2], n, size[maxN + 2];
int dp[maxN + 2][maxN + 2][2];

void input()
{
    n = read<int>();
    for (int i = 1; i < n; ++i)
    {
        int u = read<int>(), v = read<int>();
        adj[u].push_back(v), adj[v].push_back(u);
    }
}

void dfs(int u, int f)
{
    static int tmp[maxN + 2][2];

    size[u] = 1;
    dp[u][1][0] = 1;
    for (int v : adj[u])
        if (v != f)
        {
            dfs(v, u);
            for (int i = 0; i <= size[u]; ++i)
                for (int j = 0; j <= size[v]; ++j)
                    for (int a = 0; a < 2; ++a)
                        for (int b = 0; b < 2; ++b)
                        {
                            (tmp[i + j][a ^ b] += (LL) dp[v][j][a] * dp[u][i][b] % mod) %= mod;
                            if (!(j & 1))
                                (tmp[i][a ^ b ^ 1] += (LL) dp[v][j][a] * dp[u][i][b] % mod * g[j] % mod) %= mod;
                        }
            size[u] += size[v];
            for (int i = 0; i <= size[u]; ++i)
                for (int j = 0; j < 2; ++j)
                    dp[u][i][j] = tmp[i][j], tmp[i][j] = 0;
        }
}

void solve()
{
    g[0] = 1;
    for (int i = 2; i <= n; i += 2) g[i] = (LL) g[i - 2] * (i - 1) % mod;
    dfs(1, 0);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        (ans += ((LL) dp[1][i][0] - dp[1][i][1] + mod) * g[i] % mod) %= mod;
    cout << ans << endl;
}

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



Measured memory_bytes: 195328
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

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


constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 60ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
	template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
	template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
	template<typename T> void chadd(T& a, T b) { a = a + b; }

	void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
	template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
	template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

	void CCout(long long x, const char* end = "\n") { std::cerr << x << end; }
	template <typename T> void CCout(const T& x, const char* end = "\n") { std::cerr << x << end; }
	template <typename T> void CCout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cerr << x[i] << (i == sz - 1 ? end : sep); } }

	// 標準入出力
	struct inp {
		std::size_t sz;
		inp(std::size_t _sz = 1) : sz(_sz) {}
		template <typename T> operator T () const { T a; std::cin >> a; return a; }
		template <typename T> operator std::vector<T>() const { vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
		template <typename T, typename U> operator std::pair<T, U>() const { T f; U s; std::cin >> f >> s; return std::pair<T, U>(f, s); }
	};

	inp inp1; // input one
}

int main() {

	string s = inp1;

	if (s[2] == s[3] && s[4] == s[5]) {
		Cout(Yes(true));
	}
	else {
		Cout(Yes(false));
	}

	return 0;
}


Measured memory_bytes: 256
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, M, Q = LI()
ABCD = LRI(Q)

def calc(A):
    ret = 0

    for a, b, c, d in ABCD:
        if A[b] - A[a] == c:
            ret += d
    
    return ret


def dfs(A):
    ans = 0
    stack = A

    while stack:
        s = stack.pop()
            
        if len(s) < N+1:
            back = s[-1]
            while back <= M:
                stack.append(s + [back])
                back += 1
        else:
            ans = max(ans, calc(s))

    return ans

print(dfs([[1]]))


Measured memory_bytes: 68836
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

#define ll long long
#define MOD 998244353

using namespace std;

ll leapCountCache[200001] = {0, 1}, leapCountSumCache[200001] = {0, 1};

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

    vector<pair<ll, ll>> leapSegments(k);

    for (ll i = 0; i < k; i++)
        cin >> leapSegments[i].first >> leapSegments[i].second;

    for (ll i = 2; i <= n; i++)
    {
        for (ll j = 0; j < k; j++)
        {
            ll leftEndIndex = max(i - leapSegments[j].second, 1ll);
            ll rightEndIndex = i - leapSegments[j].first;

            if (rightEndIndex < 0)
                continue;

            leapCountCache[i] += leapCountSumCache[rightEndIndex] - leapCountSumCache[leftEndIndex - 1];
            leapCountCache[i] %= MOD;
        }

        leapCountSumCache[i] = leapCountSumCache[i - 1] + leapCountCache[i];
    }

    cout << leapCountCache[n] << endl;

    return 0;
}

Measured memory_bytes: 6732
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<int,int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
int gcd(int a,int b){if(a<b)swap(a,b);int c=a%b;while(c!=0){a=b;b=c;c=a%b;}return b;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

ll n;
int sum = 0;
int d[] = {7, 5, 3};

void dfs(ll a, vector<bool> m){
  // cout << a << endl;
  if(a <= n){
    bool f = 1;
    rep(i, 3){
      if(!(m[i])) f = 0;
    }
    if(f){
      sum++;
    }
    rep(i, 3){
      vector<bool> m2(3, 0);
      m2 = m;
      m2[i] = 1;
      dfs(a*10+d[i], m2);
    }
  }
}

int main(){
  cin >> n;

  vector<bool> memo(3,0);
  dfs(0, memo);

  cout << sum << endl;

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void) {
	int n, count = 0;
	int i;
	char s[100];

	scanf("%d", &n);

		scanf("%s",s);
	
	
	for (i = 0; i <= n - 3; i++) {
		if (
			(s[i] == 'A') && (s[i + 1] == 'B') && (s[i + 2] == 'C')
			) {

			count++;
		}
	}

	printf("%d", count);
	return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <numeric>
#include <regex>
#include <climits>

#define FOR(i, f, n) for(int (i) = (f); (i) < (n); (i)++)
#define RFOR(i, f, n) for(int (i) = (f); (i) >= (n); (i)--)
#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, n) for(int (i) = 0; (i) < (n); (i)++)
#define rrep(i, n) for(int (i) = (n); (i) >= 0; (i)--)
#define forin(i, a) for(auto i: (a))
#define p(...) printf(__VA_ARGS__); cout << endl;
#define in(...) __VA_ARGS__; input__(__VA_ARGS__);
#define input(...) in(__VA_ARGS__)
#define out(...) output__(__VA_ARGS__);
#define output(...) out(__VA_ARGS__)
#define list_input(x, n) x[(n)]; for(int (i) = 0; (i) < (n); (i)++) cin >> x[i];
#define lambda(a, b, c) [](auto const &a, auto const &b){ return c ;}
#define key(t, x, compare) [](const t &a, const t &b){ return a x compare b x ;}
#define unless(a) if(!(a))

using namespace std;

using pii = pair<int, int>;

template <class... T>
void input__(T &...a) {
  for(auto v: {&a...}) {
    cin >> *v;
  }
}

void output__(){
  cout << endl;
}

template <class Head, class... T>
void output__(Head const &v, T const &...a) {
  if(sizeof...(a) == 0) {
    cout << v;
  } else {
    cout << v << " ";
  }
  output__(a...);
}

int main(){
  long long in(h, w);
  if(h == 1 and w == 1) {
    out(1);
  } else if(h == 1) {
    if(w != 1) {
      out(w - 2);
    } else {
      out(0);
    }
  } else if(w == 1) {
    if(h != 1) {
      out(h - 2);
    } else {
      out(0);
    }
  } else if(h == 2 or w == 2) {
    out(0);
  } else {
    out((h - 2) * (w - 2));
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<vector<long>> dp;
vector<long>nums;
// int solve(int i,int j){
//     if(i>j) return 0;
//     else{
        
//     }
// }

int main(){
    int size;
    cin>>size;
    nums.resize(size,0);
    dp.resize(size,vector<long>(size));
    // dpy.resize(size,0);
    
    for(int i=0;i<size;i++){
        cin>>nums[i];
    }
    for(int i=size-1;i>=0;i--){
        
        for(int j=i;j<size;j++){
            if(i==j) dp[i][j]=nums[i];
            else dp[i][j]=max((i+1<size)?nums[i]-dp[i+1][j]:0,(j-1>=0)?nums[j]-dp[i][j-1]:0);
        }
    }
    long ans=dp[0][size-1];
    // solve(0,size-1);
    cout<<ans;
    return 0;
    
    
}

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

int main() {
  int W, H, N;
  cin >> W >> H >> N;
  int x, y, a, b[4] = {0, W, 0, H};
  for (int i=0; i<N; i++) {
    cin >> x >> y >> a;
    a--;
    if (a == 0)
      b[a] = max(b[a], x);
    else if (a == 1)
      b[a] = min(b[a], x);
    else if (a == 2)
      b[a] = max(b[a], y);
    else
      b[a] = min(b[a], y);
  }
  int ans = max(0, b[1]-b[0]) * max(0, b[3]-b[2]);
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
parseInt(x)=parse(Int, x)
parseMap(x::Array{SubString{String},1})=map(parseInt, x)

function main()
	n = readline() |> parseInt
	d = Dict{String,Int}()
	for i in 1:n
		s=readline() |> chomp
		if !haskey(d,s)
			d[s]=1
		end
	end
	println(length(keys(d)))
end

main()

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

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

const int N = 1<<18;
const ll INF= INT_MAX; 

/*datのサイズはNに固定*/

class RMQ{
public:
  ll n;
  P dat[2*N-1];
  
  //初期化
  RMQ(){
    n=N;
    for(int i=0;i<2*n-1;i++) dat[i]=P(INF,INF);
  }
  
  //k番目の値をaに変更
  void update(int k,P a){
    k+=n-1;
    dat[k]=a;
    while(k>0){
      k=(k-1)/2;
      dat[k]=min(dat[k*2+1],dat[k*2+2]);
    }
  }
  
  //[a,b)の最小値を求める query(a,b,0,0,n)
  P query(int a,int b,int k=0,int l=0,int r=N){
    if(r<=a||b<=l)return P(INF,INF);
    if(a<=l&&r<=b)return dat[k];
    P vl=query(a,b,k*2+1,l,(l+r)/2);
    P vr=query(a,b,k*2+2,(l+r)/2,r);
    return min(vl,vr);
  }
};

const int MAX_N = 1<<18;

class BIT{
public:
  int n;
  ll bit0[MAX_N+1],bit1[MAX_N+1];//1オリジン
  BIT(){n = MAX_N;memset(bit0,0,sizeof(bit0));memset(bit1,0,sizeof(bit1));}
  BIT(int n){this->n=n;memset(bit0,0,sizeof(bit0));memset(bit1,0,sizeof(bit1));}
  
  ll sum(ll *b,int i){
    ll s=0;
    while(i>0){
      s=(s+b[i]);
      i-=i&-i;
    }
    return s;
  }

  void add(ll *b,int i,ll v){
    while(i<=n){
      b[i]=(b[i]+v);
      i+=i&-i;
    }
  }

  //[a,b]にxを加算(1<=a)
  void add (int a,int b,ll x){
    add(bit0,a,-x*(a-1));
    add(bit1,a,x);
    add(bit0,b+1,x*b);
    add(bit1,b+1,-x);
  }

  //[a,b]のsumを得る(1<=a)
  ll sum(int a,int b){
    ll res=0;
    res+=sum(bit0,b)+sum(bit1,b)*b;
    res-=sum(bit0,a-1)+sum(bit1,a-1)*(a-1);
    return res;
  }
};

string s;
int k;

void solve(){
  
  RMQ rmq = RMQ();
  BIT bit = BIT(s.size());
  
  for(int i=0;i<s.size();i++){
    rmq.update(i, P(s[i],i));
    bit.add(i+1, i+1, 1);
  }
    
  string ans;
  
  while(ans.size()!=s.size()){
    
    int l=0, r=s.size();
    
    while(l<r){
      
      int m=(l+r)/2;
      
      if(bit.sum(1, m+1)<=k+1) l=m+1;
      else r=m;
      
    }
    
    P minp=rmq.query(0, l);
    char minc=minp.first;
    int minidx=minp.second;
    
    k-=bit.sum(1, minidx);
    bit.add(minidx+1, minidx+1, -1);
    rmq.update(minidx, P(INF, INF));
    
    ans+=minc;
  }
  
  cout<<ans<<endl;
}

int main(){
  
  cin>>s;
  cin>>k;
  
  solve();
  
  return 0;
}



Measured memory_bytes: 11744
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;
    auto G = new int[][](N);
    foreach (_; 0..N-1) {
        auto s = readln.split.map!(to!int);
        G[s[0]-1] ~= s[1]-1;
        G[s[1]-1] ~= s[0]-1;
    }

    if (N == 2) {
        writeln(A[0] == A[1] ? "YES" : "NO");
        return;
    }

    int root;
    foreach (i; 0..N) {
        if (G[i].length >= 2) {
            root = i;
            break;
        }
    }


    bool dfs(int n, int p) {
        if (G[n].length == 1) {
            return true;
        }
        
        long sm = 0;
        long mx = 0;
        foreach (m; G[n]) {
            if (m != p) {
                if (!dfs(m, n)) return false;
                sm += A[m];
                mx = max(mx, A[m]);
            }
        }

        if (sm < A[n] || sm > A[n] * 2) return false;
        long k = sm - A[n];
        if (k > sm - mx) return false;
        A[n] -= k;
        
        return n == root ? A[n] == 0 : (A[n] >= 0);
    }

    writeln(dfs(root, -1) ? "YES" : "NO");
}


Measured memory_bytes: 24716
#include <cstdio>
using namespace std;

typedef long long LL;

int main(int argc, char** argv)
{
	int h, w;
	scanf("%d%d", &h, &w);
	if(h == 1 || w == 1) {puts("1"); return 0;}
	LL t = LL(h) * w;
	printf("%lld\n", t & 1LL? (t >> 1LL) + 1LL: t >> 1LL);
	return 0;
}

Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long int ll;

int N;
int a;

int main(){
	scanf("%d", &N);
	bool flag = true;
	for(int i = 0; i < N; i++){
		scanf("%d", &a);
		if(a % 2 == 1) flag = false;
	}
	if(flag) printf("second\n");
	else printf("first\n");
	return 0;
}


Measured memory_bytes: 128
n,x=map(int,input().split())
A=list(map(int,input().split()))
cnt=0

if A[0]>x:
  cnt+=A[0]-x
  A[0]-=A[0]-x

for i in range(1,n):
  total= A[i]+A[i-1]
  if total>x:
    cnt+=total-x
    A[i]-=total-x
print(cnt)

Measured memory_bytes: 14252
//
//  main.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


int main(){	
	int n;
	int team[3][10001];
	int point[3][10001];
	int gets[10001];
	for(int i = 0;i<3;i++)for(int j=0;j<10001;j++)gets[j] = team[i][j] = point[i][j]= 0;
	
	cin >> n;
	for(int i=0;i<n*(n-1)/2;i++){
		cin >> team[0][i] >> team[1][i] >> point[0][i] >> point[1][i];
	}
	
	for(int i=0;i<n*(n-1)/2;i++){
		if(point[0][i] > point[1][i]){
			gets[team[0][i]] += 3;
		}else if(point[0][i] < point[1][i]){
			gets[team[1][i]] += 3;
		}else{
			gets[team[0][i]] += 1;
			gets[team[1][i]] += 1;
		}
	}
	
	vector <pair<int,int> > vec;
	for(int i=1;i<=n;i++){
		vec.push_back(make_pair(gets[i],i));//?????°?????????
	}
	sort(vec.begin(),vec.end());
	int answer[101]={};
	int memo = -1;
	int count = 0;
	for(int i=n-1;i>=0;i--){
		if(memo == vec[i].first){
			count ++;
		}else{
			memo = vec[i].first;
			count = 0;
		}
		answer[vec[i].second] = n - i - count;
	}
	for(int i=1;i<=n;i++){
		cout << answer[i] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3376
#include <stdio.h>
 
int main(){
   int n,a,b,i,j,q1,q2,q3;
    
   scanf("%d",&n);
   scanf("%d %d",&a,&b);
   for (q1=q2=q3=i=0;i<n;i++) {
      scanf("%d",&j);
      if (j<=a) q1++;
      else if (j<=b) q2++;
      else q3++;
   }
   if (q2<q1) q1=q2;
   if (q3<q1) q1=q3;
   printf("%d\n",q1);
   return 0;
}


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

using namespace std;


int main(){
    int N;cin >> N;
    vector<long long> vec;
    priority_queue<pair<long long,long long>, vector<pair<long long,long long>> , greater<pair<long long,long long>>> que;
    for(int a = 0;a < N;a++){
        long long b;cin >> b;
        vec.push_back(b);
        que.push({b,a});
    }
    set<long long> se;
    se.insert(-1);
    se.insert(N);
    long long ans = 0;
    while(!que.empty()){
        pair<long ,long> q = que.top();que.pop();
        long long under = *prev(se.lower_bound(q.second))+1;
        long long upper = *se.upper_bound(q.second);
      //  cout<<q.second-under+1<<" "<<upper-q.second<<endl;
        ans += 1LL*q.first * (((upper-q.second)*(q.second-under+1)));
        se.insert(q.second);
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 15072
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    string S;
    cin >> S;
    int ans;
    int N = S.size();
    int il, ir;
    char c;

    if(N % 2 == 0){
        ans = N / 2;
        il = N / 2 - 1;
        ir = N / 2;
        c = S[il];
    }else{
        ans = (N - 1) / 2;
        il = ir = (N - 1) / 2;
        c = S[il];
    }

    while(il >= 0 && ir < N && S[il] == c && S[ir] == c){
        ans++;
        il--;
        ir++;
    }

    cout << ans;
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 512
a,b=map(int,input().split())
ans=0
for i in range(a//10000,10):
    for j in range(0,10):
        for k in range(0,10):
            x=i*(10000+1)+j*(1000+10)+k*100
            if x>=a and x<=b:ans+=1
print(ans)

Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;
LL x[100001];
LL L;
int Q;
LL a[100001];
LL b[100001];
vector<int>G[100011];
int root;
int parent[21][100011];
int depth[100011];

void dfs(int v,int p,int d){
   parent[0][v]=p;
   depth[v]=d;
   REP(i,G[v].size()){
       if(G[v][i]!=p)dfs(G[v][i],v,d+1);
   }
}

void init(int V){
     //parent[0]とdepthを初期化する
     dfs(root,-1,0);
     //cout<<parent[0][N-1]<<endl;
     //parentを初期化する
     REP(k,19){
         REP(v,V){
            if(parent[k][v]<0)parent[k+1][v]=-1;
            else parent[k+1][v]=parent[k][parent[k][v]];
         }
     }
}


int main(){
    cin>>N;
    REP(i,N){
        cin>>x[i];
    }
    cin>>L>>Q;
    REP(i,Q){
        cin>>a[i]>>b[i];
        if(a[i]>b[i])swap(a[i],b[i]);
        a[i]--;b[i]--;
    }
    //木の構築
    int now=0;
    REP(i,N-1){
        while(1){
           if(now==N)break;
           if(x[now]-x[i]<=L){
              now++;
           }else{
              break;
           }
        }
        G[now-1].push_back(i);
        G[i].push_back(now-1);
    }
    //LCAの初期化
    root=N-1;
    init(N);
    /*REP(i,N){
        REP(j,20){
            cout<<parent[j][i]<<" ";
        }
        cout<<endl;
    }*/
    LL d=1;
    REP(i,20){
        d*=2;
    }
    
    REP(i,Q){
        LL c=0;
        LL e=d;
        int cc=a[i];
        for(int j=20;j>=0;j--){
            if(parent[j][cc]<=b[i]&&parent[j][cc]>0){
               cc=parent[j][cc];
               c+=e;
            }
            e/=2;
        }
        if(cc!=b[i]){
           c++;
        }
        
        cout<<c<<endl;
    }
    return 0;
}

Measured memory_bytes: 23424
#include <bits/stdc++.h>
#define REP(i,n) for (int i=0;i<(n);i++)
#define FOR(i,s,e) for (int i=s;i<(e);i++)
#define All(v) (v).begin(),(v).end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define fi first
#define se second
#define int long long
using namespace std;
typedef long long llint;
typedef pair<int, int> P;
const int MOD = (int)1e9 + 7;
const int INF = (int)1e18 * 2;

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

    int n, m;
    cin >> n >> m;
    while(!(n==0 && m==0)){
        vector<int> t(n);
        vector<int> h(m);
        int t_sum=0, h_sum=0;
        REP(i, n){
            cin >> t[i];
            t_sum += t[i];
        }
        REP(j, m){
            cin >> h[j];
            h_sum += h[j];
        }
        P ans = mp(INF, INF);
        REP(i, n)REP(j, m){
            if(t_sum-t[i]+h[j] == h_sum-h[j]+t[i]){
                if(ans.fi+ans.se > t[i]+h[j]){
                    ans = mp(t[i], h[j]);
                }
            }
        }
        if(ans.fi == INF) cout << -1 << "\n";
        else cout << ans.fi << " " << ans.se << "\n";

        cin >> n >> m;
    }
    return 0;
}


Measured memory_bytes: 3104
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;

struct CumulativeSum2D{
  vector<vector<int> > data;
  CumulativeSum2D(int H, int W) : data(H + 1, vector<int>(W + 1, 0)) {}
  void add(int x, int y, int z){
    ++x, ++y;
    if(x >= data.size() || y >= data[0].size()) return;
    data[x][y] += z;
  }
  void build(){
    for(int i = 1; i < data.size(); i++) {
      for(int j = 1; j < data[i].size(); j++) {
        data[i][j] += data[i][j - 1] + data[i - 1][j] - data[i - 1][j - 1];
      }
    }
  }
  //左上[sy, sx], 右下(gx, gy)の矩形内の和を求める(半開区間) (0-index)
  int query(int sx, int sy, int gx, int gy){
    return (data[gx][gy] - data[sx][gy] - data[gx][sy] + data[sx][sy]);
  }
};

int main(){
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> s(h);
  for(int i = 0; i < h; ++i) cin >> s[i];
  CumulativeSum2D cs(h, w);
  for(int i = 0; i < h; ++i){
    for(int j = 0; j < w; ++j){
      if(s[i][j] == '1') cs.add(i, j, 1);
    }
  }
  cs.build();
  int ans = 1e9;
  for(int mask = 0; mask < (1 << (h - 1)); ++mask){
    int sum = __builtin_popcountll(mask);
    int left = 0;
    vector<int> t, r;
    r.push_back(0);
    t.push_back(0);
    for(int i = 0; i < h - 1; ++i){
      if(mask & (1 << i)) t.push_back(i + 1);
    }
    t.push_back(h);
    for(int j = 1; j < w; ++j){
      bool f = true;
      for(int i = 0; i < t.size() - 1; ++i){
        if(cs.query(t[i], left, t[i + 1], j + 1) > k){
          f = false;
        }
      }
      if(!f){
        sum++;
        r.push_back(j);
        left = j;
      }
    }
    r.push_back(w);
    bool g = true;
    for(int j = 0; j < r.size() - 1; ++j){
      for(int i = 0; i < t.size() - 1; ++i){
        if(cs.query(t[i], r[j], t[i + 1], r[j + 1]) > k){
          g = false;
        }
      }
    }
    if(g) ans = min(ans, sum);
  }
  cout << ans << endl;
}

Measured memory_bytes: 3688
using System;
using System.Collections.Generic;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var input = Array.ConvertAll(ReadLine().Split(' '), ulong.Parse);
        var min = input[0];
        var max = input[1];
        var num = input[2];
        var set = new HashSet<ulong>();
        for(var i = min; i <min+num; i++)
        {
            if (i > max) break;
            WriteLine(i);
            set.Add(i);
        }
        for(var i = max-num+1; i <= max; i++)
        {
            if (i < min) continue;
            if(!set.Contains(i))
            WriteLine(i);
        }
    }
}



Measured memory_bytes: 13396
#ARC060 C
#すごいdpを思いつく人もいるものだと思う
'''
直感的には？
- dp[i][t] = dp[i-1][t]+dp[i-1][t-X[i-1]]
    取らなかった場合の数＋取ってこの値にした場合の数
    t=0で-2を取るか取らないかを迫られた時、取ればt=+2から2引いてt=0に来て、取らねばt=0はt=0から来る
- dp[i][t] = dp[i-1][t]
    取らなかった場合の数で、
    「起こり得ない数からの遷移はしない」と考えた場合dp[i-1][t-X[i-1]]が不要になるというだけ
    無理に取ろうとすると配列外参照となる
- dp[0][N*MX] = 1
    初期状態では当然、平均は0なので
- それ以外
    i=0の時しかないが、初期状態で平均が他の値になることはない
'''

N,A = map(int,input().split())
X = list(map(lambda x:int(x)-A,input().split()))

MX = max(X+[0])

dp = [[0 for i in range(2*MX*N+1)] for _ in range(N+1)]

for i in range(N+1):
    for t in range(2*MX*N+1):
        if i==0 and t==N*MX:
            dp[i][t] = 1
        elif i>=1:
            if t-X[i-1]>=0 and t-X[i-1]<=2*MX*N:
                dp[i][t] = dp[i-1][t]+dp[i-1][t-X[i-1]]
            else:
                dp[i][t] = dp[i-1][t]
        else:
            dp[i][t] = 0
    
print(dp[N][N*MX]-1)
#print("\n".join([str(d) for d in dp]))

Measured memory_bytes: 5108
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>

using namespace std;

int main(void) {
	int N;
	cin >> N;
	vector<long long int> A(N), B(N), C(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	for (int i = 0; i < N; i++) cin >> C[i];
	B.push_back(0);
	C.push_back(0);
	sort(A.rbegin(), A.rend());
	sort(B.rbegin(), B.rend());
	sort(C.rbegin(), C.rend());

	vector<long long int> NB(N, 0);
	int ic = 0;
	for (int ib = 0; ib < N; ib++) {
		while (B[ib] < C[ic]) ic++;
		NB[ib] = ic;
	}

	vector<long long int> NBC(N + 1, 0);
	for (int i = 0; i < N; i++) {
		NBC[i + 1] = NBC[i] + NB[i];
	}

	//for (int i = 0; i < N; i++) cout << i << " " << NB[i] << " " << NBC[i] << endl;

	long long int ans = 0;
	int ib = 0;
	for (int ia = 0; ia < N; ia++) {
		while (A[ia] < B[ib]) ib++;
		//cout << ia << " " << ib << endl;
		ans += NBC[ib];
	}


	cout << ans << endl;
	system("pause");
	return 0;
}

Measured memory_bytes: 5244
import sys
from itertools import product

def main():
  input = sys.stdin.readline
  h, w = map(int, input().split())
  ans = [[0 for _ in range(w+2)] for _ in range(h+2)]
  for i in range(h):
    s = list(map(str, input().strip()))
    for j in range(w):
      if s[j] == '#':
        ans[i+1][j+1] = '#'
      
        for k in product([-1, 0, 1], repeat=2):
          if ans[i+1+k[0]][j+1+k[1]] != '#':
            ans[i+1+k[0]][j+1+k[1]] += 1
        
  for i in range(1, h+1):
    print(*ans[i][1:w+1], sep='')


if __name__ == '__main__':
  main()

Measured memory_bytes: 3444
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n][3],dp[n][3];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i][0]>>arr[i][1]>>arr[i][2];
    }
    dp[0][0]=arr[0][0];
    dp[0][1]=arr[0][1];
    dp[0][2]=arr[0][2];
    for(int i=1;i<n;i++)
    {
        dp[i][0]=max(dp[i-1][1],dp[i-1][2])+arr[i][0];
        dp[i][1]=max(dp[i-1][2],dp[i-1][0])+arr[i][1];
        dp[i][2]=max(dp[i-1][1],dp[i-1][0])+arr[i][2];
    }
    cout<<max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2]));
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[105];
int main() {
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	ll ans=1e18;
	ll res=0;
	for(int i=-100;i<=100;i++)
	{
		res=0;
		for(int j=1;j<=n;j++)
		{
			res+=(a[j]-i)*(a[j]-i);
		}
		ans=min(ans,res);
	}
    printf("%lld",ans);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); i++)
#define lower(s) transform(s.begin(), s.end(), s.begin(), ::tolower)
using namespace std;
using ll = long long;
int INF = 1001001001;

  int a, b, c;
  int k;
  bool ans = false;

void dfs(vector<int> x, int cnt) {
  cnt++;
  // cout << cnt << endl;
  // rep(i, 3) cout << x[i] << " ";
  if(x[0] < x[1] && x[1] < x[2]) {
    ans = true;
    return;
  }
  if(cnt > k) {
    return;
  }
  rep(i, 3) {
    // cout << endl;
    vector<int> tmp = x;
    tmp[i] *= 2;
    dfs(tmp, cnt);
    if(ans) break;
  }
}

int main() {
  cin >> a >> b >> c;
  cin >> k;
  vector<int> x;
  x.push_back(a);
  x.push_back(b);
  x.push_back(c);
  dfs(x, 0);
  if(ans) {
    cout << "Yes" << endl;
  } else {
  cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 3616
/**********************************************************/
/**            Bismillahir-rahmanir-rahim                **/
/**  In the name of Allah, the Beneficent, the Merciful. **/
/**********************************************************/
/****@author: Sayed Sohan, CSE 13th batch(2016), MBSTU*****/
/**********************************************************/

#include <bits/stdc++.h>
using namespace std;
//              Typedefs
typedef long long               ll;
typedef unsigned long long      ull;

//              Templates
template<class T>               using min_heap = \
                                priority_queue<T, \
                                std::vector<T>, std::greater<T>>;

//              Basic-Defs
#define PB                      push_back
#define MP                      make_pair
#define SP                      " "
#define NL                      "\n"
#define all(v)                  v.begin(), v.end()

//              DEBUG--SECTION
#define DE                      cout<<"HERE\n";
#define DE1(x)                  cout<<x<<"###\n";
#define DE2(x,y)                cout<<x<<"--->"<<y<<"\n";
#define Pause                   system("pause");

//              Functions
#define clr(arr,value)          memset(arr,value,sizeof(arr))
#define __FAST_IO               ios_base::sync_with_stdio(0);\
                                cin.tie(0);cout.tie(0);
#define NUM1(x)                 __builtin_popcount(x)
#define LCM(x,y)                (x*y)/__gcd(x,y)

//              Sizes--Math     0123456789
#define MOD                     1000000007   //1e9+7 
#define MAX                     100050      
#define INF                     1e18
#define PI                      acos(-1)
#define eps                     1e-6

//** your code goes from here


int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    __FAST_IO;
    
    ll i,j,k,n,m,T; //basic variables

    string s,s2;
    cin>>s>>s2;

    ll ans = 0;
    for(i=0;i<s.size();i++){
        if(s[i]!=s2[i]) ans++;
    }
    cout<<ans<<NL;


    /// Don't forget to set array size....
    return 0;
}




Measured memory_bytes: 3828
var fs = require("fs");
var line = fs.readFileSync("/dev/stdin");
var N = Number(line);
var res = 0;

for (var i = 1; i <= N; i++) {
  var n = Math.floor(N / i);
  res += Math.floor((i * n * (n + 1)) / 2);
}

console.log(res);


Measured memory_bytes: 33196
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(x) x.begin(), x.end()
#define mod 1000000007
typedef long long ll;

int main(){
  string str;
  cin >> str;
  rep(i, str.length()){
    if(str[i] == '?') str[i] = 'D';
  }
  cout << str << endl;
  return 0;
}

Measured memory_bytes: 3712
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <algorithm>
#include <iostream>

using namespace std;

const int MAX_N = 100;

int N, Y;
int D[MAX_N];

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

    cin >> N >> Y;
    Y /= 1000;

    int a = -1;
    int b = -1;
    int c = -1;
    bool getans = false;
    for (int i = 0; i <= min(N, Y / 10); i++) {
        int sumtt = 10 * i;
        for (int j = 0; j <= min(N - i, Y - sumtt); j++) {
            if (sumtt + j + 5 * (N - i - j) == Y) {
                a = i;
                c = j;
                b = N - i - j;
                getans = true;
                break;
            }
        }
        if (getans)
            break;
    }
    cout << a << " " << b << " " << c << "\n";
    return 0;
}

Measured memory_bytes: 3632
N, M = map(int, input().split())
AC = [0]*N
WA = [0]*N
L = []
for m in range(M):
    p, S = map(str, input().split())
    p = int(p)
    L.append([p, S])
for m in range(M):
    if not AC[L[m][0]-1] == 0:
        continue    
    if L[m][1] == 'AC':
        AC[L[m][0]-1] = 1
    elif L[m][1] == 'WA':
        WA[L[m][0]-1] += 1
A = sum(AC)
W = 0
for n in range(N):
    if AC[n] == 1:
        W += WA[n]
print(A, W)

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

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

int main(){
	string s, t;
	cin >> s >> t;
	vector<int> en1(27, 0), en2(27, 0);

	for (int i = 0; i < s.size(); i++){
		int index = 0;
		for (char c = 'a'; c <= 'z'; c++){
			if (s[i] == c){
				en1[index]++;
			}
			index++;
		}
	}
	for (int i = 0; i < t.size(); i++){
		int index = 0;
		for (char c = 'a'; c <= 'z'; c++){
			if (t[i] == c){
				en2[index]++;
			}
			index++;
		}
	}

	sort(en1.begin(), en1.end());
	sort(en2.begin(), en2.end());

	for(int i = 0; i < 27; i++){
		// cout << en1[i] << " " << en2[i] << endl;
		if (en1[i] != en2[i]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 776
#include <cstdlib>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>
#include <functional>
using namespace std;

int main() {
    vector<char> v(3);
    for(int i = 0; i < 3; i++) cin >> v[i];

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

    if(v[0] != v[1] && v[1] != v[2]) cout << "Yes" << endl;
    else cout << "No" << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,a,m2=0,m4=0;
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a;
    if(a%4==0)
      m4++;
    else if(a%2==0)
      m2++;
  }
  if(m4>0){
  if(m4+1>=(n-m4-m2+min(m2,1)))
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  }else{
    if(m2==n)
  cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
static const int MAX = 1000;

void print_ary(int ary[], int n)
{
  int i;
  for (i = 0; i < n; i++)
  {
    if (i > 0)
      cout << " ";
    cout << ary[i];
  }
  cout << endl;
}

void insertion_sort(int ary[], int n)
{
  int v, i, j;
  for (i = 1; i < n; i++)
  {
    v = ary[i];
    j = i - 1;

    while (j >= 0 && ary[j] > v)
    {
      ary[j + 1] = ary[j];
      j--;
    }

    ary[j + 1] = v;

    print_ary(ary, n);
  }
}

int main(void)
{
  int i, n, a[MAX];

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

  print_ary(a, n);
  insertion_sort(a, n);

  return 0;
}



Measured memory_bytes: 3072
#include <algorithm>
#include <boost/dynamic_bitset.hpp>
#include <iostream>
#include <numeric>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main() {
    auto h = 0;
    auto w = 0;
    std::cin >> h >> w;

    auto maze = std::vector<std::string>();
    for (auto i_ = 0; i_ < h; ++i_) {
        auto s = std::string();
        std::cin >> s;
        maze.emplace_back(s);
    }

    auto q = std::queue<std::pair<std::pair<int, int>, int>>();
    q.emplace(std::make_pair(0, 0), 1);

    auto in_queue = boost::dynamic_bitset<>(w * h);

    auto push_next_place = [&](const auto& i, const auto& j, const auto& dist) {
        if (i < 0 || i > h - 1) return;
        if (j < 0 || j > w - 1) return;

        if ((!in_queue[i * w + j]) && (maze[i][j] == '.')) {
            in_queue.set(i * w + j);
            q.emplace(std::make_pair(i, j), dist);
        }
    };

    while (!q.empty()) {
        const auto place = q.front().first;
        const auto dist = q.front().second;

        const auto i = place.first;
        const auto j = place.second;
        q.pop();

        if ((i == (h - 1)) && (j == (w - 1))) {
            const auto white_space = std::accumulate(maze.begin(), maze.end(), 0, [](auto sum, const auto& a) {
                return sum + std::count(a.begin(), a.end(), '.');
            });
            std::cout << (white_space - dist) << std::endl;
            return 0;
        }

        push_next_place(i - 1, j, dist + 1);
        push_next_place(i + 1, j, dist + 1);
        push_next_place(i, j - 1, dist + 1);
        push_next_place(i, j + 1, dist + 1);
    }

    std::cout << -1 << std::endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
values = list(map(int,input().split()))
costs = list(map(int,input().split()))

sub_list = []
for i in range(n):
    sub_list.append(values[i]-costs[i])

ans = 0
for num in sub_list:
    if num > 0:
        ans += num

print(ans)


Measured memory_bytes: 3060
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).unwrap();
    let s = s.trim();
    println!("{}", if s.chars().zip(s.chars().skip(1)).all(|(a, b)| a != b) { "Good" } else { "Bad" });
}


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

int main(){
  int H,W;
  cin >> H >> W;
  vector<string> s(H);
  for(int i=0;i<H;i++){
    cin >> s.at(i);
  }
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      if(s.at(i).at(j)=='#'){
        if(i!=0){
          if(s.at(i-1).at(j)=='#'){
            continue;
          }
        }
        if(i!=H-1){
          if(s.at(i+1).at(j)=='#'){
            continue;
          }
        }
        if(j!=0){
          if(s.at(i).at(j-1)=='#'){
            continue;
          }
        }
        if(j!=W-1){
          if(s.at(i).at(j+1)=='#'){
            continue;
          }
        }
        cout << "No" << endl;
        return 0;
      }
    }
  }
  cout << "Yes" << endl;
}


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

const ll MAX = 200000;
const ll INF = 1001001001;
const ll MOD = 1000000007;

ll N, ans=0, tmp=0;
string S;
vector<set<ll>> A(26);

signed main(){
    cin >> S;
    for(int i=0;i<S.size();i++) {
        ll id = S[i]-'a';
        A[id].insert(i);
    }
    for(int i=0;i<S.size();i++) {
        ll id = S[i]-'a';
        set<ll>::iterator itr = A[id].upper_bound(i);
        if(itr!=A[id].end()) {
            if(*itr<i+3) {
                cout << i+1 << " " << *itr+1 << endl;
                return 0;
            }
        }
    }
    cout << "-1 -1" << endl;
    return 0;
}

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

int main() {
  int a, b, c, d;
  int count = 0;
  cin >> a >> b >> c >> d;
	while ( (a > 0) && (c > 0)){
      if( ( (count % 2) == 0 ) || (count == 0) ){ 
      	c = c - b;
      }else{
		a = a - d;      
      }
      count++;
    }
  	if(a > 0){
    	cout << "Yes" << endl;
    }else{
      	cout << "No" << endl;
    }
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;


double Length(int x0,int y0,int x1,int y1){
    double res = ( x0 - x1 ) * ( x0 - x1 ) +  ( y0 - y1 ) * ( y0 - y1 );
    res = sqrt(res);
    return res;
}

int factorial( int N ){
    int res = 1;
    for ( int i = 1; i <= N; ++i){
        res = res * i;
    }
    return res;
}

int main(){
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for ( int i = 0; i < N; ++i){
        cin >> x.at(i) >> y.at(i);
    }
    
    vector<int> C(N);
    for ( int i = 0; i < N; ++i){
        C.at(i) = i;
    }
    
    double res_all = 0;
    do {
        double res = 0;
        for ( int i = 0; i < N-1; ++i){
            res += Length(x.at(C.at(i)),y.at(C.at(i)),x.at(C.at(i+1)),y.at(C.at(i+1)));
        }
        //cout << res << endl;
        res_all += res;
    } while ( next_permutation(C.begin(),C.end()) );
    
    //cout << res_all / factorial(N) << endl;
    printf("%10.10f \n", res_all / factorial(N)  );
    
    return 0;
}

Measured memory_bytes: 256
//2020.1.6
//s1270188 xxxmk2
//alds1_07b

#include<stdio.h>
#include<stdlib.h>

//struct
typedef struct{
  int p, l, r;
}node;

//prototype
int depth(int);
int height(int);


//global
node *data;

int main(){
  int i, a, cnt, num;

  //input
  scanf("%d",&num);
  data=(node *)malloc(sizeof(node)*num);
  for(i=0;i<num;i++) data[i].p=-1;
  for(i=0;i<num;i++){
    scanf("%d",&a);
    scanf(" %d %d",&data[a].l,&data[a].r);
    data[data[a].l].p=a;
    data[data[a].r].p=a;
  }

  //output
  for(i=0;i<num;i++){
    printf("node %d: parent = %d, sibling = ",i,data[i].p);
    if(data[i].p==-1) printf("-1, ");
    else if(data[data[i].p].l!=i) printf("%d, ",data[data[i].p].l);
    else printf("%d, ",data[data[i].p].r);

    cnt=0;
    if(data[i].l!=-1) cnt++;
    if(data[i].r!=-1) cnt++;
    printf("degree = %d, depth = %d, height = %d, ",cnt,depth(i),height(i));

    
    if(data[i].p==-1) printf("root\n");
    else if(cnt==0) printf("leaf\n");
    else printf("internal node\n");
  }

  free(data);
  return 0;
}

int depth(int n){
  int d=0;

  for(n=data[n].p;n!=-1;n=data[n].p) d++;

  return d;
}

int height(int n){
  int a=0, b=0;

  if(data[n].l!=-1) a=height(data[n].l)+1;
  if(data[n].r!=-1) b=height(data[n].r)+1;

  if(a>b) return a;
  else return b;
}



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

using namespace std;

int n, ans;
int s[300];
char h[45][12] = {"000","One", "Two", "Three", "Four"};

int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        char a;
        cin>>a;
        s[a]++;
    }
    for(int i=1; i<299; i++) {
        if(s[i]!=0)ans++;
    }
    cout<<h[ans]<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int INF = 100000000;
typedef pair<int, int> P;

struct edge{
	int to;
	int cost;
};

int N, M;
vector<edge> G[100];
int d[100][100], dist[100];

void dijkstra(int s){
	priority_queue<P, vector<P>, greater<P> > que;
	fill(dist, dist+N, INF);
	dist[s] = 0;
	que.push(P(0, s));
	while(!que.empty()){
		P p = que.top();
		que.pop();
		int v = p.second;
		if(dist[v] < p.first) continue;
		for(int i=0; i<G[v].size(); i++){
			edge e = G[v][i];
			if(dist[e.to] > dist[v] + e.cost){
				dist[e.to] = dist[v] + e.cost;
				que.push(P(dist[e.to], e.to));
			}
		}
	}
	for(int i=0; i<N; i++) d[s][i] = dist[i];
}

int main(){
	cin >> N >> M;
	int a[M], b[M], c[M];
	for(int i=0; i<M; i++){
		cin >> a[i] >> b[i] >> c[i];
		a[i]--;
		b[i]--;
		edge e1 = {b[i], c[i]}, e2 = {a[i], c[i]};
		G[a[i]].push_back(e1);
		G[b[i]].push_back(e2);
	}
	for(int i=0; i<N; i++) dijkstra(i);
	int ans = 0;
	for(int i=0; i<M; i++){
		bool flag = true;
		for(int j=0; j<N; j++){
			for(int k=0; k<N; k++){
				if(c[i] + d[j][a[i]] + d[b[i]][k] == d[j][k] || c[i] + d[j][b[i]] + d[a[i]][k] == d[j][k]){
					flag = false;
				}
			}
		}
		if(flag) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long int lli;
vector<lli> h;

int main(void) {
    lli n,A,B;
    scanf("%lld%lld%lld",&n,&A,&B);

    for(int i=0; i<n; i++) {
        lli hh;
        scanf("%lld",&hh);
        h.push_back(hh);
    }

    lli b=0, e=0x7FFFFFFF;
    while(e-b > 1) {
        lli m = (b+e)/2;

        lli sum = 0;
        for(lli t : h) {
            if(t-(m*B) > 0)
                sum += (t-(m*B)+(A-B-1))/(A-B);
            if(sum > m)
                break;
        }

        if(sum > m)
            b = m;
        else
            e = m;
    }
    printf("%lld\n", e);
    return 0;
}

Measured memory_bytes: 1400
/**
 * Author: Behradm
 * Created: 14-04-2020 12:03:03
**/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;

#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define LOCAL

#ifdef LOCAL
	#define debugi(x) cerr << "{" << #x << "}: " << (x) << '\n'
	#define debug(v, begin, end) cerr << "{ | "; for(auto i = begin; i < end; i++){cerr << #v << "[" << i << "]: " << v[i] << " | ";} cerr << " }\n"
	#define debugp(a, b) cerr << "\n{ " << a << " " << b << " }\n"
#else
	#define debugi(x) 42
	#define debug(v, begin, end) 42
	#define debugp(a, b) 42 
#endif

int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cout.precision(6);
	cout << fixed;
	int n;
	cin >> n;
	ll res = 0LL;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			for(int k = 1; k <= n; k++){
				res += __gcd(i, __gcd(j, k));
			}
		}
	}

	cout << res << '\n';
	return 0;
}



Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long
#define F(type, i, a, b) for(type i = a; i <= b; i ++)
#define RF(type, i, a, b) for(type i = a; i >= b;i --)
#define sz(a) sizeof(a)
#define deb(a) cerr<<" ["<<#a<<"->"<<a<<"] "
#define next_line cerr<<'\n'
#define all(a) a.begin(), a.end()
#define iter(it, s) for(auto it = s.begin(); it != s.end(); it ++)

using namespace std;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <typename T>
void tk_input(vector<T> &arr){
    for(T &i: arr)
        cin>>i;
}
ll mod = 1e9 + 7LL;
ll bin_exp(ll x, ll pw){
    ll res = 1LL;
    while(pw ){
        if(pw & 1LL){
            res *= x;
            res %= mod;
        }
        x *= x;
        x %= mod;
        pw >>= 1;
    }
    return res;
}

//1.Check for overflows and don't panic
//
//2.If you cannot think of a solution, try 
//  to think from backwards
void solve()
{
    int n;
    cin>>n;
    ll ans = bin_exp((ll)10, n);
    ans -= bin_exp((ll)9, n);
    ans += mod;
    ans %= mod;
    ans -= bin_exp((ll)9, n);
    ans += mod;
    ans %= mod;
    ans += bin_exp((ll)8, n);
    ans %= mod;
    cout<<ans<<'\n';
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        freopen("Debug.txt", "w", stderr);
    #else
    #endif
        solve();
}

Measured memory_bytes: 3648