akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)

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

    int N,M; cin >> N >> M;
    vei X(M);
    rep(i,M) cin >> X[i];

    if(N >= M){
        cout << 0 << endl;
        return 0;
    }

    sort(all(X));

    int width = X[M-1] - X[0];
    vei part(M-1); 
    rep(i,M-1) part[i] = X[i+1] - X[i];

    sort(rall(part));

    int remove = 0;
    rep(i,N-1) remove += part[i];

    cout << width - remove << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <iostream>
#include <istream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <tuple>
#include <iomanip>
#include <climits>
#include <fstream>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
//typedef pair<ll, ll> P;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define revrep(i, n) for(int i = (n)-1; i >= 0; i--)
#define pb push_back
#define f first
#define s second
#define chmin(x, y) x = min(x, y);
#define chmax(x, y) x = max(x, y);
#define sz(a) (int)(a).size()

//const ll INFL = LLONG_MAX;//10^18 = 2^60
const ll INFL = 1LL<<60;
//const int INF = INT_MAX;
const int INF = 1 << 30;//10^9
ll MOD = 1000000007;
//ll MOD = 998244353;
double EPS = 1e-11;

vector<ll> dy = {0, 1, 0, -1, 1, 1, -1, -1, 0};
vector<ll> dx = {1, 0, -1, 0, 1, -1, 1, -1, 0};

void pres(double A){printf("%.12lf\n", A);}
void BinarySay(ll x, ll y = 60){rep(i, y) cout << (x>>(y-1-i) & 1); cout << endl;}
ll cnt_bit(ll x){return __builtin_popcountll(x);}

ll pow_long(ll x, ll k){
  ll res = 1;
  while(k > 0){
    if(k % 2) res *= x;
    x *= x; k /= 2;
  }
  return res;
}

ll pow_mod(ll x, ll k){
  x %= MOD;
  ll res = 1;
  while(k > 0){
    if(k % 2){
      res *= x; res %= MOD;
    }
    x *= x; x %= MOD;
    k /= 2;
  }
  return res;
}

ll inverse(ll x){return pow_mod(x, MOD - 2);};

ll gcd(ll a, ll b){
    if(b == 0) return a;
    return gcd(b, a % b);
}

ll lcm(ll x, ll y){
  ll res = x / gcd(x, y);
  res *= y;
  return res;
};


//コンビネーション
const int MAXcomb = 2000010;
ll fac[MAXcomb], finv[MAXcomb], inv[MAXcomb];
//facはn!,finvは1/n!
//invは逆元
void COMinit(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < MAXcomb; i++){
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
ll comb(int n, int k){
    if(n < k) return 0;
    if(n < 0 || k < 0) return 0;
    return fac[n] * finv[k] % MOD * finv[n-k] % MOD;
}

const int MAXkai = 200010;
ll kai_memo[MAXkai];
ll kai(ll N){
  if(kai_memo[N] != 0) return kai_memo[N];
  if(N <= 1) return 1;
  return kai_memo[N] = N * kai(N-1) % MOD;
}

ll disit(ll s, ll base = 10){
  ll res = 0;
  while(s){
    res++;
    s /= base;
  }
  return res;
}

//素因数分解O(√n)
vector<pair<ll, ll>> MakePrimeList(ll x) {
    vector<pair<ll, ll>> res;
    for(ll k=2; k*k<=x; k++) {
        if(x % k == 0) {
            ll cnt = 0;
            while(x % k == 0){
              x /= k;
              cnt++;
            }
            res.pb({k, cnt});
        }
    }
    if(x > 1) res.push_back({x, 1});
    return res;
}


void solve(){
  ll N, K;
  cin >> N >> K;
  cout << disit(N, K) << endl;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  solve();
}


Measured memory_bytes: 256
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const N = parseInt(arg[0].split(" ")[0]);
    let L = arg[1].split(" ").map(n=>parseInt(n)).sort((a,b)=>b-a);
    
    const longest = L.shift();
    const sum = L.reduce((m,n)=>m+n);
    
    console.log(longest < sum ? "Yes" : "No");
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 20936
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{
	int n, p[25];

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> p[i];
	}
	int ans = 0;
	for (int i = 0; i < n - 2; i++) {
		if ((p[i] < p[i + 1] && p[i + 1] < p[i + 2])
			|| (p[i + 2] < p[i + 1] && p[i + 1] < p[i])) {
				ans++;
		}
	}
	
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
n=io.read("*n","*l")
a={{0},{0}}
for i=1,2 do
    for j=2,n+1 do
        a[i][j]=a[i][j-1]+io.read("*n")
    end
end

total=0
for i=2,n+1 do
    total=math.max(total, a[1][i]+a[2][n+1]-a[2][i-1])
end
print(total)

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

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int i = 0;i < (n);i++)
#define FOR(i, a, b) for(int i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

const int64 mod = 1e9+7;

int32 N, M;
vector<PII> G[112345];
map<int32, vector<int32>> G2[112345];
map<int32, int32> d[112345];
bool visited[112345] = {};

int main(void){
	cin >> N >> M;
	REP(i, M){
		int32 p, q, c;
		cin >> p >> q >> c;
		p--; q--;
		G[p].push_back({q, c});
		G2[p][c].push_back(q);
		G[q].push_back({p, c});
		G2[q][c].push_back(p);
	}

	using taplis = tuple<int32, int32, int32>;
	priority_queue<taplis, vector<taplis>, greater<>> pq;
	pq.push(taplis(0, 0, -1));// d, v, c
	int32 res = INF;
	while(pq.size()){
		int32 dis, v, c;
		tie(dis, v, c) = pq.top(); pq.pop();
		if((v != 0 && d[v][c] != 0) && d[v][c] < dis) continue;
		if (!visited[v]){
			visited[v] = 1;
			REP(i, G[v].size()){
				int32 to, cc;
				tie(to, cc) = G[v][i];
				if ((to != 0 && d[to][cc] == 0) || d[to][cc] > d[v][c] + (c != cc)){
					d[to][cc] = d[v][c] + (c != cc);
					if (to == N - 1)
						res = min(res, d[to][cc]);
					pq.push(taplis(d[to][cc], to, cc));
				}
			}
		}else{
			REP(i, G2[v][c].size()){
				int32 to = G2[v][c][i];
				if((to != 0 && d[to][c] == 0) || d[to][c] > d[v][c]){
					d[to][c] = d[v][c];
					if(to == N-1)
						res = min(res, d[to][c]);
					pq.push(taplis(d[to][c], to, c));
				}
			}
		}
	}

	cout << (res==INF?-1:res) << endl;
}

