akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define countof(array) (sizeof(array) / sizeof(array[0]))
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,n,s) for(int i = s; i < (n); ++i)
#define rsrep(i,n,s) for(int i = (n)-1; i >= s; --i)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define aall(a) (a), (a)+countof(a)//for array sorting
#define raall(a) (a), (a)+countof(a), greater<>()
#define show(x) cout<<#x<<" = "<<x<<endl;
#define vfind(v, a) find(all(v), a) != v.end()
#define yn(f) { if (f) puts("YES"); else puts("NO"); }
#define yns(f) { if (f) puts("Yes"); else puts("No"); }
#define show_ary(...) { cout<<#__VA_ARGS__<<" = "; for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define show_pair(...) cout<<#__VA_ARGS__<<" = "<<endl; for (const auto& x : (__VA_ARGS__)) { cout<<"  "<<x.fi<<" : "<<x.se<<endl; }
#define out_ary(...) { for (const auto& x : (__VA_ARGS__)) { cout<<x<<" "; } cout<<endl; }
#define argmax(v) distance((v).begin(), max_element(all(v)))
#define argmin(v) distance((v).begin(), min_element(all(v)))
#define vmax(v) *max_element(all(v))
#define vmin(v) *min_element(all(v))
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<P> vpair;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<string> vstr;
typedef vector<bool> vbool;
typedef vector<vint> vvint;
typedef vector<vll> vvll;
typedef vector<vstr> vvstr;
typedef vector<vbool> vvbool;
const ll LINF = 2000000000000000000ll;
const int INF = 1000000100;
const ll MOD = 1e9+7;

int main() {
    ll n, a, b;
    cin >> n >> a >> b;
    vll x(n);
    rep(i, n) cin >> x[i];
    vll d(n-1);
    rep(i, n-1) d[i] = x[i+1] - x[i];
    ll ans = 0;
    rep(i, n-1) {
        ans += min(d[i]*a, b);
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
using namespace std;
string s;
int main() {
    cin >> s;
    int l, t;
    for (int i=1; i <= s.size(); i++) {
        if (s[i-1] == 'A') {
            l = i;
            break;
        }
    }
    for (int i=s.size(); i >= 1; i--) {
        if (s[i-1] == 'Z') {
            t = i;
            break;
        }
    }
    cout << t-l+1 << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>
#include <stdlib.h>
#include <stdio.h>
#include <functional>
#include <cfloat>
#include <math.h>
#include <numeric>
#include <string.h>
#include <sys/time.h>
#include <random>


#define fs first
#define sc second

using namespace std;

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

ll gcd(ll a, ll b) {
    if(a < b) return gcd(b, a);
    ll r;
    while ((r=a%b)) {
        a = b;
        b = r;
    }
    return b;
}


int main(){
    ll n, m, a[101000];
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i] /= 2;
    }
    int xx = -1;
    for(int i = 0; i < n; i++){
        ll y = a[i], count = 0;
        while(y > 0){
            if(y % 2 == 1){
                break;
            }
            y /= 2;
            count++;
        }
        if(xx == -1){
            xx = count;
        }
        else{
            if(xx != count){
                cout << 0 << endl;
                return 0;
            }
        }
    }

    ll hist = a[0];
    for(int i = 1; i < n; i++){
        ll x = hist * a[i] / gcd(hist, a[i]);
        hist = x;
        if(hist > m){
            cout << 0 << endl;
            return 0;
        }
    }

    cout << (m - hist) / (2 * hist) + 1 << endl;



    return 0;
}


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

int main()
{
	int h, w;
	cin >> h >> w;

	vector<bool> wc(w, false);
	vector<string> m;
	for (int i = 0; i < h; ++i){
		string s;
		cin >> s;
		bool isContinue = true;
		for (int j = 0; j < w; ++j) {
			if (s[j] == '#') {
				wc[j] = true;
				isContinue = false;
			}
		}
		if (isContinue) {
			continue;
		}
		m.push_back(s);
	}

	for (auto& i : m) {
		for (int j = 0; j < w; ++j) {
			if (wc[j]) {
				cout << i[j];
			}
		}
		cout << endl;
	}


	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll read() {
    ll x=0,f=1; char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())
        if(ch=='-')f=-f;
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=x*10+ch-'0';
    return x*f;
}
inline void chkmin( int &a,int b ) { if(a>b) a=b; }
inline void chkmax( int &a,int b ) { if(a<b) a=b; }
#define _ read()
#define ln endl
const int N = 5005;
int n, len;
unsigned long long hsh[N], base[N];
char s[N];
inline unsigned int gethash ( int l, int r, int len ) {
	return hsh[r] - hsh[l-1] * base[len];
}
int main() {
	n = _ ;
	scanf("%s", s + 1 );
	base[0] = 1;
	for( int i = 1; i <= n; i++ )
		hsh[i] = hsh[i-1] * 233 + s[i] - 'a', base[i] = base[i-1] * 233;
	// cout << gethash(3, 7, 5) << " " << gethash(9,13,5) << ln;
	len = 0;
	for( int i = 1; i <= n; i++ ) 
		for( int j = i + 1; j <= n; j++ ) 
			while(i + len < j && j + len <= n && gethash(i, i+len, len+1) == gethash(j, j+len, len+1))
				++len;
	cout << len << ln; 
}


Measured memory_bytes: 384
n=int(input())
v=[0]*100
ans=0
for i in range(1,n+1):
    x=int(str(i)[0])
    y=int(str(i)[-1])
    v[x*10+y]+=1

for i in range(len(v)):
    x=int(str(i)[0])
    y=int(str(i)[-1])
    ans+=v[i]*v[10*y+x]
print(ans)

Measured memory_bytes: 40812
#pragma region def
//#define _GLIBCXX_DEBUG
#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()

using llint = long long;
using vint = vector<int>;
using vvint = vector<vector <int>>;
using pint = pair<int, int>;
const int INF = 1e9;
const long long llINF = 1e18;
#pragma endregion

int main () {
    int n; cin >> n;
    vint a(n);
    rep(i, n) cin >> a[i];
    int ans = 0, gu = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] % 2 == 0) {
            gu++;
            if (a[i] % 3 == 0 || a[i] % 5 == 0) {
                ans++;
            } else {
                break;
            }
        }
    }

    if(ans == gu) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i < 10; i++)
    {
        for (int j = 1; j < 10; j++)
        {
            if (i*j == n)
            {
                cout << "Yes" << endl;
                return 0;
            }
            
        }
        
    }
    cout << "No" << endl;
}
    

