akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include<cstdlib>
#include<queue>
#include<set>
#include<vector>
#include<string>
#include<algorithm>
#include<stack>
#include<map>
#include<cstdio>
using namespace std;
#define rep(i,a) for(int i=0;i<a;i++)
#define mp make_pair
#define pb push_back
#define P pair<int,int>
#define ll __int64
#define ll long long
ll k;
int n;
ll a[100];

int main(){
	cin>>k;

		n=50;
		rep(i,n)a[i]=49+k/50;
		rep(i,k%50){
			rep(j,n){
				if(i==j)
				a[j]+=n;
				else a[j]--;
		}
	}
	cout<<n<<endl;
	rep(i,n){
		cout<<a[i];
		if(i==n-1)cout<<endl;
		else cout<<" ";
	}

	return 0;
}


Measured memory_bytes: 256
def c_zigzag(N, V):
    from collections import Counter
    count_seq_even = Counter(V[::2])  # 数列の(0-indexedで)偶数番目の要素の出現頻度
    count_seq_odd = Counter(V[1::2])  # 出現頻度(奇数番目)

    count_seq_even_s = sorted(count_seq_even.items(), key=lambda x: x[1], reverse=True)
    count_seq_odd_s = sorted(count_seq_odd.items(), key=lambda x: x[1], reverse=True)

    # 偶数番目からなる数列と奇数番目からなる数列のそれぞれについて、
    # 基本的には最も出現回数の多い要素に書き換えればいい。
    # ただし、それらの要素が一致する場合は書き換えられないので、
    # 2番目に出現回数の多い要素も(あれば)調べておく。(それ以下は見る必要はない)
    seq_even_select = [count_seq_even_s[k][0] for k in range(min(2, len(count_seq_even)))]
    seq_odd_select = [count_seq_odd_s[k][0] for k in range(min(2, len(count_seq_odd)))]

    ans = float('inf')
    # 両方の数列についてそれぞれ1種の要素しかなく、かつそれらが一致する
    # (全要素が等しい値)場合は、奇数番目か偶数番目かどちらかの要素を
    # すべて書き換えなければならない
    if len(seq_even_select) == 1 and len(seq_odd_select) == 1 and seq_even_select[0] == seq_odd_select[0]:
        return N // 2

    for e in seq_even_select:
        for o in seq_odd_select:
            if e == o:
                continue
            ans = min(ans, N - count_seq_even[e] - count_seq_odd[o])
    return ans

N = int(input())
V = [int(i) for i in input().split()]
print(c_zigzag(N,V))

Measured memory_bytes: 21008
n, m, x, y = map(int, input().split())
xlst = [int(i) for i in input().split()]
ylst = [int(i) for i in input().split()]

xcon = max(xlst)
ycon = min(ylst)

anslst = [int(i) for i in range(x+1, y+1)]

for i in anslst:
    if i > x and i <= y:
        if i > xcon and i <= ycon:
            print('No War')
            exit()
else:
    print('War')
    exit()

Measured memory_bytes: 3064
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);
void prime_map(map<ll, ll> &, ll);

int main() {
    // source
    string o, e;
    cin >> o >> e;
    string n = "";
    if (o.size() == e.size()) {
        rep(i, o.size()) {
            n += o[i];
            n += e[i];
        }
    } else {
        rep(i, e.size()) {
            n += o[i];
            n += e[i];
        }
        n += o[o.size() - 1];
    }

    cout << n << endl;
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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

void prime_map(map<ll, ll> &m, ll num) {
    ll cache = num;
    repd(i, 2, sqrt(num) + 2) {
        if (num % i == 0) {
            if (m[i] == 0) {
                m[i] = 1;
            } else {
                m[i]++;
            }

            num /= i;
            break;
        }
    }

    if (cache == num) {
        if (m[num] == 0) {
            m[num] = 1;
        } else {
            m[num]++;
        }
        return;
    } else {
        prime_map(m, num);
    }
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int c[3][3];
int a[3],b[3];
int main(){
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>c[i][j];
        }   
    }   
    for(int i=0;i<3;i++) b[i]=c[0][i];        
    bool x=((c[1][0]-b[0])==(c[1][1]-b[1]))&( (c[1][0]-b[0])==(c[1][2]-b[2]));                                                          
    bool y=((c[2][0]-b[0])==(c[2][1]-b[1]))&((c[2][0]-b[0])==(c[2][2]-b[2]));
    cout<<(x&y?"Yes":"No")<<"\n";
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys

YES = "YES"  # type: str
NO = "NO"  # type: str


def solve(A: int, B: int, X: int):
    return YES if A <= X < (A+B) else NO


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    A = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    print(solve(A, B, X))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()


Measured memory_bytes: 3064
import operator

vals = input()
nums = list(map(int, tuple(vals)))

def dump(a,b,c):
    if a == operator.add:
        a = '+'
    else:
        a = '-'
    if b == operator.add:
        b = '+'
    else:
        b = '-'
    if c == operator.add:
        c = '+'
    else:
        c = '-'
    print(vals[0] + a + vals[1] + b + vals[2] + c + vals[3] + '=7')

for a in (operator.add, operator.sub):
    for b in (operator.add, operator.sub):
        for c in (operator.add, operator.sub):
            if c(b(a(nums[0], nums[1]), nums[2]), nums[3]) == 7:
                dump(a, b, c)
                exit(0)

Measured memory_bytes: 9160
#-*- coding: utf-8 -*-

def main():
    s = raw_input()

    for i, c in enumerate(list(s)):
        # loop前から、検索は後ろからなので
        # インデックスが異なる場合、複数アルファベットが存在
        if s.rfind(c)!=i:
            print 'no'
            return 0
            
    print 'yes'

if __name__ == '__main__':
    main()

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vint;
typedef vector<double> vd;
typedef vector<ll> vll;
typedef vector<string> vstr;
typedef vector<vector<int>> vvint;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<ll, ll>> vpll;
typedef priority_queue<int, vector<int>, greater<int>> spqint; //小さい順に取り出し
typedef priority_queue<ll, vector<ll>, greater<ll>> spqll;     //小さい順に取り出し
typedef priority_queue<int, vector<int>, less<int>> bpqint;    //大きい順に取り出し
typedef priority_queue<ll, vector<ll>, less<ll>> bpqll;        //大きい順に取り出し

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, a, b) for (ll i = (ll)a; i < (ll)b; i++)
#define IREP(i, v) for (auto i = (v).begin(); i != (v).end(); i++)
#define FI first
#define SE second
#define MP make_pair
#define MT make_tuple
#define PB push_back
#define PF push_front
#define TS to_string
#define BS binary_search
#define LB lower_bound
#define UB upper_bound
#define NP next_permutation
#define ALL(v) (v).begin(), (v).end()
#define SZ(x) (ll) x.size()
#define SP(x) setprecision((ll)x)


