akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



int main(){

	char buf[2];

	scanf("%s",buf);

	if(buf[0] == 'a' || buf[0] == 'i' || buf[0] == 'u' || buf[0] == 'e' || buf[0] == 'o'){

		printf("vowel\n");

	}else{

		printf("consonant\n");
	}

	return 0;
}


Measured memory_bytes: 256
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val Ts = Array.fill(sc.nextInt())(sc.nextInt())
  val sum = Ts.sum
  List.fill(sc.nextInt())(sc.nextInt() -> sc.nextInt()).foreach {
    case (p, x) => println(sum - Ts(p - 1) + x)
  }
}


Measured memory_bytes: 55864
#include <bits/stdc++.h>
#define MAX_N 10000
#define INF 1e9

using namespace std;

typedef int long long ll;
typedef int long l;
typedef pair<int, int> Pii;
const ll MOD = 1000000007;

int dp[101][10001];  // dp[i+1][j]:=i番目までで重さがj以下

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, W;
    int v[100];
    int w[100];
    cin >> n >> W;
    for (int i = 0; i < n; i++) {
        cin >> v[i] >> w[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= W; j++) {
            if (j - w[i] >= 0)
                dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i]);
            else
                dp[i + 1][j] = dp[i][j];
        }
    }

    cout << dp[n][W] << endl;


    return 0;
}


Measured memory_bytes: 7064
#include <stdio.h>
#include <math.h>

int main() {
  int i, j, number_n, max = 1;
  scanf("%d", &number_n);
  for(i = 2; i <= number_n; i++) {
    for(j = 2; ; j++) {
      if(pow(i, j) <= number_n) {
        max = (max < pow(i, j))? pow(i, j) : max;
      } else {
        break;
      }
    }
  }
  printf("%d\n", max);
  return 0;
}


Measured memory_bytes: 384
cnt500 = int(input())
cnt100 = int(input())
cnt50 = int(input())
X = int(input())

all_set = set([])

for i,a in enumerate(range(cnt500+1)):
    tmp500 = i*500
    if tmp500 > X:
        break
    all_set.add((tmp500, 0, 0))
    for i,b in enumerate(range(cnt100+1)):
        tmp100 = i*100
        if tmp100 > X:
            break
        all_set.add((tmp500, tmp100, 0))
        for i,c in enumerate(range(cnt50+1)):
            tmp50 = i*50
            if tmp50 > X:
                break
            all_set.add((tmp500, tmp100, tmp50))

all = []
for a in all_set:
    all.append(sum(a))
print(all.count(X))

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

int main() {
    int a[1000010];
    cin >> a[0];

    int n = 0;
    while (true) {
        if (a[n] % 2 == 0) a[n+1] = a[n] / 2;
        else a[n+1] = 3 * a[n] + 1;
        n++;

        for (int i = 0; i < n; i++) {
            if (a[n] == a[i]) {
                cout << n + 1 << endl;
                return 0;
            }
        }
    }

}

Measured memory_bytes: 3576
#include<bits/stdc++.h>
using namespace std;
const int modulo=(1e9+7),maxn=(1e5+10);
long long dp[maxn][3];
string s;
long long tp=1;
int main()
{
	cin>>s;
	memset(dp,0,sizeof(dp));
	for(int i=0;i<s.size();i++)
	{
		if(s[i]=='?')
		{
			dp[i+1][0]=(dp[i][0]*3+tp)%modulo;
			dp[i+1][1]=(dp[i][1]*3+dp[i][0])%modulo;
			dp[i+1][2]=(dp[i][2]*3+dp[i][1])%modulo;
			tp=tp*3%modulo;
		}
		else if(s[i]=='A')
		{
			dp[i+1][0]=(dp[i][0]+tp)%modulo;
			dp[i+1][1]=dp[i][1];
			dp[i+1][2]=dp[i][2];
		}
		else if(s[i]=='B')
		{
			dp[i+1][0]=dp[i][0];
			dp[i+1][1]=(dp[i][0]+dp[i][1])%modulo;
			dp[i+1][2]=dp[i][2];
		}
		else if(s[i]=='C')
		{
			dp[i+1][0]=dp[i][0];
			dp[i+1][1]=dp[i][1];
			dp[i+1][2]=(dp[i][1]+dp[i][2])%modulo;
		}
	}
	cout<<dp[s.size()][2]<<endl; 
	return 0;
}
/*
      Author:
      Jerryjiang090210
*/

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

using ll = long long;
using Vi = vector<int>;
using Vl = vector<ll>;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

constexpr int I_INF = numeric_limits<int>::max();
constexpr ll L_INF = numeric_limits<ll>::max();

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

void solve() {
    int Q;
    cin >> Q;
    Vl A;
    using bs = bitset<202>;
    vector<bs> mat;
    while (Q--) {
        ll N;
        cin >> N;
        A.resize(N);
        for (ll i = 0; i < N; i++) {
            cin >> A[i];
        }
        string S;
        cin >> S;
        reverse(A.begin(), A.end());
        reverse(S.begin(), S.end());

        constexpr ll mx_d = 61;

        mat.assign(mx_d, bs());

        bool is_zero = true;

        for (ll i = 0; i < N; i++) {
            if (S[i] == '0') {
                for (ll j = 0; j < mx_d; j++) {
                    mat[j][i] = (bool)(A[i] & (1ll << j));
                }
            }
            else {
                constexpr ll bk = 201;

                for (ll j = 0; j < mx_d; j++) {
                    mat[j][bk] = (bool)(A[i] & (1ll << j));
                }

                auto mat_cpy = mat;

                int rank = 0;
                for (ll col = 0; col < bk; col++) {
                    int pivot = -1;
                    for (ll row = rank; row < mx_d; ++row) {
                        if (mat[row][col]) {
                            pivot = row;
                            break;
                        }
                    }

                    if (pivot == -1) continue;
                    swap(mat[pivot], mat[rank]);
                    for (ll row = 0; row < mx_d; ++row) {
                        if (row != rank && mat[row][col]) mat[row] ^= mat[rank];
                    }
                    ++rank;
                }

                for (ll row = rank; row < mx_d; ++row) {
                    if (mat[row][bk]) {
                        is_zero = false;
                        break;
                    }
                }

                if (!is_zero) {
                    break;
                }

                mat = mat_cpy;
            }
        }

        if (is_zero)
            cout << 0 << "\n";
        else
            cout << 1 << "\n";
    }
}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

