akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

int main()
{
    //経路の数と最大コスト時間
    int N;  //経路の数
    int T;  //最大時間
    cin>>N>>T;

    //各経路のコストと最大時間
    vector<array<int, 2>> keiro;
    for(int a=0; a<N; a++)
    {
        array<int, 2> push;
        cin>>push[0]>>push[1];
        keiro.push_back(push);
    }

    //使用時間で降順ソートをかける
    sort(keiro.rbegin(), keiro.rend(),[](const array<int, 2> &left, const std::array<int,2> &right) {return left[1] < right[1];});

    //何番目の要素から時間オーバーか調べる
    for(int a=0; a<N; a++)
    {
        if(keiro[a][1]<=T)
        {
            int min=keiro[a][0];
            //帰れるときはコスト最小のものを選ぶ
            for(int b=a; b<N; b++)
            {
                if(min>keiro[b][0]) min = keiro[b][0];
            }

            cout<<min<<endl;
            return 0;
        }
    }

    //帰れないときはTLE
    cout<<"TLE"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

ll n;
V< P<ll, ll> > vw;

vvll predp;
void precalc(ll i, vll &dp) {
    vll nxt(100001, 0);
    for (ll j = 0; j <= 100000; j++) {
        chmax(nxt[j], dp[j]);
        if (j + vw[i].second <= 100000) chmax(nxt[j + vw[i].second], dp[j] + vw[i].first);
    }
    predp[i] = nxt;
    ll left = 2 * i + 1;
    if (left < n && left < ((1LL << 10) - 1)) precalc(left, nxt);
    ll right = 2 * i + 2;
    if (right < n && right < ((1LL << 10) - 1)) precalc(right, nxt);   
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    vw.resize(n);
    for (ll i = 0; i < n; i++) cin >> vw[i].first >> vw[i].second;
    predp.resize(min((1LL << 10) - 1, n));
    vll dp(100001, 0);
    precalc(0, dp);

    ll q; cin >> q;
    for (ll i = 0; i < q; i++) {
        ll v, l; cin >> v >> l;
        v--;
        if (v < ((1LL << 10) - 1)) {
            cout << predp[v][l] << '\n';
        } else {
            V< P<ll, ll> > cand;
            V<int> nodes;
            while (v >= ((1LL << 10) - 1)) {
                cand.emplace_back(vw[v]);
                v = (v - 1) >> 1;
            }
            int sz = cand.size();
            ll ans = predp[v][l];
            for (ll state = 0; state < (1LL << sz); state++) {
                ll tmpw = 0, tmpv = 0;
                for (int bit = 0; bit < sz; bit++) {
                    if ((state >> bit) & 1) {
                        tmpv += cand[bit].first;
                        tmpw += cand[bit].second;
                    }
                }
                if (tmpw <= l) {
                    chmax(ans, predp[v][l - tmpw] + tmpv);
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}


Measured memory_bytes: 815308
import sys
s = input()
odd = s[::2]
even = s[1::2]
for _ in odd:
  if _ != 'R':
    if _ != 'U':
      if _ != 'D':
        print('No')
        sys.exit()
for _ in even:
  if _ != 'L':
    if _ != 'U':
      if _ != 'D':
        print('No')
        sys.exit()
print('Yes')
    

Measured memory_bytes: 3060
// #pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vll = vector<ll>;
using vii = vector<int>;
using pii = pair<int, int>;
template <typename T = vii> 
using vec = vector<T>;

const ll INF = 1e18, MOD = 1e9 + 7;

const int MAX = 1e6;

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    // freopen("in.in", "r", stdin);
    
    int n;
    cin >> n;
    vll v(n);
    for (auto &e : v) {
        cin >> e;
    }
    vll suf(n + 1, 0);
    partial_sum(v.rbegin(), v.rend(), suf.rbegin() + 1);
    ll cur = 0, res = INF;
    for (int i = 0; i < n; i++) {
        cur += v[i];
        res = min(res, abs(suf[i + 1] - cur));
    }
    cout << res << '\n';
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main(void){
    int n;
    std::cin>>n;
    string s,t;
    std::cin>>s>>t;
    
    for(int i=0;i<n;i++){
        std::cout<<s[i]<<t[i];
    }
    std::cout<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef vector<int> vi;

#define mp make_pair
#define pb push_back

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
 
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
 
const int MOD = 1000000007;
double PI = 4*atan(1);

int par[2][200001];

map<pii,int> done;

int getpar(int city, int k) {
    if (par[k][par[k][city]] == par[k][city]) return par[k][city];
    else return par[k][city] = getpar(par[k][city],k);
}

void merge(int c1, int c2, int k) {
    c1 = getpar(c1,k), c2 = getpar(c2,k);
    if (c1 == c2) return;
    if (c1>c2) swap(c1,c2);
    par[k][c2] = c1;
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int N,K,L; cin >> N >> K >> L;
	FOR(i,1,N+1) par[0][i] = par[1][i] = i;
	F0R(i,K) {
	    int p,q; cin >> p >> q;
	    merge(p,q,0);
	}
	F0R(i,L) {
	    int r,s; cin >> r >> s;
	    merge(r,s,1);
	}
	FOR(i,1,N+1) done[mp(getpar(i,0),getpar(i,1))]++;
	FOR(i,1,N+1) cout << done[mp(getpar(i,0),getpar(i,1))] << "\n";
}

Measured memory_bytes: 13568
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <vector>
#include <math.h>

using namespace std;

#define INF 210000000

static long long gcd(long long a, long long b) {
  int amari = a % b;
  int c = b;
  if (amari == 0) {
    return b;
  } else {
    return gcd(b, amari);
  }
}

static long long lcm(long long a, long long b) { return a * b / gcd(a, b); }

int main() {
    string s;
    cin >> s;
    if(s.find('a') != string::npos && s.find('b') != string::npos && s.find('c') != string::npos){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
#define int long long
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ALL(obj) begin(obj), end(obj)
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define LOWER_BOUND(A, key) distance(A.begin(), lower_bound(ALL(A), key))
#define UPPER_BOUND(A, key) distance(A.begin(), upper_bound(ALL(A), key))

using namespace std;
using ll      = long long;
const int MOD = (int)(1e9 + 7);
const int INF = (int)(1e13 + 7);

int bpm(int x, unsigned int y) {
  if (x == 0) return 0;
  if (y == 0) return 1;
  int ans   = 1;
  int digit = (int)((log((double)y) / log((double)2) / 1 + 1));
  x %= MOD;
  for (unsigned int i = 0; i < digit; i++) {
    if (((y >> i) & 1u) == 1) ans = ans * x % MOD;
    x = x * x % MOD;
  }
  return ans;
}

signed main() {
  int N, d;
  cin >> N >> d;
  vector<vector<int>> data(N);
  rep(i, N) {
    int temp_x, temp_y, b;
    cin >> temp_x >> temp_y >> b;
    data[i] = {b, temp_x, temp_y};
  }
  sort(ALL(data));
  map<int, int> x;
  map<int, int> y;
  x[data[0][1]] = 1;
  y[data[0][2]] = 1;
  int L         = 0;
  int R         = 0;
  int ans       = 0;
  while (true) {
    if (data[R][0] - data[L][0] <= d) ans = max(ans, (x.rbegin()->first - x.begin()->first) * (y.rbegin()->first - y.begin()->first));
    if (R == N - 1) break;
    if (data[R][0] - data[L][0] <= d) {
      R++;
      x[data[R][1]] += 1;
      y[data[R][2]] += 1;
    } else if (R == L) {
      if (x[data[L][1]]-- == 1) {
        x.erase(data[L][1]);
      }
      if (y[data[L][2]]-- == 1) {
        y.erase(data[L][2]);
      }
      R++;
      L++;
      x[data[R][1]] += 1;
      y[data[R][2]] += 1;
    } else {
      if (x[data[L][1]]-- == 1) {
        x.erase(data[L][1]);
      }
      if (y[data[L][2]]-- == 1) {
        y.erase(data[L][2]);
      }
      L++;
    }
  }
  cout << ans << endl;
}



Measured memory_bytes: 29364
#![allow(non_snake_case, unused)]
use std::cmp::*;
use std::collections::*;
use std::f64::consts::*;

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn prime_factor(n: usize) -> HashMap<usize, usize> {
    let mut res = HashMap::new();
    let mut n_ = n.clone();

    for i in 2..n+1 {
        if i * i > n_ {
            break
        }
        while (n_ % i == 0) {
            *res.entry(i).or_insert(0) += 1;
            n_ /= i;
        }
    }
    if (n_ != 1) {
        res.insert(n_, 1);
    }
    res
}


fn main() {
    input!{
        mut n: usize,
    }
    let mut ans = 1;
    let mut dicts = HashMap::new();

    for i in 1..n + 1 {
        let acc = prime_factor(i);
        for (k, v) in &acc {
            *dicts.entry(*k).or_insert(0) += *v;
        }
    }

    for (k, v) in dicts {
        ans = (ans * (v+1)) % 1_000_000_007;
    }
    println!("{}", ans)
}


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

int main() {
  int n;
  cin >> n;
  int answer = 1;
  vector<int> a(n);
  int zogen = 0;//増加1→、減少-1→、初期値→0
  if (n == 1 || n == 2) goto OWA;
  for (int i = 0; i < n; i++) cin >> a[i];
  
  for (int i = 1; i < n; i++) {//どこから始める？
    if(zogen == 1 && a[i-1] <= a[i]) continue;
    else if(zogen == 1 && a[i-1] > a[i]) {
      answer++;
      zogen = 0;
    }else if(zogen == -1 && a[i-1] < a[i]) {
      answer++;
      zogen = 0;
    }else if(zogen == -1 && a[i-1] >= a[i]) continue;
    else if(zogen == 0 && a[i-1] < a[i]) zogen = 1;
    else if(zogen == 0 && a[i-1] > a[i]) zogen = -1;
  }
  OWA:
  cout << answer;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i=0; i<n; i++) cin >> a.at(i);
  
  vector<long long> cnt(n+1);
  for (int i=0; i<n; i++) {
    cnt.at(a.at(i))++;
  }
  
  long long res = 0;
  for (int i=1; i<n+1; i++) res += cnt.at(i) * (cnt.at(i) - 1) / 2;
  
  for (int i=0; i<n; i++) {
    cout << res - cnt.at(a.at(i)) + 1 << endl;
  }
  
  return 0;
}


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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  
  int count_T = 0;
  for (int i = 0; ; i++) {
    C -= B;
    if (C <= 0) {
      break;
    }
    count_T++;
  }
  
  int count_A = 0;
  for (int i = 0; ; i++) {
    A -= D;
    if (A <= 0) {
      break;
    }
    count_A++;
  }
  
  if (count_T <= count_A) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>
#include <iomanip>
typedef long long int ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const ll MOD=1000000007;
const ll MAX_N=500010;
const ll INF=999999999999;

int main(){
    string s;
    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            char a;
            cin>>a;
            if(i==j){
                s+=a;
            }
        }
    }
    cout<<s<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct sword{
	int x,y;
	bool friend operator <(sword a,sword b){
		return a.y>b.y;
	}
}a[maxn];
int main()
{
	int n,q;cin>>n>>q;int max_=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].x>>a[i].y;
		max_=max(a[i].x,max_);
	}
	sort(a+1,a+n+1);
	int ans=0;
	int i=1;
	while(a[i].y>=max_)
	{
		q-=a[i].y;ans++;
		if(q<=0)
		{
			printf("%d\n",ans);
			return 0;
		}
		i++;
	}
	while(q>0)
	{
		q-=max_;ans++;
	}
	printf("%d\n",ans);
	return 0;
}

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

#include <math.h>
#include <stdlib.h>


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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int bingo[3][3];
    bool check[3][3];
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < 3; j++){
             cin >> bingo[i][j];
             check[i][j] = false;
        }
    }    

    int n; cin >> n;
    for(int k = 0; k < n; k++){
        int b; cin >> b;
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                if(b == bingo[i][j]) check[i][j] = true;
            }
        }
    }

    bool ans = false;
    for(int i = 0; i < 3; i++){
        ans = ans || (check[i][0] && check[i][1] && check[i][2]);
        ans = ans || (check[0][i] && check[1][i] && check[2][i]);
    } 

    ans = ans || (check[0][0] && check[1][1] && check[2][2]);
    ans = ans || (check[0][2] && check[1][1] && check[2][0]);

    if(ans) cout << "Yes" << endl;
    else cout <<"No" << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using pii = pair<long, long>;
