akhauriyash/Code-Regression huggingface dataset:
#include "bits/stdc++.h"
using namespace std;
const int N = 1e5 + 5;
using ll = long long int;

int main(){
    ll a, b, c, k;
    cin >> a >> b >> c >> k;
    ll ans = 0;
    ans += min(a, k);
    k -= ans;
    ans += 0 * min(b, k);
    k -= min(b, k);
    ans += -1 * min(c, k);
    cout << ans;
    return 0;
}

Measured memory_bytes: 3636
/**
 * @Author:      H S-J
 * @DateTime:    2017-12-22 21:16:07
 * @Description: 
 */
#include <bits/stdc++.h>
using namespace std;
#define MST(a, b) memset(a, b, sizeof(a));
#define CLR(a) MST(a, 0);
#define DBG(x) cout << '#' << " = " << (x) << endl;
#define ALL(x) x.begin(), x.end()
#define INS(x) inserter(x, x.begin())
#define lson(x) (x) << 1
#define rson(x) (x) << 1|1
#define pb push_back
#define rep(x, y, z) for (int x = y; x < z; ++x)
#define ech(x, y, z) for (auto x = z.begin(), y = z.end(); x != y; ++x)
#define lowbit(x) (x & (-x))
#define opr operator
#define _st first
#define _nd second
#define prior_q1(x) priority_queue<x>
#define prior_q2(x) priority_queue<x, vector<x>, greater<x> >
typedef long long LL;
typedef stringstream strstm;
struct FastIO {
    static const int S = 1310720;
    int wpos;
    char wbuf[S];
    FastIO() : wpos(0) {}
    inline int xchar() {
        static char buf[S];
        static int len = 0, pos = 0;
        if (pos == len)
            pos = 0, len = fread(buf, 1, S, stdin);
        if (pos == len) return -1;
        return buf[pos ++];
    }
    inline int xuint() {
        int c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x;
    }
    inline int xint() {
        int s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline LL xlongint() {
        LL s = 1, c = xchar(), x = 0;
        while (c <= 32) c = xchar();
        if (c == '-') s = -1, c = xchar();
        for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0';
        return x * s;
    }
    inline void xstring(char *s) {
        int c = xchar();
        while (c <= 32) c = xchar();
        for (; c> 32; c = xchar()) * s++ = c;
        *s = 0;
    }
    inline void wchar(int x) {
        if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0;
        wbuf[wpos ++] = x;
    }
    inline void wint(LL x) {
        if (x < 0) wchar('-'), x = -x;
        char s[24];
        int n = 0;
        while (x || !n) s[n ++] = '0' + x % 10, x /= 10;
        while (n--) wchar(s[n]);
    }
    inline void wstring(const char *s) {
        while (*s) wchar(*s++);
    }
    ~FastIO() {
        if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0;
    }
} io;
int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(0);cin.tie(0);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a += b; c += d;
	if(a == c) cout << "Balanced" << endl;
	else if(a < c)  cout << "Right" << endl;
	else 	   cout << "Left" << endl;
	return 0;
}

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

