akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
#define ote(x) cout<<(x)<<endl
#define all(x) (x).begin(),(x).end()
#define rp(i,s,e) for(int i=(s);i<(e);++i)
#define rpz(i,e) rp(i,0,(e))
#define irp(i,s,e) for(int i=(s);i>(e);--i)
#define irpz(i,s) irp(i,(s),-1)
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 in(){T x;cin>>x;return x;}
// long long a = in<long long>();
template<class T> vector<T> inarr(int s,int e, T init=0){
	vector<T> v;T x;
	for(int i=0;i<s;++i)v.push_back(init);
	for(int i=s;i<e;++i){x=in<T>();v.push_back(x);}
	return v;
}
// vi P = inarr<int>(1,N+1,INT_MAX);
// vi P = inarr<int>(0,N);

// #define NMAX 1000000000
int N,K;
vi P;

double solve(){
	double ans = 0;

	vector<double> X(N);
	rp(i,0,N){
		X[i] = (double)(P[i]+1)/2.0;
	}

	vector<double> Y(N+1);
	rp(i,0,N){
		Y[i+1] = Y[i] + X[i];
	}
	// for(auto x:X) ote(x);puts("");
	// for(auto y:Y) ote(y);puts("");

	rp(i,0,N-K+1){
		// chmax(ans, Y[i+K]-Y[i]);
		ans = max(ans, Y[i+K]-Y[i]);
		// ote(ans);////
	}

	return ans;
}

int main(){
	cin>>N>>K;
	P = inarr<int>(0,N);
	printf("%.12f\n",solve());
}


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

#define ll long long
#define MOD 1000000007
#define LLMN LONG_LONG_MIN
#define LLMX LONG_LONG_MAX
#define MAX 1000000

vector<bool>prime(MAX, true);
vector<ll>fact(MAX);
vector<ll>factinv(MAX);

ll  fastpower(ll a, ll n)
{
	ll res = 1;
	while(n > 0)
	{
		if(n % 2 != 0)
		{
			res = (res * a) % MOD;
		}
		n /= 2;
		a=(a * a) % MOD;
	}
	return res;
}

void getprime()
{
	for(ll i = 2;i < MAX; i++)
	{
		if(prime[i-1])
		{
			for(ll j = i*i; j < MAX; j += i)
				prime[j-1] = false;
		}
	}
}

void getfact()
{
	fact[0] = 1;
	factinv[0] = 1;
	
	for(ll i = 1; i < MAX; i++)
		fact[i] = (fact[i-1] * i)%MOD;
	
	for(ll i = 1; i < MAX; i++)
		factinv[i] = (factinv[i-1] * fastpower(i, MOD -2) )%MOD;

}
/*
char find(char x, vector<char>&par)
{
	if(par[x]=='$')
		return x;
	else
		return find(par[x], par);
}
void unionn(char x, char y, vector<char>par)
{
	char a=find(x,par);
	char b=find(y,pR);
	if(a!=b)
	{
		par[a]=b;
	}
}
*/
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll t,n,m,q;
	cin>>n;
	vector<ll>a(n-1);
	for(ll i=0;i<n-1;i++) cin>>a[i];
	map<ll,ll>mp;
	for(ll i=1;i<=n;i++)
		mp[i]=0;
	for(ll i=0;i<n-1;i++)
		mp[a[i]]++;
	
	for(ll i=1;i<=n;i++)
		cout<<mp[i]<<"\n";
	
	return 0;
}

Measured memory_bytes: 33032
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.util.stream.Collectors;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int x = Integer.parseInt(line[1]);
        List<Integer> list = Arrays.stream(br.readLine().split(" "))
            .map(Integer::parseInt)
            .sorted()
            .collect(Collectors.toList());
        int output = 0;    
        for (int num: list) {
            if (x >= num) {
                x -= num;
                output++;
            } else {
                break;
            }
        }
        if (list.size() == output && x > 0) {
            output--;
        }
        out.println(output);
        out.close();
    }
}

Measured memory_bytes: 27732
package main

import (
	"fmt"
)

func tableTennisTraining(n, a, b uint64) uint64 {
	var ans uint64
	if (a&1) != 1 && (b&1) != 1 {
		// a and b == Even
		// a と b の中間までの距離
		ans = (b - a) / 2
	} else if (a&1) == 1 && (b&1) == 1 {
		// a and b == odd
		// a と b の中間までの距離
		ans = (b - a) / 2
	} else {
		// a or b == odd
		ans = min((a-1), (n-b)) + 1 + (b-a-1)/2
	}
	return ans
}

func min(a, b uint64) uint64 {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n, a, b uint64
	fmt.Scan(&n, &a, &b)
	fmt.Println(tableTennisTraining(n, a, b))
}


Measured memory_bytes: 512
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};

typedef struct node * Node;

Node root,NIL;
int maxh;

void insert(int x){
  int H;
  Node b=NIL;
  Node a = root;
  Node c;

  c = malloc(sizeof(struct node));
  c->key =x;
  c->left = NIL;
  c->right = NIL;

  while(a!=NIL){
    b=a;
    if(c->key < a->key){
      a = a->left;
    }
    else{
      a = a->right;
    }
  }

  c ->parent = b;

  if(b ==NIL){
    root =c;
  }
  else{
    if(c->key < b->key){
      b->left =c;
    }
    else{
      b->right =c;
    }
  }
}
 
void inorder(Node x){
  if(x == NIL){
    return;
  }
  inorder(x->left);
  printf(" %d",x->key);
  inorder(x->right);
}
void preorder(Node x){
  if( x ==NIL) {
    return;
  }
  printf(" %d",x->key);
  preorder(x->left);
  preorder(x->right);
}

