akhauriyash/Code-Regression huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True

g = []


def rec(i, s, N):
    # print(s)
    global g
    g.append(int(s))
    if len(s) > N:
        return

    if i - 1 >= 0:
        rec(i-1, s + str(i-1), N)
    rec(i, s + str(i), N)
    if i + 1 <= 9:
        rec(i+1, s + str(i+1), N)


def main():
    global g
    K = I()
    ans = []

    for i in range(1, 10):
        rec(i, str(i), 11)
    g = sorted(g)
    # print(len(g))
    print(g[K-1])


if __name__ == '__main__':
    main()


Measured memory_bytes: 118356
n=int(input())
kotaezyun=[]
renketu=[[] for i in range(n+1)]
ans_dict={}
for i in range(n-1):
    a,b=map(int, input().split())
    renketu[a].append(b)
    kotaezyun.append([a,b])

from collections import deque
que=deque()

que.append(1)

iro=[-1]*(n+1)
iro[1]=0
irokazu=0

tansaku_moto=[1]

while que:
    tansaku_moto=que.popleft()
    ironuri=1
    for tansaku_saki in renketu[tansaku_moto]:
        if ironuri==iro[tansaku_moto]:
            ironuri+=1
        iro[tansaku_saki]=ironuri
        ans_dict[tansaku_moto,tansaku_saki]=ironuri
        que.append(tansaku_saki)
        irokazu=max(irokazu,ironuri)
        ironuri+=1
        
print(irokazu)
for i in range(n-1):
    tmp=(kotaezyun[i][0],kotaezyun[i][1])
    print(ans_dict[tmp])

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

int main()
{
  string s;
  cin >> s;
  for(int i = (s.size() - 2) / 2; i >= 0; --i)
  {
    string tmp1 = s.substr(0, i), tmp2 = s.substr(i,i);
    if(tmp1 == tmp2)
    {
      s = tmp1 + tmp2;
      break;
    }
  }
  cout << s.size() << endl;
}

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

using namespace std;


void solve() {
    double L; cin >> L;
    cout << setprecision(15) << (L/3) * (L/3) * (L/3) << endl;
}


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

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np
# いっこ入力
n =int(input())

# 空白区切りの数列をリストに代入
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

d = []
value  =0
value_d =0
number =0
for i in range(n):
    if a[i] < b[i]:
        value += b[i] - a[i]
        number += 1
    else:
        d.append(a[i]-b[i])
        value_d += a[i]-b[i]

if(value > value_d):
    print("-1")
    exit()
d.sort(reverse=True)
if value <= 0:
    print("0")
    exit()

for i in range(len(d)):
    value = value - d[i]
    number += 1
    if value <= 0:
        break
print(number)



Measured memory_bytes: 34572
import sys
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    V = list(map(int, input().split()))
    C = list(map(int, input().split()))
    ans = 0
    for i in range(1 << N):
        value = 0
        cost = 0
        for j in range(N):
            if i & (1 << j):
                value += V[j]
                cost += C[j]
        ans = max(ans, value - cost)
    print(ans)




if __name__ == "__main__":
    main()


Measured memory_bytes: 41580
from heapq import*
import sys
r=sys.stdin.readline
def g(n,E,S,G):
 F=[1e7]*-~n;F[S]=0;H=[(0,S)]
 while H:
  c,u=heappop(H)
  if u==G:return c
  for f,v in E[u]:
   t=c+f
   if t<F[v]:F[v]=t;heappush(H,(t,v))
 return-1
def s(n,k):
 E=[[]for _ in[0]*-~n]
 for _ in[0]*k:
  f=r()
  if'0'==f[0]:print(g(n,E,*map(int,f[2:].split())))
  else:c,d,e=map(int,f[2:].split());E[c]+=[(e,d)];E[d]+=[(e,c)]
for e in iter(r,'0 0\n'):s(*map(int,e.split()))


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

int main() {
  int N;
  cin >> N;
  vector<ll> A(N), B(N);
  for (int i=0; i<N; i++) {
    cin >> A[i];
  }
  for (int i=0; i<N; i++) {
    B[i] = A[i] - (i + 1);
  }
  
  sort(B.begin(), B.end());
  
  ll b = B[(N-1)/2];
  ll ans = 0;
  
  for (int i=0; i<N; i++) {
    ans += abs(B[i]-b);
  }

  cout << ans << endl;
  
  
}

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

int main(){
    int a,b,ans;
    cin>>a>>b;
    if(a<b) ans=min(b-a,abs(a+b)+1);
    else ans=min(abs(a+b)+1,abs(a-b)+2);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
X, Y, A, B, C = map(int, input().split())
*P, = map(int, input().split())
*Q, = map(int, input().split())
*R, = map(int, input().split())
P = sorted(P, reverse=True)[:X]
Q = sorted(Q, reverse=True)[:Y]
print(sum(sorted(P + Q + R, reverse=True)[:X + Y]))


Measured memory_bytes: 119848
#include <stdio.h>

int max(int a, int b){
	return a>b?a:b;
}

int min(int a, int b){
	return a<b?a:b;
}

int main(){
	
	int i,n;
	scanf("%d",&n);
	int r[n],minv=2000000000,maxv=-1000000000;
	for(i=0;i<n;i++){
		scanf("%d",&r[i]);
		maxv = max(maxv, r[i]-minv);
		minv = min(minv, r[i]);		
    }

	printf("%d\n", maxv);
	return 0;
}

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

int main(void)
{
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int a;
        cin >> a;
        n -= a;
    }

    if(n >= 0)
    {
        cout << n << endl;
    }else {
        cout << -1 << endl;
    }
    return 0;
}



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

int debug = 1;

int n, ans;
string s;
map <pair <string, string>, int> cnt;