int main() {
  string s, t;
  cin >> s >> t;
  sort(s.begin(), s.end());
  sort(t.begin(), t.end());
  reverse(t.begin(), t.end());
  //cout << s << endl;
  
  string ans="humei";
  for (int i=0; i<min(s.size(), t.size()); i++) {
    if (s[i]<t[i]) {
      ans = "Yes";
      break;
    }
    else if (s[i]==t[i]) {
      continue;
    }
    else {
      ans = "No";
      break;
    }
  }
  if (ans=="humei") {
    if (s.size()<t.size()) {
      ans = "Yes";
    }
    else {
      ans = "No";
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3604
if __name__ == '__main__':
    n = int(input())
    a = list(map(int, input().split()))

    # n = 5
    # a = [6, 9, 4, 2, 11]

    max_a = max(a)
    max_half = max_a / 2

    best_a_j = a[0] if a[0] != max_a else a[1]
    min_d = max_half
    for a_j in a:
        if a_j == max_a:
            continue

        d = abs(a_j - max_half)
        if d < min_d:
            best_a_j = a_j
            min_d = d

    print(max_a, best_a_j)


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

int main() {
    int N;
    cin >> N;
    vector<int> A(N),B(N),C(N-1);
    for(int i=0;i<N;i++){
        cin >> A.at(i);
    }    
    for(int i=0;i<N;i++){
        cin >> B.at(i);
    }
    for(int i=0;i<N-1;i++){
        cin >> C.at(i);
    }
    int sum=0;
    for(int i=0;i<N;i++){
        sum+=B.at(i);
    }
    for(int i=0;i<N-1;i++){
        if(A.at(i)==A.at(i+1)-1) sum+=C.at(A.at(i)-1);
    }
    cout << sum << endl;
}


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


int main(){
    int n; cin >> n;
    v a(n);
    
    rep(i,n)cin>>a[i];
    map<ll,v> l,r;
    
    rep(i,n){
        l[a[i]+i].push_back(i);
        r[i-a[i]].push_back(i);
    }
    
    ll ans = 0;
    
    for(auto p: l){//pair<ll, v>
        ll i = p.first;
        v vj = p.second;
        if(!r.count(i))continue;
        for(auto j: vj){//ll
            ll len = r[i].end() - upper_bound(r[i].begin(), r[i].end(), i);
            ans += len;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 45236
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let n = read::<usize>();
    let v = read_vec::<usize>()
        .into_iter()
        .map(|x| x)
        .collect::<Vec<_>>();
    let mut poses = vec![vec![]; n + 1];
    for i in 0..n {
        poses[v[i]].push(i);
    }
    let mut res = 0;
    let mut cur = 0;
    for i in 1..n + 1 {
        let idx = poses[i].lower_bound(&cur);
        if idx == poses[i].len() {
            break;
        }
        cur = poses[i][idx];
        res += 1;
    }
    if res == 0 {
        println!("-1");
        return;
    } else {
        println!("{}", n - res);
    }
}

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

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

use std::cmp::Ordering;

pub trait BinarySearch<T> {
    fn lower_bound(&self, x: &T) -> usize;
    fn upper_bound(&self, x: &T) -> usize;
}

impl<T: Ord> BinarySearch<T> for [T] {
    fn lower_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less => {
                    low = mid + 1;
                }
                Ordering::Equal | Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }

    fn upper_bound(&self, x: &T) -> usize {
        let mut low = 0;
        let mut high = self.len();

        while low != high {
            let mid = (low + high) / 2;
            match self[mid].cmp(x) {
                Ordering::Less | Ordering::Equal => {
                    low = mid + 1;
                }
                Ordering::Greater => {
                    high = mid;
                }
            }
        }
        low
    }
}


Measured memory_bytes: 18664
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int main(int argc,char const* argv[]){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin>>n;
	vector<vector<int> > dp(n,vector<int>(3,0));
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++){
			cin>>dp[i][j];
		}
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			if(j == 0){
				dp[i][j] += max(dp[i-1][1],dp[i-1][2]);
			}
			else if(j == 1){
				dp[i][1] += max(dp[i-1][0],dp[i-1][2]);
			}
			else{
				dp[i][2] += max(dp[i-1][0],dp[i-1][1]);
			}
		}
	}
	int ans = 0;
	for(int i=0;i<3;i++){
		ans = max(ans,dp[n-1][i]);
	}
	cout<<ans<<"\n";
	return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
double prob[3005];
double dp[3005][3005];
int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> prob[i];
    dp[1][0] = 1 - prob[1];
    dp[1][1] = prob[1];
    for(int i = 2; i <= n; i++)
        for(int k = 0; k <= i; k++){
            dp[i][k] = dp[i-1][k]*(1 - prob[i]);
            if(k > 0)
                dp[i][k] += dp[i-1][k-1]*prob[i];
        }
    double res = 0;
    for(int j = n/2 + 1; j <= n; j++)
        res += dp[n][j];
    cout.setf(ios::fixed);
    cout.precision(10);
    cout << res << '\n';
    return 0;
}


Measured memory_bytes: 68992
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define lli long long int
#define ulli unsigned long long int
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define loopl(i,a,b) for(lli i=a;i<b;i++) 
#define loop(i,a,b) for(int i=a;i<b;i++)
#define all(v) v.begin(), v.end()
#define mod 1000000007
#define mod2 1000000006
#define inf 1000000000000000000
#define lld long double
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<lli>
#define vii vector<int>
#define is indexed_set
#define eps 0.000001
#define endl '\n'
#define mo 998244353
#define pi 3.141592653589793
#define FF first
#define SS second
using namespace std ;
 
const lli dx4[] = {-1, 0, 1, 0};
const lli dy4[] = {0, 1, 0, -1};
const lli dx8[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const lli dy8[] = {0, 1, 0, -1, -1, 1, -1, 1};
 
typedef tree<pll,null_type,less<pll>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); // can give negative values too

#define N 100001

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

    lli a[n],b[n];

    loopl(i,0,n) cin>>a[i];
    loopl(i,0,n) cin>>b[i];

    lli ans=0;
    loopl(j,0,n)
    {
        lli cnt=0;
        loopl(i,0,j+1) cnt+=a[i];
        loopl(i,j,n) cnt+=b[i];

        ans = max(ans , cnt);
    }

    cout<<ans<<endl;
}   

int main()
{
////////////////////////////////////////////   
    fastio;
////////////////////////////////////////////
    
    lli t;
    t=1;
    while(t--)
    {
        solve();
    }
}


Measured memory_bytes: 3540
[<AutoOpen>]
module Program

open System

let read f = stdin.ReadLine() |> f
let reads f = stdin.ReadLine().Split() |> Array.toList |> List.map f

[<EntryPoint>]
let main argv =
    let [n;_;c] = reads int
    let bs = reads int
    let ass = List.map (fun _ -> reads int) [1..n]
    seq {
        for xs in ass do
            let ab = List.map2 (*) bs xs |> List.sum
            if ab + c > 0 then yield ()
    }
    |> Seq.length
    |> printfn "%i"
    0

Measured memory_bytes: 12252
#include <random>
#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld eps = 1e-12;
constexpr int inf = numeric_limits<int>::max() / 2;
constexpr ll mod = 1e9 + 7;
mt19937_64 rnd{random_device()()};

template <typename T>
void printv(const vector<T> &v) {
  int sz = v.size();
  for (int i = 0; i < sz; i++) {
    cout << v[i] << " \n"[i == sz - 1];
  }
}

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

  string s;cin>>s;
  cout << s.substr(0, 3) << endl;
}



Measured memory_bytes: 3664
#include <iostream>

using namespace std;
const int MaxR = 11;
const int MaxC = 10001;
int pan[MaxR][MaxC];
int res;
int ans;
int R;
int C;

void dfs(int k){
    if (k == R){
        res = 0;
        for(int i = 0; i < C; i++){
            int sum = 0;
            for(int j = 0; j < R; j++){
                if(pan[j][i]) sum++;
            }
            res += max(sum, R - sum);
        }
        ans = max(res, ans);
        return;
    }
    dfs(k + 1);
    for(int i = 0; i < C; i++){
        pan[k][i] = 1 - pan[k][i];
    }
    dfs(k + 1);
}

void solve(){
    ans = 0;
    for(int i = 0; i < R; i++){
        for(int j = 0; j < C; j++){
            cin >> pan[i][j];
        }
    }
    dfs(0);
}

int main(){
    ios_base::sync_with_stdio(false);
    while(cin >> R >> C && R > 0 && C > 0){
        solve();
        cout << ans << endl;
    }
    return 0;
}



Measured memory_bytes: 3508
d,n=map(int,input().split())
if n!=100:

    if d==0:
        print(n)
    elif d==1:
        print(n*100)
    elif d==2:
        print(n*10000)

else:
    if d==0:
        print(101)
    elif d==1:
        print(10100)   
    elif d==2:
        print(1010000)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