int main(){
  int i,num,x;
char com[20];
scanf("%d",&num);
maxh=0;
for(i=0;i<num;i++){
  scanf("%s",com);
  if(strcmp(com,"insert")==0){
    scanf("%d",&x);
    insert(x);
  }
  else if(strcmp(com,"print")==0){
    inorder(root);
    printf("\n");
    preorder(root);
    printf("\n");
  }
 }
return 0;
}



Measured memory_bytes: 25140
#include <bits/stdc++.h>
using  namespace std;
typedef long long ll;
#define RAP(i, n) for(ll i=0;i<(n);i++)
#define FOR(i, a, b) for(ll i=(a);i<(b);i++)

int main(){
    string S, c, front = "", back = "";
    ll q, f, t, tcount=0;
    bool check = true;
    cin >> S >> q;
    RAP(i, q){
        cin >> t;
        if(t==1){
            check = !check;
            tcount++;
        }else{
            cin >> f >> c;
            if((f==1 && check) || (f==2 && !check)){
                front += c;
            }else{
                back += c;
            }
        }
    }
    reverse(front.begin(), front.end());
    S = front + S + back;
    if(tcount%2){
        reverse(S.begin(), S.end());
    }
    cout << S << endl;
    return 0;
}


Measured memory_bytes: 1348
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define PI acos(-1.0)
#define mod 1e9+7
using namespace std;
ll dp[100010];
int main()
{
    ll N, W;
    scanf("%lld%lld", &N, &W);
    for(int i=0; i<N; i++)
    {
        ll w, v;
        scanf("%lld%lld", &w, &v);
        for(int left=W-w; left>=0; left--)
        {
            dp[left+w]=max(dp[left+w], dp[left]+v);
        }
    }
    ll ans=0;
    for(int i=0; i<=100000; i++)
        ans=max(ans, dp[i]);
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 1024
n,k=[int(i) for i in input().split()]
h=[int(i) for i in input().split()]
dp=[0]+[100000000000]*100010
for i in range(n):
    for j in range(1,k+1):
        try:
            dp[i+j]=min(dp[i+j],dp[i]+abs(h[i+j]-h[i]))
        except:
            break
print(dp[n-1])

Measured memory_bytes: 52448
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(int i=a;i<b;i++)
#define REP(i, n) FOR(i, 0, n)
#define LAR(a, b) ((a)=max((a),(b)))
#define SML(a, b) ((b)=min((a),(b)))
typedef vector<int> vi;
#define PB push_back
#define MP make_pair

#define N 55
int s[N][3], t[N][3];
int a[3];
#define FORND(i, a, b) for(i=a; i<b; i++)
#define REPND(i, n) FORND(i, 0, n)

int rd(){
	int a, b;
	scanf("%d%d", &a, &b);
	return a*60+b;
}
int main(){
	int n;
	scanf("%d", &n);
	REP(i, n){
		REP(j, 3){
			s[i][j]=rd();
			t[i][j]=rd();
		}
	}
	int ans=0;
	REPND(a[0], n){
		REPND(a[1], n){
			REPND(a[2], n){
				int cnt=0;
				REP(i, n){
					int pl=1;
					REP(j, 3) if(t[i][j]<s[a[j]][j] || s[a[j]][j]<s[i][j]) pl=0;
					cnt+=pl;
				}
				LAR(ans,cnt);
			}
		}
	}
	printf("%d\n", ans);
}

Measured memory_bytes: 3220
n,m=map(int,input().split())

from_1=[]
to_n=[]
for i in range(m):
    a,b=map(int,input().split())
    if a==1:
        from_1.append(b)
    if b==n:
        to_n.append(a)

if len(set(from_1) & set(to_n)) >= 1:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')


Measured memory_bytes: 21836
import math

def solve(x, k, d):
    x = math.fabs(x)
    if x - k * d >= 0:
        return int(x - k * d)
    else:
        cur = x - x // d * d
        k = k - x // d
        if k % 2 == 0:
            return int(cur)
        else:
            return int(abs(cur - d))

if __name__ == "__main__":
    x, k, d = map(int, input().split(' '))
    print(solve(x, k, d))


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

void SelectionSort(int A[], int N);
static int cnt = 0;

int main(void)
{
    int N, A[100];

    cin >> N;

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

    SelectionSort(A, N);
    for(int i = 0; i < N; i++)
    {
        if(i) cout << " ";
        cout << A[i];
    }
    cout << endl << cnt << endl;

    return 0;
}

void SelectionSort(int A[], int N)
{
    for(int i = 0; i < N - 1; i++)
    {
        int minj = i;
        for(int j = i; j < N; j++)
        {
            if(A[j] < A[minj])
            {
                minj = j;
            }
        }
        if(i != minj)
        {
            swap(A[i], A[minj]);
            cnt++;
        }
        
    }
}


Measured memory_bytes: 3112
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int max(int a,int b){return (a>b)?a:b;}

int main(){
	int n;
	cin>>n;
	int p[n];
	rep(i,n)cin>>p[i];
	int q[n+1];
	rep(i,n)q[p[i]]=i;
	int ans=0,cnt=1;
	loop(i,1,n){
		if(q[i]>q[i+1]){
			ans=max(ans,i-cnt+1);
			cnt=i+1;
		}
	}
	ans=max(ans,n-cnt+1);
	cout<<n-ans<<endl;
	return 0;
}

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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;

#define rep(i,n) for(int i=0; i<(n); ++i)
#define all(n) n.begin(),n.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; }

#define DEBUG

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	int a,b,c,x;
	cin >> a >> b >> c >> x;

	int ans = 0;
	for(int i = 0; i <= a; i++)
	{
		for(int j = 0; j <= b; j++)
		{
			for(int k = 0; k <= c; k++)
			{
				int sum = 500 * i + 100 * j + 50 * k;
				if(sum == x) ans++;
			}
		}
	}

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

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

int main() {
    uint64_t A, B, K;
    std::cin >> A >> B >> K;

    if (A >= K) {
        A -= K;
    } else {
        K -= A;
        A = 0;
        if (B >= K) {
            B -= K;
        } else {
            B = 0;
        }
    }

    std::cout << A << " " << B << std::endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
typedef long long ll;

using namespace std;

// init {{{
struct ProconInit {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;

    ProconInit() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(IOS_PREC);
        if(AUTOFLUSH)
            cout << unitbuf;
    }
} PROCON_INIT;


const int NM = 101001;//ここを問題の制約を見ながらいじる．配列の確保に使う．
int A[NM];//あまり褒められたことではないが関数の外側に配列を確保すると怒られにくい．

// Main program
void solve(){
  int N;
  string S,T;
  cin >> N ;
  cin >> S ;
  cin >> T ;

  string out;
  
  for (int i=0; i<N; i++){
    out += S[i];
    out += T[i];
  }
  cout << out;
  return;
  

}

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






Measured memory_bytes: 256
#include<bits/stdc++.h>
#define lli long long int
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    lli n,r;
    cin>>n>>r;
    if(n>=10)
     cout<<r<<"\n";
    else
     cout<<r+(100*(10-n))<<"\n";
}

