akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<stdio.h>
#include<time.h>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	ll m, n, k;
	cin>>m>>n>>k;
	vector<vector<vector<ll> > > mp(m + 1, vector<vector<ll> >(n + 1, vector<ll>(3, 0)));
	REP(i, m + 1) {
		REP(j, n + 1) {
			if(i == 0 || j == 0) {
				mp[i][j][0] = mp[i][j][1] = mp[i][j][2] = 0;

			} else {
				mp[i][j][0] = mp[i][j - 1][0];
			    mp[i][j][1] = mp[i][j - 1][1];
				mp[i][j][2] = mp[i][j - 1][2];
				char gomi;
				cin>>gomi;
				if(gomi == 'J') {
					++mp[i][j][0];
				}
				if(gomi == 'O') {
					++mp[i][j][1];
				}
				if(gomi == 'I') {
					++mp[i][j][2];
				}
			}
		}
	}
	FOR(i, 1, n + 1) {
		FOR(j, 1, m + 1) {
			mp[j][i][0] += mp[j - 1][i][0];
			mp[j][i][1] += mp[j - 1][i][1];
			mp[j][i][2] += mp[j - 1][i][2];
		}
	}
	REP(i, k) {
		ll a, b, c, d;
		cin>>a>>b>>c>>d;
		cout<<mp[c][d][0] - mp[a - 1][d][0] - mp[c][b - 1][0] + mp[a - 1][b - 1][0]<<" "<<mp[c][d][1] - mp[a - 1][d][1] - mp[c][b - 1][1] + mp[a - 1][b - 1][1]<<" "<<mp[c][d][2] - mp[a - 1][d][2] - mp[c][b - 1][2] + mp[a - 1][b - 1][2]<<endl;
	}
}

Measured memory_bytes: 57476
#include <stdio.h>

#define STACKSZ ( 10 )

/** Application main entry point. */
int main (
  int argc,
  char *argv[ ]
  )
{
  int stack[ STACKSZ ];
  int *sp = stack;
  int d;

  while ( scanf ( "%d", &d ) == 1 )
  {
    if ( d )
    {
      *( sp++ ) = d;
    }
    else
    {
      printf ( "%d\n", *( --sp ) );
    }
  }

  return ( 0 );
}

Measured memory_bytes: 0
S = input()
S1 = int(S[0:2])
S2 = int(S[2:4])

MM = [1,2,3,4,5,6,7,8,9,10,11,12]

if S1 in MM and S2 in MM:
    print("AMBIGUOUS")
if S1 in MM and S2 not in MM:
    print("MMYY")
if S1 not in MM and S2 in MM:
    print("YYMM")
if S1 not in MM and S2 not in MM:
    print("NA")

Measured memory_bytes: 3064
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Stray Twins
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int[][] move = {{-1,0},{0,1},{1,0},{0,-1}};
		while(true){
			int w = sc.nextInt();
			int h = sc.nextInt();
			if((w|h)==0)break;
			int sj = sc.nextInt()-1;
			int si = sc.nextInt()-1;
			int tj = sc.nextInt()-1;
			int ti = sc.nextInt()-1;
			int[][] m = new int[h][w];
			for(int i=0;i<h;i++)for(int j=0;j<w;j++)m[i][j]=sc.nextInt();
			boolean[][] u = new boolean[w*h][w*h];
			u[si*w+sj][ti*w+tj] = true;
			List<int[]> l = new ArrayList<int[]>();
			l.add(new int[]{si*w+sj, ti*w+tj});
			int step = 0;
			boolean f = false;
			while(step<=99&&!l.isEmpty()&&!f){
				List<int[]> next = new ArrayList<int[]>();
				for(int[] v:l){
					si = v[0]/w;
					sj = v[0]%w;
					ti = v[1]/w;
					tj = v[1]%w;
					if(si==ti&&sj==tj){
						f = true;
						next.clear();
						break;
					}
					for(int k=0;k<4;k++){
						int nsi = si+move[k][0];
						int nsj = sj+move[k][1];
						int nti = ti+move[(k+2)%4][0];
						int ntj = tj+move[(k+2)%4][1];
						if(!(0<=nsi&&nsi<h&&0<=nsj&&nsj<w&&m[nsi][nsj]==0)){
							nsi = si;
							nsj = sj;
						}
						if(!(0<=nti&&nti<h&&0<=ntj&&ntj<w&&m[nti][ntj]==0)){
							nti = ti;
							ntj = tj;
						}
						if(!u[nsi*w+nsj][nti*w+ntj]){
							u[nsi*w+nsj][nti*w+ntj] = true;
							next.add(new int[]{nsi*w+nsj, nti*w+ntj});
						}
					}
				}
				step++;
				l = next;
			}
			System.out.println(f?step-1:"NA");
		}
	}
}

Measured memory_bytes: 22000
n = int(input())
f = [int(input().replace(' ', ''), 2) for i in range(n)]
p = []
for i in range(n):
    p.append([int(v) for v in input().split()])

ans = -10000000000
for store in range(1, 1024):
    p_sum = 0
    for i, v in enumerate(f):
        c = v & store
        p_sum += p[i][bin(c).count('1')]
    ans = max(ans, p_sum)

