akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=(b);++i)
#define LL long long
#define Mod 1000000007

LL N,M,K,Ans,P3[600001];
LL Frc[900001],Fnv[900001];

inline LL C(int N,int M){
	if( M<0 || M>N ) return 0ll;
	return Frc[N]*Fnv[M]%Mod*Fnv[N-M]%Mod;
}

int main(){
	scanf("%lld%lld%lld",&N,&M,&K);
	
	P3[0]=1;
	F(i,1,M+K) P3[i]=P3[i-1]*3%Mod;
	
	Frc[0]=1;
	F(i,1,N+M+K) Frc[i]=Frc[i-1]*i%Mod;
	
	Fnv[0]=Fnv[1]=1;
	F(i,2,N+M+K) Fnv[i]=(Mod-Mod/i)*Fnv[Mod%i]%Mod;
	F(i,2,N+M+K) Fnv[i]=Fnv[i-1]*Fnv[i]%Mod;
	
	LL Thi=1;
	F(i,N,N+M+K){
		Ans=(Ans+P3[N+M+K-i]*C(i-1,N-1)%Mod*Thi)%Mod;
		Thi=(2*Thi-C(i-N,i-N-K)-C(i-N,M)+2*Mod)%Mod;
	}
	
	printf("%lld",Ans);
	
	return 0;
}