int main() {
#ifdef FASTIO
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
#endif
#ifdef FILEINPUT
    ifstream ifs("./in_out/input.txt");
    cin.rdbuf(ifs.rdbuf());
#endif
#ifdef FILEOUTPUT
    ofstream ofs("./in_out/output.txt");
    cout.rdbuf(ofs.rdbuf());
#endif
    solve();
    cout << flush;
    return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using VI = vector<int>;
using VL = vector<ll>;
template<class T> using PQ = priority_queue<T, vector<T>, greater<T>>;
#define FOR(i,a,n) for(int (i)=(a);(i)<(n);++(i))
#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);++(i))
#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);--(i))
#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);--(i))
#define each(i, a) for(auto &i : a)
#define SORT(i) sort((i).begin(),(i).end())
#define rSORT(i,a) sort((i).begin(),(i).end(),(a))
#define all(i) (i).begin(),(i).end()
#define out(y,x) ((y) < 0 || h <= (y) || (x) < 0 || w <= (x))
#define line cout << "------------------------\n" 
#define ENDL(i,n) ((i) == (n) - 1 ? "\n" : " ")
#define stop system("pause")
constexpr ll INF = 1000000000;
constexpr ll LLINF = 1LL << 60;
constexpr ll mod = 1000000007;
constexpr ll MOD = 998244353;
const long double pi = acos(-1);
const long 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; }
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& elemnt : v)is >> elemnt; return is; }
template<class T, class U>inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template<class T>inline vector<T> vec(size_t a) { return vector<T>(a); }
template<class T>inline vector<T> defvec(T def, size_t a) { return vector<T>(a, def); }
template<class T, class... Ts>inline auto vec(size_t a, Ts... ts) { return vector<decltype(vec<T>(ts...))>(a, vec<T>(ts...)); }
template<class T, class... Ts>inline auto defvec(T def, size_t a, Ts... ts) { return vector<decltype(defvec<T>(def, ts...))>(a, defvec<T>(def, ts...)); }

int main() {
    init();

    string s, t; cin >> s >> t;
    cout << t << s << "\n";
}


Measured memory_bytes: 256
S = input()

def DFSCalculation(plus_list):
    """return: 合計値"""

    if len(plus_list) == len(S) - 1:
        cand_list = []
        pre_i = 0
        for i in range(len(plus_list)):
            if plus_list[i] == 0:
                pass
            else:
                cand_list.append(S[pre_i : i + 1])
                pre_i = i + 1
        cand_list.append(S[pre_i :])
    
        sum_value = 0
        for x in cand_list:
            sum_value += int(x)
        return sum_value

    else:
        in_plus = DFSCalculation(plus_list + [1])
        not_in_plus = DFSCalculation(plus_list + [0])
        return in_plus + not_in_plus

sum_value = DFSCalculation([])

print(sum_value)

Measured memory_bytes: 3064
import java.util.*;

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

        int sub = b - a;
        int length = 0;
        for (int i = sub; i > 0; i--) {
            length += i;
        }

        System.out.println(length - b);
    }
}

Measured memory_bytes: 23252
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <set>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)
#define mp std::make_pair

const int INF = 1 << 24;
// S N E W(南北東西)
const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};

typedef unsigned long long ull;
typedef std::pair<int,int> P;
typedef std::pair<int,P> State;

int solve(int Y, int M, int D){
    int res = 0;
    while(!(Y == 1000 && M == 1 && D == 1)){
        res++;

        if(D < 19 + (M % 2 || !(Y % 3))){
            D++;
        }else{
            if(M == 10){
                Y++; M = 1; D = 1;
            }else{
                M++; D = 1;
            }
        }
    }

    return res;
}

int main(){
    int T;
    std::cin >> T;

    REP(_, T){
        int Y, M, D;
        std::cin >> Y >> M >> D;

        std::cout << solve(Y, M, D) << std::endl;
    }
}

Measured memory_bytes: 1160
#![allow(unused_parens)]
#![allow(unused_imports)]
#![allow(non_upper_case_globals)]
#![allow(non_snake_case)]
#![allow(unused_mut)]
#![allow(unused_variables)]
#![allow(dead_code)]

use itertools::Itertools;
use proconio::input;
use proconio::marker::{Chars, Usize1};

#[allow(unused_macros)]
#[cfg(debug_assertions)]
macro_rules! mydbg {
    //($arg:expr) => (dbg!($arg))
    //($arg:expr) => (println!("{:?}",$arg));
      ($($a:expr),*) => {
          eprintln!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
      }
}
#[cfg(not(debug_assertions))]
macro_rules! mydbg {
    ($($arg:expr),*) => {};
}

macro_rules! echo {
    ($($a:expr),*) => {
          $(println!("{}",$a))*
      }
}

use std::cmp::*;
use std::collections::*;
use std::ops::{Add, Div, Mul, Sub};

#[allow(dead_code)]
static INF_I64: i64 = 92233720368547758;
#[allow(dead_code)]
static INF_I32: i32 = 21474836;
#[allow(dead_code)]
static INF_USIZE: usize = 18446744073709551;
#[allow(dead_code)]
static M_O_D: usize = 1000000007;
#[allow(dead_code)]
static PAI: f64 = 3.1415926535897932;

trait IteratorExt: Iterator {
    fn toVec(self) -> Vec<Self::Item>;
}

impl<T: Iterator> IteratorExt for T {
    fn toVec(self) -> Vec<Self::Item> {
        self.collect()
    }
}