int INF = 1e9;
int NIL = -1;
ll MOD = 1000000007;
ll LINF = 1e18;
double EPS = 1e-9;
double PI = M_PI;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; } //最大公約数
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }     //最小公倍数

void yes(){ cout << "Yes" << endl;}
void no(){ cout << "No" << endl;}
//-----------------------------------------

//-----------------------------------------
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::chrono::system_clock::time_point start,end;
    start = std::chrono::system_clock::now();
    int n ;
    cin >> n ;
    set<int> Set ;
    ll sum = 0 ;
    REP(i,n){
        ll a ;
        cin >> a ;
        sum += a ;
        Set.insert(a) ;
    }
    auto mini = Set.begin() ;
    auto maxi = Set.rbegin() ;
    cout << (*mini) <<" " << (*maxi) <<" " << sum <<endl;


    end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(end - start).count();
    //std::cout << elapsed <<"ms"<< std::endl;

    

    return 0;
}




Measured memory_bytes: 3612
import math

n, m = map(int, input().split(' '))
if n >= 2:
    ret_n = n * (n - 1) / 2
else:
    ret_n = 0

if m >= 2:
    ret_m = m * (m - 1) / 2
else:
    ret_m = 0

print(int(ret_n + ret_m))


Measured memory_bytes: 2940
import collections

N = int(input())
A = [int(i) for i in input().split()]

c = collections.Counter(A)

def count_list(c):
    modify = {}
    ret = 0
    for k, v in c.items():
        a = v*(v-1)//2
        b = (v-1)*(v-2)//2
        ret += a
        modify[k] = -a + b
    return ret, modify

counts, modify = count_list(c)
for a in A:
    print(counts + modify[a])


Measured memory_bytes: 32028
#include <bits/stdc++.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    int n,m;
    cin>>n>>m;
    bool mat[n][n]={};
    rep(i,m){
        int t,s;
        cin>>t>>s;
        t--;s--;
        mat[t][s]=mat[s][t]=true;
    }
    vector<int> v(n-1,0);
    rep(i,n-1){
        v[i]=i+1;
    }
    DEBUG{
        rep(i,n-1){cout << v[i] << " ";}
        cout << endl;
    }
    int res=0;
    do {
        bool flg=true;
        int now=0;
        for(auto x:v){
            DEBUG{
                cout << "x: " << x << " now: " << now<<endl;
            }
            if(!mat[now][x]){
                flg=false;
                break;
            }
            now=x;
        }
        if(flg){res++;}
    }while(next_permutation(v.begin(), v.end()));
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
#include <ctime>
#include <bitset>
#include <complex>
#include <chrono>
#include <random>
#include <functional>

using namespace std;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
typedef long long ll;

using ipair = pair<int, int>;

ll INF = 1e16+7;
ll mod = 1e9+7;

bool operator>(const ipair a,const ipair b){return a.first > b.first;}


const double PI=3.14159265358979323846;

int N, K;

int one_side_ans(vector<int> minus, vector<int> plus){
  int L = sz(minus);
  int R = sz(plus);

  if(L==0){
    return plus[K-1];
  }

  if(R==0){
    return minus[K-1];
  }

  int ret = 1e9;
  
  int minus_s = min(L, K);

  // Lから0こ取る場合
  if(R >= K){
    ret = min(ret, plus[K-1]);
  }

  // Lから１個以上取る場合
  for(int l=minus_s; l>=0; --l){
    // check
    int rest_r = K - l;
    if(rest_r > R){
      break;
    }

    // Lからl個(折返し), Rから(K-l)個取る
    int tmp_ret = minus[l-1] * 2 + plus[rest_r-1];

    ret = min(ret, tmp_ret);
  }


  return ret;
}

int main(){
  cin >> N >> K;
  vector<int> minus;
  vector<int> plus;
  rep(i, N){
    int tmp;
    cin >> tmp;
    if(tmp == 0){
      K--;
    }else if(tmp < 0){
      minus.push_back(-tmp);
    }else{
      plus.push_back(tmp);
    }
  }

  if(K==0){
    cout << 0 << endl;
    return 0;
  }

  sort(minus.begin(), minus.end());

  int ans = 1e9;
  ans = min(ans, one_side_ans(minus, plus));
  ans = min(ans, one_side_ans(plus, minus));

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1148
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//String s = sc.next();
		long n = sc.nextLong();
		long m = sc.nextLong();
		long k = sc.nextLong();

		if(n==m) {
			System.out.println(k);
		}else if(m==k){
			System.out.println(n);
		}else {
			System.out.println(m);
		}
		//System.out.println(n*n-m);
	}
}




Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;

ll powmod(ll x, ll y) {
  ll res=1;
  for(ll i=0; i<y; ++i) res=res*x%MOD;
  return res;
}

int main() {
  int N; cin>>N;
  ll ans=0;
  ans+=powmod(10,N);
  ans=(ans-powmod(9,N)+MOD)%MOD;
  ans=(ans-powmod(9,N)+MOD)%MOD;
  ans=(ans+powmod(8,N)+MOD)%MOD;
  cout << ans << endl;
}


