akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
#include<ctype.h>
#include<math.h>


int main()
{
    int a[3][3];
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    int f00=1,f01=1,f02=1,f10=1,f11=1,f12=1,f20=1,f21=1,f22=1;
    int n;
    scanf("%d", &n);
    int b[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d", &b[i]);
        if(b[i]==a[0][0])f00=0;
        else if(b[i]==a[0][1])f01=0;
        else if(b[i]==a[0][2])f02=0;
        else if(b[i]==a[1][0])f10=0;
        else if(b[i]==a[1][1])f11=0;
        else if(b[i]==a[1][2])f12=0;
        else if(b[i]==a[2][0])f20=0;
        else if(b[i]==a[2][1])f21=0;
        else if(b[i]==a[2][2])f22=0;
    }
    if((f00==0 && f01==0 && f02==0) || (f10==0 && f11==0 && f12==0) || (f20==0 && f21==0 && f22==0))printf("Yes");
    else if((f00==0 && f10==0 && f20==0) || (f01==0 && f11==0 && f21==0) || (f02==0 && f12==0 && f22==0))printf("Yes");
    else if((f00==0 && f11==0 && f22==0) || (f02==0 && f11==0 && f20==0))printf("Yes");
    else printf("No");
}


Measured memory_bytes: 128
#!/usr/bin/env python

s = int(input())
mod = 10**9+7

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod 

mod = 10**9+7 
N = 10**4
g1 = [1, 1]
g2 = [1, 1]  
inverse = [0, 1]  

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

n = s//3
ans = 0 

for i in range(n):
    tmp = s 
    tmp -= 3*(i+1)
    ans += cmb(tmp+i, i, mod)

print(ans%mod)


Measured memory_bytes: 10296
#include <iostream>
#include <iomanip>

int main(int argc, char **argv) {
	double a, b, c, d, e, f, x, y;
	
	while(std::cin >> a >> b >> c >> d >> e >> f) {
		y = (c * d - a * f) / (b * d - a * e);
		x = (c - b * y) / a;
		std::cout << std::fixed << std::setprecision(3) << x << " " << y << std::endl;
	}
}


Measured memory_bytes: 3200
from collections import Counter
s = input()
n = len(s)

for i in range(n):
    if n == 2:
        if s[0] == s[1]:
            print(1, 2)
            exit()
    if i == n - 2:
        break
    c = Counter(s[i:i + 3])
    v = c.most_common()
    if v[0][1] * 2 > len(s[i:i + 3]):
        print(i + 1, i + 3)
        exit()

print(-1, -1)

Measured memory_bytes: 9504
#include <bits/stdc++.h>
using namespace std;
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T> using gpp_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename L> using gpp_map = tree<T, L, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using gpp_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) { cout << #v << "=" << endl; REP(i_debug, v.size()){ cout << v[i_debug] << ","; } cout << endl; }
#define mdebug(m) { cout << #m << "=" << endl; REP(i_debug, m.size()){ REP(j_debug, m[i_debug].size()){ cout << m[i_debug][j_debug] << ","; } cout << endl;} }
#define Return(ans) { cout << (ans) << endl; return 0; }
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T1, typename T2> ostream &operator<<(ostream &os, pair<T1, T2> p){ cout << '(' << p.first << ',' << p.second << ')'; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }
 
using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;
 
//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};
 
const int mod = 1000000007;
//const int mod = 998244353;
//#define Add(x, y) x = (x + (y)) % mod
//#define Mult(x, y) x = (x * (y)) % mod

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

signed main(){
    int A,B,H,M; cin>>A>>B>>H>>M;
    double KakuH = H*30+M/2.0;
    int KakuM = M*6;
    double CL = abs(KakuH-KakuM);
    double pi = 3.141592653589793238;
    double ans = A*A+B*B-2*A*B*cos(CL/180.0*pi);
    Out(sqrt(ans));
}

Measured memory_bytes: 4212
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <stdio.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; i++)
#define rep(i,b) Rep(i,0,b)
#define rrep(i,a) for(int i = a; i >= 0; i--)
#define allof(a) (a).begin(), (a).end()

typedef long long ll;
const int inf = 1e9 + 7;
const ll infll = 1ll << 60ll;
const ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

/*
// 最大公約数
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}

// 最小公倍数
ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}*/

int main() {

	string s;
	cin >> s;

	int n = (int)s.size();

	// 周期性を見極める
	// LとRの境目を行き来する
	// RLの並びを探す

	vector<int> ans(n, 0);

	// 辿り着くマス Rの終わりとLの終わり
	vector<int> dest(n, 0);

	// ruisekiwaruisekiwa
	// まず左
	Rep(i, 1, n) {
		if (s[i] == 'L') {
			if (s[i - 1] == 'R') {
				dest[i] = i;
			}
			else {
				dest[i] = dest[i - 1];
			}
		}
	}

	// つぎ→
	for (int i = n - 2; i >= 0; i--) {
		if (s[i] == 'R') {
			if (s[i + 1] == 'L') {
				dest[i] = i;
			}
			else {
				dest[i] = dest[i + 1];
			}
		}
	}

	rep(i, n) {
		int dif = abs(dest[i] - i);
		if (s[i] == 'R') {
			ans[i] = (dif % 2 == 1) ? (dest[i] + 1) : dest[i];
		}
		else {
			ans[i] = (dif % 2 == 1) ? (dest[i] - 1) : dest[i];
		}
	}

	vector<int> num(n, 0);
	rep(i, n) {
		num[ans[i]]++;
	}

	rep(i, n) {
		cout << num[i] << " ";
	}
	cout << endl;

	return 0;
}


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

using namespace std ;

int main()
{
	int n ;
	while( cin >> n ,n )
	{
		int m ;
		cin >> m ;
		int num[ n + 1 ] ;
		num[ 0 ] = 0 ;
		for( int i = 1 ; i <= n ; i++ )
		{
			cin >> num[ i ] ;
			num[ i ] += num[ i - 1 ] ;
		}
		int ans = 0 ;
		for( int i = m ; i <= n ; i++ )
			ans = max( ans ,num[ i ] - num[ i - m ] ) ;
		cout << ans << endl ;
	}
	return 0 ;
}

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

