akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

int main() {
  std::string s;
  std::cin >> s;

  uint64_t dp[100001][3];
  dp[0][0] = dp[0][1] = dp[0][2] = 0;

  uint64_t count = 1;
  for (uint64_t i = 0; i < s.size(); i++) {
    if (s[i] == 'A') {
      dp[i + 1][0] = dp[i][0] + count;
      dp[i + 1][1] = dp[i][1];
      dp[i + 1][2] = dp[i][2];
    } else if (s[i] == 'B') {
      dp[i + 1][0] = dp[i][0];
      dp[i + 1][1] = dp[i][1] + dp[i][0];
      dp[i + 1][2] = dp[i][2];
    } else if (s[i] == 'C') {
      dp[i + 1][0] = dp[i][0];
      dp[i + 1][1] = dp[i][1];
      dp[i + 1][2] = dp[i][2] + dp[i][1];
    } else {
      dp[i + 1][0] = dp[i][0] * 3 + count;
      dp[i + 1][1] = dp[i][1] * 3 + dp[i][0];
      dp[i + 1][2] = dp[i][2] * 3 + dp[i][1];
      count *= 3;
      count %= 1000000007;
    }
      dp[i + 1][0] %= 1000000007;
      dp[i + 1][1] %= 1000000007;
      dp[i + 1][2] %= 1000000007;
  }

  std::cout << dp[s.size()][2] << std::endl;
  return 0;
}

Measured memory_bytes: 2816
n = int(input())
dices = [list(map(int,input().split(" "))) for i in range(n)]
check = []
count = 0
eq = 0
for i in range(n):
    check.append(dices[i])
d= []

def move(x):
    # N
    if x == 0:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[1],d[5],d[2],d[3],d[0],d[4]
    # W
    elif x == 1:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[2],d[1],d[5],d[0],d[4],d[3]

    # E
    elif x == 2:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[3],d[1],d[0],d[5],d[4],d[2]
    # S
    elif x == 3:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[4],d[0],d[2],d[3],d[5],d[1]

# そのまま
    elif x == 4:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[0],d[1],d[2],d[3],d[4],d[5]
#ひっくり返し
    elif x == 5:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[5],d[4],d[2],d[3],d[1],d[0]


#頂点維持のまま回転
    elif x == 6:
        d[0],d[1],d[2],d[3],d[4],d[5] = d[0],d[2],d[4],d[1],d[3],d[5]


for i in range(6):
    d.append(dices[0][i])

for i in range(n-1):
    del check[0]
    for j in range(6):
        d[0],d[1],d[2],d[3],d[4],d[5] = dices[i][0],dices[i][1],dices[i][2],dices[i][3],dices[i][4],dices[i][5]
        move(j)
        for k in range(4):
            count += 1
            move(6)
            if d in check:
                eq = 1

                # print(d)
            # print(count)




if eq == 1:
    print("No")
else:
    print("Yes")



Measured memory_bytes: 5684
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
int main(void){
    // Your code here!
    int n;
    cin >> n;
    std::set<int> st;
    
    for (int i=0; i<n; i++) {
        int s;
        cin >> s;
        st.insert(s);
    }
    
    cout << st.size() << endl;
    
}

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

bool compare_by_b(pair<ll, ll> a, pair<ll, ll> b) {
    if(a.second != b.second){
        return a.second < b.second;
    }else{
        return a.first < b.first;
    }
}

int main(){
  int n;
  cin >> n;
  vector<pair<ll, ll> > pairs(n);
  for(int i=0;i<n;i++){
    ll a, b;
    cin >> a >> b;
    pairs[i] = make_pair(a, b);
  }
  sort(pairs.begin(), pairs.end(), compare_by_b);
  ll t=0;
  for(int i=0;i<n;i++){
    t+=pairs[i].first;
    if(t<=pairs[i].second)continue;
    else{
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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

	
	int N;
	cin >> N;
	int A[2000];
	int B[2001] = {};
	int goukei = 0;
	rep(i, N) {
		cin >> A[i];
		goukei += A[i];
		B[A[i]]++;
	}
	int hanbun = (goukei + 1) / 2;

	vector<int> V(4000001);
	V[0] = 1;
	int saidai = 0;
	rep1(i, 2000) {
		if (B[i]) {
			for (int j = saidai; j >= 0; j--) {
				if (V[j]) {
					rep1(k, B[i]) V[j + k * i] = 1;
					
				}
			}
			saidai += B[i] * i;
		}
		if (V[hanbun]) {
			co(hanbun);
			return 0;
		}
	}

	for (int i = hanbun; i < 4000000; i++) {
		if (V[i]) {
			co(i);
			break;
		}
	}

	Would you please return 0;
}

Measured memory_bytes: 15872
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long int
#define ar array
#define mp make_pair
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n,m;
	cin>>n>>m;
	cout<<(n-1)*(m-1)<<endl;
	return 0;
}

Measured memory_bytes: 384
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define BUGAVOID(x) x
#define rep(...) BUGAVOID(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define sz(c) (int)(c.size())
#define all(c) c.begin(),c.end()
#define ms(a,v) memset(a,v,sizeof(a))
#define unq(v) v.erase(unique(v.begin(),v.end()),v.end());
#define mp make_pair
#define write(x) cout<<(x)<<endl
using namespace std; typedef long long ll;
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; }
const int INF = 1 << 28; const ll LINF = 1ll << 60;
const int MAX = 1e5 + 5; const int MOD = 1e9 + 7; const double EPS = 1e-6;
const int dy[4] = { 0,1,0,-1 }; const int dx[4] = { 1,0,-1,0 };
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int N, M, H, W;
//int n, m, a, b, c, d, ans;
string s;

int main() {
    int T, X;
    cin >> T >> X;
    write((double)T / X);
}

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