void go(string s){
	int k=0;	
    if(s.size()%2==1){
		cout<<"No"<<endl;
		return;
	} 
	else{
		for(int i=0;i<s.size()/2;i++){
			if(s[i]==s[i+(s.size()/2)]){
				k++;
			}
		}
	}
	if(k==s.size()/2){
		cout<<"Yes"<<endl;
		return;
	}
	else{
		cout<<"No"<<endl;
		return;
	}
}	
int main(){
	int n;
	cin>>n;
	string s;
	cin>>s;

    go(s); 
	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>

using namespace std;

struct Node {
    string key = "";
    Node *left = nullptr;
    Node *right =nullptr;
};

void insert(Node *newnode, Node *ptr){
    if(newnode->key.compare(ptr->key) <= 0){
        if(ptr->left == nullptr){
            ptr->left = newnode;
        }else {
            insert(newnode, ptr->left);
        }
    }
    else{
        if(ptr->right == nullptr){
            ptr->right = newnode;
        }else{
            insert(newnode, ptr->right);
        }
    }

}

string combine(Node *ptr){
    string str;
    if(ptr != nullptr)
        str = combine(ptr->left) + ptr->key + combine(ptr->right);
    return str;
}

int main(){
    int L,N;
    string str;
    cin >> N >> L;

    Node *root = new Node;
    cin >> str;
    root->key = str;

    for(int i=1; i<N; i++) {
        cin >> str;
        Node *newnode = new Node;
        newnode->key = str;
        insert(newnode, root);
    }

    string ret = combine(root);
    cout << ret << endl;
    return 0;
}

Measured memory_bytes: 256
function Main(input) {
    input = input.trim().split("\n").map(function(x) { return x.split(" ")});

    const lowerBound = (arr, n) => {
        let first = 0, last = arr.length - 1, middle;
        while (first <= last) {
            middle = Math.floor((first + last) / 2);
            if (arr[middle] < n) first = middle + 1;
            else last = middle - 1;
        }
        return first;
    }


    let n = parseInt(input[0][0], 10);
    let v_a = [];
    for (let i = 0; i < n; i++){
        v_a.push(parseInt(input[i + 1][0], 10));
    }
    let dp = Array.from({length: n}, () => Infinity);

    dp[0] = v_a[0];
    let index;
    for (let i = 1; i < n; i++){
        index = lowerBound(dp, v_a[i]);
        dp[index] = v_a[i];
    }

    console.log(lowerBound(dp,1e9+1));

}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));



Measured memory_bytes: 41312
using System;
using System.Collections.Generic;
using System.Linq;

namespace MyProgram{
    class AtCoder{
        static void Main(){
            long N = long.Parse(Console.ReadLine());
            long[] A = Array.ConvertAll(Console.ReadLine().Split(' '),long.Parse);
            for(var i=0;i<N;i++){
                A[i] -= i+1;
            }
            Array.Sort(A);
            double med;
            if(N%2 == 0){
                med = (A[N/2]+A[N/2-1])/2;
            }else{
                med = A[(N-1)/2];
            }
            double sum=0;
            for(var i=0;i<N;i++){
                sum += Math.Abs(A[i] - (med));
            }
            Console.WriteLine(sum);

        }
    } 
}

Measured memory_bytes: 30684
n,k=map(int,input().split())
s=input()
slist=list(s)
num=0
for i in range(17):
    if 2**num>=n:
        num+=1
        break
    num+=1
if k>=num:
    slist.sort()
    ans=slist[0]*n
    print(ans)
else:
    for i in range(n):
        slist.append(slist[n-1-i])
    s1=[]
    for i in range(n+1):
        s1.append(slist[i:i+n])
    s1.sort()
    sstr=s1[0]
    ss2=""
    for i in range(n):
        ss2+=sstr[i]
    s3=sstr[0]
    num10=1
    for i in range(n-1):
        if s3!=sstr[i+1]:
            break
        else:
            num10+=1
    s2=""
    for i in range(n):
        s2+=sstr[-1-i]
    slist.sort()
    num=min((2**(k-1))*num10,n)
    num2=n-num
    ans=slist[0]*num
    ans+=ss2[num10:num10+num2]
    print(ans)


Measured memory_bytes: 203748
n = [0] + list(map(int, list(input())))
ans = 0
c_in = 0

while n:
    s = n.pop()
    s += c_in
    if 0 <= s <= 4:
        ans += s
        c_in = 0
    elif 6 <= s:
        ans += abs(10 - s)
        c_in = 1
    else:
        ans += 5
        if 5 <= n[-1]:
            c_in = 1
        else:
            c_in = 0

print(ans)


Measured memory_bytes: 21228
#include <bits/stdc++.h>
using namespace std;
 
struct edge {int /*from,*/to,cost;};
typedef long long ll;
typedef pair<int,int> P;
typedef pair<pair<int,int>,int> PP;
typedef vector<int> VI;
typedef vector<long long int> VL;
typedef vector<edge> VE;
//static const int INF = 2147483647;
//static const long long INF = 9223372000000000000;
//static const long long INF = 9223372000000000000/2;
//static const long long INF = 9223372000000000000/2145;
//static const int INF = 1000010000;
//static const int NIL = -1;
//static const int MOD = 1000000007;
//int dx4[4] = {0,1,0,-1}, dy4[4] = {-1,0,1,0};
//int dx5[5] = {-1,0,0,0,1}, dy5[5] = {0,-1,0,1,0};
//int dx8[8] = {-1,0,1,1,1,0,-1,-1}, dy8[8] = {1,1,1,0,-1,-1,-1,0};
//int dx9[9] = {-1,0,1,1,1,0,-1,-1,0}, dy9[9] = {1,1,1,0,-1,-1,-1,0,0};
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define np next_permutation
#define pq priority_queue
//#define int ll

string s;

bool hantei(int n){
    for(int i=0;i<n/2;i++){
        if(s[i]!=s[i+n/2]) return false;
    }
    return true;
}

signed main(){
    cin>>s;
    for(int i=s.length()-2;i>0;i-=2){
        if(hantei(i)){
            printf("%d\n",i);
            break;
        }
    }

    return 0;
}

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

int main() {
  string S;
  cin >> S;
  
  for (int i = 0; i < S.size(); i++) {
    if(i == S.size() - 1) {
      cout << "x" << endl;
    }
    else {
      cout << "x";
    }
  }
}


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

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;