int main() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    vector<vector<ll>> G(N);
    rep(i, N-1){
        G[i].push_back(i+1);
        G[i+1].push_back(i);
    }
    G[X-1].push_back(Y-1);
    G[Y-1].push_back(X-1);
    vector<ll> ans(N-1, 0);

    rep(i, N){
        vector<ll> dist(N, -1);
        queue<ll> que; 
        dist[i] = 0;
        que.push(i);
        while(!que.empty()){
            ll v = que.front();
            que.pop();
            for(ll nv : G[v]){
                
                if(dist[nv] != -1) continue;
                dist[nv] = dist[v] + 1;
                que.push(nv);
            }
        }

        rep(j, N){
            if(dist[j] > 0){
                ans[dist[j]-1]++;
            }
        }
    }
    
    rep(i, N-1){
        cout << ans[i]/2 << endl;
    }
}


Measured memory_bytes: 512
N = int(input())
S = input()
maxn =0
alp = [chr(i) for i in range(97, 97+26)]
for i in range(N-1):
  A = S[:i+1:]
  B = S[i+1::]
  count = 0
  for j in alp:
    if A.find(j)!=-1 and B.find(j)!=-1:
      count+=1
  maxn = max(maxn,count)
print(maxn)

Measured memory_bytes: 3064
// hmmmm ...coool
#include<bits/stdc++.h>
using namespace std;	
#pragma GCC optimize("Ofast") 
#define int long long
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back 
#define eb emplace_back
#define fn for(int i =0 ;i <n;i++)
#define fn1 for( int i =1;i<=n;	i++)
#define fm for(int j =0 ;j <m;j++)
#define fm1 for(int j =1;j<=m;j++)
#define fi first
#define se second
#define endl '\n'
# define PI  3.14159265358979323846
#define MOD 1000000007
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
const int N = 2e6+5;
const int INF = 1e18L;
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}
int ar[N];
int dp[N];
signed main(){
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS;
	int T=1;
	// cin >> T;
	while(T--){
		int n =5;
		fn1{
			cin >> ar[i];
			if(ar[i]==0)return cout << i, 0;
		}

	}
	return 0;
}

Measured memory_bytes: 3572
#include<iostream>
#include<string>
#include<math.h>
#include<vector>
#include<algorithm>