print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define badi_val 1000000007
int main(){
	int n;
 	string s;
  	cin >> n;
 	cin >> s;
  	int ans = 0;
  	int crt = 0;
  	for(int i = 0 ; i < s.size() ; i++){
    	if(s[i] == 'I')
          crt++;
      	else
          crt--;
      	ans = max(ans,crt);
    }
  	cout << ans << endl;
 	return 0; 
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<climits>
using namespace std;
vector<int>a;
vector<int>memo;

int dp(int curr)
{
    if(curr >= (int)a.size()-1)
    {
        return 0;
    }
    if(memo[curr]!=-1)
    {
        return memo[curr];
    }
    int ans = INT_MAX;
    ans = min(ans,abs(a[curr]-a[curr+1])+dp(curr+1));
    if(curr+2<(int)a.size())
    {
         ans = min(ans,abs(a[curr]-a[curr+2])+dp(curr+2));
    }
    if(ans ==INT_MAX)
    {
        ans = 0;
    }
    return memo[curr] = ans;
}


int main()
{

    int n;
    cin>>n;

    a.resize(n);
    memo.resize(n+1,-1);
    for(int i = 0;i<n;i++)
    {
        cin>>a[i];
    }


    cout<<dp(0);

}


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

using namespace std;
using ll = long long;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ll a, b, c;
  cin >> a >> b >> c;
  for(int i = 0; i < 10; ++i) {
    cout << a * c - b << '\n';
    c = a * c - b;
  }
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
#include<string>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define rep(i,n) for(int i = 0;i<((int)(n));i++)
#define reg(i,a,b) for(int i = ((int)(a));i<=((int)(b));i++)
#define irep(i,n) for(int i = ((int)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(int i = ((int)(b)-1);i>=((int)(a));i--)
typedef long long int lli;
typedef pair<int, int> mp;
#define fir first
#define sec second
#define IINF INT_MAX
#define LINF LLONG_MAX
#define eprintf(...) fprintf(stderr,__VA_ARGS__)
#define pque(type) priority_queue<type,vector<type>,greater<type> >
#define memst(a,b) memset(a,b,sizeof(a))

int main(void){
	lli n, m;
	cin >> n >> m;

	if(n*2 >= m) cout << m/2 << endl;
	else cout << n + (m-n*2)/4 << endl;
	return 0;
}

Measured memory_bytes: 256
#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字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const ll mod = 1e9+7;

void chmod(ll &M){
    if(M >= mod) M %= mod;
    else if(M < 0){
        M += (abs(M)/mod + 1)*mod;
        M %= mod;
    }
}

const ll inf = 1LL<<60;

ll N, M, p;

// void shortest_path(int s){
//     for(int i=0; i<n; ++i) d[i] = inf;
//     d[s] = 0;

//     int cnt = 0;
//     while(cnt <= m){
//         ++cnt;
//         bool update = false;
//         for(int i=0; i<m; ++i){
//             Edge e = edge[i];
//             if(d[e.from] != inf && d[e.to] > d[e.from]+e.cost){
//                 d[e.to] = d[e.from] + e.cost;
//                 update = true;
//             }
//         }
//         if(!update) break;
//     }
    
// }

// bool find_negative_loop(){
//     for(int i=0; i<n; ++i) d[i] = 0;

//     for(int i=0; i<n; ++i){
//         for(int j=0; j<m; ++j){
//             Edge e = edge[j];
//             if(d[e.to] > d[e.from] + e.cost){
//                 d[e.to] = d[e.from] + e.cost;

//                 if(i == n-1) return true;
//             }
//         }
//     }

//     return false;
// }

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

    int n, m; cin >> n >> m;
    vector<pair<int, int>> ab(n);
    for(int i=0; i<n; ++i) cin >> ab[i].first >> ab[i].second;
    sort(ab.begin(), ab.end());

    priority_queue<int> qu;
    int cur = 0;
    int ans = 0;
    for(int i=m-1; i>=0; --i){
        while(cur<n){
            pair<int, int> p = ab[cur];
            if(i+p.first <= m){
                qu.push(p.second);
                ++cur;
            }
            else break;
        }
        if(!qu.empty()){
            ans += qu.top();
            qu.pop();
        }
    }

    cout << ans << endl;

	return 0;
}


Measured memory_bytes: 1660
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
int main(){
  ll n;
  cin>>n;
  vll a(n+1);
  for(int i=1;i<n+1;i++){
    cin>>a[i];
  }
  vll b(n+1);
  for(int i=n;i>0;i--){
    if(a[i]==1) b[i]=1;
    int y=0;
    int t=2;
    while(i*t<=n){
      y+=b[i*t];
      t++;
    }
    if(a[i]==0){
      if(y%2==0){
        b[i]=0;
      }
      else{
        b[i]=1;
      }
    }
    else{
      if(y%2==0){
        b[i]=1;
      }
      else{
        b[i]=0;
        
      }
    }
  }
  ll ans=0;
  for(int i=1;i<n+1;i++){
    if(b[i]) ans++;
  }
  COUT(ans);
  for(int i=1;i<=n;i++){
    if(b[i]) cout<<i<<" ";
  }

}
         


Measured memory_bytes: 3968
in_d = input()
n = int(in_d)

a = [int(i) for i in input().split()]

result = 0
if 0 in a:
    print(0)
else:
    result = 1
    limit = 10 ** 18
    over = 0
    a.sort()
    for v in a:
        result *= v
        if result > limit:
            over = 1
            break
    if over == 1:
        print(-1)
    else:
        print(result)

Measured memory_bytes: 21784
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <fstream>
#include <chrono>
#include <random>
#include <bitset>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) ((int)(x).size())
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;
ll gcd(ll a, ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) {return a/gcd(a,b)*b;}

int main(){
  int N,M; cin >> N >> M;
  vector<int> A(N); rep(i,N) cin >> A[i];
  int cnt = 0;
  int sum = 0;
  rep(i,N) sum += A[i];
  rep(i,N){
    if(A[i]*4*M>=sum) cnt++;
  }
  if(cnt>=M) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args)  {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		String[][] snake = new String[H][W];
		char a = 'A';
		for(int i = 0; i < H; i++) {
			for(int j = 0; j < W; j++) {
				snake[i][j] = sc.next();
				if(snake[i][j].equals("snuke")) {
					a += j;
					i++;
					System.out.println(a + "" + i );
					return;
				}
			}
		}
	}
}