#define fix10 cout << fixed << setprecision(10);
#define rep(i,n) for(int i=0; i<(int)(n);i++)
#define MOD 1000000007

int main(){
  int n;
  long W;
  cin >> n >> W;
  vector<vector<long>> V(4);
  long min_w;
  rep(i,n){
    int w,v;
    cin >> w >> v;
    if(i == 0) min_w = w;
    w -= min_w;
    V.at(w).push_back(v);
  }
  rep(i,4){
    sort(V.at(i).begin(),V.at(i).end(),greater<long>());
    rep(j,V.at(i).size()-1){
      V.at(i).at(j+1) += V.at(i).at(j);
    }
    reverse(V.at(i).begin(),V.at(i).end());
    V.at(i).push_back(0);
    reverse(V.at(i).begin(),V.at(i).end());
  }
  vector<pii> data;
  rep(i,V.at(0).size()){
    rep(j,V.at(1).size()){
      rep(k,V.at(2).size()){
        rep(l,V.at(3).size()){
          long w = i*min_w + j*(min_w+1) + k*(min_w+2) + l*(min_w+3);
          long v = V.at(0).at(i) + V.at(1).at(j) + V.at(2).at(k) + V.at(3).at(l);
          data.push_back(pii(w,v));
        }
      }
    }
  }
  long ans = 0;
  rep(i,data.size()){
    long w = data.at(i).first;
    long v = data.at(i).second;
    if(w <= W) ans = max(ans,v);
  }
  cout << ans << endl;
}