int main() {
  string S; cin >> S;
  int K; cin >> K;
  int L = S.size();
  // dp[i : 決めた桁数][j : 未満フラグ][k : 0 でない個数]
  vvvl dp(110, vvl(2, vl(110, 0)));
  dp.at(0).at(0).at(0) = 1;
  for (int i = 0; i < L; i++) {
    int D = S.at(i) - '0';
    for (int j = 0; j < 2; j++) {
      for (int k = 0; k < 101; k++) {
        for (int d = 0; d <= (j ? 9 : D); d++) {
          if (d == 0) dp.at(i+1).at(j || (d < D)).at(k) += dp.at(i).at(j).at(k);
          else dp.at(i+1).at(j || (d < D)).at(k+1) += dp.at(i).at(j).at(k);
        }
      }
    }
  }
  cout << dp.at(L).at(0).at(K) + dp.at(L).at(1).at(K) << endl;
}

Measured memory_bytes: 512
n, m = map(int, input().split())
childs = list(map(int, input().split()))
if(m > sum(childs)):
    print(len(childs)-1)
else:
    count = 0
    childs.sort()
    for child in childs:
        if m >= child:
            m -= child
            count += 1
    print(count)

Measured memory_bytes: 3060
#include <stdio.h>
 
int gcd(int x, int y);
 
int main(void)
{
    int x, y;
     
    scanf("%d %d", &x, &y);
    printf("%d\n", gcd(x, y));
     
    return (0);
}
 
int gcd(int x, int y)
{
    if (y == 0){
        return (x);
    }
    else {
        return (gcd(y, x % y));
    }
}

Measured memory_bytes: 592
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<cstdlib>
#include<bitset>
#include<utility>
#include<sstream>
#include<iomanip>
using namespace std;

#define ll long long
#define MP make_pair

int main(void) {
    int n;

    while(1){
        cin>>n;
        int s[100]={};
        double sum=0.0;
        if(n==0)break;

        for (int i = 0; i < n; i++) {
            cin>>s[i];
        }
        
        sort(s,s+n);
        for (int si = 1; si < n-1; si++) {
            sum+=double(s[si]);
        }
        
        double ave = sum/(double)(n-2);
        cout<<int(ave)<<"\n";

    }
    
    return 0;
}


Measured memory_bytes: 3168
#include <stdio.h>

#define N 50
#define X 50

int main() {
	static long long dp[N + 1][N * X + 1];
	int n, a, h, i, j;
	long long cnt;

	scanf("%d%d", &n, &a);
	dp[0][0] = 1;
	for (h = 1; h <= n; h++) {
		int x;

		scanf("%d", &x);
		for (i = h; i > 0; i--)
			for (j = x; j <= i * X; j++)
				dp[i][j] += dp[i - 1][j - x];
	}
	cnt = 0;
	for (i = 1; i <= n; i++)
		cnt += dp[i][i * a];
	printf("%lld\n", cnt);
	return 0;
}


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

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pair<int,int>>
#define vpll vector<pair<ll,ll>>
#define fr(i,k,n) for (int i = k; i < n; ++i)
#define fri(i,k,n) for (int i = k; i >= n; --i)
#define INF (int)1e9
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define all(arr) arr.begin(),arr.end()