Measured memory_bytes: 3576
const Main = (input) => {
  const X = BigInt(input.trim())
  let deposit = 100

  let result = 0

  while (deposit < X) {
    deposit = Math.floor(deposit * 1.01)
    result += 1
  }

  console.log(result)
  return result
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'))

Measured memory_bytes: 29720
N = int(input())
A = [int(_) for _ in input().split()]

ans = 0
MOD = 10**9+7
for i in range(60):
    b = 1 << i
    cnt_1 = sum([a & b > 0 for a in A])
    cnt_0 = N - cnt_1
    b_sum = cnt_1 * cnt_0
    ans += (b_sum << i) % MOD
print(ans%MOD)


Measured memory_bytes: 137920
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 524290;
const int mod = 1e9 + 7;

int f[2][MAXN], n, m, k, a[25][25], cur;

inline void Inc(int &x, int y) { x += y; if (x >= mod) x -= mod; }
inline int Lowbit(int x) { return x & -x; }

inline int Trans(int x, int y, int z)
{
	if (x >> y & 1)
		return !z ? -1 : x;
	return !z ? x : ((x >> y) - Lowbit(x >> y) + 1) << y | (x & (1 << y) - 1);
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read() - 1, m = Read(), k = Read();
	mset(a, -1);
	for (int i = 1, x, y; i <= k; i ++)
		x = Read(), y = Read() - 1, a[x][y] = Read();
	f[0][0] = cur = 1;
	for (int i = 1; i <= m; i ++)
		for (int j = 0; j < n; j ++, cur ^= 1)
		{
			mset(f[cur], 0);
			for (int k = 0; k < (1 << n); k ++)
				if (f[cur ^ 1][k])
				{
					if (a[i][j] != 1 && ~Trans(k, j, 0))
						Inc(f[cur][Trans(k, j, 0)], f[cur ^ 1][k]);
					if (a[i][j] != 0 && ~Trans(k, j, 1))
						Inc(f[cur][Trans(k, j, 1)], f[cur ^ 1][k]);
				}
		}
	int ans = 0;
	for (int i = 0; i < (1 << n); i ++)
		Inc(ans, f[cur ^ 1][i]);
	return printf("%d\n", ans), 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

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

  rep(i, n) {
    auto itr = lower_bound(d.rbegin(), d.rend(), a[i]);
    if (itr == d.rbegin())
      d.push_back(a[i]);
    else
      *--itr = a[i];
  }
  cout << d.size() << endl;
  return 0;
}

Measured memory_bytes: 5016
n = int(input())
mod = 10**9 + 7

per = [1] * (n+1)
for i in range(1, n+1):
  per[i] = per[i-1] * i
  per[i] %= mod

inv = [1] * (n+1)
inv[-1] = pow(per[-1], mod-2, mod)
for j in range(2, n+2):
  inv[-j] = inv[-j+1] * (n-j+2)
  inv[-j] %= mod

def C(n, k):
  cmb = per[n] * inv[k] * inv[n-k]
  cmb %= mod
  return cmb

total = 0
for k in range(1, n+1):
  if n < 3*k:
    break
  total += C(n-2*k-1, k-1)
  total %= mod

print(total)


Measured memory_bytes: 9256
#include <iostream>
#include <algorithm>
#include <string> 
#include <vector>
#include <iomanip>
#include <queue>
#include <math.h>
	using namespace std;
#define lol long long



	int main()
	{
		int N;
		cin >> N;
		int A = N / 100;
		int B = N % 100;
		if (1 <= A && A <= 12 && 1 <= B && B <= 12) {
			cout << "AMBIGUOUS" << endl;
		}
		else if (0 <= A && A <= 99 && 1 <= B && B <= 12) {
			cout << "YYMM" << endl;
		}
		else if (1 <= A && A <= 12 && 0 <= B && B <= 99) {
			cout << "MMYY" << endl;
		}
		else {
			cout << "NA" << endl;
		}
	}

Measured memory_bytes: 256
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 10000000000L
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

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

__attribute__((constructor)) void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    int len[3];
    int K;
    cin >> len[0] >> len[1] >> len[2] >> K;
    vector<ll> A[3];
    rep(i, 3) {
        int inputLength = len[i];
        // DEBUG(inputLength);
        for (int j = 0; j < inputLength; j++) {
            // DEBUG(j);
            ll a;
            cin >> a;
            A[i].pb(a);
        }
    }

    rep(i, 3) {
        sort(A[i].rbegin(), A[i].rend());
    }

    // rep(i, A[0].size()) DEBUG(A[0][i]);
    // rep(i, A[1].size()) DEBUG(A[1][i]);
    // rep(i, A[2].size()) DEBUG(A[2][i]);

    vector<ll> AB;

    rep(i, A[0].size()) {
        rep(j, A[1].size()) {
            AB.pb(A[0][i] + A[1][j]);
        }
    }
    sort(AB.rbegin(), AB.rend());
    
    // rep(i, AB.size()) DEBUG(AB[i]);

    priority_queue<ll> que;
    for (int i = 0; i < AB.size() && i <= K; i++) {
        for (int j = 0; j < A[2].size() && j <= K; j++) {
            que.push(AB[i] + A[2][j]);
        }
    }

    int count = 1;
    while (!que.empty() && count <= K) {
      cout << que.top() << endl;
      que.pop();
      count++;
    }

}