Measured memory_bytes: 3616
#include<bits/stdc++.h>
#define update(a,b,c) if(dp[a][b]<c)dp[a][b]=c,q.push({a,b})
using namespace std;
struct edge{int v,w;};
int n,m,dp[70001][21],sum,cost[70001];
vector<edge> w[21];
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		x--;y--;
		w[x].push_back({y,z});
		w[y].push_back({x,z});
		sum+=z;
	}
	for(int s=0;s<(1<<n);s++)
		for(int i=0;i<n;i++)
			if(s&(1<<i))
				for(edge j:w[i])
					if(s&(1<<j.v))cost[s]+=j.w;
	for(int s=0;s<(1<<n);s++)cost[s]/=2;
	memset(dp,-1,sizeof dp);
	dp[1][0]=0;
	queue<pair<int,int> > q;
	q.push({1,0});
	while(!q.empty())
	{
		int s=q.front().first,u=q.front().second,ss=((1<<n)-1)^s;q.pop();
		for(edge j:w[u])
			if(~s&(1<<j.v))update(s^(1<<j.v),j.v,j.w+dp[s][u]);
		for(int t=ss;t;t=(t-1)&ss)
			if(~t&(1<<u))update(s^t,u,cost[t^(1<<u)]+dp[s][u]);
	}
	int ans=1<<30;
	for(int i=0;i<(1<<n);i++)ans=min(ans,sum-dp[i][n-1]);
	printf("%d\n",ans);
	return 0;
}


Measured memory_bytes: 8576
#include<bits/stdc++.h>
using namespace std;
#define int long long 
//using int128 = __int128;
typedef long long ll;
typedef pair<int,int>pi;
typedef vector<int>vi;
const int MAXN=200005;
const int MOD=1000000007;

#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())
#define UP(v,x) (upper_bound(all(v),(x))-(v).begin())

int N, A[MAXN], B[MAXN];
map<pi, int> M;
pi reduce(pi x){
	bool sign = (x.first>=0)^(x.second>=0);
	x.first = abs(x.first);
	x.second = abs(x.second);
	int d = __gcd(x.first, x.second);
	
	int num = x.first/d;
	int denom = x.second/d;
	
	if (!sign) return {num,denom};
	else return {-num,denom};
}

pi inverse(pi x){
	bool sign = (x.first>=0)^(x.second>=0);
	x.first = abs(x.first);
	x.second = abs(x.second);
	if (!sign) return {-x.second, x.first};
	else return {x.second, x.first};
}

ll qmult(ll X, ll Y, ll M) {    
    return X * Y % M;
}

ll qexp(ll A, ll B, ll M) {
    if (B == 0) return 1;
    ll half = qexp(A, B/2, M); 
    half = qmult(half, half, M); 
    half %= M;
    if (B%2==1) half *= A%M;
    return half%M;
}

int type0, type1, type2;

main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>N;
	FOR(i,1,N) cin>>A[i]>>B[i];
	FOR(i,1,N) {
		if (A[i] ==0 && B[i] == 0) type0++;
		else if (A[i] == 0) type1++;
		else if (B[i] == 0) type2++;
		else M[reduce({A[i],B[i]})]++;
		
		//p = inverse(p);
		//cout<<p.first << " "<<p.second<<"\n";
	}
	//db(type0), db(type1), db(type2);
	int ans = 1;
	if (type1) ans += qexp(2, type1, MOD)-1, ans%= MOD;
	if (type2) ans += qexp(2, type2, MOD)-1, ans%= MOD;
	for (auto x:M){
		//cout<<x.first.first<<" " << x.first.second<<"\n";
		if (x.second == 0) continue;
		pi inv = inverse(x.first);
		int tmp = (qexp(2,x.second,MOD) + qexp(2, M[inv], MOD) - 1)%MOD;
		ans *= tmp;
		ans %= MOD;
		M[inv] = 0;
	}
	ans--;
	ans += type0;
	cout<<(ans+MOD)%MOD;
	
}


Measured memory_bytes: 31668
N, M, K = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)
B = gets.split.map(&:to_i)

c = -1
as = 0

ai = 0

As = Array.new(N + 1, 0)
N.times do |i|
    as += A[i]
    if as <= K then
        ai = i + 1
        As[ai] = as
    else break; end
end
c = ai

bs = 0
M.times do |bi|
    none = false
    bs += B[bi]
    until bs + As[ai] <= K do
        if ai == 0 then
            none = true
            break
        end
        ai -= 1
    end
    break if none
    ctmp = ai + bi + 1
    c = ctmp if ctmp > c
end

puts c


Measured memory_bytes: 43308
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    	Scanner sc = new Scanner(System.in);
    	try {
    		final int n = sc.nextInt();
    		final int m = sc.nextInt();

    		int [] s = new int[m];
    		char [] c = new char[m];
    		for (int i=0; i<m; i++) {
    			s[i] = sc.nextInt();
    			c[i] = sc.next().charAt(0);
    		}

    		if (n == 1 && m == 0) {
    			System.out.println(0);
    			return;
    		}

    		char [] str = new char[n];
    		boolean [] modified = new boolean[n];
    		str[0] = '1';
			modified[0] = false;
    		for (int i=1; i<n; i++) {
    			str[i] = '0';
    			modified[i] = false;
    		}

    		for (int i=0; i<m; i++) {
    			if (modified[s[i]-1] && str[s[i]-1] != c[i]) {
        			System.out.println("-1");
        			return;
    			} else {
        			str[s[i]-1] = c[i];
        			modified[s[i]-1] = true;
    			}
    		}

    		if (n > 1 && str[0] == '0') {
    			System.out.println("-1");
    		} else {
        		for (int i=0; i<n; i++) {
        			System.out.print(str[i]);
        		}
        		System.out.println();
    		}

    	} finally {
    		sc.close();
    	}
    }
}


Measured memory_bytes: 23764
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<map>
#include<iomanip>
#include<sstream>
#include<vector>
using namespace std;



int main() {
	//cout << fixed << setprecision(10);
	long long int a, b, c, d, n, m, k[100] = {}, x[100][100] = {}, like[100] = {},res=0;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> k[i];
		for (int j = 0; j < k[i]; j++) {
			cin >> x[i][j];
			like[x[i][j]]++;
		}
	}
	for (int i = 1; i <= m; i++) {
		if (like[i] == n) { res++; }
	}
	cout << res;
}

Measured memory_bytes: 384
#include<iostream>

using namespace std;