using namespace std;
int main() {
	int a, b, c, d;

	cin >> a >> b >> c >> d;
	cout << max((a*b), (c*d)) << endl;
	
	return 0;

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int a[100001];
string aa;
int main()
{
	cin>>aa;
	int l=aa.length();
	int ans=0;
	int cap=0;
	for(int i=0;i<l;i++)
	{
		if(cap==0)
		{
			cap++;
			a[cap]=aa[i];
		}
		else if(aa[i]!=a[cap])
		{
			cap--;
			ans+=2;
		}
		else
		{
			cap++;
			a[cap]=aa[i];
		}
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(a)  (a).begin(),(a).end()
#define SZ(a) int((a).size())
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define MP make_pair
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define sqr(x)  ((x) * (x)) 
#define cub(x)  ((x) * (x) * (x))
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; }
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
// ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

const ll INF = 1001001001001001001;

int main(void){
  ll n,W; cin >> n >> W;
  ll v[45],w[45];
  FOR(i,0,n-1){
    cin >> v[i] >> w[i];
  }
  pair<ll,ll> ps[1 << 20];

  int n2 = n/2;
  FOR(i,0,(1<<n2)-1){
    ll sw = 0, sv = 0;
    FOR(j,0,n2-1){
      if(i & (1<<j)){
        sw += w[j];
        sv += v[j];
      }
    }
    ps[i] = MP(sw,sv);
  }

  sort(ps,ps+(1<<n2));
  int m = 1;
  FOR(i,1,(1<<n2)-1){
    if(ps[m-1].second < ps[i].second){
      //は？
      ps[m] = ps[i];
      ++m;
    }
  }

  ll res = 0;
  FOR(i,0,(1<<(n-n2))-1){
    ll sw = 0, sv = 0;
    FOR(j,0,n-n2-1){
      if(i & (1<<j)){
        sw += w[n2 + j];
        sv += v[n2 + j];
      }
    }
    if(sw<=W){
      ll tv = (lower_bound(ps,ps+m,MP(W-sw,INF))-1)->second;
      res = max(res, sv+tv);
    }
  }

  cout << res << endl;
}





Measured memory_bytes: 19500
#include <bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
int n,dp[2003][2003],a[6003],ans,tg,MX[2003],cur;
vector<int>A,B,C;
void add(int x,int y,int z){A.push_back(x),B.push_back(y),C.push_back(z);}
int main(){
	cin>>n;
	for(int i=1;i<=3*n;i++)cin>>a[i]; 
	memset(dp,-1,sizeof(dp));
	memset(MX,-1,sizeof(MX));
	dp[a[1]][a[2]]=dp[a[2]][a[1]]=MX[a[1]]=MX[a[2]]=cur=0;
	for(int i=3;i<3*n;i+=3){
		if(a[i]==a[i+1]&&a[i]==a[i+2]){tg++;continue;}
		A.clear(),B.clear(),C.clear();
		if(a[i]>a[i+1])swap(a[i],a[i+1]);
		if(a[i+1]>a[i+2])swap(a[i+1],a[i+2]);
		if(a[i]>a[i+1])swap(a[i],a[i+1]);
		for(int j=1;j<=n;j++){
		if(a[i]==a[i+1])if(dp[j][a[i]]>=0)add(j,a[i+2],dp[j][a[i]]+1);
		if(a[i+1]==a[i+2])if(dp[j][a[i+1]]>=0)add(j,a[i],dp[j][a[i+1]]+1);
		}
		if(dp[a[i]][a[i]]>=0)add(a[i+1],a[i+2],dp[a[i]][a[i]]+1);
		if(dp[a[i+1]][a[i+1]]>=0)add(a[i],a[i+2],dp[a[i+1]][a[i+1]]+1);
		if(dp[a[i+2]][a[i+2]]>=0)add(a[i],a[i+1],dp[a[i+2]][a[i+2]]+1);
		add(a[i],a[i+1],cur),add(a[i+1],a[i+2],cur),add(a[i],a[i+2],cur);
		for(int j=i;j<i+3;j++)for(int k=1;k<=n;k++)if(MX[k]>=0)add(a[j],k,MX[k]);
		for(int j=0;j<(int)A.size();j++)if(dp[A[j]][B[j]]<C[j])
			dp[A[j]][B[j]]=dp[B[j]][A[j]]=C[j],MX[A[j]]=max(MX[A[j]],C[j]),MX[B[j]]=max(MX[B[j]],C[j]),cur=max(cur,C[j]);
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++)if(dp[i][j]>=0)ans=max(ans,dp[i][j]);
		if(dp[i][i]>=0)if(i==a[3*n])ans=max(ans,dp[i][i]+1);
	}
	printf("%d",ans+tg);
}


Measured memory_bytes: 19584
#include <bits/stdc++.h>	
using namespace std;
#define short int
void read(short &x){
	char ch=getchar();x=0;
	for (;ch==' '||ch=='\n';ch=getchar());
	for (;ch!=' '&&ch!='\n';x=x*10+ch-'0',ch=getchar());
}
void write(short x){
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
short n,m,sum[190][190],dp[190][190][190][17];
short got(short a,short b,short  c,short d){
	return sum[c][d]-sum[a-1][d]-sum[c][b-1]+sum[a-1][b-1];
}
int main(){
	read(n),read(m);
	for (short i=1;i<=n;i++,getchar()) for (short j=1;j<=m;j++){
		char c=getchar();
		sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+(c=='#');
	}
	for (short i=1;i<=n;i++) for (short j=1;j<=m;j++) for (short k=j;k<=m;k++){
		short l=0,r=n-i+2;
		if (got(i,j,i,k)!=0 && got(i,j,i,k)!=k-j+1);
		else while (r>l+1){
			short mid=(l+r)/2;
			if (got(i,j,mid+i-1,k)==0 || got(i,j,mid+i-1,k)==(k-j+1)*mid) l=mid;
			else r=mid;
		}
		for (short p=0;p<17;p++) dp[i][j][k][p]=l;
	}
	for (short l=1;l<17;l++) for (short i=1;i<=n;i++) for (short j=1;j<=m;j++) for (short k=j;k<=m;k++){
		dp[i][j][k][l]=dp[i][j][k][l-1]+dp[i+dp[i][j][k][l-1]][j][k][l-1];
		short ld=j,rd=k;
		while(ld<rd){
			short mid=(ld+rd)/2;
			if(dp[i][j][mid][l-1]<=dp[i][mid+1][k][l-1]) rd=mid;
			else ld=mid+1;
		}
		short val=dp[i][j][ld][l-1];
		ld=j,rd=k;
		while(ld<rd){
			short mid=(ld+rd+1)/2;
			if(dp[i][mid][k][l-1]<=dp[i][j][mid-1][l-1]) ld=mid;
			else rd=mid-1;
		}
		val=max(val,dp[i][ld][k][l-1]);
		dp[i][j][k][l]=max(dp[i][j][k][l],val);
	}
	for (short i=0;i<17;i++)if (dp[1][1][m][i]>=n){
		write(i);return 0;
	}
}

Measured memory_bytes: 444800
#include<bits/stdc++.h>
#define L 1301281
using namespace std;
int T,a,b,c,d;
long long n,V,h[L],f[L];
int get(long long x){
	int y=x%L;
	while(h[y]&&h[y]^x)y=(++y==L)?0:y;
	return y;
}
long long calc(long long n){
	if(!n)return 0;
	if(n==1)return d;
	int x=get(n);
	if(h[x]==n)return f[x];
	h[x]=n;
	if(8e18/d<n)f[x]=8e18;else f[x]=n*d;
	f[x]=min(f[x],calc(n>>1)+(n&1)*d+a);
	if(n&1)f[x]=min(f[x],calc(n+1>>1)+d+a);
	f[x]=min(f[x],calc(n/3)+(n%3)*d+b);
	if(n%3)f[x]=min(f[x],calc(n/3+1)+(3-n%3)*d+b);
	f[x]=min(f[x],calc(n/5)+1ll*(n%5)*d+c);
	if(n%5)f[x]=min(f[x],calc(n/5+1)+1ll*(5-n%5)*d+c);
	return f[x];
}
int main(){
	scanf("%d",&T);
	for(;T--;){
		scanf("%lld %d %d %d %d",&n,&a,&b,&c,&d);
		printf("%lld\n",calc(n));
		for(int i=0;i<L;++i)h[i]=f[i]=0;
	}
}

Measured memory_bytes: 24144
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int d;
		int r;
		double f;

		d = x / y;
		r = x % y;
		f = (double)x / y;

		System.out.printf("%d %d %.5f", d, r, f);

	}
}

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

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int N = sc.nextInt();

		double T = sc.nextDouble();

		double A = sc.nextDouble();

		double[] H = new double[N];

		for(int i=0;i<N;i++) H[i] = sc.nextDouble();

		double h = T - (H[0]*0.006);

		int ans = 1;

		for(int i=1;i<N;i++) {

			double hi = T - (H[i]*0.006);

			if(Math.abs(A-h)>Math.abs(A-hi)) {

				h = hi;

				ans = i+1;

			}
		}

		System.out.println(ans);
	}

}


Measured memory_bytes: 28400
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>

using namespace std;

long long MOD = 1000000007;


