akhauriyash/Code-Regression huggingface dataset:
//
// Created by maze on 2019/09/15.
//

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

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

using int32 = int32_t;
using int64 = int64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

int main(void) {
    string s;
    cin >> s;
    bool ok = 1;
    REP(i, s.size()) {
        if (i%2 && s[i] == 'R') ok = 0;
        if (i%2 == 0 && s[i] == 'L') ok = 0;
    }
    cout << (ok ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define all(x)(x).begin(), (x).end() // 昇順ソート
#define rall(v)(v).rbegin(), (v).rend() // 降順ソート
#define INF 1LL << 60
typedef long long int LL;
typedef long long int ll;
#define pll pair < ll, ll >
#define F first
#define S second
const int MOD = 1000000007;
template < class T > bool chmax(T & a,const T & b) { if (a < b) { a = b; return true; } return false; }
template < class T > bool chmin(T & a,const T & b) { if (a > b) { a = b; return true; } return false; }
// 任意のlogは　対数の底の変換を使う    log(N) / log(任意の底)

int main() {
    string S,T;
    cin >> S >> T;
    map<char,int> s;
    map<char,int> t;
    rep(i,S.size()){
        s[S[i]]++;
    }
    rep(i,T.size()){
        t[T[i]]++;
    }

    vector<int> sa;
    vector<int> ta;

    for(auto c : s){
        sa.push_back(c.S);
    }
    for(auto c : t){
        ta.push_back(c.S);
    }

    bool ok = true;
    if(sa.size() != ta.size())ok = false;
    else{
        sort(all(sa));
        sort(all(ta));
        rep(i,sa.size()){
            if(sa[i] != ta[i])ok = false;
        }
    }

    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 776
#include <bits/stdc++.h>
#define ll long long
using namespace std;
typedef long double ld;
char s[100050],t[100050];
int n,m;
ll ans;
vector <int> v[30+'a'];

int main(){
	scanf("%s",s);
	scanf("%s",t);
	n=strlen(s),m=strlen(t);
	for(int i=0;i<n;++i){
		v[s[i]].push_back(i);
	}
	int p1=-1;
	for(int i=0;i<m;++i){
		char c=t[i];
		if(v[c].empty())return puts("-1"),0;
		auto it=upper_bound(v[c].begin(),v[c].end(),p1);
		if(it==v[c].end()){
			it=v[c].begin();
			ans++;
		}
		p1=*it;
	}
	cout<<ans*1LL*strlen(s)+p1+1<<endl;
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <map>
#include <iomanip>
#include <math.h> 
#include <stack>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <tuple>
#include <cctype>
#include <ctype.h>
#include <set>
#include <sstream>
#include <time.h>
using namespace std;
//#define int long long
#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define l1 list[index]
#define l2 list[index - 1]
#define l3 list[index + 1]
#define iif(i,j) ((i<0 && j<0) || (i>0 && j>0)) ? true : false 
typedef long long ll;
typedef pair<int, int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint, int> P1;
typedef pair<int, pint> P2;
typedef pair<pint, pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD = 1000000007;
const ll INF = 1e18;
const double PI = 3.14159265359;
int ca[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };


signed main() {
	int n, m;
	vector<int>list;
	int maxn = 9999999;
	int dp[100005];
	bool flag[100005];

	cin >> n >> m;

	memset(dp, 0, sizeof(dp));
	memset(flag, 0, sizeof(flag));

	for (int i = 0; i < m; i++) {
		int num;
		cin >> num;
		flag[num] = true;
	}

	dp[0] = 1;

	if (flag[1] == false) {
		dp[1] = 1;
	}

	for (int i = 2; i <= n; i++) {
		if (flag[i] == true) continue;
		dp[i] += dp[i - 1];
		dp[i] %= MOD;
		dp[i] += dp[i - 2];
		dp[i] %= MOD;
	}


	/*for (int i = 2; i <= n; i++) {
		cout << "i->" << dp[i] << endl;
	}*/

	cout << dp[n] << endl;

	getchar();
	getchar();
	return 0;
}

Measured memory_bytes: 768
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def is_nth_set(x, n):
    if x & (1 << n):
        return 1
    else:
        return 0


def main():
    N, M = map(int, input().split())
    S = []
    for _ in range(M):
        k, *s = map(int, input().split())
        s = [i - 1 for i in s]
        S.append(s)
    P = list(map(int, input().split()))

    ans = 0
    for pattern in range(2 ** N):
        switch = []
        for i in range(N):
            switch.append(is_nth_set(pattern, i))

        for i in range(M):
            cnt = 0
            for s in S[i]:
                cnt += switch[s]
            if cnt % 2 != P[i]:
                break
        else:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()


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

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

typedef long long ll;
using namespace std;
int mod = 1000000007;

int main(void){
    string S; cin >> S;
    int K; cin >> K;
    S = "0" + S;
    int lenS = S.length();
    int cnt[lenS] = {}; //i文字目までに0でない数が出現した回数
    ll dp[4][lenS];
    
    rep(i, 4) rep(j, lenS) dp[i][j] = 0;
    dp[0][0] = 1;
    for(int i = 1; i < lenS; i++){
        if(S[i] == '0') cnt[i] = cnt[i-1];
        else cnt[i] = cnt[i-1] + 1;
    }

    for(int c = 0; c < lenS-1; c++){
        for(int k = 0; k <= K; k++){
            if(k < 3){
                dp[k][c+1] += dp[k][c];
                if(c == 0 && k == 0) dp[k+1][c+1] = (S[c+1]-'0');
                else if(c > 0 && k == cnt[c]){
                    dp[k+1][c+1] += (dp[k][c]-1)*9 + (S[c+1]-'0');
                }
                else dp[k+1][c+1] += dp[k][c]*9;
            }
            else{
                dp[k][c+1] += dp[k][c];
            }
        }
    }
    cout << dp[K][lenS-1] << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
int main()
{
	int k,s;
	scanf("%d%d",&k,&s);
	long long ans=0;
	for(int i=0;i<=k;i++)
	{
		for(int j=0;j<=k;j++)
		{
			if(s-i-j>=0&&s-i-j<=k)
			{
				ans++;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
} 

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, P> PP;

int main(){
	int N;
	cin >> N;
	vector<ll> x1(N), y1(N), x2(N), y2(N);
	vector<PP> x, y;
	for(int i = 0; i < N; i++){
		cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
		x.push_back(PP(x1[i], P(i, 1)));
		x.push_back(PP(x2[i], P(i, -1)));
		y.push_back(PP(y1[i], P(i, 1)));
		y.push_back(PP(y2[i], P(i, -1)));
	}
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());
	for(int i = 0; i < 2 * N; i++){
		if(x[i].second.second == 1) x1[x[i].second.first] = i;
		if(x[i].second.second == -1) x2[x[i].second.first] = i;
		if(y[i].second.second == 1) y1[y[i].second.first] = i;
		if(y[i].second.second == -1) y2[y[i].second.first] = i;
	}
	vector<vector<int> > memo(2 * N, vector<int>(2 * N, 0));
	for(int i = 0; i < N; i++){
		for(int j = y1[i]; j < y2[i]; j++){
			memo[j][x1[i]]++;
			memo[j][x2[i]]--;
		}
	}
	for(int i = 0; i < 2 * N; i++){
		for(int j = 1; j < 2 * N; j++){
			memo[i][j] += memo[i][j - 1];
		}
	}
	ll res = 0;
	for(int i = 0; i < 2 * N; i++){
		for(int j = 0; j < 2 * N; j++){
			//cout << memo[i][j] << (j == 2 * N - 1 ? '\n' : ' ');
			if(memo[i][j] == 0) continue;
			ll diff_x = x[j + 1].first - x[j].first;
			ll diff_y = y[i + 1].first - y[i].first;
			res += diff_x * diff_y;
		}
	}
	cout << res << endl;
	return 0;
}



Measured memory_bytes: 65724
n, h = map(int, input().split())
a = [0]*n
b = [0]*n
maxa = 0
for i in range(n):
    a[i], b[i] = map(int, input().split())
    maxa = max(maxa, a[i])

c = []
for i in range(n):
    if b[i] >= maxa:
        c.append(b[i])
        
c.sort()
csum = sum(c)
count = len(c)

if csum >= h:
    i = 0
    while csum - c[i] >= h:
        if i == len(c):
            break
        else:
            csum -= c[i]
            i += 1
            count -= 1
else:
    if (h - csum) % maxa == 0:
        count += (h - csum) // maxa
    else:
        count += (h - csum) // maxa
        count += 1

print(count)

Measured memory_bytes: 12140
#include <bits/stdc++.h>
#define int long long
#define const 1000000000000
using namespace std;

int dp[101][100010];

int32_t main() {
	int n,w;
	cin >> n >> w;
    vector<pair<int, int> > vec;    
    for(int i = 0; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        vec.push_back({a, b});
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 100010; ++j) {
            dp[i][j] = const;       
        }
    }
    for(int i = 0; i < n; ++i) {
        dp[i][vec[i].second] = vec[i].first;
    }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 100010; ++j) {
            if(i-1 >= 0)
                dp[i][j] = min(dp[i][j], dp[i-1][j]);
            if(i-1 >= 0 && j-vec[i].second >= 0)
                dp[i][j] = min(dp[i][j], dp[i-1][j-vec[i].second] + vec[i].first);
        }
    }
    int mx = -1;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < 100010; ++j) {
            // if(dp[i][j] != const)
            //     cout << j << " " << dp[i][j] << " ";
            if(dp[i][j] != const && dp[i][j] <= w)
                mx = max(mx, j);
        }
        // cout << endl;
    }
    cout << mx << endl;
}


Measured memory_bytes: 78336
n,k=map(int,input().split())
l = list(map(int, input().split()))
a=[0]*(n-k+1)
s=0
for i in range(k):
  s+=l[i]
a[0]=s
for i in range(1,n-k+1):
  a[i]=a[i-1]-l[i-1]+l[i+k-1]
print((max(a)+k)/2)

Measured memory_bytes: 24808
#include <bits/stdc++.h>
inline int read(){char c = getchar();int x = 0,s = 1;
while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
return x*s;}
using namespace std;
#define NewNode (TreeNode *)malloc(sizeof(TreeNode))
#define Mem(a,b) memset(a,b,sizeof(a))
#define lowbit(x) (x)&(-x)
const int N = 1e3 + 5;
const long long INFINF = 0x7f7f7f7f7f7f7f;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-7;
const int mod = 1e9+7;
const double II = acos(-1);
const double PP = (II*1.0)/(180.00);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> piil;
signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    //    freopen("input.txt","r",stdin);
    //    freopen("output.txt","w",stdout);
    ull n,sum = 0;
    cin >> n;
    ull arr[n+5] = {0},ans[n+5] = {00};
    for(int i = 1;i <= n;i++) cin >> arr[i];
    for(int i = 1;i <= n;i++) ans[i] = (arr[i]+ans[i-1]);
    for(int i = 1;i <= n;i++) sum = ((sum + arr[i]*((ans[n]-ans[i])%mod))%mod)%mod;
    cout << sum << endl;
}


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

int gcd(int x, int y){
  if(x<y)swap(x,y);
  if(y==0) return x;
  gcd(x%y,y);
}

int main() {
  int n;
  cin >> n;
  vector<int>a(n);
  rep(i,n) cin >> a[i];
  vector<int>l(n), r(n);
  rep(i,n-1){
    l[i+1] = gcd(l[i],a[i]);
  }
  for (int i = n-1; i >= 1; --i){
    r[i-1] = gcd(r[i],a[i]);
  }
  int ans = 1;
  rep(i,n) {
    ans = max(ans, gcd(l[i],r[i]));
  }
  cout << ans << endl;
  return 0;
}

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

ll comb(ll n)
{
    return n * (n - 1) / 2;
}

int main()
{
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, n) cin >> a[i];
    rep(i, n) a[i]--;

    int cnt[n];
    fill_n(cnt, n, 0);
    rep(i, n) cnt[a[i]]++;
    ll tot = 0;
    rep(i, n) tot += comb(cnt[i]);

    rep(i, n)
    {
        ll ans = tot;
        ans -= comb(cnt[a[i]]);
        ans += comb(cnt[a[i]] - 1);
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 4096
#include <stdio.h>
#include <math.h>

int main(void) {
	int d, y, k;
	int x = 600;
	
	
	while(scanf("%d",&d) != EOF){
	
	y = 0;
	
	for(k=0;k<=(x-d);k=(k+d)){
		y = y+pow(k,2)*d;
	}
	
	printf("%d\n", y);
	
	}
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define PB push_back
#define MP make_pair
#define MOD 1000000007LL
#define endl "\n"
const ll UNDEF = -1;
const ll INF=1e18;
template<typename T> inline bool chkmax(T &aa, T bb) { return aa < bb ? aa = bb, true : false; }
template<typename T> inline bool chkmin(T &aa, T bb) { return aa > bb ? aa = bb, true : false; }
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	string s; cin>>s;
	ll n=s.length();
	ll zlim=1LL<<(n-1);
	ll ans=0;
	for (ll z=0;z<zlim;z++) {
		ll sum=0;
		ll cur=s[0]-'0';
		for (ll x=0;x<n-1;x++) {
			if (z&(1LL<<x)) {
				sum+=cur;
				cur=s[x+1]-'0';
			}
			else {
				cur*=10;
				cur+=s[x+1]-'0';
			}
		}
		sum+=cur;
		ans+=sum;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	bool operator<(const struct Info &arg) const{
		return mult < arg.mult;
	};
	int mult,can_plant;
};

int main(){

	int N,M,K;
	scanf("%d %d %d",&N,&M,&K);

	Info info[N];

	for(int i = 0; i < N; i++){
		scanf("%d",&info[i].mult);
	}

	for(int i = 0; i < N; i++){
		scanf("%d",&info[i].can_plant);
	}

	int ans = M;

	int limit = pow(2,N);

	vector<int> V;

	priority_queue<Info> Q;

	for(int i = 0; i < limit; i++){
		V.clear();
		for(int loop = 0; loop < N; loop++){
			if(i & (1 << loop)){
				V.push_back(loop);
			}
		}
		if((int)V.size() > K)continue;

		for(int a = 0; a < V.size(); a++){
			Q.push(info[V[a]]);
		}

		int sum = 0;
		int rest = M;

		while(!Q.empty()){

			if(rest >= Q.top().can_plant){

				rest -= Q.top().can_plant;
				sum += Q.top().can_plant*Q.top().mult;

			}else{ //rest < Q.top().can_plant
				sum += rest*Q.top().mult;
				rest = 0;
			}
			Q.pop();
		}

		sum += rest;

		ans = max(ans,sum);
	}

	printf("%d\n",ans);

	return 0;
}

Measured memory_bytes: 3440
#include<bits/stdc++.h>
using namespace std;
int main(){
  long N;
  cin >> N;
  long ans = 0;
  long i,j;
  int chk[4]={0,0,0,0};
  long tmp = 0;
  int logi;
  int tmpi;
  int chk7;

  for(i=357;i<=N;i+=2){
    tmp = i;
    logi = 1;
    chk[0]=0;
    chk[1] = 0;
    chk[2]=0;
    chk[3]=0;
    tmpi = 14;
    chk7 = 0;
    while(tmp>0 && chk[3] == 0){
      switch(tmp%10){
        case 3:
          chk[0]++;
          break;
        case 5:
          chk[1]++;
          break;
        case 7:
          chk[2]++;
          if(chk[2]==logi) chk7++;
          break;
        default:
          chk[3]++;
          break;
      }
      tmp =(tmp-tmp%10)/10;
      logi ++;
    }
    if(chk[0]>0 && chk[1]>0 && chk[2]>0 && chk[3]==0) ans++;
    // cout <<i<<" "<<chk[0] <<" "<<chk[1]<<" "<<chk[2]<<" "<<chk[3]<<endl;
    
    for(j=1;j<chk7;j++){
      tmpi *= 10;
    }
    if(chk7>0 && chk[3]==0)i+= tmpi;
  }

  cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define mod 1000000007LL
#define eps 1e-13
// #define PI 3.141592653589793238L
#define INF 1000000011
#define INFLL 1000000000000000011LL
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pil pair<int, long long>
#define pli pair<long long, int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define fo(i,a,n) for(i = (a); i < (n); i++)
#define gtl(x) getline(cin, (x))
#define flsh fflush(stdout)
#define sws ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define gcd __gcd
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)((a).size())
#define io_file freopen("D:/Coding Problems/Contest/input_file.in", "r", stdin); freopen("D:/Coding Problems/Contest/output_file.out", "w", stdout)

ll modx(ll Base, ll exponent)
{
	ll ans = 1;
	if(Base == 1)
		return Base;
	while(exponent)
	{
		if(exponent & 1)
			ans = (ans * Base)%mod;
		Base = (Base * Base)%mod;
		exponent = exponent >> 1;
	}
	return ans;
}

ll inmodx(ll num)
{
	return (modx(num, mod-2LL));
}

bool cmp(pair < pll, int > a, pair < pll, int > b)//true for a before b
{
	if(a.F.F*b.F.S <= b.F.F*a.F.S)
		return 1;
	return 0;
}

const int N = (1e2) + 9;
const int M = (N<<2) + 9;
const int LOGN = ((int)log2(N)) + 3;
const int LOGM = ((int)log2(M)) + 3;
const int BUCK = 2*550;
const int SQRT = BUCK+9;

ll l[N];

void solve()
{
	int n, i, ans = 0;
	ll x, d;
	cin >> n >> x;
	fo(i,1,n+1)
		cin >> l[i];
	d = 0;
	ans = 1;
	fo(i,1,n+1)
	{
		d += l[i];
		if(d <= x)
			ans++;
	}
	cout << ans << '\n';
	return;
}

int main()
{
	sws;
	clock_t clk;
	clk = clock();
	// io_file;
	// srand (time(NULL));

	//Code here
	int t = 1, cs;
	cout << fixed << setprecision(20);
	// cin >> t;
	fo(cs,1,t+1)
	{
		// cout << "Case #" << cs << ": ";
		solve();
	}
	// Code ends here

	clk = clock() - clk;
	cerr << fixed << setprecision(6) << "Time: " << ((double)clk)/CLOCKS_PER_SEC << "\n";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int a, b, c;
	int min, max, midle, tmp;
	scanf("%d%d%d",&a,&b,&c);
	if(a<b){ 
		min=a;
		max=b;
		midle=b;

	}else{
			min=b;
			max=a;
			midle=a;

	}
	//printf("(1)%d %d %d\n",min, midle, max);
	if(min<c){
	    midle=c;
//	    max=c;	

	}else{
		midle=min;
		min=c;
	
	}
	//rintf("(2)%d %d %d\n",min, midle, max);
	if(midle<max){
//		midle= max;
//		max=c;
	}else{
		tmp=max;
		max=midle;
		midle=tmp;
	}
	printf("%d %d %d\n",min, midle, max);
	//return 0;
}


Measured memory_bytes: 2068
#include <bits/stdc++.h>
using namespace std;
#define MIN(a,b) ((a)<(b) ? (a) : (b))

int main() {
  int N;
  int max_ = 30;
  
  cin >> N;
  
  for ( int i = 0 ; i < N ; i++ ) {
    int x;
    int count=0;
    cin >> x;
    while (!(x & 1)) {
      count++;
      x >>= 1;
    }
    max_ = MIN(max_,count);
  }
  
  cout << max_ << endl;
}


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

#define ll long long
using namespace std;

int main()
{
  int N, MOD = 998244353;
  cin >> N;
  int maxs = N*300+1;
  vector<int> a(N);
  vector<vector<ll>> dp(N + 1, vector<ll>(maxs, 0));
  vector<vector<ll>> bicol(N + 1, vector<ll>(maxs, 0));
  dp[0][0] = 1;
  bicol[0][0] = 1;
  for (int i = 0; i < N; i++){
    cin >> a[i];
  }
  int sum = 0;
  for (int i = 0; i < N; i++){
    for (int j = 0; j < maxs; j++){
      dp[i+1][j] += dp[i][j]*2;
      bicol[i+1][j] += bicol[i][j];
      if (j-a[i]>=0) {
        dp[i+1][j] += dp[i][j-a[i]];
        bicol[i+1][j] += bicol[i][j-a[i]];
      }
      dp[i+1][j] %= MOD;
      bicol[i+1][j] %= MOD;
    }
    sum += a[i];
  }

  ll ans = 1;
  for (int i = 0; i < N; i++){
    ans *= 3;
    ans %= MOD;
  }

  for (int i = (sum+1)/2; i <= sum; i++){
    ans += MOD - dp[N][i]*3;
    ans %= MOD;
  }

  if(sum%2 == 0){
    ans += bicol[N][sum/2] * 3;
    ans %= MOD;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 424512
#include <iostream>
#include <algorithm>
#include <stack>
#include <string>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <list>
#include <string.h>
using namespace std;

int n, a[20];

int solve(int i, int m) {
	if(m == 0) return 1;
	if(i >= n) return 0;
	int res;
	res = solve(i+1, m) || solve(i+1, m-a[i]);
	return res;
}

int main() {
	int m,q;
	cin >> n;
	for( int i = 0; i < n; i++ ) {
		cin >> a[i];
	}
	cin >> m;
	for( int i = 0; i < m; i++) {
		cin >> q;
		if( solve(0, q) ) cout << "yes" <<endl;
		else cout << "no" <<endl;
	}
	return 0;
}

Measured memory_bytes: 1156
#include<cstdio>
#include<math.h>
#include<algorithm>

using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001;
#define LLINF 1001001001001001001001;
#define LL long long

int main(){
    int N;
    scanf("%d",&N);
    int A[100002];
    long long int ans=0;
    rep(i,N){
        scanf("%d",&A[i]);
        if(i>0)ans+=abs(A[i]-A[i-1]);
        if(i==0)ans+=abs(A[i]);
        if(i==N-1)ans+=abs(A[i]);
    }
    rep(i,N){
        long long int sans=ans;
        if(i==0){
           if(A[0]*A[1]>0&&abs(A[0])>abs(A[1]) )sans=ans-2*abs(A[0]-A[1]);
            if(A[0]*A[1]<0)sans=ans-2*abs(A[0]);
            if(A[1]==0)sans=ans-2*A[0];
        }else if(i==N-1){
            if(A[N-1]*A[N-2]>0&&abs(A[N-1])>abs(A[N-2]) )sans=ans-2*abs(A[N-1]-A[N-2]);
            if(A[N-1]*A[N-2]<0)sans=ans-2*abs(A[N-1]);
            if(A[N-2]==0)sans=ans-2*A[N-1];
        }else{
            if( (A[i]-A[i-1])*(A[i+1]-A[i-1] )<0 ){
                sans=ans-2*abs( abs(A[i]-A[i-1]) );
            }else{
                if(abs(A[i]-A[i-1])>abs(A[i-1]-A[i+1])  ){
                    sans=ans-2*abs( abs(A[i]-A[i-1])-abs(A[i-1]-A[i+1]) ) ;
                }
            }
        }
        printf("%lld\n",sans);
    }
    return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

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

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}


// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main()
{
    long long N;
    scanf("%lld", &N);
    long long H;
    scanf("%lld", &H);
    vector<pair<ll, ll>> a(N * 2);
    ll A, B;
    for (int i = 0; i < N; i++)
    {
        cin >> A >> B;
        a.push_back(make_pair(A, 0));
        a.push_back(make_pair(B, 1));
    }

    RSORT(a);

    ll ans = 0;

    for (auto &&i : a)
    {
        if (i.second == 1)
        {
            ans++;
            H -= i.first;
        }
        else
        {
            int cnt = ceil(H,i.first);
            ans += cnt;
            H -= cnt * i.first;
        }

        if (H <= 0)
        {
            break;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 8448
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'

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

    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n = ((s1[0] - '0') * 1000) + ((s1[1] - '0') * 100) + ((s1[2] - '0') * 10) + (s1[3] - '0');
    (n < 3200) ? cout << "red\n" : cout << s2 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, a, b) for(int i = a; i < b; i++)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

ll const INF = 1LL<<60;

int main(){
    int n;
    cin >> n;
    vector<int> x(n);
    rep(i,n) cin >> x[i];
    double avg = 0;
    rep(i,n) avg += x[i];
    avg /= n;

    ll ans = INF;
    rep(i,2){
        int pos = i == 0 ? floor(avg) : ceil(avg);
        ll sum = 0;
        rep(j,n) sum += (x[j] - pos) * (x[j] - pos);
        ans = min(ans, sum);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3636
/* Alohomora */
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define pb         push_back
#define mp         make_pair
#define mod        1000000007
#define all(x)     x.begin(),x.end()    
#define F          first 
#define S          second
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
void comp() {
 ll i,j,k,n,m;
 cin>>k;
 queue<string>q1;
 q1.push("1");
 q1.push("2");
 q1.push("3");
 q1.push("4");
 q1.push("5");
 q1.push("6");
 q1.push("7");
 q1.push("8");
 q1.push("9");
 ll count1=0;
 string temp,temp1;
 while(q1.size()>0) {
  temp=q1.front();
  q1.pop();
  count1++;
  if(count1==k) {
    cout<<temp<<endl;
    break;
  }
  char c=temp[temp.size()-1];
  if(c=='0') {
    temp1=temp+'0';
    q1.push(temp1);
    temp1=temp+'1';
    q1.push(temp1);
  }
  else if(c=='9') {
    temp1=temp+'8';
    q1.push(temp1);
    temp1=temp+'9';
    q1.push(temp1);
  }
  else {
    temp1=temp+char(c-'0'-1+'0');
    q1.push(temp1);
    temp1=temp+c;
    q1.push(temp1);
    temp1=temp+char(c-'0'+1+'0');
    q1.push(temp1);
  }
 }
}
  
int main() {
  speedup;
  ll i=0,t;
  //cin>>t;
  t=1;
  while(t--) {
    comp();
  }
  return 0;
}



Measured memory_bytes: 13824
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef vector<ll> Vl;
template<typename T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }
template<typename T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
const int inf = 1e9 + 7;
const ll longinf = 1LL << 60;
const ll mod = 1e9 + 7;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;


int n, ans;
int a[15];
Pll x[15][15];

int numofbits5(long bits)
{
	bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
	bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
	bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
	bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
	return (bits & 0x0000ffff) + (bits >> 16 & 0x0000ffff);
}

int main() {

	cin >> n;

	rep(i, n) {
		cin >> a[i];
		rep(j, a[i]) {
			ll tmp1, tmp2;
			cin >> tmp1 >> tmp2;
			x[i][j] = make_pair(tmp1, tmp2);
		}
	}

	rep(bit, (1 << n)) {
		bool psbl = true;
		rep(i, n) {
			if (bit & 1 << i) {
				rep(j, a[i]) {
					if (x[i][j].se) {
						if (!(bit & (1 << (x[i][j].fi - 1)))) {
							psbl = false;
							break;
						}
					}
					else {
						if (bit & (1 << (x[i][j].fi - 1))) {
							psbl = false;
							break;
						}
					}
				}
			}
			if (!psbl) {
				break;
			}
		}
		if (psbl) {
			ans = max(ans, numofbits5(bit));
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
const int N = 100020;
int n,q,f[N][30]; long long x[N],L;
int main(void)
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&x[i]);
    scanf("%lld\n%d",&L,&q);
    for (int i=1;i<=n;i++)
        f[i][0] = upper_bound( x+1 , x+n+1 , x[i] + L ) - x - 1;
    for (int k=1;k<=25;k++)
        for (int i=1;i<=n;i++)
            f[i][k] = f[f[i][k-1]][k-1];
    for (int i=1;i<=q;i++)
    {
        int a , b , ans = 0;
        scanf("%d%d",&a,&b);
        if ( a > b ) swap( a , b );
        for (int k=25;k>=0;k--)
            if ( f[a][k] < b ) a = f[a][k] , ans += 1<<k;
        if ( a < b ) a = f[a][0] , ans += 1;
        printf("%d\n",ans);
    }
    return 0;
}


Measured memory_bytes: 13312
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll mod=1e9+7;
ll n,m,q;
ll f[210000],dp[210000],jc[210000],ijc[210000],inv[210000];
struct node{
	ll x,y;
}a[210000];
ll calc(int n,int k){
	return jc[n]*ijc[k]%mod*ijc[n-k]%mod;
}
bool cmp(node a,node b){
	return a.x==b.x?a.y<b.y:a.x<b.x;
} 
int main(){
	cin>>n>>m;
	inv[0]=inv[1]=1;
	for(int i=2;i<=n+m;++i){
		inv[i]=(mod-mod/i)*inv[mod%i]%mod;
	}
	jc[0]=ijc[0]=1;
	for(int i=1;i<=n+m;++i){
		jc[i]=jc[i-1]*i%mod,ijc[i]=ijc[i-1]*inv[i]%mod;
	}
	cin>>q;
	for(int i=1;i<=q;++i){
		cin>>a[i].x>>a[i].y;
	}
	sort(a+1,a+1+q,cmp);
	a[0]=(node){1,1};a[++q]=(node){n,m};
	f[0]=1;
	for(int i=0;i<q;++i){
		for(int j=i+1;j<=q;++j){
			if(a[i].y<=a[j].y){
				f[j]=(mod+f[j]-f[i]*calc(a[j].x-a[i].x+a[j].y-a[i].y,a[j].x-a[i].x)%mod)%mod;
			}
		}
	}
	cout<<(mod-f[q])%mod<<'\n';
	return 0;
}

Measured memory_bytes: 8448
#include<iostream>
using namespace std;
int main(){
  int A, B, C, D;
  cin>>A>>B>>C>>D;
  int takanum=0, aokinum=0;
  if(C%B==0){
    takanum=C/B;
  }else{
    takanum=C/B+1;
  }
  if(A%D==0){
    aokinum=A/D;
  }else{
    aokinum=A/D+1;
  }
  if(takanum<=aokinum){
    cout<<"Yes";
  }else{
    cout<<"No";
  }
  return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ins insert
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define up_b upper_bound
#define low_b lower_bound
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define rev(i,a,b) for(int i=b;i>=a;i--)
#define boost ios_base::sync_with_stdio(NULL),cin.tie(NULL),cout.tie(NULL)
#define nl '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<pii> vii;

const int N=200001;
const int MXN=1000001;
const int inf=1e9;
const ll INF=1e18;

int main(){
  boost;
  int n,k;
  cin>>n>>k;
  if((n-1)*(n-2)/2<k){
    cout<<"-1";
    return 0;
  }
  vector<pii>edg;
  for(int i=2;i<=n;i++){
    edg.pb(mp(1,i));
  }
  int cnt=(n-1)*(n-2)/2-k;
  for(int i=n-1;i>=2;i--){
    if(cnt==0)break;
    for(int j=n;j>i;j--){
      if(cnt==0)break;
      cnt--;
      edg.pb(mp(i,j));
    }
  }
  cout<<sz(edg)<<nl;
  for(int i=0;i<sz(edg);i++){
    cout<<edg[i].x<<" "<<edg[i].y<<nl;
  }
  return 0;
}



Measured memory_bytes: 384
using System;
using System.Linq;

class B
{
	static void Main()
	{
		Console.ReadLine();
		var l = Console.ReadLine().Split().Select(int.Parse).OrderByDescending(x => x).ToArray();
		Console.WriteLine(l[0] < l.Skip(1).Sum() ? "Yes" : "No");
	}
}


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

int main() {
 // ここにプログラムを追記
 //0≤R,G≤4500整数　入力は以下の形式で標準入力から与えられる。 
 int n,a ; cin >> n >> a;
 //cout<<m<<r<<endl;
 /*N×Nのマス目があります。

このマス目の各マスを白色または黒色に塗ることにしました (すべてのマスをどちらか片方の色に塗ります)。

ちょうど Aマスを白色に塗るとき、黒色に塗ることになるマスはいくつあるでしょうか。 */

//
 
 cout << n*n -a <<endl;
}

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

#define ll long long int
#define ull unsigned long long int
#define Max 1000005
#define _fastio  ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define ALL(x) x.begin(),x.end()
#define pi acos(-1.0)
#define pb push_back
#define load(array,size)  for(ll i=0 ; i<size ; i++) cin>>array[i] ;
#define endl '\n'

#define sc(n) scanf("%d",&n)
#define scan(n) scanf("%lld",&n)
/*        speed up       */
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define sci(n) scanf("%d",&n);
#define scl(n) scanf("%lld",&n);
#define load1(array,size)  for(ll i=1 ; i<=size ; i++) cin>>array[i] ;
#define INF    1LL<<19
#define pll pair<ll,ll>
#define mst(arr,value) memset(arr,value,sizeof(arr));
#define tst() _fastio;int testsalam;cin >> testsalam;while(testsalam--)
#define Mod 100000007
#define YES cout<<"Yes"<<endl;
#define NO cout<<"No"<<endl;

//void inversemod(ll n, ll mod, ll invmod[],ll MOD){for(int i=2; i<=n; ++i) invmod[i]=MOD-MOD/i*invmod[MOD%i]%MOD;}
//void bigmod( ll a, ll b ,ll mod){ll r = 1;a = a%mod;while(b){if( b%2 ) r = (r*a)%mod;b = b/2;a = (a*a)%mod; }return (ll)r;}
string inttostr(ll n){std::stringstream ss;ss << n;string out=ss.str();return out;}
ll stringtoint(string s){istringstream iss (s);ll n;iss >> n;return n;}
template <typename T> T gcd(T a,T b){if(a < 0)return gcd(-a,b);if(b < 0)return gcd(a,-b);return (b == 0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a,T b) {if(a < 0)return lcm(-a,b);if(b < 0)return lcm(a,-b);return a*(b/gcd(a,b));}
typedef vector<ll>vec;
typedef pair<ll,ll> pii;
typedef map<ll,ll>mpll;
typedef set<ll>seet;
typedef tuple<ll,ll,ll>tpl;

int main()
{
    string a,b,c;
    ll n,m;
    cin  >> n;
    ll r=n/1000;
    if(r*1000==n)return cout<<0<<endl,0;
    else{
    	r=(r+1)*1000;
    	return cout<<abs(r-n)<<endl,0;
    }
}
/*
     remember:
     ll vs int
     array size
     case for 1 2 3 
*/



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

using namespace std;

int main()
{
    int n,d,diff=0,x,cnt=0;
    cin>>n>>d;
    vector<vector <int> > v;
    vector<int> vec;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<d;j++)
        {
           cin>>x;
           vec.push_back(x);
        }
        v.push_back(vec);
        vec.clear();
    }
    int temp=0,t;
    for(int i=0;i<n;i++)
    {
       for(int j=i+1;j<n;j++)
       {

           for(int k=0;k<d;k++)
           {
               temp=v[i][k]-v[j][k];
               diff+=temp*temp;
           }
           t=sqrt(diff);
           if(t*t==diff) cnt++;
           diff=0;

       }
    }
    cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;n>i;++i)
using namespace std;
using ll=int64_t;
using vi=vector<int>;
using VI=vector<ll>;
using vis=vector<string>;
using vvi=vector<vi>;
int gcd(int a,int b){
    if(a%b==0)
    return b;
    return gcd(b,a%b);
}
int main(){
    int a,b,c,k,i=0;
    cin>>a>>b>>c>>k;
    while(i<k){
        if(!(b>a)){
            b*=2;
        }
        else if(!(c>b)){
            c*=2;
        }
        ++i;
    }
    if(b>a&&c>b){
        cout<<"Yes"<<endl;
        return 0;
    }
    else{
        cout<<"No"<<endl;
        return 0;
    }
}

Measured memory_bytes: 3584
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using StructLayoutAttribute = System.Runtime.InteropServices.StructLayoutAttribute;
using FieldOffsetAttribute = System.Runtime.InteropServices.FieldOffsetAttribute;

class P
{
    static int[] Parents;
    static List<int>[] Childs;
    static bool[] IsEmpty;
    static void Main()
    {
        int n = int.Parse(Console.ReadLine());
        Parents = Enumerable.Repeat(-1, 1).Concat(Enumerable.Repeat(0, n - 1).Select(_ => int.Parse(Console.ReadLine()) - 1)).ToArray();
        Childs = Enumerable.Repeat(0, n).Select(_ => new List<int>()).ToArray();
        for (int i = 1; i < Parents.Length; i++) Childs[Parents[i]].Add(i);
        IsEmpty = Childs.Select(x => x.Count == 0).ToArray();
        memo = Enumerable.Repeat(-1, n).ToArray();
        Console.WriteLine(DFS(0));
    }

    static int[] memo;
    //いままでの対戦回数を返す
    static int DFS(int n)
    {
        if (IsEmpty[n]) return 0;
        if (memo[n] != -1) return memo[n];
        int[] a = new int[Childs[n].Count];
        for (int i = 0; i < Childs[n].Count; i++) a[i] = DFS(Childs[n][i]);
        Array.Sort(a);
        int res = 0;
        for (int i = 0; i < a.Length; i++) res = Max(res, a[i] + a.Length - i);
        return memo[n] = res;
    }
}


Measured memory_bytes: 39864
import math

N = int(input())

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

List_re = list(reversed(List))
arr = [-1 for i in range(N+1)]
arr2 = [-1 for i in range(N+1)]
arr3 = [-1 for i in range(N+1)]

for i in range(N+1):
  a = List_re[i]
  if i == 0:
    arr3[N-i] = a    
  else:
    arr3[N-i] = math.ceil(arr3[N-i+1]/2) + a

for i in range(N+1):
  a = List_re[i]
  if i == 0:
    arr[N-i] = a    
  else:
    arr[N-i] = arr[N-i+1] + a
    
for i in range(N+1):
  a = List[i]
  if i == 0:
    arr2[i] = 1
  else:
    arr2[i] = ( arr2[i-1]-List[i-1]) *2

ans = 0

for i in range(N+1):
  a = arr[-i-1]
  b = arr2[-i-1]
  c = min(a,b)
  ans += c

if arr3[0] != 1:
  print(-1)
else:
  print(int(ans))

Measured memory_bytes: 684644
def listint():
    a = input().split()
    for i in range(len(a)):
        a[i] = int(a[i])
    return a
n,m = listint()
votes = listint()
sumvo = sum(votes)
able = 0
for i in range(n):
    if votes[i] >= sumvo/(4*m):
        able = able+1
if able >= m:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 38480
//minamoto
#include<bits/stdc++.h>
#define R register
#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)
#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)
#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)
template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}
template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}
using namespace std;
typedef long long ll;
const int N=5e5+5;
int a[N],n,k;ll Pre[N],suf[N],sum[N],res;
int main(){
	scanf("%d%d",&n,&k);
	fp(i,1,n)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	fp(i,1,n)Pre[i]=Pre[i-1]+(a[i]>=0?a[i]:0);
	fd(i,n,1)suf[i]=suf[i+1]+(a[i]>=0?a[i]:0);
	for(R int l=1,r=k;r<=n;++l,++r)
		cmax(res,Pre[l-1]+suf[r+1]+max(sum[r]-sum[l-1],0ll));
	printf("%lld\n",res);
	return 0;
}

Measured memory_bytes: 11264
#include <iostream>
#include <limits.h>
using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    if (a <= b && b <= c) cout << c - a;
    else if (a <= c && c <= b) cout << b - a;
    else if (b <= a && a <= c) cout << c - b;
    else if (b <= c && c <= a) cout << a - b;
    else if (c <= b && b <= a) cout << a - c;
    else if (c <= a && a <= b) cout << b - c;
	return 0;
}


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 P = pair<int, int>;

int main()
{
    string s, t;
    cin >> s >> t;
    int ans = 1e9;
    rep(i, s.size() - t.size() + 1)
    {
        int cnt = 0;
        rep(j, t.size())
        {
            if (s[i + j] != t[j])
                cnt++;
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3628
n = int(input())
a = list(map(int, input().split()))
left = 0
right = 0

ans = 0
now = 0
while True:
    while right < n and now + a[right] == now ^ a[right]:
        now += a[right]
        right += 1

    if left >= n:
        break

    ans += right - left
    now -= a[left]
    left += 1

print(ans)


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

using namespace std;

int main() {
	string b;
	while (getline(cin, b)) {
		if (b == "END OF INPUT") {
			break;
		}
		int counter = 0;
		for (int i = 0; i < b.size(); i++) {
			if (b[i] != ' ') {
				counter++;
			} else {
				cout << counter;
				counter = 0;
			}
		}
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1184
#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	string s,t; cin >> s >> t;
  	int ans = 0;
  	for(int i =0; i < s.size(); i++)
      if (s[i] == t[i]) ans++;
  	cout << ans << endl;
	return 0;
}

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

int main(void) {
  int N, M; cin >> N >> M;
  vector<int> P(M);
  vector<int> Y(M);
  vector<int> yd[100001];
  for (int i = 0; i < M; i++) {
    cin >> P[i] >> Y[i];
    yd[P[i]].push_back(Y[i]);
  }
  for (int i = 0; i < N; i++) {
    sort(yd[i+1].begin(), yd[i+1].end());
  }
  for (int i = 0; i < M; i++) {
    int lb = int(lower_bound(yd[P[i]].begin(), yd[P[i]].end(), Y[i]) - yd[P[i]].begin()) + 1;
    printf("%012lld\n", (long long)(P[i]) * 1000000 + int(lb));
  }

}


Measured memory_bytes: 7808
#include <iostream>
#include <bitset>
using namespace std;
int nr,cul;
int N;
int A[105];
bitset<9> U;
int main()
{
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        cin>>A[i];
        if(A[i]<400){cul+=(U[1]==0);U[1]=1;}
        else if(A[i]<800){cul+=(U[2]==0);U[2]=1;}
        else if(A[i]<1200){cul+=(U[3]==0);U[3]=1;}
        else if(A[i]<1600){cul+=(U[4]==0);U[4]=1;}
        else if(A[i]<2000){cul+=(U[5]==0);U[5]=1;}
        else if(A[i]<2400){cul+=(U[6]==0);U[6]=1;}
        else if(A[i]<2800){cul+=(U[7]==0);U[7]=1;}
        else if(A[i]<3200){cul+=(U[8]==0);U[8]=1;}
        else
            nr++;
    }
    cout<<max(1,cul)<<" "<<nr+cul;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;

int n,m,i,ans,x;

int main()
{
    cin>>n>>m;
    for (i=0;i<n;i++)
    {
        cin>>x;
        ans+=min(m-x,x);
    }
    cout<<ans*2;
}


Measured memory_bytes: 256
use std::collections::HashMap;
use whiteread::parse_line;

fn main() {
    let n: usize = parse_line().unwrap();
    let mut dic: HashMap<String, u32> = HashMap::new();

    for _ in 0..n {
        let s: String = parse_line().unwrap();
        *dic.entry(s).or_insert(0) += 1;
    }

    let max_cnt = *dic.values().max().unwrap();
    let mut max_key = dic
        .iter()
        .filter(|(_, &v)| v == max_cnt)
        .collect::<Vec<_>>();
    max_key.sort_by(|(k1, _), (k2, _)| k1.cmp(k2));
    for (ans, _) in max_key {
        println!("{}", ans);
    }
}


Measured memory_bytes: 21304
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
using namespace std;

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    swap(a, b);
    swap(a, c);
    cout << a << " " << b << " " << c << " " << endl;
    // system("pause");
}

Measured memory_bytes: 256
import static java.lang.System.out;
import static java.lang.Integer.parseInt;
import java.io.File;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        new Main().digit();
    }

    public void digit() {
        try (Scanner scan = new Scanner(System.in)) {
            scanDigit(scan);
        } catch (Exception e) {
            System.exit(0);
        }
    }

    public void digit(String inDataPath) {
        try (Scanner scan = new Scanner(new File(inDataPath))) {
            scanDigit(scan);
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    public void scanDigit(Scanner scan) throws Exception {
        String inData;
        while ((inData = scan.nextLine()) != null || !"".equals(inData)) {
            String[] inDataList = inData.split(" ");
            int sum = parseInt(inDataList[0]) + parseInt(inDataList[1]);
            out.println(String.valueOf(sum).length());
        }
    }
}

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

int main(void) {
  int N, M;
  cin >> N >> M;
  vector<int> A(N, 0);

  int all = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    all += A[i];
  }

  int count = 0;
  for (int i = 0; i < N; i++) {
    if (A[i] * 4 * M >= all) {
      count++;
    }
  }
  if (count < M) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N, M, X = map(int, input().split())


def num2bi(num):
    l = [0] * N
    for i in range(N):
        if num >= 2 ** (N - 1 - i):
            num -= 2 ** (N - 1 - i)
            l[i] = 1
    return l


SUM = [0] * M
A = [[0] * M for _ in range(N)]
C = []
for i in range(N):
    a = list(map(int, input().split()))
    for j in range(M):
        SUM[j] += a[j + 1]
        A[i][j] = a[j + 1]
    C.append(a[0])

ans = sum(C)
if min(SUM) < X:
    ans = -1
else:
    for num in range(2 ** N):
        SUM = [0] * M
        tmp = 0
        for i in range(N):
            if num2bi(num)[i] == 1:
                for j in range(M):
                    SUM[j] += A[i][j]
                tmp += C[i]
        if min(SUM) >= X:
            ans = min(ans, tmp)

print(ans)

Measured memory_bytes: 9152
#include <iostream>
#include <cmath>
#include <bits/stdc++.h>
#include <algorithm>
#include <complex>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(7)<<(x)
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)

using namespace  std;
using ll = long long;
const ll mod = 1e9 + 7;
typedef pair<ll, ll> pairs;
typedef complex<ll> G;
const int N=2e5+5;

const int INF = 1e9+5;


void done() {


    char p;
    cin >> p;
    if(islower(p)) cout << 'a' << '\n';
    else cout << 'A';

}
void solve() {
    int n, k;
    cin >> n >> k;
    int a[n];
    for(int i=0; i< n;i++) {
        cin >> a[i];
    }
    sort(a, a+n);
    int sum = 0;
    for(int i=0;i < k;i++) {
        sum += a[i];
    }
    cout << sum << '\n';

}

void another() {

}
int main() {

    fast;
    solve();

}


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

#define REP(i,a,b) for(int i=int(a);i<int(b);i++)

using namespace std;

typedef long long int lli;

int main () {
    int N;
    cin >> N;
    cout << ((N / 10 == 9 || N % 10 == 9) ? "Yes" : "No") << endl;
    return 0;
}


Measured memory_bytes: 256
package main
import(
  "fmt"
)
func main(){
  var s string
  var i, n int 
  fmt.Scan(&s)
  n=len(s)
  if n%2==1{
      fmt.Println("No")
      return
    }
  for i=0;i<n-1;i+=2{
    if s[i]!='h'||s[i+1]!='i'{
      fmt.Println("No")
      return
    }
  }
  fmt.Println("Yes")
}

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

using namespace std;

int q(vector<int>& d, vector<vector<int>>& e, int v) {
    if (d[v] != -1) return d[v];
    int an = 0;
    for (int i : e[v]) {
        an = max(an, 1 + q(d, e, i));
    }
    d[v] = an;
    return d[v];
}

int main() {
    int n, m;
    cin>>n;
    cin>>m;
    vector<vector<int>> e;
    for (int i = 0; i < n; i++) {
        vector<int> v;
        e.push_back(v);
    }
    for (int i = 0; i < m; i++) {
        int p, q;
        cin>>p;
        cin>>q;
        e[p-1].push_back(q-1);
    }
    int l = 0;
    vector<int> d(n, -1);
    for (int i = 0; i < n; i++) {
        if (d[i] != -1) l = max(l, d[i]);
        else l = max(l, q(d, e, i));
    }
    cout<<l<<endl;
    return 0;
}


Measured memory_bytes: 8816