akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define PRINT(x) cout<<(x)<<endl
#define INF 1000000000000 // 10^12
#define MOD 1000000007 // 10^9+7
#define PB push_back
#define MP make_pair

const int MAX_N = 100000;

int N;
pair<int, int> x[MAX_N], y[MAX_N];

struct edge { int u, v, d; };
vector<edge> es;

bool comp_edge(const edge& e1, const edge& e2) {
    return e1.d < e2.d;
}

struct UnionFind {
    vector<int> par;

    UnionFind(int N) : par(N) {
        REP(i, N) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    cin >> N;
    int xi, yi;
    REP(i, N) {
        cin >> xi >> yi;
        x[i] = MP(xi, i);
        y[i] = MP(yi, i);
    }
    sort(x, x + N);
    sort(y, y + N);
    REP2(i, 1, N) {
        es.PB(edge{ .u = x[i-1].second, .v = x[i].second, .d = x[i].first - x[i-1].first });
        es.PB(edge{ .u = y[i-1].second, .v = y[i].second, .d = y[i].first - y[i-1].first });
    }
    sort(es.begin(), es.end(), comp_edge);
    UnionFind city(N);
    int min_cost = 0;
    REP(i, es.size()) {
        if (city.same(es[i].u, es[i].v)) continue;
        city.unite(es[i].u, es[i].v);
        min_cost += es[i].d;
    }
    PRINT(min_cost);
    return 0;
}

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

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<bool> snuke(n, true);
    for (int i = 0; i < k; i++) {
        int d;
        cin >> d;
        for (int j = 0; j < d; j++) {
            int a;
            cin >> a;
            snuke.at(a - 1) = false;
        }
    }
    int ans = 0;
    for (bool x : snuke) {
        if (x == true) {
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3632
(N,M),*AB = $<.map{|ln| ln.split.map(&:to_i) }

g, *W = 0, *0..M
D = lambda{|d|
	return M < d ? M : W[d] == d ? d : W[d] = D[W[d]]
}
AB.sort_by{|*,b|-b}.each{|a,b|
	next if M == d = D[a-1]
	g, W[d] = g+b, d+1
}
p g


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

int main(){
    using namespace std;

    unsigned long N;
    cin >> N;
    array<unsigned long, 3> ans{0, 0, 0};
    while(N--){
        unsigned long st{0}, nd{0}, j{0}, c{0};
        for(auto& i : ans){
            unsigned long a;
            cin >> a;
            i += a;
            if(st < i){
                nd = st;
                st = i;
                j = c;
            }else if(nd < i)nd = i;
            ++c;
        }
        fill(ans.begin(), ans.end(), st);
        ans[j] = nd;
    }
    cout << *max_element(begin(ans), end(ans)) << endl;
}

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

using namespace std;

int N;

int Search(int x, int L, int R, int* p) {
	if (R - L == 1) {
		if (x >= p[L])
			return R;
		return L;
	}

	int Mid = (L + R) / 2;

	if (x >= p[Mid])
		return Search(x, Mid, R, p);
	return Search(x, L, Mid, p);
		

}


int main() {

	cin >> N;

	int * A = new int[N];
	int * B = new int[N];
	int * C = new int[N];

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

	sort(A, A + N);
	sort(B, B + N);
	sort(C, C + N);

	long long int * S = new long long int[N];
	for (int i = 0; i < N; i++)
		S[i] = N - Search(B[i], 0, N, C);

	for (int i = N - 1; i > 0; i--)
		S[i - 1] += S[i];

	long long int Ans = 0;
	for (int i = 0; i < N; i++) {
		if (Search(A[i], 0, N, B) == N)
			continue;
		Ans += S[Search(A[i], 0, N, B)];
	}
	cout << Ans << endl;
	return 0;
}

Measured memory_bytes: 2176
#include <iostream>
#include <vector>

using namespace std;
typedef unsigned long long int ll;

const ll INF = ((ll)1<<31) - (ll)1;

template <typename T>
class SegTree{
public:
	// ????????????????????±
	struct node {
		T v;
		node(){
			v = INF;
		}
		// ?????????????????´??°
		void update(T _v){
			v = _v;
		}
		// ??????????????´??°
		void merge(T vl, T vr){
			v = min(vl, vr);
		}
		// ????????????????????????
		T get(){
			return v;
		}
	};

	vector<node> data;
	int N;
	SegTree(int _N){
		// _N <= (N = 2^k) ???????????????
		N = 1;
		while( N < _N ) N<<=1;
		data.resize(N*2+5);
	}

	// ?????°???????????????????????´??°
	void update(int l, T v){
		if( l >= N ) return;
		int k = l + N;	// ???????????????
		data[k].update(v);
		updateNode( k/2 );
	}
	// ???????????????????????£?????´??°
	void updateNode(int k){
		if( k <= 0 ) return;	// ???????????¶
		data[k].merge( data[k*2].get(), data[k*2+1].get() );
		updateNode(k/2);	// ??????
	}

	// ???????????? [l,r)
	T get(int l, int r, int a=0, int b=-1, int k=1){
		if( b == -1 ) b = N;
		//cout << l << " " << r << " " << a << " " << b << " " << k << endl;
		node nd;
		// ?????¨?????????????????´???
		if( l <= a && b <= r ) return data[k].get();
		// ?????¨?????????????????´???
		if( r <= a || b <= l ) return nd.get();
		// ?????????????????????????????´???
		int m = (a+b) / 2;
		T vl = get(l,r, a, m, k*2);
		T vr = get(l,r, m, b, k*2+1);
		nd.merge( vl, vr );
		return nd.get();
	}
};


// AOJ DSL_2_A

#define rep(i,n) for(int i=0; i<(n); i++)
#define rrep(i,n) for(int i=(n)-1; i>=0; i--)
#define all(X) (X).begin(),(X).end()

typedef pair<int,int> pii;

SegTree<ll> sg(100005);
int main(){
	int n, q;
	cin >> n >> q;
	rep(i,q){
		int c, x, y;
		cin >> c >> x >> y;
		if( c == 0 ){
			sg.update(x, y);
		}else{
			y++;
			cout << sg.get(x, y) << endl;
		}
		//rep(j,18) cout << sg.data[j].get() << " "; cout << endl;
	}
	return 0;
}

Measured memory_bytes: 4772
import sys
input = sys.stdin.buffer.readline
import math

def main():
    N,a,b = map(int,input().split())
    MOD = 10**9+7
    
    def Comb(N, r, mod):
        x = 1
        y = 1
        for i in range(1, r + 1):
            x = x * (N-i+1) % mod 
            y = y * i % mod
        return (x*pow(y, mod-2, mod)) % mod

    s = pow(2,N,MOD) 
    a = Comb(N,a,MOD)
    b = Comb(N,b,MOD)
    ans = (s-1-a-b) % MOD

    print(int(ans))
    
if __name__ == "__main__":
    main()

Measured memory_bytes: 3192
use proconio::{fastout, input};

#[fastout]
fn main() {
    input! {
        n: usize, k: u64,
        aa: [u64; n],
    }
    let mut ok = *aa.iter().max().unwrap();
    let mut ng = 0;
    while ng + 1 < ok {
        let x = (ng + ok) / 2;
        let mut s = 0;
        for &a in aa.iter() {
            s += a / x + (if a % x == 0 { 0 } else { 1 }) - 1;
        }
        if s <= k {
            ok = x;
        } else {
            ng = x;
        }
    }
    println!("{}", ok);
}


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

#ifdef LOCAL
#include "../dump.hpp"
#else
#define dump(...)
#endif

#define rep(i,n) for(ll i=0,i##_cond=(n);i<i##_cond;i++)
#define FOR(i,a,b) for(ll i=(a),i##_cond=(b);i<i##_cond;i++)
#define ROF(i,a,b) for(ll i=(a)-1,i##_cond=(b);i>=i##_cond;i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend() //sortで大きい順
#define UNIQUE(v) v.erase(unique(all(v)),v.end())
#define SUM(a) accumulate(all(a),0)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define fst first
#define snd second
#define mp make_pair

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;

const ll inf = 1ll<<62;
const ll mod = 1e9+7;

#define int ll

main(){
  // input
  int n,d,x; cin >> n >> d >> x;
  vvi p(d,vi(n));
  rep(i,d) rep(j,n) cin >> p[i][j];

  rep(i,d-1){ // i日目からi+1日目で増える量を考える
    
    vi inc; // 増えている種類を記録
    rep(j,n) if(p[i+1][j] > p[i][j]) inc.pb(j);

    // 個数制限なしナップザック
    // 容量 : x, 種類数 : inc.size(), j種類目の重さ : p[i][inc[j]], j種類目の価値 : p[i+1][inc[j]] - p[i][inc[j]]
    vvi dp(sz(inc)+1, vi(x+1));
    rep(j, sz(inc)) rep(k, x+1){
      if(k < p[i][inc[j]]) dp[j+1][k] = dp[j][k];
      else dp[j + 1][k] = max(dp[j][k], dp[j + 1][k - p[i][inc[j]]] + (p[i+1][inc[j]] - p[i][inc[j]]));
    }
    x += dp[sz(inc)][x]; // 増加量を足す
    //cout << x << endl;
  }
  cout << x << endl;
}


Measured memory_bytes: 4472
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
using namespace std;

typedef long long ll;
#define modulo 1000000007 // 10^9 + 7
#define MAX 1000000000 // 10^9


int main() {
	int N; cin >> N;
	int x[N], y[N], h[N];
	for (int i = 0; i < N; i++) cin >> x[i] >> y[i] >> h[i];

	// (i,j) : 中心座標
	for (int i = 0; i <= 100; i++) {
		for (int j = 0; j <= 100; j++) {
			int H = 0;
			for (int k = 0; k < N; k++) {
				if (h[k] != 0) H = h[k] + abs(x[k] - i) + abs(y[k] - j);
			}

			bool check = true;
			for (int k = 0; k < N && check == true; k++) {
				check = (max(0, H - abs(x[k] - i) - abs(y[k] - j)) == h[k]);
			}
			if (check) {
				cout << i << " " << j << " " << H << endl;
			}

		}
	}



	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

/* ?????????????´??????????????????? */
void trace(int A[],int N) {
	int i;
	for(i=0;i<N;i++) {
		/* ??£??\??????????´??????????1????????????????????? */
		if(i>0) printf(" ");
		printf("%d",A[i]);
	}
	printf("\n");
}

/* ?????\?????????(0??????????????????) */
void insertionSort(int A[], int N) {
	int i,j,v;
	for(i=1;i<N;i++) {
		v=A[i];
		j=i-1;
		while(j>=0 && A[j] > v) {
			A[j+1] = A[j];
			j--;
		}
		A[j+1]=v;
		trace(A,N);
	}
}

int main(void)
{
	int N, i, j;
	int A[100];
	scanf("%d",&N);
	for(i=0;i<N;i++) scanf("%d",&A[i]);
	
	trace(A,N);
	insertionSort(A,N);
	return 0;
}

Measured memory_bytes: 2708
N,K = STDIN.gets.strip.split.map(&:to_i)
a = STDIN.gets.strip.split.map(&:to_i)

minval=1e20
(0..N-K).each do |i|
    s=a[i]
    e=a[i+K-1]
    if s*e>=0
        t=[s.abs, e.abs].max
    else
        t=[s.abs, e.abs].min*2 + [s.abs, e.abs].max
    end
    minval=t if minval>t
end

puts minval



Measured memory_bytes: 12036
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 999999999
#define rep(i,n) for(int i=0;i<n;i++)
const int MOD = 1000000007;

int main(){
  int a,b; cin >> a >> b;
  int all = 1;
  if(b==1){
     cout << 0 << endl;
     return 0;
  }
  if(a >= b){
     cout << 1 << endl;
     return 0;
  }
  for(int i=1;i<=b;i++){
     all+=a-1;
     if(all >= b ){
        
        cout << i << endl;
        return 0;
     }
  }
  
}



Measured memory_bytes: 256
data = []
output = []
for x in range(0,10000):
    data = input().split()
    if data[1] == '?':
        break
    elif data[1] == '+' :
        output.append(int(data[0]) + int(data[2]))
    elif data[1] == '-' :
        output.append(int(data[0]) - int(data[2]))
    elif data[1] == '*' :
        output.append(int(data[0]) * int(data[2]))
    else:
        output.append(int(data[0]) // int(data[2]))
    data.clear()
for x in range(0,len(output)):
    print(output[x])


Measured memory_bytes: 7700
#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <deque>
#include <set>
#include <numeric>
using namespace std;
using ll = long long;
using ld = long double;

const ll MOD = 998244353;
const ld PI = acos((long double)(-1));

#define no "no"
#define No "No"
#define NO "NO"
#define yes "yes"
#define Yes "Yes"
#define YES "YES"
#define next '\n'
#define sp " "
#define print(x) cout << (x)
#define println(x) cout << (x) << next
#define stop return(0)
#define rep(i, n) for(int (i) = (0); (i) < (n); (++i))
#define FOR(i, start, end) for(int (i) = (start); (i) < (end); (++i))
#define foreach(elem, _list) for(auto& (elem) : (_list))
#define view(_list) foreach(e, _list){ cout << e << sp; } cout << next
#define FAST ios::sync_with_stdio(false); cin.tie(nullptr)
#define size(s) (s).size()
#define ALL(vec) (vec).begin(), (vec).end()
#define pb(e) push_back(e)
#define INF 1e+9
#define EPS 0.00000001

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    bool zero = false;
    rep(i, n){
        cin >> a[i];
        if(a[i] == 0){
            zero = true;
        }
    }

    if(zero){
        println(0);
        return 0;
    }

    ll ans = 1;
    rep(i, n){
        if(a[i] <= 1000000000000000000 / ans){
            ans *= a[i];
        }else{
            println(-1);
            return 0;
        }
    }

    println(ans);
}


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

# define INIT() cin.tie(0); ios::sync_with_stdio(false); cout << fixed << std::setprecision(20)

#define ll long long
const int MOD = 1e9 + 7;


int main() {
    INIT();
    ll a,b  ;
    cin >> a >> b;
    for(ll i = 0; i < 10000; i++) {
        if((ll)(i * .08) == a && (ll)(i * .1) == b) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
}


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

struct segtree {
  int ide;
  function<int(int, int)> f;
  vector<int> node;
  static const int N = 1 << 18;

  segtree(int ide, function<int(int, int)> f) : ide(ide), f(f), node(2 * N, ide){}

  void init(vector<int> &v) {
    for (int i = 0; i < v.size(); ++i) {
      node[i + N - 1] = v[i];
    }
    for (int i = N - 2; i >= 0; --i) {
      node[i] = f(node[2 * i + 1], node[2 * i + 2]);
    }
  }

  int find(int a, int b, int k, int l, int r) {
    if (r <= a || b <= l) return ide;
    if (a <= l && r <= b) return node[k];
    return f(
      find(a, b, 2 * k + 1, l, (l + r) / 2),
      find(a, b, 2 * k + 2, (l + r) / 2, r)
    );
  }

  int find(int a, int b) {
    return find(a, b, 0, 0, N);
  }

  void update(int k, int x) {
    k += N - 1;
    node[k] = x;
    while (k) {
      k = (k - 1) / 2;
      node[k] = f(node[2 * k + 1], node[2 * k + 2]);
    }
  }
};

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

  segtree seg((1ll << 31) - 1, [&](int a, int b) { return (a < b ? a : b); } );
  while (q--) {
    int f, a, b;
    cin >> f >> a >> b;

    if (f) cout << seg.find(a, b + 1) << endl;
    else seg.update(a, b);
  }
}

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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N;
  int64_t K;
  cin >> N >> K;
  vector<int> A(N);
  for (auto&& e : A) {
    cin >> e;
    e--;
  }
  vector table(60, vector(N, 0));
  for (int i = 0; i < N; i++) {
    table[0][i] = A[i];
  }
  for (int k = 0; k < 60 - 1; k++) {
    for (int i = 0; i < N; i++) {
      table[k + 1][i] = table[k][table[k][i]];
    }
  }
  int cur = 0;
  for (int i = 0; K > 0; i++) {
    if (K & 1) cur = table[i][cur];
    K /= 2;
  }
  cout << cur + 1 << '\n';
  return 0;
}


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

int main()
{
    string arr;
    cin >> arr;
    int cnt=0;
int     ans=0;
    for(int i=0;i<3;i++)
    {
        if(arr[i]=='S')
            cnt=0;
        if(arr[i]=='R'&&cnt==0)
        {
            cnt++;
            ans=max(ans, cnt);
            continue;

        }
        if(arr[i]=='R'&&cnt)
        {
            cnt++;
            ans=max(ans, cnt);
            continue;
        }
        ans=max(ans, cnt);

    }
    cout << ans;


    return 0;
}


Measured memory_bytes: 3620
#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)


// Write From This Line
int main()
{
	int n;
	cin >> n;
	ll ans = 0;
	for(int i = 1; i<= n;i++){
		for(int j = 1; j<= n;j++){
			for(int k = 1; k<= n;k++){
				int g1 = __gcd(i,j);
				ans += __gcd(g1,k);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3620
using System;
using System.Collections.Generic;
using System.Linq;
class Program{
	static void Main(){
		int[] s=Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
		int a=Math.Min(s[0]+s[1]+1,s[2]);
		Console.WriteLine("{0}",a+s[1]);
	}
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define pb push_back
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; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

bool ng[1010101];
int cnt[1010101];

void solve() {
    int n;
    cin >> n;
    vector<int> A(n);
    rep(i, n) cin >> A[i];
    rep(i, n) {
        if (cnt[A[i]]) ng[A[i]] = 1;
        cnt[A[i]]++;
        if (ng[A[i]]) continue;
        for(int a = A[i] * 2; a < 1010101; a += A[i]) {
            ng[a] = 1;
        }
    }
    int ans = 0;
    rep(i, n) {
        if (!ng[A[i]]) ans++;
    }
    cout << ans << endl;
    return;
}

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

Measured memory_bytes: 8772
N = int(input())
S = input().strip()

cnt_MAX = 0
for i,s in enumerate(S):
    X = S[:i]
    Y = S[i:]
    cnt = 0
    for x in set(list(X)):
        if x in Y:
            cnt += 1
    if cnt > cnt_MAX:
        cnt_MAX = cnt
print(cnt_MAX)

Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main()
{
	int h,w;
	cin>>h>>w;
	char c;
	int a[h][w];//1=hitam , 0 = putih
	for(int i=0;i<=h-1;i++)
	{
		for(int j=0;j<=w-1;j++)
		{
			cin>>c;
			if(c=='#')
			{
				a[i][j]=1;
			}
			else
			{
				a[i][j]=0;
			}
		}
	}
	bool yes=true;//dianggap bisa.
	for(int i=0;i<=h-1;i++)
	{
		for(int j=0;j<=w-1;j++)
		{
			if(a[i][j]==1)
			{
				int con4=0;
				if(i>0)
				{
					if(a[i-1][j]==1)
						con4++;
				}
				if(j>0)
				{
					if(a[i][j-1]==1)
						con4++;
				}
				if(i<h)
				{
					if(a[i+1][j]==1)
						con4++;
				}
				if(j<w)
				{
					if(a[i][j+1]==1)
						con4++;
				}
				if(con4==0)
				{
					yes=false;//sudah ketahuan tidak bisa
					break;
				}
			}
		}
		if(yes==false)
		{
			break;
		}
	}
	if(yes)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10,maxq=500+10;
int main()
{
    int n,q,S[maxn],T[maxq];
    cin>>n;
    for(int i=0;i<n;i++) cin>>S[i];
    cin>>q;
    for(int i=0;i<q;i++) cin>>T[i];
    int cnt=0;
    for(int i=0;i<q;i++){
        for(int j=0;j<n;j++){
            if(S[j]==T[i]){
                cnt++;
                break;
            }
        }
    }
    cout<<cnt<<"\n";
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

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; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n; cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    vector<vector<ll>> b(32, vector<ll>(n));
    rep(i,n) {
        int idx = 0;
        ll m = a[i];
        while (m>0) {
            b[idx++][i] = m%2;
            m/=2;
        }
    }

    vector<vector<ll>> c(b);
    rep(i,32) {
        for (int j = 1; j < n; ++j) {
            b[i][j] += b[i][j-1];
        }
    }

    ll ans = 0;
    rep(j,n) {
        ll cnt = INF;
        rep(i,32) {
            int see = 2;
            if (c[i][j]) see--; 
            auto itr = lower_bound(b[i].begin()+j, b[i].end(), b[i][j]+see);
            ll tmp = (itr-b[i].begin())-j;
            chmin(cnt, tmp);
        }
        ans += cnt;
    }

    cout << ans << '\n';

    return 0;
}

Measured memory_bytes: 101860
#include <stdio.h>
#include <cstring>
#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
double esp = 1e-8;
int flag;
double r,PI = acos(-1);
int a[maxn];
int dp[maxn];
int main()
{
    int n, b;
    a[0] = 1;
    int l=1,sum = 0, te=6;
    while(te<=100000)
    {
        a[l++] = te;
        te*=6;
    }
    te = 9;
    while(te<=100000)
    {
        a[l++] = te;
        te*=9;
    }
    sort(a, a+l);
    scanf("%d",&n);

    memset(dp,0x3f3f3f3f,(n+3)*sizeof(int));
    dp[0] = 0;
    for(int i=0; i<l; i++)
    {
        for(int j=a[i]; j<=n; j++)
        {
            dp[j] = min(dp[j], dp[j-a[i]]+1);
        }
    }
    cout<<dp[n]<<endl;

    return 0;
}
/***************

****************/


Measured memory_bytes: 640
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1]*n
    
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x,y = y,x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)
      
    def size(self, x):
        return -self.parents[self.find(x)]

N, M = map(int, input().split())
A = list()
B = list()
for j in range(M):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)
ans = [0] * M
ans[M-1] = N*(N-1)//2
uf = UnionFind(N+1)
for i in range(M-1, 0, -1):
  a = A[i]
  b = B[i]
  if uf.same(a,b): 
    ans[i-1] = ans[i]
  else:
    ans[i-1] = ans[i] - uf.size(a)*uf.size(b)
  uf.union(a, b)
    
for i in range(M):
  print(ans[i])

Measured memory_bytes: 104152
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;
    vector<string> v;

    int n = s.size();
    for (int i = 1; i < min(n, 5) + 1; i++) {
        for (int j = 0; j < n - i + 1; j++) {
            v.push_back(s.substr(j, i));
        }
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    cout << v[k - 1] << endl;
    return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
 
#define int long long
#define MOD 1000000007
 
using namespace std;
 
template <class T> ostream &operator<<(ostream &os, vector<T> V) {
    os << "[ ";
    for (auto v : V)
        os << v << " ";
    os << "]";
    return os;
}
template <class T> ostream &operator<<(ostream &os, set<T> S) {
    os << "{ ";
    for (auto s : S)
        os << s << " ";
    return os << "}";
}
template <class L, class R> ostream &operator<<(ostream &os, map<L, R> M) {
    os << "{ ";
    for (auto m : M)
        os << "(" << m.first << ":" << m.second << ") ";
    return os << "}";
}
template <class L, class R> ostream &operator<<(ostream &os, pair<L, R> P) {
    return os << "(" << P.first << "," << P.second << ")";
}

void solve() {
    int a, b, c;
    int k;
    cin >> a >> b >> c;
    cin >> k;
    int count = 0;
    while(b <= a) {
        b *= 2;
        count++;
    }
    while(c <= b) {
        c *= 2;
        count++;
    }
    if(count <= k) {
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}
 
int32_t main() {
    int t;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    // cin >> t;
    // while(t--) {
    //     solve();
    // }
    return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m;
vector<pair<int,int> >a[310];
bool ok[310][310][310];
int dp[310][310][310];
void init() {
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=i; j++) {
			for(int k=0; k<=j; k++) {
				if(i==j&&i) continue;
				if(i==k&&i) continue;
				if(j==k&&j) continue;
				ok[i][j][k]=true;
				for(int h=0; h<a[i].size(); h++) {
					int l=a[i][h].first;
					int cnt=1;
					if(k>=l) cnt++;
					if(j>=l) cnt++;
					if(cnt!=a[i][h].second) {
						ok[i][j][k]=false;
						break;
					}
				}
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		a[y].push_back(make_pair(x,z));
	}
	init();
	int res=0;
	dp[0][0][0]=1;
	for(int i=0; i<=n; i++) {
		for(int j=0; j<=n; j++) {
			for(int k=0; k<=n; k++) {
				int x=i,y=j,z=k;
				if(x<y) swap(x,y);
				if(x<z) swap(x,z);
				if(y<z) swap(y,z);
				if(!ok[x][y][z]) continue;
				if(x==n) res=(res+dp[i][j][k])%mod;
				dp[x+1][j][k]=(dp[x+1][j][k]+dp[i][j][k])%mod;
				dp[i][x+1][k]=(dp[i][x+1][k]+dp[i][j][k])%mod;
				dp[i][j][x+1]=(dp[i][j][x+1]+dp[i][j][k])%mod;
			}
		}
	}
	cout<<res<<endl;
}


Measured memory_bytes: 145664
def solve(Q, H, S, D, N):
    prices =[(int(0.25 * 4), Q),
             (int(0.5 * 4), H),
             (int(1.0 * 4), S),
             (int(2.0 * 4), D)]
    prices.sort(key=lambda x: x[1] / x[0])
    ans = 0
    N *= 4
    for p in prices:
        L = N // p[0]
        ans += L * p[1]
        N -= L * p[0]
    return ans


if __name__ == "__main__":
    Q, H, S, D = tuple(map(int, input().split(" ")))
    N = int(input())
    print(solve(Q, H, S, D, N))


Measured memory_bytes: 3064
//#define NDEBUG
#include <cstddef>
#include <cstdint>
#include <vector>

using i8 = ::std::int_least8_t;
using i32 = ::std::int_least32_t;
using i64 = ::std::int_least64_t;
using u8 = ::std::uint_least8_t;
using u32 = ::std::uint_least32_t;
using u64 = ::std::uint_least64_t;
using isize = ::std::ptrdiff_t;
using usize = ::std::size_t;

class rep {
	const usize f, l;

public:
	class itr {
		friend rep;
		usize i;
		itr(usize x) noexcept : i(x) {}

	public:
		void operator++() noexcept { ++i; }
		usize operator*() const noexcept { return i; }
		bool operator!=(const itr x) const noexcept { return i != x.i; }
	};
	rep(usize first, usize last) noexcept : f(first), l(last) {}
	itr begin() const noexcept { return itr(f); }
	itr end() const noexcept { return itr(l); }
};
class revrep {
	const usize f, l;

public:
	class itr {
		friend revrep;
		usize i;
		itr(usize x) noexcept : i(x) {}

	public:
		void operator++() noexcept { --i; }
		usize operator*() const noexcept { return i; }
		bool operator!=(const itr x) const noexcept { return i != x.i; }
	};
	revrep(usize first, usize last) noexcept : f(first), l(last) {}
	itr begin() const noexcept { return itr(l - 1); }
	itr end() const noexcept { return itr(f - 1); }
};
template <class T> bool maxi(T &a, const T &b) {
	return a <= b ? (a = b, 1) : 0;
}
template <class T> bool mini(T &a, const T &b) {
	return b <= a ? (a = b, 1) : 0;
}
template <class T> bool smaxi(T &a, const T &b) {
	return b <= a ? 0 : (a = b, 1);
}
template <class T> bool smini(T &a, const T &b) {
	return a <= b ? 0 : (a = b, 1);
}
template <class T> using vec_alias = ::std::vector<T>;
template <class T> auto md_vec(usize n, const T &value) {
	return ::std::vector<T>(n, value);
}
template <class... Args> auto md_vec(usize n, Args... args) {
	return ::std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> const T &as_const(const T &v) noexcept { return v; }

#include <algorithm>
#include <iostream>
#include <utility>
#include <array>
#include <string>

int main() {
	::std::string s, t;
	::std::cin >> s >> t;
	::std::array<::std::vector<usize>, 26> cs, ct;
	for (const auto i : rep(0, s.size()))
		cs[s[i] - 'a'].emplace_back(i);
	for (const auto i : rep(0, t.size()))
		ct[t[i] - 'a'].emplace_back(i);
	::std::sort(cs.begin(), cs.end());
	::std::sort(ct.begin(), ct.end());
	for (const auto i : rep(0, 26))
		if (cs[i] != ct[i])
			return ::std::cout << "No" << ::std::endl, 0;
	::std::cout << "Yes" << ::std::endl;
	return 0;
}


Measured memory_bytes: 5108
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
import collections
import copy
import heapq
from collections import defaultdict
from heapq import heappop, heappush
import itertools
input = sys.stdin.readline

##### リストの 二分木検索 #####
# bisect_left(lists, 3)
# bisect_right(lists, 3)

##### プライオリティキュー #####
# heapq.heapify(a) #リストaのheap化
# heapq.heappush(a,x) #heap化されたリストaに要素xを追加
# heapq.heappop(a) #heap化されたリストaから最小値を削除＆その最小値を出力

# heapq.heappush(a, -x) #最大値を取り出す時は、pushする時にマイナスにして入れよう
# heapq.heappop(a) * (-1) #取り出す時は、-1を掛けて取り出すこと

##### タプルリストのソート #####
# sorted(ans) #(a, b) -> 1st : aの昇順, 2nd : bの昇順
# sorted(SP, key=lambda x:(x[0],-x[1])) #(a, b) -> 1st : aの昇順, 2nd : bの降順
# sorted(SP, key=lambda x:(-x[0],x[1])) #(a, b) -> 1st : aの降順, 2nd : bの昇順
# sorted(SP, key=lambda x:(-x[0],-x[1])) #(a, b) -> 1st : aの降順, 2nd : bの降順

# sorted(SP, key=lambda x:(x[1])) #(a, b) -> 1st : bの昇順
# sorted(SP, key=lambda x:(-x[1])) #(a, b) -> 1st : bの降順

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))

def main():
	A,B = inputMap()

	ans = lcm(A,B)
	print(ans)



def gcd(a, b):
	if a > b:
		a, b = b, a

	while a > 0:
		a, b = b % a, a
	return b

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

if __name__ == "__main__":
	main()


Measured memory_bytes: 38516
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <random>
#include <stack>
#include <set>
#include <unordered_set>

#define bug(x) cout<<"zdongdebug1: "<<x<<endl;
#define bug2(x, y) cout<<"zdongdebug2: "<<x<<" "<<y<<endl;
#define bug3(x, y, z) cout<<"zdongdebug3: "<<x<<" "<<y<<" "<<z<<endl;
using namespace std;
typedef long long ll;
const int maxn = 1005;
const int mod = 1000000007;

int main() {
#ifdef suiyuan2009
  freopen("/Users/suiyuan2009/CLionProjects/icpc/input.txt", "r", stdin);
  //freopen("/Users/suiyuan2009/CLionProjects/icpc/output.txt", "w", stdout);
#endif
int n;
  string s;
  cin>>n>>s;
  int cr = 0;
  for(int i=0;i<n;i++)if(s[i]=='R')cr++;
  if(cr==n||cr==0){
    cout<<0<<endl;
    return 0;
  }
  int c = 0;
  for(int i=0;i<cr;i++)if(s[i]=='R')c++;
  cout<<cr-c<<endl;
  return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, maxn = 0, maxcnt = 0, cnt, tempi;
    cin >> n;
    if (n == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    for (int i = 1; i <= n; i++)
    {
        cnt = 0;
        tempi = i;
        while (tempi % 2 == 0)
        {
            tempi /= 2;
            cnt++;
        }
        if (cnt > maxcnt)
        {
            maxn = i;
            maxcnt = cnt;
        }
    }
    cout << maxn << endl;
    return 0;
}

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

#define endl "\n"

typedef long long ll;
typedef pair <ll, ll> pii;
typedef long double ld;

const ll DIM = 3007;
const ll INF = 1000000007;
ll n, m, k;
ll used[DIM][DIM];
// LCL NOT DONE

string s,s1;
int main()
{
   // ios_base::sync_with_stdio(0);
   // cin.tie(0);
   // cout.tie(0);
    cin >> s >> s1;
    for(ll i=1; i<=s.size(); i++)
        for(ll j=1; j<=s1.size(); j++)
        {
            if(s[i-1]==s1[j-1])
                used[i][j]=used[i-1][j-1]+1;
            else
            {
                used[i][j]=max(used[i][j-1],used[i-1][j]);
            }
        }
    ll a=s.size(),b=s1.size();
    string ha="";

    while(a!=0||b!=0)
    {
        if(a==0||b==0)break;
        if(s[a-1]==s1[b-1])
        {
            a--;
            b--;
            ha+=s[a];
        }
        else if(used[a-1][b]==used[a][b])
            a--;
        else
            b--;
    }
    for(ll i=ha.size()-1; i>=0; i--)
        cout<<ha[i];
}


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

int main(){
  int n;
  int num[200][3],pt[200] = {},game[101];
  cin >> n;
  for(int i = 0;i < n;i++){
    for(int j = 0;j < 3;j++) cin >> num[i][j];
  }
  for(int i = 0;i < 3;i++){
    for(int j = 0;j < 101;j++) game[j] = -1;
    for(int j = 0;j < n;j++){
      if(game[num[j][i]] == -1) game[num[j][i]] = j;
      else game[num[j][i]] = -2;
    }
    for(int j = 0;j < 101;j++){
      if(game[j] >= 0) pt[game[j]] += j;
    }
  }
  for(int i = 0;i < n;i++) cout << pt[i] << endl;
  return 0;
}

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

#define mem(f, v) memset(f,v,sizeof(f))
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);

typedef long long ll;
const int maxn = 100010;
const int inf = ~(1u << 31u);
const ll linf = ~(1llu << 63u);

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    string str;
    cin >> str;
    str = str;
    int n = str.length(), res = n;
    for (int i = 1; i < n; i++) {
        if (str[i - 1] != str[i])
            res = min(res, max(i, n - i));
    }
    cout << max((n + 1) / 2, res) << endl;
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<char> vchar;
typedef vector<vector<char>> vvchar;
typedef vector<int> vint;
typedef vector<vector<int>> vvint;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
typedef priority_queue<long long> prque;
#define ain(i,n,a) for(long long i=0;i<(long long)(n);i++){cin>>a[i];}
#define aout(i,n,a) for(long long i=0;i<(long long)(n);i++){if(i){cout<<" ";}cout<<a[i];if(i==n-1){cout<<endl;}}
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define vsort(v) sort((v).begin(),(v).end())
#define vrsort(v) sort((v).rbegin(),(v).rend())
#define vreverse(v) reverse((v).begin(),(v).end())
#define pf(a) push_front(a)
#define pb(a) push_back(a)
#define INF 1998021900
#define MOD 1000000007
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //input
  ll a,b;vll d(3);cin>>a>>b;
  d[0]=a*b;d[1]=a+b;d[2]=a-b;
  vsort(d);cout<<d[2]<<endl;
  //caricurate
  //output
}

Measured memory_bytes: 256
//
// Created by cerussite on 6/14/20.
//
#include <iostream>
#include <vector>

int main() {
  int x, n;
  std::cin >> x >> n;

  std::vector<bool> p(101, false);
  for (int i = 0; i < n; ++i) {
    int pp;
    std::cin >> pp;
    p[pp] = true;
  }

  int p_size = static_cast<int>(p.size());
  for (int i = 0; true; ++i) {
    const auto min = x - i;
    const auto max = x + i;

    if (min <= 0 || !p[min]) {
      std::cout << min << std::endl;
      break;
    }

    if (p_size <= max || !p[max]) {
      std::cout << max << std::endl;
      break;
    }
  }
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
constexpr int IINF = INT_MAX;

int main() {
    int w, h, cnt[3][55]{}, ans = IINF;
    cin >> h >> w;
    for(int i=0;i<h;i++){
        string s;
        cin >> s;
        for(int j=0;j<w;j++){
            if(s[j]!='W')cnt[0][i+1]++;
            if(s[j]!='B')cnt[1][i+1]++;
            if(s[j]!='R')cnt[2][i+1]++;
        }
        for(int j=0;j<3;j++)cnt[j][i+1] += cnt[j][i];

    }
    for(int i=1;i<h;i++){
        for(int j=i+1;j<h;j++){
            ans = min(ans, cnt[0][i]+cnt[1][j]-cnt[1][i]+cnt[2][h]-cnt[2][j]);
        }
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define ll long long
#define MAXN 200010
using namespace std;
#define MAXN 200010
int N, K, C;
string S;
pair<int, int> l[MAXN];
pair<int, int> r[MAXN];

int main()
{
	cin>>N>>K>>C;
	cin>>S;
	l[0] = make_pair(0, 300000);
	int rest = 300000;
	int work = 0;
	for(int i = 0; i < N - 1; ++i)
	{
		if(S[i] == 'o' && rest >= C)
		{
				work++;
				rest = 0;
		}
		else
		{
				rest++;
		}
		l[i+1] = make_pair(work, rest);
	}
	rest = 300000;
	work = 0;
	r[N-1] = make_pair(work, rest);
	for(int i = N - 1; i > 0; --i)
	{
			if(S[i] == 'o' && rest >= C)
			{
				work++;
				rest = 0;
			}
			else
			{
				rest++;
			}
			r[i-1] = make_pair(work, rest);
	} 
	for(int i = 0; i < N; ++i)
	{
			if(S[i] == 'x')
				continue;
			int w = l[i].first + r[i].first;
			int re = l[i].second + r[i].second;
			if(w < K)
			{
				cout<<i+1<<endl;
			}
	}
}


Measured memory_bytes: 4996
#include <stdio.h>

int main(void) {
  char input[6];
  int n, m;
  fgets(input, 5, stdin);
  sscanf(input, "%d", &n);
  while(n > 1000)n = n-1000;
  m = 1000 - n;
  printf("%d", m);
  return 0;
}

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

// @@ !! LIM()

int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  string S; cin >> S;
  if (S.at(2) == S.at(3) && S.at(4) == S.at(5)) {
    cout << "Yes\n";
  }else {
    cout << "No\n";
  }

  return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,o,n) for(long long i = o;i<n;i++)
#define oneforall ios::sync_with_stdio(false);cin.tie(0);
#define all(v) (v).begin(),(v).end()
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define int long long 
const long long INF=1e18;
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << "\n";} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
typedef vector<int> vi;
typedef vector<long long> vl;
typedef long long ll;
typedef vector<pair<long, long > > vpll;
typedef vector<pair<int, int > > vpii;
#define FORR(x,arr) for(auto& x:arr)

/*
bool isprime(int x){
	for(int i = 2;i*i<=x;i++){
		if(x%i == 0)return false;
	}
	return x!=1;
}
int gcd(int a, int b) 
{ 
    if (a == 0) 
       return b; 
    if (b == 0) 
       return a; 
   
    if (a == b) 
        return a; 
   
    if (a > b) 
        return gcd(a-b, b); 
    return gcd(a, b-a); 
} 
void dfs(int x,int y){
		if(x == n+1){
			int tmp = 0;
			FOR(i,0,k){
				if(tmp1[mortyy[i]]-tmp1[morty[i]] == mortyyy[i])tmp+=mortyyyy[i];
			}
			rick = max(rick,tmp);
			return ;
		}
		int i;
		for(i = y;i<=n1;i++){
			tmp1[x] = i;
			dfs(x+1,i);
		}
	}
*/


//3111111111111111111111111111111


	void solve(){

		ini(n);
		vi morty;
		FOR(i,0,n){ini(x);morty.push_back(x);}
		vi morty1 = morty;
		sort(all(morty1));
		FOR(i,0,n){
			if(morty[i]<=morty1[n/2-1])out(morty1[n/2]);
			else out(morty1[n/2-1]);
		}













	}









































int32_t main() {
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall
	oneforall 
	oneforall

	solve();
	


	return 0;
}

Measured memory_bytes: 5488
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int main() {
    int a, b;
    char op;
    cin >> a >> op >> b;
    if (op == '+') {
        cout << a+b << endl;
    } else {
        cout << a-b << endl;
    }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
using lint=long long;
using ld=long double;
template<class T>using numr=std::numeric_limits<T>;
int main(){
    std::cin.tie(nullptr);std::ios_base::sync_with_stdio(false);
    std::cout.setf(std::ios_base::fixed);std::cout.precision(15);
    lint n;std::cin>>n;
    std::vector<std::tuple<std::string,lint,lint>>a(n);
    for(int i=0;i<n;i++){
        std::string s;lint p;std::cin>>s>>p;
        a.at(i)=std::make_tuple(s,-p,i+1);
    }
    std::sort(ALL(a));
    for(auto&&t:a){
        std::cout<<std::get<2>(t)<<'\n';
    }
}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<set>
#include<map>
#include<queue>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);++i)
#define rrep(i,n) for(int (i)=(n)-1;(i)>=0;--i)
#define rep1(i,n) for(int (i)=1;(i)<=(n);++i)
#define rrep1(i,n) for(int (i)=(n);(i)>=1;--i)
#define pb push_back
#define fr first
#define sc second
typedef long long ll;
typedef pair<int,int> P;
typedef pair<long long,long long> LP;
typedef double db;
using namespace std;

ll N;
string s;
int e[300000];
int w[300000];

int main()
{
  cin>>N;
  cin>>s;
  if(s[0]=='W') w[0]=1;
  rep1(i,N-1){
    w[i]+=w[i-1];
    if(s[i]=='W') w[i]++;
  }
  if(s[N-1]=='E') e[N-1]=1;
  rrep(i,N-1){
    e[i]+=e[i+1];
    if(s[i]=='E') e[i]++;
  }
  int ans=min(w[N-1],e[0]);
  rep1(i,N-2){
    ans=min(ans,w[i-1]+e[i+1]);
  }
  cout<<ans<<endl;
}


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

int main(){
 ll x;
  cin >> x;
  
  ll a = 100;
  int y = 0;
  while(a<x){
    a *= 1.01;
    y++;}
  
  cout << y << endl;
  
  return 0;
}

Measured memory_bytes: 3608
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define MAX 200

int top,stack[MAX];

void push(int n){
  stack[++top] = n;
}

int pop(){
  return stack[top--];
}

int main(){
  int i,x,y;
  char s[100];

  while(scanf("%s", s) != EOF){
    if(s[0] == 'b') break;
    if ( s[0] == '+' ){
      x = pop();
      y = pop();
      push(y + x);
    } else if ( s[0] == '-' ){
      x = pop();
      y = pop();
      push(y - x);
    } else if ( s[0] == '*' ){
      x = pop();
      y = pop();
      push(y * x);
    } else {
      x = atoi(s);
      push(x);
    }

  }

  printf("%d\n",pop());
  
  return 0;
}



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

int main()
{
    int N, Y;
    cin >> N >> Y;
    int ansa = -1, ansb = -1, ansc = -1;
    for (int a = 0; a <= N; a++){
        for (int b = 0; b <= N; b++){
            int c = N - (a + b);
            if (c < 0) {
                break;
            }
            if (10000 * a + 5000 * b + 1000 * c == Y){
                ansa = a;
                ansb = b;
                ansc = c;
            }
        }
    }
    cout << ansa << ' ' << ansb << ' ' << ansc << endl;
    return 0;
}

Measured memory_bytes: 384
#include <stdio.h>

int main(){
	double r;
	double area, line;
	scanf("%lf", &r);
	area = 3.141592653589 * r * r;
	line = 2 * 3.141592653589 * r; 
	
	printf("%f %f", area, line);
	return 0;
}


Measured memory_bytes: 2716
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ

		Scanner sc = new Scanner(System.in);

		//入力表示
		int N = sc.nextInt();
		double ans = 0;

		for (int i = 0; i < N; i++) {
			double x = sc.nextDouble();
			String u = sc.next();

			if (u.equals("JPY")) {
				ans += x;
			}
			if (u.equals("BTC")) {
				ans += x * 380000.0;

			}
		}

		System.out.println(ans);
	}
}

Measured memory_bytes: 22996
#include<iostream>
using namespace std;
int m[1000];
int main()
{
  int n,x,sum=0,count=0,men=100000;
  cin >> n >> x;
  for(int a=0;a<n;a++)
  {
    cin >> m[a];
    sum+=m[a];
    if(m[a]<men)
      men = m[a];
  }
  x-=sum;
  count+=n;
  while(1)
  {
    if(x-men>=0)
    {
      x-=men;
      count++;
    }
    else
      break;
  }
  cout << count;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int a = 0, b = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '0') a++;
        else b++;
    }
    cout << min(a, b) * 2;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define two(a) (1<<(a))
#define LINF (1ll<<61)
#define EPS (1e-14)
#define Lshift(a,b) ((a)<<(b))
#define Rshift(a,b) ((a)>>(b))
#define rep(a,b) for(a=0 ; a<b ; a++)
#define xrep(a,b,c) for(a=b ; a<c ; a++)
#define INF (1<<29)
#define sz(a) int(a.size())
#define swap(a,b) ( (a^=b) , (b^=a) , (a^=b) )
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5]|=1<<(x&31))
#define maxL (10000000>>5)+1
#define mod 1000000007
#define vi vector<int>
#define pii pair<int, int>
#define mii map<int, int>
#define si set<int>
#define pb push_back
typedef long long ll;
using namespace std;


int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll n, m;
    cin >> n >> m;
    vector<ll> in(m);
    int i;
    rep(i, m) cin >> in[i];
    sort(in.begin(), in.end());
    ll ans(0), sum(0);
    rep(i, m) {
        ans += in[i];
    }
    if (ans > n) cout << -1 << endl;
    else 
    cout << n - ans << endl;
}


Measured memory_bytes: 3692
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7

harmonic=[pow(i,mod-2,mod) for i in range(N+1)]
for i in range(1,N+1):
    harmonic[i]+=harmonic[i-1]

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

for i in range(N):
    ans*=(i+1)
    ans%=mod
print(ans)

Measured memory_bytes: 63384
#include <iostream>

using namespace std;

long long dp[3007][3007];
int tab[3007];

int main()
{
    int N;
    cin >> N;
    for(int i=1; i<=N; i++)
    {
        cin >> dp[i][i];
        tab[i]=dp[i][i];
    }
    cout << "\n";
    for(int i=1; i<=N; i++)
        for(int j=i-1; j>0; j--)
            dp[j][i]=max(tab[j]-dp[j+1][i], tab[i]-dp[j][i-1]);
    /*
    for(int i=1; i<=N; i++)
    {
        for(int j=1; j<=N; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }
    */
    cout << dp[1][N];
}

Measured memory_bytes: 70144
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const double PI = 4*atan(1);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-9;
const string YES = "Possible";
const string NO = "Impossible";
#define pb push_back
#define mp make_pair

int N;

void solve()
{
	ll ans = 0;
	for(int i=1;i<=N;++i){
		if(i%3==0 && i%5==0) continue;
		else if(i%3==0) continue;
		else if(i%5==0)continue;
		else ans += i;
	}
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> N;
	solve();
	return 0;
}

Measured memory_bytes: 3652
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n, m = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(n + m - 1)]

T = [[] for i in range(n+1)]
RT = [set() for i in range(n+1)]

for a, b in A:
    T[a].append(b)
    RT[b].add(a)

D = [0] * (n+1)
P = [0] * (n+1)
used = [0] * (n+1)

def dfs(p, i, depth):
    if used[i]:
        return None
    D[i] = depth
    P[i] = p
    used[i] = True
    for t in tuple(T[i]):
        RT[t].remove(i)
    for t in tuple(T[i]):
        if not RT[t]:
            dfs(i, t, depth+1)

def root(i):
    if not RT[i]:
        return i
    return root(tuple(RT[i])[0])

dfs(0, root(1), 1)
for p in P[1:]:
    print(p)

Measured memory_bytes: 316036