Measured memory_bytes: 96048
#include <iostream>
#include <unordered_set>
#include <cstdint>
#include <vector>
#include <string>
#include <climits>
#include <set>
#include <algorithm>
using namespace std;

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

	while (a <= b)
	{
		if (a % k == 0)
		{
			cout << "OK";
			return 0;
		}
		a++;
	}
	cout << "NG";
}

Measured memory_bytes: 3616
n, y = map(int, input().split())

for i in range(n+1):
    for j in range(n-i+1):
        s = y-(i*10000+j*5000)
        k = n-(i+j)
        if k*1000==s:
            print(i, j, k)
            exit(0)

print(-1, -1, -1)

Measured memory_bytes: 3060
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

int main(){

    int i,j,n;
    double xy[8][2];
    double a,count;

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

    a = 0.0;
    count = 0.0;
    for(i = 0; i < n-1; i++){
        for( j = i+1; j < n; j++ ){
            a += sqrt((xy[i][0]-xy[j][0])*(xy[i][0]-xy[j][0])+(xy[i][1]-xy[j][1])*(xy[i][1]-xy[j][1]));
            count += 1.0;
        }
    }
    
    a = a*(double)(n-1);

    printf("%.6f\n",a/count);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;

int binpow(int a, int b) {
    if (b == 0)
    {
        return 1;
    }
    ll res = binpow(a, b / 2);
    res*=res;
    if (b % 2)
    {
        return res * a;
    }
    return res;
}

ll gcd(ll a,ll b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}
string to_upper(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
    return a;
}
 
string to_lower(string a)
{
    for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
    return a;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,k;
    cin>>n>>k;
    int h[n];
    int dp[n];
    for (int i=0;i<n;++i)
    {
        cin>>h[i];
    }
    dp[0]=0;
    for (int i=1;i<n;++i)
    {
        dp[i]=dp[i-1]+abs(h[i]-h[i-1]);
        for (int j=2;j<=k&&i-j>=0;++j)
        {
           dp[i]=min(dp[i-j]+abs(h[i]-h[i-j]),dp[i]); 
        }
    }
    cout<<dp[n-1];
    return 0;
}

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

using namespace std;

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

ll A[300100];
ll AY[200100];
int main(){
    int N;
    cin >> N;
    priority_queue<ll, vector<ll>, greater<ll> > pr;
    ll X = 0;
    ll Y = 0;
    REP(i,3*N){
        ll a;
        cin >> a;
        A[i] = a;
        if(i < N) {
            pr.push(a);
            X += a;
        }
        else{
            AY[i-N] = a;
        }
    }
    sort(AY, AY+2*N);
    map<ll, int> in;
    map<ll, int> out;
    for(int i = 0; i < N; i++){
        Y += AY[i];
        in[AY[i]]++;
    }
    for(int i = N; i < 2*N; i++){
        out[AY[i]]++;
    }


    ll ans = X-Y;
    for(int p = N; p < 2*N; p++){
        ll a = A[p];

        ll x = pr.top();
        if(a > x){
            pr.pop();
            pr.push(a);
            X += a - x;
        }

        auto bound = in.end();
        bound--;
        if(bound->first >= a){
            auto m = out.begin();
            ll y = m->first;
            Y += y - a;
            m->second--;
            if(m->second == 0) out.erase(m->first);

            in[a]--;
            if(in[a] == 0) in.erase(a);
            in[y]++;
        }
        else{
            out[a]--;
            if(out[a] == 0) out.erase(a);
        }

        //cout<< X << " " << Y << endl;
        ans = max(ans, X-Y);
    }

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


Measured memory_bytes: 17396
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int N, x;
    cin >> N >> x;
    vector<long long int> a(N);
    for (int i = 0; i < N; i++){
        cin >> a.at(i);
    }
    vector<long long int> new_a(a.begin(), a.end());

    if (new_a[0] > x){
        new_a[0] = x;
    }
    for(int i = 0; i < N-1; i++){
        while(1)
        {
            if (new_a[i] + new_a[i+1] <= x){
                break;
            }
            if (new_a[i] + new_a[i+1] > x){
                new_a[i+1] = x - new_a[i];
            }
        }
    }
    long long int ans = accumulate(a.begin(), a.end(), 0LL) - accumulate(new_a.begin(), new_a.end(), 0LL);
    cout << ans << endl;
}

Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main()
{
    int a,b,c,k,ka=0,kb=0,kc=0;
    cin >>a>>b>>c>>k;

    if(a>=k)ka=k;
    else ka=a;
    k=k-ka;
    if(k>0)
    {
    if(b>=k)kb=k;
    else kb=b;
    }
    k=k-kb;
    if(k>0)
    {
    if(c>=k)kc=k;
    else cout << "error" << endl;
    }

    cout << (ka-kc) << endl;
    return 0;
}


Measured memory_bytes: 3640
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

while True:
    n, x = map(int, sys.stdin.readline().split())
    if n == 0 and x == 0:
        break

    combi = 0
    for a in range(1, n-1):
        for b in range(a+1, n): # b > a
            c = x - a - b
            if c <= b:  # c must be > b
                break
            if c > n:
                continue
            # print(a, b, c)
            combi += 1

    print(combi)




Measured memory_bytes: 5604
package main

import "fmt"

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func main() {
	var x, y int
	fmt.Scan(&x, &y)
	ans := abs(abs(x) - abs(y))
	if x*y > 0 { // xとyは同符号
		if x > y {
			ans += 2
		}
	} else if x*y == 0 { // xとyのどちらかが0
		if x == 0 {
			if y < 0 {
				ans++
			}
		} else { // y == 0
			if x > 0 {
				ans++
			}
		}
	} else { // xとyは異符号
		ans++
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
n,x,m = map(int,input().split())

if x == 0:
    print(0)
    exit()

li = [-1] * (m+1)
v = [False] * (m+1)
v2 = [False] * (m+1)
v[x] = True
tmp = x
ans = x
loop = 0
cnt = 0
cnt_l = 0
loop_li = [0]
ans_li = [x]

for i in range(m):
    li[i] = (i ** 2) % m

while True:
    tmp = li[tmp]
    ans += tmp
    v[tmp] = True
    cnt += 1
    ans_li.append(ans_li[-1] + tmp)
    if v[li[tmp]]:
        break

while True:
    tmp = li[tmp]
    loop += tmp
    v2[tmp] = True
    cnt_l += 1
    loop_li.append(loop_li[-1] + tmp)
    if v2[li[tmp]]:
        break

cnt -= cnt_l - 1
loop_li = loop_li[1:]
ans_li = ans_li

if n < len(ans_li):
    print(ans_li[n-1])
elif n == len(ans_li):
    print(ans_li[n-1])
else:
    n -= len(ans_li)
    if len(loop_li) == 0:
        print(ans_li[-1])
    else:
        if n % len(loop_li) == 0:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)))
        else:
            print(ans_li[-1] + loop_li[-1] * (n//len(loop_li)) + loop_li[n%len(loop_li)-1])


Measured memory_bytes: 76288
a, b = map(int, input().split())

s = input()
t = input()

def gcd(x, y):
    if y==0:
        return x
    else:
        return gcd(y, x%y)
    
k = gcd(a, b)

f = 1

for i in range(k):
    if not s[i*(a//k)]==t[i*(b//k)]:
        f = -1
        
if f<0:
    print(-1)
else:
    print(a*b//k)

Measured memory_bytes: 3316
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    H,W = LI()
    A = [LI() for _ in range(H)]
    B = [LI() for _ in range(H)]
    C = [[abs(A[i][j]-B[i][j]) for j in range(W)] for i in range(H)]
    D = [[set() for _ in range(W+1)] for _ in range(H+1)]
    D[0][1] = {0}
    for i in range(1,H+1):
        for j in range(1,W+1):
            for k in D[i-1][j] | D[i][j-1]:
                D[i][j].add(abs(k+C[i-1][j-1]))
                D[i][j].add(abs(k-C[i-1][j-1]))

    print(min(D[-1][-1]))


if __name__ == '__main__':
    main()

Measured memory_bytes: 551576
MOD = 10 ** 9 + 7

n=int(input()) #3
alst=list(map(int,input().split())) #[1,2,3]

s=[0]
for i in range(len(alst)):
  s.append(s[i]+alst[i])

sum=0

for i in range(len(alst)-1):
  sum+=alst[i]*(s[len(s)-1]-s[i+1])

print(sum%MOD)

Measured memory_bytes: 31444
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <set> 
#include <map>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <cctype>
#define REP(i,n) for(int i=0; i<(n); ++i)
#define FOR(i,a,b) for(int i=(a); i<(b); ++i)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 100100100;
const ll INFLL = 1001001001001001001;  // > 10^18
const int MOD = (int)1e9 + 7;
const ll MODLL = (ll)1e9 + 7;
const double EPS = 1e-9;

int main () {
    
    char a,b; cin >> a>>b;


    if (a == 'H') {
        if (b == 'H') {
            cout << 'H' << endl;
        } else {
            cout << 'D' << endl;
        } 
    } else {
        if (b == 'D') {
            cout << 'H' << endl;
        } else {
            cout << 'D' << endl;
        } 
    } 
    
    return 0;
}




Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
  	int a, b;
  	cin >> a >> b;
  	int c = b - a, h = 0;
  	for(int i = 1; i < b - a; i++){
      	h += i;
    }
  	cout << h - a;
  	return 0;
}

Measured memory_bytes: 256
w,h,n = map(int,input().split())
x_a = 0
y_a = 0
for i in range(n):
    x,y,a = map(int,input().split())
    
    if a == 1:
        if x_a < x:
            x_a = x
    elif a == 2:
        if x < w:
            w = x
    elif a == 3:
        if y_a < y:
            y_a = y
    elif a == 4:
        if y < h:
            h = y

if w - x_a <= 0 or h - y_a <= 0:
    ans = 0
else:
    ans = (w - x_a)*(h - y_a)

print(ans)

Measured memory_bytes: 9132
#include<cstdio>

int n,a[101],sum,i;

int main()
{
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	for(i=1;i<n-1;i++)
		if((a[i]>a[i-1]&&a[i]<a[i+1])||(a[i]<a[i-1]&&a[i]>a[i+1]))
			sum++;
	printf("%d",sum);
	return 0;
}

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

#define ll long long
#define mk make_pair
#define pb push_back
#define ff first
#define sc second

ll gcd(ll a, ll b){
   if(b == 0) return a;
   
   return gcd(b, a % b);
}

using namespace std;


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

   string n; cin >> n;
   string ans = "No";
   for(char i : n){
      if(i == '9'){
         ans = "Yes";
         break;
      }
   }
   cout << ans;
   return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;

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; }

__attribute__ ((constructor))
void init() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << fixed << setprecision(10);
}

signed main(){
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.rbegin(), t.rend());
  if(s < t)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3616
// J'aime
// Chemise Blanche

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

#define int long long

#define ii pair<int,int>
#define fi first
#define sc second

#define all(x) (x).begin(),(x).end()
#define dbg(x) cerr << __LINE__ << " > " << #x << " = " << (x) << endl

void MAIN() {
  int n, k;
  cin >> n >> k;
  if (n == 0) cout << 1 << '\n';
  else {
    int c = 0;
    while (n) {
      n /= k;
      c++;
    }
    cout << c << '\n';
  }
}

signed main() {
#ifdef _DEBUG
  // freopen("in" , "r", stdin );
  // freopen("out", "w", stdout);
#endif
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3660
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,h,w = IR(3)
    print((n-h+1)*(n-w+1))
    return

#B
def B():
    n = I()
    a,b = LI()
    p = LI()
    k = [0 for i in range(a+1)]
    k += [1 for i in range(b-a)]
    k += [2 for i in range(max(p)+1-b)]
    d = defaultdict(int)
    for i in p:
        d[k[i]] += 1
    ans = min(d[0],d[1],d[2])
    print(ans)
    return

#C
def C():
    h,w = LI()
    s = SR(h)
    bfs_map = [[-1 for i in range(w)] for j in range(h)]
    d = [[0,1],[0,-1],[1,0],[-1,0]]
    ans = 0
    for y in range(h):
        for x in range(w):
            if s[y][x] == "#":
                if bfs_map[y][x] < 0:
                    bfs_map[y][x] = 0
                    a = 1
                    b = 0
                    q = deque()
                    q.append([y,x])
                    while q:
                        n,m = q.popleft()
                        for dy,dx in d:
                            n2 = n+dy
                            m2 = m+dx
                            if 0 <= n2 < h and 0 <= m2 < w:
                                if s[n][m] != s[n2][m2] and bfs_map[n2][m2] < 0:
                                    if s[n2][m2] == "#":a += 1
                                    else:b += 1
                                    bfs_map[n2][m2] = 0
                                    q.append([n2,m2])
                    ans += a*b
    print(ans)
    return

#D
def D():
    n,q = LI()
    a = LI()
    b = [a[i] for i in range(n)]
    c = [a[i] if i%2 else 0 for i in range(n)]
    for i in range(n-1):
        b[i+1] += b[i]
        c[i+1] += c[i]
    for i in range(q):
        x = I()
        l = 0
        r = n
        while r-l > 1:
            m = (l+r)//2
            if abs(a[m]-x) < abs(a[m-(n-m-1)]-x):
                l = m
            else:
                r = m
        l = r-(n-r)
        r -= 1
        ans = b[n-1]-b[r]
        l -= 1
        if l >= 0:
            if not n%2:
                ans += c[l]
            else:
                ans += b[l]-c[l]
        print(ans)
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


Measured memory_bytes: 66028
#include<iostream>
#include<algorithm>

using namespace std;
int n, m;
char c[1080][1080];
int cnt[1080][1080];
char ans[2][2];
int anss, res;
int main(){
	cin >> m >> n;
	for(int i = 1;i <= m;i++)
		for(int j = 1;j <= n;j++) 
			cin >> c[i][j];
	
	for(int i = 0;i < 2;i++)
		for(int j = 0;j < 2;j++)
			cin >> ans[i][j];
			
	for(int i = 1;i <= m;i++)
		for(int j = 1;j <= n;j++){
			cnt[i][j] = 1;
		  	for(int k = 0;k < 2;k++)
				for(int l = 0;l < 2;l++)
					if(c[i + k][j + l] != ans[k][l])cnt[i][j] = 0;
			res += cnt[i][j];
		}
	
	int anss = res;
	for(int i = 1;i <= m;i++){
		for(int j = 1;j <= n;j++){
			int last = c[i][j];
			int tres;
			c[i][j] = 'J';
			tres = res;
			for(int k = i - 1;k <= i;k++)
				for(int l = j - 1;l <= j;l++){
					int tmp = 1;
					for(int o = 0;o < 2;o++)
						for(int p = 0;p < 2;p++)
							if(c[k + o][l + p] != ans[o][p])tmp = 0;
					tres += tmp - cnt[k][l];	
				}
                        anss = max(anss, tres);
			c[i][j] = 'O';
			tres = res;
			for(int k = i - 1;k <= i;k++)
				for(int l = j - 1;l <= j;l++){
					int tmp = 1;
					for(int o = 0;o < 2;o++)
						for(int p = 0;p < 2;p++)
							if(c[k + o][l + p] != ans[o][p])tmp = 0;
					tres += tmp - cnt[k][l];	
				}
                        anss = max(anss, tres);
			
			c[i][j] = 'I';
			tres = res;
			for(int k = i - 1;k <= i;k++)
				for(int l = j - 1;l <= j;l++){
					int tmp = 1;
					for(int o = 0;o < 2;o++)
						for(int p = 0;p < 2;p++)
							if(c[k + o][l + p] != ans[o][p])tmp = 0;
					tres += tmp - cnt[k][l];	
				}
                        anss = max(anss, tres);
			
			c[i][j] = last;
		}
	}
	cout << anss << endl;
	return 0;
	
}

Measured memory_bytes: 6448
// D - Prediction and Restriction

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

// 勝てる時は勝てる手を出す。
// 勝てる手が出せない時、K回後で勝てる手ではない方を出す。

int main()
{
    int N, K;
    int R, S, P;
    string T;

    cin >> N >> K;
    cin >> R >> S >> P;
    cin >> T;

    char hand[100000];
    ll score = 0;

    char cannot;
    for (int i = 0; i < N; i++) {
        // K回前の手をチェック
        if (i - K >= 0) {
            cannot = hand[i - K];
        } else {
            cannot = 'n'; // none
        }

        // 勝てる手とK回後の勝てる手から出す手を決定
        switch (T[i]) {
            case 'r': // 'p'なら勝てる
                if (cannot != 'p') {
                    hand[i] = 'p';
                    score += P;
                } else {
                    // cannotはpなのでrもsも出せる
                    if (i + K < N) {
                        if (T[i + K] == 'p') {
                            hand[i] = 'r';
                        } else {
                            hand[i] = 's';
                        }
                    } else {
                        hand[i] = 'r'; // どちらでもよい
                    }
                }
                break;

            case 's': // 'r'なら勝てる
                if (cannot != 'r') {
                    hand[i] = 'r';
                    score += R;
                } else {
                    // cannotはrなのでrもsも出せる
                    if (i + K < N) {
                        if (T[i + K] == 'r') {
                            hand[i] = 's';
                        } else {
                            hand[i] = 'p';
                        }
                    } else {
                        hand[i] = 's'; // どちらでもよい
                    }
                }
                break;

            case 'p': // 's'なら勝てる
                if (cannot != 's') {
                    hand[i] = 's';
                    score += S;
                } else {
                    // cannotはsなのでrもsも出せる
                    if (i + K < N) {
                        if (T[i + K] == 's') {
                            hand[i] = 'p';
                        } else {
                            hand[i] = 'r';
                        }
                    } else {
                        hand[i] = 'p'; // どちらでもよい
                    }
                }
                break;

            default:
                cout << "error" << endl;
                return 0;
        }

    }

    // **** debug ****
    /*
    for (int i = 0; i < N; i++) {
        cout << hand[i];
    }
    cout << endl;
    */
    // ***************s

    cout << score << endl;

    return 0;
}

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

#define rep(i,n) for(int i=0; i<(n); i++)
#define rep2(i,x,n) for(int i=x; i<(n); i++)
#define all(x) x.begin(),x.end()
typedef long long ll;
ll mod = 1000000007;
ll inf = 1e18;
int main(){

    int n,m,x;
    cin >> n >> m >> x;
    vector<int> c(n);
    vector<vector<int>> a(n,vector<int>(m));
    rep(i,n){
        cin >> c[i];
        rep(j,m) cin >> a[i][j];
    }
    vector<int> skill(m);
    int cost=-1;
    
    for(int bit=0; bit<(1<<n); bit++){
        int sum=0;
        rep(i,n){
            if(bit & (1<<i)){
                rep(j,m) skill[j]+=a[i][j];
                sum+=c[i];
            }
        }
        bool ans=true;
        rep(i,m){
            if(skill[i]<x) ans=false;
            skill[i]=0;
        }
        if(ans){
            if(cost==-1) cost=sum;
            else cost=min(cost,sum);
        }
        // if(ans) cout << 0 << ' ';
        // else cout << 1 << ' ';
        // cout << sum << endl;
    }

    cout << cost << endl;

    return 0;
}

Measured memory_bytes: 3660
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>

int main(){
  int A,B,C;
  scanf("%d%d%d",&A,&B,&C);
  int sa;
  sa = C - A - B;
  if(sa <= 1){
    printf("%d\n",B + C);
    return 0;
  }else{
    printf("%d\n",A + B*2 + 1);
    return 0;
  }
}

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

using ll = long long;

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

    ll ans = 1;
    for(ll i = 2; i * i <= gcd; i++){
        if(gcd % i == 0){
            while(gcd % i == 0){
                gcd /= i;
            }
            ans++;
        }
    }
    if(gcd != 1) ans++;
    cout << ans << endl; 
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define f(i,a,b) for(int i=a;i<=b;i++)
#define mm make_pair
#define pi 2*acos(0.0)
#define lcm(a,b) (a*b)/__gcd(a,b)
#define Case(i,ans) cout<<"Case "<<i<<": "<<ans<<endl;
#define cp(i,ans) printf("%.if",ans);
#define cpp(i,ans) cout.precision(i);cout<<fixed<<ans<<endl;
#define Y {cout<<"YES"<<endl;return 0;}
#define pb(x) push_back(x)
#define lowbit(x) (x)&(-x)
#define out(x) {cout<<x<<endl;return 0;} 
#define all(v) v.begin(),v.end() 
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int inf=0x3f3f3f,maxn=2e5+100;
ll gcd(ll x,ll y){if(y==0) return x;else return gcd(y,x%y);} 
ll ksm(ll a,ll b){ll r=1;while(b){if(b&1) r=(r*a)%mod;a=a*a%mod;b>>=1;}return r;} 
int n,m,a[maxn]; 
int main()
{
	fast;cin>>n;
	int max1=0;
	for(int i=1;i<=n;i++) 
	{
		cin>>a[i];
		max1=max(max1,a[i]);
	}
	sort(a+1,a+1+n);
	int mid=n/2+1,ans=0;
	for(int i=1;i<=max1;i++)
	{
		int pos1=lower_bound(a+1,a+1+n,i)-a;
		//int pos2=upper_bound(a+1,a+1+n,i)-a;
		int sum1=n-pos1+1,sum2=pos1-1;
		if(sum1==sum2) ans++;
	}
	cout<<ans<<endl;
} 

Measured memory_bytes: 640
N = int(input())
A, B, C = [list(map(int, input().split())) for _ in range(3)]

for x in [A, B, C]:
	x.sort()

def bsr(a, v, lo=0, hi=None):
	if hi == None:
		hi = len(a) - 1
	while lo <= hi:
		mid = (lo + hi) // 2
		if v < a[mid]:
			hi = mid - 1
		else:
			lo = mid + 1
	return lo

bt = []
for b in B:
	bt += [max(0, (N - bsr(C, b)))]

for i in range(len(B) - 2, -1, -1):
	bt[i] += bt[i + 1]

r = 0
for ai, a in enumerate(A):
	bif = bsr(B, a)
	if bif < N:
		r += bt[bif]

print(r)


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

int main(void){
    string s; cin >> s;
  if(s[0] == s[1] || s[0] == s[2] || s[1] == s[2]) cout << "No" << endl;
  else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 3632
N = int(input())
B = list(map(int, input().split()))

flag = True
ans = list()
while flag and len(B):
    for i in range(len(B) - 1, -1, -1):
        if B[i] == i + 1:
            del B[i]
            ans.append(i + 1)
            break
    else:
        flag = False
        break

if not flag:
    print(-1)
else:
    for i in range(len(ans)-1,-1,-1):
        print(ans[i])


Measured memory_bytes: 3064
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int W = sc.nextInt();
		int w[] = new int[n];
		int v[] = new int[n];
		int Sv = 0;
		for (int i = 0; i < n; i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
			Sv += v[i];
		}
		int oo = (int)1e9 + 100;
		int DP[][] = new int[n][Sv + 1];
		for (int i = 0; i < n; i++) {
			for (int j = 1; j <= Sv; j++) DP[i][j] = oo;
		}
		DP[0][v[0]] = w[0];
		for (int i = 1; i < n; i++) {
			for (int j = 0; j <= Sv; j++) {
				DP[i][j] = DP[i - 1][j];
				if (j >= v[i]) DP[i][j] = Math.min(DP[i - 1][j - v[i]] + w[i],DP[i][j]);
			}
		}
		for (int i = Sv; i >= 0; i--) {
			if (DP[n - 1][i] <= W) {
				System.out.print(i);
				System.exit(0);
			}
		}
	}

}


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

int main () {

  int N, K;
  cin >> N >> K;
  
  int ans = 0;
  for (int i=0; i<N; i++) {
    int x; cin >> x;
    ans += 2*min(abs(x), abs(K-x));
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
n, m = gets.chomp.split(" ").map(&:to_i)
a_arr = gets.chomp.split(" ").map(&:to_i).sort

bc = []
m.times do |i|
  bc << gets.chomp.split(" ").map(&:to_i)
end
bc.sort_by!{|(b,c)| -c }

index = 0
bc.each do |(b, c)|
  i = 0
  b.times do
    if a_arr[index + i] <= c
      a_arr[index + i] = c
    else
      break
    end
    i += 1
    break if a_arr[index + i].nil?
  end
  index += i
  break if a_arr[index].nil?
end

puts a_arr.inject(0) {|sum,x| sum + x }


Measured memory_bytes: 21880
#include <iostream>
#include <algorithm>

int maxt(int x){
    if (10 - (x % 10) == 10)return x;
    return x + (10 - (x % 10));
}
int remt(int x){
    if (10 - (x % 10) == 10)return 0;
    return 10 - (x % 10);
}

int main() {
	int A, B, C, D, E;
	std::cin >> A >> B >> C >> D >> E;

    int sum = maxt(A) + maxt(B) + maxt(C) + maxt(D) + maxt(E);

    sum -= std::max({remt(A), remt(B), remt(C), remt(D), remt(E)});

    std::cout << sum << std::endl;
	return 0;
}

Measured memory_bytes: 256
h,w=gets.split.map(&:to_i)
a=h.times.map{gets.chomp}

b = [[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1],[-1,0],[-1,1]]

h.times{|i|
  w.times{|j|
    if a[i][j]=='.' then
      sum = 0
      b.each{|y,x|
        ny = i+y
        nx = j+x
        if 0<=ny&&ny<h&&0<=nx&&nx<w then
          if a[ny][nx]=='#' then
            sum+=1
          end
        end
      }
      a[i][j]=sum.to_s
    end
  }
}

a.each{|t|puts t}


Measured memory_bytes: 3836
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <string>

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

using namespace std;

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

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

int A, B;

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


    if (A < 10 && B < 10) {
        cout << A * B << endl;
    } else {
        cout << -1 << endl;
    }
}



Measured memory_bytes: 256
program get_everything
    implicit none

    integer(4):: n,m,i,j
    integer(4),allocatable:: a(:), b(:),c(:),key(:), dp(:)
    integer(4),parameter:: inf=1000000001

    read*, n,m
    allocate(a(m), b(m), key(m))
    allocate(dp(0:2**n-1))
    dp(:) = inf
    dp(0) = 0

    do i=1,m
        read*,a(i),b(i)
        allocate(c(b(i)))
        read*,c(:)
        key(i) = sum(2**(c(:)-1))
        deallocate(c)
    end do

    do i=0,2**n-1
        do j=1,m
            dp(or(i,key(j))) = min(dp(or(i,key(j))),dp(i)+a(j))
        end do
    end do

    if (dp(2**n-1) == inf) then
        print*, -1
    else
        print*, dp(2**n-1)
    end if

end program get_everything

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int mod=1000000007,MAX=1<<17,MAX_LOG=20,INF=1<<30;
vector<pair<int,ll>> G[MAX];
int N,par[MAX_LOG][MAX],depth[MAX];
ll dis[MAX];

void BFS(int u){
    for(int i=0;i<N;i++){
        depth[i]=-1;
        dis[i]=0;
        for(int j=0;j<20;j++){
            par[j][i]=-1;
        }
    }
    queue<int> Q;
    Q.push(u);
    depth[u]=0;
    dis[u]=0;
    while(!Q.empty()){
        int a=Q.front();
        Q.pop();
        for(int i=0;i<G[a].size();i++){
            int b=G[a][i].first;
            ll c=G[a][i].second;
            if(depth[b]==-1){
                depth[b]=depth[a]+1;
                dis[b]=dis[a]+c;
                par[0][b]=a;
                Q.push(b);
            }
        }
    }
    return;
}

void init(){
    for(int k=0;k+1<MAX_LOG;k++){
        for(int i=0;i<N;i++){
            if(par[k][i]<0) par[k+1][i]=-1;
            else par[k+1][i]=par[k][par[k][i]];
        }
    }
}

int lca(int u,int v){
    if(depth[u]>depth[v]) swap(u,v);
    for(int i=0;i<20;i++){
        if(((depth[v]-depth[u])>>i)&1) v=par[i][v];
    }
    if(u==v) return u;
    
    for(int i=19;i>=0;i--){
        if(par[i][u]!=par[i][v]){
            u = par[i][u];
            v = par[i][v];
        }
    }
    return par[0][u];
}


int main(){

    cin>>N;
    for(int i=0;i<N;i++){
        int k;cin>>k;
        for(int j=0;j<k;j++){
            int a;cin>>a;
            G[i].push_back({a,1});
            G[a].push_back({i,1});
        }
    }
    
    BFS(0);
    init();
    
    int Q;cin>>Q;
    while(Q){
        int a,b;cin>>a>>b;
        cout<<lca(a,b)<<endl;
        
        Q--;
    }
}



Measured memory_bytes: 20840
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    double d;
    cin>>d;
    double a=d/3;
    a=pow(a,3);
    doublecout(a);
    return 0;
}


Measured memory_bytes: 384
#include<iostream>
#include<cstring> 
using namespace std;
bool a[10000000];
int main()
{
	int n;
	while(cin>>n)
	{	
		int js=0;
		for (int i=2;i<=n;i++)
		  if (!a[i]) {js++;for (int j=i+i;j<=n;j+=i) a[j]=true;}
		cout<<js<<endl;   
	}
} 


Measured memory_bytes: 3976
import sys
s=input() 
n = len(s)
k=(n-1)//2

for i in range(n):
    if s[i]!=s[-i-1]:
        print('No')
        sys.exit()
for j in range(k):
    if s[j]!=s[k-j-1] or s[j+k+1]!=s[2*k-j]:
        print('No')
        sys.exit()
print('Yes')



Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
  ll n,m;cin>>n>>m;
  ll x[n],y[n],z[n];
  vector<ll>v[8];
  for(ll i=0;i<n;i++){
    cin>>x[i]>>y[i]>>z[i];
    v[0].push_back(x[i]+y[i]+z[i]);
    v[1].push_back(x[i]+y[i]-z[i]);
    v[2].push_back(x[i]-y[i]+z[i]);
    v[3].push_back(x[i]-y[i]-z[i]);
    v[4].push_back(-x[i]+y[i]+z[i]);
    v[5].push_back(-x[i]+y[i]-z[i]);
    v[6].push_back(-x[i]-y[i]+z[i]);
    v[7].push_back(-x[i]-y[i]-z[i]);
  }
  ll ans=0;
  for(ll i=0;i<8;i++){
    sort(v[i].begin(),v[i].end(),greater<ll>());
    ll sum=0;
    for(ll j=0;j<m;j++)sum+=v[i][j];
    ans=max(ans,sum);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 384
// https://atcoder.jp/contests/abc144/tasks/abc144_e

#include "algorithm"
#include "iostream"
#include "queue"
#include "set"
#include "vector"
#define rep(i, to) for (ll i = 0; i < (to); ++i)
#define repf(i, from, to) for (ll i = from; i < (to); ++i)
using namespace std;
typedef long long ll;
template <typename T>
using V = vector<T>;
using VL = V<ll>;
using VVL = V<VL>;
template <typename T, typename U>
using P = pair<T, U>;
using PL = P<ll, ll>;
using VPL = V<PL>;
template <typename T>
inline bool chmax(T& a, T b);
template <typename T>
inline bool chmin(T& a, T b);
void print_ints(vector<ll> v);
template <typename T>
void drop(T a);

void solve() {
  ll N, K;
  cin >> N >> K;
  VL as(N);
  rep(i, N) cin >> as[i];
  VL fs(N);
  rep(i, N) cin >> fs[i];

  sort(as.begin(), as.end());
  sort(fs.rbegin(), fs.rend());

  ll ng = -1;
  ll ok = 1e18;

  while (ok - ng > 1) {
    ll mid = (ok + ng) / 2;
    ll rest = K;
    ll failed = false;

    rep(i, N) {
      ll target = mid / fs[i];  // A は target 以下にならないといけない

      ll diff = as[i] - target;
      if (diff < 0) continue;
      if (diff > rest) {
        failed = true;
        break;
      }

      rest -= diff;
    }

    if (failed) {
      ng = mid;
    } else {
      ok = mid;
    }
  }

  cout << ok << endl;
}

struct exit_exception : public std::exception {
  const char* what() const throw() { return "Exited"; }
};

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

  try {
    solve();
  } catch (exit_exception& e) {
  }

  return 0;
}
#endif

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

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

void print_ints(vector<ll> v) {
  rep(i, v.size()) {
    if (i > 0) {
      cout << " ";
    }

    cout << v[i];
  }

  cout << endl;
}

template <typename T>
void drop(T res) {
  cout << res << endl;
  throw exit_exception();
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
#define float double
#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define F first
#define S second
using namespace std;

vector <float> p;
int n;

float dp[3000][3000];

float toss(int number, int heads){
    if(number == n){
        if(heads > n - heads)
            return 1;
        else return 0;
    }
   if(dp[number][heads] > -1){
        return dp[number][heads];
    }
    return dp[number][heads] = p[number]*toss(number + 1, heads + 1) + (1 - p[number])*toss(number + 1, heads);
    
}


signed main(){
    cin >> n;
    p.resize(n);
    memset(dp, -2 ,sizeof(dp));
    for(int i = 0; i < n; i++)
        cin>>p[i];
    printf("%0.10lf",toss(0,0));
}



Measured memory_bytes: 70784
#include <iostream>
#include <vector>
#include <functional>
#include <cstring>

using namespace std;

int main(){
    int N, M, Q;
    int a[55], b[55], c[55], d[55];
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(c, 0, sizeof(c));
    memset(d, 0, sizeof(d));

    cin >> N >> M >> Q;
    for(int i=0; i<Q; ++i){
        cin >> a[i];
        cin >> b[i];
        cin >> c[i];
        cin >> d[i];
        a[i]--;
        b[i]--;
    }

    vector<int> A;
    for(int i=0; i<M-1; ++i) A.push_back(0);
    for(int i=0; i<N; ++i) A.push_back(1);


    int point = 0;
    do{
        int cnt =1;
        vector<int> retu;
        
        // convert A into the retu
        for(int i=0; i<A.size(); ++i){
            if(A[i] == 1){
                if(cnt == 0) cnt++;
                retu.push_back(cnt);
            }else{
                cnt++;
            }
        }
        
        int tmp_point =0;
        //apply the pint of the retu
        for(int i=0; i<Q; ++i){
            if(retu[b[i]] - retu[a[i]] == c[i]){
                tmp_point += d[i];
            } 
        }

        point = max(point, tmp_point);

    }while(next_permutation(A.begin(), A.end()));

    cout << point << endl;

}

Measured memory_bytes: 3612
import sys


def solv(boad):
    boad = map(lambda x: [0] + x + [0], boad)
    boad.insert(0, [0] * 14)
    boad.append([0] * 14)
    n = sum([foo(boad, x, y) for x in xrange(1, 13) for y in xrange(1, 13)])
    return n


def foo(b, x, y):
    if b[y][x]:
        b[y][x] = 0
        foo(b, x-1, y)
        foo(b, x+1, y)
        foo(b, x, y-1)
        foo(b, x, y+1)
        return 1
    else:
        return 0



boads = []
b = []
for line in sys.stdin:
    line = line.rstrip()
    if line == '':
        boads.append(b)
        b = []
        continue
    b.append(map(int, line))
boads.append(b)
for boad in boads:
    print solv(boad)

Measured memory_bytes: 4320
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
//V,P(大文字)使用不可

const ll INF=1000000000000000000;

signed main(){
    int n;
    cin>>n;
    set<char> st;
    rep(i,n){
        char c;
        cin>>c;
        st.insert(c);
    }// st.insert(s[i]);
    if(st.size()==3) cout<<"Three"<<endl;
    else cout<<"Four"<<endl;
}

Measured memory_bytes: 256
S = input()

isEasy = True
for i, v in enumerate(S):
  if ((i + 1) % 2 == 0 and (v == 'L' or v == 'U' or v == 'D')):
    continue
  elif ((i + 1) % 2 == 1 and (v == 'R' or v == 'U' or v == 'D')):
    continue
  else:
    isEasy = False
    break
  
if isEasy:
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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


int main()
{
int n,i;
cin>>n>>i;
cout<<n-i+1<<endl;
}

Measured memory_bytes: 256
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

move = ((1, 0), (-1, 0), (0, 1), (0, -1))


def bfs(i, j):
    if S[i][j] == '#':
        return 0

    visited = [[False] * W for _ in range(H)]
    visited[i][j] = True
    que = deque([(i, j, 0)])

    while que:
        ci, cj, d = que.popleft()

        for di, dj in move:
            ni, nj = ci + di, cj + dj
            if not (0 <= ni < H and 0 <= nj < W) or visited[ni][nj]:
                continue
            if S[ni][nj] == '.':
                visited[ni][nj] = True
                que.append((ni, nj, d+1))

    return d


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, bfs(i, j))
print(ans)


Measured memory_bytes: 44268
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
using namespace std;
typedef pair<int, int> P;

struct Era{
    string name;
    int s, t;
};

signed main(){
    int n, q;
    while(1){
        cin >> n >> q;
        if(n + q == 0) break;
        vector<Era> d(n);
        rep(i, 0, n){
            string s;
            int a, b;
            cin >> s >> a >> b;
            d[i].name = s;
            d[i].s = b - a + 1;
            d[i].t = b;
        }
        rep(j, 0, q){
            int y;
            cin >> y;
            string era = "";
            int ans = -1;
            rep(i, 0 ,n){
                if(d[i].s <= y && y <= d[i].t){
                    era = d[i].name;
                    ans = y - d[i].s + 1;
                    break;
                }
            }
            if(ans == -1){
                cout << "Unknown" << endl;
            }else{
                cout << era << " " << ans << endl;
            }
        }
    }
}

Measured memory_bytes: 1284
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<long long>;
using vvi = vector<vector<int>>;
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 (b<a) {a=b; return 1;} return 0;}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    reverse(s.begin(), s.end());
    vs t = {"dream", "dreamer", "erase", "eraser"};
    rep(i, 4) reverse(t[i].begin(), t[i].end());
    bool ans = true;
    while (s.size()) {
        bool flag = false;
        rep(i, 4) {
            if (t[i] == s.substr(0, t[i].size())) {
                s.erase(0, t[i].size());
                flag = true;
                break;
            }
        }
        if (!flag) {
            ans = false;
            break;
        }
    }
    if (ans) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 512
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	P := map[int]int{}
	P[readInt()] = 1
	P[readInt()] = 1
	Loop(1, 4, func(i int) {
		if _, Exists := P[i]; !Exists {
			fmt.Println(i)
			os.Exit(0)
		}
	})
}

/////////////////////////////////////////
var scanner = bufio.NewScanner(os.Stdin)

func init() {
	//scanner.Split(bufio.ScanWords)
	scanner.Split(bufio.ScanLines)
}

func readString() string {
	scanner.Scan()
	return scanner.Text()
}

func readInt() int {
	scanner.Scan()
	t, _ := strconv.Atoi(scanner.Text())
	return t
}

func Loop(start, end int, f func(i int)) {
	for i := start; i < end; i++ {
		f(i)
	}
}

Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    char s[10005];
    scanf("%s",s);
    int n=strlen(s);
    int flag=1;
    for(int i=0;i<n/2;i++)
        if(s[i]!=s[n-1-i])
        flag=0;
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    return 0;
}


Measured memory_bytes: 256