Measured memory_bytes: 10480
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	int x, y;
	cin >> x >> y;
	if (x < y)
		swap(x, y);
	while (y > 0) {
		int r = x % y;
		x = y;
		y = r;
	}
	cout << x << endl;
}


Measured memory_bytes: 3084
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <bitset>
#include <cstring>
#include <string.h>
#include <cmath>
#include <queue>
#include <string>
#include <stack>
#include <utility>
#include <queue>
#include <cmath>
#define mp make_pair
#define pii pair<int,int> 
#define ff first
#define ss second
#define ll long long 
#define vi vector<int>

using namespace std;

ll _sieve_size; 
bitset<10000010> bs; 
vi primes; 
void sieve(ll upperbound) { 
_sieve_size = upperbound + 1; 
bs.set(); 
bs[0] = bs[1] = 0; 
for (ll i = 2; i <= _sieve_size; i++) if (bs[i]) {
for (ll j = i * i; j <= _sieve_size; j += i) bs[j] = 0;
primes.push_back((int)i);
} } 
bool isPrime(ll N) { 
if (N <= _sieve_size) return bs[N]; 
for (int i = 0; i < (int)primes.size(); i++)
if (N % primes[i] == 0) return false;
return true; 
} 

int a;

int main()
{
	sieve(11000);
	while(1)
	{	
		scanf("%d",&a);
		if(a==0)break;
		if(a%2==0)
		a-=3;
		else
		a-=2;
		//printf("%d",b);
		while(1)
		{
			if(isPrime(a)&&isPrime(a+2))
			{
				printf("%d %d\n",a,a+2);
				break;
			}
			a-=2;
		}
	}
}

Measured memory_bytes: 2444
n = int(input())
st = 0
sx, sy = 0, 0
ng = False
for _ in range(n):
    t, x, y = map(int, input().split())
    dt = (t - st)
    dx = abs(sx - x)
    dy = abs(sy - y)

    if dt%2 == (dx+dy)%2 and dx+dy <= dt:
        st = t
        sx = x
        sy = y
    else:
        ng = True
        break
print('No' if ng else 'Yes')


Measured memory_bytes: 3060
#include <iostream>
#include <stack>
#include <ctype.h>
#include <string>
using namespace std;

int main() {
	stack <int> st;
	string s;
	while(cin >> s){
		char c = s[0];
		if(isdigit(c)){
			st.push(stoi(s));
		}
		else{
			int y=st.top();
			st.pop();
			int x=st.top();
			st.pop();
			int z=0;
			if(c=='+') z=x+y;
			else if(c=='-') z=x-y;
			else if(c=='*') z=x*y;
			else if(c=='/') z=x/y;
			st.push(z);
		}
	}
	cout << st.top() <<endl;
		
	return 0;
}

Measured memory_bytes: 3208
h,w = map(int, input().split())
a0 = [[] for i in range(h)]
for i in range(h):
  a0[i] = input()
a = [j for j in a0 if "#" in j]
at0 = list(map(list, zip(*a)))
for k in range(len(at0)):
  at0[k] = "".join(at0[k])