main() {
    cin >> n >> s;
    rep(mask, 0, (1 << n)) {
        string r = "", b = "";
        rep(i, 0, n) {
            if ((mask >> i) & 1) {
                r += s[i + n];
            } else {
                b += s[i + n];
            }
        }
        reverse(b.begin(), b.end());
        cnt[{r, b}]++;
    }
    ans = 0;
    rep(mask, 0, (1 << n)) {
        string r = "", b = "";
        rep(i, 0, n) {
            if ((mask >> i) & 1) {
                r += s[i];
            } else {
                b += s[i];
            }
        }
        reverse(b.begin(), b.end());
        ans += cnt[{b, r}];
    }
    cout << ans << '\n';
}

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);  
	int n, a, b;
	cin >> n >> a >> b;
	int x = 0, y = 0, z = 0;
	for(int i = 0; i < n; i++) {
		int k;
		cin >> k;
		if(k <= a) x++;
		if(a < k && k <= b) y++;
		if(b < k) z++;
	}
	cout << min({x, y, z}) << endl;
	return 0;	
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int n,s,cnt;
void dfs(int m,int num,int sum);
int main(){
	while(cin>>n>>s,n || s){
		cnt=0;
		dfs(1,0,0);
		cout<<cnt<<endl;
	}
	return 0;
}

void dfs(int m,int num,int sum){
	if(m>9 && (num==n || num==n-1) && sum==s)cnt++;
	if(m>9)return;
	dfs(m+1,num+1,sum+m);
	dfs(m+1,num,sum);
}

Measured memory_bytes: 1160
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
        String W,T;
        int count=0;
        W= sc.next();
        while(sc.hasNext()){
        T=sc.next();
        if(T.equalsIgnoreCase(W))count++;
        }
        System.out.println(count);
    }
}



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

#define rep(X,N) for(ll X = 0LL; X < (N); X++)
#define ALL(V) (V).begin(),(V).end()
#define endl "\n"

using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

const double PI = 3.1415926535897932384626;
const double EPS = 1e-10;
const ll MODN = 1000000007;
const ll MODN2 = 998244353;

class UnionFind{
    vector<int> parent;
    vector<int> sizev;

public:
    UnionFind(){}
    UnionFind(int n){
        for(int i = 0; i < n; i++){
            parent.push_back(i);
            sizev.push_back(1);
        }
    }

    void merge(int a, int b){
        int pa = leader(a);
        int pb = leader(b);

        if(pa != pb){
            if(size(pa) < size(pb)) swap(pa, pb);
            parent[pb] = parent[pa];
            sizev[pb] += sizev[pa];
            sizev[pa] = sizev[pb];
        }
    }

    bool same(int a, int b){
        return leader(a) == leader(b);
    }

    int leader(int a){
        int tmp = parent[a];
        if(tmp == a) return a;

        tmp = leader(tmp);
        parent[a] = tmp;
        return tmp;
    }

    int size(int a){
        return sizev[leader(a)];
    }

    vector<vector<int>> groups(){
        vector<int> index(parent.size(), -1);
        int count = 0;
        for(int i = 0; i < parent.size(); i++){
            if(i == leader(i)){
                index[i] = count;
                count++;
            }
        }
        vector<vector<int>> result(count + 1);

        for(int i = 0; i < parent.size(); i++){
            int tmp = leader(i);
            result[index[tmp]].push_back(i);
        }

        return result;
    }
};

int main(){

    int n, q;
    cin >> n >> q;

    UnionFind uf(n);

    rep(i, q){
        int t,u,v;
        cin >> t >> u >> v;

        if(t == 0){
            uf.merge(u, v);
        }else{
            cout << (uf.same(u,v) ? 1 : 0) << endl;
        }
    }

    return 0;
}


Measured memory_bytes: 4820
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define INF (1<<30)
#define INFLL (1ll<<60)
typedef pair<int, int> P;
typedef pair<int, P> E;
#define MOD (1000000007ll)
#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	b += MOD;
	a += b;
	a %= MOD;
}

ll memo[444][444],a[444];
bool done[444][444];

ll solve(int i, int j){
	int k;
	if(done[i][j]){
		return memo[i][j];
	}
	done[i][j] = true;
	if(i==j){
		memo[i][j] = 0ll;
		return memo[i][j];
	}
	memo[i][j] = INFLL;
	for(k=i; k<j; ++k){
		memo[i][j] = min(memo[i][j],solve(i,k)+solve(k+1,j));
	}
	for(k=i; k<=j; ++k){
		memo[i][j] += a[k];
	}
	return memo[i][j];
}

int main(void){
	int n,i;
	fill(done[0],done[444],false);
	cin >> n;
	for(i=0; i<n; ++i){
		cin >> a[i];
	}
	cout << (solve(0,n-1)) << endl;
	return 0;
}


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

#define reint register int
#define coint const int

using namespace std;

typedef long long ll;

coint SIZE = 100000 + 5;

bitset<SIZE> bit[SIZE], tmp;
int fa[SIZE], cnt, sz[SIZE];

int getfa(coint u) { return u == fa[u] ? u : fa[u] = getfa(fa[u]); }

struct Node { int x, y, bel; };

Node li[SIZE];

inline bool cmp1(const Node &x, const Node &y) { return x.x < y.x; }
inline bool cmp2(const Node &x, const Node &y) { return x.y < y.y; }

inline int getint(void) {
    reint x = 0, ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar());
    for (; ch >= '0' && ch <= '9';
            x = (x << 1) + (x << 3) + ch - '0', ch = getchar());
    return x;
}

ll ans;

inline void union_(coint x, coint y) {
    coint xfa = getfa(x), yfa = getfa(y);
    if (xfa == yfa) return;

    tmp = bit[xfa] | bit[yfa];
    coint tcnt = tmp.count(), xcnt = bit[xfa].count(), ycnt = bit[yfa].count();
    ans += (tcnt - xcnt) * sz[xfa] + (tcnt - ycnt) * sz[yfa];
    bit[yfa] = tmp, fa[xfa] = yfa, sz[yfa] += sz[xfa];

    return;
}