Measured memory_bytes: 3580
import java.io.BufferedReader;
//import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		//System.setIn(new FileInputStream("./ALDS1_4_D-in35.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int[] t = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		int n = t[0];
		int k = t[1]; // max no of dump truck
		int[] w = new int[n];
		int left = 0;
		int right = 0;
		for(int i = 0; i < n; ++i) {
			w[i] = Integer.parseInt(br.readLine());
			right += w[i];
			if(left < w[i]){
				left = w[i];
			}
		}
		int mid = 0;
		while(left < right) {
			mid = (left + right)/2;
			int l = 1;// number of dump truck
			int s = mid;
			for(int i = 0; i < n && l <= k; ++i) {
				s -= w[i];
				if(s < 0){
					l += 1;
					s = mid - w[i];
				}
			}
			if(l <= k){
				right = mid;
			}else{
				left = mid + 1;
			}
		}
		System.out.println(right);

	}

}

Measured memory_bytes: 39144
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    a, b, c, k = LI()
    num = 0
    if k < a:
        num = k
        print(num)
        return

    k -= a
    num += a
    if k < b:
        print(num)
        return
    k -= b

    if k < c:
        num -= k
        print(num)
        return
    k -= c
    num -= c
    print(num)
main()



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

int debug = 0;

int main(){
    ll x;
    cin >> x;
    vector<ll> table(200);
    for(ll i=0;i<200;++i){
        table[i]=i*i*i*i*i;
    }

    bool found=false;
    ll a=0,b=0;

    bool minus=false;
    if(x<0){ x=-x; minus=true;}
    
    for(int i=0;i<200;++i){
        for(int j=0;j<200;++j){
            if((table[i]+table[j]) ==x){
                a=i;b=-j;found=true;
            }
            if((table[i]-table[j])==x){
                a=i;b=j;found=true;
            }
            if(found)break;
        }
        if(found)break;
    }

    if(minus){
        a*=-1;
        b*=-1;
    }

    cout << a << " " << b <<endl;

    return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#define rep(i,n); for(int i = 0;i < (n);i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef tuple<int,int,int> state;
long double pi = acos(-1);
const int INF = 1001001001;


// 最小公倍数を求める
int euqlid (int a, int b){
  int temp;
  temp = a % b;
  if(temp == 0)return b;
  return euqlid(b,temp);
}
ll conbination(ll a,ll b){
  ll u = 1;
  ll d = 1;
  while(b != 0){
    u *= a;
    d *= b;
    a--;
    b--;
  }
  return u / d;
}
int strtoint(char s){
  return (int(s-'0'));
}
char changeS(char alpha){
  if(0x41 <= alpha and alpha <= 0x5A)return (alpha + 0x20);
  else if(0x61 <= alpha and alpha <= 0x7A)return (alpha - 0x20);
  return alpha;
}
int fact(int n){
  if(n == 1)return 1;
  return n * fact(n-1);
  }
int ceil(int a,int b){
  // a/bの切り上げを考える
  return (a+b-1)/b;
}

int main() {
  int ans;
  rep(i,5){
    int x;
    cin >> x;
    if(x == 0)ans = i+1;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3592
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::*;
#[allow(dead_code)]
fn getline() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    return ret;
}
fn get_word() -> String {
    let mut stdin = std::io::stdin();
    let mut u8b: [u8; 1] = [0];
    loop {
        let mut buf: Vec<u8> = Vec::with_capacity(16);
        loop {
            let res = stdin.read(&mut u8b);
            if res.is_err() || res.ok().unwrap() == 0 || u8b[0] <= ' ' as u8 {
                break;
            } else {
                buf.push(u8b[0]);
            }
        }
        if buf.len() >= 1 {
            let ret = std::string::String::from_utf8(buf).unwrap();
            return ret;
        }
    }
}
fn parse<T: std::str::FromStr>(s: &str) -> T { s.parse::<T>().ok().unwrap() }

#[allow(dead_code)]
fn get<T: std::str::FromStr>() -> T { parse(&get_word()) }

fn main() {
    let n:usize = get();
let mut a: Vec<i32> = (0 .. 2 * n).map(|_| get()).collect();
a.sort();
let mut sum = 0;
for i in 0 .. n { sum += a[2 * i]; }
println!("{}", sum);
}

Measured memory_bytes: 380
#include<stdio.h>
int main(){
    unsigned long long a,b,x,i=0,sum;
    scanf("%llu",&a);
    scanf("%llu",&b);
    scanf("%llu",&x);

    if(a%x == 0){
        i=1;
    }
   
    sum=i+(b/x)-(a/x);

    printf("%llu\n",sum);

    return 0;
    
} 

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

array<array<long,1000>,8> value;

int main(void){
    long n, m;
    cin >> n >> m;
    for(long i=0; i<n; i++){
        long x, y, z;
        cin >> x >> y >> z;
        value[0][i] = + x + y + z;
        value[1][i] = + x + y - z;
        value[2][i] = + x - y + z;
        value[3][i] = + x - y - z;
        value[4][i] = - x + y + z;
        value[5][i] = - x + y - z;
        value[6][i] = - x - y + z;
        value[7][i] = - x - y - z;
    }
    long v_max=0;
    for(long i=0; i<8; i++){
        long sum = 0;
        sort(value[i].begin(), value[i].begin()+n, greater<long>());
        for(long j=0; j<m; j++){
            sum += value[i][j];
        }
        v_max = max(sum, v_max);
    }
    cout << v_max << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <climits>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <deque>
#define INF_INT (INT_MAX / 2)
#define INF_LONG (LONG_MAX / 2)
//#define DEBUG true
#define DEBUG false
using namespace std;

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

int ceil(int x, int y){
  return (x % y == 0) ? x / y : x / y + 1;
}

int gcd(int x, int y){
  return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y){
  return x / gcd(x, y) * y;
}

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

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

  int count = 0;
  for(int i = 0; i < n; i++){
    int j = a[i];
    if(a[j] == i) ++count;
  }
  count /= 2;

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int N, M, R;
int D[201][201];
int r[8];
int kotae;
int ima;
bool v[8];
void sagasu(int n, int prev) {
	if (n == R) kotae = min(kotae, ima);
	else {
		rep(i, R) {
			if (!v[i]) {
				v[i] = 1;
				if (prev >= 0) ima += D[r[prev]][r[i]];
				sagasu(n + 1, i);
				if (prev >= 0) ima -= D[r[prev]][r[i]];
				v[i] = 0;
			}
		}
	}
}

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


	cin >> N >> M >> R;
	rep(i, R) cin >> r[i];

	rep1(i, N) rep1(j, N) D[i][j] = 1e9;
	rep(i, M) {
		int a, b, c;
		cin >> a >> b >> c;
		D[a][b] = c;
		D[b][a] = c;
	}
	rep1(k, N) rep1(i, N) rep1(j, N) {
		D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
	}

	kotae = 1e9;
	sagasu(0, -1);

	co(kotae);

	Would you please return 0;
}

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

#define pb push_back
#define fr first
#define sc second
typedef pair<int,int> pii;
typedef vector<int> vi;
const int INF = (1<<25);
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int main(){
  int a[4],b[4];
  int asum=0,bsum=0;
  for(int i=0;i<4;i++){
    cin>> a[i];
    asum+=a[i];
  }

  for(int i=0;i<4;i++){
    cin>> b[i];
    bsum+=b[i];
  }

  if(asum>bsum) cout<< asum<< endl;
  else cout<< bsum<< endl;
}

Measured memory_bytes: 1160
#include<stdio.h>
int main()
{
  int n;
  scanf("%d",&n);
  int arr[n+1];
  for(int i=1;i<=n;i++)
  {
    scanf("%d",&arr[i]);
  }
  int count =0;
  for(int i=1;i<=n;i++)
  {
    if(arr[i]%2!=0&&i%2!=0)
    {
      count++;
    }
  }
  printf("%d",count);
  return 0;
}

Measured memory_bytes: 3256
N = int(input())
A1 = list(map(int, input().split()))
A2 = list(map(int, input().split()))
ans1 = []
ans2 = []

for x in range(N):
    if x == 0:
        ans1.append(A1[x])
        ans2.append(A1[x] + A2[x])
    else:
        ans1.append(ans1[x - 1] + A1[x])
        ans2.append(max(ans1[x], ans2[x - 1]) + A2[x])
print(ans2[N - 1])


Measured memory_bytes: 3064
package main

import "fmt"

func main() {
	var x, y int
	fmt.Scan(&x, &y)

	ans := 0
	switch x {
	case 1:
		ans += 300000
	case 2:
		ans += 200000
	case 3:
		ans += 100000
	}
	switch y {
	case 1:
		ans += 300000
	case 2:
		ans += 200000
	case 3:
		ans += 100000
	}
	if x == 1 && y == 1 {
		ans += 400000
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main(void){
    int a, b, ans;
    cin >> a >> b;
  
  	if (a >= 13) {
        ans = b;
    } else if (a <= 5) {
        ans = 0;
    } else {
        ans = b / 2;
    }
  
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
use std::io::*;
use std::str::FromStr;
   
fn read<T: FromStr>() -> T {
	let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}
     
fn main() {
    let s: String = read();
    let v = vec!["MON", "TUE", "WED", "THU", "FRI", "SAT", "SUN"];
	let index = v.iter().position(|&r| r == s).unwrap();
	if index ==  6 {
		println!("{}", 7);
	} else {
		println!("{}", 6 - index);
	}
}

Measured memory_bytes: 4352
#include<iostream>

int main(){
    int d,S;
    while(std::cin >> d){
        S = 0;
        for(int i = 1; i < 600 / d; ++i)
            S += (i*d) * (i*d) * d;
        std::cout << S << std::endl;
    }
    return 0;
}

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

using namespace std;
typedef long long ll;

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

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

  if (sum % (n * (n + 1) / 2)) {
    cout << "NO\n";
  } else {
    ll cnt = sum / (n * (n + 1) / 2), cnt2 = 0;
    vector<ll> b = a;
    for (int i = 0; i < n; i++) {
      b[i] = a[i] - a[(i - 1 + n) % n];
      cnt2 += abs(b[i] - cnt) / n;
    }
    cout << (cnt == cnt2 ? "YES" : "NO") << endl;
  }

  return 0;
}

Measured memory_bytes: 1792
#include <stdio.h>

int main(void)
{
	int n, m, l, i, j, k;
	int a[100][100] = { 0 }, b[100][100] = { 0 };
	long int c;

	scanf("%d %d %d", &n, &m, &l);

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

	for (i = 0; i < m; i++)
		for (j = 0; j < l; j++)
			scanf("%d", &b[i][j]);

	for (i = 0; i < n; i++)
		for (j = 0; j < l; j++) {
			c = 0;
			for (k = 0; k < m; k++) 
				c += a[i][k] * b[k][j];

			printf("%ld%s", c, j == l - 1 ? "\n" : " ");
		}


	return 0;
}

Measured memory_bytes: 688
n, k = list(map(int, input().split()))

arr = list(map(int, input().split()))

dp = [1] * (k+1)


for i in range(1, k+1):
    curr = 1
    for j in range(len(arr)):
        if arr[j] <= i:
            if dp[i-arr[j]] == 0:
                curr = 1
            else:
                curr = 0
                break
    
    dp[i] = curr

# print(dp)

if dp[-1] == 1:
    print("Second")
else:
    print("First")

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

int main() {
  int n;
  cin >> n;
  int d[n];
  for (int i=0; i<n; i++) cin >> d[i];
  sort(d, d+n);
  int ans = 1;
  for (int i=1; i<n; i++) {
    if (d[i] != d[i-1]) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(X) (X).begin(),(X).end()
#define rall(X) (X).rbegin(),(X).rend()
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define ff first
#define ss second
#define P 1000000007
#define in(x, a, b) (a <= x && x < b)

using namespace std;
using ll = long long;
typedef pair<int, int> ii;
typedef vector<ii> vii; 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
const ll inf = 1000000001, INF = (ll)1e18 + 1;

ll power(ll a, ll b) {
	ll result = 1;
	while(b) {
		if(b % 2) result = (result * a) % P;
		a = (a * a) % P;
		b /= 2;
	}
	
	return result;
}

ll divide(ll a, ll b) {
	return a * power(b, P - 2) % P;
}

void solve() {
	int s;
	cin >> s;
	
//	ll ans = 0;
//	for(int i = 1; i <= s; i++) {
//		int n = s - 3 * i;
//		if(n < 0) break;
//		
//		ll res = 1;
//		for(int j = 1; j <= n + i - 1; j++) res = (res * j) % P;
//		for(int j = 1; j <= n; j++) res = divide(res, j);
//		for(int j = 1; j <= i - 1; j++) res = divide(res, j);
//		
//		ans = (ans + res) % P;
//	}
	
	int ans = 0;
	
	vi dp(s + 1, 0);
	dp[0] = 1;
	for(int i = 0; i < s; i++) {
		vi ndp(s + 1, 0);
		int pre = 0;
		for(int j = 3; j <= s; j++) {
			(pre += dp[j - 3]) %= P;
			(ndp[j] += pre) %= P;
		}
		
		(ans += ndp[s]) %= P;
		
		dp = ndp;
	}
	
	cout << ans << endl;
}

int main() {
	ios_base::sync_with_stdio(false);
	solve();
    return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<deque>
#include<map>
#include<stack>
#include<bitset>
#include<list>
#include<cassert>
#include<numeric> 

using namespace std;

long long n, k;
long long power(long long a, long long b)
{
	if (b == 0)
	{
		return 1;
	}
	long long x = power(a, b / 2);
	x = x * x;
	if (b % 2 == 1)
	{
		x = x * a;
	}
	return x;
}

int main()
{
	cin >> k >> n;
	if (k == 1)
	{
		cout << n;
		exit(0);
	}
	long long m = n;
	long long ans = 1;
	for (long long i = 2; i * i <= n; i++)
	{
		if (m % i == 0)
		{
			long long cnt = 0;
			while (m % i == 0)
			{
				m = m / i;
				cnt++;
			}
			cnt = cnt / k;
			ans = ans * power(i, cnt);
		}
	}
	cout << ans << endl;

}


Measured memory_bytes: 256
import sys
pin=sys.stdin.readline

S=pin()[:-1]
Q=int(pin())
now=1
ans1=""
ans2=""
for i in range(Q):
  D=pin().split()
  T=0
  F=0
  C=""
  if len(D)==1:
    T=int(D[0])
  else:
    T=int(D[0])
    F=int(D[1])
    C=D[2]
  if T==1:
    now*=-1
  else:
    if F==1:
      if now==1:
        ans1=C+ans1
      else:
        ans2=ans2+C
    else:
      if now==1:
        ans2=ans2+C
      else:
        ans1=C+ans1
if now==1:
  print(ans1+S+ans2)
else:
  print(ans2[::-1]+S[::-1]+ans1[::-1])



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

using namespace std;

string s;

int main(){
	cin >> s;
	int zero = 0, one = 0;
	for(int i = 0; i < (int)s.size(); ++i){
		if(s[i] == '1') one++;
		else zero++;
	}
	int ans = 2 * min(zero, one);
	cout << ans << endl;
}

Measured memory_bytes: 512
//2020 4.18 Linear Search

#include <stdio.h>
#define MAX1 10000
#define MAX2 500

int main()
{
    int a,b,cnt=0;
    int i,j;
    int A[MAX1],B[MAX2];

    scanf("%d",&a);
    for(i=0;i<a;i++)
    {
        scanf("%d",&A[i]);
    }

    scanf("%d",&b);
    for(i=0;i<b;i++)
    {
        scanf("%d",&B[i]);
        for(j=0;j<a;j++)
        {
            if(A[j]==B[i]) {cnt++; break;}
        }
    }
    printf("%d\n",cnt);
}


Measured memory_bytes: 2124
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
sys.setrecursionlimit(10**7)

def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

def main():
    N = I()
    A = numpy.array(LI())
    A_mod2 = A[A%2==0]
    is_approved = ((A_mod2%3==0)|(A_mod2%5==0)).all(axis=0)
    print("APPROVED" if is_approved else "DENIED")

main()



Measured memory_bytes: 27348
#include <cstdio>

char c[210];
int n, mid;

int main(){
	
	scanf("%d %s", &n, c);
	if(n & 1){
		puts("No");
		return 0;
	}
	mid = n / 2;
	for(int i = 0; i < mid; i++)
		if(c[i] != c[mid + i]){
			puts("No");
			return 0;
		}
	
	puts("Yes");
	
	return 0;
}

Measured memory_bytes: 128
import java.util.*;
public class Main {
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        for(int i=0;i<s.length()-t.length()+1;i++){
            String p = s.substring(i,i+t.length());
            if(p.equals(t)) System.out.println(i);
        }
    }
}


Measured memory_bytes: 26400
// #include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <tuple>
#include <map>
#include <math.h>
#include <algorithm> // std::sort, std::min, std::next_permutation, std::lower_bound
#include <iomanip> // std::setprecision
#include <cmath> // std::ceil
#include <numeric> // std::gcd, std::lcm
#include <limits> // std::numeric_limits<long int>::max()
#include <unordered_map>
#include <map>
#include <cmath> // std::atan2
#include <deque>
#include <queue>

using namespace std;
typedef long long ll;
#define INF 1999999999
#define MODA 1000000007 
#define rep(i,n) for (long long i = 0; i < (n); ++i)

template<typename T>
T powint (const T& x, const T& y) {
  T ret = 1;
  for(T i=0; i<y; ++i) ret *= x;
  return ret;
}

int main() {
  ll A, B;
  cin >> A >> B;

  vector<ll> numflipsB;
  for (ll i=0; (B >> i) != 0; ++i) {
    ll digit = powint((ll)2, i);
    ll rest = (B+1) % (2 * digit);
    ll blink = (B+1) - rest;
    numflipsB.push_back(blink / 2);
    //cerr << blink <<" "<< rest <<" "<< digit << endl;
    if (rest > digit) numflipsB[i] += rest - digit;
  }

  A = A - 1;
  vector<ll> numflipsA;
  for (ll i=0; (B >> i) != 0; ++i) {
    if (A >> i == 0) {
      numflipsA.push_back(0);
      continue;
    }
    ll digit = powint((ll)2, i);
    ll rest = (A+1) % (2 * digit);
    ll blink = (A+1) - rest;
    numflipsA.push_back(blink / 2);
    //cerr << blink <<" "<< rest <<" "<< digit << endl;
    if (rest > digit) numflipsA[i] += rest - digit;
  }
  
  long long ans = 0;
  for (ll i = 0; i < numflipsB.size(); ++i) {
    cerr << numflipsB[i] <<" "<< numflipsA[i] << endl;
    if ((numflipsB[i] - numflipsA[i]) % 2 == 1) ans += (ll)1 << i;
  }
  cout << ans << endl; 
  return 0;
}


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

#define SWAP(a,b) ((a != b)? (a += b,b = a - b,a -= b) : 0 ) //数値のみ
#define SWAPs(type,a,b) { type temp = a; a = b; b = temp; } //型指定する ポインタ, 構造体等
#define rng(i, a, b) for(int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define pb push_back
#define eb emplace_back
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed

int main() {
  int ans = 0, maxi = 0, tsize;
  //map<string, int> m;
  string s, t;
  cin >> s >> t;
  //vector<ll> c(n), v(n);
  rep(i, s.size() - t.size() + 1) {
    ans = 0;
    rep(j, t.size()) if(s.at(i + j) == t.at(j)) ans++;
    maxi = max(maxi, ans);
  }
  cout << t.size() - maxi << endl;
}


Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys


def solve(S: str):
    N = len(S)
    m = N
    for i in range(N - 1):
        if S[i] != S[i + 1]:
            m = min(m, max(N - (i + 1), i + 1))
    print(m)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3316
#include <iostream>
using namespace std;
int main(void){
   int a,b,c,d,e;
   cin>>a>>b>>c;
   if(c<a){cout<<0<<endl;}else if(a+b-c>-1){cout<<c-a<<endl;}
   if(a+b-c<0){cout<<"NA"<<endl;}
}



Measured memory_bytes: 3096
n, W = map(int, input().split())
v, w = [], []
for _ in range(n):
    v_, w_ = map(int, input().split())
    v.append(v_)
    w.append(w_)

# dpi[j] := i番目以降のものでjのコストで実現できる最大の価値
dp = [0] * (W + 1)

for i in range(n):
    for j in range(W, w[i]-1, -1):
        #w[i]よりjが小さい時はそのコストを払えないので考えない
        #jを上から考えれば小さなjについてはまだ前のテーブルが残ってる
        dp[j] = max(dp[j], dp[j-w[i]] + v[i])

print(dp[W])


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

#define  __  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  int  long long
#define  endl  '\n'
const double pi = acos(-1);
const int mod = 1e9 + 7;
//______________________



int32_t main()
{ 
 
  
  string s, t;
  cin >> s >> t;
  int sc[26] = {0};
  vector<int> g[26];

  for(int i = 0; i < s.size(); i++)
  {
    sc[s[i] - 'a']++;
    g[s[i] - 'a'].push_back(i + 1);
  }
  

  for(char c : t)
    if(!sc[c - 'a'])
      return cout << -1, 0;

  
  int ans = 0, last = 0, cur;

  for(char c : t)
  {
     auto it = lower_bound(g[c - 'a'].begin(), g[c - 'a'].end(), last);
     if(it == g[c - 'a'].end())
     {
        ans += (int)s.size();
        last = g[c - 'a'].front() + 1;
     }
     else
     {
        last = *it + 1;
     }
  }
  
  ans += last - 1;

  cout << ans;


 return 0;
}

Measured memory_bytes: 1852
#include<bits/stdc++.h>
#define mod 1000000007
#define max 5005
//#define max1 60000000
#define inf INT_MAX
using namespace std;
typedef  long long int ll;
template<typename T> inline T maxi(T a,T b){return a>b?a:b;}
template<typename T> inline T mini(T a,T b){return a<b?a:b;}
template<typename T> inline T absl(T a){return a>0?a:-a;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
#define mp(a,b) make_pair(a,b)
//###################################################------------------------------------------------------#######################################

void input(){
    ll n,m;
    cin>>n>>m;
    vector<pair<ll,ll> >co(n);
    for(ll i =0;i<n;++i){
        cin>>co[i].first>>co[i].second;
    }
    sort(co.begin(),co.end());
    ll ans =0;
    for(auto it = co.begin();it!=co.end();++it){
        ans += it->first*((it->second<m)?it->second:m);
        m-=((it->second<m)?it->second:m);
    }
    cout<<ans<<endl;
}
int main(){
    input();
    return 0;
}


Measured memory_bytes: 1792
#include <iomanip>
#include <random>
#include <time.h>
#include <vector>
#include <queue>
#include <functional>
#include <map>
#include <string>
#include <cstdlib>
#include <typeinfo>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <list>
#include <stack>
#include <set>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
using namespace std;
int main() {
	long long int  n, m, r, R[10], a, b, c, dis[210][210], inf = 1e9;
	for (int i = 0; i < 210; i++) {
		for (int j = 0; j < 210; j++) {
			dis[i][j] = inf;
		}
		dis[i][i] = 0;
	}
	cin >> n >> m >> r;
	for (int i = 0; i < r; i++)cin >> R[i];
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		dis[a][b] = min(dis[a][b], c);
		dis[b][a] = dis[a][b];
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				dis[j][k] = min(dis[j][k], min(dis[j][a] + dis[b][k], dis[j][b] + dis[a][k]) + dis[a][b]);
			}
		}
	}
	sort(R, R + r);
	ll yan, ans = 1e9;
	do {
		yan = 0;
		for (int i = 0; i < r - 1; i++)yan += dis[R[i]][R[i + 1]];
		ans = min(yan, ans);
	} while (next_permutation(R, R + r));
	cout << ans << endl;
	return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    sort(a.rbegin(), a.rend());
    int aa = -1, b = -1;

    int cnt = 0;
    for (int i = 0; i < n-1; i++) {
        if (a[i] != a[i+1]) {
            cnt = 0;
            continue;
        }
        if (a[i] == a[i+1]) {
            if (aa == -1) {
                aa = a[i];
                i++;
            }
            else {
                b = a[i];
                break;
            }
        }
    }
    if (aa == -1 || b == -1) cout << 0 << endl;
    else cout << (Int)aa * b << endl;
}

Measured memory_bytes: 3736
#include "bits/stdc++.h"
#define _USE_MATH_DEFINES
#include <math.h>
 
using namespace std;
 
using LL = long long;
using VLL = std::vector<LL>;
using VVLL = std::vector<VLL>;
using VVVLL = std::vector<VVLL>;
using LD = long double;
using VLD = std::vector<LD>;
using VVLD = std::vector<VLD>;
using VVVLD = std::vector<VVLD>;
 
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; }

#define REP(i,n) for(LL (i)=0;(i)<(n);(i)++)
#define ALL(v) v.begin(), v.end()
#define PRINTLN(v) {LL i=0; for(auto (a): v ){   cerr <<i << " : "<<  a << endl; i++;}}
#define PRINTSP(v) for(auto (a): v ) {cerr << a << " ";} cerr << endl
#define cmax(a,b) {if(a<b){a=b;}}
#define cmin(a,b) {if(a>b){a=b;}}
#define EACH(a,A) for(auto a: A)
//#define cmax(a,b) a = (a>b ? a:b)
//#define cmin(a,b) a = (a<b ? a:b) 
void func(){
  LL N,M;
  cin >> N>>M;
  VVLL A;
  A.resize(N);

  REP(i,M){
    LL a,b;
    cin >>a>>b;
    a--;
    b--;
    A[a].push_back(b);
    A[b].push_back(a);
  }
  REP(i,N){
    sort(ALL(A[i]));
  }
 
  VLL P;
  REP(i,N){
    P.push_back(i);
  }

  LL cnt=0;
  do{
    if(P[0]!=0){
      continue;
    }
    bool isConnect=true;
    REP(i,N-1){
      LL a = P[i];
      LL b = P[i+1];
      if(binary_search(ALL(A[a]),b)==false){
        isConnect = false;
        break;
      }
    }
    if(isConnect){
      //PRINTSP(P);
      cnt++;
    }
  }while(next_permutation(ALL(P)));
  cout << cnt;
} 
int main()
{
  func();
  return 0;
}
 

Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e9
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R, K,X;
ll A;
ll B[200001];
ll ans;
string S;
char s[52][52];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
ll x[100000];
int main() {
	cin >> N >> X;
	cin >> x[0];
	ans = abs(x[0] - X);
	rep(i, 1, N) {
		cin >> x[i];
		x[i] -= X;
		ans=gcd(ans,abs(x[i]));
	}
	cout << ans << endl;
	
	
	cin >> ans;
	return 0;
}

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



int main(){
    

    bool check[50001];
    check[0]=false;
    check[1]=false;

    for(int i=2;i<=50000;i++){
        check[i]=true;
    }

    for(int i=2;i*i<=50000;i++){
        if(check[i]){
            for(int j=i*2;j<=50000;j+=i){
                check[j]=false;
            }
        }
    }



    while(true){
        int n;
        cin >> n;
        
        if(n==0){
            break;
        }

        if(cin.eof()){
            break;
        }

        int ans = 0;

        for(int i=2;i*2<=n;i++){
            if(check[i]){
                if(check[n-i]){
                    ans++;
                }
            }
        }

        cout << ans << endl;
    }
    
}


Measured memory_bytes: 3108
from itertools import product
D, G = map(int, input().split())
P, C = [], []
for _ in range(D):
    p, c = map(int, input().split())
    P.append(p)
    C.append(c)

def make_pat(i):
    pat = [[0, 1]] * i + [[0]] + [[0, 1]] * (D-i-1)
    return product(*pat)

min_ = sum(p for p in P)
for i in range(D):
    for pat in make_pat(i):
        scr = sum(P[j] * (j+1) * 100 + C[j] for (j, p) in enumerate(pat) if p == 1)
        num = sum(P[j] for (j, p) in enumerate(pat) if p == 1)
        for k in range(P[i]):
            zbn = k * (i+1) * 100 + (0 if k < P[i] else C[i])
            if scr + zbn >= G:
                if min_ > num + k:
                    min_ = num + k
                break

print(min_)


Measured memory_bytes: 3064
/*
ID: learnin7
TASK: test
LANG: C++                 
*/
/* LANG can be C++11 or C++14 for those more recent releases */
#include<bits/stdc++.h>

/*  Macros from Endagorion */
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;


int main(){
        
    ios_base::sync_with_stdio(0);
    
    //ofstream fout ("test.out");
    //ifstream fin ("test.in");
    //fin >> a >> b;
    //fout << a+b << endl;
    int n,m;
    cin>>n>>m;
    vector<string> a(n);
    vector<string> b(m);
    forn(i,n)   cin>>a[i];
    forn(i,m)   cin>>b[i];

    for(int i=0;i<=n-m;i++){
        for(int j=0;j<=n-m;j++){
            bool flag = true;
            for(int k=0;k<m;k++){
                for(int l=0;l<m;l++){
                    if(a[i+k][j+l]!=b[k][l]){
                        flag = false;
                        break;
                    }
                }
                if(!flag){
                    break;
                }
            }
            if(flag){
                cout<<"Yes\n";
                return 0;
            }
        }
    }
    cout<<"No\n";
    return 0;
}



Measured memory_bytes: 3612
package main

// Solution for https://atcoder.jp/contests/abc179/tasks/abc179_d

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

type contest struct {
	in  io.Reader
	out io.Writer
}

func (con *contest) Scan(a ...interface{}) (int, error) {
	return fmt.Fscan(con.in, a...)
}
func (con *contest) Scanln(a ...interface{}) (int, error) {
	return fmt.Fscanln(con.in, a...)
}
func (con *contest) Scanf(f string, a ...interface{}) (int, error) {
	return fmt.Fscanf(con.in, f, a...)
}
func (con *contest) Print(a ...interface{}) (int, error) {
	return fmt.Fprint(con.out, a...)
}
func (con *contest) Println(a ...interface{}) (int, error) {
	return fmt.Fprintln(con.out, a...)
}
func (con *contest) Printf(f string, a ...interface{}) (int, error) {
	return fmt.Fprintf(con.out, f, a...)
}
func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	con := &contest{in: in, out: out}
	con.main()
}

const M = 998244353

type seg struct{ l, r int }

func (con *contest) main() error {
	var N, K int
	con.Scan(&N, &K)
	segs := make([]seg, K)
	for i := 0; i < K; i++ {
		con.Scan(&segs[i].l, &segs[i].r)
		segs[i].r++
	}
	sort.Slice(segs, func(i, j int) bool { return segs[i].l < segs[j].r })
	x := make([]int, N)
	y := make([]int, N)
	x[0] = 1
	y[0] = 1
	for i := 1; i < N; i++ {
		z := 0
		for _, s := range segs {
			if s.l > i {
				break
			}
			z += y[i-s.l]
			z %= M
			if s.r <= i {
				z -= y[i-s.r]
				if z < 0 {
					z += M
				}
			}
		}
		x[i] = z
		y[i] = y[i-1] + x[i]
		y[i] %= M
	}
	con.Println(x[N-1])
	return nil
}


Measured memory_bytes: 5124
x, y = gets.split.map(&:to_i)
pair = (0..100).to_a.product((0..100).to_a).sort_by{|(a, b)| a + b }
ans = 'No'
pair.each do |a, b|
  if (a + b == x ) && ( 2*a + 4*b  == y )
    ans = 'Yes'
    break
  end
end
puts ans


Measured memory_bytes: 14912
#include "bits/stdc++.h"
using namespace std;

#define ll long long int
#define loop(i,s,e) for(ll i=s; i<e; i++)
#define endl '\n'
#define vll vector<ll>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define N 100001
#define pb push_back
#define INF LLONG_MAX
#define inf INT_MAX
#define minusinf INT_MIN

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

ll n;
double arr[3000];
double dp[3000][3000];

double util(ll i, ll count){
	if(i==n and count>0) return 0;
	if(i==n and count<=0) return 1;

	if(dp[i][count]!=-1.0) return dp[i][count];

	double tails = (1-arr[i])*util(i+1, count);
	double heads = (arr[i])*util(i+1, count-1);

	return dp[i][count] = tails+heads;
}


void alpha(){

	loop(i,0,3000){
		loop(j,0,3000){
			dp[i][j]=-1.0;
		}
	}

	cin>>n;

	loop(i,0,n) cin>>arr[i];

	double ans = util(0, n/2+1);

	cout<<fixed<<setprecision(10)<<ans<<endl;
	
	return;

}

int main(){

	ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);


    ll t=1;
	//cin>>t;

  	while(t--) alpha();

	return 0;

}

Measured memory_bytes: 70912
#include<iostream>
#include<cstdio>
#include<cstring>
#include <cstdlib>  
#include <math.h>
#include <cmath>
#include<complex>
#include<cctype>
#include<string>
#include<set>
#include<iomanip>
#include <map>
#include<algorithm>
#include <functional>
#include<vector>
#include<climits>
#include<stack>
#include<queue>
#include<bitset>
#include <deque>
#include <climits>
#include <typeinfo>
#include <utility> 
#include <numeric>
using namespace std;
using Complex = complex<double>;
using ll = long long;
template<typename T>using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
const ll inf = 1145141919810364364LL;
double PI = acos(-1.0);
#define all(x) (x).begin(),(x).end()
#define puts(x) cout << x << endl
#define rep(i,m,n) for(ll i = m;i < n;++i)
#define pb push_back
#define fore(i,a) for(auto &i:a)
#define rrep(i,m,n) for(ll i = m;i >= n;--i)


//ford-fulkerson
struct edge { ll to, cap, rev; };

const int MAX_V = 400;
int used[MAX_V + 3];
vector<edge>G[MAX_V + 3];
int fl = 0;

ll dfs(ll v, ll t, ll f) {
	if (v == t)return f;
	used[v] = 1;
	for (int i = 0; i < G[v].size(); i++) {
		edge e = G[v][i];
		if (used[e.to] == 0 && e.cap > 0) {
			ll d = dfs(e.to, t, min(f, e.cap));
			if (d > 0) {
				G[v][i].cap -= d;
				G[e.to][e.rev].cap += d;
				return d;
			}
		}
	}
	return 0;
}

void add_edge(ll from, ll to, ll cap) {
	edge fe = { to,cap,(int)G[to].size() };
	edge toe = { from,0,(int)G[from].size() };
	G[from].pb(fe);
	G[to].pb(toe);
}

ll max_flow(int s, int t) {
	ll flow = 0;
	while (1) {
		memset(used, 0, sizeof(used));
		ll f = dfs(s, t, inf);
		if (f == 0)return flow;
		flow += f;
	}
}
// end of ford-fulkerson


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

	int X,Y,E;
	cin >> X >> Y >> E;

	for (int i = 0; i < X; i++)add_edge(300,i,1);
	for (int i = 0; i < Y; i++)add_edge(i+100,301,1);
	for (int i = 0; i < E; i++) {
		int x, y;
		cin >> x >> y;
		add_edge(x,y+100,1);
	}
	
	puts(max_flow(300,301));
	
	return 0;
}


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

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; }
constexpr long long INF = 1LL << 60;