int main() {

  int N, A[100005];
  cin>>N;
  for(int i=0; i<N; i++) cin>>A[i];

  int m[100005];
  fill(m, m+N, 0);

  for(int i=0; i<N; i++){
    m[(N-1)/2 - A[i]/2]++;
    if((N-1)/2 - A[i]/2 != (N-1)/2 + A[i]/2) m[(N-1)/2 + A[i]/2]++;
    //cout<<i<<" : "<<(N-1)/2 - A[i]/2<<" "<<(N-1)/2 + A[i]/2<<endl;
  }

  long long ans = 1;
  for(int i=0; i<=(N-1)/2; i++){
    //cout<<i<<" : "<<m[i]<<endl;
    if(m[i] == 0 || m[i]> 2 || (i == N/2 && m[i] >1)){
      cout<<0<<endl;
      return 0;
    }
    if(i == N/2) ans = ans;
    else ans = (ans % MOD) * 2 % MOD;
  }


  cout<<ans % MOD<<endl;

  return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,k;
    cin >> n >> k;
    int h[n];
    for(int i=0;i<n;i++) cin >> h[i];
    sort(h,h+n);
    int hm=1000000000;
    for(int i=0;i<=n-k;i++){
        if(hm>h[i+k-1]-h[i])hm=h[i+k-1]-h[i];
    }
    cout << hm <<endl;
}

Measured memory_bytes: 640
import java.util.Scanner;

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

        // 個数
        int n = sc.nextInt();
      
      	//それぞれの数字
      	long[] a= new long[n];
      
      	long result=0;
      	long sum=0;
      	long sqSum=0;
		
      	for(int i=0;i<n;i++){
          a[i]=sc.nextLong();
          sum=(sum+a[i])%(long)(2*Math.pow(10,9)+14);
          sqSum=(sqSum+a[i]*a[i])%(long)(2*Math.pow(10,9)+14);
        }
      	
      	result=((sum*sum-sqSum)/2) % (long)(Math.pow(10,9)+7);
      	

      	System.out.println(result);
      
      
      
      
    }
}

Measured memory_bytes: 63476
#define PROB ChangingChange

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
#define rep(i, l, r) for (int i = l; i<r;i++)
#define all(b) b.begin() , b.end()
#define mp(a, b) make_pair(a,b)
#define pb(a) push_back(a)
#define vi vector<int>
#define vd vector<double>
#define vs vector<string>
#define vii vector<pair<int,int>>
#define vvi vector<vector<int>>
#define ii pair<int,int>
#define turnOff(k, i) (k&(~(1<<(i-1))))
#define isOn(k, i) (k&&(1<<i-1)?true:false)
#define pll pair<long long int , long long int>
#define ull unsigned long long int
#define ll  long long int
#define add(a, b) ((a+b)%MOD)
#define sub(a, b) ((a-b+MOD)%MOD)
#define mul(a, b) ((a*b)%MOD)
#ifdef  DEBUG
#define MAXN 105
#else
#define MAXN 5000020
#endif
#define MAXLG 20
#define endl '\n'
#define PI 3.141592653589793238
#define MOD (1000000007)
#define INF (2000000000)
#define EPS (0.00000001)
#define treap treapNode*

int gcd(int a, int b) {
    while (a != 0) {
        int c = a;
        a = b % a;
        b = c;
    }
    return b;
}

vi adj[3000];

vi getAllDivisors(int num) {
    vector<int> divs;
    int square_root = (int) sqrt(num) + 1;
    for (int i = 1; i < square_root; i++) {
        if (num % i == 0) {
            if (i * i != num) {
                divs.pb(i);
            }
            divs.pb(num / i);
        }

    }
    return divs;
}

class PROB {
public:
};


ll mod_pow(long x, int y) {
    // exponentiation by squaring
    ll r = 1;
    while (y > 0) {
        if (y % 2 == 1) {
            r = (r * x) % MOD;
        }
        x = (x * x) % MOD;
        y /= 2;
    }
    return r;
}
int dp[2][1001][51][51];


int main() {
    PROB temp;
    ios_base::sync_with_stdio(false);
    cin.tie(0);

#ifdef DEBUG
    freopen("input", "r", stdin);
#endif
     int n,m;
    cin>>n>>m;
    set<int> from[n];
    rep (i,0,m) {
        int x,y;
        cin>>x>>y;
        from[x-1].insert(y-1);
    }
    int total = 0;
    for (int mid : from[0]) {
        if (from[mid].count(n-1))total++;
    }

    if(total)cout <<"POSSIBLE";
    else cout<<"IMPOSSIBLE";


    return 0;
}

Measured memory_bytes: 19072
class node:
    def __init__(self, parent, left, right, depth, height):
        self.p = parent
        self.l = left
        self.r = right
        self.d = depth
        self.h = height

def setDepth(u, depthPosition):
    if u == -1:
        return
    T[u].d = depthPosition
    setDepth(T[u].r, depthPosition + 1)
    setDepth(T[u].l, depthPosition + 1)

def setHeight(u):
    h1 = h2 = 0
    if T[u].r != -1:
        h1 = setHeight(T[u].r) + 1
    if T[u].l != -1:
        h2 = setHeight(T[u].l) + 1
    T[u].h = max(h1, h2)
    return max(h1, h2)

def getDegree(u):
    degree = 0
    if T[u].r != -1:
        degree += 1
    if T[u].l != -1:
        degree += 1
    return degree

def getSibling(u):
    if T[u].p == -1:
        return -1
    if T[T[u].p].l != u and T[T[u].p].l != -1:
        return T[T[u].p].l
    if T[T[u].p].r != u and T[T[u].p].r != -1:
        return T[T[u].p].r
    return -1    

n = int(input())
T = [node(-1, -1, -1, 0, 0) for _ in range(n)]
for _ in range(n):
    info = list(map(int, input().split(" ")))
    T[info[0]].l = info[1]
    T[info[0]].r = info[2]
    if info[1] != -1:
        T[info[1]].p = info[0]
    if info[2] != -1:
        T[info[2]].p = info[0]