int main(void) {
    coint n = getint();
    for (reint i = 1; i <= n; ++i) li[i].x = getint(), li[i].y = getint();
    sort(li + 1, li + n + 1, cmp1);

    int ind = 0;
    for (reint i = 1; i <= n; i = ind + 1) {
        ++cnt, fa[cnt] = cnt, sz[cnt] = 1;
        for (; ind < n && li[ind + 1].x == li[i].x; ++ind)
            bit[cnt][li[ind + 1].y] = 1, li[ind + 1].bel = cnt;
    }

    sort(li + 1, li + n + 1, cmp2), ind = 0;
    for (reint i = 1; i <= n; i = ind + 1) {
        for (; ind < n && li[ind + 1].y == li[i].y; ++ind);
        for (reint j = i; j < ind; ++j)
            union_(li[j].bel, li[j + 1].bel);
    }

    printf("%lld\n", ans);

    return 0;
}



Measured memory_bytes: 614272
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MAX = 100000;
const int INF = 1e9;
const int dx[] = {-1,0,1,0};
const int dy[] = {0,-1,0,1};
#define PI 3.14159265358979323846264338327950L
#define MOD 1000000007
//setprecision(15)

int main() {
	char s; cin >> s;
	char ans = 'a' + ((s - 'a' + 1) % 26);
	cout << ans << endl;
}

Measured memory_bytes: 3564
#include <bits/stdc++.h>
#define DAU  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PLEC exit(0);
using namespace std;
int n, d;
int main() {
    DAU
    cin >> n >> d;
    d = 2 * d + 1;
    cout << n / d + (n % d != 0);
    PLEC
}


Measured memory_bytes: 3636
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <utility>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cstdio>

using namespace std;

#define REP(i,n,m) for( long long int i = (n); i < (m); i++ )
#define ll long long
#define ALL(a) (a).begin(), (a).end()
#define SORT(v) sort( ALL(v) );
#define LAST(v) v[v.size()-1]
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,-1,sizeof(a))
#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 pi pair<int, int>
#define MP make_pair
#define PB push_back
#define IIN(a) int a; cin >> a;
#define LIN(a) ll a; cin >> a;
#define SIN(a) string a; cin >> a;
#define EPS (1e-10)
#define INF 1000000000000LL

int MOD=1000000007;
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
//I ASCII code: '0' = 48; 'A' = 65; 'a' = 97


signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    LIN( a )
    LIN( b )
    LIN( c )
    ll ans = 0;

    if( a % 2 == 0 || b % 2 == 0 || c % 2 == 0 ){
      ans = 0;
    }else{
      ans = a * b;
      ans = min( ans, b * c);
      ans = min( ans, c * a);
    }
    cout << ans << endl;
    return 0;
}


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, X, Sum=0;
  cin >> N >> X;
  vector<int> A(N);
  rep(i, N) cin >> A.at(i);
  sort(A.begin(), A.end());
  rep(i, N){
    X-=A.at(i);
    if(i!=N-1 && X>=0) Sum++;
    else if(i==N-1 && X==0) Sum++;
    else break;
  }
  cout << Sum << endl;
}

Measured memory_bytes: 256
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_vec2<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
    (0..n).map(|_| read_vec()).collect()
}
fn main(){
    let s: String = read();
    let cs : Vec<char> = s.chars().collect();
    let len = cs.len();
    for i in 1..len{
        let sub = len/2 - i;
        let (f,l) = cs.split_at(sub);
        let (s,l) = l.split_at(sub);
        if f == s {
            println!("{}",sub*2);
            break;
        }
    }
}

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

int main()
{
 int n;
  cin >> n;
  vector<int> v;
  for (int i = 0;i < n;i++)
    v.push_back(i);
  
  map<int,pair<int,int>> m;
  for (int i =0;i < n;i++)
  {
	int tx,ty;
    cin >> tx >> ty;
	m[i] = make_pair(tx, ty);
  }
  
  int cnt = 0;
  double sum = 0;
  do
  {
    int tx = m[v[0]].first, ty = m[v[0]].second;
	for (int i = 1;i < n;i++)
    {
      sum = sum + sqrt( (tx-m[v[i]].first)*(tx-m[v[i]].first) + (ty-m[v[i]].second)*(ty-m[v[i]].second) );
      tx = m[v[i]].first;
      ty = m[v[i]].second;      
    }
    cnt++;
  } while(next_permutation(v.begin(), v.end()));
  printf("%.10f",sum/cnt);
}

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

#define INF 1e9
#define ll long long int
#define ff first
#define ss second


int main() 
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin>>n;
	int counter=0;
	int flag=0;
	
	int a,b;
	while(n)
	{
		cin>>a>>b;
		if(a==b)
		{
			counter++;
			if (counter==3)
			{
				flag=1;
				break;
			}
		}
		else
		{
			counter=0;
		}
		n--;
	}
	if (flag)
		cout<<"Yes"<<'\n';
	else
		cout<<"No"<<'\n';
	
	return 0;
}

Measured memory_bytes: 3636
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

tt = ord('A')
# print(ord('Z'))
n = inp()
s = input()
res = ''
for i in s:
    if ord(i) + n <= tt+25:
        tmp = chr(ord(i) + n)
    else:
        tmp = chr(ord(i) + n - 26)
    res += tmp
print(res)

Measured memory_bytes: 66536
#include<stdio.h>

int main(void)
{
	int h, m, s;
	int temp;
	int S;
	
	h = 0;
	m = 0;
	s = 0;
	temp = 0;
	S = 0;
	
	// 数値入力
	scanf("%d", &S);
	
	// 計算
	// 時
	h = S / 3600;
	temp = S % 3600;
	
	// 分
	m = temp / 60;
	
	// 秒
	s = temp % 60;
	
	// 結果出力
	printf("%d:%d:%d\n", h, m, s);
	
	return 0;
}


Measured memory_bytes: 2112
import sys
import heapq

s = sys.stdin.readline().strip()
K = int(sys.stdin.readline())

ls = len(s)
q = []
exists = set()
for i in range(26):
    ini = chr(ord("a") + i)
    for j in range(ls):
        if s[j] == ini:
            k = 0
            while k < K and j + k < ls:
                tmp = s[j:j+1+k]
                if tmp not in exists:
                    heapq.heappush(q, s[j:j+1+k])
                    exists.add(tmp)
                k += 1

    if K <= len(q):
        break