Measured memory_bytes: 42744
#include <bits/stdc++.h>
using namespace std;
#define MD 1000000007
typedef long long int ll;
typedef pair<ll, ll> P;
template <typename T>
std::string tostr(const T &t){std::ostringstream os;os << t;return os.str();}
int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};

int main(){
    string s;
    cin>>s;
    int cnt=0;
    for(int i=0;i<s.length();i++){
        if(s[i]=='o') cnt++;
    }
    if(cnt+15-s.length()>=8) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define repA(i, a, n) for(int  i = a; i <= (n); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int) (x).size()
#define fill(a) memset(a, 0, sizeof(a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
#define endl '\n'
#define init(n) int n;cin>>n;int a[n];rep(i,n)cin>>a[i];
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<long long int> vll;
typedef vector<pii> vii;
ll p=1000000007;
ll const N=1e6+5;

int main() {
  
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);
    int T=1;
    // cin>>T;
    while(T--){
        ll h,w;cin>>h>>w;
        ll ans=(h*w+1)/2;
        if(h==1||w==1){
            ans=1;
        }
        cout<<ans;
    }
    return 0;   
}
 

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

using namespace std;

#define int long long


int mypower(int a, int b, int mod)
{
    int ans = 1;
    while(b)
    {
        if(b%2 == 1)
            ans = ans*a%mod;
        b=b/2;
        a=a*a%mod;
    }
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int i;
    int n;
    cin >> n;
    int pre[n+5];
    pre[0] = 0;
    for(i=1;i<(n+5);i++)
    {
        int j = i, cnt = 0;
        while(j)
        {
            int x = __builtin_popcount(j);
            j=j%x;
            cnt++;
        }
        pre[i] = cnt;
    }
    string x;
    cin >> x;
    int cnt1 = 0;
    for(i=0;i<n;i++)
        if(x[i] == '1')
            cnt1++;
    if(cnt1 == 0)
    {
       // assert(false);
        for(i=0;i<n;i++)
            cout << 1 << '\n';
        return 0;
    }
    if(cnt1 == 1)
    {
        //assert(false);
        if(x[n-1] == '1')
        {
            for(i=0;i<n-1;i++)
                cout << 2 << '\n';
            cout << 0 << '\n';
        }
        else
        {
            for(i=0;i<n-1;i++)
            {
                if(x[i] == '0')
                    cout << 1 << '\n';
                else
                    cout << 0 << '\n';
            }
            cout << 2 << '\n';
        }
        return 0;
    }
    // cnt1 > 1
    int rem = 0, remf = 0, remb = 0;
    int pw = 1;
    for(i=n-1;i>=0;i--)
    {
        rem = (rem + (x[i] - '0')*pw)%cnt1;
        pw = pw*2%cnt1;
    }
    pw = 1;
    for(i=n-1;i>=0;i--)
    {
        remf = (remf + (x[i] - '0')*pw)%(cnt1+1);
        pw = pw*2%(cnt1+1);
    }
    pw = 1;
    for(i=n-1;i>=0;i--)
    {
        remb = (remb + (x[i] - '0')*pw)%(cnt1-1);
        pw = pw*2%(cnt1-1);
    }
    vector<int> pos_idx[n+5];
    for(i=0;i<n;i++)
    {
        if(x[i] == '0')
        {
            int nrem = (remf + mypower(2, n-1-i, cnt1+1))%(cnt1+1);
            nrem = (nrem + cnt1+1)%(cnt1+1);
            pos_idx[nrem].push_back(i);
        }
        else if(x[i] == '1')
        {
            int nrem = (remb - mypower(2, n-1-i, cnt1-1))%(cnt1-1);
            nrem = (nrem + cnt1-1)%(cnt1-1);
            pos_idx[nrem].push_back(i);
        }
    }
    int ans[n];
    for(i=0;i<n+5;i++)
    {
        for(auto j : pos_idx[i])
        {
            ans[j] = 1 + pre[i];
        }
    }
    for(i=0;i<n;i++)
        cout << ans[i] << '\n';
}