void boost(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

void solve(){
	int n;
	cin>>n;
	string s;
	cin>>s;
	int cnt=0;
	int l=0,r=n-1;
	while(l<r){
		if(s[l]=='W' && s[r]=='R'){
			cnt++;
			l++;
			r--;
		}
		else if(s[l]=='W'){
			r--;
		}
		else if(s[l]=='R'){
			l++;
		}
	}
	cout<<cnt<<endl;
	return;
}

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

Measured memory_bytes: 3760
#include <bits/stdc++.h>
#define LARB 1
#define RARB 30000
#define inf 1e18
#define zeros(x) ((x^(x-1))&x)
#define endl '\n'
#define eps 1e-9
#define mod 1000000007
#define NMAX 300

using namespace std;

typedef long long ll;
typedef long double ld;

ll n, Ans[205];
vector<ll> V;

ll ask()
{
    string ans;
    cout<<"? ";
    for (auto i : V)
        cout<<i<<" ";
    cout<<'\n';
    cout.flush();
    cin>>ans;
    if (ans == "-1")
        assert(false);
    return ans == "Blue";
}

ll askllerval(ll l, ll r, ll x)
{
    if (r>2*n)
        r-=2*n;

    V.clear();
    if (r<l)
    {
        for (ll i = l; i <= 2*n; i++)
            V.push_back(i);
        for (ll i = 1; i <= r; i++)
            V.push_back(i);
    }
    else
    {
        for (ll i = l; i <= r; i++)
            V.push_back(i);
    }
    if (x!=-1)
        V.push_back(x);
    ll ans = ask();
    return ans;
}

void prllAns()
{
    cout<<"! ";
    for (ll i=1; i<=2*n; i++)
    {
        if (Ans[i] == -1)
            assert(false);

        if (Ans[i] == 0)
            cout<<"R";
        else
            cout<<"B";
    }
    cout.flush();
    exit(0);
}

void askOutOf(ll l, ll r)
{
    if (l<=r)
    {
        for (ll i=1; i<=2*n; i++)
        {
            if (!(l<=i && i<=r) && Ans[i] == -1)
            {
                ll ans = askllerval(l, r, i);
                Ans[i] = ans;
            }
        }
    }
    else
    {
        for (ll i=1; i<=2*n; i++)
        {
            if (r < i && i < l && Ans[i] == -1)
            {
                ll ans = askllerval(l, r, i);
                Ans[i] = ans;
            }
        }
    }

}

void askFinish(ll x)
{
    ll l = x;
    ll r = x+n-2;
    askOutOf(l, r);

    l = r+2;
    r = l+n-2;
    askOutOf(l, r);

    prllAns();
}

int main()
{
    //freopen("input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;

    for (ll i=1; i<=2*n; i++)
        Ans[i] = -1;

    if (n==1)
    {
        V.push_back(1);
        Ans[1] = ask();
        V.clear();
        V.push_back(2);
        Ans[2] = ask();
        prllAns();
        return 0;
    }

    ll last = -1;
    int init = askllerval(1, n, -1);
    int st = 2, dr = n+1;
    while (st<=dr)
    {
        ll mijl = (st+dr)/2;
        ll here = askllerval(mijl, mijl+n-1, -1);
        if (here != init)
            dr = mijl-1;
        else
            st = mijl+1;
    }
    if (dr>=2 && askllerval(dr, dr+n-1, -1) != init)
        askFinish(dr);
    else
        askFinish(st);
    assert(false);
    return 0;
}

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


int main(){
    int n, k;
    cin >> n >> k;
    double ans = 0.0;
    for(int i = 1; i <= n; i++){
        int x = i;
        double p = 1.0;
        while(x < k){
            p *= 0.5;
            x *= 2;
        }
        ans += p / n;
    }
    cout << setprecision(12) << ans << endl;
}


Measured memory_bytes: 256
#include <stdio.h>
#include<math.h>
#include <algorithm>
using namespace std;

int main(){
	char buf[10];
	bool FLG;

	while(scanf("%s",buf)!=EOF){
		FLG = true;
		for(int i=0;i<=6;i+=3){
			if((buf[i] == 'o' || buf[i] == 'x') && buf[i] == buf[i+1] && buf[i+1] == buf[i+2]){
				printf("%c\n",buf[i]);
				FLG = false;
				break;
			}
		}

		if(FLG){
			for(int i = 0; i <=2; i++){
				if((buf[i] == 'o' || buf[i] == 'x') && buf[i] == buf[i+3] && buf[i] == buf[i+6]){
					printf("%c\n",buf[i]);
					FLG = false;
					break;
				}
			}
		}

		if(FLG){
			if((buf[0] == 'o' || buf[0] == 'x') && buf[0] == buf[4] && buf[4] == buf[8]){
				printf("%c\n",buf[0]);
				FLG = false;
			}
		}

		if(FLG){
			if((buf[2] == 'o' || buf[2] == 'x')  && buf[2] == buf[4] && buf[4] == buf[6]){
				printf("%c\n",buf[2]);
				FLG = false;
			}
		}

		if(FLG)printf("d\n");

	}

    return 0;
}



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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

class mint {
public:
    long long x;

    constexpr mint(long long x = 0) : x((x % MOD + MOD) % MOD) {}

    constexpr mint operator-() const {
        return mint(-x);
    }

    constexpr mint &operator+=(const mint &a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }

    constexpr mint &operator-=(const mint &a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }

    constexpr mint &operator*=(const mint &a) {
        (x *= a.x) %= MOD;
        return *this;
    }

    constexpr mint operator+(const mint &a) const {
        mint res(*this);
        return res += a;
    }

    constexpr mint operator-(const mint &a) const {
        mint res(*this);
        return res -= a;
    }

    constexpr mint operator*(const mint &a) const {
        mint res(*this);
        return res *= a;
    }

    [[nodiscard]] constexpr mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    [[nodiscard]] constexpr mint inv() const {
        return pow(MOD - 2);
    }

    mint &operator/=(mint a) {
        return *this *= a.inv();
    }

    mint operator/(const mint a) const {
        return mint(*this) /= a;
    }

    constexpr bool operator==(const mint &a) const noexcept {
        return this->x == a.x;
    }

    constexpr bool operator!=(const mint &a) const noexcept {
        return this->x != a.x;
    }

    friend istream &operator>>(istream &is, mint &a) {
        is >> a.x;
        return is;
    }

    friend ostream &operator<<(ostream &os, const mint &a) {
        return os << a.x;
    }
};

void Main() {
    ll N;
    cin >> N;
    vector<mint> C(N);
    rep(i, N) cin >> C[i];
    vector<mint> dp(N + 1, 0);
    dp[0] = 1;
    map<ll, ll> pos;
    rep(i, N) {
        pos[C[i].x] = -1;
    }
    rep(i, N) {
        mint c = C[i];
        if (pos[c.x] != -1 && i > pos[c.x] + 1) {
            dp[i + 1] += dp[pos[c.x] + 1];
        }
        dp[i + 1] += dp[i];
        pos[c.x] = i;
    }
    cout << dp[N] << '\n';
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 15872
/*input
0 3
*/
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define watch(x) cout << (#x) << " is " << (x) << endl
#define debug cout << "hi" << endl

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

const int MOD = 1e9 + 7;
const int INF32 = 1<<30;
const ll INF64 = 1LL<<60;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m; cin >> n >> m;
    cout << (n * (n - 1))/2 + (m * (m - 1))/2;

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
		double l[7][2];
		l[0][0]=35.5;l[0][1]=71;l[1][0]=37.5;l[1][1]=77;
		l[2][0]=40;l[2][1]=83;l[3][0]=43;l[3][1]=89;
		l[4][0]=50;l[4][1]=105;l[5][0]=55;l[5][1]=116;
		l[6][0]=70;l[6][1]=148;
		string c[7];
		c[0]="AAA";c[1]="AA";c[2]="A";c[3]="B";c[4]="C";c[5]="D";c[6]="E";
		double a,b;
		while(cin>>a>>b){
			string d;
			for(int i=0;i<7;i++){
				if(a<l[i][0]&&b<l[i][1]){
					d=c[i];
					goto stop;
				}
			}
			d="NA";
			stop:;
			cout<<d<<endl;
		}
	}

Measured memory_bytes: 3068
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <queue>
#include <stack>
#include <cstdlib>
#include <map>
#include <iomanip>
#include <set>
#include <stdio.h>
#include <ctype.h>
#include <random>
#include <string.h>
#include <cmath>
#include <unordered_map>
#include <cstdio>
using namespace std;
#define pie 3.141592653589793238462643383279
#define mod 1000000007
#define int long long
#define P pair<int,int>
#define all(vec) vec.begin(),vec.end()

int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x%y);
}
int lcm(int x, int y) {
	return x / gcd(x, y)*y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}

int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}

const int INF = 1000000000000000000;

int n, m, a[1010], b[1010], c[1010], d[1010], e[1010], f[1010];
vector<int> vecx, vecy;
bool bl[3010][3010], bl2[3010][3010][4];
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int ans;