using namespace std;


#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep1(i, n) for (int i = 1; i < (n); i++)
#define rrep(i, n) for (int i = (n)-1; i >= 0; i--)
#define all(i) (i).begin(), (i).end()
#define rall(i) (i).begin(), (i).end(), greater<int>()

#define int long long

#define elif else if
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define fst first
#define sec second

template <typename T>

void print(T x)
{
	std::cout << x <<" " ;
}


signed main(void) {
	int X,A;
	cin >> X>> A  ;
	if (X < A)print(0);
	else print(10);
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <algorithm>
#define NMAX 10000
using namespace std;

ifstream f("date.in");

int n;
int l[NMAX], vis[NMAX], dp[NMAX];
int l_max;

int main() {

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

    sort(l, l + n);
    l_max = l[n - 1] + l[n - 1];
    for (int i = 1; i <= l_max; ++i) {
        dp[i] = dp[i - 1] + vis[i];
    }

    int nr = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int a = l[i];
            int b = l[j];
            nr += (dp[b + a - 1] - dp[b]);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int a = l[i];
            int b = l[j];
            int pos = j + 1;
            while (pos < n && l[pos] == b) {
                nr ++;
                pos ++;
            }
        }
    }

    cout << nr;

    return 0;
}


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

int main()
{
    long long i, x = 0, ans = 0;
    string s;
    cin >> s;

    for(i = 0; i < s.size(); i++)
    {
        if(s[i] == 'B')
            x++;
        else
            ans += x;
    }

    cout << ans;
}


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

int main(void)
{
	const int Size = 1000;
	int size;
	int a,b,c,get_bool[Size]={0};
	
	cin >> size;
	for(int i=1;i<=size;i++)
	{
		cin >> a >> b >> c;
		if(a*a+b*b==c*c || a*a+c*c==b*b || b*b+c*c==a*a)
			get_bool[i]++;
		else 
			get_bool[i]=0;
	}
	
	for(int i=1;i<=size;i++)
	{
		if(get_bool[i]!=0)
			cout << "YES\n";
		else 
			cout << "NO\n";
	}
	return 0;
}


Measured memory_bytes: 3012
#include <bits/stdc++.h>
#include <cassert>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int, int>;
struct Edge
{
  int to;
  int weight;
  Edge(int t, int w) : to(t), weight(w) {}
};
using Graph = vector<vector<Edge>>;
// using Graph = vector<vector<int>>;

const long long INF = 1LL << 60;
const int INT_INF = 1000000000;

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

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  cin >> N;
  cout << N * (N + 1) / 2 << endl;
  return 0;
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define mov(i,a,b) for(int i = a; i < b; i++)
#define MOD 1000000007
#define INF 1e9+5
typedef unsigned long long ll;
using namespace std;
bool isPowerOfTwo(ll n){
	return (ceil(log2(n)) == floor(log2(n)));
}
long long binpow(long long a, long long b){
	long long res = 1;
	while(b>0){
		if(b&1) res *= a;
		a = a*a;
		b >>= 1;
	}
	return res;
}
int main(){
	
	string n;
	cin>>n;
	bool flag = true;
	for(int i = 1; i < n.size(); i++){
		if(n[i] == n[i-1]) flag = false;
	}
	if(flag) cout<<"Good"<<"\n";
	else cout<<"Bad"<<"\n";
	
	
	
	
	
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
   int w,a,b;
   cin >> w >> a >> b;
   if(b-a-w>0){
       cout << b-a-w << endl;
   }
   else if(a-b-w>0){
       cout << a-b-w << endl;
   }
   else{
       cout << "0" << endl;
   }
   
   return 0; 
}


Measured memory_bytes: 256
//g++ -std=c++14 test.cpp -o test.out

#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <cassert>
#include <algorithm>
#include <functional>
#include <iostream>
#include <iomanip>
#include <vector>
#include <queue>
#include <stack>
#include <map> 
#include <unordered_map> 
#include <utility>
#include <limits.h>
#include <bitset>
#include <set>
using namespace std;
 
#define LL long long int
const LL INF = (1LL<<60);
const int INF_INT = 2147483647-1e6-1;
const LL mod = 1000000007ll;
const int mod_int = 1000000007;

string S;

string ans = "";

void solve(){
	for(int i=0;i<3;i++){
		ans += S[i];
	}
}

int main(){
    cin >> S;

    solve();

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

Measured memory_bytes: 3048
import java.util.*;
import java.io.*;
import java.math.*;
 
 
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
 
public class Main{ 
 
 
    static long mod=1000000007;
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    // static int dx[]={1,-1,0,0,1,1,-1,-1};
    // static int dy[]={0,0,1,-1,1,-1,1,-1};
    // PriorityQueue<Integer> que = new PriorityQueue<Integer>(); 
    //HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
 
    public  static void main(String[] args)   throws Exception, IOException{
     
        
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);
     
        // int n=sc.nextInt();
        int n=sc.nextInt();
        int k=sc.nextInt();
        int a[] = new int[n];
        int b[] = new int[n];
        long ans=0;
        for (int i=0;i<n ;i++ ) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        if(k==0){
            for (int i=0;i<n ;i++ )if(a[i]==0)ans+=b[i];
        }
        else {
            int bit=1,one=0;
            long ans2=0;
                for (int i=0;i<n ;i++ )if( (k|a[i])==k )ans+=b[i];

            while(true){
                ans2 = 0;
                if(bit*2>k)break;
                else bit*=2;
                one = bit - 1;
                if( k<(k|bit) )continue;
                // db(k,bit,one,ans,((k-bit) | one));
                for (int i=0;i<n ;i++ ) {
                    if( (((k-bit) | one) | a[i]) == ( (k-bit) | one) )ans2+=b[i];
                }
                    ans=max(ans,ans2);
            }
        }
        out.println(ans);
        out.flush();
    }
     
    static void db(Object... os){
     
        System.err.println(Arrays.deepToString(os));
     
    }
     
    static boolean validpos(int x,int y,int r, int c){
        
        return x<r && 0<=x && y<c && 0<=y;
        
    }
     
    static boolean bit(long x,int k){
        // weather k-th bit (from right) be one or zero
        return  ( 0 < ( (x>>k) & 1 )  )  ? true:false;
    }    
}
 