int main() {
	int a[13] = { 0,1,3,1,2,1,2,1,1,2,1,2,1 };
	//同じグループには同じ数字 1から12  a[0]は実際なんでもいい
	int x, y; cin >> x >> y;

	if (a[x] == a[y]) {
		cout << "Yes";
	}
	else { cout << "No"; }

	return 0;
}

Measured memory_bytes: 256
S = input()
K = int(input())

l = len(S)

MOD = 1000000007

# [桁数][未満][0でない数の合計数]
dp = [[[0] * (l + 1) for _ in range(2)] for _ in range(l + 1)]


# 初期化
dp[0][False][0] = 1

for i in range(l):
    cur = int(S[i])

    for j in range(i + 1):
        # true -> true
        for k in range(10):
            if k == 0:
                dp[i + 1][True][j] += dp[i][True][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][True][j]

        # false -> true
        for k in range(cur):
            if k == 0:
                dp[i + 1][True][j] += dp[i][False][j]
            else:
                dp[i + 1][True][j + 1] += dp[i][False][j]

        # false -> false
        if cur == 0:
            dp[i + 1][False][j] += dp[i][False][j]
        else:
            dp[i + 1][False][j + 1] += dp[i][False][j]

if K > l:
    print(0)
else:
    print(dp[l][True][K] + dp[l][False][K])


Measured memory_bytes: 3428
#include<iostream>
#include<algorithm>
using namespace std;
static const int MAX = 200000;

int main() {
	int R[MAX], n;

	cin >> n;
	for (int i = 0; i < n; i++)cin >> R[i];

	int maxv = -2000000000;
	int minv = R[0];

	for (int i = 1; i < n; i++) {
		maxv = max(maxv, R[i] - minv);
		minv = min(minv, R[i]);
	}

	cout << maxv << endl;

	return 0;
}

Measured memory_bytes: 3856
a = int(input())
b = [int(input()) for _ in range(a)]
c = 0
d = 1
while True:
    c += 1
    if b[d-1] == 2:
        print(c)
        exit()
    elif c > a:
        print(-1)
        exit()
    else:
        d = b[d-1]


Measured memory_bytes: 7084
#include <bits/stdc++.h>
using namespace std;
#define rep(i,c,n) for(int i=c;i<n;i++)
 