Measured memory_bytes: 18944
#include<stdio.h>
int main()
{
	int next;
	scanf("%d", &next);

	int n;
	for ( n = 0; n < 10; n++)
	{
		if (next<=n*111)
		{
			printf("%d", n * 111);
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll H, W;
    cin >> H >> W;

    vector<string> S(H);
    rep(i, H) cin >> S[i];
    
    vector<vector<int>> L(H, vector<int>(W)); 
    vector<vector<int>> R(H, vector<int>(W)); 
    vector<vector<int>> U(H, vector<int>(W)); 
    vector<vector<int>> D(H, vector<int>(W)); 

    // left
    rep(y, H) {
        int cnt = 0;
        rep(x, W) {
            if (S[y][x] == '.') {
                cnt++;
            }
            else {
                cnt = 0;
            }
            L[y][x] = cnt;
        }
    }

    // right
    rep(y, H) {
        int cnt = 0;
        for (int x = W - 1; x >= 0; x--) {
            if (S[y][x] == '.') {
                cnt++;
            }
            else {
                cnt = 0;
            }
            R[y][x] = cnt;
        }
    }

    // Up
    rep(x, W) {
        int cnt = 0;
        rep(y, H) {
            if (S[y][x] == '.') {
                cnt++;
            }
            else {
                cnt = 0;
            }
            U[y][x] = cnt;
        }
    }

    // Down
    rep(x, W) {
        int cnt = 0;
        for (int y = H - 1; y >= 0; y--) {
            if (S[y][x] == '.') {
                cnt++;
            }
            else {
                cnt = 0;
            }
            D[y][x] = cnt;
        }
    }

    int res = 0;
    rep(y, H) rep(x, W) {
        res = max(res, U[y][x] + D[y][x] + L[y][x] + R[y][x] - 3);
    }
    put(res);
}
signed main(){ Main();return 0;}

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

using namespace std;
#define REP(i, n) for(ll i = 0;i < n;i++)
#define ll long long
#define MOD 1000000007LL
#define llMAX 9223372036854775807LL
#define llMIN -9223372036854775808LL
using vi = vector<ll>; // intの1次元の型に vi という別名をつける
using vvi = vector<vi>; // intの2次元の型に vvi という別名をつける

ll D=365;
vi c(26);
vi last(26,-1);
vvi dat(D, vi(26));  // N * M の2次元配列
vvi AAlist(D, vi(D));  // N * M の2次元配列




ll calcscore(vi &Alist)
{
  for(ll i=0;i<26;i++){
    last[i]=-1;
  }
  

  ll sc=0;
  ll sct=0;
  ll l;
  ll id;
  ll factscore=0;
  for(ll i=0;i<D;i++){
    sc=-922337203685477580LL;
    for(ll j=0;j<26;j++){
      if (Alist[i]==j)continue;
      l=i-last[j];
      sct=l*c[j];
      factscore-=sct;
    }

    id=Alist[i];
    factscore+=dat[i][id];
    last[id]=i;
  }

  return factscore;
}



void makeseed(int xid,int startoffset)
{

  ll sc=0;
  ll sct=0;
  ll maxid=-1;
  ll factscore=0;
  
  for(ll i=0;i<26;i++){
    last[i]=startoffset-1;
  }

  for(ll i=startoffset;i<D;i++){
    sc=-922337203685477580LL;
    maxid=0;
    
    for(ll j=0;j<26;j++){
      ll l=i-last[j];
      
      l*=(l-1-l*5/6);
      sct=l*c[j];
      factscore-=sct;
      sct=dat[i][j]+sct;
      if (sc<sct){
        sc=sct;
        maxid=j;
      }
    }
    factscore+=sc;
    last[maxid]=i;
    AAlist[startoffset][i]=maxid;
    //cout<<(maxid+1)<<endl;
  }


}





int main(){
  ll ans=0;
  ll debug=0;//本番では0に
  cin>>ans;
  ll factscore=0;


  for(ll i=0;i<26;i++){
    cin>>c[i];
  }
  for(ll i=0;i<D;i++){
    for(ll j=0;j<26;j++){
      cin>>dat[i][j];
    }
  }


  for(ll i=0;i<D;i++){
    makeseed(0,i);
  }
  



  for(ll i=1;i<D;i++){
    for(ll j=0;j<i;j++){
      AAlist[i][j]=AAlist[i-1][j];
    }
  }
  
  ll score=-922337203685477580LL;
  ll ansid=0;
  for(ll i=0;i<D;i++){
    if (score<calcscore(AAlist[i])){
      score=calcscore(AAlist[i]);
      ansid=i;
    }

    if (debug==1){
      cout<<calcscore(AAlist[i])<<endl;
    }

  }



  if (debug==0)
  {
    for(ll i=0;i<D;i++){
      cout<<(AAlist[ansid][i]+1)<<endl;
    }
  }else{
    cout<<calcscore(AAlist[ansid])<<endl;
  }
    

  return 0;
}

/*
1万
36万
92万
*/

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> p(n);
    int sum = 0;
    rep(i, n) {
        cin >> p[i];
        sum += p[i];
    }
    int s = 4 * m, select = 0;

    rep(i, n) {
        if(p[i] * s >= sum) {
            ++select;
        }

        if(select == m) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}


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

int main() {
    int N;
    cin >> N;
    int A[N];
    for (int i = 0; i < N; i++) cin >> A[i];
    int ans = 0;
    for (int i = 0; i < N; i += 2) {
        if (A[i] % 2 != 0) {
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3484
MOD = 1000000007
L = input()
n = len(L)
ans = 0
one = 0
for i in range(n):
    c = L[i]
    if c == '1':
        m = n - i - 1
        # print('m =', m)
        t = pow(3, m, MOD) * pow(2, one, MOD)
        # print('t =', t)
        ans += t
        ans %= MOD
        one += 1
t = pow(2, one)
ans += t
ans %= MOD
print(ans)


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

int m, n;
int w[100];

bool check(int mid){
    int tmpm = 1, nowp = 0;
    for(int i = 0; i < n; i++){
        if(mid < w[i])  return false;

        if(nowp + w[i] <= mid){
            nowp += w[i];
        }else{
            nowp = w[i];
            tmpm++;
        }
    }
    return tmpm <= m;
}

int main(){
    while(1){
        cin >> m >> n;

        if(m + n == 0)  break;

        int minp = 1000001;
        for(int i = 0; i < n; i++){
            cin >> w[i];
            minp = min(minp, w[i]); 
        }

        int l = minp, r = 1500000;

        while(r-l > 1){
            int mid = (r+l) / 2;
            if(check(mid))  r = mid;
            else            l = mid;
        }

        cout << (check(l) ? l : r) << endl;
    }

    return 0;
}


Measured memory_bytes: 3088
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
const int MOD=(int)1e9+7;
using namespace std;
int main(){
    string s;
    cin>>s;
    int ans=0;
    REP(i,3){
        if(s[i]=='o') ans++;
    }
    cout<<700+100*ans<<endl;    
}

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

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

    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (a + b > c + d)
    {
        cout << "Left" << endl;
    }
    else if (a + b == c + d)
    {
        cout << "Balanced" << endl;
    }
    else
    {
        cout << "Right" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
table = [0] * 4*3*10

n = int(input())

for i in range(n):
    b,f,r,v = map(int, input().split())
    table[30*(b-1)+10*(f-1)+(r-1)] += v

for i in range(120):
    if i != 0 and i % 30 == 0:
        print("####################")
    print(" %d" % table[i], end="")
    if i%10 == 9:
        print()


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

int g[105][105];

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

    rep(i, n) {
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1) {
            rep(i, h) rep(j, x) g[i][j] = 1;
        } else if (a == 2) {
            rep(i, h) for (int j = w; j >= x; j--) g[i][j] = 1;
        } else if (a == 3) {
            rep(i, y) rep(j, w) g[i][j] = 1;
        } else {
            for (int i = h; i >= y; i--) rep(j, w) g[i][j] = 1;
        }
    }

    int ans = 0;
    rep(i, h) rep(j, w) if (g[i][j] == 0) ans++;

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


Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int n;cin>> n;int w[n],ans1=0,ans2=0,ans=100000;
  for(int i=0;i<n;i++){
    cin>> w[i];
  }
  for(int i=1;i<n;i++){
    ans1=0;ans2=0;
    for(int j=0;j<i;j++){
      ans1+=w[j];
    }
    for(int j=0;j<n-i;j++){
      ans2+=w[n-j-1];
    }
    if(ans1-ans2<0){
    ans=min(ans,ans2-ans1);
    }else{
    ans=min(ans,ans1-ans2);
    }
  }
  cout << ans <<endl;
}

Measured memory_bytes: 256
n,m = list(map(int,input().split()))
import numpy as np
A = np.zeros([n,n]).astype(np.int)
B = np.zeros([m,m]).astype(np.int)
for i in range(n):
    A[i,:] = [1 if s == '#' else 0 for s in input()]
for i in range(m):
    B[i,:] = [1 if s == '#' else 0 for s in input()]
# print(A)
# print("---")
# print(B)
# print("---")

ans = 0
for i in range(0,n-m+1):
    for j in range(0,n-m+1):
        if (A[i:i+m,j:j+m] == B).all():
            ans = 1
            break

if ans:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 12448
n = gets.to_i

a = []
b = []

n.times{
    m, i = gets.split
    a.push([m, i.to_i])
    b.push([m, i.to_i])
}

def pertition(a, p, r)
    x = a[r][1]
    i = p - 1
    for j in p .. r - 1
        if a[j][1] <= x then 
            i += 1
            a[i], a[j] = a[j], a[i]
        end
    end
    a[i + 1], a[r] = a[r], a[i + 1]
    return i + 1
end

def quickSort(a, p, r)
    if p < r then
        q = pertition(a, p, r)
        quickSort(a, p, q-1)
        quickSort(a, q+1, r)
    end
    return a
end

a = quickSort(a, 0, a.length - 1)

stable = true
(0..n-2).each {|i|
    if a[i][1] == a[i+1][1] then
        if b.index(a[i]) > b.index(a[i+1]) then
            stable = false
            break
        end
    end
}

if stable then
    puts "Stable"
else
    puts "Not stable"
end

a.each{|k|
    puts k.join(" ")
}


Measured memory_bytes: 35372
#include<iostream>
#include<algorithm>
#include<vector>
using LL = long long;
LL INF = 1 << 30;
int N, M, R;
LL ans = INF;
LL wf[210][210];
LL rs[10];
LL inst;
int solve() {
	inst = 0;
	for (int i = 0; i < R; i++) {
		inst += wf[rs[i]-1][rs[i + 1]-1];
	}
	return 0;
}

int main() {
	std::cin >> N >> M >> R;
	for (int i = 0; i < R; i++) {
		std::cin >> rs[i];
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			wf[i][j] = INF;
		}
		wf[i][i] = 0;
	}
	for (int i = 0; i < M; i++) {
		int a, b, c;
		std::cin >> a >> b >> c;
		a--;
		b--;
		if (c < wf[a][b]) {
			wf[a][b] = c;
			wf[b][a] = c;
		}
	}
	for (int k = 0; k < N; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				wf[i][j] = std::min(wf[i][j], wf[i][k] + wf[k][j]);
			}
		}
	}
	std::sort(rs, rs+R);
	do {
		solve();
		ans = std::min(ans, inst);
	} while (std::next_permutation(rs, rs+R));

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

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;

#if DEBUG && !ONLINE_JUDGE
    ifstream input_from_file("input.txt");
    #define cin input_from_file
#else

#endif



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); // Togliere nei problemi con query online

    int N;
    cin >> N;
    vector<LL> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    LL res = 0;
    for (int i = 1; i < N; i++) {
        if (A[i] < A[i-1]) res += A[i-1]-A[i], A[i] = A[i-1];
    }
    cout << res << "\n";
}