for x in T:
    if x.p == -1:
        setDepth(T.index(x), 0)
        setHeight(T.index(x))

for i in range(n):
    print("node", end = ' ')
    print(i, end = ': ')
    print("parent =", end = ' ')
    print(T[i].p, end = ', ')
    print("sibling =", end = ' ')
    print(getSibling(i), end = ', ')
    print("degree =", end = ' ')
    print(getDegree(i), end = ', ')
    print("depth =", end = ' ')
    print(T[i].d, end = ', ')
    print("height =", end = ' ')
    print(T[i].h, end = ', ')
    if T[i].p == -1: print("root")
    elif T[i].r == -1 and T[i].l == -1: print("leaf")
    else: print("internal node")



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

int main() {
  int n;
  cin >> n;
  int ans = 0;
  int count = 0;
  vector<int> h (n);
  for (int i=0; i < n; i++){
    cin >> h.at(i);
  }
  for (int j=0; j < n-1; j++){
    if (h.at(j) >= h.at(j+1)){
      count++;
    }
    else{
      if (count > ans){
        ans = count;
      }
      count = 0;
    }
  }
  if (count > ans){
    ans = count;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#include<list>
#include<unordered_map>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k,a[1010],sum[1010]={},x=0;
    vll v;
    cin>>n>>k;
    rep(i,n){
        cin>>a[i];
        v.pb(a[i]);
        sum[i+1]=sum[i]+a[i];
    }
    rep(i,n){
        rep2(j,i+1,n){
            v.pb(sum[j+1]-sum[i]);
        }
    }
    for(ll t=40;t>0;t--){
        ll cnt=0;
        rep(i,(ll)v.size()){
            if(((x+(1LL<<(t-1))) & v[i]) ==((x+(1LL<<(t-1)))))cnt++;
        }
        if(cnt>=k){
            x+=(1LL<<(t-1));
        }
    }
    cout<<x<<endl;
    return 0;
}

Measured memory_bytes: 6384
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
ll n,m,c;
cin >> n >> m >> c;
ll b[m];
ll a[n][m];
for(ll i=0;i<m;i++){
    cin >> b[i];
    }
for(ll i=0;i<n;i++){
    for(ll j=0;j<m;j++){
        cin >> a[i][j];
    }
}
ll point[n];
for(ll i=0;i<n;i++){
    point[i]=0;
}
for(ll i=0;i<n;i++){
    for(ll j=0;j<m;j++){
        point[i]+=a[i][j]*b[j];
    }
}
ll ans=0;
for(ll i=0;i<n;i++){
    if(point[i]+c>0)ans++;
}
cout << ans << endl;
}


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

int main()
{
    int n;
    cin >> n ;
    vector<int> c(n - 1), s(n - 1), f(n - 1);
    for(int i = 0;i < n - 1;i++){
        cin >> c[i] >> s[i] >> f[i];
    }

    for(int i = 0;i < n - 1;i++){
        int ans = 0;
        ans += s[i] + c[i];
        for(int j = i + 1;j < n - 1;j++){
            while(ans % f[j] != 0 || s[j] > ans){
                ans++;
            }
            ans += c[j];
        }

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

    if(n != 1){
        cout << 0;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const long double PI = acos(-1);
typedef long long ll;
typedef pair<int64_t,int64_t> pll;
typedef pair<int,int> pii;
typedef vector<int64_t> vl;
int dx[]={1,-1,0,0,1,-1,1,-1};
int dy[]={0,0,1,-1,1,-1,-1,1};
#define INF (2147483647)
#define mod (1000000007)
#define limit (7368791)
#define rep(i,a,b) for (int64_t i = (a); i < (b); i++)
#define REP(i,n) rep(i,0,n)
#define sz(s) (s).size()
#define ALL(a) begin(a),end(a)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

    bool dp[30010][4][1010];
void solve()
{
	int n;string s;cin>>n>>s;
    dp[0][0][0]=1;
    REP(i,n)REP(j,4)REP(k,1000){
        if(dp[i][j][k]==0)continue;
        dp[i+1][j][k]=1;
        if(j<3)dp[i+1][j+1][k*10+(s[i]-'0')]=1;
    }
    int ans=0;
    REP(i,1000)if(dp[n][3][i])ans++;
    cout<<ans<<endl;
}

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


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

int main() {
  int N;
  cin >> N;
  vector<int> height(N);
  for (int i=0; i<N; ++i) {
    cin >> height[i];
  }
  
  int ans=0, var=0;
  for (int i=0; i<N; ++i) {
    var = 1;
    for (int j=0; j<=i; ++j) {
      if (height[i] < height[j]) {
        var = 0;
      }
    }
    ans += var;
  }
  
  cout << ans << endl;
  return 0;
}







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

int main() {
	int N, M, X, Y;
	cin >> N >> M >> X >> Y;
	vector<int> x(N + 1);
	vector<int> y(M + 1);
	for(int i = 0; i < N + 1; i++){
		if(i == 0){
			x.at(i) = X;
		}
		else{
			int a;
			cin >> a;
			x.at(i) = a;
		}
	}
	sort(x.begin(), x.end());
	for(int i = 0; i < M + 1; i++){
		if(i == 0){
			y.at(i) = Y;
		}
		else{
			int a;
			cin >> a;
			y.at(i) = a;
		}
	}
	sort(y.begin(), y.end());
	if(x.at(x.size() - 1) < y.at(0)){
		cout << "No War" << endl; 
	}
	else{
		cout << "War" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int day,a,b,c,d;
	int joy = 0;
	//freopen("C:\\Users\\J2401\\Desktop\\In.txt","r",stdin);
	//freopen("C:\\Users\\J2401\\Desktop\\out.txt","w",stdout);
	scanf("%d %d %d %d %d",&day,&a,&b,&c,&d);
	if(a % c == 0)
	{
		if(b % d == 0)
		{
			if(a / c >= b / d)
			{
				joy = a / c;
			}
			else
			{
				joy = b / d;
			}
		}
		else
		{
			if(a / c >= (b / d + 1))
			{
				joy = a / c;
			}
			else
			{
				joy = b / d + 1;
			}
		}
		
	}
	else
	{
		if(b % d == 0)
		{
			if(a / c + 1 >= b / d)
			{
				joy = a / c + 1;
			}
			else
			{
				joy = b / d;
			}
		}
		else
		{
			if(a / c + 1 >= (b / d + 1))
			{
				joy = a / c + 1;
			}
			else
			{
				joy = b / d + 1;
			}
		}
	}
	printf("%d\n",day - joy);
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int(i) = 0; (i) < (n); (i)++)
#define FOR(i, m, n) for(int(i) = (m); (i) < (n); (i)++)
#define All(v) (v).begin(), (v).end()
#define pb push_back
#define MP(a, b) make_pair((a), (b))
template <class T> vector<T> make_vec(size_t a, T val) {
    return vector<T>(a, val);
}
template <class... Ts> auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec(ts...))>(a, make_vec(ts...));
}
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using Graph = vector<vector<int>>;
template <typename T> struct edge {
    int to;
    T cost;
    edge(int t, T c) : to(t), cost(c) {}
};
template <typename T> using WGraph = vector<vector<edge<T>>>;
const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;

int main() {
    int N, A, B;
    cin >> N >> A >> B;
    if((B - A) % 2 == 0) {
        cout << "Alice" << endl;
    } else {
        cout << "Borys" << endl;
    }
}

Measured memory_bytes: 3616
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pi pair<ll, ll>
#define mp make_pair
#define pb push_back
#define vi vector<ll>
#define pd pair<double, double>
#define vp vector<pi>
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, a, n) for(int i = a; i < n; i++)
#define mod (1000*1000*1000+7)
#define sz(x) int((x).size())
#define all(x) x.begin(),x.end()
#define DBG(v) cerr << #v << " = " << (v) << endl;
ll INF = (1ll<<61);

using namespace std;

int main(int argc, char* argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
      int n, m; cin >> n >> m;
      vi v(n, -1);
      f(i, m){
        int a, b; cin >> a >> b;
        if(v[a-1] == -1 || v[a-1] == b) v[a-1] = b;
        else{
          cout << -1 << endl;
          return 0;
        }
      }
      if(v[0] == -1 && sz(v) > 1) v[0] = 1;
      else if(v[0] == 0 && sz(v) > 1){
        cout << -1 << endl;
        return 0;
      }
      f(i, sz(v)) cout << (v[i] ==-1?0:v[i]);
      cout << endl;
    }
    return 0;
}


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