signed main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i] >> c[i];
		vecx.push_back(a[i]);
		vecx.push_back(b[i]);
		vecy.push_back(c[i]);
	}
	for (int i = 0; i < m; i++) {
		cin >> d[i] >> e[i] >> f[i];
		vecx.push_back(d[i]);
		vecy.push_back(e[i]);
		vecy.push_back(f[i]);
	}
	vecx.push_back(0); vecx.push_back(-INF); vecx.push_back(INF);
	vecy.push_back(0); vecy.push_back(-INF); vecy.push_back(INF);
	sort(all(vecx));
	sort(all(vecy));
	vecx.erase(unique(all(vecx)), vecx.end());
	vecy.erase(unique(all(vecy)), vecy.end());
	//for (int i = 0; i < (int)vecx.size(); i++)cout << vecx[i] << endl;
	for (int i = 0; i < n; i++) {
		a[i] = lower_bound(all(vecx), a[i]) - vecx.begin();
		b[i] = lower_bound(all(vecx), b[i]) - vecx.begin();
		c[i] = lower_bound(all(vecy), c[i]) - vecy.begin();
		for (int j = a[i]; j < b[i]; j++) {
			bl2[j][c[i]][3] = true;
			bl2[j][c[i] - 1][1] = true;
		}
	}
	for (int i = 0; i < m; i++) {
		d[i] = lower_bound(all(vecx), d[i]) - vecx.begin();
		e[i] = lower_bound(all(vecy), e[i]) - vecy.begin();
		f[i] = lower_bound(all(vecy), f[i]) - vecy.begin();
		for (int j = e[i]; j < f[i]; j++) {
			bl2[d[i]][j][2] = true;
			bl2[d[i] - 1][j][0] = true;
		}
	}
	int xx = lower_bound(all(vecx), 0) - vecx.begin();
	int yy = lower_bound(all(vecy), 0) - vecy.begin();
	queue<P> que;
	bl[xx][yy] = true;
	que.push(make_pair(xx, yy));
	while (!que.empty()) {
		int x = que.front().first, y = que.front().second; que.pop();
		ans += (vecx[x + 1] - vecx[x])*(vecy[y + 1] - vecy[y]);
		for (int i = 0; i < 4; i++) {
			if (bl2[x][y][i])continue;
			int tx = x + dx[i], ty = y + dy[i];
			if (bl[tx][ty])continue;
			if (tx == 0 || tx == (int)vecx.size() || ty == 0 || ty == (int)vecy.size()) {
				cout << "INF" << endl;
				return 0;
			}
			bl[tx][ty] = true;
			que.push(make_pair(tx, ty));
		}
	}
	cout << ans << endl;
}


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

def calc_ex(x):
    return  x/2 + 0.5
p_ = list(map(calc_ex,p_))

res = sum(p_[:k])
cnt = sum(p_[:k])
for i in range(1,n-k+1):
    cnt = cnt - p_[i-1] + p_[i+k-1]
    res = max(res,cnt)
print(res)


Measured memory_bytes: 24804
n = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(n[int(input())-1])

Measured memory_bytes: 3060
import java.util.*;

public class Main {

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

    if (a + b >= c) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }

}


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

int main(){
  int x;
  cin >> x;
  int ans = 1;
  for(int i = 2; i < x; ++i){
    int cur = i * i;
    while(cur <= x){
      if(cur > ans){
        ans = cur;
      }
      cur *= i;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[][] rec = new int[N][];
        int[] a = new int[N];
        int[] b = new int[N];
        for(int i=0;i<N;i++){
            a[i]=sc.nextInt();
            b[i]=sc.nextInt();
        }
        for(int i=0;i<N;i++){
            int x = a[i];
            int y = b[i];
            rec[i] = new int[]{i,x,y};
        }
        ArrayList<Edge>[] map = new ArrayList[N];
        for(int i=0;i<N;i++) map[i]=new ArrayList<>();
        Arrays.sort(rec, new myComX());
        for(int i=0;i<N-1;i++){
            int dist = rec[i+1][1]-rec[i][1];
            map[rec[i][0]].add(new Edge(rec[i+1][0],dist));
            map[rec[i+1][0]].add(new Edge(rec[i][0],dist));
        }
        Arrays.sort(rec,new myComY());
        for(int i=0;i<N-1;i++){
            int dist = rec[i+1][2]-rec[i][2];
            map[rec[i][0]].add(new Edge(rec[i+1][0],dist));
            map[rec[i+1][0]].add(new Edge(rec[i][0],dist));
        }
        HashSet<Integer> vis = new HashSet<>();
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        vis.add(0);
        for(Edge e:map[0]) pq.add(e);
        long ans = 0;
        while(vis.size()<N){
            Edge cur = pq.poll();
            int now = cur.to;
            if(vis.contains(now)) continue;
            vis.add(now);
            ans += cur.len;
            for(Edge e:map[now]){
                if(!vis.contains(e.to)) pq.add(e);
            }
        }
        System.out.println(ans);
    }

    static class myComX implements Comparator<int[]>{
        public int compare(int[] a, int[] b){return a[1]-b[1];}
    }
    static class myComY implements Comparator<int[]>{
        public int compare(int[] a, int[] b){return a[2]-b[2];}
    }
    static class Edge implements Comparable<Edge>{
        int to;
        int len;

        public Edge(int t, int l){
            this.to = t;
            this.len = l;
        }

        @Override
        public int compareTo(Edge o) {
            return this.len-o.len;
        }
    }
}


Measured memory_bytes: 113944
package main

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

var sc = bufio.NewScanner(os.Stdin)

func read() string {
	sc.Scan()
	return sc.Text()
}

func geti() int {
	n, _ := strconv.Atoi(read())
	return n
}

// 10 11 12 => [10, 11, 12]
func getli(size int) []int {
	a := make([]int, size)
	list := strings.Split(read(), " ")
	for i, s := range list {
		n, _ := strconv.Atoi(s)
		a[i] = n
	}
	return a
}

func get2byte(size int) [][]byte {
	a := make([][]byte, size)
	for i := 0; i < size; i++ {
		var low string
		fmt.Scan(&low)
		a[i] = []byte(low)
	}
	return a
}

func transpose(a [][]int) {
	n := len(a)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			a[i][j], a[j][i] = a[j][i], a[i][j]
		}
	}
}