Measured memory_bytes: 13964
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
int modpow(int x,int y,int md=mod){if(y==0)return 1;int ret=modpow(x,y>>1,md);ret=(ll)ret*ret%md;if(y&1)ret=(ll)ret*x%md;return ret;}
int n,ans=inf;
int x[55],y[55];
multiset<pair<int,int> >S;
void calc(int i,int j){
	int p=x[i]-x[j],q=y[i]-y[j];
	int _ans=n;
	for(int i=1;i<=n;i++){
		if(S.count(make_pair(x[i]-p,y[i]-q)))_ans--;
	}
	ans=min(ans,_ans);
}
int main(){
	cin>>n;ans=n;
	for(int i=1;i<=n;i++)cin>>x[i]>>y[i],S.insert(make_pair(x[i],y[i]));
	for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
		calc(i,j);
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
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; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

bool solve(){
  ll a,b,c,k;cin>>a>>b>>c>>k;
  if(k<=a)cout<<k<<endl;
  else if(k<=a+b)cout<<a<<endl;
  else cout<<a-(k-(a+b))<<endl;
    return false;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout<<fixed<<setprecision(30);
    solve();
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n,m;
    cin >> n >> m;
    int a[m],sum=0;
    for(int i = 0 ; i < m ;i++){
        cin >> a[i];
        sum += a[i];
    }

    if(n - sum >= 0){
        cout << n - sum << endl;
    }else{
        cout << -1 << endl;
    }

}

Measured memory_bytes: 3660
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int Maxn = 600;

int N, M;
vector<pair<int, int> > G[Maxn + 5];
int out_deg[Maxn + 5];
double f[Maxn + 5];
bool vis[Maxn + 5];
int best_edge[Maxn + 5];

double PreDFS(int u) {
	static double mx[Maxn + 5];
	if(vis[u]) return f[u];
	vis[u] = true;
	if(u == N) return f[u] = 0;
	mx[u] = 0;
	for(int i = 0; i < (int)G[u].size(); i++) {
		int v = G[u][i].first, id = G[u][i].second;
		double res = PreDFS(v);
		if(res > mx[u]) {
			mx[u] = res;
			best_edge[u] = id;
		}
		f[u] += 1.0 * (res + 1) / out_deg[u];
	}
	return f[u];
}

int del;
double DFS(int u) {
	if(vis[u]) return f[u];
	vis[u] = true;
	if(u == N) return f[u] = 0;
	for(int i = 0; i < (int)G[u].size(); i++) {
		int v = G[u][i].first, id = G[u][i].second;
		if(u == del && best_edge[u] == id) continue;
		f[u] += 1.0 * (DFS(v) + 1) / (out_deg[u] - (u == del));
	}
	return f[u];
}

int main() {
#ifdef LOACL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	scanf("%d %d", &N, &M);
	for(int i = 1; i <= M; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		G[u].push_back(make_pair(v, i));
		out_deg[u]++;
	}
	double ans = PreDFS(1);
	for(int i = 1; i <= N; i++) {
		if(out_deg[i] <= 1) continue;
		memset(f, 0, sizeof f);
		memset(vis, false, sizeof vis);
		del = i;
		ans = min(ans, DFS(1));
	}
	printf("%.7lf\n", ans);
	return 0;
}

Measured memory_bytes: 2560
using System;
using System.Text;

class Program
{
    public static void Main()
    {
        while (true)
        {
            StringBuilder sb = new StringBuilder(Console.ReadLine());
            if (sb.ToString().Equals("-")) break;
            int m = int.Parse(Console.ReadLine());
            for (int i = 0; i < m; ++i)
            {
                int h = int.Parse(Console.ReadLine());
                string sub = sb.ToString().Substring(0, h);
                sb.Remove(0, h);
                sb.Append(sub);
            }
            Console.WriteLine(sb);
        }
    }
}


Measured memory_bytes: 17992
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0;i < n;i++)
#define REP(i,n,k) for(int i = n;i < k;i++)
#define P(p) cout << (p) << endl;
#define sP(p) cout << setprecision(15) << fixed << p << endl;
#define vi vector<int>
#define printv(v) for(int i = 0;i < v.size();i++)P(v[i]);
#define printt(a,b) cout << a << " " << b << endl; 
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0};
int dy[] = { 0,  0,  1, -1};
int MOD = 1e9 + 7;

void solve() {
    int a,p;
    cin >> a >> p;
    P((a*3+p)/2);
}

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define rep(i,n) for(int i=0;i<(n);++i)

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
vector<vector<int>> d(1000,vector<int>(1000,INF));
vector<vector<char>> maze;
queue<P> que;
P start;
int R,C,N;
void bfs(){
  while(que.size()){
    P p=que.front();que.pop();
    rep(i,4){
      int nx = p.first+dx[i];
      int ny = p.second+dy[i];
      if(0<=nx && nx<R && 0<=ny && ny<C  && d[nx][ny]==INF){
        que.push(P(nx,ny));
        d[nx][ny] = d[p.first][p.second]+1;
      }
    }
  }
}
      
int main(){
  cin >> R >> C;
  maze.resize(R);
  rep(i,R){
    rep(j,C){
      char c;
      cin >> c;
      if(c=='#'){
        que.push(P(i,j));
        d[i][j]=0;
      }
      maze[i].push_back(c);
    }
  }
  int res=0;
  bfs();
  rep(i,R){
    rep(j,C){
      res = max(res,d[i][j]);
    }
  }
  cout << res << endl;
  return 0;
}



Measured memory_bytes: 13456
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
using Graph = vector<vector<int>>;
using Graphl = vector<vector<ll>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Rep(i, k, n) for (int i = k; i < (int)(n); i++)
#define RRep(i, k, n) for (int i = k; i > (int)(n); i--)
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define ALL(a)  (a).begin(),(a).end()
#define rALL(a)  (a).rbegin(),(a).rend()
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; }
template<class T> void PrintVector(const vector<T> &vec) {for (auto val : vec) cout << val << " "; cout << endl;}
const long long INF = 1LL << 40;
const int MOD = 1000000007;
const double PI = acos(-1); //3.14~
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main()
{
    ll n, k; cin >> n >> k;
    Graphl s(n);
    rep(i, n)
    {
        ll t, d; cin >> t >> d; --t;
        s[t].push_back(d);
    }

    for(auto &v : s)
    {
        sort(rALL(v));
        if (v.empty()) v.push_back(-INF);
    }

    sort(ALL(s), [&](vector<ll> a, vector<ll> b) {return a[0] > b[0];});

    ll cur = 0;
    priority_queue<ll> q;
    rep(i, k)
    {
        cur += s[i][0];
        Rep(j, 1, s[i].size()) q.push(s[i][j]);
    }
    Rep(i, k, n) rep(j, s[i].size()) q.push(s[i][j]);

    ll ans = cur + k * k;
    for (ll x = k - 1; x >= 1; --x)
    {
        ll v = s[x][0];
        ll w = q.top();
        if (v < w)
        {
            q.pop(); cur += w;
            q.push(v); cur -= v;
        }
        ans = max(ans, cur + x * x);
    }
    cout << ans << endl;
}

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