using namespace std;

int main()
{
    int A, B, K;
    int a, b, r, kcd, count;

    cin >> A >> B >> K;
    if (A < B) 
        swap(A, B);
    a = A;
    b = B;
    kcd = 1;

    r = a % b;
    while (r != 0) {
        a = b;
        b = r;
        r = a % b;
    }
    for (int i = b; i > 0; i--) {
        if (A % i ==  0 && B % i == 0) 
            count++;
        if (count == K) {
            kcd = i;
            break;
        }
   }

   cout << kcd << endl;

   return 0;
}

Measured memory_bytes: 256
def SGS(X):
    global ans
    global N
    if X != "":
        if int(X) > N :
            return False
    if "7" in X and "5" in X and "3" in X:
        ans += 1
    SGS("3" + X)
    SGS("5" + X)
    SGS("7" + X)
    return(ans)

ans = 0
N = int(input())
print(SGS(""))

Measured memory_bytes: 3060
#include<iostream>
#include<unordered_set>

using namespace std;

int main(){

    int size,query;
    unordered_multiset<int> ans;
    cin >> size;
    for (int i=0;i<size;i++){
        cin >> query;
        if (ans.find(query) == ans.end()){
            ans.emplace(query);
        }
        else{
            ans.erase(query);
        }

    }
    cout << ans.size() << endl;
    return 0;
}

Measured memory_bytes: 4388
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define INF 1<<30
#define LINF 1LL<<60
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
	string A; cin >> A;
	ll len = A.length();
	ll sum = (len*(len - 1)) / 2;
	vector<ll> cnt(26, 0);
	for (int i = 0; i < len;i++) {
		cnt[A[i] - 'a']++;
	}
	ll C = 0;
	for (int i = 0; i < 26;i++) {
		C += (cnt[i] * (cnt[i] - 1)) / 2;
	}
	cout << sum - C + 1 << endl;
	return 0 ;
}

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

typedef long long ll;
#define ALL(a) a, a+sizeof(a)/sizeof(a[0])
#define all(a) a.begin(),a.end()
#define MOD 1000000007
using namespace std;
ll gcd(ll n, ll m) {
	if (m == 0) return n;
	return gcd(m, n % m);
}
ll lcm(ll n, ll m) {return m / gcd(n, m) * n;}

int main(void) {
	ll n;
	cin >> n;
	int num = 1;
	while (num <= n) {
		num *= 2;
	}
	cout << num / 2 << endl;
	return 0;
}


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