trait CharExt {
    fn toNum(&self) -> usize;
    fn toAlphabetIndex(&self) -> usize;
    fn toNumIndex(&self) -> usize;
}
impl CharExt for char {
    fn toNum(&self) -> usize {
        return *self as usize;
    }
    fn toAlphabetIndex(&self) -> usize {
        return self.toNum() - 'a' as usize;
    }
    fn toNumIndex(&self) -> usize {
        return self.toNum() - '0' as usize;
    }
}

trait VectorExt {
    fn joinToString(&self, s: &str) -> String;
}
impl<T: ToString> VectorExt for Vec<T> {
    fn joinToString(&self, s: &str) -> String {
        return self
            .iter()
            .map(|x| x.to_string())
            .collect::<Vec<_>>()
            .join(s);
    }
}

trait StringExt {
    fn get_reverse(&self) -> String;
}
impl StringExt for String {
    fn get_reverse(&self) -> String {
        self.chars().rev().collect::<String>()
    }
}

trait UsizeExt {
    fn pow(&self, n: usize) -> usize;
}
impl UsizeExt for usize {
    fn pow(&self, n: usize) -> usize {
        return ((*self as u64).pow(n as u32)) as usize;
    }
}

fn main() {
    input! {
       N: usize,
       A:[i64;N],
    }
    mydbg!(A);

    let mut a = vec![(0, 0); N];
    let mut b = vec![(0, 0); N];
    for i in 0..N {
        a[i] = ((i + 1) as i64 + A[i], i);
        b[i] = ((i + 1) as i64 - A[i], i);
    }
    //let mut ans = HashSet::new();
    let mut ans = 0;
    mydbg!(a);
    mydbg!(b);
    let mut ah = HashMap::new();
    let mut bh = HashMap::new();
    for i in 0..N {
        let mut hp = ah.entry(a[i].0).or_insert(vec![]);
        hp.push(a[i].1);
        let mut hp = bh.entry(b[i].0).or_insert(vec![]);
        hp.push(b[i].1);
    }
    for (key, value) in &ah {
        match bh.get(&key) {
            Some(x) => {
                ans += value.len() * x.len();
            }
            None => {}
        }
    }

    //echo!(ans);
    mydbg!(ans);
    echo!(ans);
}


Measured memory_bytes: 39704
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	int n;
	cin >> n;

	vector<pair<int, int>> arr(n);
	for (int i = 0; i < n; i++)
	{
		cin >> arr[i].first;
		arr[i].second = i;
	}

	sort(arr.begin(), arr.end());
	for (int i = 0; i < n; i++)
	{
		cout << arr[i].second  + 1<< " ";
	}

	cout << endl;
}

Measured memory_bytes: 1664
#!/usr/bin/ruby
_,M,s,*A=`dd`.split.map &:to_i
*b=a=[r=0]*(2*M+1)
A.each{|e|
	e+=M if e<s
	k=e-s
	if k>1
		a[s+1]+=1
		a[e]-=k
		a[e+1]+=k-1
	end
	r += k
	s = e%M
}
0.upto(2*M-2){|i|
	a[i+1] += a[i]
}
0.upto(2*M-2){|i|
	a[i+1] += a[i]
}
p r - M.times.map{|i|a[i]+a[i+M]}.max

Measured memory_bytes: 12944
n = int(input())
x=[]
y=[]
h=[]
for i in range(0,n):
    a,b,c = map(int,input().split())
    x.append(a)
    y.append(b)
    h.append(c)
 
 
 
for i in range(0,101):
    for j in range(0,101):
        tmph=0
        flag = True
        for k in range(0,n):
            if tmph == 0 and h[k] != 0:
                tmph=abs(x[k]-i)+abs(y[k]-j)+h[k]
                break
        for k in range(0,n):
            calch = tmph - abs(x[k]-i)-abs(y[k]-j)
            if h[k] != max(calch,0):
                flag = False
                break
        if flag == False:
            continue
        elif tmph == 0:
            flag2 = True
            for c in range(0,101):
                if i == x[c] and j == y[c]:
                    flag2 = False
                    break
            if flag2:
                ansx = i
                ansy = j
                ansh = 1
        else:
            ansx=i
            ansy=j
            ansh=tmph
 
print(ansx,ansy,ansh)

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int pre[100000], in[100000], post[100000], n, pos, cnt;
void rec(int l, int r) { if (l >= r) { return; }int root = pre[pos++]; int m = 0; for (int i = 0; i < n; i++) { if (in[i] == root) { m = i; } }rec(l, m); rec(m + 1, r); post[cnt] = root; cnt++; }
int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> pre[i]; }for (int i = 0; i < n; i++) { cin >> in[i]; }rec(0, n); for (int i = 0; i < n; i++) { if (i) { cout << ' '; }cout << post[i]; }cout << endl; return 0; }

Measured memory_bytes: 1168
h, w = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(h)]

count = 0
ans = []
for i in range(0, h-1, 2):
    for j in range(w):
        if lst[i][j] % 2 == 1:
            count += 1
            if j == w-1:
                lst[i+1][j] += 1
                ans.append((i+1, j+1, i+2, j+1))
            else:
                lst[i][j+1] += 1
                ans.append((i+1, j+1, i+1, j+2))
    for j in reversed(range(w)):
        if lst[i+1][j] % 2 == 1:
            if j == 0 and i+1 == h-1:
                pass
            elif j == 0:
                lst[i+2][j] += 1
                ans.append((i+2, j+1, i+3, j+1))
                count += 1
            else:
                lst[i+1][j-1] += 1
                ans.append((i+2, j+1, i+2, j))
                count += 1
if h % 2 == 1:
    for j in range(w):
        if lst[-1][j] % 2 == 1:
            if j == w-1:
                pass
            else:
                lst[-1][j+1] += 1
                ans.append((h, j+1, h, j+2))
                count += 1
                
print(count)
for a,b,c,d in ans:
    print(a,b,c,d)

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

using namespace std;

typedef long long ll;

const int max_n = 101010;
int depth[max_n];
int max_depth[max_n];

vector<int> g[max_n];

