akhauriyash/Code-Regression huggingface dataset:
// Last Change: 05/06/2019 19:21:54.
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

namespace NS {
void LoopUntilZeroInpput() {
  int hogegegege = 0;
  while (cin >> hogegegege && hogegegege != 0) {
  }
}
} // namespace NS

class UnionFind {
private:
  // firstは親、secondはサイズ
  // 正しいサイズ情報は親(根)のみが持つ
  vector<pair<long long, long long>> vec;

private:
  long long FindRoot(long long ipt) {
    if (vec[ipt].first == ipt) {
      return ipt;
    } else {
      vec[ipt].first = FindRoot(vec[ipt].first);
      return vec[ipt].first;
    }
  }

public:
  UnionFind() = delete;
  UnionFind(const UnionFind &another) = delete;
  UnionFind(long long size) {
    vec.resize(size);
    for (long long i = 0; i < size; ++i) {
      vec[i].first = i;
      vec[i].second = 1;
    }
  }

  bool Same(long long a, long long b) {
    return FindRoot(a) == FindRoot(b);
  }

  void Union(long long a, long long b) {
    long long x = FindRoot(a);
    long long y = FindRoot(b);
    vec[y].first = x;
    vec[x].second += vec[y].second;
  }

  long long Size(long long a) {
    return vec[FindRoot(a)].second;
  }
};

int main() {
  ll N, M;
  cin >> N >> M;
  UnionFind unf(N);

  vector<ll> ans(M + 1);
  vector<pair<ll, ll>> bridge(M);
  for (auto &&e : bridge) {
    cin >> e.first >> e.second;
    --e.first;
    --e.second;
  }

  ans[M] = N * (N - 1) / 2;
  for (ll i = M - 1; i >= 0; --i) {

    if (unf.Same(bridge[i].first, bridge[i].second)) {
      ans[i] = ans[i + 1];
    } else {
      ans[i] =
          ans[i + 1] - unf.Size(bridge[i].first) * unf.Size(bridge[i].second);
      unf.Union(bridge[i].first, bridge[i].second);
    }
  }

  for (ll i = 1; i <= M; ++i) {
    cout << ans[i] << endl;
  }

  //NS::LoopUntilZeroInpput();
}