at = [l for l in at0 if "#" in l]
for m in list(map(list, zip(*at))):
  print("".join(m))

Measured memory_bytes: 9168
#include<stdio.h>
#define A 100

main(){
  int array[A];
  int mini,tmp;
  int count=0;
  int N;
  int i,j;
  
  scanf("%d",&N);/*input includes an integer N*/
  
  for(i=1; i<=N; i++){
    scanf("%d",&array[i]);
  }
  
  for(i=1; i<=N; i++){
    mini = i;
    for(j=i; j<=N; j++){
      if(array[j]<array[mini]){
	mini=j; 
      }
    }
    if(i!=mini){
      tmp=array[i];
      array[i]=array[mini];
      array[mini]=tmp; 
      count++;
    }
  }
  
  for(i=1; i<=N; i++){
    printf("%d",array[i]);
    if(i < N){
      printf(" ");
    }
  }
  printf("\n%d\n",count);
  
  return 0;
}

Measured memory_bytes: 604
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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;
}
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin>>n;
    if (n%2==0){
        cout << n/2-1<<endl;
    }
    else {
        cout << n/2 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include  <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include<math.h>
#include<iomanip>
#include<stdio.h>
#include <stdlib.h>
#include<stdio.h>
#include <queue>
#include<map>
#include <sstream>
#include<set>
#include<stack>

//#include<bits/stdc++.h>


using namespace std;



int main() {

	int n;
	cin >> n;
	vector<int>p(n+2);
	for (int i = 1; i <= n; i++)cin >> p[i];
	vector<int>b(n + 2);
	for (int i = n; i >= 1; i--) {
		int s = 0;
		for (int j = i + i; j <= n; j += i)s += b[j];
		if (s % 2 && !p[i])b[i] = 1;
		if (s % 2 == 0 && p[i])b[i] = 1;

	}

	vector<int>a;
	for (int i = 1; i <= n; i++)if (b[i])a.push_back(i);
	cout << a.size()<< endl;
	for (int i = 0; i < a.size(); i++) {
		if (i)cout << " ";
		cout << a[i];
		if(i==n-1)cout << endl;
	}
	

	return 0;

}

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
int main() {
  int n,a[100000],i,d=0,x=1;
  scanf("%d",&n);
  for (i=0;i<n;i++) {
    scanf("%d",&a[i]);
  }
  for (i=1;i<n;i++) {
    if (d==0&&a[i]-a[i-1]!=0) {
      d=(a[i]-a[i-1])/(abs(a[i]-a[i-1]));
    }
    if (d*(a[i]-a[i-1])<0) {
      x++;
      d=0;
    }
  }
  printf("%d\n",x);
  return 0;
}

Measured memory_bytes: 512
N, W = map(int, input().split())
items = [[0, 0]]

for i in range(N):
	v, w = map(int, input().split())
	items.append([v, w])

# dp table (N + 1) * (W + 1)
dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
	for w in range(1, W + 1):
		# print(dp)
		if items[i][1] <= w:
			dp[i][w] = max(dp[i-1][w], dp[i-1][w-items[i][1]] + items[i][0])
		else:
			dp[i][w] = dp[i-1][w]

print(dp[N][-1])


Measured memory_bytes: 25504
#include<stdio.h>
int main()
{
    int x, a, b;
    scanf("%d%d%d",&x, &a, &b);
    if(-a+b<=0)
        printf("delicious\n");
    else if(-a+b<=x)
        printf("safe\n");
    else
        printf("dangerous\n");
    return 0;
}

Measured memory_bytes: 128
import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

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

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

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""


N =  int(sys.stdin.readline())
A =  int(sys.stdin.readline())

print(N ** 2 - A)

Measured memory_bytes: 64492
#include<iostream>
using namespace std;
int main(){
    int n,total=0;
    cin>>n;
    int d[n];
    for(int i=0;i<n;i++)cin>>d[i];
    for(int i=0;i+1<n;i++)for(int j=i+1;j<n;j++)total+=d[i]*d[j];
    cout<<total<<endl;
}

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

using namespace std;

int main() {
	string x;
	cin >> x;
	for (int i = x.size() - 1; i >= 0; --i) {
		cout << x[i];
	}
	cout << endl;
	//{char c; cin >> c;}
	return 0;
}

Measured memory_bytes: 1172
#
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


x = I()
if x <= 6:
    ans = 1
elif x <= 11:
    ans = 2
else:
    ans = (x // 11) * 2
    if x % 11 == 0:
        pass
    elif x % 11 <= 6:
        ans += 1
    elif x % 11 <= 10:
        ans += 2
print(ans)


Measured memory_bytes: 9220
A=[]
B=[]
for i in range(3):
  A.extend(list(map(int,input().split())))

n=int(input())
for i in range(n):
  b=int(input())
  try:
    A[A.index(b)]=0
  except:
    continue

if A[0]==A[1]==A[2] or A[3]==A[4]==A[5] or A[6]==A[7]==A[8] or A[0]==A[3]==A[6] or A[1]==A[4]==A[7] or A[2]==A[5]==A[8] or A[0]==A[4]==A[8] or A[2]==A[4]==A[6]:
  print('Yes')
else:print('No')

Measured memory_bytes: 3064
a = list(map(int, input().split()))
b = list(map(int, input().split()))
t = int(input())

v = a[1]
w = b[1]

if v <= w:
    print('NO')
else:
    s = v - w
    d = abs(b[0] - a[0])
    if d / s <= t:
        print('YES')
    else:
        print('NO')

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

int main(){
  int n=0;
  cin>>n;
  int arr[n+1]={0};
  cin>>arr[1];
  pair<int,int> jumps[n+1]={};
  for(int i=2;i<=n;i++){
    cin>>arr[i];
    jumps[i-2].second=abs(arr[i-2]-arr[i]);
    jumps[i-1].first=abs(arr[i-1]-arr[i]);
  }
  long long int dp[n+1]={0};
  jumps[0].second=1e5;
  for(int i=2;i<=n;i++){
    dp[i]=dp[i-1]+jumps[i-1].first;
    if(dp[i]>dp[i-2]+jumps[i-2].second) dp[i]=dp[i-2]+jumps[i-2].second;
  }
  cout<<dp[n]<<endl;
  cin>>n;
  return 0;
}


Measured memory_bytes: 2176
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.nextLine());
		
		for(int i = 0; i < n; i++){
			int out = 0;
			int runner = 0;
			int score = 0;
			
			while(out != 3){
				String str = sc.next();
				if("OUT".equals(str)){
					out++;
				}else if("HIT".equals(str)){
					runner++;
					if(runner > 3){
						score++;
						runner = 3;
					}
				}else if("HOMERUN".equals(str)){
					score += runner + 1;
					runner = 0;
				}
			}
			System.out.println(score);
		}
	}
}