Measured memory_bytes: 4756
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
const ll INF = 1e9 + 7;
typedef pair<int,int> P;// pair型は２つの値の組を表せる

int main(){
    int A,B; cin >> A >> B;
    rep(i,1010){
        if (floor(i*0.08)==A && floor(i*0.1)==B){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 256
/**
 * Sliding Window - The Smallest Window I
 */

#include <iostream>

using namespace std;

int main() {

    int N, S, a[100000];

    cin >> N >> S;

    for (int i = 0; i < N; i++) cin >> a[i];

    //
    int s, t, sum, ans;
    s = t = sum = 0;
    ans = N + 1;

    while (true) {
        while (t < N && sum < S) {
            sum += a[t++];
        }
        if (sum < S) break;
        ans = min(ans, t - s);
        sum -= a[s++];
    }

    if (ans > N) ans = 0;

    cout << ans << endl;
}


Measured memory_bytes: 3468
import bisect

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)

ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        tmp=a[i]+a[j]
        index=bisect.bisect_left(a,tmp)
        ans+=index-j-1

print(ans)

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

long long int getans(vector<long long int>&nums) {
	vector<long long int>sums(nums.size()+1);
	vector<vector<long long int>>anss(nums.size(), vector<long long int>(nums.size()+1));
	vector<vector<int>>ks(nums.size(), vector< int>(nums.size()+1));
	sums[0] = 0;
	for (int i = 0; i < nums.size(); ++i) {
		sums[i+1] = sums[i]+nums[i];
	}
	
	for (int i = 0; i < nums.size(); ++i) {
		for (int j = 0; j <= nums.size(); ++j) {
			anss[i][j] = 1e18;
		}
		anss[i][i+1] = 0;
		ks[i][i+1] = i;
	}
	for (int len =2; len <= nums.size(); ++len) {
		for (int l = 0; l + len <= nums.size(); ++l) {
			const int r = l + len;
			for (int c = ks[l][r - 1]; c <= ks[l + 1][r]; ++c) {
				const long long int ans = anss[l][c] + anss[c][r] + sums[r]-sums[l];
				if (anss[l][r] > ans) {
					anss[l][r] = ans;
					ks[l][r] = c;
				}
			}
		}
	}
	return anss[0][nums.size()];
}
int main() {
	int N; cin >> N;
	vector<long long int>ws(N);
	for (int i = 0; i < N; ++i)cin >> ws[i];
	const long long int ans = getans(ws);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 190836
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <functional>
#include <sstream>
#include <string>
#include <iomanip>
using namespace std;
#define LOG(x) cout << #x << " := " << (x) << endl
#define _LOG(x) cout << "Momentai " << x << endl
typedef long long ll;
typedef long double Lf;

const int max_N = 5005;

int N, K;
int ar[max_N];
int memo_l[max_N][max_N] = {}, memo_r[max_N][max_N] = {};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> K;
    for (int i = 1; i <= N; ++i) {
        cin >> ar[i];
        ar[i] = min(ar[i], K);
    }

    for (int k = 0; k <= K; ++k) for (int n = 0; n <= N; ++n) {
        if (k == 0) memo_l[n][k] = 1;
        else if (n == 0) memo_l[n][k] = 0;
        else {
            memo_l[n][k] = memo_l[n-1][k];
            if (ar[n] <= k) memo_l[n][k] = max(memo_l[n][k], memo_l[n-1][k-ar[n]]);
        }
    }

    for (int k = 0; k <= K; ++k) for (int n = N+1; n >= 1; --n) {
        if (k == 0) memo_r[n][k] = 1;
        else if (n == N+1) memo_r[n][k] = 0;
        else {
            memo_r[n][k] = memo_r[n+1][k];
            if (ar[n] <= k) memo_r[n][k] = max(memo_r[n][k], memo_r[n+1][k-ar[n]]);
        }
    }

    for (int n = 1; n <= N+1; ++n) for (int k = 1; k <= K; ++k)
        memo_r[n][k] += memo_r[n][k-1];

    int ans = 0;
    for (int n = 1; n <= N; ++n) {
        int flag = 1;
        for (int k = 0; k < K; ++k) {
            if (memo_l[n-1][k] && (k+ar[n] >= K || memo_r[n+1][K-k-1] != memo_r[n+1][K-k-1-ar[n]])) {
                flag = 0;
            }
        }
        ans += flag;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 195840
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>

using ll = long long;

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int p[n];
    for (auto &pi:p) {
        cin >> pi;
        pi += 1;
    }
    int i=0, sum=0;
    for ( ; i<k; i++) sum += p[i];
    int ans2 = sum;
    for ( ; i<n; i++) {
        sum += p[i] - p[i-k];
        ans2 = max(ans2, sum);
    }
    cout << setprecision(15) << (double)ans2 / 2. << '\n';
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define pb push_back
#define sc1(n) scanf("%lld",&n)
#define sc2(a,b) scanf("%lld%lld",&a,&b)
#define sc3(a,b,c) scanf("%lld%lld%lld",&a,&b,&c)
#define MX 100000
using namespace std;

typedef long long int ll;
typedef unsigned long long ul;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll n,k;
ll mn;
ll ans;
ll arr[105];
ll dp[100005];
ll solve(ll stone)
{
    if(stone<mn)
        return 0;
    if(dp[stone]!=-1)
        return dp[stone];
    for(ll i=1;i<=n;i++)
    {
        if(stone>=arr[i])
        {
            if(solve(stone-arr[i])==0)
                return dp[stone]=1;
        }
    }
    return dp[stone]=0;
}
int main()
{
    memset(dp,-1,sizeof dp);
    sc2(n,k);
    mn=INT_MAX;
    for(ll i=1; i<=n; i++)
    {
        sc1(arr[i]);
        mn=min(mn,arr[i]);
    }
    ans=solve(k);
    if(ans)
        printf("First\n");
    else
        printf("Second\n");
    return 0;
}


Measured memory_bytes: 4096
K,N = map(int, input().split())
A = [int(i) for i in input().split()]

ans = float("inf")
for right in range(N):
    left = right - (N - 1)
    if left >= 0:
        ans = min(ans, A[right] - A[left])
    else:
        ans = min(ans, A[right] + (K - A[left]))

print(ans)

Measured memory_bytes: 26420
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <string>
 
using namespace std;
typedef long long ll;

int main()
{
	int A, B;
	scanf("%d %d", &A, &B);
	bool solved =false;
	
	for(int i = 0; i < 12000; i++){
		if((i * 8) / 100 == A && (i * 10) / 100 == B){
			printf("%d\n", i);
			solved = true;
			break;
		}
	}
	if(!solved){
		printf("-1\n");
	}
	
	return 0;
}

Measured memory_bytes: 128
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		// 文字の入力
		char c = sc.next().charAt(0);;
		// 出力
      	int ascii;
      	ascii = (int)c;

        if(ascii>=65 && 90>=ascii) 
          System.out.println("A");
      	else 
          System.out.println("a");
	}
}

Measured memory_bytes: 35656
from math import gcd


def solve():

    K = int(input())

    rangeK = range(1, K+1)
    ans = 0

    for a in rangeK:
        for b in rangeK:
            for c in rangeK:
                ans += gcd(gcd(a, b), c)

    print(ans)


if __name__ == "__main__":
    solve()


Measured memory_bytes: 67548
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) {
    cin >> A[i];
  }
  vvi sums(21,vi(N+1,0));
  rep(i,N) {
    rep(j,21) {
      sums[j][i+1] = sums[j][i] + (A[i]>>j&1);
    }
  }
  ll ans = 0;
  rep(i,N) {
    ll m = INF;
    rep(j,21) {
      ll k = lower_bound(rng(sums[j]),sums[j][i+1]+2-(A[i]>>j&1)) - (sums[j].begin()+i+1);
      m = min(m,k);
    }
    ans += m;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 18304
#include <bits/stdc++.h>
#define REP(i, n) for (ll i = 0; i < (n); i++)
#define INF 1e9
#define MOD 1000000007
#define All(x) (x).begin(), (x).end()
typedef long long ll;
using namespace std;

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

int g_bfs(const vector<string> &v, int x, int y){
    int H = v.size(), W = v[0].size();
    vector<vector<int>> dist(H, vector<int>(W, -1));
    queue<pair<int, int>> que;

    int res = 0;
    que.push({x, y});
    dist[x][y] = 0;
    while (!que.empty()){
        int x = que.front().first, y = que.front().second;
        res = max(res, dist[x][y]);
        que.pop();
        for (int dir = 0; dir < 4; dir++){
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W)continue;
            if (v[nx][ny] == '#')continue;
            if(dist[nx][ny] == -1){
                dist[nx][ny] = dist[x][y] + 1;
                que.push({nx, ny});
            }
        }
    }
    return res;
}
int main(void){
    int H, W;
    cin >> H >> W;
    vector<string> v(H);
    for (int i = 0; i < H;i++)cin >> v[i];
    int res = 0;
    for (int x = 0; x < H; x++){
        for (int y = 0; y < W; y++){
            if(v[x][y] == '#') continue;
            res = max(res, g_bfs(v, x, y));
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 256
fun main(args: Array<String>) {

    var (L, R) = readLine()!!.split(" ").map { it.toInt() }
    if (R - L >= 2019) {
        println(0)
        return
    }
    L %= 2019
    R %= 2019
    if (L > R) {
        println(0)
        return
    }

    if (L == 0 || R == 0) {
        println(0)
        return
    }

    var min = Int.MAX_VALUE
    for (l in L until R) {
        for (r in L + 1 until R + 1) {
            min = Math.min(min, (r * l) % 2019)
        }
    }
    println(min)
    return
}



Measured memory_bytes: 37904
N,A,B = map(int,input().split())
S = input()

pass_human = 0
overseas = 0

for i in S:
    if i == "a":
        if pass_human < A+B:
            print("Yes")
            pass_human += 1
        else:
            print("No")
    elif i == "b":
        if pass_human < A+B and overseas < B:
            print("Yes")
            pass_human += 1
            overseas += 1
        else:
            print("No")
    else:
        print("No")

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

int main(){
	int e[2][4] = {};
	double a,b;
	while(1){
		cin >> a >> b;
		if(cin.eof()) break;
		if(a >= 1.1) e[0][0]++;
		else if(a >= 0.6) e[0][1]++;
		else if(a >= 0.2) e[0][2]++;
		else e[0][3]++;
		if(b >= 1.1) e[1][0]++;
		else if(b >= 0.6) e[1][1]++;
		else if(b >= 0.2) e[1][2]++;
		else e[1][3]++;
	}
	for(int i = 0;i < 4;i++) cout << e[0][i] << " " << e[1][i] << endl;
	return 0;
}

Measured memory_bytes: 1224
/*
これを入れて実行
g++ code.cpp
./a.out
 */

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
typedef long long ll;

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

const long long INF = 1LL << 60;

bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}

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

    vector<int> p(n);

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

    vector<int> sorted(n);
    for(int i = 0; i < n; i++){
        sorted[i] = p[i];
    }
    sort(sorted.begin(), sorted.end());

    bool finished = false;

    bool c = true;
    for(int i = 0; i < n; i++){
        if(p[i] != sorted[i]){
            c = false;
            break;
        }
    }

    if(c){
        cout << "YES" << endl;
        return 0;
    }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            
            vector<int> check(n);
            for(int a = 0; a < n; a++){
                check[a] = p[a];
            }

            // if(i == j)continue;

            swap(check[i], check[j]);

            bool ok = true;
            for(int a = 0; a < n; a++){
                if(check[a] != sorted[a]){
                    ok = false;
                    break;
                }
            }

            if(ok){
                finished = true;
                // cout << i << " " << j << endl;
                break;
            }

        }
        if(finished)break;
    }

    if(finished){
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }


}