int main()
{
    int N;
    std::cin >> N;
    std::vector<int> d(N);

    for (int i = 0; i < N; i++) std::cin >> d[i];

    std::sort(std::begin(d), std::end(d));

    int ans = 1;
    int b = d[0];
    for (int i = 1; i < N; i++) {
        if (b < d[i]) {
            b = d[i];
            ans++;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    int x = n % 10;
    if(x == 3){
        cout << "bon" << endl;
    }else if (x == 0 || x == 1 || x == 6 || x == 8){
        cout << "pon" << endl;
    }else{
        cout << "hon" << endl;
    }

    return 0;
}

Measured memory_bytes: 3636
import java.io.*;
import java.util.ArrayList;

class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] sl = str.split(" ");
        int N = Integer.parseInt(sl[0]);
        int K = Integer.parseInt(sl[1]);
        str = br.readLine();
        ArrayList<Integer> nums = new ArrayList<>();
        int tmp = 1;
        int cont = 0;
        for (String s:str.split("")){
            if (Integer.parseInt(s)== tmp){
                cont++;
            } else {
                nums.add(cont);
                cont = 1;
                tmp = 1 - tmp;
            }
        }
        if (cont != 0){
            nums.add(cont);
        }
        if (nums.size() % 2 == 0){
            nums.add(0);
        }
        Integer[] nums_ = nums.toArray(new Integer[nums.size()]);
        int ans = 0;
        ArrayList<Integer> list = new ArrayList<>();
        int k = K * 2 + 1;
        for (int i=0;i<nums_.length;i+=2){
            for (int j=i;j<Math.min(i+k,nums_.length);j++){
                ans += nums_[j];
            }
            list.add(ans);
            ans = 0;
        }
        for (int i:list){
            if (ans < i){
                ans = i;
            }
        }
        System.out.println(ans);
    }
}

Measured memory_bytes: 33228
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>
 
int main(void){
    int n,m,near=0,ans=0;
    scanf("%d%d",&n,&m);
    int a[m],b[m],c[n];
    for (int i=0; i<n; i++){
        c[i]=1e9;
    }
    for (int i=0; i<m; i++){
        scanf("%d%d",&a[i],&b[i]);
        a[i]--;
        b[i]--;
        if(c[a[i]]>b[i]){
            c[a[i]]=b[i];
        }
    }
    for (int i=0; i<n; i++){
        if (c[i]!=1e9){
            if (i>=near){
                ans++;
                near=c[i];
            } else if (c[i]<near){
                near=c[i];
            }
        }
    }
    printf("%d\n",ans);
	return 0 ;
}

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

int main(){
    int N;
    string S;
    cin >> N >> S;

    int ans = 0;
    for(int i=0;i<1000;i++){
        string s;
        int x = i;
        for(int j=0;j<3;j++){
            s += '0' + x%10;  
            x /= 10;   
        }
        int ti = 0;
        for(int i=0;i<N;i++){
            if(S[i] == s[ti])
                ti++;
            if(ti == 3){
                ans++;
                break;
            }
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
import math
L = int(input())

t = int(math.log2(L))
ans = []
N = t+1

for i in range(t):
    ans.append((i,i+1,0))
    ans.append((i,i+1,2**i))
offset = 2**t
while True:
    remains = L - offset
    if remains <= 0:
        break

    t = int(math.log2(remains))
    ans.append((t,N-1,offset))

    offset += 2 ** t


print(N,len(ans))
for a,b,l in ans:
    print(a+1,b+1,l)

def check_ans(ans,N):
    assert  N <= 20
    from collections import defaultdict
    d = defaultdict(list)
    for a,b, l in ans:
        d[a].append((b,l))

    def guchoku(d,i=0,l_tmp=0):
        if i==N-1:
            return [l_tmp]
        tmp = []
        for _next,l in d[i]:
            tmp+= guchoku(d,_next,l_tmp+l)
        return tmp
    # print(guchoku(d),N)
    print(tuple(sorted(guchoku(d))) == tuple(range(L)))



Measured memory_bytes: 3316
#include <bits/stdc++.h>
const int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
typedef long long ll;
const int N=200005;
const int mod=1e9+7;
int n,P,a[N];
ll f[N][2];
using namespace std;

/*struct node
{
	int t,next;
}adj[N<<1];
void add(int s,int t)
{
	adj[++now]=(node){t,head[s]};
	head[s]=now;
}*/
int calc(int a,int b)
{
	int ans=1,tmp=a;
	while (b)
	{
		if (b&1) ans=(ll)ans*tmp%mod;
		tmp=(ll)tmp*tmp%mod,b>>=1;
	}
	return ans;
}
inline int read()
{
	char c;int x;
	while (c=getchar(),c<'0' || c>'9');x=c^'0';
	while (c=getchar(),c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^'0');
	return x;
}
void write(int x)
{
	if (x==0) return;
	write(x/10);
	putchar((x%10)+'0');
}
int main()
{
	#ifdef Kay
		freopen ("code.in","r",stdin);
		freopen ("code.out","w",stdout);
	#endif
	cin>>n>>P;
	int i,j;f[0][0]=1;
	for (i=1;i<=n;i++)
	{
		cin>>a[i],a[i]&=1;
		for (j=0;j<2;j++)
		f[i][j]=f[i-1][j^a[i]]+f[i-1][j];
	}
	cout<<f[n][P];
	return 0;
}


Measured memory_bytes: 256
#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 o(a) cout << a << endl
#define int long long
using namespace std;
typedef pair<int, int> P;

string s[8], t = "ox";
int MAX, MAXy, MAXx, my, op;
int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dx[8] = {1, 0, -1, -1, 1, 1, -1, 0};

bool contain(int y, int x){
    return (0 <= y && y < 8 && 0 <= x && x < 8);
}

void check(int y, int x, int dg){
    if(dg == 0 && s[y][x] != '.') return;
    int cnt = 0;
    rep(i, 0, 8){
        int tmp = 0;
        rep(j, 1, 8){
            int ny = y + dy[i] * j;
            int nx = x + dx[i] * j;
            if(!contain(ny, nx) || s[ny][nx] == '.') break;
            if(s[ny][nx] == t[op]){
                // if(dg == 1) s[ny][nx] = t[my];
                tmp++;
            }else{
                if(dg == 1){
                    rep(k, 1, j + 1){
                        s[y + dy[i] * k][x + dx[i] * k] = t[my];
                    }
                }
                cnt += tmp;
                break;
            }
        }
    }
    if(MAX < cnt){
        MAX = cnt;
        MAXy = y;
        MAXx = x;
    }
}

signed main(){
    rep(i, 0, 8) cin >> s[i];
    int g = 0;
    for(int i = 0;; i++){
        my = i % 2;
        op = (i + 1) % 2;
        MAX = 0; MAXy = 0; MAXx = 0;
        if(my == 0){
            rep(j, 0, 8){
                rep(k, 0, 8){
                    check(j, k, 0);
                }
            }
        }else{
            repb(j, 7, 0){
                repb(k, 7, 0){
                    check(j, k, 0);
                }
            }
        }
        if(MAX == 0) g++;
        else g = 0;
        if(g == 2) break;
        if(MAX != 0){
            s[MAXy][MAXx] = t[my];
            check(MAXy, MAXx, 1);
        }
        // rep(j, 0, 8) cout << s[j] << endl;
        // cout << endl;
        
    }
    rep(i, 0, 8) cout << s[i] << endl;
}

Measured memory_bytes: 3208
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;

constexpr long double PI = 3.14159265358979323846264338327950288L;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

class BMakingTriangle {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n; cin >> n;
      vector<int> l(n);
      rep(i, n) {
        cin >> l[i];
      }
      sort(all(l));
      int ret = 0;
      for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
          for(int k=j+1; k<n; k++) {
            if (l[i] < l[j] && l[j] < l[k]) {
              if (l[i] + l[j] > l[k]) {
                ret++;
              }
            }
          }
        }
      }
      cout << ret << endl;
    }
};