Measured memory_bytes: 21844
N=int(input())
S=input()



ans=0

for i in range(1,N):
    X=S[:i]
    Y=S[i:]
    setX=set(X)
    setY=set(Y)
    intersectionXY=setX & setY
    _temp=len(intersectionXY)
    if _temp>ans:
        ans=_temp
    else:
        pass
print(ans)

Measured memory_bytes: 9056
fun main() {
    var count = 0
    nextInt()
    nextIntList().forEach {
        var num = it
        while (num % 2 == 0) {
            num /= 2
            count++
        }
    }
    println(count)
}

// # Utils
// ## Input
fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = next().split(" ").map(String::toInt)
fun nextLongList() = next().split(" ").map(String::toLong)
fun nextDoubleList() = next().split(" ").map(String::toDouble)

// ## Array
inline fun <reified T> sizedArray(size: Int, default: T) = Array(size) { default }
inline fun <reified T> sized2DArray(row: Int, column: Int, default: T) = Array(row) { Array(column) { default } }

// ## mod^-1
//    [NOTE] CANNOT use this for 0, mod, 2mod, 3mod ...(return wrong value)
fun modinv(num: Long, mod: Long): Long {
    var a = num
    var b = mod
    var u = 1L
    var v = 0L
    while (b > 0) {
        val t = a.div(b)
        a -= t * b
        a = b.also { b = a } // swap a and b
        u -= t * v
        u = v.also { v = u } // swap u and v
    }
    u %= mod
    if (u < 0) u += mod
    return u
}

fun gcd(x: Int, y: Int): Int {
    fun innerGcd(x: Int, y: Int): Int {
        return if (x % y == 0) y else innerGcd(y, x % y)
    }
    return if (x >= y) innerGcd(x, y) else innerGcd(y, x)
}

fun gcd(x: Long, y: Long): Long {
    fun innerGcd(x: Long, y: Long): Long {
        return if (x % y == 0L) y else innerGcd(y, x % y)
    }
    return if (x >= y) innerGcd(x, y) else innerGcd(y, x)
}

// classes
class UnionFindTree(val size: Int) {
    private val r = sizedArray(size, -1)
    fun root(x: Int): Int {
        if (r[x] < 0) return x
        return root(r[x])
    }

    fun unite(x: Int, y: Int) {
        var rx = root(x)
        var ry = root(y)
        if (rx == ry) return
        if (r[rx] > r[ry]) {
            rx = ry.also { ry = rx }
        }
        r[rx] += r[ry]
        r[ry] = rx
    }

    fun size(x: Int) = -r[root(x)]

    override fun toString(): String {
        return r.joinToString(separator = ", ")
    }
}

Measured memory_bytes: 39892
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
//priority_queue<int, vector<int>, greater<int> > pq;
#define _CRT_SECURE_NO_DEPRECATE
const int N = 300030;
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
const ll mod =  1e9+7;

int main(){
 ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n;
cin>>n;
ll arr[n];
rep(i,0,n)
cin>>arr[i];
sort(arr,arr+n);
ll ar[n];
rep(i,0,n)
ar[i]=0;
ar[0]=arr[0];
rep(i,1,n)
{

	ar[i]+=arr[i]+ar[i-1];
}
ll cnt=0;

ll pre=0;
rep(i,0,n-1)
{
	if(2*ar[i]>=arr[i+1])
	cnt++;
	else
	cnt=0;
}
cout<<cnt+1;
}





Measured memory_bytes: 1792
use std::str::FromStr;

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

fn get_vec<T : FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    return s.trim().split_whitespace().map(|e| e.parse().ok().unwrap()).collect();
}

fn get_vec_by_lines<T : FromStr>(n : usize) -> Vec<T> {
    let mut v : Vec<T> = Vec::new();
    for _i in 0..n {
        let x : T = get_one();
        v.push(x);
    }
    return v;
}

fn main() {
    let v : Vec<String> = get_vec();
    let vv : Vec<i32> = get_vec();
    let s : String = get_one();
    println!("{} {}", if v[0] == s {vv[0]-1} else {vv[0]}, if v[1] == s {vv[1]-1} else {vv[1]});
}


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

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

    vector<long> c(n);
    long i;
    for(i=0; i<n; i++) {
        scanf("%ld", &c[i]);
    }

    map<long, long> zz;
    vector<ll> dp(n);
    for(i=0; i<n; i++) {
        dp[i] = (i>0? dp[i-1]: 1);
        auto it = zz.find( c[i] );
        if(it != zz.end()) {
            long prev = it->second;
            if(prev<i-1) {
                dp[i] = (dp[i] + dp[prev])%MOD;
            }
        }
        zz[c[i]] = i;
    }

    printf("%lld\n", dp[n-1]);

    return 0;
}


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