Measured memory_bytes: 5248
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define Rep(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define Repr(i, b, e) for(int (i) = (b) - 1; (i) >= (e); --(i))
#define Print(x) cout << (x) << endl 
#define Min2(a, b) ((a) < (b)) ? (a) : (b)
#define Max2(a, b) ((a) > (b)) ? (a) : (b)

typedef long long ll;

using namespace std;

int N;
string s[10000];

int countAB(string str, int l){
    int cnt = 0;
    Rep(i, 0, l - 1){
        if(str[i] == 'A' && str[i + 1] == 'B') cnt++;
    }
    return cnt;
}

int main(){
    cin >> N;
    int cnt = 0, cA = 0, cB = 0, cC = 0, l = 0;
    string str;
    Rep(i, 0, N) cin >> s[i];
    Rep(i, 0, N){
        str = s[i];
        l = (int)str.length();
        cnt += countAB(str, l);
        if(str[0] == 'B') cB++;
        if(str[l - 1] == 'A') cA++;
        if(str[0] == 'B' && str[l - 1] == 'A') cC++;
    }
    int ans = Min2(cnt + cA, cnt + cB);
    if(cA == cB && cB == cC && cC > 0) ans--;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 768
package main

import "fmt"

func main() {
	var K, S int
	fmt.Scan(&K, &S)
	ans := 0
	for x := 0; x <= K; x++ {
		for y := 0; y <= K; y++ {
			z := S - (x + y)
			if 0 <= z && z <= K {
				ans++
			}
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 1784
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define PI 3.14159265359
#define INF 1000100100
#define MOD 1000000007
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define P pair<ll,ll>
#define PP pair<P,P>
using namespace std;

int main(){
    long double a,b; cin >> a >> b;
    long double ans=a*b;
    ll ans2=(ll)(ans/1);
    cout << ans2 << endl;
return 0;
}


Measured memory_bytes: 3732
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
priority_queue<long long>q;
long long n,k,h,c;
int main()
{
	scanf("%lld%lld",&n,&k);
	for(long long i=1; i<=n; i++)
	{
		scanf("%lld",&h);
		q.push(h);
	}
	for(long long i=0; i<k; i++)
	{
		if(q.empty())
			break;
		q.pop();
	}
	while(!q.empty())
	{
		c+=q.top();
		q.pop();
	}
	printf("%lld",c);
	return 0;
}



Measured memory_bytes: 2420
#include<iostream>
#include<climits>
#include<math.h>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<stdio.h>
#include <string>
#include <complex>
#include <functional>
#include <map>
#include <queue>
using namespace std;
using ll = long long;
//typedef pair<string,string> P;
//double dat[100][100];
//int dp[6][1010];//動的計画法
//int prime[100001];
//char str[1010][1010];
//typedef pair<ll,ll> A;
//vector<A> pc;
//int ABS(int a){return max(a,-a);}
int main() {
  int a,b,t;
  cin>>a>>b>>t;
  int ans;
  ans=t/a*b;
  cout<<ans;
  return 0;
}

Measured memory_bytes: 256
def get_gcd(x, y):
    if x < y:
        y, x = x, y

    while y > 0:
        r = x % y
        x = y
        y = r

    return x

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

a, b = map(int, input().split())
gcd = get_gcd(a, b)
common_divisors = prime_factorize(gcd)
print(len(set(common_divisors)) + 1)

Measured memory_bytes: 3064
import numpy as np

n,m = list(map(int, input().split()))
a = np.array(list(map(int, input().split())))
b=np.sum(a)
a_sort=np.sort(a)[::-1]
if a_sort[m-1]<b/(4*m):
  print("No")
else:
  print("Yes")

Measured memory_bytes: 13056
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define si(X) scanf("%d", &(X))
#define sll(X) scanf("%lld",&(X))
#define INFL 0x3f3f3f3f3f3f3f3fLL
const ll mod = 1e9 + 7;
const int M = 2e6 + 5;
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll expo(ll base,ll pow){ll ans = 1;
   if(pow < 0) return 0;
   while(pow!=0){if(pow&1==1){ans = ans*base;ans = ans%mod;}
   base *= base;base%=mod;pow/=2;}return ans;}
ll inv(ll x){return expo(x,mod-2);}
ll mult_mod(ll a , ll b){a = a%mod; b = b%mod;ll c = (a * b)%mod;return c;}
ll add_mod(ll a , ll b){a = (a + mod)%mod;b = (b + mod)%mod;ll c = (a + b)%mod;return c;}
ll fac[(int)(2e6 + 7)] , inv_fac[(int)(2e6 + 7)];
void precomp_factorial(){fac[0] = 1;for(ll i = 1 ; i <= M ; i++) fac[i] = mult_mod(i , fac[i - 1]);
    inv_fac[M] = inv(fac[M]);for(ll i = M - 1 ; i >= 0 ; i--) inv_fac[i] = mult_mod(i + 1 , inv_fac[i + 1]);}
ll nCk(ll n , ll k){ll ans = fac[n];ans = mult_mod(ans , inv_fac[n - k]);ans = mult_mod(ans , inv_fac[k]);return ans;}
int dx[8] = {1 , 0 , -1 , 0 , 1 , -1 , -1 , 1};    // last 4 diagonal
int dy[8] = {0 , 1 , 0 , -1 , 1 , 1 , -1 , -1};


int main() {
    
   
   int n;
   cin >> n;
   vector <int> vec(n+1), ans(n+1);

   for(int i = 1; i <= n; i++){
       cin >> vec[i];
       ans[vec[i]] = i; 
   }
   for(int i = 1; i <= n; i++) cout << ans[i] << " ";
}


Measured memory_bytes: 1536
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
using namespace std;

struct Info{
	Info(){
		white = blue = red = 0;
	}
	int white,blue,red;
};

int main(){

	int N,M;
	scanf("%d %d",&N,&M);

	char buf[M+1];
	Info info[N];

	int w_num,b_num,r_num;

	for(int i = 0; i < N; i++){
		scanf("%s",buf);
		r_num = b_num = w_num = 0;

		for(int k = 0; k < M; k++){
			switch(buf[k]){
			case 'W':
				w_num++;
				break;
			case 'B':
				b_num++;
				break;
			case 'R':
				r_num++;
				break;
			}
		}
		info[i].white = w_num;
		info[i].blue = b_num;
		info[i].red = r_num;
	}

	int minimum = BIG_NUM,tmp;

	for(int w_bottom = 1; w_bottom <= N-2;w_bottom++){
		for(int b_bottom = w_bottom+1; b_bottom <= N-1; b_bottom++){
			tmp = 0;
			for(int i = 0; i < w_bottom; i++){
				tmp += info[i].blue;
				tmp += info[i].red;
			}
			for(int i = w_bottom; i < b_bottom; i++){
				tmp += info[i].white;
				tmp += info[i].red;
			}
			for(int i = b_bottom; i < N; i++){
				tmp += info[i].white;
				tmp += info[i].blue;
			}
			minimum = min(minimum,tmp);
		}
	}

	printf("%d\n",minimum);

    return 0;
}

Measured memory_bytes: 2756
count = int(input());
data = [];
for i in range(count):
    data.append(int(input()));
gaps = [1];
for i in range(99):
    next_gap = 3 * gaps[-1] + 1;
    if count > next_gap:
        gaps.append(next_gap);
    else:
        break;
gaps.reverse();

def shell_sort(data, gaps):
    o = 0;
    for gap in gaps:
        for g in range(gap):
            o += insert_sort(data, gap, g);
    return o;

def insert_sort(data, gap, g):
    o = 0;
    count = len(data);
    for i in range(g + gap, count, gap):
        n = data[i];
        j = i - gap;
        while j >= 0:
            if data[j] > n:
                o += 1;
                data[j + gap] = data[j];
                j -= gap;
            else:
                break;
        data[j + gap] = n;
    return o;

o = shell_sort(data, gaps);

print(len(gaps));
print(" ".join(str(n) for n in gaps));
print(o);
print("\n".join(str(n) for n in data));


Measured memory_bytes: 125984
import java.util.*;

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

    int n = sc.nextInt();
    double[] array = new double[n];
    double a, sum = 0 ;

    for(int i=0; i<n; i++){
      a = sc.nextInt();
      a = 1 /(double)a;
      sum += a;
    }
    sum = 1 /sum ;
    System.out.println(sum);
  }

}


Measured memory_bytes: 23252
fun main(args: Array<String>) {
    val cList: List<List<Int>> = (0 until 3).map {
        readLine()?.split(" ")?.map { it.toInt() } ?: listOf()
    }
    for (a1 in 0..100) {
        for (a2 in 0..100) {
            for (a3 in 0..100) {
                val b1 = cList[0][0] - a1
                val b2 = cList[1][1] - a2
                val b3 = cList[2][2] - a3
                if (cList[0][1] == a1 + b2 &&
                    cList[0][2] == a1 + b3 &&
                    cList[1][0] == a2 + b1 &&
                    cList[1][2] == a2 + b3 &&
                    cList[2][0] == a3 + b1 &&
                    cList[2][1] == a3 + b2
                ) {
                    println("Yes")
                    return
                }
            }
        }
    }
    println("No")
}

Measured memory_bytes: 36544
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN=200000;

int n,want;
int x[MAXN];
ll xs[MAXN+1];

pair<ll,int> s[MAXN];

int b[MAXN+2];
void bmod(int idx) { ++idx; while(idx<=n+1) { ++b[idx]; idx+=idx&-idx; } }
int bget(int idx) { ++idx; int ret=0; while(idx>0) { ret+=b[idx]; idx-=idx&-idx; } return ret; }


void run() {
	scanf("%d%d",&n,&want); REP(i,n) scanf("%d",&x[i]);
	xs[0]=0; REP(i,n) xs[i+1]=xs[i]+x[i];
	REPE(i,n) s[i]=MP(xs[i]-(ll)want*i,i);
	sort(s,s+n+1);
	memset(b,0,sizeof(b));
	ll ret=0;
	REPE(i,n) {
		//printf("%lld %d\n",s[i].first,s[i].second);
		ret+=bget(s[i].second);
		bmod(s[i].second);
	}
	printf("%lld\n",ret);
}

int main() {
	run();
	return 0;
}


Measured memory_bytes: 6528
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>
#include <bitset>

using ll = long long;
typedef unsigned long long ull;
typedef std::pair<ll, ll>P;

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}

const ll mod = 1000000007;
const ll INF = 1 << 30;
const ll INF2 = 9000000000000000000LL;
bool fl = true;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
std::string abc = "abcdefghijklmnopqrstuvwxyz";
struct edge { ll to, cost; };
struct edge1 { ll from, to, cost; };
double pai = 3.141592653589793;
std::vector<P>v[100010];

int main() {
	int n, m, a[1000], b[1000], c[1000], d[1000];
	std::cin >> n >> m;
	for (int i = 1;i <= n;i++) {
		std::cin >> a[i] >> b[i];
	}
	for (int i = 1;i <= m;i++) {
		std::cin >> c[i] >> d[i];
	}
	for (int i = 1;i <= n;i++) {
		int e = INF, ans = 0;
		for (int j = 1;j <= m;j++) {
			int sum = abs(a[i] - c[j]) + abs(b[i] - d[j]);
			if (sum < e)ans = j, e = sum;
		}
		std::cout << ans << std::endl;
	}
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  string s;
  R s;
  ll d[s.size()+1];
  mem(d);
  d[0]=1;
  rep(i,s.size()) d[i+1]=d[i]*3%MAX;
  ll ans=0,p=1;
  rep(i,s.size()) {
    if(s[i]=='1') {
      ans+=d[s.size()-i-1]*p%MAX;
      ans%=MAX;
      p*=2;
      p%=MAX;
    }
  }
  ans+=p;
  ans%=MAX;
  pr(ans);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

#define MyREP(i, n) for (long long i = 0; i < (long long)(n); i++)
#define MySORT(v) sort(v.begin(),v.end())

template <typename T>
ostream& operator<<(ostream& s, const vector<T> &vec){
    for(int i=0;i<vec.size();i++){
        if(i) s << ',';
        else s << '{';
        s <<setw(2)<< vec[i];
    }
    s << '}' << endl;
    return s;
}


int main(){
    int n;
    cin>>n;
    vector<pair<int,int>> xy(n);
    vector<int> ad(n),sb(n);
    MyREP(i,n){
        int x,y;
        cin>>x>>y;
        ad[i]=x+y;
        sb[i]=x-y;
    }
    MySORT(ad);
    MySORT(sb);
    int ma = ad.back()-ad[0];
    int ms = sb.back()-sb[0];
    cout<<max(ma,ms)<<endl;
    return 0;
}

Measured memory_bytes: 6420
#include <stdio.h>

char str[1005];
char p[1005];

int main()
{
	int q, a, b;
	char op[10], *x, *y, c;
	
	scanf("%s%d", str, &q);
	while (q--) {
		scanf("%s%d%d", op, &a, &b);
		if (op[2] == 'i') {             // print
			b++, c = *(str+b), *(str+b) = 0, puts(str+a), *(str+b) = c;
		} else if (op[2] == 'v') {      // reverse
			x = str+a, y = str+b;
			while (x < y) {
				c = *x, *x = *y, *y = c;
				x++, y--;
			}
		} else {                        // replace
			scanf("%s", p);
			x = str+a, y = p;
			while (*y) *x++ = *y++;
		}
	}
	return 0;
}



Measured memory_bytes: 2144
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	int n;
	cin >> n;
	
	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	int ans = -1;
	for(int i = 0; i < n - 1; ++i) {
		for(int j = i + 1; j < n; ++j) {
			ans = max(ans, abs(a[i] - a[j]));
		}
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <complex>
//#include <fstream>	// require freopen

using namespace std;

typedef complex <double> P;

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)

// OÏ (cross product) : a~b = |a||b|sinÆ
double cross(P a, P b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

int main()
{
//	cut here before submit 
//	freopen("testcase.ic", "r", stdin);
	string str = "";

	while (getline (cin, str ) ){
		while (str.find(',') != string::npos ){
			str = str.replace(str.find(','), 1, " " );
		} // end while

		stringstream ss (str );
		vector <P> p(4);
		int i;

		for (i = 0; i < 4; ++i){
			ss >> p[i].real() >> p[i].imag();
		} // end for

		if ( (    cross (p[1] - p[0], p[2] - p[0] ) > 0.0 
			&& cross (p[2] - p[1], p[3] - p[1] ) > 0.0
			&& cross (p[3] - p[2], p[0] - p[2] ) > 0.0
			&& cross (p[0] - p[3], p[1] - p[3] ) > 0.0
		      )
		||    (
   			   cross (p[1] - p[0], p[2] - p[0] ) < 0.0 
			&& cross (p[2] - p[1], p[3] - p[1] ) < 0.0
			&& cross (p[3] - p[2], p[0] - p[2] ) < 0.0
			&& cross (p[0] - p[3], p[1] - p[3] ) < 0.0
		      )
		){
			cout << "YES" << endl;
		}else{
			cout << "NO" << endl;
		} // end if

	} // end while
		
	return 0;
}

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

#define fi first
#define se second
#define pb push_back
#define ins insert
#define er erase

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m;
long double dp[100005], dp1[100005];
vector<int> Adj[100005];

void preprocess(){
	dp[n] = 0;
	for(int i = n - 1; i >= 1; i--){
		for(int j = 0; j < Adj[i].size(); j++) dp[i] += dp[Adj[i][j]];
		dp[i] /= (long double)(Adj[i].size());
		dp[i] += 1.0;
		//cout << dp[i] << "\n";
	}
}

long double cal(int banx, int bany){
	dp1[n] = 0;
	for(int i = n - 1; i >= 1; i--){
		dp1[i] = 0;
		if(i == banx){
			bool minus = 0;
			for(int j = 0; j < Adj[i].size(); j++){
				if(Adj[i][j] == bany){
					minus = 1;
					continue;
				}
				dp1[i] += dp1[Adj[i][j]];
			}
			dp1[i] /= (long double)(Adj[i].size() - minus);
			dp1[i] += 1.0;
		}
		else{
			for(int j = 0; j < Adj[i].size(); j++) dp1[i] += dp1[Adj[i][j]];
			dp1[i] /= (long double)(Adj[i].size());
			dp1[i] += 1.0;
		}
		//if(banx == 1) cout << dp1[i] << "\n";
	}
	return dp1[1];
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y;
		cin >> x >> y;
		Adj[x].pb(y);
	}
	preprocess();
	long double answ = dp[1];
	//cout << answ << "\n";
	for(int i = 1; i < n; i++){
		if(Adj[i].size() == 1) continue;
		long double mx = 0;
		int ind = -1;
		for(int j = 0; j < Adj[i].size(); j++){
			if(dp[Adj[i][j]] > mx){
				mx = dp[Adj[i][j]];
				ind = Adj[i][j];
			}
		}
		//cout << cal(i, ind) << "\n";
		answ = min(answ, cal(i, ind));
	}
	cout << fixed << setprecision(6) << answ;
}



Measured memory_bytes: 7212
//include
//------------------------------------------
#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 <climits>
#include <queue>

using namespace std;

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
//------------------------------------------
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI  = acos(-1.0);

struct Edge{
  int to, cost;

  Edge(int t, int c = 0): to(t), cost(c)
  {}
  bool operator>(const Edge& rhs) const{
	return cost > rhs.cost;
  }
  bool operator<(const Edge& rhs) const{
	return cost < rhs.cost;
  }

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


// calc Lowest Common Ancestor
// O(N logN)
struct LCA{
  const Graph& G;
  int N, R;
  int LOG_MAX;
  vector<int> depth;
  vector<vector<int>> parent;

  LCA(const Graph& G_, int N_, int R_):
	G(G_), N(N_), R(R_)
  {
	LOG_MAX = log2(N) + 1;
	depth.assign(N, -1);
	parent.resize(LOG_MAX);
	for(int i=0;i<LOG_MAX;++i)
	  parent[i].resize(N);

	function<void(int,int,int)> dfs = [&](int u, int p, int d){
	  depth[u] = d;
	  parent[0][u] = p;
	  for(const auto& e: G[u])
		if(e.to != p)
		  dfs(e.to, u, d+1);
	};
	dfs(R, -1, 0);
	
	for(int i=0;i+1<LOG_MAX;++i){
	  for(int v=0;v<N;++v){
		if(parent[i][v] == -1) parent[i+1][v] = -1;
		else parent[i+1][v] = parent[i][parent[i][v]];
	  }
	}
  }


  int query(int u, int v){
	if(depth[u] > depth[v]) swap(u, v);
	// assume: depth[u] <= depth[v]
	for(int i=0;i<LOG_MAX;++i)
	  if((depth[v] - depth[u]) >> i & 1)
		v = parent[i][v];
	if(u == v) return u;
	
	for(int i=LOG_MAX-1;i>=0;--i){
	  if(parent[i][u] != parent[i][v]){
		u = parent[i][u];
		v = parent[i][v];
	  }
	}
	return parent[0][u];
  }
};

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

  int V; cin >> V;
  Graph G(V);
  REP(i,V){
	int k; cin >> k;
	REP(j,k){
	  int c; cin >> c;
	  G[i].PB(c);
	  G[c].PB(i);
	}
  }
  LCA lca(G, V, 0);

  int Q; cin >> Q;
  while(Q--){
	int u, v; cin >> u >> v;
	cout << lca.query(u,v) << endl;
  }
  
  return 0;
}

Measured memory_bytes: 23224
#include<iostream>
const int N = 1e5+50;
bool death[N];
int primelist[N], a[N];
using namespace std;
int main() {
    int t, m, n, tail = 0;   
    death[1] = 1;
    for(int i = 2;i <= N; ++i) {
    	if( !death[i] )
    		primelist[++tail] = i;
    	for(int j = 1; j <= tail; ++j) {
    		if(primelist[j]*i > N) break;
    		death[primelist[j]*i] = 1;
    		if(i%primelist[j] == 0) break;
    	}	
    }
    for(int i = 2; i <= N; ++i) {
      if((i&1)&&(!death[i])&&(!death[(i+1)/2]))
             a[i] = 1;
             a[i]+=a[i-1];           
        } 
    cin>>t;
    while(t--) {
      int sum = 0;
      cin>>m>>n;
      cout<<(a[n]-a[m-1])<<"\n";
    }  
    return 0;
} 

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

int main() {
    int n,k;
    cin >> n >> k;
    string s;
    cin >> s;
    deque<int> seq;
    int ctr=1;
    rp(i,n-1){
        if(s.at(i)==s.at(i+1)) ctr++;
        else{
            seq.push_back(ctr);
            ctr=1;
        }
    }
    seq.push_back(ctr);
    if(s.at(0)=='0') seq.push_front(0);
    if(s.at(n-1)=='0') seq.push_back(0);
    int si=seq.size();
    if(si<=k+k+1){
        cout<< n << endl;
        return 0;
    }
    vector<int> sum(si+1);
    sum.at(0)=0;
    for(int i=1; i<=si; i++){
        sum.at(i)=sum.at(i-1)+seq.at(i-1);
    }
    //for(auto p:sum) cout << p << endl;
    int ans=0;
    for(int i=0; i<=si-k-k-1; i+=2){
        ans=max(ans,sum.at(i+k+k+1)-sum.at(i));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int main() {
  ll A, B, N;
  cin >> A >> B >> N;
  ll x = min(N, B - 1);
  cout << floor ((double)A * x / B) - A * floor((double)x / B) << endl;
  return 0;
}

Measured memory_bytes: 3768
#include<bits/stdc++.h>
#define mod 1000000007
#define pb push_back
#define ll long long
#define mk make_pair
#define fi first
#define lb lower_bound
#define test ll int t;cin>>t;while(t)
#define se second
using namespace std;

int main(){
   int h,w,m;
   cin>>h>>w>>m;
   map<int,int>x;
   map<int,int>y;
   map<pair<int,int>,int>tar;
   for(int i=0;i<m;i++){
       int e,f;
       cin>>e>>f;
       x[e]++;y[f]++;
       tar[{e,f}]++;
   }
   int tx=0,ty=0;
   int fx,fy;
   for(auto j:x){
       if(tx<j.second){
           fx=j.first;
           tx=j.second;
       }
   }
   for(auto j:y){
       if(ty<j.second){
           fy=j.first;
           ty=j.second;
       }
       else if(ty==j.second&&tar.find({fx,j.first})==tar.end()){
           fy=j.first;
           ty=j.second;
       }
   }
   //cout<<fx<<" "<<fy<<endl;
   int ans1=tx+ty;
   if(tar.find({fx,fy})!=tar.end())
   ans1--;
   tx=0,ty=0,fx=0,fy=0;
   for(auto j:y){
       if(ty<j.second){
           fy=j.first;
           ty=j.second;
       }
   }
   for(auto j:x){
       if(tx<j.second){
           fx=j.first;
           tx=j.second;
       }
       else if(tx==j.second&&tar.find({j.first,fy})==tar.end()){
           fx=j.first;
           tx=j.second;
       }
   }
   int ans2=tx+ty;
   if(tar.find({fx,fy})!=tar.end())
   ans2--;
   cout<<max(ans1,ans2)<<endl;
    return 0;
}

Measured memory_bytes: 50484
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <string>
#include <sstream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

template <class T>
int bsl(const vector<T> &x, T target)
{
  int n=x.size();
  int a=0; int b=n-1; int c;
  while(a<=b){
    c = (a+b)/2;
    T xc = x[c];
    if(xc>=target)
      b = c-1;
    else
      a = c+1;
  }
  return a;
}


template <class T>
int bsr(const vector<T> &x, T target)
{
  int n=x.size();
  int a=0; int b=n-1; int c;
  while(a<=b){
    c = (a+b)/2;
    T xc = x[c];
    if(xc>target)
      b = c-1;
    else
      a = c+1;
  }
  return a;
}


int main(){
  cin.tie(0); ios::sync_with_stdio(false);    // Magic for faster cin
  int N, Q;
  cin >> N >> Q;
  string S;
  cin >> S;

  vector<int> ii; ii.reserve(N);
  rep(i,N-1){
    if(S.substr(i,2)=="AC") ii.push_back(i);
  }
  // rep(i,ii.size()) cout << ii[i] << " ";
  // cout << endl;
  
  int l,r;
  rep(i,Q){
    cin >> l >> r;
    int low = bsl(ii,l-1);
    int high = bsr(ii,r-2);
    cout << high - low << endl;
  }
  return 0;
}


Measured memory_bytes: 1232
#coding:utf-8

def main():
    N = int(input())
    v = list(map(int, input().split()))
    c = list(map(int, input().split()))
    result = []

    for i in range(N):
        plus = v[i] - c[i]
        if plus > 0:
            result.append(plus)

    print(sum(result))

if __name__ == "__main__":
    main()

Measured memory_bytes: 3060
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s, t string
	fmt.Scan(&s)
	for i := range s {
		t = string(s[i])
		if i%2 != 0 {
			if strings.Index("LUD", t) == -1 {
				fmt.Println("No")
				return
			}
		} else {
			if strings.Index("RUD", t) == -1 {
				fmt.Println("No")
				return
			}
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 640
/* ex 9_2
   nknm */
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100001

//リストのノード（スタック内の各データ）の定義
typedef struct node{
    char elem;
    struct node *next;
} node;

//スタックにデータを追加
node* push(node **first, char elem){
    //追加する分の領域を確保
    node *new = calloc(1, sizeof(node));
    if(new == NULL){
        exit(1);
    }
    new->elem = elem;
    new->next = *first;
    *first = new;
    return *first;

}


node* delete_node(node **first){        //スタックからデータを削除
    node *tmp = *first;
    if(tmp == NULL){
        exit(1);
    }
    
    *first = tmp->next;
    free(tmp);
    return *first;
}


int main(void){

    char imput[SIZE];
    int i = 0, count = 0;
    scanf("%s", imput);
    //最初のノードの指す先
    node *first = NULL;
    //スタックにノードを追加
    while(imput[i] != '\0'){
        
        if(imput[i] == '0'){
            push(&first, '0');
        }else if(imput[i] == '1'){
            push(&first, '1');
        }
            
        if(first->next != NULL){        //2つ以上データがあるとき
            if(first->elem == '1' && (first->next)->elem == '0'){
                delete_node(&first);
                delete_node(&first);
                count += 2;
            }else if(first->elem == '0' && (first->next)->elem == '1'){
                delete_node(&first);
                delete_node(&first);
                count += 2;
            }
        }
        i++;
    }
    printf("%d\n", count);

    return 0;
}

Measured memory_bytes: 4924
#include <bits/stdc++.h>
using namespace std;
#define int long
void fail() {
    cout << "No";
    exit(0);
}
signed main() {
    int n, sum = 0;
    map<char, int> var;
    cin >> n >> var['A'] >> var['B'] >> var['C'];
    sum = var['A'] + var['B'] + var['C'];
    vector<string> str(n);
    vector<char> res(n);
    for (auto& i : str) cin >> i;
    if (sum == 0) fail();
    if (sum == 1) {
        for (int i = 0; i < n; ++i) {
            char c0 = str[i][0], c1 = str[i][1];
            if (var[c0] == var[c1]) fail();
            if (!var[c0])
                ++var[c0], --var[c1], res[i] = c0;
            else
                ++var[c1], --var[c0], res[i] = c1;
        }
    } else
        for (int i = 0; i < n; ++i) {
            char c0 = str[i][0], c1 = str[i][1];
            if (!i && !var[c0] && !var[c1]) fail();
            if (!var[c0])
                ++var[c0], --var[c1], res[i] = c0;
            else if (!var[c1])
                ++var[c1], --var[c0], res[i] = c1;
            else {
                if (i + 1 < n && str[i + 1] != str[i]) {
                    if (str[i + 1][0] == c0 || str[i + 1][1] == c0)
                        ++var[c0], --var[c1], res[i] = c0;
                    else
                        ++var[c1], --var[c0], res[i] = c1;
                } else {
                    if (var[c0] < var[c1])
                        ++var[c0], --var[c1], res[i] = c0;
                    else
                        ++var[c1], --var[c0], res[i] = c1;
                }
            }
        }
    cout << "Yes" << endl;
    for (auto ch : res) cout << ch << endl;
}

Measured memory_bytes: 6840
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

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

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文
int main() {
	int a[13] = { 0,1,2,1,3,1,3,1,1,3,1,3,1 };
	int x, y;
	cin >> x >> y;
	ansYes(a[x] == a[y]);
}

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

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  int a, b;
  cin >> a >> b;
  
  for (double i = 0; i <= 10000; i++) {
    int x = i * 0.08, y = i * 0.1;
    if (x == a && y == b) {
      cout << i << '\n';
      return 0;
    }
  }
  
  cout << -1 << '\n';
  return 0;
}

Measured memory_bytes: 256
"""Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d
"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 5 + 1)

class Node:
    def __init__(self, num):
        self.num = num
        self.edge = set()
        self.edge_color = set()


def dfs(node, c = -1 , p = -1):
    k = 1    
    for e in node.edge:
        if e == p:
            continue
        if k == c:
            k += 1
        # 子のノードを取得
        child = tree[e]

        # 答えを記録
        if a < b:
            ans['{0} {1}'.format(node.num, child.num)] = k
        else:
            ans['{0} {1}'.format(child.num, node.num)] = k
        k += 1

        # 掘る
        dfs(child,k - 1, node.num)


N = int(input())
ans = {}
# colors = {1}

# treeの初期化
tree = [Node(i) for i in range(0, N + 1)]
edges = []
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].edge.add(b)
    tree[b].edge.add(a)
    if a < b:
        edges.append('{0} {1}'.format(a, b))
    else:
        edges.append('{0} {1}'.format(b, a))

dfs(tree[1], -1)

# print("edges:{}".format(edges))
# print(max(c))
# print(ans)
count = 0
for node in tree:
    count = max(count, len(node.edge))
print(count)
for edge in edges:
    # print(edge)
    print(str(ans.get(edge)))



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

int main(){
	int a;double x,ans=0;
	cin>>a;
	for(int i=1;i<=a;i++){
		cin>>x;
		x=1.0/x;
		ans+=x;
	}
	ans=1.0/ans;
	cout<<ans<<endl;
	return 0;
} 

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int x = sc.nextInt();

		if(500*k >= x) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
	}
}


Measured memory_bytes: 23252
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
  int n; cin >> n;
  bool ans = false;
  for(int i = 1;i < 10;i++)
  {
    for(int j = i;j < 10;j++)
    {
      if(i * j == n) ans = true;
    }
  }
  cout << (ans ? "Yes\n" : "No\n");
}


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

int solve(int n, int64_t k, const std::vector<int>& to) {
  std::vector<int> dis(n + 1, -1);
  int step = 0, pos = 1;
  dis[pos] = 0;
  int loop_start, loop_len;
  while (true) {
    if (step == k) return pos;
    int next = to[pos];
    if (dis[next] != -1) {
      loop_start = next;
      loop_len = dis[pos] - dis[next] + 1;
      break;
    }
    ++step;
    dis[next] = dis[pos] + 1;
    pos = next;
  }
  k = (k - dis[loop_start]) % loop_len;
  int ans = loop_start;
  while (k--) ans = to[ans];
  return ans;
}

int main() {
  int n;
  int64_t k;
  std::cin >> n >> k;
  std::vector<int> to(n + 1);
  for (int i = 1; i <= n; ++i) {
    std::cin >> to[i];
  }
  std::cout << solve(n, k, to) << std::endl;
  return 0;
}


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

int main() {
  string S;
  cin >> S;
  
  if (S.at(2) == S.at(3) && S.at(4) == S.at(5)) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,l;
    cin >> n >> l;
    vector<string> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    sort(a.begin(),a.end());
    for(int i = 0; i < n; i++){
        cout << a[i];
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <assert.h>
#include <time.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;
 
using namespace std;

vector<vector<int> > g;   // to
vector<int> pars;
vector<int> depth;

void dfs(int par, int curr, int depth_curr)
{
    pars[curr]=par;
    depth[curr]=depth_curr;
    int siz=(int)g[curr].size();
    int i;
    for(i=0; i<siz; i++) {
        int next=g[curr][i];
        if(par==next) continue;
        dfs(curr, next, depth_curr+1);
    }
    return;
}

int main(int argc, char* argv[])
{
    int n;
    scanf("%d", &n);

    g.resize(n);
    pars.resize(n);
    depth.resize(n);
    int i;
    for(i=0; i<n-1; i++) {
        int a,b;
        scanf("%d%d", &a, &b); a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(-1, 0, 0);

    vector<int> flag(n-1);
    int Q;
    scanf("%d", &Q);
    for(i=0; i<Q; i++) {
        int a,b;
        scanf("%d%d", &a, &b); a--; b--;
        if(depth[a]<depth[b]) swap(a,b);
        while(depth[a]>depth[b]) {
            flag[a-1]+=(1<<i);
            a=pars[a];
        }
        while(a!=b) {
            flag[a-1]+=(1<<i);
            flag[b-1]+=(1<<i);
            a=pars[a];
            b=pars[b];
        }
    }

    ll ans=0;
    int j;
    for(i=0; i<(1<<Q); i++) {
        int cnt=0;
        for(j=0; j<Q; j++) {
            if(i & (1<<j)) cnt++;
        }
        int mult=(cnt%2? -1: 1);

        cnt=0;
        for(j=0; j<n-1; j++) {
            if(flag[j] & i) cnt++;
        }
        ll ans0=((ll)1<<(n-1-cnt))*mult;
        ans+=ans0;
    }
    printf("%lld\n", ans);

    return 0;
}


Measured memory_bytes: 256
//https://atcoder.jp/contests/dp/tasks/dp_i
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define float long double
#define f(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
double final=0;
double dp[3100][3100];
double find(ll i,ll n,double a[],ll noofhead){
if(i==n){
if(noofhead>(n-noofhead)){
    return 1.0;}

else{
    return 0.0;
}
}
if(dp[i][noofhead]!=-1.0){
    return dp[i][noofhead];
}
double ans=0.0;
double head=a[i];
double tail=1.0-a[i];
double val1=head*find(i+1,n,a,noofhead+1);
double val2=tail*find(i+1,n,a,noofhead);
return dp[i][noofhead]=double(val1+val2);

}

int main(){

ll n;
cin>>n;double a[n];
f(i,0,n)cin>>a[i];

double p=1.0;

f(i,0,n+1){
    f(j,0,n+1){
        dp[i][j]=-1.0;
    }
}

cout<<fixed << setprecision(10)<<find(0,n,a,0)<<endl;







    }   

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

using namespace std;

int main(){
	long long n, x;
	cin >> n >> x;
	long long ans = n;
	n -= x;
	bool flag = true;
	while (flag){
		if (x > n){
			swap(x, n);
		}
		long long temp = 2 * (n / x);			
		if (n % x == 0){
			temp -= 1;
			flag = false;
		}
		temp *= x;
		ans += temp;
		n %= x;
	}
	cout << ans << '\n';
	return 0;
}

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

int main(){
	int a, b, c; cin >> a >> b >> c;
	
	for(int i = 0; i < b; i++){
		if(a * i % b == c){
			cout << "YES" << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std ;
#define ll 		long long
#define IOS 		ios_base::sync_with_stdio(false);   cin.tie(NULL);
#define FOR(i,n) 	for(int i=0;i<n;i++)
#define nl 		"\n"
#define BUFFER     	cin.ignore(numeric_limits<streamsize>::max(),'\n');
#define SORT		sort(a,a+n);

int main()
{
double a,b;
  cin>>a>>b;
  ll c=ceil((b-1)/(a-1));
  cout<<c;

return 0;
}

Measured memory_bytes: 256
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
 
//#include <x86intrin.h>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <bitset> 
#include <vector>
#include <cmath>
#include <deque>
#include <queue>
#include <iomanip>
#include <stack>
#include <map>
#include <set>
//#include <ordered_set>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 
//using namespace __gnu_pbds;
using namespace std;
 
//template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;
 
const double pi = acos (-1.0);
const double eps = 1e-9;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, a[N], l[N], r[N];
stack <int> st;
ll ans;

inline void boost () {
   ios_base :: sync_with_stdio (0);
   cin.tie (0), cout.tie (0);
}
 
inline void Solve () {
   cin >> n;
   for (int i = 1; i <= n; i ++) cin >> a[i];
   for (int i = 1; i <= n; i ++) {
      while (sz (st) && a[st.top ()] >= a[i]) st.pop ();
      if (sz (st)) l[i] = st.top () + 1;
      else l[i] = 1;
      st.push (i);
   }
   st = stack <int> ();
   for (int i = n; i >= 1; i --) {
      while (sz (st) && a[st.top ()] >= a[i]) st.pop ();
      if (sz (st)) r[i] = st.top () - 1;
      else r[i] = n;
      st.push (i);
   }
   for (int i = 1; i <= n; i ++) {
      ans += 1ll * (i - l[i] + 1) * (r[i] - i + 1) * a[i]; 
   }
   cout << ans;

}               
 
signed main () {                                       
   //#ifdef QWERTY
   //   freopen("input", "r", stdin);
   //#endif
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}      

Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<n; i++)
#define rrep(i, n) for(int i=n-1; i>=0; i--)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define ALL(v) v.begin(),v.end()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LLINF = 1e18;
const ll MOD = 1e9+7;
const double EPS = 1e-10;
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; }

bool sortBySec(const pii &a, const pii &b) {
    return a.second < b.second;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<pii> v(m);
    rep(i, m) cin >> v[i].first >> v[i].second;
    sort(v.begin(), v.end(), sortBySec);

    vector<int> cut;
    rep(i, m) {
        int a = v[i].first;
        int b = v[i].second;
        if (cut.empty()) cut.push_back(b-1);
        bool ok = false;
        for (auto e: cut) {
            if (a <= e && e <= b) {
                ok = true;
                break;
            }
        }
        if (!ok) cut.push_back(b-1);
    }
    cout << cut.size() << endl;
}


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



int main(){
    ll n;cin>>n;
    ll t,a;cin>>t>>a;
    rep(i,1,n){
        ll x,y;cin>>x>>y;
        ll mul=max((t+x-1)/x,(a+y-1)/y);
        t=mul*x;
        a=mul*y;
    }
    cout<<t+a<<endl;
}
    









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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
  int N, K, Q;
  cin >> N >> K >> Q;
  int a;
  vector<int> P(N, K - Q);

  rep (i, Q) {
    cin >> a;
    P.at(a - 1)++;
  }

  rep (i, N) {
    if (P.at(i) > 0) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }
}

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

using namespace std;

#define INF 1000000007
#define LINF (1LL << 60)
#define PI 3.14159265358979

typedef long long i64;
typedef pair<i64,i64> P;

inline i64 mod(i64 a, i64 m) { return (a % m + m) % m; }

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



int n, k, a[101010];
void solve(){
	cin >> n >> k;
	for(int i = 0; i < n; i++){
		cin >> a[i];
	}
	sort(a,a+n);
	
	int ans = INF;
	for(int i = k-1; i < n; i++){
		chmin(ans, a[i]-a[i-k+1]);
	}
	cout << ans << endl;
}

int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	
	return 0;
}


Measured memory_bytes: 640