Measured memory_bytes: 12000
n, k = map(int, input().split())
ans = 0

for i in range(1,n+1):
    point = 0
    if i >= k:
        ans += 1/n
    else:
        point = i
        count = 0
        while point < k:

            point *= 2
            count += 1
        ans += (1/n)*((1/2)**count)

print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x ,n) for(int i = x; i < n; i++)
#define repr(i, n) for(int i = n; i >= 0; i--)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
int main(){
    int n,b=2,p=2,ans=0;
    cin >> n;
    
    if(n==1){
        cout << 1;
        return 0;
    }
    
    while(1){
        while(1){
            if(pow(b,p)<=n)ans=max(ans,(int)pow(b,p));
            if(pow(b,p)>n) break;
            p++;
        }
        b++;p=2;
        if(pow(b,p)>n)break;
    }
    
    cout << ans;
    
    return 0;
}

Measured memory_bytes: 4024
#include <bits/stdc++.h>
using namespace std;
struct Fast {
    Fast() {
        std::cin.tie(0);
        ios::sync_with_stdio(false);
        cout.precision(20);
    }
} fast;

/* define */
#define FOR(I, X, Y) for (long long(I) = (X); (I) < (Y); (I)++)
#define REP(I, X, Y) for (long long(I) = (Y)-1; (I) >= (X); (I)--)
#define ALL(X) (X).begin(), (X).end()
#define pb push_back
#define COUNT(V, X)                           \
    (upper_bound((V).begin(), (V).end(), X) - \
     lower_bound((V).begin(), (V).end(), X))
#define debug(x) cerr << #x << ':' << x << endl;
#define DEBUG(v)                             \
    {                                        \
        cerr << #v << ':';                   \
        for (auto xv : v) cerr << xv << ' '; \
        cerr << endl;                        \
    }
#define Yes(X) cout << (X ? "Yes" : "No") << endl;
#define YES(X) cout << (X ? "YES" : "NO") << endl;
#define ctoi(C) (C - '0')
#define pow2(x) ((long long)((long long)1 << x))

/* alias */
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vii = vector<vector<int>>;
using vl = vector<long long>;
using vll = vector<vector<long long>>;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
template <typename T>
using PQ = priority_queue<T>;
template <typename T>
using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const long long dx[] = {1, 0, -1, 0};
const long long dy[] = {0, 1, 0, -1};
const long long dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
const long long dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const long long dx9[] = {1, 1, 0, -1, -1, -1, 0, 1, 0};
const long long dy9[] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int INF = 1000000007;
const long long LINF = 1000000000000000007;

/* func */
template <typename T1, typename T2>
inline bool chmin(T1 &a, const T2 &b) {
    if (a > b) a = b;
    return a > b;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) a = b;
    return a < b;
}
long long max(long long x, int y) {
    return max(x, (long long)y);
}
long long max(int x, long long y) {
    return max((long long)x, y);
}
long long min(long long x, int y) {
    return min(x, (long long)y);
}
long long min(int x, long long y) {
    return min((long long)x, y);
}

/* library */

/* main */

signed main() {
    ll N;
    cin >> N;
    ll ans[N];
    FOR(i, 0, N) {
        ans[i] = INF;
    }
    FOR(i, 0, N - 1) {
        ll B;
        cin >> B;
        ans[i] = min(ans[i], B);
        ans[i + 1] = min(ans[i + 1], B);
    }
    ll a = 0;
    FOR(i, 0, N) {
        a += ans[i];
    }
    cout << a << endl;
}

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

public class Main {