int dfs(int x, int d){
	depth[x] = d;

	int mx = d;
	for(int y : g[x]){
		if(depth[y] == -1){
			mx = max(mx, dfs(y, d + 1));
		}
	}

	return max_depth[x] = mx;
}

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

	int n, u, v;
	cin >> n >> u >> v;
	u--; v--;

	rep(i, n - 1){
		int a, b;
		cin >> a >> b;
		a--; b--;

		g[a].push_back(b);
		g[b].push_back(a);
	}

	rep(i, n){
		depth[i] = -1;
		max_depth[i] = -1;
	}

	dfs(v, 0);

	rep(i, n) cerr << depth[i] << (i == n- 1 ? "\n" : " ");
	rep(i, n) cerr << max_depth[i] << (i == n- 1 ? "\n" : " ");

	int t = u;
	int canuse_d = max_depth[u];
	int canuse_i = u;
	for(int i = 0; i < depth[u]; i++){
		for(int y : g[t]){
			if(depth[y] == depth[t] - 1){
				if(depth[u] - depth[y] < depth[y]){
					if(canuse_d < max_depth[y]){
						canuse_d = max_depth[y];
						canuse_i = y;
					}
				}
				t = y;
			}
		}
	}
	
	cout << canuse_d - 1 << endl;
}


Measured memory_bytes: 10368
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<utility>
#include<map>
#include<stack>
#include<queue>
#include<math.h>


using namespace std;




int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif


	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	long long int n;
	long long int k;
	cin >> n >> k;
	long long int arr[n];

	for (long long int i = 0; i < n; i++)
	{	cin >> arr[i];

	}
	vector<bool>dp(k + 1, false);
	for (long long int i = 1; i < k + 1; i++)
	{
		for (long long int j = 0; j < n; j++)
		{
			if (i >= arr[j] && !dp[i - arr[j]])
			{
				dp[i] = true;
			}
		}
	}
	(dp[k] == true) ? cout << "First" : cout << "Second";
	cout << endl;




	return 0;


}


Measured memory_bytes: 3656
from bisect import bisect_right, bisect_left
from collections import Counter, deque
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import groupby, permutations, combinations, product
from sys import stdin, stderr


# 最大公約数（ユークリッドの互除法）
# Python3.5 で math.gcd()が追加され、
# AtCoder環境と最新環境でパッケージが分かれてしまったので、自分で書いておく
def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