func fact(n, m int) int {
	res := 1
	for i := m + 1; i <= n; i++ {
		res *= i
	}
	return res
}

func perm(n, r int) int {
	if r > n {
		return 0
	}
	return fact(n, n-r)
}

func comb(n, m int) int {
	if m > n {
		return 0
	}
	return fact(n, n-m) / fact(m, 0)
}

func reverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}
	return string(runes)
}

func main() {
	N := 2019
	sc.Buffer([]byte{}, math.MaxInt64)
	s := read()
	s = reverse(s)
	var m = make([]int, N)
	m[0]++
	total := 0
	ten := 1
	for i := 0; i < len(s); i++ {
		n, _ := strconv.Atoi(s[i : i+1])
		total += (n * ten) % N
		ten = (ten * 10) % N
		m[total%N]++
	}
	sum := 0
	for _, v := range m {
		sum += v * (v - 1) / 2
	}
	fmt.Println(sum)
}


Measured memory_bytes: 3444
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 1000000007
using namespace std;
ll gcd(ll a, ll b)
{
    while (1)
    {
        if (a < b)
            swap(a, b);
        if (!b)
            break;
        a %= b;
    }
    return a;
}
string solve(ll a, ll b, ll c, ll d)
{
    if (a < b || d < b)
    {
        return "No";
    }
    if (c > b)
    {
        return "Yes";
    }
    else
    {
        ll g = gcd(b, d);
        if (b - g + a % g > c)
        {
            return "No";
        }
        else
        {
            return "Yes";
        }
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        cout << solve(a, b, c, d) << endl;
    }
}

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

int main(){

  int n,m,X,Y;
  cin >> n >> m>> X>> Y;

  int x[n];
  int y[m];

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

  sort(x,x+n);
  sort(y,y+m);

  for(int i=X+1;i<=Y;i++){
    if(x[n-1]<i&&y[0]>=i){
      cout << "No War" << endl;
      return 0;
    }
  }
  cout << "War" << endl;

}


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

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n,m,c; cin>>n>>m>>c;
	vector<int>b(m); for(auto&i:b)cin>>i;
	int ans=0;
	for(int i=0;i<n;++i){
		int sum=0;
		for(int j=0;j<m;++j){
			int A; cin>>A;
			sum+=A*b.at(j);
		}
		if(sum+c>0)++ans;
	}
	cout<<ans<<"\n"s;
}

Measured memory_bytes: 256
k = int(input())

numset = {i for i in range(1,10)}
flag = False
count = len(numset)
if count >= k:
    flag = True
arr = [numset]
index = 0

while not flag:
    beforeset = arr[index]
    tmpset = set()
    for i in beforeset:
        tail = str(i)[-1]
        if tail == "0":
            tmpset.add(int(str(i)+str(0)))
            tmpset.add(int(str(i)+str(1)))
        elif tail == "9":
            tmpset.add(int(str(i)+str(8)))
            tmpset.add(int(str(i)+str(9)))
        else:
            tmpset.add(int(str(i)+str(int(tail))))
            tmpset.add(int(str(i)+str(int(tail)+1)))
            tmpset.add(int(str(i)+str(int(tail)-1)))
    count += len(tmpset)
    if count >= k:
        flag = True
    arr.append(tmpset)
    index += 1
    
totalarr = []
for tmpset in arr:
    totalarr += list(tmpset)
    
totalarr.sort()
print(totalarr[k-1])

Measured memory_bytes: 20364
#include <iostream>
#include <vector>

using namespace std;
constexpr int64_t MOD = 1'000'000'007;
template< typename T >
T mod_pow(T x, T n) {
    T ret = 1;
    while(n > 0) {
        if(n & 1) (ret *= x) %= MOD;
        (x *= x) %= MOD;
        n >>= 1;
    }
    return ret;
}