    public static void main(String[] args) {

        int f = 2;
        int s = 1;
        String str = null;
        InputStreamReader isr = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(isr);

        try {
            str = br.readLine();

            String[] i = str.split(" ");


            for (int j = 0; j < 3; j++) {
                if (i[j].equals("5")) {
                    --f;
                } else if (i[j].equals("7")) {
                    --s;
                }
            }
        } catch (NumberFormatException e) {
            System.out.println("NO");
        } catch (IOException e) {
            System.out.println("NO");
        }
        if (f == 0 && s == 0) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

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


int main() {
    int N, A, B;
    cin >> N >> A >> B;
    int sum = 0;
    int total = 0;
    for (int i = 1; i <= N; ++i) {
        int a = i;
        while (a > 0) {
            sum += a % 10;
            a /= 10;
        }
        if (sum >= A && sum <= B) {
            total += i;
            sum = 0;
        } else {
            sum = 0;
        }
    }
    cout << total << endl;
}

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

const int MODULO = 1e9 + 7;

int nbLig, nbCol;
char grid[1000][1000];
int nbPaths[1000][1000];
bool vu[1000][1000];

int dfs(int lig, int col){
    if (lig >= nbLig || col >= nbCol || nbPaths[lig][col] == -1) return 0;
    if (vu[lig][col]) return nbPaths[lig][col];

    int curNbPath = dfs(lig+1, col) + dfs(lig, col+1);
    nbPaths[lig][col] = (curNbPath % MODULO);
    vu[lig][col] = true;

    return curNbPath;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> nbLig >> nbCol;

    

    for (int i = 0; i < nbLig; i++){
        for (int a = 0; a < nbCol; a++){
            char car; cin >> car;
            nbPaths[i][a] = -(car == '#');
        }
    }

    vu[nbLig-1][nbCol-1] = true;
    nbPaths[nbLig-1][nbCol-1] = 1;

    cout << dfs(0,0) % MODULO << endl;
}

Measured memory_bytes: 9088
#include<stdio.h>
int main(void)
{
        int n;
        int d[100];
        int i;
        int j,min,m;
        int s=1;
        scanf("%d",&n);
        for(i=0;i<n;i++) scanf("%d",&d[i]);
        for(i=0;i<n;i++){
                min=d[i]; m=i;
                for(j=i+1;j<n;j++) if(d[j]<=min){min=d[j]; m=j;}
                d[m]=d[i]; d[i]=min;
        }
        for(i=1;i<n;i++) if(d[i]!=d[i-1]) s++;
        printf("%d\n",s);
        return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
    string s;
    cin >> s;
    int k;
    cin >> k;
    priority_queue<string, vector<string>, greater<string> > in;
    for(int i = 0; i < s.size(); i++){
        for(int j = i; j < s.size(); j++){
            if(j > (i + 6)){
                break;
            }
            string l = s.substr(i, j - i + 1);
            in.push(l);
        }
    }
    string before = "gjoeaiweor";
    while(k > 0){
        string now = in.top();
        if(before == now){
            in.pop();
            continue;
        }
        before = now;
        k--;
        in.pop();
    }
    cout << before << endl;
    return 0;
}

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

typedef long long ll;

int main() {
    string S, T;
    cin >> S >> T;
    vector<int> start(26, -1);
    vector<int> goal(26, -1);

    for (int i = 0; i < S.size(); i++) {
        int a = S[i] - 'a';
        int b = T[i] - 'a';

        if (start[a] != -1 || goal[b] != -1) {
            if (start[a] != b || goal[b] != a) {
                cout << "No" << endl;
                return 0;
            }
        } else {
            start[a] = b;
            goal[b] = a;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 776
n=gets.to_i
as=gets.split.map(&:to_i)
fourfolds=0
evens=0
odds=0
as.each do |an|
  if an%4==0
    fourfolds+=1
  elsif an.even?
    evens+=1
  else
    odds+=1
  end
end
if odds==0
  puts "Yes"
else
  fourfolds+=1 if evens==0
  if odds<=fourfolds
    puts "Yes"
  else
    puts "No"
  end
end


Measured memory_bytes: 8452
object Main {

  class UnionFindRank(val n: Int) {
    private[this] val par = Array.range(0, n)
    private[this] val rank = Array.fill(n)(1)

    def root(x: Int): Int =
      if(par(x)==x) x
      else {par(x) = root(par(x)); par(x)}

    def same(x: Int, y: Int): Boolean = root(x)==root(y)

    def unite(ax: Int, ay: Int): Unit = {
      val x = root(ax)
      val y = root(ay)
      if(x!=y){
        if(rank(x) < rank(y)) par(x) = y
        else {
          par(y) = x
          if(rank(x) == rank(y))rank(x) = rank(x)+1;
        }
      }
    }
  }

  def main(args: Array[String]): Unit = {

    val Array(n,q,_*) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
    val uf = new UnionFindRank(n)

    for(i <- 1 to q){
      val Array(com,x,y,_*) = scala.io.StdIn.readLine.split(" ").map(_.toInt)
      if(com==0)uf.unite(x,y)
      else println(if(uf.same(x,y)) 1 else 0)
    }

  }

}

Measured memory_bytes: 84820
#include <iostream>
#include <sstream>
using namespace std;
#include <bits/stdc++.h>
#include<utility>
#include <algorithm>
#include<iterator>
#define  go return 0
#define rep(i,n) for(int i=0;i<n;++i)
#define rep(j,m) for(int j=0;j<m;++j)
#define REP(i,n) for(int i=1;i<=n;++i)
#define all(v)   ((v).begin()), ((v).end())
#define len(s)   ((int)s.size())
#define F first
#define S second
#define pb push_back
#define pf push_front
#define mp make_pair
typedef long long ll;
typedef double db;
typedef vector<int> ve;
typedef vector<pair<char,int> >vepa;
typedef set<string>se;
typedef map<char ,int> mpp;
const ll N=1e5+5 ,OO=1e18;
const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};
int TC,n,a,arr[N],dp[1000][100];
bool vis[N],f;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
     int x,y;
    cin>>x>>y;
    if(y&1|| y>4*x || y<2*x ){
        puts("No");
    }else{
     puts("Yes");
    }
go;
}


Measured memory_bytes: 3648
#include <iostream>
#include <string>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <climits>
#include <set>
using namespace std;
 
long long A[100000];
long long gcd_from_head[100000];
long long gcd_from_tail[100000];
long long gcd(long long a, long long b){
    if(a < b){
        long long tmp = b;
        b = a;
        a = tmp;
    }
    if(b == 0){
        return a;
    }
    return gcd(b, a % b);
}


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

    gcd_from_head[0] = A[0];
    for(int i = 1; i < N; i++){
        gcd_from_head[i] = gcd(A[i], gcd_from_head[i - 1]);
    }
    gcd_from_tail[N - 1] = A[N - 1];
    for(int i = N - 2; i >= 0; i--){
        gcd_from_tail[i] = gcd(A[i], gcd_from_tail[i + 1]);
    }

    long long ans = gcd_from_tail[1];
    for(int i = 0; i < N - 2; i++){
        ans = max(ans, gcd(gcd_from_head[i], gcd_from_tail[i + 2]));
    }
    ans = max(ans, gcd_from_head[N - 2]);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 2560
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;
const int MOD = 1000000007;
const int iINF = 1001001001;
const long long llINF = 1LL << 60;
int h, w;
int main()
{
	int n;
	cin >> n;
	vector<P> d(n);
	rep(i, n) {
		int x, l;
		cin >> x >> l;
		d[i] = make_pair(x + l, x - l);
	}
	sort(d.begin(), d.end());
	int cur = -iINF;
	int ans = 0;
	rep(i, n) {
		if (cur <= d[i].second) {
			++ans;
			cur = d[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3928
import java.util.Arrays;
import java.util.Scanner;

class Main
{
  static void do_left(String s, int[] v, int idx){
	while(idx > 0 && s.charAt(idx) == '>'){
      v[idx - 1] = Math.max(v[idx] + 1, v[idx - 1]);
      idx -= 1;
    }
  }

  static void do_right(String s, int[] v, int idx){
    while(idx < s.length() - 2 && s.charAt(idx + 1) == '<'){
      v[idx + 1] = Math.max(v[idx] + 1, v[idx + 1]);
      idx += 1;
    }
  }
  
  public static void main(String... args){
	Scanner scanner = new Scanner(System.in);
	String s = ">" + scanner.next() + "<";
    int[] v = new int[s.length() - 1];

    for(int i = 0; i < s.length() - 1; i++){
      if(s.charAt(i) == '>' && s.charAt(i + 1) == '<'){
        do_left(s, v, i);
        do_right(s, v, i);
      }
    }

    //Arrays.stream(v).forEach(x -> System.out.print(x + ","));
    //System.out.println();
	long[] sum = new long[1];
    Arrays.stream(v).forEach(x -> { sum[0] += x; });
    System.out.println(sum[0]);    
  }
}


Measured memory_bytes: 36832
a = int(input()) # 500 yen coins
b = int(input()) # 100 yen coins
c = int(input()) #  50 yen coins
x = int(input()) # X yen

count = 0
tmp = 0

for i in range(a,-1,-1) :
  tmp_500 = 500 * i
  if tmp_500 > x :
    continue

  for j in range(b,-1,-1) :
    tmp_100 = tmp_500 + j * 100
    if tmp_100 > x :
      continue

    for k in range(c,-1,-1) :
      tmp_50 = tmp_100 + k * 50
      #print(tmp_50)
      if tmp_50 > x :
        continue
      elif tmp_50 == x :
        count += 1

print(count)

Measured memory_bytes: 3064
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n = f()[0]
    a = f()

    cnt = {}
    for i in a:
        if i in cnt:
            cnt[i] += 1
        else:
            cnt[i] = 1
    
    ans = 0
    for k,v in cnt.items():
        if k!= v:
            if k>v:
                ans += v
            else:
                ans += v - k 
    
    print(ans)


solve()


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

#define endl '\n'
#define ends ' '
#define die(x) return cout << x << endl, 0
#define all(v) v.begin(), v.end()
#define sz(x) (int)(x.size())
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << ends << H; debug_out(T...); }
#define debug(...) cerr << "{" << #__VA_ARGS__ << "}:", debug_out(__VA_ARGS__)
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const ll MOD = 998244353;
 
////////////////////////////////////////////////////////////////////

const int N = 18 + 1;

pii DP[1 << N];

void Add(pii &a, int x) {
	if (a.first < x) a.second = a.first, a.first = x;
	else if (a.second < x) a.second = x;
}
pii Sync(pii a, pii b) {
	Add(a, b.first), Add(a, b.second);
	return a;
}

int main() {

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	mt19937 Rnd(time(0));
	
	int n; cin >> n;
	for (int i = 0; i < (1 << n); i++) {
		int x; cin >> x;
		DP[i] = make_pair(x, 0);
	}
	for (int i = 0; i < n; i++) for (int mask = (1 << n) - 1; mask >= 0; mask--) {
		if ((mask >> i) & 1) DP[mask] = Sync(DP[mask], DP[mask ^ (1 << i)]);
	}
	int ans = 0;
	for (int i = 1; i < (1 << n); i++) {
		ans = max(ans, DP[i].first + DP[i].second);
		cout << ans << endl;
	}
	
	return 0;
}


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

using namespace std;
using ll = long long;

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

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

  int ans = 0;
  for (int i = 1; i <= n; i += 2) {
    int now = 0;
    for (int j = 1; j <= i; ++j) {
      if (i % j == 0) ++now;
    }
    if (now == 8) ++ans;
  }

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


Measured memory_bytes: 3572
#include <bits/stdc++.h>
using namespace std;
 
long long gcd(long long  a, long long b){
  if(a%b == 0)
    return b;
  else
    return gcd(b,a%b);
}
 
int main(){
  long long A, B; cin >> A >> B;
  int sol = 1;
  
  long long val = gcd(A,B);
  long long val_r = pow(val,0.5);
 
  for(int i=2; val>1; i++){
    if(i > val_r){
      if(val != 0)
        sol++;
      break;
    }

    if(val%i != 0)
      continue;

    while(val%i == 0){
      val /= i;
    }
    sol++;
    
  }
  
  cout << sol << endl;
}

Measured memory_bytes: 640
parseInt(x) = parse(Int, x)
parseArray(x::Array{SubString{String},1}) = map(parseInt, x)

type Edge
  from::Int
  to::Int
  cost::Float64
end

function bellmanFord(
  n_vertices::Int, edges::Array{Edge}, s_edge::Int
)::Array{Float64}
  # d[i] = min{d[j] + (cost from j to i) | e = (j to i) in E}

  n_edges = length(edges)
  d_cost = fill(Inf, n_vertices)
  d_cost[s_edge] = 0

  updated = true
  i = 1
  while updated
    updated = false
    for e in edges
      prev = d_cost[e.to]
      d_cost[e.to] = min(d_cost[e.to], d_cost[e.from] + e.cost)
      d_cost[e.to] != prev && (updated = true)
      (i >= n_vertices && d_cost[e.to] != prev) && (d_cost[e.to] = -Inf)
    end
    i += 1
  end

  d_cost
end

function main()
  n_vertices, m_edges, p_cost = readline() |> split |> parseArray
  a_vertex = zeros(Int, m_edges)
  b_vertex = zeros(Int, m_edges)
  c_cost = zeros(Int, m_edges)
  for i in 1:m_edges
    a_vertex[i], b_vertex[i], c_cost[i] = readline() |> split |> parseArray
  end

  c_cost -= p_cost
  c_cost *= -1
  edges = zip(a_vertex, b_vertex, c_cost) |> a -> map(t -> Edge(t...), a)

  d_cost = bellmanFord(n_vertices, edges, 1)

  println(d_cost[n_vertices] |> x -> x == -Inf ? -1 : max(Int(-x), 0))
end

main()


Measured memory_bytes: 120276
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String arg[]) {
		Scanner sc = new Scanner(System.in);

		int A = sc.nextInt();
		int B = sc.nextInt();
		int K = sc.nextInt();
		
		List <Integer> Adivisor = new ArrayList<Integer>();
		List <Integer> Bdivisor = new ArrayList<Integer>();
		List <Integer> ABdivisor = new ArrayList<Integer>();
		
		for(int i=1; i<=A; i++) {
			if(A%i==0) {
				Adivisor.add(A/i);
			}
		}
		
		for(int i=1; i<=B; i++) {
			if(B%i==0) {
				Bdivisor.add(B/i);
			}
		}
		
		for(int i=0; i<Adivisor.size(); i++) {
			for(int j=0; j<Bdivisor.size(); j++) {
				if(Adivisor.get(i)==Bdivisor.get(j)) {
					ABdivisor.add(Adivisor.get(i));
				}
			}
		}
		
		System.out.print(ABdivisor.get(K-1));
	}
}

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

long inf = 1000000007;


int main() {
	int h, a;
	cin >> h >> a;
	if (h % a == 0) {
		cout << h / a << endl;
	}
	else {
		cout << h / a + 1 << endl;
	}
}
	


Measured memory_bytes: 256
#include<stdio.h>

int main()
{
  int n, F[44], i, j;
  scanf("%d", &n);
  F[0] = 1;
  F[1] = 1;
  for(i = 2; i <= n; i++){
    F[i] = F[i-1]+F[i-2];
  }
  printf("%d\n", F[n]);
  return 0;
}

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

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める

int main(){
    int N;
    cin >> N;
    vector<int> num(100001,0);
    REP(i,N){
        int a;
        cin >> a;
        num[a]++;
    }

    ll ans=0;
    REP(i,100001){
        ans += i * num[i];
    }

    int q;
    cin >> q;
    REP(i,q){
        int b,c;
        cin >> b >> c;
        num[c] += num[b];
        ans += ( c - b ) * num[b];
        num[b] = 0;
        cout << ans << endl;
    }
    

    return 0;
}

Measured memory_bytes: 3780
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

int main() {
    int n;
    cin >> n;
    map<int,int> m;
    for(int i = 0;i < n;i++){
        m.insert(make_pair(i+1,0));
    }
    
    int a;
    for(int i = 0;i < n-1;i++){
        cin >> a;
        m[a-1]++;
    }
    m.erase(n);
    for(auto i = m.begin();i != m.end();i++){
            cout << i->second << endl;
    }
}



Measured memory_bytes: 12980
#include <iostream>

using namespace std;

long long int MOD=1000000007;

long long int POWER(long long int K, long long int p) {

	if (p==0) { return 1; }

	if ((p % 2) == 1) { return (POWER(K, p - 1)*K) %MOD; }
	
		long long int tmp = POWER(K, p / 2);
		return (tmp*tmp) % MOD;
	
}

long long int INV(long long int K) {
	return POWER(K, MOD - 2);
}

long long int fac[200005];

long long int C(long long int n, long long int m) {

	long long int ret = 1;
	ret = fac[n] * INV(fac[n - m]);
	ret %= MOD;
	ret *= INV(fac[m]);
	ret %= MOD;

	return ret;
}

long long int NB, NW;

int main(void) {

	cin >> NB >> NW;

	fac[0] = 1;

	for (int i = 1; i <= 200000; i++) {
		fac[i] = fac[i - 1] * i; fac[i] %= MOD;
	}


	long long int Pw = 0;
	long long int Pb = 0;

	long long int NUM = 1;

	for (int i = 1; i <= NB + NW; i++) {
		long long int tmp = 1 + (MOD - Pw) + (MOD - Pb); tmp %= MOD;
		tmp *= INV(2);
		tmp %= MOD;
		cout << (Pb + tmp) % MOD << endl;

		NUM *= INV(2); NUM %= MOD;

		if (NB <= i) {
			long long int H = C(i - 1, NB - 1);
			H *= NUM; H %= MOD;
			Pw += H; Pw %= MOD;
		}

		if (NW <= i) {
			long long int H = C(i - 1, NW - 1);
			H *= NUM; H %= MOD;
			Pb += H; Pb %= MOD;
		}
	}


	//system("pause");
	return 0;
}

Measured memory_bytes: 3712