long long h[100010];
long long dp[100010];

int main()
{
  int N;
  std::cin >> N;
  for(int i=0; i<N; i++){ std::cin >> h[i]; }

  for(auto& e : dp) { e = INF; }

  // i==0
  dp[0] = 0;

  for(int i = 0; i < N; i++){
    chmin(dp[i+1], dp[i] + std::abs(h[i]-h[i+1]));
    chmin(dp[i+2], dp[i] + std::abs(h[i]-h[i+2]));
  }

  std::cout << dp[N-1] << std::endl;

  return 0;
}

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

int main() {
  int k;
  cin >> k;
  if (k <= 9) {
    cout << k << endl;
    return 0;
  }

  queue<ll> q;
  for (int i = 1; i <= 9; i++) q.push(i);
  ll x;
  while (k != 0) {
    x = q.front();
    q.pop();
    k--;

    int a = x % 10;
    if (a == 0) {
      q.push(x * 10);
      q.push(x * 10 + 1);
    } else if (a == 9) {
      q.push(x * 10 + 8);
      q.push(x * 10 + 9);
    } else {
      q.push(x * 10 + a - 1);
      q.push(x * 10 + a);
      q.push(x * 10 + a + 1);
    }
  }

  cout << x << endl;
  return 0;
}

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

public class Main{
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = sc.nextInt();
		long[] a = new long[count];
		for(int i=0;i<count;i++) {
			a[i] = sc.nextLong();
		}
		