# print(q)
for i in range(K-1):
    heapq.heappop(q)
print(q[0])

Measured memory_bytes: 9144
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N; cin >> N;
    int odd = 0;

    for(int i=0; i<N; i++){
        int a; cin >> a;
        if(a%2 == 1) odd++;
    }

    if(odd%2 == 1) cout << "NO" << endl;
    else cout << "YES" << endl;
}

Measured memory_bytes: 256
///#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,abm,mmx,popcnt,avx,avx2,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

/*
    zet:
        find_by_order(k): k-stat [k > 0]
        order_of_key(k) : {el < k}

    gp_hash_table<key, val, custom_hash>

    rope<T>:
        iterators: mutable_begin, ..
        methods  : erase, insert, substr, ..
*/

#define all(x) (x).begin(), (x).end()
#define size(x) (int)((x).size())
#define em_back emplace_back

using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename T>
using zet = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

mt19937 eng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;

const int N = 3e2 + 4;

int sum(int x, int y) {
    return (x + y) % mod;
}

int diff(int x, int y) {
    return (x - y + mod) % mod;
}

int mult(int x, int y) {
    return (ll)x * y % mod;
}

int n, m, dp[N][N][N];

int f(int s, int a, int b) {
    int& res = dp[s][a][b];
    if (res != -1) {
        return res;
    }
    if (s == m + 1) {
        return res = (a == n && b == 0);
    }
    res = 0;

    int r1 = mult(a, f(s + 1, a + b, 0));
    int r2 = mult(b, f(s + 1, a, b));
    int r3 = mult(n - a - b, f(s + 1, a, b + 1));

    return res = sum(r1, sum(r2, r3));
}

void solve() {
    cin >> n >> m;
    memset(dp, -1, sizeof dp);
    cout << f(1, 1, 0) << "\n";
}

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

    int z = 1;
    /// cin >> z;

    while (z--) {
        solve();
    }

    return 0;
}


Measured memory_bytes: 113372
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lvector vector<ll>
#define cvector vector<char>
#define svector vector<string>
#define lque queue<ll>
#define lpque priority_queue<ll>
#define dlpque priority_queue<ll,lvector,greater<ll>>
#define P pair<ll,ll>
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define rep(i,n) for(ll i=0; i<n; ++i)
#define print(a) cout << (a) << endl

ll mod=1e9+7;

map<ll,ll> pfact(ll n) {
  map<ll,ll> ret;
  while(n%2==0) {ret[2]++;n/=2;}
  for(ll i=3;i*i<=n;i+=2) while(n%i==0) {ret[i]++;n/=i;}
  if(n!=1) ret[n]=1;
  return ret;
}

ll com(ll N, ll K, ll L) {
  ll d=1,e=(L*K)%mod,m_=mod-2;
  while(m_!=0) {
    if(m_&1) d=(d*e)%mod;
    e=e*e%mod;
    m_=m_>>1;
  }
  return (N*d)%mod;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll n,m,ans=1;cin>>n>>m;
  map<ll,ll> mp=pfact(m);
  lvector factorial(2*n+10,1);
  rep(i,2*n) factorial[i+1]=(factorial[i]*(i+1))%mod;
  ll v;
  for(auto p:mp) {
    v=p.second;
    ans*=com(factorial[n+v-1],factorial[n-1],factorial[v]);
    ans%=mod;
  }
  print(ans);
  return 0;
}

Measured memory_bytes: 1792
const main = stdin => {
  const input = stdin.trim().split('\n')
  const N = parseInt(input[0])
  let c = 0
  for (let i = N - 1; i >= 1; i--) {
    for (let j = 1; j < N - 1; j++) {
      if (i * j >= N) {
        break
      }
      c++
    }
  }
  console.log(c + 1);
}


// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


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

const int N=100010;
struct node{
	int a,b;
	bool operator<(const node q)const{
		return a>q.a;
	}
}s[N];
int n;
long long sum=0;

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

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int x,y;
		scanf("%d %d",&x,&y);
		sum+=x;
		s[i].a=max(x,y);s[i].b=y;
	}
	sort(s+1,s+1+n);
	long long as=0;
	int k=0;
	while(1){
		k++;
		as+=s[k].a;
		if(as>=sum) break;
	}
	long long ansx=1,ansy=1;
	for(int i=1;i<=n;i++){
		long long now=sum-(as-s[min(i,k)].a);
		if(now<=s[i].b && now*ansy<1ll*s[i].b*ansx) ansx=now,ansy=s[i].b;
	}
	ansx=ansy-ansx+(n-k)*ansy;
	ansy*=n;
	printf("%lld %lld",ansx/gcd(ansx,ansy),ansy/gcd(ansx,ansy));
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define brep(index,num) for(int index=num-1;index>=0;index--)
#define brep1(index,num) for(int index=num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N;
	vpll A;
	int ans=0;
	scan(N);
	rep(i,N){
		ll a;
		scan(a);
		A.push_back({a,i});
	}
	sort(ALL(A));
	rep(i,N){
		ans+=abs(i-A[i].second)%2;
	}
	prin(ans/2);
	return 0;
}


Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define M ((ll)1e12)
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define pi acos(-1)
typedef long long ll;
using namespace std;