Measured memory_bytes: 256
import numpy as np
a, b, h, m = map(int, input().split())
argh = 2 * np.pi * ((h + (m / 60) ) / 12)
argm = 2 * np.pi * (m / 60)
arg = abs(argh - argm)
if arg > np.pi:
    arg = 2 * np.pi - arg
print((a**2 + b**2 - 2 * a * b * np.cos(arg)) ** (1/2))

Measured memory_bytes: 27112
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i, n) for (int i = 0; i < (n); i++)
 
int main(){
    long long N,A,B;
    cin >> N >> A >> B;
    if(A%2 == B%2){
        cout << abs(A-B) / 2 << endl;
    }else{
        cout << min(A-1,N-B) + 1 + (B-A-1) / 2 << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
char  a[100010];
int main(){
    int ans=0,k;
    scanf("%s",a);
    int s=strlen(a);
    for(k=1;k<s;k++){
        if(a[k]!=a[k-1]) ans++;
    }
    printf("%d",ans);
}

Measured memory_bytes: 512
import core.bitop;
import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

void main()
{
  bool[char] set;
  foreach (c; readln.chomp)
  {
    set[c] = true;
  }
  foreach (c; 'a' .. 'z')
  {
    if (c !in set)
    {
      c.writeln;
      return;
    }
  }
  if ('z' !in set)
    "z".writeln;
  else
    "None".writeln;
}


Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O0")
typedef long long int ll;
typedef long double ld;
const ll mod = 1e9+7;
const ll INF = 1e18;
#define rep(i,n) for (ll i = 0; i < (n); ++i)
#define Rep(i,a,n) for (ll i = (a); i < (n); ++i)
#define All(a) (a).begin(),(a).end()
#define Pi acos(-1)
using Graph = vector<vector<ll>>;
using V = vector<ll>;
using P = pair<ll,ll>;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << setprecision(15) << fixed;
  chrono::system_clock::time_point start,end;
  start = chrono::system_clock::now();

  ll n;
  cin >> n;
  V a(n);
  V b(n);
  rep(i,n) {
    ll x, y;
    cin >> x >> y;
    a[i] = x+y;
    b[i] = x-y;
  }
  sort(All(a));
  sort(All(b));
  ll t = a[n-1] - a[0];
  ll s = b[n-1] - b[0];
  cout << max(t,s) << '\n';

  end = chrono::system_clock::now();
  auto elapsed = chrono::duration_cast< chrono::milliseconds >(end - start).count();
  cerr << elapsed << "ms" << '\n';
}

Measured memory_bytes: 6428
#include<stdio.h>

int main()
{
  char a[26] = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};

  int n;
  scanf("%d", &n);
  char str[10000];
  scanf("%s", str);
  int length  = strlen(str);
  int i;
  
  for(i=0;i<length;i++)
  {
    int j;
    char c = str[i];
    for(j=0;j<26;j++)
    {
      if(c == a[j])
      {
        if((j+n) > 25)
        {
        str[i] = a[j+n-26];
        }
        else
        {
            str[i] = a[j+n];
        }
        break;
      }
    }
  }
  printf("%s", str);
}

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

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

    string s;
    cin>>s;
    vector<int> v;
    for(int i=0;i<s.size();i++){
        v.push_back(s[i]-'0');
    }
    long long ans=0;
    for(int i=1;i<=s.size();i++){
        for(int j=0;j<s.size()-i+1;j++){
            long long num=0;
            for(int k=0;k<i;k++){
                num*=10;
                num+=v[j+k];
            }
            if(i==s.size()){
                ans+=num;
                continue;
            }
            if(j==0 || j==s.size()-i){
                ans+=num*pow(2,s.size()-1-i);
            }
            else ans+=num*pow(2,s.size()-i-2);
            //cout<<num<<" "<<ans<<endl;
        }
    }
    cout<<ans<<endl;

}