		for(int i=1;i<=count;i++) {
			System.out.print("node "+i+": key = "+a[i-1]+", ");
			if(i!=1) {
				System.out.print("parent key = "+a[i/2-1]+", ");
			}
			if(2*i<=a.length) {
				System.out.print("left key = "+a[2*i-1]+", ");
			}
			if(2*i<=a.length-1) {
				System.out.print("right key = "+a[2*i]+", ");
			}
			System.out.println();
		}
}}



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

using namespace std;

int main() {
    string s;
    getline(cin, s);

    int length = 0, max = 0;
    for (string::size_type i = 0; i < s.size(); i++)
    {
        if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')
        {
            length = 1;
            i++;
            while(s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')
            {
                i++;
                length++;
            }
            
            i--;
            if (length > max)
            {
                max = length;
            }
        }
    }

    cout << max;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

vector<int> fac[10101];

int f(int x){
    int cnt = 0;
    for(int i=1; i*i<=x; i++) for(int j=1; j*j<=x; j++){
        if(i*i + j*j > x) break;
        ll t = x - i*i - j*j - i*j;
        ll a = 1, b = i + j, c = -t;
        for(auto k : fac[abs(c)]){
            if(a*k*k + b*k + c == 0) cnt++;
        }
    }
    return cnt;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    for(int i=1; i<=n; i++){
        for(int j=1; j*j<=i; j++) if(i%j == 0){
            fac[i].push_back(j);
            if(i/j != j) fac[i].push_back(i/j);
        }
    }
    for(int i=1; i<=n; i++) cout << f(i) << "\n";
}

Measured memory_bytes: 4376
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
#https://atcoder.jp/contests/abc148/tasks/abc148_f
#F - Playing Tag on Tree
"""
"""
N = gi()
U = gi()
V = gi()
t = [[] for i in range(N + 1)]
d = [[-1 for i in range(2)] for j in range(N + 1)]

for _ in range(1, N):
    a = gi()
    b = gi()
    t[a].append(b)
    t[b].append(a)


def bfs(s, di):
    d[s][di] = 0
    q = deque()
    q.append(s)
    while len(q):
        v = q.pop()
        for u in t[v]:
            if d[u][di] >= 0:
                continue
            d[u][di] = d[v][di] + 1
            q.append(u)


bfs(U, 0)
bfs(V, 1)

ans = 0
for l in range(1, N + 1):
    if len(t[l]) > 1:
        continue
    du = d[l][0]
    dv = d[l][1]
    #print(l, du, dv)
    if dv >= du:
        ans = max(ans, dv - 1)

print(ans)


Measured memory_bytes: 48528
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;
int main() {
    ll n, m;
    while(cin >> n >> m, n) {
        vector<ll> a(n);
        for(auto &x:a) cin >> x;
        ll ans = -1;
        for(int i = 0; i < n - 1; i++) {
            for(int j = i + 1; j < n; j++) {
                if(a[i] + a[j] <= m)
                    ans = max(ans, a[i] + a[j]);
            }
        }
        if(ans == -1) cout << "NONE" << endl;
        else cout << ans << endl;
    } 
}



Measured memory_bytes: 3080