#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

typedef long long ll;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

int D, len, up;

ll Pow[20], v[20];

int Pool[20], *d = Pool + 10;

ll Dfs(ll cur, int dep) {
	if (dep == up) return !cur;
	int t = cur / v[dep]; ll res = 0;
	For (i, t - 1, t + 1) if (abs(i) <= 9 && abs(cur - i * v[dep]) < v[dep])
		res += (d[i] - (i >= 0 && !dep)) * Dfs(cur - i * v[dep], dep + 1);
	return res;
}

int main () {

	File();

	for (int tmp = (D = read()); tmp; tmp /= 10) ++ len;

	Pow[0] = 1;
	For (i, 1, 18) 
		Pow[i] = 10ll * Pow[i - 1];

	Rep (i, 10) Rep (j, 10) ++ d[i - j];

	ll ans = 0;
	For (i, len, len << 1) {
		For (j, 0, up = i >> 1)
			v[j] = Pow[i - j - 1] - Pow[j];
		ans += (i & 1 ? d[0] : 1) * Dfs(D, 0);
	}
	printf ("%lld\n", ans);

	return 0;

}

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector< vector<int> > F(N,vector<int>(10)), P(N,vector<int>(11));
  for(int i = 0; i < N; ++i){
    for(int j = 0; j < 10; ++j){
      cin >> F[i][j];
    }
  }
  for(int i = 0; i < N; ++i){
    for(int j = 0; j < 11; ++j){
      cin >> P[i][j];
    }
  }
  int ans = -1000000000;
  for(int i = 1; i < (1<<10); ++i){
    int t = 0;
    for(int j = 0; j < N; ++j){
      int c = 0;
      for(int k = 0; k < 10; ++k){
        if(((i>>k) & 1) && F[j][k]) ++c;
      }
      t += P[j][c];
    }
    ans = max(ans,t);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    ll n;
    cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        if(i%3!=0 && i%5!=0)
        {
           // cout<<i<<endl;
            ans+=i;
        }
    }
cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> l_l;
typedef pair<int , int> i_i;
typedef pair<string , int> s_i;
typedef vector<ll> vel;
typedef vector<int> vei;
typedef vector<char> vec;
typedef vector<bool> veb;
typedef vector<string> ves;
typedef vector<vector<ll>> ve_vel;
typedef vector<vector<int>> ve_vei;
typedef vector<vector<char>> ve_vec;
typedef vector<vector<bool>> ve_veb;
typedef vector<vector<string>> ve_ves;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define rep2(i,n) for(int i=2;i<(int)(n);i++)
#define repk(i,k,n) for(int i=k;i<(int)(n);i++)
#define fs first
#define sc second
#define pub push_back
#define puf push_front
#define pob pop_back
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define maxel(a) *max_element(all(a))
#define minel(a) *min_element(all(a))
#define acc accumulate
#define EPS (1e-7)
//#define INF (1e9)
#define PI (acos(-1))
#define mod (1000000007)
typedef long long int64;
const int64 INF = 1LL << 58;
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 (a>b) { a=b; return 1; } return 0; }
template<typename T> void remove(T & vector, unsigned int index){vector.erase(vector.begin() + index);}

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

    int N; cin >> N;
    vel x(N), y(N); rep(i,N) cin >> x[i] >> y[i];
    ll A = 1, B = 1;
    
    rep(i,N) {
        ll n = ceil( max( (ld) A / x[ i ], (ld) B / y[ i ] ) );
        A = n * x[i];
        B = n * y[i];
    }
    cout << A + B << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
n = int(input())

tmpx = 0
tmpy = 0
tmpt = 0
for _ in range(n):
    (t, x, y) = map(int, input().split())
    dist = abs(tmpx - x) + abs(tmpy - y)
    splt = t - tmpt
    if splt < dist:
        print('No')
        sys.exit(0)
    if (splt - dist) % 2 != 0:
        print('No')
        sys.exit(0)
    tmpx = x
    tmpy = y
    tmpt = t
print('Yes')


Measured memory_bytes: 3064
#include <stdio.h>