# 拡張ユークリッド互除法
# 正整数x, y について、a*x + b*y == gcd(x,y)なるa,bを返す。
# 特に、互いに素なるx, yについては a*x + b*y == 1 となる a, b。
def exgcd(x, y):
    if y == 0:
        return 1, 0
    a, b = exgcd(y, x % y)
    return b, a - (x // y) * b


# 最小公倍数
def lcm(x, y):
    m = gcd(x, y)
    return (x // m) * (y // m)


def main():
    N = int(input())
    
    return N // 2 if N % 2 == 0 else N // 2 + 1


if __name__ == "__main__":
    print(main())

Measured memory_bytes: 3564
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
//#define uint __int128_t

#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define low(a,b) lower_bound(all(a),(b))-(a).begin()
#define upp(a,b) upper_bound(all(a),(b))-(a).begin()
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<vint> vvint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N;
double p[100010];
double dp[3030][3030];

signed main() {
    IOS();
    //(1ll<<N)シフト演算のオーバーフローに気をつける
    cin>>N;
    rep(i,0,N)cin>>p[i];
    dp[0][0]=1;
    rep(i,0,N){
        rrep(j,0,N+1){
            dp[i+1][j]+=dp[i][j-1]*p[i];
            dp[i+1][j-1]+=dp[i][j-1]*(1-p[i]);
        }
    }
    double ans=0;
    rep(i,(N+1)/2,N+1){
        ans+=dp[N][i];
        //printf("%.10lf\n",dp[N][i]);
    }
    printf("%.10lf\n",ans);
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
    return 0;
}

Measured memory_bytes: 71936
#include <bits/stdc++.h>
using namespace std;
 
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}

int main(){

ios::sync_with_stdio(false);
cin.tie(0);

long long int n;
cin>>n;

long long int n500=0;

n500=n/500;


long long int n2=n%500;

long long int n5=0;

n5=n2/5;


cout << n500*1000+n5*5<<endl;




}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;

LL res, res2;
int k, i, j, l, f;
char last, t[105];
string s, s2;
set<int> zb[135];

bool same(int a, int b) {
	if (zb[a].size() != zb[b].size()) return false;
	for (auto& w : zb[a]) if (zb[b].find(w) == zb[b].end()) return false;
	return true;
}

int main() {
scanf("%s", t);
s = t;
scanf("%d", &k);
s2 = "";
for (i=0;i<min(k, 130);i++) s2 += s;
last = s2[0];
for (i=1;i<s2.size();i++) {
	if (s2[i] == last) {
		zb[i / s.size()].insert(i % s.size());
		//printf("ins %d %d\n", i / s.size(), i % s.size());
		last = 'A';
	} else {
		last = s2[i];
	}
}
f = 0;
for (i=1;i<min(k, 130);i++) {
	for (j=0;j<i;j++) if (same(i, j)) {
		f = 1;
		break;
	}
	if (f) break;
}
//printf("%d %d\n", i, j);
if (f) {
	res = 0;
	for (l=0;l<j;l++) res += zb[l].size();
	res2 = 0;
	for (l=j;l<i;l++) res2 += zb[l].size();
	k -= j;
	res += (res2 * (k / (i - j)));
	for (l=j;l<j + k % (i - j);l++) res += zb[l].size();
} else {
	res = 0;
	for (i=0;i<min(k, 130);i++) res += zb[i].size();
}
printf("%lld\n", res);
}





Measured memory_bytes: 512
def main():
    n = int(input())
    a = 1
    b = n
    a_r = int(n**0.5) + 1
    for i in range(1, a_r):
        if n % i == 0:
            b_tmp = n // i
            if i + b_tmp < a + b:
                a = i
                b = b_tmp
    print(a+b-2)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
import math
A, B, X = list(map(int, input().split()))
if X >= (A**2)*B / 2:
    print(math.degrees(math.atan2(2*((A**2)*B - X), A**3)))
else:
    print(math.degrees(math.atan2(A*B*B, 2 * X)))

Measured memory_bytes: 62380
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<tuple>
#include<map>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<math.h>
using namespace std;
int main(){
    string n;
    cin >> n;

    int sum =0;
    for(int i=0;i<n.size();i++){
        sum += int(n.at(i))-48;
    }
    //cout << sum << endl; 

    if(sum%9==0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 3748
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#define len(X) ((int)(X).size())

#ifdef __LOCAL
#define DBG(X) cout << #X << "=" << (X) << '\n';
#define SAY(X) cout << (X) << '\n';
#else
#define DBG(X)
#define SAY(X)
#endif

#define M_PI       3.14159265358979323846

using namespace std;

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

const int INT_INF = (int)(2e9);
const ll  LL_INF = (ll)(2e18);

const int NIL = -1;
static mt19937 _g(time(nullptr));

std::string pad(int num)
{
    char buffer[4];
    std::snprintf(buffer, sizeof(buffer), "%03d", num);
    return buffer;
}

inline ll randint(ll a, ll b) { ll w = (_g() << 31LL) ^ _g(); return a + w % (b - a + 1); }
inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); };
template<typename T> inline T sign(T x) { return T(x > 0) - T(x < 0); }
template<typename T, typename S> inline ostream& operator<<(ostream& os, const pair<T, S> p) { cout << "[" << p.first << ";" << p.second << "]"; return os; }
template<typename T> inline ostream& operator<<(ostream& os, const vector<T>& v) { for (auto el : v) cout << el << " "; return os; }
template<typename T> inline T fetch() { T ret; cin >> ret; return ret; }
template<typename T> inline vector<T> fetch_vec(int sz) { vector<T> ret(sz); for (auto& elem : ret) cin >> elem; return ret; }

#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif

int solve()
{
    ll  N, K;
    cin >> N >> K;

    ll R, S, P;
    cin >> R >> S >> P;

    string game;
    cin >> game;

    ll ans = 0;
    int i = 0;

    while (i < game.length())
    {
        if (i >= K && game[i - K] == game[i])
        {
            game[i] = '?';
        }
        else
        {
            switch (game[i]) {
                case 'r':
                    ans += P;
                    break;
                case 's':
                    ans += R;
                    break;
                case 'p':
                    ans += S;
                    break;
            }
        }
        ++i;
    }

    return ans;
}

int main()
{
    cout << solve() << endl;

    return 0;
}

Measured memory_bytes: 512
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pi acos(-1.0)
#define ll long long
#define vi vector<int>
#define mod 1000000007
#define C 0.5772156649
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pii pair<int,int>
#define cd complex<double>
#define ull unsigned long long
#define base 1000000000000000000
#define fio ios::sync_with_stdio(false);cin.tie(0)

using namespace std;

const double g=10.0,eps=1e-12;
const int N=200000+10,maxn=200000+10,inf=0x3f3f3f3f,INF=0x3f3f3f3f3f3f3f3f;

vi v[N];
int pre[N],ans1[N],ans2[N],suf[N];
bool ban[N];
void dfs(int u,int f,int dis,int &ma,int &id)
{
    if(ma<dis)
    {
        ma=dis;
        id=u;
    }
    for(int i=0;i<v[u].size();i++)
    {
        int x=v[u][i];
        if(x!=f)
        {
            pre[x]=u;
            dfs(x,u,dis+1,ma,id);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int a,b;scanf("%d%d",&a,&b);
        v[a].pb(b),v[b].pb(a);
    }
    int id1,id2,ma=0;
    dfs(1,-1,0,ma,id1);
    ma=0;
    dfs(id1,-1,0,ma,id2);
    int now=id2;
    while(now!=id1)
    {
        ban[now]=1;
        now=pre[now];
    }
    ban[id1]=1;
    now=id2;
    while(now!=id1)
    {
        for(int i=0;i<v[now].size();i++)
            if(!ban[v[now][i]]&&v[v[now][i]].size()>1)
                return 0*puts("-1");
        now=pre[now];
    }
    for(int i=0;i<v[now].size();i++)
        if(!ban[v[now][i]]&&v[v[now][i]].size()>1)
            return 0*puts("-1");
    now=id2;
    int cnt=0;
    while(now!=id1)
    {
        int te;
        if(now==id2)te=v[now].size()-1;
        else te=v[now].size()-2;
        ans1[cnt+te+1]=cnt+1;
        for(int i=1;i<=te;i++)
            ans1[cnt+i]=cnt+i+1;
        cnt+=te+1;
        suf[pre[now]]=now;
        now=pre[now];
    }
    int te=v[now].size()-1;
    ans1[cnt+te+1]=cnt+1;
    for(int i=1;i<=te;i++)
        ans1[cnt+i]=cnt+i+1;
//    for(int i=1;i<=n;i++)printf("%d ",ans1[i]);
//    puts("");
    now=id1;cnt=0;
    while(now!=id2)
    {
        int te;
        if(now==id1)te=v[now].size()-1;
        else te=v[now].size()-2;
//        printf("%d\n",te);
        ans2[cnt+te+1]=cnt+1;
        for(int i=1;i<=te;i++)
            ans2[cnt+i]=cnt+i+1;
        cnt+=te+1;
        now=suf[now];
    }
    te=v[now].size()-1;
    ans2[cnt+te+1]=cnt+1;
    for(int i=1;i<=te;i++)
        ans2[cnt+i]=cnt+i+1;
//    for(int i=1;i<=n;i++)printf("%d ",ans2[i]);
//    puts("");
    int an;
    for(int i=1;i<=n;i++)
    {
        if(ans1[i]>ans2[i])
        {
            an=2;
            break;
        }
        else if(ans1[i]<ans2[i])
        {
            an=1;
            break;
        }
    }
    for(int i=1;i<=n;i++)printf("%d ",an==1?ans1[i]:ans2[i]);puts("");
    return 0;
}
/***********************

***********************/


Measured memory_bytes: 18944
<?php
  
fscanf(STDIN, "%d %d", $n, $k);
$array = [];
$sum = 0;

for($i = 0; $i < $n; $i++){
    fscanf(STDIN,  "%d %d", $a, $b);
    $array[$a] += $b;
}

uksort($array, function($a, $b){
    return $a <=> $b;
});

foreach($array as $key => $value){
    $sum += $value;
    if($sum >= $k){
        print $key; 
    break;
    };
}

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

int main(){
  int n, m, a, p, x;
  vector<int> t;
  cin >> n;
  t.resize(n);
  for(int i=0;i<n;i++){
    cin >> a;
    t[i] = a;
  }
  cin >> m;
  vector< vector<int> > px;
  px.resize(m);
  for(int i=0;i<m;i++){
    cin >> p >> x;
    px[i].resize(2);
    px[i][0] = p;
    px[i][1] = x;
  }
  for(int i=0;i<m;i++){
    int total = 0;
    for(int j=0;j<n;j++){
      if(j==px[i][0]-1){
        total += px[i][1];
      }
      else{
        total += t[j];
      }
    }
    cout << total << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import operator
while 1:
    n = int(input())
    if n == 0:break

    s = [list(map(int,input().split())) for i in range(n)]
    e = s[:]
    s.sort(key = operator.itemgetter(1))
    e.sort(key = operator.itemgetter(2))
    s_i = e_i = 0
    w = 0
    for i in range(n*2):
        if e_i < len(e) and s[s_i][1] >= e[e_i][2]:
            w -= e[e_i][0]
            e_i += 1
        else:
            w += s[s_i][0]
            s_i += 1

        if w > 150:
            print('NG')
            break
        if i == n*2-1 or s_i >= len(s):
            print('OK')
            break

Measured memory_bytes: 6724
#include <iostream>
#include <algorithm>
#include <vector>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

constexpr int INF = 1 << 30;
constexpr int X = 50;

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> xs(n), ys(n);
    for (auto& x : xs) std::cin >> x;
    for (auto& y : ys) std::cin >> y;

    auto dp = vec(1 << n, vec(X + 1, INF));
    dp[0][0] = 0;
    for (int b = 0; b < (1 << n); ++b) {
        int i = __builtin_popcount(b);

        for (int a = 0; a <= X; ++a) {
            for (int j = 0; j < n; ++j) {
                if ((b >> j) & 1) continue;

                bool side = ((i - j) % 2 == 0);
                int x = (side ? xs[j] : ys[j]);
                if (x < a) continue;

                int c = 0;
                for (int k = j + 1; k < n; ++k) {
                    if ((b >> k) & 1) ++c;
                }

                dp[b | (1 << j)][x] =
                    std::min(dp[b | (1 << j)][x], dp[b][a] + c);
            }
        }
    }

    int ans = *std::min_element(dp.back().begin(), dp.back().end());
    std::cout << (ans == INF ? -1 : ans) << std::endl;
}

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

    solve();

    return 0;
}


Measured memory_bytes: 65792
N = int(input())
# とりあえず先頭の性別を取得する
print(0)
begin = input()

l, r = 0, N
while r - l > 1:
    mid = (l+r)//2
    print(mid)
    sex = input()
    if sex == "Vacant":
        l = mid
        break
    elif mid % 2 == 0:
        if sex != begin:
            r = mid
        else:
            l = mid
    else:
        if sex != begin:
            l = mid
        else:
            r = mid

print(l)


Measured memory_bytes: 74740
#include<bits/stdc++.h>                                                         
using namespace std;
int main(){
  string c;
  cin >> c;
  if(c.at(0)=='a' || c.at(0)=='i' || c.at(0)=='u' || c.at(0)=='e' || c.at(0)=='o')
    cout << "vowel" << endl;
  else
    cout << "consonant" << endl;
}


Measured memory_bytes: 256
import { readFileSync } from 'fs'

const range = (length: number) =>
  [...Array(length).keys()]

function main(input: string) {
  const [header, ...lines] = input.split('\n')
  const [h, w, k] = header.split(' ').map(Number)

  // すべてのマス
  const cells = lines.flatMap((v, row) =>
    v.split('').map((color, col) => ({ color, row, col }))
  )

  // 行・列選びパターン
  const pattarn = range(1 << h << w).map(mask => {
    const rows = new Set(range(h).filter(v => (mask >> w >> v) & 1))
    const cols = new Set(range(w).filter(v => (mask >> v) & 1))

    return { rows, cols }
  })

  const result = pattarn.filter(({ rows, cols }) => {
    const blackCells = cells.filter(cell =>
      cell.color === '#' && !rows.has(cell.row) && !cols.has(cell.col)
    )

    return blackCells.length === k
  })

  console.log(result.length)
}

main(readFileSync('/dev/stdin', 'utf8').trim())


Measured memory_bytes: 36564
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int MOD = 1000000007;


signed lsm(int a, int b){
    int a0=a,b0=b;
    if(a0>b0)swap(a0,b0);
    while(a0!=0){
        b0=b0%a0;
        swap(a0,b0);
    }
    return b0;
}
signed main(){
    int n,ans,ala,p,q;
   cin>>n;
  
   int a[n],u[n],d[n];
    cin >>a[0];
    u[0]=a[0];
    for(int i=1;i<n;i++){
        cin>>a[i];
        u[i]=lsm(u[i-1],a[i]);
    }
    d[n-1]=a[n-1];
    for(int i=n-2;i>=0;i--){
        d[i]=lsm(d[i+1],a[i]);
    }
    ans=max(u[n-2],d[1]);
    for(int i=1;i<n-1;i++){
        ans=max(ans,lsm(u[i-1],d[i+1]));
    }

  
    cout<<ans;
  
    return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>

int main(void) {
  while (1) {
    int i,j, H, W;
    scanf("%d %d", &H, &W);

    if ((H == 0) && (W == 0))
      break;

    for (i = 0; i < H; i++) {
      for (j = 0; j < W; j++) {
        if (i % 2)
          if (j % 2)
            printf("#");
          else
            printf(".");
        else
          if (j % 2)
            printf(".");
          else
            printf("#");
      }
      printf("\n");
    }
    printf("\n");
  }
  return 0;
}

Measured memory_bytes: 572
#include "bits/stdc++.h"

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

constexpr int atcoder_mod = 1e9+7;

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

vector<ll> enum_div(ll n){
	vector<ll> ret;
	for(ll i=1;i*i<=n;++i){
		if(n%i==0){
			ret.push_back(i);
			if(i*i!=n){
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

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

	int N=in();
	int num = 0;
	REP(i,N){
		int v=in();
		if(enum_div(v).size()==2) num++;
	}
	
	out(num);
	return 0;
}



Measured memory_bytes: 3172
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
	int a,b;
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	
	cin>>a>>b;
	int tmp = b,note=0;
	while(tmp){
		tmp/=10;
		note++;
	}
	
	int ans = a*(int)pow(10,note)+b;

	
	if((int)sqrt(ans)*(int)sqrt(ans)==ans)
		cout<<"Yes"<<endl;
	else 
		cout<<"No"<<endl;
	
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define pb push_back
const int maxn = 10000;
const int INF32 = 1'050'000'000;
const long long INF64 = 4'000'000'000'000'000'000;
const int MOD7 = 1'000'000'007;
const int MOD9 = 1'000'000'009;
const int mod = MOD7;

void ERROR(int num) { printf("ERROR%d!\n",num); }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
int dx[8]={-1,0,1,0,1,1,-1,-1};
int dy[8]={0,-1,0,1,1,-1,1,-1};


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

    string S;
    cin >> S;

    int l = S.length();
    reverse(S.begin(), S.end());
    vector<ll> sum;
    sum.resize(l+1,0);
    vector<ll> cnt;
    cnt.resize(2019,0);

    ll total = 0;
    ll ten = 1;
    cnt[0] = 1;
    for(int i = 0; i<l; i++){
    	sum[i+1] = (sum[i] + (S[i]-'0')*ten%2019+2019)%2019;
    	//cout << "sum[i+1]: " << sum[i+1] << " , total=" << total << endl; 
    	total += cnt[sum[i+1]];
    	cnt[sum[i+1]]++;
    	ten = ten*10%2019;
    }

    cout << total << endl;
}

Measured memory_bytes: 5212
ans = 'Yes'
m = []
t_last = x_last = y_last = 0
N = int(input())
for i in range(0, N):
  m.append(list(map(int, input().split())))

for l in m:
  t = abs(l[0] - t_last)
  mv = abs(l[1] - x_last) + abs(l[2] - y_last)
  if mv > t or (t - mv) % 2 != 0 :
    ans = 'No'
    break
  t_last=l[0]
  x_last=l[1]
  y_last=l[2]


print(ans)


Measured memory_bytes: 27380
#include <stdio.h>
#include <math.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    char s[n];
    scanf("%s", &s);
    int i, ans = 0;
    for (i = 0; i < n; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            ans += 1;
            i += 2;
        }
    }
    printf("%d\n", ans);

    return 0;
}


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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

// ====================================================================

int main() {
  ll a, b, c, k;
  cin >> a >> b >> c >> k;

  if (k <= a) {
    cout << k << endl;
  } else if (k <= a + b) {
    cout << a << endl;
  } else {
    cout << a - (k - a - b) << endl;
  }
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define f first
#define s second
#define mp make_pair
#define pi M_PI
#define inf 600000
#define eps (1e-11)
#define equals(a,b) (fabs((a)-(b))<eps)
using namespace std;

class Point{
public:
  double x,y;
  Point(double x=0,double y=0):x(x),y(y){}

  Point operator+(Point p){ return Point(x+p.x,y+p.y);}
  Point operator-(Point p){ return Point(x-p.x,y-p.y);}
  Point operator*(double k){ return Point(x*k,y*k);}
  Point operator/(double k){ return Point(x/k,y/k);}
  bool operator<(Point p)const{ return (x!=p.x ? x<p.x : y<p.y);}
  bool operator==(Point p)const{ return fabs(x-p.x)<eps && fabs(y-p.y)<eps;}

  double abs(){ return sqrt(norm());}
  double norm(){ return (x*x+y*y);}
};
typedef Point Vector;

class Segment{
public:
  Point p1,p2;
  Segment(Point p1=Point(),Point p2=Point()):p1(p1),p2(p2){}
};
typedef Segment Line;

class Circle{
public:
  Point c;
  double r;
  Circle(Point c=Point(),double r=0.0):c(c),r(r){}
};

double norm(Vector a){ return (a.x*a.x+a.y*a.y);}
double abs(Vector a){ return sqrt(norm(a));}
double dot(Vector a,Vector b){ return (a.x*b.x+a.y*b.y);}
double cross(Vector a,Vector b){ return (a.x*b.y-a.y*b.x);}

Point project(Segment s,Point p){
  Vector base=(s.p2-s.p1);
  double r=(dot(p-s.p1,base)/base.norm());
  return (s.p1+base*r);
}

pair<Point,Point> getCrossPoints(Circle c,Line l){
  Vector pr=project(l,c.c);
  Vector e=(l.p2-l.p1)/abs(l.p2-l.p1);
  double base=sqrt(c.r*c.r-norm(pr-c.c));
  return mp(pr+e*base,pr-e*base);
}

double getDistanceLP(Line l,Point p){
  return abs(cross(l.p2-l.p1,p-l.p1)/abs(l.p2-l.p1));
}

bool intersect(Circle c,Line L){
  double dis=getDistanceLP(L,c.c);
  if((dis-c.r)<eps)return true;
  return false;
}

int n;
vector<Circle> vc;

bool ok(double mid){

  Line L(Point(-inf,mid),Point(inf,mid));
  vector<pair<double,double> > v;
  for(int i=0;i<n;i++){
    if(!intersect(vc[i],L))continue;
    pair<Point,Point> pp=getCrossPoints(vc[i],L);
    double mind=min(pp.f.x,pp.s.x),maxd=max(pp.f.x,pp.s.x);
    v.push_back(mp(mind,maxd));
  }
  v.push_back(mp(inf,inf));

  double sum=0,x=v[0].f;
  for(int i=0;i<v.size()-1;i++){
    if(v[i].f<v[i+1].f && v[i+1].s<v[i].s){
      sum+=abs(x-v[i].s);
      if((mid*2-sum)<eps)return true;
      x=v[i+2].f;
      sum=0;
      i++;
      continue;
    }
    if(v[i+1].f<v[i].f && v[i].s<v[i+1].s){
      x=v[i+1].f;
      continue;
    }
    sum+=abs(v[i].s-x);
    if(v[i+1].f<v[i].s)x=v[i].s;
    else {
      if((mid*2-sum)<eps)return true;
      sum=0;
      x=v[i+1].f;
    }
  }
  return false;
}

int main()
{
  double x,r;

  while(1){
    cin>>n;
    if(n==0)break;
    vc.clear();
    double maxr=0;
    for(int i=0;i<n;i++){
      cin>>x>>r;
      vc.push_back(Circle(Point(x,0),r));
      maxr=max(maxr,r);
    }

    double l=0;r=maxr;
    for(int i=0;i<40;i++){
      double m=(l+r)/2.0;
      if(ok(m))l=m;
      else r=m;
    }
    printf("%.10f\n",l*2);
  }
  return 0;
}

Measured memory_bytes: 4124
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
int main(){
  long long A, B, C, K; cin >> A >> B >> C >> K;
  long long ans = 0;
  if(K <= A){
    ans = K;
  } else if(K <= A+B){
    ans = A;
  } else {
    ans = A - (K-A-B);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,Q,K,A,B;
string S;
//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
typedef pair<ll, ll> P;
const ll INF = (1LL<<58);

int calc(mat &G, int h, int w){
    int res = 0;
    rep(i,H){
        rep(j, W){
            if(G[i][j] && (h>>i)&1 && (w>>j)&1) ++res;
        }
    }
    return res;
}

int main() {
    cin>>H>>W>>K;
    mat memo(H, vec(W, 0));
    rep(i,H){
        rep(j, W){
            char c;
            cin>>c;
            memo[i][j] = c == '#';
        }
    }
    ll res = 0;
    rep(h, (1<<H)){
        rep(w, (1<<W)){
            res += (calc(memo, h, w) == K);
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 3608
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include<algorithm> 
#include <iomanip>
#include <math.h>
#include <iostream>
#include <bitset>
#include <map>
#include<numeric>
#include<list>

#define db double
#define vi vector<int>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define maxn 5005
#define mod 998244353
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vll vector<ll>
#define vpi vector<pii>
#define vpll vector<pll>
#define vv(z,a,b) vector<vector<int>>z(a,vector<int>(b))
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(c) begin(c),end(c)
#define pp pair<int,int>
#define fix(n) fixed << setprecision(n)
#define gmax(a,b) __gcd(a,b)
#define gmin(a,b) a/__gcd(a,b)*b
using namespace std;
//obj;
class binary{
public:
    bool isOK(int index, int key,vi a) {
    if (a[index] >= key) return true;
    else return false;
}
int binary_search(int key,vi a) {
   
    int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)a.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key,a)) ok = mid;
        else ng = mid;
    }
    return ok;
}
}obj;

int main(){
    int h,w,k;cin>>h>>w>>k;
    int ans=0;
    vector<vector<char>>a(h,vector<char>(w));
    rep(i,h)rep(j,w)cin>>a.at(i).at(j);
    for(int bits=0;bits<(1<<h);bits++){
        for(int bits2=0;bits2<(1<<w);bits2++){
            int sin=0;
            rep(i,h){
                rep(j,w){
                    if((((bits>>i)&1)==0)&&(((bits2>>j)&1)==0)){
                        if(a.at(i).at(j)=='#')sin++;
                    }
                }
            }
            if(sin==k)ans++;
        }
    }
    cout<<ans<<endl;
}




Measured memory_bytes: 3600
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, k = map(int, readline().split())
ans = 0
for i in range(k + 1, n + 1):
    cnt = 0
    max_x = n // i
    cnt += max_x * (i - k)
    low = max_x * i + k
    if low <= n:
        high = min((max_x + 1) * i - 1, n)
        cnt += high - low + 1
    ans += cnt
if k == 0:
    ans -= n
print(ans)


Measured memory_bytes: 3064
#include <cstdio>
#include <climits>
#include <algorithm>
using namespace std;
int n, col[10000];
int calc(int x, int c) {
    if (col[x]==c) return n;
    int p=x-1, q=x+1;
    int cnt=1;
    for (;p>=0;p--) {
        if (col[p]==c) cnt++;
        else break;
    }
    for (;q<n; q++) {
        if (col[q]==c) cnt++;
        else break;
    }
    if (cnt<4) return n;
    else if (p<0||q>=n) return n-cnt;
    else if (col[p]!=col[q]) return n-cnt;

    int res=n-cnt;
    while (true) {
        cnt=0;
        c=col[p];
        for (;p>=0;p--) {
            if (col[p]==c) cnt++;
            else break;
        }
        for (;q<n; q++) {
            if (col[q]==c) cnt++;
            else break;
        }
        if (cnt<4) return res;
        else if (p<0||q>=n) return res-cnt;
        else if (col[p]!=col[q]) return res-cnt;
        res-=cnt;
    }
    return res;
}
int main() {
    while (scanf("%d",&n)) {
        if (!n) break;
        for (int i=0; i<n; i++) {
            scanf("%d",&col[i]);
        }
        int res=INT_MAX/2;
        for (int i=0; i<n; i++) {
            for (int j=1; j<=3; j++) {
                res=min(res,calc(i,j));
            }
        }
        printf("%d\n",res);
    }
}

Measured memory_bytes: 0
import sys
import heapq
from bisect import insort_right
input = sys.stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [-a for a in A]
heapq.heapify(A)
  
for i in range(M):
  tmp = heapq.heappop(A)
  heapq.heappush(A,int(tmp/2))
print(sum([-a for a in A]))

Measured memory_bytes: 14300