void solve()
{
   ll n;
   cin>>n;
   ll v=floor((n*100.0)/108);
   ll v1=ceil((n*100.0)/108);
   if(floor(v*1.08)==n)
   cout<<v<<endl;
   else if(floor(v1*1.08)==n)
   cout<<v1<<endl;
   else
   cout<<":("<<endl;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	solve();
	return 0;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

"""
・逆再生
・各時点に対して、「(Ai,Aj)がjが右になって終わる確率」を計算していく
"""

import numpy as np

MOD = 10**9 + 7

N,Q = map(int,readline().split())
data = list(map(int,read().split()))
A = np.array(data[:N])
it = iter(data[N:])
XY = list(zip(it,it))

dp = np.triu(np.ones((N,N),np.int64),1)

for x,y in XY[::-1]:
    x -= 1; y -= 1
    p=dp[x,y]; q=dp[y,x]; r=p+q
    if r&1:
        r += MOD
    r //= 2
    if r>=MOD:
        r -= MOD
    temp = dp[x]
    temp += dp[y]
    temp[temp&1==1] += MOD; temp//=2; temp[temp>=MOD] -= MOD; dp[y] = temp
    temp = dp[:,x]
    temp += dp[:,y]
    temp[temp&1==1] += MOD; temp//=2; temp[temp>=MOD] -= MOD; dp[:,y] = temp
    dp[x,y]=r; dp[y,x]=r; dp[x,x]=0; dp[y,y]=0

select = A[:,None]>A[None,:]
answer = (dp*select).sum()%MOD*pow(2,Q,MOD)%MOD
print(answer)

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

int n, a, b, c, d;
string S;

int main()
{
    cin >> n >> a >> b >> c >> d >> S;
    a--;
    b--;
    c--;
    d--;
    //cout << S << S[0] << endl;
    int cnt = 0;
    for (int i = a; i < max(c,d); i++)
    {
        if (S[i] == '#') cnt ++;
        else cnt = 0;
        if (cnt == 2)
        {
            cout << "No" << endl;
            return 0;
        }
        
        
    }
    cnt = 0;
    if (d < c)
    {
        for (int i = b-1; i < d+2; i++)
        {
            if (S[i] == '.') cnt ++;
            else cnt = 0;
            if (cnt == 3) {
                cout << "Yes" << endl;
                return 0;
            }
        }
        cout << "No" << endl;
        return 0;
    }
    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
long long modpow(int a, int b, int p){
//a^b%p
  long long res = 1;
	while (b > 0){
		if (b % 2 == 1) res = res * a % p;
		a = a * a % p;
		b = b / 2;
	}
	return res;
}
int main(){
  int N, P;
  cin >> N >> P;
  string S;
  cin >> S;
  vector<int> d(N);
  for (int i = 0; i < N; i++){
    d[i] = S[i] - '0';
  }
  if (P == 2 || P == 5){
    long long ans = 0;
    for (int i = 0; i < N; i++){
      if (d[i] % P == 0){
        ans += i + 1;
//        cout << i + 1 << endl;
      }
    }
    cout << ans;
  } else {
    vector<long long> R(N);
    R[N - 1] = d[N - 1] % P;
    for (int i = N - 2; i >= 0; i--){
      R[i] = R[i + 1] + modpow(10, N - 1 - i, P) * d[i];
      R[i] = R[i] % P;
    }
    vector<long long> C(P, 0);
    for (int i = 0; i < N; i++){
      C[R[i]]++;
    }
    long long ans = C[0];
    for (int i = 0; i < P; i++){
      ans += C[i] * (C[i] - 1) / 2;
    }
    cout << ans;
  }
}

Measured memory_bytes: 2948
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>

#define rep(i, a) REP(i, 0, a)
#define REP(i, a, b) for(int i = a; i < b; ++i)

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<P, int> PP;
const double PI = 3.14159265358979323846;
const double esp = 1e-9;
const int infi = (int)1e+9 + 10;
const ll infll = (ll)1e+17 + 10;

int dice[6];
int dir = 0;

class Dice{
public:
	//(front,back,up,down,right,left) = (1,3,5,0,2,4)
	int dat[6];

	void front(){
		int tmp = dat[0];
		dat[0] = dat[1];
		dat[1] = dat[5];
		dat[5] = dat[3];
		dat[3] = tmp;
	}
	void back(){
		int tmp = dat[0];
		dat[0] = dat[3];
		dat[3] = dat[5];
		dat[5] = dat[1];
		dat[1] = tmp;
	}
	void right(){
		int tmp = dat[0];
		dat[0] = dat[2];
		dat[2] = dat[5];
		dat[5] = dat[4];
		dat[4] = tmp;
	}
	void left(){
		int tmp = dat[0];
		dat[0] = dat[4];
		dat[4] = dat[5];
		dat[5] = dat[2];
		dat[2] = tmp;
	}
};

Dice d;

int main(){
	std::cin >> d.dat[5] >> d.dat[1] >> d.dat[2] >> d.dat[4] >> d.dat[3] >> d.dat[0];
	int q;
	std::cin >> q;
	rep(i, q){
		int a, b;
		std::cin >> a >> b;
		rep(j, 4){
			int r = (j + 3) % 4 + 1, l = (j + 1) % 4 + 1;
			if (d.dat[0] == a && d.dat[j + 1] == b)std::cout << d.dat[r] << std::endl;
			else if (d.dat[0] == b && d.dat[j + 1] == a)std::cout << d.dat[l] << std::endl;
			if (d.dat[5] == a && d.dat[j + 1] == b)std::cout << d.dat[l] << std::endl;
			else if (d.dat[5] == b && d.dat[j + 1] == a)std::cout << d.dat[r] << std::endl;
		}
		rep(j, 4){
			if (d.dat[j + 1] == a && d.dat[(j + 1) % 4 + 1] == b)std::cout << d.dat[5] << std::endl;
			else if (d.dat[j + 1] == b && d.dat[(j + 1) % 4 + 1] == a)std::cout << d.dat[0] << std::endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <cmath>
#include <cstdio>
#define eps 1e-8
int n; long double xa, ya, ra, xb, yb, rb;
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; i++) {
		scanf("%Lf%Lf%Lf%Lf%Lf%Lf", &xa, &ya, &ra, &xb, &yb, &rb);
		long double dist = sqrtl((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
		if(dist >= ra + rb + eps) {
			printf("0\n");
		}
		else if(dist <= ra - rb - eps) {
			printf("2\n");
		}
		else if(dist <= rb - ra - eps) {
			printf("-2\n");
		}
		else  {
			printf("1\n");
		}
	}
	return 0;
}

Measured memory_bytes: 2576
from math import gcd
from collections import Counter

mod = 10 ** 9 + 7

N, *AB = map(int, open(0).read().split())

def std(a, b):
    if a == 0:
        return (0, 1)

    g = gcd(a, b)
    a, b = a // g, b // g
    return (a, b) if a > 0 else (-a, -b)

C = Counter()
orig = 0
for a, b in zip(*[iter(AB)] * 2):
    if a == b == 0:
        orig += 1
    else:
        C[std(a, b)] += 1

ans = 1
cnt = 0
for (a, b), v in C.items():
    if b > 0:
        if (b, -a) in C:
            ans *= -1 + pow(2, v, mod) + pow(2, C[(b, -a)], mod)
            ans %= mod
        else:
            cnt += v
    elif (-b, a) not in C:
        cnt += v

ans *= pow(2, cnt, mod)
ans += orig - 1

print(ans % mod)

Measured memory_bytes: 72976
import qualified Data.ByteString.Char8 as BS
import Data.Maybe

readInt = fst . fromJust . BS.readInt
readIntList = map readInt . BS.words

getIntList = readIntList <$> BS.getLine

main = do
  [s, w] <- getIntList
  putStrLn $ if w >= s then "unsafe" else "safe"

Measured memory_bytes: 3672
import std.stdio, std.conv, std.string, std.algorithm, std.math, std.array, std.container;

void main() {
  int n = readln.chomp.to!int;
  int[] x = readln.chomp.split.to!(int[]);
  int minimum = int.max;
  for(int p=1; p<=100; p++) {
    int cost = 0;
    foreach(xi;x) {
      cost += (xi-p)*(xi-p);
    }
    minimum = min(cost, minimum);
  }
  writeln(minimum);
}



Measured memory_bytes: 256
/*
	Copyright: razouq (c)
	Author: Anass BENDARSI
	Date: 03/12/2017 12:26:23
	flamers will **** you
*/
#include<bits/stdc++.h>
//#include<flamers.h>
#define ll long long
#define ull unsigned long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define POB pop_back
#define dist(a, b) sqrt(a*a + b*b)
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pair<int, int>> vipi;
bool compare(pi p1, pi p2){
	 if(1) return true;
	 return false;
}

int main(){
//	freopen("input.in", "r", stdin);
//	freopen("output.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie();
	long long t, a, b;
	cin>>t>>a>>b;
	cout<<min(t*a, b)<<endl;
	return 0;
}


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

#define ll long long
#define ld long double
#define F first
#define S second

#define ONLINE_JUDGE 1

using namespace std;

const int mod = 1e9+7;
const int MAX = 100001;

void pr(vector<int> v){
	for(int x : v){
		cout << x << " ";
	}
	cout << "\n";
}

void solve(){
	int n,k,c;
	cin >> n >> k >> c;
	string s; cin >> s;
	vector<int> lf(n);
	vector<int> rt(n);
	int t = 1;
	int p = -MAX;	
	for(int i = 0; i < n; i++){
		if(s[i]=='o'){
			int d = i-p;
			if(d > c){
				lf[i] = t++;
				p = i;
			}
			if(t > k) break;
		}
	}
	reverse(s.begin(), s.end());
	t = k;
	p = -MAX;	
	for(int i = 0; i < n; i++){
		if(s[i]=='o'){
			int d = i-p;
			if(d > c){
				rt[i] = t--;
				p = i;
			}
			//if(t > k) break;
		}
	}
	reverse(rt.begin(), rt.end());
	int cnt = 0;
	for(int i = 0; i < n; i++){
		if(rt[i]==lf[i] && rt[i] > 0){
			cout << i + 1 << "\n";
		}
	}
}
int main(){
	#ifndef ONLINE_JUDGE	
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);		
	int t = 1;
	//cin >> t;
	while(t--)
		solve();
	return 0;
}

Measured memory_bytes: 3348
#include <stdio.h>

int main(void) {
	int S,h,ha,m,s;
	scanf("%d",&S);
	h=S/3600;
	ha=S%3600;
	m=ha/60;
	s=ha%60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}


Measured memory_bytes: 2100
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;

int main()
{
	unsigned long long N, A, B;
	cin >> N >> A >> B;
	vector<unsigned long long> X(N);

	for (auto i = 0; i < N; ++i)
	{
		cin >> X[i];
	}

	auto sum = 0ull;
	for (auto i = 1; i < N; ++i)
	{
		auto diff = X[i] - X[i - 1];
		if (diff * A < B)
		{
			sum += diff * A;
		}
		else
		{
			sum += B;
		}
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
int n;
std::vector<int> vec;

int main() {
  std::cin >> n;
  vec.assign(n, 0);
  for (int i = 0; i < n; i++) {
    std::cin >> vec[i];
  }
  int ans = 0;
  while (true) {
    for (int i = 0; i < n; i++) {
      if (vec[i] % 2 != 0) {
        std::cout << ans << std::endl;
          return 0;
      }
      vec[i] /= 2;
    }
    ans++;
  }
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("600");
            WillReturn.Add("300");
            WillReturn.Add("220");
            WillReturn.Add("420");
            //520
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("555");
            WillReturn.Add("555");
            WillReturn.Add("400");
            WillReturn.Add("200");
            //755
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("549");
            WillReturn.Add("817");
            WillReturn.Add("715");
            WillReturn.Add("603");
            //1152
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int A = int.Parse(InputList[0]);
        int B = int.Parse(InputList[1]);
        int C = int.Parse(InputList[2]);
        int D = int.Parse(InputList[3]);

        Console.WriteLine(Math.Min(A, B) + Math.Min(C, D));
    }
}


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

int main() {
    double N;
    cin >> N;

    for (int i = 1; i <= N; i++) {
        if (int((double)i * 1.08) == N) {
            cout << i << endl;
            return 0;
        }
    }

    cout << ":(" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
signed main(){
	double x1,y1,x2,y2,x3,y3,x4,y4;
	while( scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4) != EOF ){
		if(max(x1,x2) < min(x3,x4) || min(x1,x2) > max(x3,x4) || max(y1,y2) < min(y3,y4) || min(y1,y2) > max(y3,y4)) cout << "NO" << endl;
		else cout << "YES" << endl;
	}
	return 0;
}

Measured memory_bytes: 3208
/**
  * http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008
  */
object Main {
  def main(args: Array[String]): Unit = {
    Iterator.continually(io.StdIn.readLine()).takeWhile(_ != null).map(_.toInt)
      .map {
        case n if n > 9 * 4 => 0
        case n => {
          val ub = math.min(9, n)
          (for (a <- 0 to ub; b <- 0 to ub; c <- 0 to ub; d <- 0 to ub if a + b + c + d == n) yield 1)
            .length
        }
      }
      .foreach(println)
  }
}

Measured memory_bytes: 61788
// CPP program to find circumference of circle 
#include<bits/stdc++.h> 
using namespace std; 

#define PI 3.1415 

double circumference(double r) 
{ 
	double cir = 2*PI*r; 
	return cir; 
} 

// driver function 
int main() 
{ 
double r;
  cin>>r;
cout<< circumference(r); 
return 0; 
} 


Measured memory_bytes: 3776
using namespace std; 
#include<bits/stdc++.h>
#define pb push_back
#define mk make_pair
#define vect vector<ll>
#define maap map<ll,ll>  
#define MOD 1000000007
#define mit map::iterator
#define pii pair<ll,ll>
#define rep(i,a,b)	for(ll i=a;i< b;i++)
#define fast  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
typedef  long long   int  ll;
//stringstream convert; 
  //  convert << number; 
  //  string s = convert.str();
 ll fact[500005],invfact[500005]; 
 ll power(ll x, ll y)
{
	ll z = 1;
	while(y > 0)
	{
		if(y % 2 == 1)
			z = (z*x)%MOD;
		x = (x*x)%MOD;
		y /= 2;
	}
	return z;
}
 ll inv(ll x)
{
	return power(x,MOD-2);
}
ll divide(ll x, ll y)
{
	return (x*inv(y))%MOD;
}
ll C(ll n, ll k)
{
	if(k > n) return 0;
	return divide(fact[n], (fact[n - k]*fact[k])%MOD);
}
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
bool isPrime(int n) {
 
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
} 
void init(){
	ll p=MOD;
	fact[0]=1;
	ll i;
	for(i=1;i<500005;i++){
		fact[i]=(i*fact[i-1])%p;
	}
	i--;
	invfact[i]=power(fact[i],p-2);
	for(i--;i>=0;i--){
		invfact[i]=(invfact[i+1]*(i+1))%p;
	}
}
ll s;
ll fun(ll a)
{
	if(a==0)
	return 0;
	return a+fun(a-1);
}
priority_queue < pair<ll,ll> , vector<pair<ll,ll> >,greater<pair<ll,ll> > > gq;

#define MAXN   10000001 
ll spf[MAXN]; 
void sieve() 
{ 
    spf[1] = 1; 
    for (ll i=2; i<MAXN; i++) 
        spf[i] = i; 
    for (ll i=4; i<MAXN; i+=2) 
        spf[i] = 2; 
    for (ll i=3; i*i<MAXN; i++) 
    {
        if (spf[i] == i) 
        { 
            for (ll j=i*i; j<MAXN; j+=i) 
                if (spf[j]==j) 
                    spf[j] = i; 
        } 
    } 
} 
set<ll> getFactorization(ll x) 
{ 
    set<ll> ret; 
    while (x != 1) 
    { 
        ret.insert(spf[x]); 
        x = x / spf[x]; 
    } 
    return ret; 
}
ll sm(ll n)
{
	ll i;
	ll k=0;
	while(n>0)
	{
		k=k+n%10;
		n=n/10;
	}
	return k;
}
void ghost()
{   
  	ll i=0,j=0,k=0,n,r=0,q=0,t=0,y=100000000000,m,w;
    	cin>>n;
       double a[n];
       double l=0.0;
       for(i=0;i<n;i++)
       cin>>a[i];
       double dp[n+1][n+1];
       memset(dp,0.0,sizeof(dp));
	   dp[0][0]=1.0;
	   for(i=1;i<=n;i++)
	   {
	   	for(j=0;j<=i;j++)
	   	{ 
	   	    if(j==0)
	   	    dp[i][j]=dp[i-1][j]*(1.0-a[i-1]);
	   	    else
	   		dp[i][j]=dp[i-1][j]*(1.0-a[i-1])+dp[i-1][j-1]*a[i-1];
		   }
	   }
	   	for(j=(n+1)/2;j<=n;j++)
	   	l=l+dp[n][j];
	   cout<<setprecision(10)<<l<<endl;
	}
signed main()
{int test=1;
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
fast
//cin>>test;
while(test--)
ghost();
return 0;
}

  


Measured memory_bytes: 74160
s = input().split()
for i in range(int(s[0])+1):
	if((i * 2 + ((int(s[0])) - i) * 4) == int(s[1])):
		hantei = "OK"
		break
	else:
		hantei = "NG"
if(hantei == "NG"):
	print("No")
else:
	print("Yes")

Measured memory_bytes: 9216
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
using namespace std;
typedef long long ll;
ll MOD = 1e9+7;
#define rep(i,n) for(int i = 0; i < (n); ++i)
int main() {
    int n, a, b;
    cin >> n >> a >> b;
    int max_num = 0;
    max_num = min(a, b);
    int min_num = 0;
    if ( a + b < n ) min_num = 0;
    else             min_num = ( a + b - n );
    cout << max_num << " " << min_num << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
int n,i,j,l,r,m,lv,rv,nv;
char ans[299],c[9];
int ask(int x){
	printf("? ");
	for(int i=0;i<n;++i)printf("%d ",x-i);puts("");fflush(stdout);
	scanf("%s",c);return *c=='R';
}
char toc(int x){return x==1?'R':'B';}
int main(){
	scanf("%d",&n);
	l=n;r=n*2-1;
	lv=ask(n);rv=ask(n*2);
	for(;l<r;){
		m=l+r+1>>1;
		nv=ask(m);
		if(nv==lv)l=m;else r=m-1;
	}
	ans[l+1]=toc(rv);ans[l-n+1]=toc(lv);
	for(i=1;i<=n*2;++i){
		if(i==l+1 || i==l-n+1)continue;
		if(l-n+1<i && i<=l){
			printf("? ");
			for(j=1;j<=n*2;++j)if(j>l+1 || j<l-n+1)printf("%d ",j);
			printf("%d\n",i);fflush(stdout);
			scanf("%s",c);ans[i]=*c;		
		}else{
			printf("? ");
			for(j=1;j<=n*2;++j)if(l-n+1<j && j<=l)printf("%d ",j);
			printf("%d\n",i);fflush(stdout);
			scanf("%s",c);ans[i]=*c;
		}
	}
	printf("! %s\n",ans+1);fflush(stdout);
	return 0;
}

Measured memory_bytes: 724
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			char[] s = scanner.next().toCharArray();
			switch (s[s.length - 1]) {
			case '0':
			case '1':
			case '6':
			case '8':
				System.out.println("pon");
				break;
			case '2':
			case '4':
			case '5':
			case '7':
			case '9':
				System.out.println("hon");
				break;
			default:
				System.out.println("bon");
				break;
			}
		}
	}
}


Measured memory_bytes: 35560
import numpy as np
N = int(input())
AB = ['']*N
for i in range(N):
  AB[i] = list(map(int, input().split()))
#AB = np.array(AB)

AB = sorted(AB, key=lambda x: x[1])
#print(AB)
total = 0
flag = 1
for i in range(N):
  total += AB[i][0]
  if total > AB[i][1]:
    flag = 0
    break
if flag == 1:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 66412
def dfs(i, f):
    if i == n-1:
        return sum(list(map(int, f.split('+'))))
    return dfs(i+1, f + S[i+1]) + dfs(i+1, f + '+' + S[i+1])

def main():
    ans = dfs(0,S[0])
    print(ans)


if __name__ == '__main__':
    S = input()
    n = len(S)
    main()


Measured memory_bytes: 68004
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define mkp(a, b) make_pair(a, b)
#define pb(t) push_back(t)
#define ft first
#define sc second
#define pt(num) cout << num << "\n"
#define moC(a, s, b) (a)=((a)s(b)+MOD)%MOD
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define chmax(a, b) (a<b ? a=b : 0)
#define chmin(a, b) (a>b ? a=b : 0)
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 101010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;



int main(void) {
    ll N, K;
    cin >> N >> K;
    ll i;
    ll x[MAX];
    
    for(i=0; i<N; i++) cin >> x[i];
    
    ll ans=INF;
    for(i=0; i<=N-K; i++) {
        ll l=x[i];
        ll r=x[i+K-1];
        
        if(l>=0) chmin(ans, r);
        else if(r<=0) chmin(ans, -l);
        else chmin(ans, -l+r+min(-l, r));
    }
    
    pt(ans);
}





Measured memory_bytes: 1024
/**
 *      ABC 88 B
 *      author  : kyomukyomupurin
 *      created : 2018-09-01 00:28:05
**/

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N; cin >> N;
    vector<int> a;
    for (int i = 0; i < N; ++i) {
        int x; cin >> x;
        a.push_back(x);
    }
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    
    int Alice = 0; int Bob = 0;
    
    if (N == 1){
        cout << a[0] << endl;
    }

    else {
        for (int i = 0; i < N; i += 2) {
            Alice += a[i];
            Bob += a[i + 1];
        }
        cout << Alice - Bob << endl;
    }

    return 0;
}



Measured memory_bytes: 256
N = int(input())
 
li = [list(map(int,input().split())) for _ in range(N)]

k = 0
while li[k][2] == 0:
    k += 1
 
for x in range(101):
    for y in range(101):

        H = li[k][2]+abs(li[k][0]-x)+abs(li[k][1]-y)
        f = True

        for i in range(N):
            if li[i][2] > 0 and H != li[i][2]+abs(li[i][0]-x)+abs(li[i][1]-y):
                f = False
                break
            # 下2行を書き忘れていた
            elif li[i][2] == 0 and H > abs(li[i][0]-x)+abs(li[i][1]-y):
                f = False
                break
        if f:
            print(x,y,H)
            break
    else:
        continue
    break
 

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
const ll M = 2e5+7;

ll segt[8*M] = {};
void update(int si, int i, ll val, int sl, int sr, ll segt[]) {
    if(i < sl || sr < i)
        return;
    segt[si] = max(segt[si], val);
    if(sl < sr) {
        update(2*si+1, i, val, sl, (sl+sr)/2, segt);
        update(2*si+2, i, val, (sl+sr)/2+1, sr, segt);
    }
}

ll maxt(int si, int ql, int qr, int sl, int sr, ll segt[]) {
    if(qr < sl || sr < ql)
        return 0;
    if(ql <= sl && sr <= qr)
        return segt[si];
    return max(maxt(2*si+1, ql, qr, sl, (sl+sr)/2, segt)
           , maxt(2*si+2, ql, qr, (sl+sr)/2+1, sr, segt));
} 


int main (){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    ll h[n], a[n];
    for(int i = 0; i < n; ++i)
        cin >> h[i];
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    for(int i = 0; i < n; ++i) {
        ll prev = maxt(0, 0, h[i]-1, 0, M-6, segt);
        update(0, h[i], prev+a[i], 0, M-6, segt);
    }
    cout << maxt(0, 0, M-6, 0, M-6, segt);
    return 0;
}


Measured memory_bytes: 9472
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const int maxn = 2e5 + 10;
int A, B, C, D;
int main()
{
    scanf("%d %d %d %d", &A, &B, &C, &D);
    bool flag = true;
    while(A > 0 && C > 0)
    {
        if(flag)
            C -= B;
        else
            A -= D;
        flag = !flag;
    }
    if(A <= 0)
        printf("No");
    else
        printf("Yes");
    return 0;
}


Measured memory_bytes: 3752
#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char const* argv[])
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (abs(a - c) <= d) {
        cout << "Yes" << endl;
    } else if (abs(a - b) <= d and abs(b - c) <= d) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 256