int main() {
    long N, A, B, C, D, E;
    cin >> N;
    cin >> A;
    cin >> B;
    cin >> C;
    cin >> D;
    cin >> E;
    long transport[5] = {A, B, C, D, E}, min = A;
    for (int i = 1; i < 5; i++) {
        if (transport[i] < min) {
            min = transport[i];
        }
        else {}
    }
    cout << (N + min - 1) / min + 4 << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using Pair = pair<int, int>;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define INF 1000000007
#define SEP " "

int     main()
{
	string t;
	cin >> t;
	for (auto it = t.begin(); it != t.end(); it++)
	{
		if (*it == '?')
			*it = 'D';
	}
	cout << t << endl;
}


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

#define fill(a,val) memset(a, (val), sizeof a)
#define pb push_back
#define lli long long int
#define scantype int
#define endl "\n"
#define unique(x) x.erase(unique(x.begin(),x.end()), x.end())
#define sort_f(x)  sort(x.begin(),x.end());
#define sort_r(x)  sort(x.rbegin(),x.rend());

lli MOD  = 1000000007;
lli inf = 1e15;

void scan(scantype &x);
lli powermod(lli _a,lli _b,lli _m){lli _r=1;while(_b){if(_b%2==1)_r=(_r*_a)%_m;_b/=2;_a=(_a*_a)%_m;}return _r;}
lli string_to_number(string s){lli x=0; stringstream convert(s); convert>>x; return x;}
lli add(lli a,lli b){lli x = (a+b)%MOD; return x; }
lli mul(lli a,lli b){lli x = (a*b)%MOD; return x; }
lli sub(lli a,lli b){lli x = (a-b+MOD)%MOD; return x; }
lli divi(lli a,lli b){lli x = a;lli y = powermod(b,MOD-2,MOD);lli res = (x*y)%MOD;return res;}

#define N 200003



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    vector<lli> arr;
    for(int i=0;i<n;i++)
    {
        lli temp;
        cin>>temp;
        arr.pb(temp);
    }
    sort_f(arr);
    unique(arr);
    cout<<(int)arr.size();
    
    return 0;
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
const int M=(1<<18)+5;
int a[N],b[N],n,m,v;
int pl[19][N],pr[19][N];
int fl[M],fr[M];
int main(){
	scanf("%d%d",&n,&v);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=0;i<=18;i++){
		pl[i][1]=pl[i][0]=1;
		pr[i][n]=pr[i][n+1]=n;
		for (int j=2;j<=n;j++)
			pl[i][j]=(a[j]-a[j-1]<=v?pl[i][j-1]:j);
		for (int j=n-1;j;j--)
			pr[i][j]=(a[j+1]-a[j]<=v?pr[i][j+1]:j);
		if (!v){
			m=i; break;
		}
		v>>=1;
	}
	for (int i=0;i<1<<m;i++)
		fl[i]=0,fr[i]=n+1;
	for (int i=0;i<1<<m;i++)
		for (int j=1;j<=m;j++)
			if (!((i>>(j-1))&1)){
				int I=i|(1<<(j-1));
				fl[I]=max(fl[I],pr[j][fl[i]+1]);
				fr[I]=min(fr[I],pl[j][fr[i]-1]);
			}
	for (int i=0;i<1<<m;i++)
		if (pr[0][fl[i]+1]>=fr[((1<<m)-1)^i]-1)
			b[pr[0][fl[i]+1]]=1;
	for (int i=1;i<=n;i++)
		if (b[pr[0][i]])
			puts("Possible");
		else
			puts("Impossible");
}

Measured memory_bytes: 35712
import java.util.*;
import java.io.*;

public class Main {


	public static void main(String[] args) {
		Main ans = new Main();
		System.out.println(ans.solve());
	}

	private long solve() {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		long MOD = (long) (1e9+7);
		int [] array  = new int[N+1];
		for(int i=1;i<=N;i++){
			array[i] = sc.nextInt();
		}

		long [][] dp = new long[N+2][K+2];
		for(int i=0;i<=K;i++) {
			dp[1][i] = ((i<=array[1]) ? 1 : 0);
		}

		for(int i=2;i<=N;i++){
			for(int j=0;j<=K;j++) {
				if(j==0)
					dp[i][j] += dp[i-1][j]; 
				else {
					dp[i][j] = (MOD + dp[i-1][j] + dp[i][j-1] - (((j-1-array[i])>=0) ? dp[i-1][j-1-array[i]] : 0)) % MOD;
				}				
			}
		}
		return dp[N][K];
	}
}

Measured memory_bytes: 140056
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = (A); I < (B); ++I)
#define FORR(I,A,B) for(ll I = (B-1); I >= (A); --I)
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;else return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll a,b,c,d;
	cin >> a >> b >> c >> d;
	if(a>c){
		swap(a,c);
		swap(b,d);
	}
	if(b<=c){
		cout << 0 << endl;
	}else if(b>=d){
		cout << d-c << endl;
	}else{
		cout << b-c << endl;
	}
}

Measured memory_bytes: 256
/*COMPETITIVE PROGRAMMING C++ TEMPLATE */

#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>
#include <climits>
#include <iomanip>

#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << " = " << x << "\n"
#define MOD 1000000007

const long double PI = 3.141592653589793236L;

typedef long long int ll;
typedef long double ld;

using namespace std;

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

    vector<ll> a(n);

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

    ll max_ele = a[0];
    ll ans = 0;

    for(int i = 1; i < n; i++) 
    {
        if(a[i] < max_ele)
        {
            ans += max_ele - a[i];
            a[i] = max_ele;
        }
        else {
            max_ele = a[i];
        }
    }

    cout << ans << "\n";
    
}

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

    int T = 1;
    //cin >> T;
    
    while (T--)
    {
        solve();
    }
    
    return 0;
}




Measured memory_bytes: 4780
#include <stdio.h>

int main(void)
{
	int n;
	
	while (scanf("%d", &n) != EOF){
		while (n > 39){
			n -= 39;
		}
		printf("3C");
		if (n < 10){
			printf("0");
		}
		printf("%d\n", n);
	}
	
	return (0);
}

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