int main(void) {
    int N;
    cin >> N;
    vector<int> cnt(N);
    for(int i=0; i<N; i++) {
        int A;
        cin >> A;
        cnt[A]++;
    }

    if(N%2) {
        if(cnt[0] != 1) {
            cout << 0 << endl;
            return 0;
        }
        for(int i=2; i<N; i+=2) {
            if(cnt[i] != 2) {
                cout << 0 << endl;
                return 0;
            }
        }
    } else {
        for(int i=1; i<N; i+=2) {
            if(cnt[i] != 2) {
                cout << 0 << endl;
                return 0;
            }
        }
    }

    cout << mod_pow(2L, N/2L) << endl;
    return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<cmath>
#include<random>
#include<set>
#include<queue>

using namespace std;

long long dp[3][100100] = {};
const long long INF = 1LL << 60;
#define MOD 1000000007
#define Int int64_t
#define PI 3.14159265358979
#define dump(a) cout << a << endl; 

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

/**
* @fn
* 最大値を取ります.Vector<int>を渡すこと.
*/
long long int imax(vector<int> a) {
	int MAX = -10000000;
	for (int i = 0; i < a.size(); i++) {
		if (MAX < a.at(i)) MAX = a.at(i);
	}
	return MAX;
}

/**
* @fn
* 最小値を取ります.Vector<int>を渡すこと.
*/
long long int imin(vector<int> a) {
	int MIN = 1000000000;
	for (int i = 0; i < a.size(); i++) {
		if (MIN > a.at(i)) MIN = a.at(i);
	}
	return MIN;
}

/**
* @fn
* 自然数について、桁数を求める
*/
Int getDigit(Int num) {
	return (Int)(log10(num)) + 1;
}


int get2Digit(Int num) {
	int cnt = 0;
	while (num > 0) {
		if (num % 2 != 0) {
			return cnt;
		}
		cnt++;
		num /= 2;
	}
}

long long int absmin(vector<int> a, long long int b) {
	int mini = 100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (mini > abs(a.at(i) - b)) {
			mini = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}


long long int absmax(vector<int> a, long long int b) {
	int max = -100000000;
	int d = 0;
	for (int i = 0; i < a.size(); i++) {
		if (max < abs(a.at(i) - b)) {
			max = abs(a.at(i) - b);
			d = i;
		}
	}
	return d;
}

int gcd(int a, int b)
{
	if (a < b) swap(a, b);
	if (b < 1) return -1;
	if (a % b == 0) return b;
	return gcd(b, a % b);
}

void haerobatya(int start, int end, char level) {
	if (start > end) swap(start, end);
	for (int i = start; i <= end; i++) {
		if (i < 100) {
			cout << "https://atcoder.jp/contests/abc0" << i << "/tasks/abc0" << i << "_" << level << endl;
		}
		else {
			cout << "https://atcoder.jp/contests/abc" << i << "/tasks/abc" << i << "_" << level << endl;
		}
	}
}

long long int cntmod(long long int warareru, long long int mod) {
	long long int i = 0;
	for (i = 0; true; i++) {
		if (warareru % mod == 0 && warareru >= mod) {
			warareru /= mod;
		}
		else {
			return i;
		}
	}
}

void ansYes(bool a) {
	if (a == true) cout << "Yes" << endl;
	else cout << "No" << endl;
}

void ansYES(bool a) {
	if (a == true) cout << "YES" << endl;
	else cout << "NO" << endl;
}


Int euclidean_gcd(Int a, Int b) {
	while (true) {
		if (a < b) swap(a, b);
		if (!b) break;
		a %= b;
	}
	return a;
}

typedef pair<int, int> pai;


//ここまでライブラリ
//ここから本文
int main() {
	char a;
	cin >> a;
	if (a == 'a') { dump("vowel") return 0; }
	if (a == 'e') { dump("vowel") return 0; }
	if (a == 'i') { dump("vowel") return 0; }
	if (a == 'o') { dump("vowel") return 0; }
	if (a == 'u') { dump("vowel") return 0; }
	dump("consonant")
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>> a[100000];
vector<int> ans(100000);
void dfs(int now, int pre, int col){
    ans[now] = col;
    for (auto u:a[now]) if (u.first != pre) dfs(u.first, now, col^(u.second&1));
}


int main(){
    int i, u, v, w, n;
    cin >> n;
    for (i=1; i<n; i++){
        cin >> u >> v >> w;
        a[u].emplace_back(v, w);
        a[v].emplace_back(u, w);
    }
    dfs(1, 0, 0);
    for (i=1; i<=n; i++) cout << ans[i] << endl;
}

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

int main()
{
    int N, k;
    int sum = 0;
    vector<int> vec;

    cin >> N;
    for (int i = 0; i < N - 1; i++)
    {
        cin >> k;
        vec.push_back(k);
    }

    for (int i = 0; i < N; i++)
    {
        if (i == 0)
        {
            sum += vec[i];
        }
        else if (i == N - 1)
        {
            sum += vec[N - 2];
        }
        else
        {
            sum += min(vec[i], vec[i - 1]);
        }
    }

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

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
using namespace std;
typedef long long int ll;
using ull = unsigned long long;

int dp[1<<26],h[1<<26];

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    int n=s.size();
    for(int i=0;i<n;i++){
        h[i+1]=(h[i]^(1<<(s[i]-'a')));
    }
    int res=n;
    for(int i=0;i<n;i++){
        if(!h[i+1]||dp[h[i+1]]){
            res=dp[h[i+1]]+1;
        }
        else{
            res=n;
        }
        for(int j=1;j<(1<<26);j<<=1){
            if(dp[h[i+1]^j]||!(h[i+1]^j)){
                res=min(res,dp[h[i+1]^j]+1);
            }
        }
        if(dp[h[i+1]]||!h[i+1]){
            dp[h[i+1]]=min(dp[h[i+1]],res);
        }
        else{
            dp[h[i+1]]=res;
        }
    }
    printf("%d\n",res );
}


Measured memory_bytes: 226008
#include<stdio.h>

int main()
{
	char c;
	int T = 1;
	while(scanf("%c", &c) != EOF)
	{
		if(T)
		{
			printf("%c", c);
			T = 0;
		}
		else
			T = 1;
	}
	
	return 0;
}

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


int main() {
	
	int n,d;
	cin >> n>>d;
  int t;
  t=2*d+1;
  if(n%t==0){
    cout<<n/t<<endl;
  }
  else{
    cout<<n/t+1<<endl;
  }
}
  
  


Measured memory_bytes: 384
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<functional>
using namespace std;
typedef	long long int ll;

int main(){
    int n;
    int a[100001] = {};
    cin >> n;
    int res = 0;
    int ai;
    for(int i = 0; i < n; i++){
        cin >> ai;
        if(ai <= n){
            a[ai]++;
        }
        else res++;
    }
    for(int i = 1; i <= 100000; i++){
        if(a[i] >= i) res += a[i]-i;
        else res += a[i];
    }
    cout << res << endl;
    return 0;
}

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

using namespace std ;

int n ; 
const int MAXN = 100010 ; 

int gcd(int a, int b) {return b ? gcd(b, a % b) : a ;} 

int a[MAXN] ; 

bool check() { 
		int cnt[2] = {0, 0} ; 
		for (int i = 1; i <= n; i ++) cnt[a[i] & 1] ++ ; 
		int w = cnt[0] & 1 ; 
		if (w) return 1 ; 
		if (cnt[1] > 1) return 0 ;
	    bool flag = 0 ; 	
		for (int i = 1; i <= n; i ++) { 
				if ((a[i] & 1) && a[i] > 1) {
						a[i] -- ;
					    flag = 1 ; 	
						break ; 
				}
		}
		if (!flag) return 0 ; 
		int d = 0 ; 
		for (int i = 1; i <= n; i ++) d = gcd(a[i], d) ; 
		for (int i = 1; i <= n; i ++) a[i] /= d ; 
		return check() ^ 1 ; 
}
int main() { 
		scanf("%d", &n) ; 
		for (int i = 1; i <= n; i ++) scanf("%d", &a[i]) ; 
		if (n == 1) { 
				puts("Second") ; 
				return 0 ; 
		}
		puts(check() ? "First" : "Second") ; 
}



Measured memory_bytes: 640