Measured memory_bytes: 256
from collections import Counter
from bisect import bisect_left

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
CA = Counter(A)
CB = Counter(B)

for key, value in CB.items():
    if value + CA[key] > N:
        print('No')
        exit()

C = [0] * (N+1)
D = [0] * (N+1)

for i in range(N):
    C[i + 1] += C[i] + CA[i + 1]
    D[i + 1] += D[i] + CB[i + 1]

x = 0

for i in range(N):
    x = max(x, C[i + 1] - D[i])

ans = [B[(i - x) % N] for i in range(N)]

print('Yes')
print(*ans)





Measured memory_bytes: 177676
#include<stdio.h>
#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<math.h>
#include<algorithm>
using namespace std;

#define INF 987654321
#define ll long long

string s;
int cnt[3];

int main()
{
	cin >> s;
	for (int i = 0; i < s.size(); i++)
		cnt[s[i] - 'a']++;

	if (max({ cnt[0], cnt[1], cnt[2] }) - min({ cnt[0], cnt[1], cnt[2] }) <= 1)
		cout << "YES";
	else
		cout << "NO";

	return 0;
}

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

int main() {
  string V = "aiueo";
  char c;
  int ans = 0;
  cin >> c;
  for(int i = 0; i < 5; i++){
    if(c == V.at(i)) ans++;
  }
  if(ans) cout << "vowel";
  else cout << "consonant";
}