int main(){

int N,i=0;
cin >> N ;
while(i*1000<N){
i++;
}

cout << (i*1000 )-N<< endl;

  
}

Measured memory_bytes: 3624
#include <iostream>
#include <ccomplex>
#include <vector>
#include <cassert>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>
#include <time.h>
#include <stack>
#include <locale>
#include <clocale>
#include <ctype.h>
#include <wchar.h>
#include <random>
#include <vector>
#include <unordered_map>
#include <bitset>

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL mod = 1000000007;

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

  LL a, b, c;
  cin >> a >> b >> c;
  if(a<b&&b<c){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}



Measured memory_bytes: 3148
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define pii 3.14
#define mod (ll)(1e9 + 7)
#define inf (ll)(1e18)
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
#define pi pair<int,int>
#define N (ll)(2e5+5)

void solve()
{
    string s;
    cin>>s;

    if(s == "ABC")
        cout<<"ARC\n";
    else
        cout<<"ABC\n";
}

int main()
{
    fio;
    ll tc = 1;
    //cin>>tc;
    while(tc--)
    {
        solve();
    }
}


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

int main(){
  int a;
  int b;
  string s;
  string t;
  string u;
  cin >> s >> t;
  cin >> a >> b;
  cin >> u;
  
  if(s==u){
      cout<<a-1 <<' '<<b;
  }
  else{
      cout<<a <<' '<<b-1;
  }
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main{
	private static final Scanner scan = new Scanner(System.in);

	public static void main(String[] args){
		int x = scan.nextInt();
		int y = scan.nextInt();

		System.out.printf("%d\n", gcd(x, y));
	}

	public static int gcd(int x, int y){
		if(x < y){
			int work = y;
			y = x;
			x = work;
		}
		while(y > 0){
			int r = x % y;
			x = y;
			y = r;
		}
		return x;
	}
}

Measured memory_bytes: 26332
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

const int MOD = 1e9 + 7;

int madd(ll a, ll b){
	a += b;
	if (a >= MOD) a -= MOD;
	return a;
}

vvll mat_mul(const vvll& A, const vvll& B){
	int n = isize(A);
	vvll C = vvll(n, vll(n, 0));
	rep(i, n)rep(j, n)rep(k, n){
		C[i][k] = (C[i][k] + A[i][j] * B[j][k]) % MOD;
	}
	return C;
}

vvll mat_exp(vvll M, ll k){
	int n = isize(M);
	vvll ans = vvll(n, vll(n, 0));
	rep(i, n) ans[i][i] = 1;
	while(k){
		if (k % 2) ans = mat_mul(ans, M);
		k /= 2;
		M = mat_mul(M, M);
	}
	return ans;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	int n; cin >> n;
	ll k; cin >> k;
	vvll A = vvll(n, vll(n, 0));
	rep(i, n){
		rep(j, n){
			int x; cin >> x;
			if (x) A[i][j] = 1;
		}
	}
	ll ans = 0;
	vvll M = mat_exp(A, k);
	rep(i, n){
		rep(j, n){
			ans = madd(ans, M[i][j]);
		}
	}
	cout << ans;
}	

Measured memory_bytes: 3740
#include <stdio.h>
#include <stdlib.h>

#define BUFF 16
#define SEP 3
void check_date(int *time);

int main (void){
  char str[BUFF] = {'\0'};
  char moji[BUFF] = {'\0'};
  int time[SEP]={0};
  int i=0,j=0,idx=0;


  if ( scanf("%s",str) == 1){
    while( i< BUFF){
      if ( (str[i] == '/' || str[i] == '\0') && idx < SEP){	
    	time[idx] = atoi(moji);
    	idx++;
    	for(j=0; j<BUFF; j++)  moji[j] = '\0';
    	j=0;
      }else{
    	moji[j] = str[i];
    	j++;
      }
      	i++;
    }
  }

  check_date(time);
  

  return 0;
}

    
void check_date(int *time){
  if ( time[0] > 2019 ||
      time[0] == 2019 && time[1] > 4){
    printf("TBD\n");
  }else if ( time[1] <= 4 || time[2] <= 30) printf("Heisei\n");

  return ;
}



Measured memory_bytes: 128
// https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_b
//
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

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

#[allow(unused_macros)]
macro_rules! dvec {
    ($t:expr ; $len:expr) => {
        vec![$t; $len]
    };

    ($t:expr ; $len:expr, $($rest:expr),*) => {
        vec![dvec!($t; $($rest),*); $len]
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    input! {
        s: chars
    };
    let win = (15-s.len()) + s.into_iter().filter(|&c| c == 'o').collect::<Vec<_>>().len();

    if win >= 8 {
        println!("YES");
    } else {
        println!("NO");
    }
}


Measured memory_bytes: 4352
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

int main()
{
    int n;
    cin >> n;
    map<string,int> kei;
    string s;
    for(int i=0; i<n; i++) {
        cin >> s;
        kei.insert(std::make_pair(s,1));
    }
    cout << kei.size() << endl;
    return 0;
}

Measured memory_bytes: 19124
//Author Harsh AKA Codula
#include<iostream>
#include<vector>
#include<numeric>
using namespace std;

//def

#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define inp freopen("input.in","r",stdin);

//main class

class Solution
{
	public:
		void run()
		{
			ll t=1;//cin>>t;
			while(t--)
			{
				float d,t,s;
				cin>>d>>t>>s;
				if (d/s>t)
				{
					/* code */
					cout<<"No";
				}
				else
				{
					cout<<"Yes";
				}
				cout<<"\n";
			}
		}
};
int main()
{
	fast;
	//inp;
	Solution MAIN;
	MAIN.run();
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vint;
typedef vector<double> vdbl;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int> > vvint;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;
typedef priority_queue<int, vector<int>, greater<int> > spqint; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll> > spqll;     //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int> > bpqint;    //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll> > bpqll;        //大きい順に取り出し

#define REP(i, n) for (int(i) = 0; (i) < (int)(n); i++)
#define FOR(i, a, b) for (int(i) = a; (i) < (int)b; i++)
#define IREP(i, v) for (auto i = v.begin(); i != v.end(); i++)
#define MOD 1000000007
#define NIL -1
#define FI first
#define SE second
#define MP make_pair
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)

const int INF = 1e9;
const ll LINF = 1e18;
const double EPS = 1e-9;
const double PI = M_PI;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }     //最小公倍数

void yes()
{
    cout << "Yes" << endl;
}
void no()
{
    cout << "No" << endl;
}
//-----------------------------------------

//-----------------------------------------
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false); 
    int h, w  ;
    cin >> h >> w ;
    int n ;
    cin >> n ;
    vint cnt(n,0) ;
    REP(i,n){
        int a ;
        cin >> a ;
        cnt[i] = a ;
    }
    vvint ans(h,vint(w,0)) ;
    queue<int> que ;
    REP(i,n){
        REP(j,cnt[i]){
            que.push(i+1) ;
        }
    }
    REP(i,h){
        REP(j,w){
            ans[i][j] = que.front() ;
            que.pop() ;
        }
    }

    REP(i,h){
        if(i%2==0){
            REP(j,w){
                cout << ans[i][j] <<" " ;
            }
        }
        else{
            REP(j,w){
                cout << ans[i][w-1-j] <<" " ;
            }
        }
        cout <<endl; 
    }



    

    return 0;
}


