akhauriyash/Code-Regression huggingface dataset:
while True:
    n=int(input())
    if n==0:
        break

    s=list(map(float,input().split()))
    n=len(s)
    m=sum(s)/n

    aa = 0

    for e in s:
        aa += (e-m)**2
    
    aa /= n
    aa **=0.5

    print("{:.10f}".format(aa))


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

#define rep(i, a, b) for (int i = (a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (a); i >= (int)(b); i--)
#define all(x) (x).begin(), (x).end()
using i32 = int32_t;
using i64 = int64_t;
using f32 = float;
using f64 = double;
using P = pair<int, int>;

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

template <class T>
void dump_vec(const vector<T>& v) {
    auto len = v.size();
    rep(i, 0, len) {
        cout << v[i] << (i == (int)len - 1 ? "\n" : " ");
    }
}

struct FastIO {
    FastIO() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(20);
    }
} FASTIO;

//---------------------------------------------------------------------------------------------------

//---------------------------------------------------------------------------------------------------

signed main() {
    i64 a, b, c;
    cin >> a >> b >> c;
    auto left = 4 * a * b;
    auto r = c - a - b;
    auto right = r * r;
    bool ok = 0 <= r && left < right;
    cout << (ok ? "Yes" : "No") << "\n";
}


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

signed main(void)
{
	int n;
	cin >> n;
	long long a[n], sum;
	sum = 100000000000;
	rep(i, n) cin >> a[i];
	rep(i, n - 1) a[i + 1] += a[i];
	rep(i, n - 1)
	{
		sum = min(sum, abs(a[i] - (a[n - 1] - a[i])));
	}
	cout << sum << endl;
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll MOD = 1000000007;
int dp[3][100000 + 100];
template <class T>
inline bool chmax(T& a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
int main() {
  int N;
  cin >> N;
  vector<int> a(N), b(N), c(N);
  REP(i, N) cin >> a[i] >> b[i] >> c[i];
  REP(i, N) {
    chmax(dp[0][i + 1], dp[1][i] + a[i]);
    chmax(dp[0][i + 1], dp[2][i] + a[i]);
    chmax(dp[1][i + 1], dp[0][i] + b[i]);
    chmax(dp[1][i + 1], dp[2][i] + b[i]);
    chmax(dp[2][i + 1], dp[0][i] + c[i]);
    chmax(dp[2][i + 1], dp[1][i] + c[i]);
  }
  cout << max(dp[0][N], max(dp[1][N], dp[2][N])) << endl;
}

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

double dp[3010][3010];
int main()
{

    int N;

    cin >> N;
    double p[N];
    for (int i = 0; i < N; i++)
    {
        cin >> p[i];
    }

    dp[0][0] = 1;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            dp[i + 1][j + 1] += dp[i][j] * p[i];
            dp[i + 1][j] += dp[i][j] * (1 - p[i]);
        }
    }

    double res = 0.0;
    for (int j = N / 2 + 1; j <= N; j++)
    {
        res += dp[N][j];
    }
    cout << fixed << setprecision(10) << res << endl;

    return 0;
}

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

using namespace std;

typedef long long ll;

const int NM_MAX = 3002;

const int MOD = 998244353;

int pwr (int a, int b)
{
    if(b == 0)
        return 1;
    if(b & 1)
        return 1LL * a * pwr(a, (b ^ 1)) % MOD;
    int aux = pwr(a, (b >> 1));
    return 1LL * aux * aux % MOD;
}

int inv (int a)
{
    return pwr(a, MOD - 2);
}

int a, b, c, d;

int dp[NM_MAX][NM_MAX][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> a >> b >> c >> d;
    dp[a][b][0] = 1;
    dp[a][b][1] = b;
    for(int i = a; i <= c; i++)
        for(int j = b; j <= d; j++)
            if(i != a || j != b)
            {
                if(i - 1 != a || j != b)
                {
                    dp[i][j][0] += 1LL * dp[i - 1][j][0] * j % MOD;
                    if(dp[i][j][0] >= MOD)
                        dp[i][j][0] -= MOD;
                }
                dp[i][j][0] += dp[i - 1][j][1];
                if(dp[i][j][0] >= MOD)
                    dp[i][j][0] -= MOD;
                dp[i][j][1] += 1LL * dp[i][j - 1][0] * i % MOD;
                if(dp[i][j][1] >= MOD)
                    dp[i][j][1] -= MOD;
                if(i != a || j - 1 != b)
                {
                    dp[i][j][1] += 1LL * dp[i][j - 1][1] * i % MOD;
                    if(dp[i][j][1] >= MOD)
                        dp[i][j][1] -= MOD;
                }
            }
    if(a == c && b == d)
        cout << "1\n";
    else
        cout << (dp[c][d][0] + dp[c][d][1]) % MOD << "\n";
    return 0;
}


Measured memory_bytes: 73880
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>

using namespace std;

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()

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

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};