Measured memory_bytes: 256
N, Q = map(int,input().split())
S = list(input())

dp = [float("inf") for i in range(N)]
dp[0] = 0
for i in range(1,N):
    if S[i-1] == "A" and S[i] == "C" :
        dp[i] = dp[i-1] + 1
    else :
        dp[i] = dp[i-1]
val = [[] for i in range(Q)]
for i in range(Q) :
    a,b = map(int,input().split())
    val[i] = [a-1,b-1]
for i in range(Q):
    print("{}".format(dp[val[i][1]]-dp[val[i][0]]))

Measured memory_bytes: 23608
fn solve(n: usize, a: usize, b: usize) -> usize {
    let mut result = 0;

    for x in 1..=n {
        let v: Vec<usize> = x.to_string().chars().map(|c| c as usize - 48).collect();
        let sum = v.iter().sum::<usize>();

        if a <= sum && sum <= b {
            result += x;
        }
    }
    result
}

fn main() {
    let (n, a, b) = read_tup3();

    println!("{}", solve(n, a, b));
}

fn read_tup3<T: std::str::FromStr + Copy>() -> (T, T, T) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    let v = s.trim().split_whitespace()
        .map(|c| c.parse().ok().unwrap())
        .collect::<Vec<T>>();
    (v[0], v[1], v[2])
}


Measured memory_bytes: 2112
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
using namespace std;
int inf = 1000000000;

int main(void) {

  int e;
  while(cin >> e){
    if( e == 0 ) break;
    int ans = 10000000;
    for(int z=0; z*z*z<=e; z++){
      for(int y=0; z*z*z+y*y<=e; y++){
        int x = e - z*z*z - y*y;
        if( x >= 0 ){
          ans = min(ans, x + y + z);
        }
      }
    }
    cout << ans << endl;

  }

  return 0;
}

// EOF

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

int main(){
  int a, b, c, d, e, f, g, h, i, j, n, m;
  int x=0;
  cin >> n;
  
  for(i=0;i<n;i++){
    cin >> a;
    x=0;
    j=1;
    while(1){
      b=pow(2, j);
      if(a%b==0){
        x++;
        j++;
      }
      else{
        break;
      }
    }
    if(c>x){
      c=x;
    }
  }
  cout << c << endl;
}

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

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
E = [0 for i in range(N+4)]
F = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]
for i in range(N+1):
	E[i+1] = E[i] + D[i][i]
for i in range(N+2):
	for j in range(N+2):
		F[i+1][j] = F[i][j] + D[i][j]

# C[l][l] + ... + C[l][r] = D[l][r+1] - D[l][l]
# C[i][i] + ... + C[i][r] = D[i][r+1] - D[i][i]
# C[r][r] + ... + C[r][r] = D[r][r+1] - D[r][r]

for j in range(Q):
	p,q = map(int,input().split())
	s = F[q+1][q+1] - F[p][q+1] - (E[q+1] - E[p])
	print(s)



Measured memory_bytes: 19484
#include <bits/stdc++.h>
using namespace std;
#define int64 long long
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) (a).size())

const int N = 1111;
char a[N], b[N], c[N];