Measured memory_bytes: 384
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

#define FOR(i, start, end) for(int i = (start); i < (end); ++i)
#define REP(i, n) FOR(i, 0, n)


struct Card {
    char suit;
    int value;
    Card(char s, int v) : suit(s), value(v) {}
};

bool operator==(const Card& lhs, const Card& rhs)
{
    return lhs.value == rhs.value && lhs.suit == rhs.suit;
}

bool card_less_value(const Card& lhs, const Card& rhs)
{
    return lhs.value < rhs.value;
}

vector<Card> read_array()
{
    int n;
    scanf("%d", &n);

    vector<Card> v;
    REP(i, n) {
        char suit;
        int value;
        scanf(" %c%d", &suit, &value);
        v.push_back(Card(suit, value));
    }

    return v;
}

void bubble(vector<Card>& v)
{
    for(int jmax = v.size()-1; jmax >= 1; --jmax) {
        for(int j = 1; j <= jmax; ++j) {
            if(card_less_value(v[j], v[j-1]))
                swap(v[j-1], v[j]);
        }
    }
}

void selection(vector<Card>& v)
{
    REP(i, v.size()) {
        int argmin = i;
        FOR(j, i+1, v.size()) {
            if(card_less_value(v[j], v[argmin]))
                argmin = j;
        }
        if(argmin != i)
            swap(v[argmin], v[i]);
    }
}

void print_array(const vector<Card>& v)
{
    REP(i, v.size()) {
        Card c = v[i];
        printf("%c%d%c", c.suit, c.value, i == v.size()-1 ? '\n' : ' ');
    }
}

int main()
{
    vector<Card> v = read_array();
    //print_array(v);

    vector<Card> bubble_v(v);
    vector<Card> selection_v(v);

    bubble(bubble_v);
    selection(selection_v);

    print_array(bubble_v);
    puts("Stable");
    print_array(selection_v);
    puts(bubble_v == selection_v ? "Stable" : "Not stable");

    return 0;
}

Measured memory_bytes: 2744
import java.util.*;
         
        public class Main {
         
        	public static void main(String[] args){
            		Scanner in = new Scanner(System.in);
            		
            		int numbers = in.nextInt();
            		ArrayList<Integer> array = new ArrayList<Integer>();
            		for (int x = 0; x < numbers; x++){
            			array.add(in.nextInt());
            		}
            		
            		int counter = 0;
            		for (int x = 0; x < array.size(); x++){
            			if (x + 1 == array.get(array.get(x)-1)){
            				counter++;
            			}
            		}
            		counter /= 2;
            		System.out.println(counter);
            		in.close();
            }
        }

Measured memory_bytes: 34724
n=gets.chomp.to_i
t,a=gets.chomp.split(" ").map(&:to_i)
#平均気温がAの時の最適標高x
x=(t-a)/0.006
#最適標高との差を配列に代入
h=gets.chomp.split(" ").map{|h| (h.to_i-x).abs}
#最適標高に最も近い地点を出力
for i in 0..(n-1) do
  if h[i]==h.min then
    puts i+1
  end
end

Measured memory_bytes: 1788
# AtCoder
H, W = map(int, input().split())
N = int(input())
a = list(map(int, input().split()))

ans = [[0]*W for i in range(H)]
cu = 0
for y in range(H):
    for x in range(W):
        ans[y][x] = cu + 1
        a[cu] -= 1
        if not a[cu]:
            cu += 1

for i in range(H):
    if i % 2 != 0:
        print(' '.join(map(str, sorted(ans[i], reverse=True))))
    else:
        print(' '.join(map(str, ans[i])))


Measured memory_bytes: 3572
//0033 Ball
#include<iostream>
using namespace std;