string S[2];
int main(){
    ios::sync_with_stdio(false);
    int N;
    cin >> N >> S[0] >> S[1];
    ll ans = 1;
    int cur = 0;
    int pre = 0;
    if (S[0][0] == S[1][0]) {
        cur += 1;
        ans = 3;
    } else {
        cur += 2;
        ans = 6;
        pre = 1;
    }
    while (cur < S[0].length()) {
        if (S[0][cur] == S[1][cur]) {
            if (pre) {
                ans *= 1;
            } else {
                ans *= 2;
            }
            cur += 1;
            pre = 0;
        } else {
            if (pre) {
                ans *= 3;
            } else {
                ans *= 2;
            }
            cur += 2;
            pre = 1;
        }
        ans %= INF;
    }
    
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 256
//Merge sort マージソート
#include<stdio.h>

int S[500000], count = 0;

void MergeS(int, int, int);
void Mer(int, int, int, int);

int main(){
  int n, i;

  scanf("%d",&n);
  for(i=0 ; i<n ; i++)scanf("%d",&S[i]);

  MergeS(n, 0, n);

  for(i=0 ; i<n ; i++){
    if(i != 0) printf(" ");
    printf("%d",S[i]);
  }
  printf("\n");
  printf("%d\n",count);

  return 0;
}

void MergeS(int n, int l, int r){
  int m, i;
  if(l+1<r){
    m = (l+r)/2;
    MergeS(n, l, m);
    MergeS(n, m, r);
    Mer(n, l, m, r);
    }
}

void Mer(int n, int l, int m, int r){
  int n1, n2, L[500000], R[500000], k, i, j;

  n1 = m-l;
  n2 = r-m;

  for(i=0 ; i<n1 ; i++)L[i] = S[l+i];

  for(i=0 ; i<n2 ; i++)R[i] = S[m+i];

  L[n1] = 1000000000;
  R[n2] = 1000000000;

  i = 0;
  j = 0;

  for(k=l ; k<=r-1 ; k++){
    count++;
    
    if(L[i]<=R[j]){
      S[k] = L[i];
      i = i+1;
    }
    else{
      S[k] = R[j];
      j = j+1;
    }
  }
}



Measured memory_bytes: 5684
#include<bits/stdc++.h>
using namespace std;
#define re register
#define cmax(a,b) (a<(b)?a=(b):0)
#define dmin(a,b) ((a)<(b)?(a):(b))
#define dmax(a,b) ((a)>(b)?(a):(b))
int b1[1101000],*b[1000100],mi[1000100],bb[16][1100101],lg[1000101],n,m;
long long ans,a[100100];
inline int RMQ(re int a,re int b)
{
	re int l=lg[b-a+1];
	return dmax(bb[l][a],bb[l][b-(1<<l)+1]);
}
void dc(re int l,re int r,re int l1,re int r1)
{
	if(r<l)return;
	re int mid=(l+r)>>1,nw=mid;re long long num=0,an;
	if(r1>=mid-1)
	{
		for(re int i=1;i<=m;i++)mi[i]=b[mid][i],num+=mi[i];an=num;
	}
	else
	{
		for(re int i=1;i<=m;i++)mi[i]=RMQ(i*n-n+r1,i*n-n+mid),num+=mi[i];
		nw=r1;an=num-a[mid]+a[r1];
	}
	for(re int i1=dmin(mid-1,r1);i1>=l1;i1--)
	{
		re int*bl1=b[i1];
		for(re int i=1;i<=m;i++)if(mi[i]<bl1[i])num+=bl1[i]-mi[i],mi[i]=bl1[i];
		if(num-a[mid]+a[i1]>an)an=num-a[mid]+a[i1],nw=i1;
	}if(an>ans)ans=an;
	dc(l,mid-1,l1,nw);dc(mid+1,r,nw,r1);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(re int i=2;i<=n;i++)
	{
		lg[i]=lg[i>>1]+1;
		scanf("%lld",&a[i]);a[i]+=a[i-1];
	}for(re int i=1;i<=n;i++)
	{
		if(i>1)b[i]=b[i-1]+m;
		else b[i]=b1;
		for(re int j=1;j<=m;j++)scanf("%d",&b[i][j]);
	}for(re int i=1;i<=m;i++)for(re int j=1;j<=n;j++)bb[0][i*n-n+j]=b[j][i];
	for(re int i=1;(1<<i)<=n;i++)
	{
		for(re int j=1;j+(1<<i)<=n*m+1;j++)
		{
			bb[i][j]=dmax(bb[i-1][j],bb[i-1][j+(1<<(i-1))]);
		}
	}
	dc(1,n,1,n);
	printf("%lld\n",ans);
}

Measured memory_bytes: 66816
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int n;
vector<int> c;
vector<int> pre;
ll memo[200100];
ll dp(int i){
    if(i == -1) return 1;
    if(i == 1) return 1;
    if(memo[i] != -1) return memo[i];

    ll res = 0;
    if(pre[i] == -1){
        res += dp(i - 1);
    } else {
        int dist = i - pre[i];
        if(dist == 1){
            res += dp(i - 1);
        } else {
            res += dp(pre[i]);
            res += dp(i - 1);
        }
    }
    res %= MOD;
    return memo[i] = res;
}

int main(void){
    cin >> n;
    c.resize(n);
    for(int i = 0; i < n; i++) cin >> c[i];

    for(int i = 0; i <= n; i++){
        memo[i] = -1;
    }

    unordered_map<int,int> mp;
    pre.resize(n, -1);
    for(int i = 0; i < n; i++){
        if(mp.count(c[i])){
            pre[i] = mp[c[i]];
            mp[c[i]] = i;
        } else {
            mp[c[i]] = i;
        }
    }



    cout << dp(n - 1) << endl;
}

Measured memory_bytes: 17864
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main(){
	int n;
	int a,b;
	cin>>n>>a>>b;
	int i;
	int c;
	int k=0;
	double minn=1e9;
	for(i=0;i<n;i++){
		cin>>c;
		double d=a-c*0.006;
		//cout<<fabs(d-b)<<" "<<i<<endl;
		if(fabs(d-b)<minn){
			minn=fabs(d-b);
			k=i;
		}
	}
	cout<<k+1<<endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,K=map(int,input().split())
A=tuple(map(int,input().split()))

def nibutan(ok,ng):
    while abs(ok-ng) > 1:
        mid = (ok + ng) // 2
        if solve(mid):
            ok = mid
        else:
            ng = mid
    return ok

def solve(mid):
    c=0
    for x in A:
        c+=-(-x//mid)-1
    return K>=c

print(nibutan(10**9,0))

Measured memory_bytes: 93892
#include <iostream>
#include <stdio.h>
#include <string>
#include <math.h>
using namespace std;

int main(){
	int n, k, x, y;
	cin >> n;
	cin >> k;
	cin >> x;
	cin >> y;
	int ans;
	
	if(n<=k) ans = n*x;
	else ans = k*x+(n-k)*y;
	
	printf("%d\n", ans);
	
	return 0;
}

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

int main(){
    int n;
    string s1,s2;
    int a = 0,b=0;
    cin >>n;
    
    for(int i =0;i<n;i++){
        cin >> s1>>s2;
        if(s1>s2)a+=3;
        else if(s1<s2)b+=3;
        else{
            a++;b++;
        }
    }
    cout << a<< " "<<b<<endl;
    
    return 0;
}


Measured memory_bytes: 3156
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <functional>
#include <math.h>
#include <numeric>
#include <stdio.h>
#include <cstdio>

using namespace std;

int main(){
    int n , a , b;
    float sum = 0;
    vector<float> vsum;
    vector<float> x;
    vector<float> y;
    vector<int> count;
    cin >> n;
    for (int i = 0; i < n; i++){
        count.push_back(i);
        cin >> a >> b;
        x.push_back(a);
        y.push_back(b);
    }
    do{
        for (int i = 0; i < n -1; i++){
            sum += sqrt( pow(x.at(count.at(i)) - x.at(count.at(i + 1)), 2.0) +
                        pow(y.at(count.at(i)) - y.at(count.at(i + 1)), 2.0)
                        );
        }
        vsum.push_back(sum);
        sum = 0.0;
    } while( next_permutation(count.begin(), count.end()));
   
    printf("%10f" , float(accumulate(vsum.begin(), vsum.end(), 0.0)) / float(vsum.size()));
    
}


Measured memory_bytes: 640
//start of jonathanirvings' template v3.0.3 (BETA)

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

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int n;
map<int,int> ada;
int x;
vector<int> bisa;

int main()
{
  scanf("%d",&n);
  TC(n)
  {
    scanf("%d",&x);
    ++ada[x];
    if (ada[x] == 2) 
    {
      bisa.pb(x);
      ada[x] = 0;
    }
  }
  SORT(bisa);
  REVERSE(bisa);
  if (SIZE(bisa) > 1) printf("%lld\n",(LL)bisa[0] * bisa[1]);
  else puts("0");
  return 0;
}










Measured memory_bytes: 4992
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <iostream>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
using namespace std;

typedef long long ll;

template<typename T>
struct BIT {
  vector<T> data;
  BIT() {}
  BIT(int n) : data(n+1, 0) {}
  void init(int n) { data.assign(n+1, 0); }
  T sum(int ed) const {
    for(T res(0); ; ed &= ed-1) if(ed) res += data[ed]; else return res;
  }
  T total(void) const { return sum(data.size()-1); }
  void add(int i, const T& x) {
    for(++i; i < (int)data.size(); i += i&-i) data[i] += x;
  }
};
template<typename T> struct Compression {
  vector<T> idx2orig;
  Compression(const vector<T>& values): idx2orig(values) {
    sort(idx2orig.begin(), idx2orig.end());
    idx2orig.erase(unique(idx2orig.begin(), idx2orig.end()), idx2orig.end());
  }
  int toIndex(const T& orig) const { return lower_bound(orig); }
  int fromIndex(int idx) const { assert(0 <= idx && idx < (int)idx2orig.size()); return idx2orig[idx]; }
  int size(void) const { return idx2orig.size(); }
  int lower_bound(const T& orig) const { return std::lower_bound(idx2orig.begin(), idx2orig.end(), orig) - idx2orig.begin(); }
  int upper_bound(const T& orig) const { return std::upper_bound(idx2orig.begin(), idx2orig.end(), orig) - idx2orig.begin(); }
};

int n;
int xs[100000+10];
int vs[100000+10];
int cs[100000+10];

bool isOK(int md) {
  cs[0] = 0;
  REP(i, n) {
    vs[i] = xs[i] < md ? -1 : 1;
    cs[i+1] = cs[i] + vs[i];
  }
  vector<int> vvs;
  REP(i, n+1) {
    vvs.push_back(cs[i]);
  }
  Compression<int> c(vvs);
  REP(i, n+1) {
    cs[i] = c.toIndex(cs[i]);
  }
  const ll threshold = ll(n+1)*n/2/2;
  ll tr = 0;
  BIT<int> bit(c.size()+10);
  REP(i, n+1) {
    tr += bit.total() - bit.sum(cs[i]+1);
    bit.add(cs[i], 1);
  }
  return tr <= threshold;
}

int main(void) {
  scanf("%d", &n);
  REP(i, n) {
    scanf("%d", &xs[i]);
  }

  int left = 0;
  int right = 1000000001;
  while(left+1 < right) {
    int md = (left+right) / 2;
    if(isOK(md)) {
      left = md;
    } else {
      right = md;
    }
  }
  printf("%d\n", left);
  return 0;
}


Measured memory_bytes: 2772
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
#include <cassert>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef unsigned long long int ull;

int main(int argc,char** argv) {
	int n;
	cin >> n;
	if(n % 10 == n / 100) cout << "Yes";
	else cout << "No";
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MN 5000
#define MOD 1000000007
vector<int> v[MN+5];
int f[MN+5][MN+5],ff[MN+5],F[MN+5],s[MN+5];
void dfs(int x,int fa)
{
	f[x][1]=1;s[x]=1;
	for(int i=0;i<v[x].size();++i)if(v[x][i]!=fa)
	{
		dfs(v[x][i],x);
		for(int j=1;j<=s[x];++j)ff[j]=f[x][j],f[x][j]=0;
		for(int j=1;j<=s[x];++j)for(int k=0;k<=s[v[x][i]];++k)
			f[x][j+k]=(f[x][j+k]+1LL*ff[j]*f[v[x][i]][k])%MOD;
		s[x]+=s[v[x][i]];
	}
	for(int i=1;i<=s[x];++i)f[x][0]=(f[x][0]+MOD-1LL*f[x][i]*F[i]%MOD)%MOD;
}
int main()
{
	int n,i,x,y;
	scanf("%d",&n);
	for(F[0]=1,i=2;i<=n;i+=2)F[i]=1LL*F[i-2]*(i-1)%MOD;
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1,0);
	printf("%d",(MOD-f[1][0])%MOD);
}

Measured memory_bytes: 97408
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //        int n = sc.nextInt();

        char[] ary = sc.next().toCharArray();
        int ans = 0;

        for (int i = 0; i < 4; i++) {
            if (ary[i] == '+') {
                ans++;
            } else {
                ans--;
            }
        }

        sc.close();

        System.out.println(ans);
    }
}

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

const int N = 2000010;
const int SIGMA = 26;
using ll = long long;

int go[N][SIGMA];
int vis[N][SIGMA];
bool end[N];
int tot[N];
int sz;
std::string s[N];
char input[N];

int newnode(){
    return ++ sz;
}

void insert(int p, char *s){
    while (*s != '\0'){
        int ch = *s - 'a';
        if (!go[p][ch]){
            go[p][ch] = newnode();
        }
        p = go[p][ch];
        ++ s;
    }
    end[p] = true;
}

void dfs(int u){
    tot[u] = end[u];
    for (int i = 0; i < SIGMA; ++ i){
        int v = go[u][i];
        if (v){
            dfs(v);
            for (int j = 0; j < SIGMA; ++ j){
                if (j == i){
                    vis[u][j] += tot[v];
                }
                else{
                    vis[u][j] += vis[v][j];
                }
            }
            tot[u] += tot[v];
        }
    }
}

ll ans;

void solve(int u){
    if (!u){
        return;
    }
    for (int i = 0; i < SIGMA; ++ i){
        int v = go[u][i];
        if (end[v]){
            ans += vis[u][i] - 1;
        }
        solve(v);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    int root = newnode();
    for (int i = 0; i < n; ++ i){
        scanf("%s", input);
        int len = strlen(input);
        std::reverse(input, input + len);
        s[i] = input;
        insert(root, input);
    }
    dfs(root);
    solve(root);
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 332856
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func min(a, b int) int {
	if a < b {
		return a
	} else {
		return b
	}
}

func main() {
	sc.Split(bufio.ScanWords)

	s := next()
	n := nextInt()

	ss := make(map[string]struct{})
	for i := 0; i < len(s); i++ {
		for j := i+1; j <= min(i+n, len(s)); j++ {
			ss[s[i:j]] = struct{}{}
		}
	}

	var keys []string
	for k := range ss {
		keys = append(keys, k)
	}

	sort.Strings(keys)

	fmt.Println(keys[n-1])
}

Measured memory_bytes: 3200
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

type work struct{ time, limit int }
type works []work

func (w works) Len() int      { return len(w) }
func (w works) Swap(i, j int) { w[i], w[j] = w[j], w[i] }
func (w works) Less(i, j int) bool {
	if w[i].limit == w[j].limit {
		return w[i].time < w[j].time
	}
	return w[i].limit < w[j].limit
}

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

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	var ws works = make([]work, n)
	for i := range ws {
		sc.Scan()
		ws[i].time, _ = strconv.Atoi(sc.Text())
		sc.Scan()
		ws[i].limit, _ = strconv.Atoi(sc.Text())
	}

	sort.Sort(ws)
	sum := 0
	for _, w := range ws {
		sum += w.time
		if sum > w.limit {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 6272
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define dbg(x) cerr << #x << " = " << x << endl
#define _ << ' ' <<
using namespace std;
using ll = long long;
using vi = vector<int>;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int a = n / 100, b = n % 100;
    bool x = (a > 0 && a <= 12), y = (b > 0 && b <= 12);
    if (x && y)
        cout << "AMBIGUOUS";
    else if (x)
        cout << "MMYY";
    else if (y)
        cout << "YYMM";
    else
        cout << "NA";
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100000 + 2;
int N, M, height[MAX_N], cnt = 0;
vector<int>adj[MAX_N];
bool visited[MAX_N] = { 0, };

int main()
{
	cin >> N >> M;
	vector<pair<int, int>>v;
	for (int i = 1; i <= N; i++)
	{
		cin >> height[i];
		v.push_back({ -height[i],i });
	}
	while (M--)
	{
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	sort(v.begin(), v.end());
	for (auto i : v)
	{
		int h = -i.first, idx = i.second;
		if (visited[idx])continue;
		visited[idx] = true;
		bool isGood = true;
		for (auto next : adj[idx])
		{
			if (h <= height[next])
			{
				isGood = false;
				break;
			}
			visited[next] = true;
		}
		if (isGood)cnt++;
	}
	cout << cnt;
}

Measured memory_bytes: 9700
# include<iostream>
# include<vector>
#include<algorithm>
#include<cstdlib>
using namespace std;

int main(){
    int n;cin >> n;
    vector<int> a(n);
    vector<int> dp(n,0);
    for(int i =0;i<n;i++){
        cin >> a[i];
    }
    dp[0] = 0;dp[1] = abs(a[1]-a[0]);
    for(int l=2;l<n;l++){
        dp[l] = min(dp[l-1]+abs(a[l]-a[l-1]), dp[l-2]+abs(a[l]-a[l-2]));
    }
    cout << dp[n-1] << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define N 200001
#define ll long long
#define pi pair<int , int>
#define pip pair<pi ,int>
#define mp make_pair 
#define f first
#define s second
#define int ll 
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
// this is triplet class , which will help us .
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
// this is for finding inversing multiplicative module of a number.
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return ans.x;
}
int getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
      lps[i] = j+1;
   i++;
   j++;
  }
  else{
        if(j != 0){
         j = lps[j-1];
        }
        else{
         lps[i] = 0;
         i++;
        }
  }
 }
 return lps[len-1];
}


int32_t main(){
   ios_base::sync_with_stdio(false);
      cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin>>n;
    string str;
    cin>>str;

    int idx = -1;
    int ans = n;
    int r = 0 , w = 0;
    for(int i = 0 ; i < n ; i++){
          if(str[i] == 'W')w++;
          else
            r++;
    }
    ans =min({r , w , ans});
    if(ans == 0){
        cout<<ans<<endl;
        return 0;
    }
    int cnt = 0;
    for(int i = n-1 ; i >= n-w ; i--){
           if(str[i] == 'W')cnt++;
    }
    cout<<w-cnt<<endl;
    
}

Measured memory_bytes: 3700
#include <iostream>
using namespace std;
 int main() {
   int A, B;
    cin >> A >> B;
     if (A == B){
       cout << "Draw" <<endl;
     } else if (A == 1) {
      cout << "Alice" <<endl;
     } else if (B == 1) {
       cout << "Bob" <<endl;
     } else if (A > B) {
      cout << "Alice" <<endl;
     } else if (A < B) {
       cout << "Bob" <<endl;
     }
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<cmath>
#include<map>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<b;i++)
int main() {
	int N, c = 0;
	scanf("%d", &N);
	char* s = new char[N + 1];
	scanf("%s", s);
	vector<int>a(N);
	rep(i, 0, N)a[i] = s[i] - '0';
	rep(i, 0, 1000) {
		int v1 = i / 100, v2 = i / 10 % 10, v3 = i % 10, k1, k2, k3;
		for (k1 = 0; k1 < N; k1++)if (a[k1] == v1)break;
		for (k2 = k1 + 1; k2 < N; k2++)if (a[k2] == v2)break;
		for (k3 = k2 + 1; k3 < N; k3++)if (a[k3] == v3) {c++; break; }
	}
	printf("%d", c);
	return 0;
}

Measured memory_bytes: 384
#include<iostream>
using namespace std;
typedef struct ginko{
  int x, y;
}ginko;

bool is_prime(ginko g){
  int prime = 0;
  for (int i = -200; i < 200; i++) {
    for (int j = -200; j < 200; j++) {
      if(i == 0 && j == 0)continue;
      int divisor = i*i + j*j;//i is m, j is n, p is g.x, q is g.y
      
      if((g.x*i + j*g.y)%divisor == 0 &&
         (g.y*i - j*g.x)%divisor == 0){
        prime++;
        //std::cout << i << " "  << j<< std::endl;
      }
    }
  }
  if(prime > 8){
    return false;
  }else{
  return true;
  }
}

  
int main(int argc, char *argv[]){
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    ginko g;
    cin >> g.x >> g.y;
    if(is_prime(g)){
      std::cout << "P" << std::endl;
    }else{
      std::cout << "C" << std::endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    
    int a,b;
    
    cin >> a >> b;
    
    if(a * b % 2 == 0){
        
        cout << "Even" << endl;
        
    }else{
        
        cout << "Odd" << endl;
        
    }
}

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

using namespace std;

int main() {
    int ABCD;
    cin >> ABCD;
    int D = ABCD % 10;
    ABCD /= 10;
    int C = ABCD % 10;
    ABCD /= 10;
    int B = ABCD % 10;
    ABCD /= 10;
    int A = ABCD % 10;

    if(A + B + C + D == 7)
        cout << A << "+" << B << "+" << C << "+" << D;
    else if(A + B + C - D == 7)
        cout << A << "+" << B << "+" << C << "-" << D;
    else if(A + B - C + D == 7)
        cout << A << "+" << B << "-" << C << "+" << D;
    else if(A + B - C - D == 7)
        cout << A << "+" << B << "-" << C << "-" << D;
    else if(A - B + C + D == 7)
        cout << A << "-" << B << "+" << C << "+" << D;
    else if(A - B + C - D == 7)
        cout << A << "-" << B << "+" << C << "-" << D;
    else if(A - B - C + D == 7)
        cout << A << "-" << B << "-" << C << "+" << D;
    else if(A - B - C - D == 7)
        cout << A << "-" << B << "-" << C << "-" << D;
    cout << "=7" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <deque>
#include <queue>

using namespace std;

template <class T>
bool chmin(T &x, T y)
{
    return x>y ? (x=y, true) : false;
}
template <class T>
bool chmax(T &x, T y)
{
    return x<y ? (x=y, true) : false;
}

main()
{
    int n,x,y; cin>>n>>x>>y; --x,--y;
    vector<vector<int>> g(n);
    for(int i=0;i<n-1;++i)
    {
        g[i].emplace_back(i+1);
        g[i+1].emplace_back(i);
    }
    vector<int> ans(n);
    g[x].emplace_back(y);
    g[y].emplace_back(x);
    for(int i=0;i<n;++i)
    {
        queue<int> que;
        que.emplace(i);
        vector<int> dist(n,n);
        dist[i]=0;
        while(!que.empty())
        {
            int f=que.front(); que.pop();
            for(int v: g[f])
            {
                if(chmin(dist[v], dist[f]+1))
                {
                    que.emplace(v);
                }
            }
        }
        for(int d:dist) ans[d]++;
    }

    ans.erase(ans.begin());
    for(auto e: ans) cout << e/2 << "\n";
}

Measured memory_bytes: 384
#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()
typedef long long ll;
const int MOD = (int)1e9 + 7;

int main(){
  int n,k;
  cin >> n >> k;
  double prob = 0.0;

  rep(i,n){
    int point = i+1;
    double buf = 1.0/n;
    while(point<k){
      point *= 2;
      buf /= 2; 
    }
    prob += buf;
  } 
cout<<setprecision(12)<<(prob)<<endl;
}


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

#define endl "\n"
#define INF (int) 9e18
#define HELL (int) (1e9 + 7)
#define int long long
#define double long double
#define uint unsigned long long
#define deb(x) cerr << #x << " => " << x << "\n"
#define deba(x) cerr << #x << "\n"; for (auto a : x) cerr << a << " "; cerr << "\n";
#define debm(x) cerr << #x << "\n"; for (auto a : x){for(auto b : a) cerr << b << " "; cerr << "\n";}
#define getMat(x, n, m, val) vector<vector<int>> x(n, vector<int> (m, val))
#define fastio ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define pout cout << fixed << setprecision(10)

int fastpow(int a, int b, int m) {
    int res = 1; a %= m; while (b > 0) {
        if (b & 1) res = (res * a) % m;
        a = (a * a) % m; b >>= 1;
    } return res;
}

int now() {
    return chrono::duration_cast<chrono::milliseconds>(chrono::system_clock::now()
    .time_since_epoch()).count();
}

int32_t main() { fastio;
    time_t start = now();

    int n, p; cin >> n >> p;
    string s; cin >> s;
    int res = 0;
    if (p == 2 or p == 5) {
        for (int i = 0; i < n; i++) {
            if ((s[i] - '0') % p == 0) {
                res += i + 1;
            }
        }
    } else {
        map<int, int> H;
        H[0]++;
        int base = 1, val = 0;
        for (int i = n - 1; i >= 0; i--) {
            val = (val + (s[i] - '0') * base) % p;
            base = (base * 10) % p;
            res += H[val];
            H[val]++;
        }
    }
    cout << res << endl;

    cerr << "TIME => " << now() - start << endl;
    return 0;
}

Measured memory_bytes: 1044
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main (){
  int q,x;
  set<int> a,b;
  vector<int> result;

  cin >> q;

  for (int i = 0; i < q; i++){
    cin >> x;
    a.insert(x);
  }

  cin >> q;

  for (int i = 0; i < q; i++){
    cin >> x;
    b.insert(x);
  }
  set_symmetric_difference(begin(a),end(a),begin(b),end(b),inserter(result,end(result)));

  for_each(begin(result), end(result), [](int x) {
    cout << x << endl;
  });
  return 0;
}



Measured memory_bytes: 23756
import java.io.PrintWriter
import java.util.*

fun main(args: Array<String>) {
    PrintWriter(System.out).use { out ->
        solve(out)
        out.flush()
    }
}

fun solve(out: PrintWriter) {
    val (x, y, a, b, c) = readIntegerList()
    val pList = readLongList().sortedDescending().dropLast(a - x)
    val qList = readLongList().sortedDescending().dropLast(b - y)
    val rList = readLongList().sortedDescending()
    val queue = PriorityQueue<Long>()
    queue += pList
    queue += qList
//    println(queue.size)
    var eatR = 0
    var ans = 0L
//    println(queue.joinToString(" "))
    while (queue.isNotEmpty()) {
        val eat = queue.remove()
//        println("current $eat")
        if (eatR < c && eat < rList[eatR]) {
//            println("eat whilte ${rList[eatR]}")
            ans += rList[eatR]
            eatR++
        } else {
//            println("eat $eat")
            ans += eat
        }
//        println("-----------")
    }

    println(ans)
}

fun readInteger() = readLine()!!.toInt()
fun readLong() = readLine()!!.toLong()
fun readStringList() = readLine()!!.split(" ")
fun readIntegerList() = readStringList().map(String::toInt)
fun readLongList() = readStringList().map(String::toLong)
fun readDoubleList() = readStringList().map(String::toDouble)


Measured memory_bytes: 106348
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


l, r, d = zz()
ans = 0
for i in range(l, r+1):
    if(i % d == 0):
        ans += 1
print(ans)


Measured memory_bytes: 26872
#include<iostream>

int main(){
	
	int x,y,k;
	
	while (1){
		
		std::cin >>x>>y;
		if (x==0 && y ==0)break;
		else if (x>y) k=x, x=y, y=k;
		std::cout << x <<" "<< y <<"\n";		
		
	}
	
	return 0;
	
}

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

int main(){
	int N;
	cin >> N;
	long long ans;
	
	vector<long long> A(N),B(N);
	for(int i=0;i<N;i++)cin >> A[i] >> B[i];
	
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	
	if(N%2){
		ans=B[N/2]-A[N/2]+1;
	}else{
		ans=(B[N/2]+B[N/2-1])-(A[N/2]+A[N/2-1])+1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 6428
# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 21:11:28 2020

@author: Kanaru Sato
"""

k,n = list(map(int, input().split()))
a = list(map(int, input().split()))
dl = []

for i in range(n-1):
    d = a[i+1]-a[i]
    if d > k/2:
        d = k-d
    dl.append(d)

d = a[n-1]-a[0]
if d > k/2:
    d = k-d
dl.append(d)

ans = k-max(dl)

print(ans)

Measured memory_bytes: 25836
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;
#define RET(ans) {cout<<ans<<endl;return 0;} 

    // 二次元ベクターの基本
    /*
    vector<vector<int>> dp; // 宣言
    dp.resize(n); // 1次元めの要素数決定
    dp[i].push_back(int); // プッシュバック
    rep(i,n){
        sort(dp[i].begin(),dp[i].end()); // 二次元めを昇順ソート
    }
    */

    // 整数スキャン（複数）
    /*
    int x,y,z;
    scanf("%d%d%d",&x,&y,&z);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s; cin >> s;
    */

    // n個の文字列スキャン
    /*
    vector<string> slist;
    rep(i,n){
        string s; cin >> s;
        slist.push_back(s);
    }
    */

int main() {
    int n;
    cin >> n;
    string s,t; cin >> s >> t;

    drep(i,n+1){
        int flag = 0;
        rep(j,i){
            if(s[n-i+j]!=t[j]){
                flag = 1;
                break;
            }
        }
        if(flag==0){
            cout << n*2 - i << endl;
            return 0;
        }
    }



    return 0;
}
 
 


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

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

#define MAX 10000

int n;
pair<int, int> d[MAX];
vector<int> e[MAX];
int c[MAX], w[MAX], k;

void dfs(int s){
	w[s]=c[k];
	k++;
	for(int i=0; i<e[s].size(); i++){
		if(w[e[s][i]]==0){
			dfs(e[s][i]);
		}
	}
	return;
}

int main(){
	cin >> n;
	for(int i=0; i<n; i++){
		d[i].first=0;
		d[i].second=i;
	}
	for(int i=0; i<n-1; i++){
		int a, b;
		cin >> a >> b;
		a--; b--;
		e[a].push_back(b);
		e[b].push_back(a);
		d[a].first++;
		d[b].first++;
	}
	for(int i=0; i<n; i++) cin >> c[i];
	sort(d, d+n, greater<pair<int, int>>());
	sort(c, c+n, greater<int>());

	for(int i=0; i<n; i++){
		if(w[i]==0){
			dfs(i);
		}
	}

	int ans=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<e[i].size(); j++){
			ans+=min(w[i], w[e[i][j]]);
		}
	}
	cout << ans/2 << endl;
	for(int i=0; i<n; i++) cout << w[i] << " ";
	cout << endl;
	return 0;
}

Measured memory_bytes: 1280
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define rg register
#define LL long long
#define __space putchar(' ')
#define __endl putchar('\n')
template <typename qwq> inline void read(qwq &x)
{
	x = 0;
	rg LL f = 1;
	rg char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-') f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		x = (x << 1) + (x << 3) + (c ^ 48);
		c = getchar();
	}
	x *= f;
}
template <typename qaq> inline void print(qaq x)
{
	if (x < 0)
	{
		putchar('-');
		x = -x;
	}
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
int r;
int main()
{
	read(r);
	print(3 * r * r);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v).begin(), (v).end()
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)
#define DEBUG
#define int long long
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }
template<class T>void show(vector <T> v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<"\n";}
typedef long long ll;

bool graph[10][10];
signed main(){
    int n,m;
    cin>>n>>m;
    
   // graph.assign(n,vector<int>());
    for (int i = 0; i < m; i++)
    {
        int a,b;
        cin>>a>>b;
        a--,b--;
        graph[a][b]=true;
        graph[b][a]=true;
        
    }
    vector<int>v;
    REP(i,n) v.push_back(i);
    int cnt=0;
    do{
        
        if(v[0]!=0) continue;
        bool flag=true;
        for (int i = 0; i < n-1; i++)
        {
           if(!graph[v[i]][v[i+1]]){
               flag=false;
               break;
           }
            
        }
        if(flag) cnt++;


    }while(next_permutation(ALL(v)));
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 256
use std::collections::*;
use std::vec::Vec;
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)*}
    };
}

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)*}
    };
}

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, usize1) => {
        read_value!($next, usize) - 1
    };

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

fn main() {
    input!{
        n: usize,
        m: usize,
        py: [(usize1, usize); m],
    }
    let mut city_infos = vec![BTreeMap::new(); n];

    for (i, &(p, y)) in py.iter().enumerate() {
        city_infos[p].insert(y, i);
    }
    let mut result = vec![String::new(); m];
    for (p, city_ordered) in city_infos.iter().enumerate() {
        let mut count = 0;
        for idx in city_ordered.values() {
            count += 1;
            result[*idx] = format!("{:06}{:06}", p + 1, count);
        }
    }
    for id in result {
        println!("{}", id);
    }
}


Measured memory_bytes: 38396
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<vector>
#include<stack>
#include<queue>
#include<iostream>

using namespace std;
long long int sum[9];
int main(void)
{
	char name[10];
	int toku[9][9],n,make,kati,hiki,touroku[9];
	int flg[10];
	while(1) {
		cin>>n;
		if(n==0) break;
		for(int i=0;i<n;i++) {
			cin>>name[i];
			for(int j=0;j<n-1;j++) {
				cin>>toku[i][j];
			}
		}
		for(int i=0;i<n;i++) {sum[i]=0;touroku[i]=0;}
		for(int i=0;i<n;i++) {
			kati=0;make=0;
			for(int j=0;j<n-1;j++) {
				if(toku[i][j]==0) kati++;
				if(toku[i][j]==1) make++;
			}	
			sum[i]=kati*100000000+(make*-1);
		}
		for(int i=0;i<n;i++) touroku[i]=sum[i];
		sort(sum,sum+n,greater<int>());
		for(int i=0;i<n;i++) flg[i]=0;
		for(int i=0;i<n;i++) {
			for(int j=0;j<n;j++) {
				if(sum[i]==touroku[j] && flg[j]==0) {
					cout<<name[j]<<endl;
					flg[j]=1;
					break;
				}
			}
		}
	}
}

Measured memory_bytes: 1172
N = int(input())
cnt = 0

if N == 100000:
    N = 99999
while (10000 <= N < 100000):
    N = N - 1
    cnt += 1
if 1000 <= N < 10000:
    N = 999
while (100 <= N < 1000):
    N = N - 1
    cnt += 1
if 10 <= N < 100:
    N = 9
while (1 <= N < 10):
    N = N - 1
    cnt += 1

print(cnt)


Measured memory_bytes: 38512
# -*- coding: utf-8 -*-

import numpy as np #1.11.0
#import matplotlib as plt #1.5.1
import copy 
import math

a = []
for i in range(3):
  b = list(map(int, input().strip().split(' ')))
  a.append(b)

flag = 0

for i in range(2):
  for j in range(2):
    if (a[i + 1][j] - a[i][j]) != (a[i + 1][j + 1] - a[i][j + 1]):
      flag = 1
  
for i in range(2):
  for j in range(2):
    if (a[i][j + 1] - a[i][j]) != (a[i + 1][j + 1] - a[i + 1][j]):
      flag = 1

if flag == 0:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 12504
/* https://tenka1-2019-beginner.contest.atcoder.jp/tasks/tenka1_2019_a */

#include <iostream>
#include <vector>

/* {{{ Variables */
int A, B, C;
/* }}} */

int main(int argc, char *argv[])
{
  /* {{{ Input */
  std::cin >> A >> B >> C;
  /* }}} */

  /* {{{ Output */
  if ((A < C && C < B) || (B < C && C < A)) {
    std::cout << "Yes" << std::endl;
  } else {
    std::cout << "No" << std::endl;
  }
  /* }}} */

  return 0;
}


Measured memory_bytes: 256
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()))

P.sort()
Q.sort()

all_apples = []
for i in range(max(X,Y,C)):
  if(i<X):
    all_apples.append([P[-(i+1)],'r'])
  if(i<Y):
    all_apples.append([Q[-(i+1)],'g'])
  if(i<C):
    all_apples.append([R[i],'any'])

all_apples.sort()

ans = 0
for i in range(X+Y):
 ans += all_apples[-(i+1)][0]
print(ans)

Measured memory_bytes: 45360