class XY {
    int x,y,d;
    XY(int x, int y, int d) {
        this.x=x;
        this.y=y;
        this.d=d;
    } 
}
 
class P implements Comparable<P>{
    int x,y;
    P(int x, int y) {
        this.x=x;
        this.y=y;
    } 
      
    public int compareTo(P p){
        return -x + p.x;//des
    } 
}
 
class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}

Measured memory_bytes: 47000
n = int(input())
h = list(map(int,input().split()))
m = max(h)
ans = 0
for i in range(1,m+2):
    for j in range(n):
        if j == 0:
            if h[0] >= i:
                p = 0
            elif h[0] < i:
                p = 1
        if j == n-1:
            if p == 0:
                ans += 1
            if p == 1 and h[j] >=i:
                ans += 1
        else:
            if p == 0:
                if h[j] < i:
                    p = 1
                    ans += 1
            if p == 1:
                if h[j] >= i:
                    p = 0
        
print(ans)

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

int main() {
	int n;
	string s;
	cin >> n >> s;
	int count = 0;
	rep(i, n - 2) {
		if (s[i] == 'A' && s[i + 1] == 'B' && s[i+2]=='C') {
			count++;
	}
	}
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 384
import sys
N = int(input())

n = 10000
primeN = []
tmp = 2
for i in range(2, n):
    if primeN:
        for j in range(len(primeN)):
            if i % primeN[j] == 0:
                break
            else:
                if j == len(primeN) - 1:
                    primeN.append(i)
    else:
        if n > tmp:
            primeN.append(i)

ans = []
for i in primeN:
    if len(ans)==N:
        for j in ans:
            print(j)
        sys.exit()

    if i%5==1:
        ans.append(i)


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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
typedef long long ll;

void solve() {
    int X,Y,Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X << " " << Y << endl;
}

int main() {
    solve();
    return 0;
}

Measured memory_bytes: 3580
// kartikay26
#include <bits/stdc++.h>
using namespace std;
#define debug(x...) 
#ifdef LOCAL
#include "prettyprint.hpp"
#endif
typedef long long int ll; typedef double db; typedef vector<ll> vi; typedef pair<ll, ll> pii;
#define int ll
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define fast_io() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
void print(){cout << endl;} void prints(){}
template<typename T> void get(T* x, int n){for (int i = 0; i < n; ++i) { cin >> x[i]; }}
template<typename T> void get(T& x, int n){for (int i = 0; i < n; ++i) { cin >> x[i]; }}
template<typename T, typename... A> void print(T x,A... r){cout << x << " ";print(r...);}
template<typename T, typename... A> void prints(T x,A... r){cout << x << " ";prints(r...);}

const int mod = 1e9+7;
const int N = 1e6+1;

int32_t main(){
	fast_io();

	int n, m; cin >> n >> m;
	vector<int> was(n+1);
	vector<int> acs(n+1);
	for (int i = 0; i < m; ++i) {
		int p; string v;
		cin >> p >> v;
		if(v == "AC") {
			acs[p] = 1;
		} else {
			if (acs[p] == 1) {

			} else { 
				was[p]++;
			}
		}
	}

	for (int i = 0; i <= n; ++i) {
		if(acs[i] == 0) {
			was[i] = 0;
		}
	}

	int c = accumulate(all(acs), 0ll);
	int p = accumulate(all(was), 0ll);
	print(c, p);

	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <string>
#include <utility>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <tuple>
using namespace std;
using ll=long long;
ll gcd(ll a,ll b){return (b==0?a:gcd(b,a%b));}
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,n) for(int i=a;i<n;i++)
constexpr ll INF=1000000011;

int main (){
    int n,sum = 0;
    int d[100+5] ={};
    cin >> n;

    rep(i,n){
        cin >> d[i];
    }

    rep(i,n){
        Rep(j,i+1,n){
            
            sum += d[i]*d[j];
        }
    }

    cout << sum << endl;




}

Measured memory_bytes: 256
/** @Date    : 2017-05-06 21:02:21
  * @FileName: D.cpp
  * @Platform: Windows
  * @Author  : Lweleth (SoundEarlf@gmail.com)
  * @Link    : https://github.com/Lweleth
  * @Version : $Id$
  */
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int ,int>
#define MP(x, y) make_pair((x),(y))
#define fi first
#define se second
#define PB(x) push_back((x))
#define MMG(x) memset((x), -1,sizeof(x))
#define MMF(x) memset((x),0,sizeof(x))
#define MMI(x) memset((x), INF, sizeof(x))
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5+20;
const double eps = 1e-8;

int a[N];

vector<int> vt[N];
int flag;
int dfs(int s, int pre)
{
	if(flag == 1)
		return 0;
	int cnt = 0;
	int l = vt[s].size();
	for(int i = 0; i < l; i++)
	{
		int np = vt[s][i];
		if(np == pre)
			continue;
		if(dfs(np, s))
			cnt++;
		if(cnt >= 2)
		{
			printf("First\n");
			flag = 1;
			exit(0);
		}
	}
	return cnt ^ 1;
}

int main()
{


	int n;
	cin >> n;
		for(int i = 0; i < n - 1; i++)
		{
			int x, y;
			scanf("%d%d", &x, &y);
			vt[x].PB(y);
			vt[y].PB(x);
		}
		flag = 0;
		int f = dfs(1, -1);
		if(f == 1)
			printf("First\n");
		else if(!flag)
			printf("Second\n");
    return 0;
}

Measured memory_bytes: 5888
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN

N = int(input())
X = list(map(int, input().split()))
gt = int(Decimal(str(sum(X) / N)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
print(sum([(x-gt)**2 for x in X]))

Measured memory_bytes: 5076
#include <bits/stdc++.h>
#define RI register int
typedef long long LL;

#define FILEIO(name) freopen(name".in", "r", stdin), freopen(name".out", "w", stdout);

using namespace std;

int const MAXN = 2e5 + 5;
LL const mod = 998244353;
LL frac[MAXN], invfrac[MAXN], inv[MAXN];
LL f[MAXN], A[MAXN], B[MAXN];
int r[MAXN];

void Init(int Max) {
  frac[0] = invfrac[0] = 1;
  frac[1] = invfrac[1] = inv[1] = 1;
  for (RI i = 2; i <= Max; ++i) {
    frac[i] = frac[i - 1] * i % mod;
    inv[i] = (mod - mod / i) * inv[mod % i] % mod;
    invfrac[i] = invfrac[i - 1] * inv[i] % mod;
  }
}

inline LL qpow(LL a, LL k) {
  LL re = 1; a %= mod;
  for (; k; k >>= 1, a = a * a % mod)
    if (k & 1) re = re * a % mod;
  return re;
}
inline LL C(int n, int m) {
  if (m > n) return 0;
  return frac[n] * invfrac[m] % mod * invfrac[n - m] % mod;
}

void NTT(LL *a, int len, int op) {
  for (RI i = 0; i < len; ++i)
    if (r[i] > i)
      swap(a[i], a[r[i]]);
  for (RI i = 2; i <= len; i <<= 1) {
    LL wn = qpow(3, (mod - 1) / i);
    wn = qpow(wn, op);
    for (RI j = 0; j < len; j += i) {
      LL w = 1;
      for (RI k = j; k < j + i / 2; ++k) {
        LL x = a[k], y = a[k + i / 2] * w % mod;
        a[k] = (x + y) % mod;
        a[k + i / 2] = (x - y + mod) % mod;
        w = w * wn % mod;
      }
    }
  }
}

int main() {

#ifdef LOCAL
  FILEIO("a");
#endif

  Init(1e4);
  int n, m; cin >> n >> m;
  
  int len = 1, cnt = 0;
  while (len <= n + n + 2) len <<= 1, ++cnt;
  for (RI i = 0; i < len; ++i)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (cnt - 1));
  LL invlen = qpow(len, mod - 2);

  for (RI i = 1; i <= n; ++i) B[i] = invfrac[i + 2];
  NTT(B, len, 1);

  f[0] = 1;
  for (RI i = 1; i <= m; ++i) {
    for (RI j = 0; j <= n; ++j) A[j] = f[j] * invfrac[j] % mod;
    for (RI j = n + 1; j < len; ++j) A[j] = 0;
    NTT(A, len, 1);
    for (RI j = 0; j < len; ++j) A[j] = A[j] * B[j] % mod;
    NTT(A, len, mod - 2);
    for (RI j = 0; j <= n; ++j)
      f[j] = (frac[j + 2] * A[j] % mod * invlen % mod + f[j] * (1ll + C(j + 1, 2)) % mod) % mod;
  }
  LL ans = 0;
  for (RI i = 0; i <= n; ++i)
    ans = (ans + f[i] * C(n, i) % mod) % mod;
  printf("%lld\n", ans);

  cerr << (double)(clock()) / CLOCKS_PER_SEC * 1000 << "ms" << endl;

  return 0;
}

// created by Daniel yuan

Measured memory_bytes: 6656
#include<cstdio>
#include<algorithm>
using namespace std;

const int MAXN=405;

int n,h;
int in[MAXN],out[MAXN],cnt[MAXN],fa[MAXN];

int Find(int x){return fa[x]==0?x:fa[x]=Find(fa[x]);}

int main(){
	scanf("%d%d",&n,&h);
	for(int i=1;i<=n;i++){
        int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int x=c==0?a:(c+200);
		int y=d==0?(b+200):d;
		in[y]++,out[x]++;
		x=Find(x),y=Find(y);
		if(x!=y) fa[x]=y;
	}
	bool f=1;
	for(int i=1;i<=400;i++)
		if(in[i]!=out[i]){
			if((in[i]<out[i]&&i>200)||(in[i]>out[i]&&i<200)){
				f=0;
				break;
			}
			int x=Find(i);
			cnt[x]++;
		}
	if(f){
		for(int i=1;i<=400;i++)
			if((in[i]||out[i])&&cnt[Find(i)]==0){
				f=0;
				break;
			}
	}
	if(f) puts("YES");
	else puts("NO");
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define all(x) (x).begin(), (x).end()
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; }
template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin >> n;
    string a, b, c; cin >> a >> b >> c;
    int ans = 0;
    rep (i, n) {
        set<char> st;
        st.insert(a[i]); st.insert(b[i]); st.insert(c[i]);
        ans += st.size() - 1;
    }
    cout << ans << "\n";
    return 0;
}

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

int main() {
  while(1) {
    int n;
    cin >> n;
    if(n == 0) break;
    int mp[100001] = {};
    
    for(int i=0;i<n;i++) {
      int a;
    cin >> a;
    mp[i] = a;
    if(i%2 == 1){
      int j = i-1;
      while(mp[j] != a) mp[j] = a,j--;
    }
  }
  int ans = 0;
  for(int i=0;i<n;i++) if(mp[i] == 0) ans++;
  cout << ans <<endl;
  }

    return 0;
}

Measured memory_bytes: 1556
#include<iostream>

using namespace std;

int main(){

	int yen;
	int ans=0;

	while(cin>>yen){
	if(yen==0) break;
	yen=1000-yen;
	ans=yen%5;
	yen/=5;
	ans+=yen%2;
	yen/=2;
	ans+=yen%5;
	yen/=5;
	ans+=yen%2;
	yen/=2;
	ans+=yen%5;
	ans+=yen/5;
	cout<<ans<<endl;
	}
}

Measured memory_bytes: 2988
#include <bits/stdc++.h>
#define MOD 1e9 + 7
#define PI 3.141592653589793238
#define pb push_back
#define ALL(V) (V).begin(), (V).end()
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long long int lint;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<int> VI;
typedef pair<ll, ll> P;
ll gcd(ll a, ll b) { return (a % b == 0 ? b : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); }
ll char_to_ll(char c) { return (int)(c - '0'); }
ll string_to_ll(string s) { return char_to_ll(atoi(s.c_str())); }
bool is_prime(ll x){ if(x <= 1) return false; for(ll i = 2; sqrt(i) <= x; i++) if(x % i == 0) return false; return true; }


int main() {
    int a,b;
    cin >> a;
    b = pow(a,2.0);

    cout << b << endl;

  

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001
#define mod 1000000007
#define pi 3.141592653589793
#define all(v) v.begin(),v.end()

ll gcd(ll a,ll b){
    if(b>a) swap(a,b);
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    ll g=gcd(a,b);
    return a/g*b;
}
ll rep_jijo(ll n,ll x){
    if(x==0) return 1;
    if(x%2==0){
        ll t=rep_jijo(n,x/2);
        return t*t%mod;
    }
    return n*rep_jijo(n,x-1)%mod;
}
ll com(ll n,ll r){
    ll x=1,y=1;
    ll tmp=n;
    while(tmp>=n-r+1){
        x=x*tmp%mod;
        tmp--;
    }
    while(r>0){
        y=y*r%mod;
        r--;
    }
    return x*rep_jijo(y,mod-2)%mod;
}
int main(){
    int k,t;
    cin >> k >> t;
    vector<int>cake(t);
    rep(i,t) cin >> cake[i];
    sort(all(cake));
    reverse(all(cake));
    int mx=cake[0];
    int ans=mx-1;
    for(int i=1;i<t;i++){
        ans-=cake[i];
    }
    if(ans>0) cout << ans << endl;
    else cout << 0 << endl;
    return 0;
}


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

int main() {
    int n;
    cin >> n;
    int w[n + 1];
    for (int i = 1; i <= n; i++) cin >> w[i];
    int ans = 1e9;
    for (int i = 1; i < n; i++) {
        int s1 = 0, s2 = 0;
        for (int j = 1; j <= i; j++) s1 += w[j];
        for (int j = i + 1; j <= n; j++) s2 += w[j];
        ans = min(ans, abs(s1 - s2));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main (){
string j,k,l;
int a,b,c;
cin>>j>>k>>l;
 a=j.size()-1;
 b=k.size()-1;
 c=l.size()-1;
if (j[a]==k[0] && k[b]==l[0]){
    cout<<"YES";
}
else cout<< "NO";

return 0;
}


Measured memory_bytes: 256
#define _GLIBCXX_DEBUG

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

#define rep(i,n) for(int i = 0; i < n; i++)
#define Rep(i,n) for(int i = 1; i <= n; i++)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
template<class T> using V = vector<T>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
struct INF { template<class T> operator T() { return numeric_limits<T>::max() / 2; } } INF;


template<class T>
struct SegmentTree { // セグメント木

    const T INF = numeric_limits<T>::max();

    int n;
    int size;
    vector<T> mins, maxs;

    SegmentTree(int _n) {
        n = 1;
        size = _n;
        while(n < _n) n *= 2;
        mins.assign(n*2,INF);
        maxs.assign(n*2,-INF);
    }

    void update(int k, T a) { // val[k] = a;
        k += n-1;
        maxs[k] = mins[k] = a;
        while(k > 0) {
            k = (k-1) / 2;
            mins[k] = min(mins[k*2+1], mins[k*2+2]);
            maxs[k] = max(maxs[k*2+1], maxs[k*2+2]);
        }
    }

    T Min(int l, int r) { // 閉区間 [l,r] の最小値
        return _min(l, r+1, 0, 0, n);
    }
    T _min(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return INF;
        if(a <= l && r <= b) return mins[k];
        else {
            T vl = _min(a, b, k*2+1, l, (l+r)/2);
            T vr = _min(a, b, k*2+2, (l+r)/2, r);
            return min(vl, vr);
        }
    }

    T Max(int l, int r) { // 閉区間 [l,r] の最大値
        return _max(l, r+1, 0, 0, n);
    }
    T _max(int a, int b, int k, int l, int r) {
        if(r <= a || b <= l) return -INF;
        if(a <= l && r <= b) return maxs[k];
        else {
            T vl = _max(a, b, k*2+1, l, (l+r)/2);
            T vr = _max(a, b, k*2+2, (l+r)/2, r);
            return max(vl, vr);
        }
    }

    // 閉区間 [l,r] で x 以上の数が最初に現れるインデックスを返す
    // 無ければ一番後ろ (= r) を返す
    int lower_bound(int l, int r, T x) {
        while(abs(l-r) > 0) {
            int mid = (l+r) / 2;
            if(Max(l,mid) >= x) r = mid;
            else l = mid+1;
        }
        return Max(r,r) >= x ? l : r+1;
    }
};


int main(){

    int n, q;
    cin >> n >> q;

    SegmentTree<int> st(n);

    rep(i,n) {
        int a;
        cin >> a;
        st.update(i,a);
    }

    rep(i,q) {
        int t, a, b;
        cin >> t >> a >> b;
        if(t == 1) {
            a--;
            st.update(a,b);
        }
        if(t == 2) {
            a--; b--;
            cout << st.Max(a,b) << endl;
        }
        if(t == 3) {
            a--;
            cout << st.lower_bound(a,n-1,b) + 1 << endl;
        }
    }
}

Measured memory_bytes: 7500
#include"bits/stdc++.h"
#include<boost/multi_array.hpp>
#include<boost/optional.hpp>
#include<boost/range/irange.hpp>
#include<boost/range/algorithm.hpp>
#include<boost/range/adaptors.hpp>

namespace adaptor = boost::adaptors;

int64_t N, K, R, S, P;
std::string T;

int64_t score(char32_t ch)
{
	if (ch == 'r') return P;
	else if (ch == 's') return R;
	else return S; // ch == 'p'
}

void solve()
{
    std::cin >> N >> K >> R >> S >> P >> T;

	int64_t ans = 0;
	for (int64_t k = 0; k < K; k++)
	{
		bool won_last_game = false;
		for (int64_t i = k; i < N; i+=K)
		{
			if (i >= K && T[i - K] == T[i] && won_last_game) won_last_game = false;
            else ans += score(T[i]), won_last_game = true;
		}
	}

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

int main()
{
	std::cin.tie(nullptr);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	solve();
}


Measured memory_bytes: 3772
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <utility>
#include <numeric>
#include <map>
#include <iomanip>
using namespace std;

int main() {
    int N, M; cin >> N >> M;
	vector<pair<int, int>> PY(M);
	for(int i = 0; i < M; i++) cin >> PY[i].first >> PY[i].second;

	vector<vector<pair<int, int>>> P(N);
  
	for(int i = 0; i < M; i++){
		pair<int, int> tmp = make_pair(PY[i].second, i);
		P[PY[i].first - 1].push_back(tmp);
	}
  
	for(int i = 0; i < N; i++){
		sort(P[i].begin(), P[i].end());
	}

	vector<pair<int, long long>> num;
	for(long long i = 0; i < N; i++){
		for(int j = 0; j < P[i].size(); j++){
			long long tmp = (i + 1) * 1000000 + j + 1;
			pair<int, long long> tmp2 = make_pair(P[i][j].second, tmp);
			num.push_back(tmp2);
		}
	}
	sort(num.begin(), num.end());

	for(int i = 0; i < M; i++){
		cout << setfill('0') << std::right << setw(12) << num[i].second << endl;
	}

}

Measured memory_bytes: 9456
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<map>
using namespace std;
int main() {
    int h,w,n;
    cin >> h >> w >> n;
    int m = h > w ? h : w;
    int ans = n / m;
    if(n % m != 0) ans++;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
      return Array.new(size1){init}
  else
      return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N,K=get_i
A=get_i.sort{|x,y| y<=>x}
F=get_i.sort
def fulfil?(x)
    res=0
    N.times do|i|
        res+=max(A[i]-x/F[i],0)
    end
    return res<=K
end
head=-1
tail=A[0]*F[-1]+1
while tail-head>1
  mid=head+(tail-head)/2
  if fulfil?(mid)
      tail=mid
  else
      head=mid
  end
end
puts tail

Measured memory_bytes: 48008
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

int n, m, q;
vector<int> gph[100005];
int col[100005], vis[100005][11];
int v[100005], d[100005], c[100005];

queue<pi> que;

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<m; i++){
		int s, e;
		scanf("%d %d",&s,&e);
		gph[s].push_back(e);
		gph[e].push_back(s);
	}
	scanf("%d",&q);
	for(int i=0; i<q; i++){
		scanf("%d %d %d",&v[i],&d[i],&c[i]);
	}
	for(int i=q-1; i>=0; i--){
		que.push(pi(v[i], d[i]));
		while(!que.empty()){
			auto x = que.front();
			que.pop();
			if(vis[x.first][x.second]) continue;
			vis[x.first][x.second] = 1;
			if(!col[x.first]) col[x.first] = c[i];
			if(x.second == 0) continue;
			for(auto &i : gph[x.first]){
				que.push(pi(i, x.second - 1));
			}
		}
	}
	for(int i=1; i<=n; i++) printf("%d\n", col[i]);
}


Measured memory_bytes: 13800
#include <iostream>

using namespace std;

const int MAX_N = 21;

bool gem[MAX_N][MAX_N];

int main() {
  int N;
  while (cin >> N) {
    if (N == 0) break;
    for (int i = 0; i <= 20; i++) {
      for (int j = 0; j <= 20; j++) {
        gem[i][j] = false;
      }
    }
    for (int i = 0; i < N; i++) {
      int x, y;
      cin >> x >> y;
      gem[x][y] = true;
    }
    int M;
    cin >> M;
    int pos_x = 10, pos_y = 10;
    int count = 0;
    for (int i = 0; i < M; i++) {
      char c;
      int d;
      cin >> c >> d;
      while (d--) {
        if (c == 'N') pos_y++;
        if (c == 'S') pos_y--;
        if (c == 'E') pos_x++;
        if (c == 'W') pos_x--;
        if (gem[pos_x][pos_y]) {
          gem[pos_x][pos_y] = false;
          count++;
        }
      }
    }
    if (count == N) cout << "Yes" << endl;
    else cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 0
// Heat Strokes 2018/12/28

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int A, B, X;
    int max_A, X_B, price;
    cin >> A >> B >> X;

    if (X < 1000) max_A = 1;
    else {
        max_A = X / 1000;
        if (X % 1000) max_A++;
    }
    // cout << "max_A: " << max_A << endl;
    price = B * (X / 500 + 1); // 最大値(or + B)
    for (int num_a = 0; num_a <= max_A; num_a++) {
        int num_b = 0, tmp_price;
        X_B = X - num_a * 1000; // 残りの必要な量
        if (X_B > 0) {
            num_b = X_B / 500;
            if (X_B % 500) num_b++;
        }
        tmp_price = A * num_a + B * num_b;
        /* cout << "A: " << A << ", num_a: " << num_a;
        cout << ", B: " << B << ", num_b: " << num_b;
        cout << ", price: " << tmp_price << endl; */
        price = min(price, tmp_price);
    }
    cout << price << endl;
    return 0;
}


Measured memory_bytes: 3124
from collections import deque

s = deque(str(input()))
q = int(input())
hanten = 0

for i in range(q):
    x = input().split()
    if len(x) == 1:
        t = x[0]
        if t == "1" and hanten == 0:
            hanten = 1
        elif t == "1" and hanten == 1:
            hanten = 0

    else:
        f = int(x[1])
        c = str(x[2])
        if f == 1 and hanten == 0:
            s.appendleft(c)

        elif f == 1 and hanten == 1:
            s.append(c)

        elif f == 2 and hanten == 0:
            s.append(c)

        elif f == 2 and hanten == 1:
            s.appendleft(c)

else:
    if hanten == 1:
        s.reverse()

print("".join(s))


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// mod
const ll MOD = 1000000007ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

// floating
typedef double Real;
const Real EPS = 1e-11;
#define EQ0(x) (abs(x)<EPS)
#define EQ(a,b) (abs(a-b)<EPS)
typedef complex<Real> P;

int mp[1252];

void calc(int x){
  for(int t=2;t*t<=x;t++)while(x%t==0){
    x/=t;
    mp[t]++;
  }
  if(x>1)mp[x]++;
}

int main(){
  int n;
  cin>>n;
  FOR(x,1,n+1)calc(x);
  ll ans = 1;
  REP(i,1252)ans=ans*(mp[i]+1)%MOD;
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 764
#include <iostream>
#include <limits>
#include <vector>
#include <cstdint>

int main() {
  int N;
  std::cin >> N;
  std::vector<std::vector<std::int64_t>> locations(2, std::vector<std::int64_t>(N));
  std::vector<std::int64_t> P(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> locations[0][i] >> locations[1][i] >> P[i];
  }
  const auto kInfinity = std::numeric_limits<std::int64_t>::max() / 2;
  std::vector<std::vector<std::vector<std::int64_t>>>
      distances(2, std::vector<std::vector<std::int64_t>>(N, std::vector<std::int64_t>(1 << N, kInfinity)));
  for (int d = 0; d < 2; ++d) {
    for (int i = 0; i < N; ++i) {
      for (int subset = 0; subset < (1 << N); ++subset) {
        auto dist = std::abs(locations[d][i]);
        for (int j = 0; j < N; ++j) {
          if ((subset >> j) & 1) {
            dist = std::min(dist, std::abs(locations[d][i] - locations[d][j]));
          }
        }
        distances[d][i][subset] = dist;
      }
    }
  }
  std::vector<std::vector<std::vector<std::int64_t>>>
      costs(2, std::vector<std::vector<std::int64_t>>(1 << N, std::vector<std::int64_t>(N + 1, kInfinity)));
  for (int subset = 0; subset < (1 << N); ++subset) {
    int rails = subset;
    do {
      for (int d = 0; d < 2; ++d) {
        std::int64_t sum = 0;
        for (int i = 0; i < N; ++i) {
          if ((subset >> i) & 1) {
            sum += distances[d][i][rails] * P[i];
          }
        }
        auto& mem = costs[d][subset][__builtin_popcount(rails)];
        mem = std::min(mem, sum);
      }
      rails = (rails - 1) & subset;
    } while (rails != subset);
  }
  for (int K = 0; K <= N; ++K) {
    std::int64_t S = kInfinity;
    for (int subset = 0; subset < (1 << N); ++subset) {
      for (int v = 0; v <= K; ++v) {
        S = std::min(S, costs[0][subset][v] + costs[1][((1 << N) - 1) ^ subset][K - v]);
      }
    }
    std::cout << S << std::endl;
  }
  return 0;
}


Measured memory_bytes: 27280
#include<iostream>
#include<cstdio>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=1001000,P=998244353,iv2=(P+1)>>1;
int n,L,x,t,S,p[N],a[N];
int qpw(int x,int y){int z=1;for(;y;y>>=1,x=1ll*x*x%P)if(y&1) z=1ll*z*x%P;return z;}
void FWT(int *A,int o){
	for(int i=1;i<L;i<<=1)for(int j=0,s=i<<1;j<L;j+=s)FOR(k,0,i-1){
		x=j+k,t=A[i+x],A[i+x]=(A[x]+P-t)%P,(A[x]+=t)%=P;
		if(o<0) A[i+x]=1ll*A[i+x]*iv2%P,A[x]=1ll*A[x]*iv2%P;
	}
}
int main(){
	scanf("%d",&n);L=1<<n;
	FOR(i,0,L-1) scanf("%d",&a[i]),S=1ll*(S+a[i])%P;
	S=qpw(S,P-2);
	FOR(i,0,L-1) a[i]=1ll*a[i]*S%P,p[i]=P-1;
	(a[0]+=P-1)%=P;(p[0]+=L)%=P;
	FWT(a,+1);FWT(p,+1);
	FOR(i,0,L-1) a[i]=1ll*p[i]*qpw(a[i],P-2)%P;FWT(a,-1);
	FOR(i,0,L-1) cout<<(a[i]-a[0]+P)%P<<'\n';
}

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

typedef long long ll;

int main() {
    string alphabet = "abcdefghijklmnopqrstuvwxyz";
    string S;
    cin >> S;

    vector<bool>al(26, false);
    for (char s : S) al[s-'a'] = true;

    if (S.size() == 26) {
        int i = S.size()-1;
        while (S[i-1] > S[i]) {
            if (i == 1) {
                cout << -1 << endl;
                return 0;
            }
            al[S[i]-'a'] = false;
            i--;
        }
        al[S[i]-'a'] = false;
        while (al[S[i-1]-'a']) S[i-1]++;
        S.erase(i);
        cout << S << endl;
        return 0;
    }
    int i = 0;
    while (al[i]) i++;
    S += alphabet[i];
    cout << S << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	long long m,n,k,count=0;
	cin>>m>>n>>k;
	for(int i=0;i<k/2;i++){
		if(m%2==1) m-=1;
		m=m/2;
		n+=m;
		if(n%2==1) n-=1;
		n=n/2;
		m+=n;
	}
	if(k%2==1){
		if(m%2==1) m-=1;
		m=m/2;
		n+=m;
	}
	cout<<m<<" "<<n<<endl;
} 

Measured memory_bytes: 256
import sys
from itertools import accumulate

def read():
    return sys.stdin.readline().rstrip()

def main():
    n = 10**5
    p = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    p[1] = False
    p[2] = p[3] = p[5] = p[7] = True
    for pi in range(3, int(n ** 0.5) + 1, 2):
        if not p[pi]:
            continue
        for i in range(pi ** 2, n + 1, pi):
            p[i] = False
    like = [i % 2 == 1 and p[i] and p[(i + 1) // 2] for i in range(n)]
    a = [0] + list(accumulate(like))[1:]
    for _ in range(int(read())):
        l, r = map(int, read().split())
        print(a[r] - a[l - 1])

if __name__ == '__main__':
    main()

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


int main(){
    string S;
    string str = "Good";

    cin >> S;

    for(int i = 0; i < 3 ; i++){
        if(S[i] == S[i+1]){
            str = "Bad";
            break;
        }
    }

    cout << str;
}

Measured memory_bytes: 256
//author : raghav_0901
#include <bits/stdc++.h>
#define long double int
using namespace std;

signed main()
{
    int h1,m1,h2,m2,k;
    cin>>h1>>m1>>h2>>m2>>k;
    int total_min = (h2-h1)*60;
    total_min+=(m2-m1-k);
    cout<<total_min<<'\n';
    return 0;   
}


Measured memory_bytes: 3632
#include<stdio.h>
int main(){
    int a,b;
    scanf("%d",&a);
    b=a%100;
    if((b>0 && b<13) || (a>99 && a<1300)){
        if((b>0 && b<13) && a>99 && a<1300){
            printf("AMBIGUOUS");
        }else if(b>0 && b<13){
            printf("YYMM");
        }else{
            printf("MMYY");
        }
    }else{
        printf("NA");
    }
    return 0;
}

Measured memory_bytes: 128
def solve():
    N = int(input())
    A = list(map(int, input().split()))

    sum_a = 0
    tmp = 0
    
    for i in range(N-1):
        tmp += A[i]
        sum_a += tmp * A[i+1]

  #  print(sum_a)

    ans = sum_a % 1000000007

    print(ans)


if __name__ == "__main__":
    solve()



Measured memory_bytes: 31744
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

using namespace std;
typedef long long int lli;

int main(){
	string s;
	cin>>s;
	string t("CODEFESTIVAL2016");
	int ans=0;
	rep(i,16)if(s[i]!=t[i])ans++;
	cout<<ans;
}

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

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

int main() {
  int n, o = 0;
  cin >> n;
  vector<int> l(n);
  for(int i = 0; i < n; i++)
    cin >> l.at(i);
  sort(l.begin(), l.end());
  for(int i = n - 1; i > 1; i--) {
    for(int j = i - 1; j > 0; j--) {
      o += max(0, j - (int)distance(l.begin(), upper_bound(l.begin(), l.end(),
                                                           l.at(i) - l.at(j))));
    }
  }
  cout << o << endl;
}

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

typedef long long ll;

#define F first 
#define S second 
#define PB push_back
#define MP make_pair 
#define rep(i,a,b) for (ll i=a;i<b;i++)
const ll INF = 1LL << 60;

typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vl;
typedef pair<ll,ll> pl;


int main()
{
    int n,r;
    cin>>n>>r;

    int res=0;
    if(n>=10) {
        res = r;
    } else {
        res = r + 100*(10-n);
    }
    cout<<res<<endl;

    return 0; 
}



Measured memory_bytes: 256
while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
 
    for h in range(H):
        for w in range(W):
            if (h + w) % 2 == 0:
                print('#', end='')
            else:
                print('.', end='')
 
        print()
    print()

Measured memory_bytes: 8988
K,T=map(int,input().split())
A=list(map(int,input().split()))

B=max(A)

if T==1:
    print(K-1)
    exit()

if K%2:
    X=(K+1)//2
    if X>=B:
        print(0)
    else:
        C=B-X
        print(2*C)
else:
    Y=K//2
    if Y>=B:
        print(0)
    else:
        C=B-Y
        print(2*C-1)


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

int main() {
	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 if( A + B < C + D){
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
n=int(input())
#a,b=map(int,input().split())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]

count=0

for i in range(1,n+1):
    a=al[i-1]
    if i%2!=0 and a%2!=0:
        count+=1
print(count)




Measured memory_bytes: 9100
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define f first
#define s second
using namespace std;
double delta(ll x){
	ll c = x, s = 0;
	while( c> 0){
	 	s += c%10; c/= 10;
	}
	return (double)1.0*x/s;
}
int main(){
	int ub = 100, cnt = 0;
	cin >> ub;
	ll a = 0, b=1;
	for(int i = 0; i< ub; i++){
		if((a/b)%10 == 9 && delta(a+b) > delta(a+10*b))b*=10;
		a += b;
		cout <<a  << endl;
  	}
	return 0;
}                  


Measured memory_bytes: 3644