int main(void)
{
	int n;
	cin >> n;
	while(n--)
	{
		const int N =10;
		int a[10];
		int i;
		for(i = 0; i < N; i++)
			cin >> a[i];

		int left = 0, right = 0;
		int *pMin = NULL, *pMax = NULL;
		bool result = true;
		for(i = 0; i < N; i++)
		{
			pMin = &(left < right ? left : right);
			pMax = &(left < right ? right : left);

			if(*pMin > a[i])
			{
				result = false;
				break;
			}
			else if(*pMax < a[i])
				*pMax = a[i];
			else
				*pMin = a[i];
		}
		cout << (result ? "YES" : "NO") << endl;;
	}
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a;
  cin>>a;
  a=a%10;
  if(a==2||a==4||a==5||a==7||a==9){
    cout<<"hon"<<"\n";
    return(0);
  }
  if(a==3){
    cout<<"bon"<<"\n";
    return(0);
  }
  cout<<"pon"<<"\n";
  return(0);
}


Measured memory_bytes: 3636
// #include <boost/multiprecision/cpp_int.hpp>
// using boost::multiprecision::cpp_int;
#include <bits/stdc++.h>
using namespace std;
// ¯\_(ツ)_/¯
#define f first
#define s second
#define p push
#define mp make_pair
#define pb push_back
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define all(v) v.begin(), v.end()
#define sz(x) ((int)(x).size())
#define endl " \n"
#define newl cout<<"\n"
#define MAXN 100005
#define MOD 1000000007LL
#define EPS 1e-13
#define INFI 1000000000             // 10^9
#define INFLL 1000000000000000000ll //10^18
// ¯\_(ツ)_/¯
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define vll vector<long long>
#define vvll vector<vll>
//vector<vector<int>> v(10, vector<int>(20,500)); 2d vector initialization. of 10 rows and 20 columns, with value 500.
#define pll pair<long long, long long>

#define fast_io()                   \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL);                    \
  cout.tie(NULL);

ll tc, n, m, k;

int main()
{
    fast_io();
#ifndef ONLINE_JUDGE
    //freopen("../input.txt", "r", stdin);
    //freopen("../output.txt", "w", stdout);
#endif

    cin>>n;
    vector<ld> prob(n, 0);
    rep(i, 0, n) cin>>prob[i];
    vector<vector<ld>> dp(n+1, vector<ld>(n+1, 0));


    dp[0][0] = 1;

//    rep(i, 0, n) {
//        rep(j, 0, i+1) {
//            // dp[i][j] i - coins used, j heads
//            dp[i+1][j] += dp[i][j]*(1-prob[i]);
//            dp[i+1][j+1] += dp[i][j]*(prob[i]);
//
//            //cout<<"{"<<i<<" "<<j<<"} ";
//            //dp[i][j] = dp[i-1][j]*(1-prob[i-1]) + dp[i][j-1]*prob[i-1];
//            //debug(dp[i][j-1]*prob[i-1]);
//        }
//
//    }


    rep(i, 1, n+1) {
        rep(j, 0, n+1) {
            // dp[i][j] i - coins used, j heads
            dp[i][j] = dp[i-1][j]*(1-prob[i-1]);
            if(j>0) dp[i][j] += dp[i-1][j-1]*prob[i-1];
        }

    }
//
//    rep(i, 1, n)
//    rep(j, 1, n/2 + 2)
//        cout<<dp[i][j]<<endl[j== 1+(n/2)];


    ld ans = 0;
    rep(i, n/2+1, n+1) ans += dp[n][i];

    cout<<setprecision(10)<<ans;

    return 0;
}

/*
2
4
0 1 0 1
5
0 0 1 0 0
*/

Measured memory_bytes: 141056
#include<stdio.h>

int main() {

	char s[100];
	long long  k;
	int start = 1;
	int last = 1;
	int i = 0;
	int len;
	long long kousa;

	scanf("%s", s);
	scanf("%lld", &k);

	kousa = 0;
	while (s[i] != '\0') {

		if (s[i] == s[i + 1]) {
			kousa++;
			i++;
		}

		i++;
	}

	len = i;

	if (s[0] == s[i - 1]) {

		while (s[i - 1] == s[i - 2]) {
			last++;
			i--;
		}

		i = 0;
		while (s[i] == s[i + 1]) {
			start++;
			i++;
		}

		if (start % 2 == 1 && last % 2 == 1 && start != len) {
				printf("%lld", k*kousa+k-1);


		}
		else if (start % 2 == 1 && last % 2 == 1 && start == len) {
			printf("%lld", len*k / 2);
		}
		else {
				printf("%lld", k*kousa);

		}
	}

	else {
			printf("%lld", k*kousa);

	}

}
 





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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

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

using ll = long long;
using R = long double;
const R EPS = 1e-9L; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r) {return (r > EPS) - (r < -EPS);}
inline R sq(R x) {return sqrt(max(x, 0.0L));}

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

// Problem Specific Parameter:

struct Union_find {
	Union_find(int n) {par.resize(n), iota(_all(par), 0);}
	int find(int x) {return (par[x] == x) ? x : par[x] = find(par[x]);}
	void unite(int a, int b) {a = find(a), b = find(b); par[a] = b;}
	bool same(int a, int b) {return find(a) == find(b);}
	vector<int> par;
};

const int limit = 200010;
ll adj_cost[limit];