int main(){
	int n,ans,a,b,c,d;

	while( scanf("%d", &n)!=EOF ){
		ans = 0;
		if(n<=36){
			for(a=0 ; a<=9 ; a++){
				for(b=0 ; b<=9 ; b++){
					for(c=0 ; c<=9 ; c++){
						for(d=0 ; d<=9 ; d++){
							if((a+b+c+d)==n){
								ans++;
							}
						}
					}
				}
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}  

Measured memory_bytes: 596
n = int(input())
s = list(input())
x = len(s)
ans = []
abc = ["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
for i in range(x):
  ans.append(abc[(abc.index(s[i])+n) % 26])
print("".join(ans))

Measured memory_bytes: 39920
//
//  main.cpp
//  Test
//
//  Created by NeppsStaff on 2020/06/12.
//  Copyright © 2020 NeppsStaff. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
using namespace std ;

void doProblemA(){
    int n, q;
    string s;
    cin >> n >> q >> s;
    
    vector<int>I(q), r(q);
    for(int i = 0; i<q; i++){
        cin >> I[i] >> r[i];
    }
    vector<int>sum(n+1, 0);
    for(int i = 0; i<n; i++){
        // これだとエラー　重要→ i+1 < n and ){
//        if(s[i] == 'A' and s[i+1] == 'C' )
        if(i+1 < n and s[i] == 'A' and s[i+1] == 'C' ){
            sum[i+1] = sum[i] + 1;
        }
        else{
            sum[i+1] = sum[i];
        }
    }
    for(int i = 0; i < q; i++){
        r[i]--;
        I[i]--;
        cout << sum[r[i]] - sum[I[i]] << endl;
    }
}

void doProblemB(){
    int n;
    string s;
    cin >> n >> s;
    
    int b[300000], w[300000];
    
    int i;
    b[0] = 0;
    w[0] = 0;
    for(i = 1; i <= n; i++){
            if(s[i-1] == '.'){
                w[i] = w[i-1]+1;
                b[i] = b[i-1];
            }else{
                w[i] = w[i-1];
                b[i] = b[i-1]+1;
            }
        }
        
        int ans = 1000000;
        
        for(i = 0; i <= n; i++){
            ans = min(ans, b[i]+(w[n]-w[i]));
        }
        
        cout << ans << endl;
}

void doProblemC(){
    int A, B;
    cin >> A >> B;
    cout << A * B << endl;
}
 

int main(int argc, const char * argv[]) {
    // insert code here...
    doProblemC();
    return 0;
}


Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

int main(){

    int N;
    while(scanf("%d",&N)!=EOF){
        int sum = 1;
        int Last = N%10;
        N /= 10;
        while(N){
            if(N%10 == Last)sum++;
            else {
                sum = 1;
                Last = N%10;
            }
            if(sum >= 3)break;
            N/=10;
        }
        if(sum>=3)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}


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

int main(){
  string s;
  int i,x,r=0;
  for(;cin>>s;){
    stringstream ss;
    for(i=0;i<s.length();i++)
      if(!isdigit(s[i]))s[i]=' ';
    for(ss<<s;ss>>x;r+=x);
  }
  cout<<r<<endl;
}

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




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







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

using namespace std ;
	
	
int main () {
	ios_base::sync_with_stdio; 
	cin.tie(0) ; 
	cout.tie(0)  ; 
	string s ; 
	cin >> s ; 
	if (s[4] == s[5] && s[2] == s[3] )
		cout << "Yes" << endl  ;
	else
		cout << "No" << endl ; 

}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  long long X[N], Y[N], P[N];
  for (int i = 0; i < N; i++) {
    cin >> X[i] >> Y[i] >> P[i];
  }
  long long x_pre[1 << N][N], y_pre[1 << N][N];
  for (int s = 0; s < (1 << N); s++) {
    for (int i = 0; i < N; i++) {
      x_pre[s][i] = abs(X[i]);
      y_pre[s][i] = abs(Y[i]);
      for (int j = 0; j < N; j++)
        if ((s >> j) & 1) {
          x_pre[s][i] = min(x_pre[s][i], abs(X[i] - X[j]));
          y_pre[s][i] = min(y_pre[s][i], abs(Y[i] - Y[j]));
        }
    }
  }
  long long ans[N + 1];
  fill(ans, ans + N + 1, LLONG_MAX / 100);
  for (int s = 0; s < (1 << N); s++) {
    int n = __builtin_popcount(s);
    for (int t = s;; t = (t - 1) & s) {
      long long sum = 0;
      for (int i = 0; i < N; i++)
        if (!((s >> i) & 1)) {
          sum += min(x_pre[t][i], y_pre[s - t][i]) * P[i];
        }
      ans[n] = min(ans[n], sum);
      if (!t) break;
    }
  }
  for (int K = 0; K <= N; K++) {
    cout << ans[K] << endl;
  }
  return 0;
}


Measured memory_bytes: 11300
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return i
}

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func main() {
	sc.Split(bufio.ScanWords)
	n := nextInt()
	a := nextInts(n)

	ans := 0
	l, r := 0, 0
	for r < n {
		for r+1 < n && a[r] == a[r+1] {
			r++
		}
		ans += (r - l + 1) / 2
		l, r = r+1, r+1
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
import sys

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    L = str(input().strip())
    N = len(L)

    ans = pow(3, N, MOD)
    k = 1
    for i, b in enumerate(L, start=1):
        if b == '0':
            sub = k * 2 * pow(3, N-i, MOD) % MOD
            ans = (ans - sub) % MOD
        if b == '1':
            k = k * 2 % MOD
    return ans


if __name__ == '__main__':
    print(main())


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

ll n, ans;

void dfs(ll x) {
    if (x > n) return;
    int y = x;
    bool exists7 = false, exists5 = false, exists3 = false;
    while (y) {
        switch (y % 10) {
            case 7: exists7 = true; break;
            case 5: exists5 = true; break;
            case 3: exists3 = true; break;
        }
        y /= 10;
    }
    if (exists7 && exists5 && exists3) ans++;
    
    x *= 10;
    dfs(x + 3);
    dfs(x + 5);
    dfs(x + 7);
}

int main() {
    cin >> n;
    dfs(0);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
ll pow1(ll a, ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		{
			ans=ans*a;
		}
		a=a*a;
		b=b>>1;
	}
	return ans;
}
int dp[3005][3005];
int main()
{
	string s,t;
	cin>>s>>t;
	int i,j,ls = s.size(),lt = t.size();
	for(i=0;i<=ls;i++)
	{
		for(j=0;j<=lt;j++)
		{
			if(i == 0 || j == 0)
				continue;
			if(s[i-1] == t[j-1])
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
		}
	}
	string ans = "";
	i = ls,j = lt;
	while(i>0 && j>0)
	{
		if(s[i-1] == t[j-1])
		{
			ans += s[i-1];
			i--;
			j--;
		}
		else if(dp[i-1][j] > dp[i][j-1])
			i--;
		else
			j--;
	}
	reverse(ans.begin(),ans.end());
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 35456
answer = Array.new
while (num = $stdin.gets.to_i) > 0
	a = 0
	b = 0
	1.upto( num ){
		cards = $stdin.gets.split( /\s/ )
		n1 = cards[ 0 ].to_i
		n2 = cards[ 1 ].to_i

		a += ( n1 + n2 ) if n1 > n2
		b += ( n1 + n2 ) if n1 < n2
		if n1 == n2
			a += n1 
			b += n2 
		end

		#a += n1; b += n2 if n1 == n2
	}
	answer << [a,b]
end

answer.each{ |ans|
	printf( "%d %d\n", ans[ 0 ], ans[ 1 ] )
}


Measured memory_bytes: 6132
#include <iostream>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  string s;
  cin >> s;
  int fg = 0;
  int i = 0;
  for (; s[i]; i++) {
    if (s[i] == 'C') {
      fg++;
      break;
    }
  }
  for (; s[i]; i++) {
    if (s[i] == 'F') {
      fg++;
      break;
    }
  }
  if (fg == 2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>

int cmp(const void *a,const void *b){
    return *(int*)a > *(int*)b;
}

int main(){
    int n;
    int nums[50];

    while(~scanf("%d",&n)){
        for(int i = 0; i < n; i++) scanf("%d",&nums[i]);

        qsort(nums,n,sizeof(nums[0]),cmp);
        double sum = nums[0];
        for(int i = 1; i < n; i++)
            sum = (sum + nums[i]) / 2;
        printf("%.6g\n",sum);
    }

    return 0;
}

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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;
LL INF = 1000000007;

LL N,M,V,P;
vector<LL> A;

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  
  cin >> N >> M >> V >> P;
  A = vector<LL>(N);
  REP(i,N){
    cin >> A[i];
  }

  BACKSORT(A);
  
  vector<LL> sumA(N + 1, 0);
  REP(i,N){
    sumA[i + 1] = A[i] + sumA[i];
  }

  LL max = A[P-1];

  LL ans = P;

  FOR(i,P,N){
    if(A[i]>=max){
      ans = i + 1;
      continue;
    }
    // cout << "i" SP i << endl;
    if (A[i] + M >= A[P - 1])
    {
      //7666554321
      if(V>P){
        LL XX = i - (N - (V-P) - 1);
        // cout << "XX" SP XX << endl;
        if(XX>0){
          LL yojou = sumA[i - 1 + 1] - sumA[P - 1 - 1 + 1];
          LL diff = (i - P + 1)*(A[i] + M)-yojou;
          // cout << "yojou" SP yojou << endl;
          // cout << "diff" SP diff << endl;
          // cout << "(i-(N-(V-P)-1))" SP (i-(N-(V-P)-1)) << endl;
          if(diff<(i-(N-(V-P)-1))*M){
            break;
          }
        }
      }
      ans = i + 1;
      max = A[i];
    }
    else
    {
      break;
    }
  }

  cout << ans << endl;
}

/*
  //N問の問題
  //M人のジャッジ
  //V問選ぶ
  //P個採用
  
まず上からP問採用


投票順

推したいのに全振り
残りV-1<=P-1なら上位に全振り=>Pこ目以上になればさえよい
V-1>P-1なら下位に全振り=>Pこめ以上でかつ、全振りしてるものに推しを超えてるものがない


****X...8.****
****X....**8**
01234567890123

i-1~P

i-(N-(P-V)-1)個、余る
(i-(N-(P-V)-1))*Mだけ、余剰があるならセーフ


P-V個
*/


Measured memory_bytes: 1792
#C問題
N = int(input())
A = [int(input()) for i in range(N)]
A.sort(reverse=True)

p = 0
n = 0
if N%2 == 0:
    MAX = 0
    for i in range(N):
        if i < (N//2):
            if i == (N//2)-1:
                p+=A[i]
            else:
                p+=A[i]*2
        else:
            if i == (N//2):
                n+=A[i]
            else:
                n+=A[i]*2
    MAX = max(MAX,p-n)
else:
    MAX = 0
    for i in range(N):
        if i <= (N//2):
            if i == (N//2) or i == (N//2)-1:
                p+=A[i]
            else:
                p+=A[i]*2
        else:
            n+=A[i]*2
    MAX = max(MAX,p-n)
    p = 0
    n = 0
    for i in range(N):
        if i <= (N//2)-1:
            p+=A[i]*2
        else:
            if i == (N//2) or i == (N//2)+1:
                n+=A[i]
            else:
                n+=A[i]*2
    MAX = max(MAX,p-n)
        
print(MAX)


Measured memory_bytes: 7444
import sys
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(2000)

N = int(input())
for K in range(12) :
    if 2 ** K >= N :
        break

S = input()

path = [[] for _ in range(N)]
for _ in range(N-1) :
    a, b = map(int, input().split())
    path[a-1].append(b-1)
    path[b-1].append(a-1)

def dfs(parent, current, dp) :
    max_dp = 0
    for i in path[current] :
        if i == parent :
            continue
        dp_ = [0] * 3
        dfs(current, i, dp_)
        dp[0] += dp_[0]
        dp[1] += dp_[1]
        max_dp = max(max_dp, dp_[1]+dp_[2])
        
    if max_dp > dp[1] :
        dp[2] = max_dp - dp[1]
    else :
        dp[2] = dp[1] % 2
    
    if parent == -1 :
        return dp
        
    else :
        if S[current] == '1' :
            dp[0] += 1
            
        dp[1] += dp[0]
        dp[2] += dp[0]

ret = 10 ** 10

for root in range(N) :
    dp = dfs(-1, root, [0] * 3)
    if dp[2] == 0 :
        ret = min(ret, dp[1] // 2)
        
if ret == 10 ** 10 :
    print(-1)
else :
    print(ret)
    

Measured memory_bytes: 211460