int main() {
  int n,ans=0;
  cin>>n;
  
  vector<int> human(n);
  vector<int> qa(n);
  vector<vector<int>> torf1(n, vector<int>(n));
  vector<vector<int>> torf2(n, vector<int>(n));
  
  rep(i,0,n){
    cin>>qa[i];
    //cout<<qa[i]<<endl;
    rep(j,0,qa[i]){
      cin>>torf1[i][j]>>torf2[i][j];
      //cout<<torf1[i][j]<<torf2[i][j];
    }
    //cout<<endl;
  }
  
  /*cout<<123<<endl;
  for(int i=0;i<(1<<n);i++){
    rep(j,0,n){
      int tmp;
      tmp=(i>>j)&1;
      cout<<tmp;
    }
    cout<<endl;
  }*/
  
  for(int i=0;i<(1<<n);i++){
    bool empty=true;
    int cnt=0;
    rep(j,0,n){
      if(!(i&(1<<j))){continue;}
      rep(k,0,qa[j]){
        //誰がj誰にtorf1何をtorf2
        int tmp;
        tmp=(i>>torf1[j][k]-1)&1;
        //cout<<tmp<<" ";
        if(((i>>(torf1[j][k]-1))&1)!=torf2[j][k]){empty=false;}
        if(((i>>(torf1[j][k]-1))&1)!=torf2[j][k]){empty=false;}
        //cout<<torf1[j][k]<<" "<<torf2[j][k]<<" "<<empty<<" "<<i<<endl;
      }
    }
    if(empty==1){ans=max(ans, __builtin_popcount(i));}
    //cout<<endl;
  }
   
  cout<<ans<<endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

const int kMax_N = 51;
char fieldL[kMax_N + 1][kMax_N + 1];
char fieldR[kMax_N + 1][kMax_N + 1];
bool checked[kMax_N + 1][kMax_N + 1][kMax_N + 1][kMax_N + 1];


const int dyL[] = { -1, 0, 1, 0 };
const int dxL[] = { 0, 1, 0, -1 };
const int dyR[] = { -1, 0, 1, 0 };
const int dxR[] = { 0, -1, 0, 1 };

int w, h;


struct Search {
  int ly, lx;
  int ry, rx;
  Search() = default;
  Search(int a, int b, int c, int d):
    ly(a), lx(b), ry(c), rx(d) { }
};
int main() {
  while (true) {
    cin >> w >> h;
    if (w + h == 0) {
      break;
    }
    int ly, lx, ry, rx;
    for (int i = 0; i < h; i++) {
      string strL, strR;
      cin >> strL >> strR;
      for (int j = 0; j < w; j++) {
        fieldL[i][j] = strL[j];
        fieldR[i][j] = strR[j];
        if (strL[j] == 'L') {
          ly = i; lx = j;
        }
        if (strR[j] == 'R') {
          ry = i; rx = j;
        }
      }
    }

    memset(checked, false, sizeof(checked));

    queue<Search> que;
    que.emplace(ly, lx, ry, rx);
    bool ok = false;
    while (!que.empty()) {
      Search s = que.front(); que.pop();
      if (fieldL[s.ly][s.lx] == fieldR[s.ry][s.rx] && fieldL[s.ly][s.lx] == '%') {
        ok = true;
        break;
      }
      if (fieldL[s.ly][s.lx] == '%') {
        continue;
      }
      if (fieldR[s.ry][s.rx] == '%') {
        continue;
      }
      if (checked[s.ly][s.lx][s.ry][s.rx]) {
        continue;
      }
      checked[s.ly][s.lx][s.ry][s.rx] = true;
      for (int i = 0; i < 4; i++) {
        int nly = s.ly + dyL[i];
        int nlx = s.lx + dxL[i];
        int nry = s.ry + dyR[i];
        int nrx = s.rx + dxR[i];
        if (nly < 0) nly = 0;
        if (nly >= h) nly = h - 1;
        if (nlx < 0) nlx = 0;
        if (nlx >= w) nlx = w - 1;
        if (nry < 0) nry = 0;
        if (nry >= h) nry = h - 1;
        if (nrx < 0) nrx = 0;
        if (nrx >= w) nrx = w - 1;
        if (fieldL[nly][nlx] == '#') {
          nly = s.ly; nlx = s.lx;
        }
        if (fieldR[nry][nrx] == '#') {
          nry = s.ry; nrx = s.rx;
        }
        que.emplace(nly, nlx, nry, nrx);
      }
    }
    if (ok) {
      cout << "Yes" << endl;
    } else {
      cout << "No" << endl;
    }
  }


  return 0;
}

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

int main(){
	int R = 0;
	cin >> R;
	string code;

	if( R < 1200 ){
		code = "ABC";
	}else if( R < 2800 ){
		code = "ARC";
	}else{
		code = "AGC";
	}

	cout << code << endl;
	return 0;
}

Measured memory_bytes: 256
import sys

input = sys.stdin.readline


def main():
    N, K = map(int, input().split())

    ans = 0
    for n in range(1, N + 1):
        cnt = 0
        while n < K:
            n *= 2
            cnt += 1
        ans += (1 / 2 ** cnt)

    ans /= N
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9120
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
int main(){
    int n;
    cin>>n;
    vector<int> a(n);
    rep(i,n){
        cin>>a[i];
        a[i]--;
    }
    int ans=0;
    rep(i,n){
        if(a[a[i]]==i){
            ans++;
        }
    }
    cout<<ans/2<<endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#include<vector>
#define ll long long
#define boostUP ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define fsr(i,n) for(int i=0;i<n;i++)
#define fcr(i,a,b) for(int i=a;i<b;i++)
#define pb push_back
#define sz(arr) sizeof(arr)/sizeof(arr[0])

using namespace std;

int main(){
    int h,n;
    cin >> h >> n;
    int arr[n];
    fsr(i,n) cin >> arr[i];
    int sum = 0;
    fsr(i,n) sum += arr[i];
    if(sum >= h)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}



 







 

Measured memory_bytes: 3860
#include<bits/stdc++.h>
using namespace std;
int main()
{
  string s;
  cin>>s;
  string s1("AAA");
  string s2("BBB");
  if(s.compare(s1)==0 || s.compare(s2)==0)
    cout<<"No";
  else
    cout<<"Yes";
  return 0;
}

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

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 1e5 + 5;

ll n,a,b;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n;
  if (n == 1) {
    cout << "Hello World" << endl;
  }
  else {
    cin >> a >> b;
    cout << a + b << endl;
  }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
 
 
int main()
{
  int a,b;
  cin>>a>>b;
  
  int c[10000];
  for(int i=1;i<=b;i++)
  {
    cin>>c[i];
  }
  int sum=0;
  for(int i=1;i<=b;i++)
  {
    sum=sum+c[i];
  }
  int k=a-sum;
  if(k>=0)
    cout<<k<<endl;
  else
    cout<<"-1"<<endl;
  
  
  
    
    return 0;
}


Measured memory_bytes: 3652
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>

using namespace std;

int main()
{
   int a,b;
   cin>>a>>b;
   double c=(a+b)/2.0;
   int cc=c;
   if(cc==c)
   {
       cout<<cc<<endl;
   }
   else
    cout<<"IMPOSSIBLE"<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long k,sum=0;
	cin>>k;
	for(long long i=1;i<=k;i++){
		for(long long j=1;j<=k;j++){
			for(long long q=1;q<=k;q++){
				sum+=__gcd(i,__gcd(j,q));
			}
		}
	}
	cout<<sum<<endl;
	return 0;
}

Measured memory_bytes: 3636
#include<iostream>
using namespace std;
int i, p, sumA=0, sumB=0;
int main(){
    for (i=1; i<=4; i++) {
        cin >> p;
        sumA += p;
}
for (i=1; i<=4; i++) {
cin >> p; sumB += p;
}
cout << max(sumA, sumB) << endl;
return 0;
}

Measured memory_bytes: 3080
n = int(input())
li = [chr(i) for i in range(ord('a'), ord('z') + 1)]
result=[]
n = n - 1

while True:
    s, t = n//26, n%26
    result.append(li[t])
    if s == 0:
        result = result[::-1]
        print("".join(result))
        break
    else:
        n = s-1

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

using namespace std;

int main(int argc, char** argv) {
	int N, K;
	cin >> N >> K;
	priority_queue<pair<long long, int> > menu;

	int tmp1;
	long long tmp2;
	for(int cnt0 = 0; cnt0 < N; cnt0++){
		cin >> tmp1 >> tmp2;
		menu.push(make_pair(tmp2, tmp1));
	}
//	cout << "1" << endl;

	map<int, int> used;
	pair<long long, int> order[K];
	for(int cnt0 = K-1; cnt0 >= 0; cnt0--){
		order[K-1 - cnt0] = menu.top(); menu.pop();
		used[order[K-1-cnt0].second]++;
	}
//	cout << "2" << endl;

	long long size = used.size();

//	cout << size << endl;

	long long ans = 0;
	for(int cnt0 = 0; cnt0 < K; cnt0++) {
		ans += order[cnt0].first;
	}
	ans += size*size;

	long long ans_tmp = ans;
	for(int cnt0 = K-1; cnt0 >= 0; cnt0--) {
		if(used[order[cnt0].second] == 1) continue;

		while(menu.size()){
			auto qtmp = menu.top(); menu.pop();
			if(used[qtmp.second] != 0) continue;
			ans_tmp = ans_tmp - order[cnt0].first + qtmp.first - size*size + (size+1)*(size+1);
			used[qtmp.second]++;
			used[order[cnt0].second]--;
			ans = max(ans, ans_tmp); 
			size++;
            break;
		}
	}


	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 6256
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll dp[25000005];

int main()
{jizz
	ll n,money=0;
	pll buy[3];
	cin >> n;
	for(int i=0;i<3;++i)
		cin >> buy[i].F;
	for(int i=0;i<3;++i)
		cin >> buy[i].S;
	for(int i=0;i<3;++i)
		if(buy[i].S>buy[i].F)
		{
			dp[buy[i].F]=max(buy[i].S,dp[buy[i].F]);
			for(int j=1;j+buy[i].F<=n;++j)
				if(dp[j])
					dp[j+buy[i].F]=max(dp[j+buy[i].F],dp[j]+buy[i].S);
		}
	money=n;
	for(int i=0;i<=n;++i)
		money=max(money,n-i+dp[i]);
	MEM(dp,0),n=money;
	for(int i=0;i<3;++i)
		if(buy[i].F>buy[i].S)
		{
			dp[buy[i].S]=max(buy[i].F,dp[buy[i].S]);
			for(int j=1;j+buy[i].S<=n;++j)
				if(dp[j])
					dp[j+buy[i].S]=max(dp[j+buy[i].S],dp[j]+buy[i].F);
		}
	money=n;
	for(int i=0;i<=n;++i)
		money=max(money,n-i+dp[i]);
	cout << money << "\n";
}

Measured memory_bytes: 195584
#include<bits/stdc++.h>
#define test int t; cin>>t; while(t--)
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define mp make_pair
typedef long long ll;
using namespace std;
int main()
{
ll a,b,c; cin>>a>>b>>c;
ll s=a+b+c;
if(s>=22)
cout<<"bust"<<endl;
else
    cout<<"win"<<endl;
}


Measured memory_bytes: 3596
#include <stdio.h>
int a[100010];
int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int t;
		scanf("%d",&t);
		a[t-1]=i+1;
	}
	for(int i=0;i<n;i++)printf("%d ",a[i]);
}

Measured memory_bytes: 1152
#include<iostream>
#include<stdio.h>
using namespace std;

int m;
int inis;
int year,n;

int type;
double ritu;
int tesu;

int main(){
	int t;
	int i,j;
	int output;
	int a,b;
	
	cin >> m;
	for( t = 0; t < m; t++ ){
		if( scanf("%d",&inis) != 1 )break;
		cin >> year >> n;
		
		output = 0;
		for( i = 0; i < n; i++ ){
			cin >> type >> ritu >> tesu;
			if( type == 0 ){
				a = inis; b = 0;
				for( j = 0; j < year; j++ ){
					b += (double)a*ritu;
					a -= tesu;
				}
				//cout << "tanri = " << a + b << endl;
			}
			else{
				a = inis; b = 0;
				for( j = 0; j < year; j++ ){
					a = (double)a*(ritu+1.0);
					a -= tesu;
				}
				//cout << "fukuri = " << a + b << endl;
			}
			output = max( a+b, output );
		}
		cout << output << endl;
	}
	return 0;
}

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

int main() {
  long int n;
  cin >> n;
  long int a = 26;
  long int m;

  list<char> s;
  for (int i = 0; i < 12; i++) {
    n -= 1;
    m = n % a;
    s.push_front((char)('a' + m));
    n /= a;
    if (n <= 0) break;
  }

  for (auto i : s) {
    cout << i;
  }
  cout << endl;

  return 0;
}

Measured memory_bytes: 3612
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

//#include "atcoder/all"
//using namespace atcoder;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, d, x;
	cin >> n >> d >> x;
	int ans = x;
	rep(i,n){
		int a;
		cin >> a;
		for(int j = 1; j <= d; j+=a) ++ans;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;
public class Main
{
  public static void main(String[]args)
  {
    Scanner in=new Scanner(System.in);
    int n=in.nextInt();
    System.out.print(n+":");
    for(int i=2;i<=Math.sqrt(n);i++)
    {
      if(n%i==0)
      { 
        while(n%i==0)
        {
          System.out.print(" "+i);
          n=n/i;
        }
      }
    }
    
     if(n!=1)
       System.out.print(" "+n);
       System.out.println();
        
  }

}


Measured memory_bytes: 26364
use std::io;
use std::str::FromStr;
use std::collections::HashSet;

fn input_tuple() -> (usize, usize) {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    let vec: Vec<usize> = line.split_whitespace().map(|s| s.parse().unwrap()).collect();
    (vec[0], vec[1])
}

fn input_char_vec() -> Vec<char> {
    let mut line: String = String::new();
    io::stdin().read_line(&mut line);
    line.trim().chars().collect()
}

fn idx(y: usize, x: usize, w: usize) -> usize {
    y * w + x
}

fn count(idx: usize, w: usize, grid: &Vec<char>, checker: &Vec<char>, visited: &mut HashSet<usize>) -> Vec<u64> {
    // println!("idx: {}", idx);
    visited.insert(idx);
    if grid[idx] != checker[idx] {
        return vec![0; 2];
    }
    let i: usize;
    if grid[idx] == '#' {
        i = 0;
    } else {
        i = 1;
    }
    let mut tmp = vec![0; 2];
    tmp[i] += 1;
    let h = grid.len() / w;
    if idx % w != w - 1 && !visited.contains(&(idx+1)) {
        let c = count(idx + 1, w, grid, checker, visited);
        tmp[0] += c[0];
        tmp[1] += c[1];
    }
    if idx % w != 0 && !visited.contains(&(idx-1)) {
        let c = count(idx - 1, w, grid, checker, visited);
        tmp[0] += c[0];
        tmp[1] += c[1];
    }
    if idx < (h - 1) * w && !visited.contains(&(idx+w)) {
        let c = count(idx + w, w, grid, checker, visited);
        tmp[0] += c[0];
        tmp[1] += c[1];
    }
    if idx > w - 1 && !visited.contains(&(idx-w)) {
        let c = count(idx - w, w, grid, checker, visited);
        tmp[0] += c[0];
        tmp[1] += c[1];
    }
    tmp
}

fn main() {
    let (h, w) = input_tuple();
    let mut grid: Vec<char> = Vec::new();
    for _ in 0..h {
        let mut row = input_char_vec();
        grid.append(&mut row);
    }
    let mut ans = 0 ;
    let mut checker: Vec<char> = Vec::new();
    for i in 0..h {
        for j in 0..w {
            if (i + j) % 2 == 0 {
                checker.push('.');
            } else {
                checker.push('#');
            }
        }
    }
    let mut visited: HashSet<usize> = HashSet::new();
    for i in 0..h {
        for j in 0..w {
            if !visited.contains(&idx(i, j, w)) {
                let c = count(idx(i, j, w), w, &grid, &checker, &mut visited);
                ans += c[0] * c[1];
            }
        }
    }

    let mut checker: Vec<char> = Vec::new();
    for i in 0..h {
        for j in 0..w {
            if (i + j) % 2 == 0 {
                checker.push('#');
            } else {
                checker.push('.');
            }
        }
    }
    let mut visited: HashSet<usize> = HashSet::new();
    for i in 0..h {
        for j in 0..w {
            if !visited.contains(&idx(i, j, w)) {

                let c = count(idx(i, j, w), w, &grid, &checker, &mut visited);
                ans += c[0] * c[1];
            }
        }
    }
    println!("{}", ans);
}


Measured memory_bytes: 38520
#include <bits/stdc++.h>
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;
const ll mod = 1000000007;
using Graph = vector<vector<int>>;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main(){
    ll n; cin >> n;
    vector<ll> a(3 * n);
    rep(i, 3 * n)cin >> a[i];
    sort(a.begin(), a.end());

    ll sum = 0;
    rep(i, n) sum += a[3 * n - 2 - 2 * i];
    cout << sum << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7;

int a[N];

void calc(int len, int y){
	for (int i = 1; i <= len - 1; i++){
		a[i] += y * (len - i); 
	}
}
	
int main(){
	int n, x, y;
	scanf("%d%d%d", &n, &x, &y);
	int n1 = x, n2 = y - x - 1, n3 = (n - y + 1);

	calc(n1 + n3, 1);
	//calc(n2, 1);
	for (int i = 1; i <= (n2 + 1) / 2; i++) a[i] += n2 - 2;
	if (n2 % 2 == 0) a[n2 / 2 + 1] += n2 / 2 + 1 - 2;
	a[1] ++;
	

	int n4 = n2 / 2;
	calc(n4 + n3, 1); calc(n4, -1); calc(n3, -1);
	calc(n4 + n1, 1); calc(n4, -1); calc(n1, -1);

	calc(n4 + 1 + n1, 1); calc(n4, -1); calc(n1, -1);
	for (int i = 1; i <= n4; i++) a[i]--;
	for (int i = 1; i <= n1; i++) a[i]--;

	calc(n4 + 1 + n3, 1); calc(n4, -1); calc(n3, -1);
	for (int i = 1; i <= n4; i++) a[i]--;
	for (int i = 1; i <= n3; i++) a[i]--;

	if (n2 % 2){
		for (int i = 1; i <= n1; i++) a[n4 + i] ++;
		for (int i = 1; i <= n3; i++) a[n4 + i] ++;
	}
	
	for (int i = 1; i < n; i++) printf("%d\n", a[i]);

	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Card {
	String character;
	int num;

	public Card(String character, int num) {
		this.character = character;
		this.num = num;
	}

	@Override
	protected Card clone() {
		return new Card(this.character, this.num);
	}
}

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Card[] bCards = new Card[Integer.parseInt(br.readLine())];
		Card[] sCards = new Card[bCards.length];
		String[] strs = br.readLine().split(" ");
		for (int i = 0; i < bCards.length; i++) {
			bCards[i] = new Card(strs[i].substring(0, 1), Integer.parseInt(strs[i].substring(1, 2)));
			sCards[i] = bCards[i].clone();
		}

		bubbleSort(bCards);
		selectionSort(sCards);
		StringBuilder bSb = new StringBuilder();
		StringBuilder sSb = new StringBuilder();
		for (int i = 0 ; i < bCards.length; i++) {
			if (i > 0) {
				bSb.append(" ");
				sSb.append(" ");
			}
			bSb.append(bCards[i].character + bCards[i].num);
			sSb.append(sCards[i].character + sCards[i].num);
		}
		System.out.println(bSb.toString() + "\n" + "Stable");
		if (String.valueOf(bSb).equals(String.valueOf(sSb))) {
			System.out.println(sSb.toString() + "\n" + "Stable");
		} else {
			System.out.println(sSb.toString() + "\n" + "Not stable");
		}
	}

	public static void bubbleSort(Card[] cards) {
		for (int i = 0; i < cards.length; i++) {
			for (int j = cards.length - 1; j > 0; j--) {
				if (cards[j].num < cards[j - 1].num) {
					swapCard(cards[j], cards[j - 1]);
				}
			}
		}
	}

	public static void selectionSort(Card[] cards) {
		for (int i = 0; i < cards.length; i++) {
			int minIdx = i;
			for (int j = i + 1; j < cards.length; j++) {
				if (cards[minIdx].num > cards[j].num) {
					minIdx = j;
				}
			}
			if (i == minIdx) continue;
			swapCard(cards[i], cards[minIdx]);
		}
	}

	public static void swapCard(Card card1, Card card2) {
		int num = card1.num;
		String character = card1.character;
		card1.num = card2.num;
		card1.character = card2.character;
		card2.num = num;
		card2.character = character;
	}
}

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

long long dp[3002][3002],mod=998244353,ara[3003],n;

long long solve(long long idx,long long cap)
{
    if(idx==n+1)
    {
        if(cap==0)return 1;
        else{ return 0; }
    }
    else if(dp[idx][cap]!=-1)return dp[idx][cap];
    else
    {
        long long p=0,q=0;

        if((cap-ara[idx])>=0)p=solve(idx+1,cap-ara[idx]);
        q=solve(idx+1,cap);  q=(q*2)%mod;

        dp[idx][cap]=(p+q)%mod;   return dp[idx][cap];


    }


}

int main()
{

    long long s,a,b,c,ans,i;
    scanf("%lld %lld",&n,&s);
    for(i=1;i<=n;i++)
    {
        scanf("%lld",&ara[i]);
    }

    memset(dp,-1,sizeof dp);

    ans=solve(1,s);

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


    return 0;
}


Measured memory_bytes: 74388
import itertools
import math
import string
import collections
from collections import Counter
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
INF = 2**60


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
k = int(input())
a, b = map(int, input().split())
for i in range(a, b+1):
    if i % k == 0:
        print('OK')
        exit()
else:
    print('NG')


Measured memory_bytes: 68632
#include <bits/stdc++.h>
using namespace std;
  
int main() {
  string SA,SB,SC; cin >> SA >> SB >> SC;
  char ans;
  char card = SA[0];
  SA.erase(0,1);
  while (true) {
    if (card == 'a') {
      int NA = SA.size();
      if (NA == 0) {
        ans = 'A';
        break;
      } else {
        card = SA[0]; SA.erase(0,1);
      }
    }
    if (card == 'b') {
      int NB = SB.size();
      if (NB == 0) {
        ans = 'B';
        break;
      } else {
        card = SB[0]; SB.erase(0,1);
      }
    }
    if (card == 'c') {
      int NC = SC.size();
      if (NC == 0) {
        ans = 'C';
        break;
      } else {      
        card = SC[0]; SC.erase(0,1);
      }
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3600
void main() {
    string[] tmp = readln.split;
    uint n = tmp[0].to!uint;
    int m = tmp[1].to!int;
    long[] a = readln.split.to!(long[]);
    auto g = a.sort!"a > b".group.array;
    Tuple!(long, uint) t;
    foreach (i; 0 .. m) {
        tmp = readln.split;
        uint b = tmp[0].to!uint;
        long c = tmp[1].to!long;
        t[0] = c, t[1] = b;
        g ~= t;
    }
    g.sort!((t1, t2) => t1[0] > t2[0]);
    long ans;
    uint cnt;
    foreach (x; g) {
        if (cnt >= n) break;
        if (cnt + x[1] < n) {
            ans += x[0] * x[1].to!long;
            cnt += x[1];
        } else {
            ans += x[0] * (n - cnt).to!long;
            cnt = n;
        }
    }
    ans.writeln;
}

import std.stdio;
import std.string;
import std.array;
import std.conv;
import std.algorithm;
import std.range;
import std.typecons;

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

int main(){
  ll a,b,c,d;
  cin>>a>>b>>c>>d;
  ll val = max(a*c, max(a*d, max(b*c,b*d)));
  cout<<val<<endl;
  return 0;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
#pragma GCC optimize "03"
using namespace std;

#define int long long int
#define double long double
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define IOS ios::sync_with_stdio(false); cin.tie(NULL);
#ifndef LOCAL
#define dbg(...) ;
#define endl '\n'
#endif

const int inf = 1e15;
const int MOD = 1e9 + 7;
const int N = 2e5 + 5;



signed main(){
    IOS;
    int t;
    cin >> t;
    map<string, int> m;
    while (t--) {
        string s;
        cin >> s;
        m[s]++;
    }
    cout << "AC x " << m["AC"] << endl;
    cout << "WA x " << m["WA"] << endl;
    cout << "TLE x " << m["TLE"] << endl;
    cout << "RE x " << m["RE"] << endl;
    return 0;
}

Measured memory_bytes: 3668
from itertools import combinations

def solve():
    INF = 10**5

    def getNumInversion(odrAs):
        def makeBIT(numEle):
            numPow2 = 2 ** (numEle-1).bit_length()
            data = [0] * (numPow2+1)
            return data, numPow2
        def addValue(iA, A):
            iB = iA + 1
            while iB <= numPow2:
                data[iB] += A
                iB += iB & -iB
        def getSum(iA):
            iB = iA + 1
            ans = 0
            while iB > 0:
                ans += data[iB]
                iB -= iB & -iB
            return ans
        lenA = len(odrAs)
        data, numPow2 = makeBIT(lenA)
        ans = 0
        for odrA in reversed(odrAs):
            ans += getSum(odrA)
            addValue(odrA, 1)
        return ans

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = INF
    for iEvens in combinations(range(N), r=N//2):
        iEvens = set(iEvens)
        COdds, CEvens = [], []
        for i in range(N):
            if i in iEvens:
                if i % 2:
                    CEvens.append((As[i], i))
                else:
                    CEvens.append((Bs[i], i))
            else:
                if i % 2:
                    COdds.append((Bs[i], i))
                else:
                    COdds.append((As[i], i))
        COdds.sort()
        CEvens.sort()

        Cs = []
        for COdd, CEven in zip(COdds, CEvens):
            Cs += [COdd, CEven]
        if N % 2:
            Cs += [COdds[-1]]

        for i in range(N-1):
            if Cs[i][0] > Cs[i+1][0]:
                break
        else:
            odrAs = [i for C, i in Cs]
            num = getNumInversion(odrAs)
            ans = min(ans, num)
            if ans == 0:
                break

    if ans == INF:
        print(-1)
    else:
        print(ans)


solve()


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

int main(){
	int N;
	cin >> N;
	
	long long int Lucas = 0;
	long long int Lucasi2 = 2;
	long long int Lucasi1 = 1;
	
	if(N == 1){
		cout << 1 << endl;
	}
	else if(N > 1){
		for(int i = 1; i < N; i++) {
			Lucas = Lucasi1 + Lucasi2;
			Lucasi2 = Lucasi1;
			Lucasi1 = Lucas;
		}
		cout << Lucas << endl;
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#define MOD (1000000007l)
#define rep(i, n) for(long i = 0; i < n; i++)

using namespace std;

void solve() {
  long A, B;
  cin >> A >> B;
  if (A == 1) A += 100;
  if (B == 1) B += 100;
  if (A > B) puts("Alice");
  else if (A < B) puts("Bob");
  else puts("Draw");
}

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


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <functional>
#include <queue>
#include <stack>
#include <string.h>
#include <list>
using namespace std;
typedef long long ll;
#define all(a)  (a).begin(), (a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i = 0; i < n; i++)
#define repR(i,n) for(int i = n-1; i >= 0; i--)
#define FOR(i,m,n) for(int i = m; i < n; i++)
#define PB push_back
#define MP make_pair
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))


int main() {
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    string res;
    if(abs(a-c)<=d || (abs(a-b)<=d && abs(b-c)<=d)) res = "Yes";
    else res = "No";
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    long long N; cin >> N;
    vector<pair<long long, long long>>A(N);
    for (long long i = 0; i < N ; i++) {
        cin >> A.at(i).second >> A.at(i).first;
    }
    sort(A.begin(), A.end());
    long long num = 0;
    for (long long i = 0; i < N; i++) {
        if (num + A.at(i).second <= A.at(i).first) num += A.at(i).second;
        else {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 3328