int main(void) {
	int n, q;
	cin >> n >> q;

	const ll inf = 1LL << 40;
	rep(i, n) adj_cost[i] = inf;

	using edge = tuple<ll, ll, ll>;
	vector<edge> graph;

	rep(loop, q) {
		ll a, b, c;
		cin >> a >> b >> c;
		chmin(adj_cost[a], c + 1);
		chmin(adj_cost[b], c + 2);
		graph.push_back(edge(c, a, b));
	}

	rep(i, 2 * n) chmin(adj_cost[i % n], adj_cost[(i + n - 1) % n] + 2LL);

	rep(i,n) graph.push_back(edge(adj_cost[i],i,(i+1)%n));

	sort(begin(graph),end(graph));

	ll ans = 0LL;
	Union_find uf(n);

	for(auto &e:graph){
		ll a,b,c;
		tie(c,a,b) = e;
		if(uf.same(a,b)) continue;
		ans += c;
		uf.unite(a,b);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 16108
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  int card[N];
  for(int i=0; i<N; i++){
  cin >> card[i];
  }
  
  sort(card, card+N);
  reverse(card, card+N);
  
   int sum = 0;
  
  for( int i = 0; i<N; i++){
    if(i%2 == 0){
    	sum += card[i];
    }
    else{
      	sum -= card[i];
    }
  }
  
  cout << sum << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ld long double
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; }
using P=pair<long long,long long>;
#define rep(i,n) for(long long i=0; i<(long long)n; i++)
#define FOR(i,a,b) for(long long i=a; i<b; i++)
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((long long)(x).size())
#define COUT(x) cout << x << endl
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ld long double
#define vint vector<int>
#define vvint vector<vector<int>>
#define vstr vector<string>
#define vp vector<pair<int,int>>
#define vb vector<bool>
#define SUM(x) accumulate(x.begin(),x.end(),0)
#define MAX(x) *max_element(x.begin(),x.end())
#define MIN(x) *min_element(x.begin(),x.end())
#define couty cout<<"Yes"<<endl
#define coutn cout<<"No"<<endl
#define coutY cout<<"YES"<<endl
#define coutN cout<<"NO"<<endl
#define yn(x) cout<<(x?"Yes":"No")<<endl
#define YN(x) cout<<(x?"YES":"NO")<<endl
long long gcd(long long a,long long b){return b?gcd(b,a%b):a;}
long long lcm(long long a, long long b){return a*b/gcd(a,b);}
const long long dx[4]={1,0,-1,0};
const long long dy[4]={0,1,0,-1};
const long long INF = 1e12;
const long long MOD = 1e9+7;

struct unionFind
{
  // par[i]：データiが属する木の親の番号。i == par[i]のとき、データiは木の根ノードである
  vector<int> par;
  // sizes[i]：根ノードiの木に含まれるデータの数。iが根ノードでない場合は無意味な値となる
  vector<int> sizes;

  unionFind(int n) : par(n), sizes(n, 1) {
    // 最初は全てのデータiがグループiに存在するものとして初期化
    rep(i,n) par[i] = i;
  }

  // データxが属する木の根を得る
  int find(int x) {
    if (x == par[x]) return x;
    return par[x] = find(par[x]);  // 根を張り替えながら再帰的に根ノードを探す
  }

  // 2つのデータx, yが属する木をマージする
  void unite(int x, int y) {
    // データの根ノードを得る
    x = find(x);
    y = find(y);

    // 既に同じ木に属しているならマージしない
    if (x == y) return;

    // xの木がyの木より大きくなるようにする
    if (sizes[x] < sizes[y]) swap(x, y);

    // xがyの親になるように連結する
    par[y] = x;
    sizes[x] += sizes[y];
    // sizes[y] = 0;  // sizes[y]は無意味な値となるので0を入れておいてもよい
  }

  // 2つのデータx, yが属する木が同じならtrueを返す
  bool same(int x, int y) {
    return find(x) == find(y);
  }

  // データxが含まれる木の大きさを返す
  int size(int x) {
    return sizes[find(x)];
  }
};

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(15);

    int n,m; cin >> n >> m;
    vp e(m);
    rep(i,m){
        cin >> e[i].F >> e[i].S;
        e[i].F--; e[i].S--;
    }

    int res=0;
    rep(i,m){
        unionFind uf(n);
        rep(j,m){
            if(i==j) continue;
            uf.unite(e[j].F,e[j].S);
        }
        //cout<<uf.size(0)<<' ';
        if(uf.size(0)!=n) res++;
    }
    cout<<res<<endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <cstdio>
#include <string>
#include <cmath>
#include <queue>
#include <tuple>
//#include <bits/stdc++.h>
#define maxs(x,y) x = max(x,y)
#define mins(x,y) x = min(x,y)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i,i0,n) for(int (i)=(i0);(i)<(n);(i)++)
#define FORR(i,i0,n) for(int (i)=(n)-1; (i)>=(i0);(i)--)
#define SORT(x) sort(x.begin(),x.end())
#define rn return
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
typedef std::pair<int,int> P;
using namespace std;
using ll = long long;

const int mod = 1000000007;
struct mint{
    ll x;
    mint(ll x=0):x(x%mod){}
    mint& operator+=(const mint a){
        if ((x+= a.x) >= mod) x-= mod;
        return *this;
    }
    mint& operator-=(const mint a){
        if ((x+= mod - a.x) >= mod) x-= mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x*=a.x)%=mod;
        return *this;
    }
    mint operator+(const mint a) const{
        mint ans(*this);
        return ans+= a;
    }
    mint operator-(const mint a) const{
        mint ans(*this);
        return ans-= a;
    }
    mint operator*(const mint a) const{
        mint ans(*this);
        return ans*= a;
    }
};




int main(){
    int N; cin >> N;
    vector<P> ab;
    int a, b;
    rep(i,N){
        cin >> a >> b;
        ab.pb(mp(b,a));
    }
    SORT(ab);
    int dl = 0;
    int now = 0;
    rep(i,N){
        now += ab[i].second;
        dl = ab[i].first;
        if (now > dl){
            cout << "No";
            rn 0;
        }
    }
    cout << "Yes";
    rn 0;
}


Measured memory_bytes: 2420