signed main() {
  BMakingTriangle solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}

Measured memory_bytes: 3624
// #pragma GCC target("avx2")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<complex>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-10;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3121000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
}
// ここから編集しろ

int p[310000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<(1<<a);i++){
		scanf("%d",p+i);
	}
	for(int i=a-1;i>=0;i--){
		for(int j=0;j<(1<<i+1);j+=2){
			if(p[j]==p[j+1])p[j/2]=p[j];
			else p[j/2]=ABS(p[j+1]-p[j]);
		}
	}
	printf("%d\n",p[0]);
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(kbrni,n)cout<<" "<<a[kbrni];cout<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define svecp(v) cout<<#v<<":";each(kbrni,v)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

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

void Show(int flag)
{
	if(flag){
		cout << "First\n";
	}else{
		cout << "Second\n";
	}
}

vi solve(vi& a,int hoge)
{
	int n = len(a);
	int id = -1;
	int cnt = 0;
	rep(i,n){
		if(a[i] % 2 == 0){
			cnt++;
		}else{
			id = i;
		}
	}
	if(cnt % 2 == 0){
		if(n - cnt > 1){
			Show(hoge^0);
			return {-1};
		}else{
			if(a[id] == 1){
				Show(hoge^0);
				return {-1};
			}
			a[id]--;
			ll g = 0;
			rep(i,n){
				g = gcd(g,a[i]);
			}
			rep(i,n){
				a[i] /= g;
			}
			return a;
		}
	}else{
		Show(hoge^1);
		return {-1};
	}
}

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
	vi a(n);
	rep(i,n){
		cin >> a[i];
	}
	int hoge = 0;
	while(1){
		a = solve(a,hoge);
		hoge ^= 1;
		if(a[0] == -1){
			break;
		}
	}
    return 0;
}


Measured memory_bytes: 1024
N=int(input())

S=list(input())
m=0

a=S.count("R")
b=S.count("G")
c=S.count("B")

num=a*b*c

for i in range(N-2):
  for j in range(i+1,N):
    k=2*j-i #削る条件
    if k>N-1:
      break
    elif S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
      m+=1
      
print(num-m)

Measured memory_bytes: 9232
N = int(input())
A=list(map(int, input().split()))
all=int(sum(A)/2)
ans=[]
index=[]
i=0
for j in range(int(N/2)):
    k=(i+1+2*j)%N
    index.append(A[k])    
x=all-sum(index)
ans.append((x)*2)
for i in range(N-1):
    y=A[i]-x
    ans.append((y)*2)
    x=y
for a in ans:
    print(a)

Measured memory_bytes: 66020
N = int(input())
H = [int(i) for i in input().split()] + [float('inf')]
now = 0
ret = 0
for i in range(1, N+1) :
    if H[i] <= H[i-1] :
        now += 1
    else :
        ret = max(ret, now)
        now = 0
print(ret)

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

const int maxn = int(1e4)+5;

int A[maxn], B[maxn];

int main(void)
{
	int n;
	scanf("%d", &n);
	for(int i = 0;i < n;i++) scanf("%d", &A[i]);
	for(int i = 0;i < n;i++) scanf("%d", &B[i]);

	for(int i = 0;i < n;i++)
	{
		if(B[i] < A[i])
		{
			int req = A[i]-B[i];
			for(int j = 0;j < n;j++)
			{
				if(A[j] < B[j])
				{
					int todo = min(req, (B[j]-A[j])/2);
					B[i] += todo, A[j] += 2*todo, req -= todo;
				}
			}
		}
	}

	for(int i = 0;i < n;i++)
	{
		if(A[i] > B[i])
		{
			printf("No\n");
			exit(0);
		}
	}
	printf("Yes\n");
}

Measured memory_bytes: 384
x, y = map(int, input().split())
setA = []
setA.append({1, 3, 5, 7, 8, 10, 12})
setA.append({4, 6, 9, 11})
setA.append({2})
 
for s in setA:
  if x in s and y in s:
    print("Yes")
    exit()
print("No")

Measured memory_bytes: 3060
cnt = int(input())
tar_list = list(map(int, input().split()))
flg = False
for i in range(cnt):

  if tar_list[i] % 2 == 0:
    if tar_list[i] % 3 == 0 or tar_list[i] % 5 == 0:
      flg = False
    else:
      flg = True
      print("DENIED")
      break
      
if flg == False:
  print("APPROVED")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
int main(){
	int x,a,b;
	cin>>x>>a>>b;
	if(a>=b)
		cout<<"delicious"<<endl;
	else if((b-a)<(x+1))
		cout<<"safe"<<endl;
	else
		cout<<"dangerous"<<endl;
	return 0;
}

Measured memory_bytes: 256