int main() {
	int n, res = 0;
	scanf("%d%s%s%s", &n, a, b, c);
	for (int i = 0; i < n; ++i) {
		vector<char> v;
		v.pb(a[i]), v.pb(b[i]), v.pb(c[i]);
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
		res += sz(v) - 1;
	}
	printf("%d\n", res);
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int Inf = 1000000000;
constexpr ll INF= 1e18;
constexpr ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<int,int> P;
typedef tuple<int,int,int> TP;

template<typename T>
T Pow(T a,T b) {
    T ret = 1;
    for(int i = 0;i < b;i++) {
        ret *= a;
    }
    return ret;
}
 
ll mod(ll val) {
    ll res = val % MOD;
    if(res < 0) {
        res += MOD;
    }
    return res;
}
 
ll RS(ll N, ll P, ll M){
    if(P==0) return 1;
    if(P < 0) {
        return 0;
    }
    if(P%2==0){
        ll t = RS(N, P/2, M);
        return t*t % M;
    }
    return N * RS(N, P-1, M) % M;
}

int main() {
    string S,T;
    cin >> S >> T;
    int s = S.size();
    int t = T.size();
    vector<int> ss(s + 1);
    vector<int> tt(t + 1);
    for(int i = 0;i < s;i++) {
        if(S.at(i) == 'A') {
            ss.at(i + 1) = ss.at(i) + 1;
        }
        else {
            ss.at(i + 1) = ss.at(i) + 2;
        }
    }
    for(int i = 0;i < t;i++) {
        if(T.at(i) == 'A') {
            tt.at(i + 1) = tt.at(i) + 1;
        }
        else {
            tt.at(i + 1) = tt.at(i) + 2;
        }
    }
    int Q;
    cin >> Q;
    for(int i = 0;i < Q;i++) {
        int A,B,C,D;
        cin >> A >> B >> C >> D;
        int cnt1 = ss.at(B) - ss.at(A - 1);
        int cnt2 = tt.at(D) - tt.at(C - 1);
        if(cnt1 % 3 == cnt2 % 3) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
}

Measured memory_bytes: 1664
#include<iostream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<cmath>
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;

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

int main() {
	int n;
	cin >> n;
	string s;
	cin >> s;
    ll r=0,g=0,b=0;
    rep(i,n){
      if(s[i]=='R') r++;
      if(s[i]=='G') g++;
      if(s[i]=='B') b++;
    }
	ll ans = 0;
	ans += r*g*b;
	for (int k = 1; k <= (n - 1) / 2; k++) {
		for (int i = 0; i + 2 * k < n; i++) {
			if (s[i] != s[i + k] && s[i] != s[i + 2 * k] && s[i + k] != s[i + 2 * k]) ans--;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3640
l = [0, 0, 0, 0, 0]
for _ in range(3):
  a, b = map(int,input().split())
  l[a] += 1
  l[b] += 1
if sorted(l) == [0, 1, 1, 2, 2]:
  print("YES")
else:
  print("NO")

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

int main() {
    int n; cin >> n;
    int a[n]; for (int i = 0; i < n; ++i) cin >> a[i];
    set<int> pushed;
    
    int ans = 0, cur_btn = 1;
    while (pushed.count(cur_btn) <= 0) {
        if (cur_btn == 2) {
            cout << ans << endl;
            return 0;
        }
        pushed.insert(cur_btn); ans++;
        cur_btn = a[cur_btn - 1];
    }
    cout << -1 << endl;
}


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

int main(){
	int n,m,x;
	int ans=0x7fffffff;
	int flag=0;
	cin>>n>>m>>x;
	vector<int>c(n);
	vector<vector<int>>a(n,vector<int>(m));
	vector<int>sum(m);
	bool check=true;
	
	rep(i,m){
		sum[i]=0;
	}
	rep(i,n){
		cin>>c[i];
		rep(j,m){
			cin>>a[i][j];
		}
	}

	rep(i,1<<n){
		int sum_c=0;
		rep(j,n){
			if(i&(1<<j)){
				sum_c+=c[j];
				rep(k,m){
					sum[k]+=a[j][k];
				}
			}
		}
		rep(j,m){
			if(sum[j]<x){
				check=false;
				break;
			}
		}
		// cout<<sum_c<<endl;
		// cout<<check<<endl;
		rep(i,m){
			sum[i]=0;
		}
		if(check==true){
			if(sum_c<ans){
				ans=sum_c;
				if(flag==0)flag=1;
			}
		}
		else{
			check=true;
		}
	}
	
	if(flag==1){
		cout<<ans<<endl;
	}
	else if(flag==0){
		cout<<-1<<endl;
	}

	return 0;
}

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

int main(){  
	int N;
	string S;
	cin >> N >> S;
	int X = 0;
	int maxX = 0;
	for(int i = 0; i < N; i++){
		if(S[i] == 'I'){
			X++;
		}else if(S[i] == 'D'){
			X--;
		}
		if(maxX < X){
			maxX = X;
		}
	}
	cout << maxX << endl;
}

Measured memory_bytes: 256
'use strict';
process.stdin.on('data', function(chunk) {
  // ????????????????????????
  var inputs = chunk.toString().trim().split('\n').map(Number);
  for (var i = 0; i < inputs.length; i++) {
    if (inputs[i] === 0) {
      break;
    }
    console.log('Case ' + (i + 1) + ': ' + inputs[i]);
  }

});
process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 20572
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
int n,k;
int it[200001];
int pre[200001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=0;i<n;i++){
			cin>>it[i];
		}
	for(int i=0;i<k;i++){
		for(int j=0;j<n+1;j++){
			pre[j]=0;
		}
		for(int j=0;j<n;j++){
			pre[max(j-it[j],0)]+=1;
			pre[min(j+it[j]+1,n)]-=1;
		}
		int x=pre[0];
		int st=0;
		int su=0;
		for(int j=0;j<n;j++){
			su+=pre[j];
			if(it[j]!=x){
				st=1;
			}
			it[j]=su;
		}
		if(st==0){
			break;
		}
	}
	for(int i=0;i<n;i++){
		cout<<it[i]<<" ";
	}
	cout<<endl;


	return 0;
}

Measured memory_bytes: 5212
buildings = Array.new(4).map { Array.new(3).map { Array.new(10,0) } }

n = gets.chomp.to_i
n.times do
  line = gets.chomp.split
  b = line[0].to_i
  f = line[1].to_i
  r = line[2].to_i
  v = line[3].to_i

  buildings[b-1][f-1][r-1] += v
end

buildings.each_with_index do |floors, index|
  floors.each do |rooms|
    puts ' ' + rooms.join(' ')
  end

  puts '####################' if index < buildings.length-1
end

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

int l, r;
int main()
{
    cin >> l >> r;
    if( r - l + 1 >= 2019 ){
        cout << 0;
    }
    else{
        long long mn  = 2019;
        for( int i = l; i <= r; i ++ ){
            for( int j = i+1; j <= r; j ++ ){
                mn = min( mn, (i * 1ll * j) % 2019);
            }
        }
        cout << mn;
    }
    return 0;

}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline


class AtCoder:
    def main(self):
        N, M = map(int, input().split())
        key = []
        for _ in range(M):
            a, b = map(int, input().split())
            s = 0
            for box_num in map(int, input().split()):
                s |= 1 << (box_num - 1)
            key.append([a, s])

        INF = 100100100
        dp = [INF] * (1 << N)
        dp[0] = 0
        for s in range(1 << N):
            for i in range(M):
                t = s | key[i][1]
                cost = dp[s] + key[i][0]
                dp[t] = min(dp[t], cost)

        ans = dp[-1]
        if ans == INF:
            print(-1)
        else:
            print(ans)


# Run main
if __name__ == '__main__':
    AtCoder().main()


Measured memory_bytes: 40560
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;

int main()
{
	int n, k;
	cin >> n >> k;
	auto v = vector<int>(n);
	auto lsum = vector<int>(n + 1), rsum = vector<int>(n + 1);
	for(auto&& vv : v) cin >> vv;
	for(auto i = 1; i <= n; ++i){
		lsum[i] += lsum[i - 1] + v[i - 1];
		rsum[i] += rsum[i - 1] + v[n - i];
	}
	int ans = 0;
	auto lq = priority_queue<int, vector<int>, greater<int>>();
	for(auto l = 0; l <= n; ++l){
		if(l > k) break;
		if(l > 0 && v[l - 1] < 0) lq.push(v[l - 1]);
		auto rq = lq;
		for(auto r = 0; r <= n; ++r){
			if(l + r > n || l + r > k) break;
			if(r > 0 && v[n - r] < 0) rq.push(v[n - r]);
			int sum = lsum[l] + rsum[r];
			int rem = k - l - r;
			auto tq = rq;
			while(rem > 0 && !tq.empty()){
				sum -= tq.top();
				tq.pop();
				--rem;
			}
			ans = max(ans, sum);
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N, M = map(int, input().split())
kss = []
for i in range(1, M+1):
    ks = list(map(int, input().split()))
    kss.append(ks)
biases = list(map(int, input().split()))

active_switches = set()
for i in range(0, M):
    # でんきゅうiがつくかどうか
    for j in range(1, kss[i][0] + 1):
        active_switches.add(kss[i][j])

import itertools

def is_lit(m, s, sw, b):
    total = b
    for val in s:
        if val in sw:
            total += 1
    return total%2 == 0


def is_all_lit(sw):
    return all([is_lit(ks[0], ks[1:], sw, biases[idx]) for idx, ks in enumerate(kss)])

answer = 0
for i in range(0, len(active_switches)+1):
    c = itertools.combinations(active_switches, i)
    result = map(is_all_lit, c)
    answer += sum(result)

import math
answer *= int(math.floor(math.pow(2, N - len(active_switches))))

print(answer)

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000000
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=1e5+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,k,t;
ll dp[51][2501];
int a,now;
ll ans;
int main()
{
    int i,j;
    dp[0][0]=1;
    scanf("%d%d",&n,&a);
    rep(i,1,n)
    {
        scanf("%d",&k);
        now+=k;
        for(j=i;j>=1;j--)
            for(t=now;t>=k;t--)
                dp[j][t]+=dp[j-1][t-k];
    }
    rep(i,1,n)ans+=dp[i][a*i];
    printf("%lld\n",ans);
    //system("Pause");
    return 0;
}

Measured memory_bytes: 1280
#include <iostream>

int main(int argc, char const *argv[]) {
    int A,B; std::cin >> A >> B;

    if (A==1) {
        A=14;
    }
    if (B==1) {
        B=14;
    }
    if (A>B) {
        std::cout << "Alice" << '\n';
    }else if(A<B){
        std::cout << "Bob" << '\n';
    }else{
        std::cout << "Draw" << '\n';
    }
    return 0;
}


Measured memory_bytes: 256
H, W = map(int, input().split())
ar = []
for i in range(H):
    ar.append([i for i in input().split()])

ar_true = []
for i in range(H):
    if ar[i] != ['.'*W]:
        ar_true.append(ar[i])

ar_res_line = []
n_length = len(ar_true)
for i in range(W):
    flag = False
    for ii in range(n_length):
        if ar_true[ii][0][i] == '#':
            flag = True
    if flag:
        ar_res_line.append(i)

ar_res = []
for h in range(n_length):
    tmp = ''
    for i in range(len(ar_res_line)):
        tmp_line = ar_res_line[i]
        tmp += ar_true[h][0][tmp_line]
    ar_res.append(tmp)

for i in range(n_length):
    print(ar_res[i])

Measured memory_bytes: 3064
#include<stdio.h>
int main(void)
{
    int  a,b,c,x,y;
	long long i;
	while(scanf("%d %d",&a,&b)!=EOF){
		i=(long long)a*b;
		if(a<b){
			c=a;
			a=b;
			b=c;
		}
		c=a%b;
		while(c!=0){
			a=b;
			b=c;
			c=a%b;
		}
		i=(long long)i/b;
		printf("%d %lld\n",b,i);
	}
	return 0;
}

Measured memory_bytes: 2684
#include <bits/stdc++.h>
#define f first
#define s second
#define MOD 1000000007
#define PMOD 998244353
#define pb(x) push_back(x)
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> plii;
typedef pair<int, pii> piii;
const int INF = 1e9+10;
const ll LINF = 1LL*INF*INF;
const int MAXN = 2e5+10;
const int MAXM = 5e3+10;

priority_queue<int> pq;
vector<vector<int> > graph;
queue<int> que;

int A[MAXN];
char S[MAXN];

int main()
{
    int n,m,k,a,b,x,y,q;
    int sum = 0;
    int cnt = 0;
    int mx = 0;
    int mn = INF;
    int cur = 0, idx = -1;
    int tc;

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

    cin>>n>>m>>k;

    int vv = max(n,m);
    int res = (k+vv-1)/vv;

    cout<<res<<"\n";


    return 0;
}


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

int main() {
  
  string N;
  cin >> N;
  N.push_back('x');
  int count = 0;
  for(int first=0; first<N.size(); first++){
    int len = 0;
    while(true){
      if(N.at(first+len)=='A'||N.at(first+len)=='C'||N.at(first+len)=='G'||N.at(first+len)=='T'){
        len++;
      }
      else{break;}
    }
    if(count<len){count = len;}
  }
  
  cout << count << endl;
  
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repe(i, n) for (int i = 0; i <= (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
typedef long long ll;
const int INF = 1e9;
const ll mod = 1000000007;
int gcd(int a,int b){return b?gcd(b,a%b):a;}

int main() {
  char c[2][3];
  rep(i,2) rep (j,3) cin >> c[i][j];
  if (c[0][0] == c[1][2] && c[0][1] == c[1][1] && c[0][2] == c[1][0]) {
    cout << "YES" << "\n";
  } else {
    cout << "NO" << "\n";
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int cnt[10001];
int main(){
	int a,b,c,d;
	string str = "";
	char fir;
	cin >> a >> b >> c >> d;
	if(a == 1)cnt[1]++;
	if(b == 1)cnt[1]++;
	if(c == 1)cnt[1]++;
	if(d == 1)cnt[1]++;
	if(a == 9)cnt[2]++;
	if(b == 9)cnt[2]++;
	if(c == 9)cnt[2]++;
	if(d == 9)cnt[2]++;
	if(a == 7)cnt[3]++;
	if(b == 7)cnt[3]++;
	if(c == 7)cnt[3]++;
	if(d == 7)cnt[3]++;
	if(a == 4)cnt[4]++;
	if(b == 4)cnt[4]++;
	if(c == 4)cnt[4]++;
	if(d == 4)cnt[4]++;
	if(cnt[1] == 1 && cnt[2] == 1 && cnt[3] == 1 && cnt[4] == 1)cout << "YES";
	else cout << "NO";

	
	return 0;
}

Measured memory_bytes: 384