akhauriyash/Code-Regression huggingface dataset:
from random import randint


class RollingHash:
    def __init__(self, s):
        self.base = [7073, 7577, 5445, 2742, 6972, 7547, 2267, 286, 6396, 7147,
                     3307, 188, 266, 8253, 2818, 9527, 5110, 1207, 4633, 6196,
                     309, 2646, 7533, 85, 9870, 4730, 6862, 9213, 7456, 7098,
                     6805, 674, 5821, 4864, 8061, 1826, 2219, 459, 5937, 5667,
                     9033, 5552, 7263, 2402, 9809, 3701, 7048, 2874, 8350, 6006,
                     973, 3317, 2522, 5546, 1669, 1545, 7972, 4979, 9905, 173,
                     6812, 7715, 5006, 6068, 6340, 4989, 5510, 6380, 1200, 6739,
                     5527, 4000, 6519, 3448, 2933, 6048, 3133, 1667, 9086, 8368,
                     4914, 7142, 2770, 7752, 391, 7052, 5476, 3105, 8322, 3501,
                     7454, 3167, 8730, 9002, 4564, 138, 2197, 7238, 3411, 7433][randint(0, 100)]
        self.mod = 4611686018427387903
        self.size = len(s)
        self.string = s

        self.hash = self.make_hashtable(s)
        self.pow = self.make_powtable()

    def make_hashtable(self, _s):
        hashtable = [0] * (self.size + 1)
        for i in range(self.size):
            hashtable[i + 1] = (hashtable[i] * self.base + ord(_s[i])) % self.mod
        return hashtable

    def make_powtable(self):
        power = [1] * (self.size + 1)
        for i in range(self.size):
            power[i + 1] = (self.base * power[i]) % self.mod
        return power

    def get_hash(self, left, right):
        """get hash of s[left:right]"""
        return (self.hash[right] - self.hash[left] * self.pow[right - left]) % self.mod

    def contain(self, a):
        """return a in s"""
        m = len(a)
        if m > self.size:
            return False
        hashs = self.get_hash(0, m)
        hasha = 0
        for i in range(m):
            hasha = (hasha * self.base + ord(a[i])) % self.mod
        for i in range(self.size - m + 1):
            if hasha == hashs:
                return True
            hashs = self.get_hash(i, m + i)
        return hasha == hashs


from collections import defaultdict
# d = defaultdict(int)で0で初期化
# d = defaultdict(lambda: 100)で100で初期化
n, s = int(input()), input()
rh = RollingHash(s)


def check(m):
    d = defaultdict(lambda: 10000000)
    for i in range(n - m + 1):
        h = rh.get_hash(i, i + m)
        d[h] = min(d[h], i)
        # m以上離れていて2回目
        if i - d[h] >= m:
            return True
    return False


l, r = 0, n // 2 + 1
while l + 1 < r:
    mid = (l + r) // 2
    if check(mid):
        l = mid
    else:
        r = mid
print(l)


Measured memory_bytes: 10848
n = input()
num_list = input().split()
num_list = [int(num) for num in num_list]

count = 0

while all([num % 2 == 0 for num in num_list]):
    for i in range(len(num_list)):
        num_list[i] = num_list[i]/2
    count += 1

print(count)


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define mp make_pair
#define INF (int)1e9
#define cBits(x) __builtin_popcount(x)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) a/gcd(a,b)*b
#define FOR(i,a,b) for (int i=a;i<b;i++)
#define FORr(i,a,b) for (int i=a;i>=b;i--)
#define MAX3(a,b,c) max(a,max(b,c))
#define MIN3(a,b,c) min(a,min(b,c))
#define eachTest int t; cin >> t; while(t--) solve();

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef pair<ll,ll> PLL;
typedef pair<int,int> PII;

const int MOD=1000000007;

void solve() {
	;
}

int main() {

	fastio;
	// #ifndef ONLINE_JUDGE
	// 	freopen("input.txt", "r", stdin);
	// 	freopen("output.txt", "w", stdout);
	// #endif

	// eachTest

	ll n;
	cin >> n;
	vector <ll> arr(n);
	map <ll, ll> same;
	FOR(i,0,n) {
		cin >> arr[i];
		same[arr[i]]++;
	}
	ll temp;
	ll total = 0;
	for (auto v:same) {
		temp = v.second;
		total += temp*(temp-1)/2;
	}
	FOR(i,0,n) {
		cout << total - same[arr[i]] + 1 << "\n";
	}

	return 0;
}


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

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

	long long L[86];
	L[0] = 2;
	L[1] = 1;
	for (int i=2;i <= n;i++) {
		L[i] = L[i - 1] + L[i - 2];
	}
	cout << L[n] << endl;
}


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

int main() {
  int N;
  cin >> N;
  int x = 0, y = 1;
  for (int i = 0; i < 9; i++) {
    x = x + N / y % 10;
    y = y * 10;
  }
  if (N % x == 0) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
}


Measured memory_bytes: 3624
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cctype>
using namespace std;

inline char gc() {
//	static char buf[100000],*p1,*p2;
//	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin)),p1==p2)?EOF:*p1++;
	return getchar();
}

template<class T>
int read(T &ans) {
	ans=0;T f=1;
	char ch=gc();
	while(!isdigit(ch)) {if(ch=='-') f=-1; if(ch==EOF) return EOF; ch=gc();}
	while(isdigit(ch)) ans=ans*10+ch-'0',ch=gc();
	ans*=f;
	return 1;
}

typedef long long ll;

int main() {
//	freopen("test.in","r",stdin);
	ll n,p,ans=1;
	read(n);read(p);
	for(ll i=2;i*i<=p;i++) {
		ll temp=0;
		while(p%i==0) p/=i,temp++;
		temp/=n;
		while(temp--) ans*=i;
	}
	if(n==1) ans*=p;
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 128
a,v=map(int, input().split())
b,w=map(int, input().split())
t=int(input())
sa=abs(a-b)
kyori=t*(v-w)
if sa==0:
    ans='YES'
else:
    if kyori>=sa:
        ans='YES'
    else:
        ans='NO'
print(ans)

Measured memory_bytes: 9208
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

ans = 0
for i in range(N):
    ans += min(A[i], B[i])
    ans += min(A[i+1], B[i] - min(A[i], B[i]))
    A[i+1] -= min(B[i] - min(A[i], B[i]), A[i+1])

print(ans)


Measured memory_bytes: 18624
#include<stdio.h>
int main(){
	int n,i,j,key,d[104],c,L,R,C;
	for(;scanf("%d",&n)&&n;){
		for(i=0;i<n;i++)scanf("%d",&d[i]);
		L=0;R=n-1;c=0;
		scanf("%d",&key);
		for(;L<=R;){
			c++;
			C=(R+L)/2;
			if(d[C]==key)break;
			if(d[C]<key)L=C+1;
			else R=C-1;
		}
		printf("%d\n",c);
	}
	return 0;
}

Measured memory_bytes: 0
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(long, "next", long, "cost");
alias PQueue(T, alias less = "a>b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, m, R;
    scan(n, m, R);
    auto r = aryread.sort.array();
    auto route = new Pair[][](n, 0);
    foreach (_; iota(m))
    {
        long a, b, c;
        scan(a, b, c);
        route[a - 1] ~= Pair(b - 1, c);
        route[b - 1] ~= Pair(a - 1, c);
    }

    auto mincost = new long[][](n, n);
    foreach (i; iota(n))
    {
        mincost[i][] = INF;
        mincost[i][i] = 0;
    }

    foreach (i; iota(n))
    {
        foreach (e; route[i])
        {
            mincost[i][e.next] = e.cost;
        }
    }

    foreach (k; iota(n))
    {
        foreach (i; iota(n))
        {
            foreach (j; iota(n))
            {
                if (mincost[i][j] > mincost[i][k] + mincost[k][j])
                    mincost[i][j] = mincost[i][k] + mincost[k][j];
            }
        }
    }

    long ans = INF;
    while (r.nextPermutation())
    {
        long tmp;
        foreach (i; iota(R - 1))
        {
            tmp += mincost[r[i] - 1][r[i + 1] - 1];
        }
        ans = min(ans, tmp);
    }
    ans.writeln();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


Measured memory_bytes: 4428
import java.util.*;
import java.io.*;
 
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;
 
public class Main{
    static final long mod=1000000007;
    
    public  static void main(String[] args)   throws Exception, IOException{
        Reader sc = new Reader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        // int n=sc.nextInt();
        // char c[][] = new char[h][w];
        // char c[]=sc.nextString().toCharArray();
        // int d[]=new int[n];
        // for(int i=0; i<n; i++) {d[i]=sc.nextInt();}

        // int n=sc.nextInt();
        char c[]=sc.nextString().toCharArray();
        char d[]=sc.nextString().toCharArray();
        int s[]=new int[200];
        int t[]=new int[200];
        String ans="Yes";
        for(int i=0; i<c.length; i++) {
            if(s[d[i]]>0 && s[d[i]]!=c[i]){ans="No";break;}
            s[d[i]]=c[i];
            if(t[c[i]]>0 && t[c[i]]!=d[i]){ans="No";break;}
            t[c[i]]=d[i];
        }
        
        out.println(ans);
        out.flush();
    }


    static void db(Object... os){
        System.err.println(Arrays.deepToString(os));
    }  

    static long gcd(long a, long b){
        if(min(a,b) == 0)return max(a,b);
        return gcd(max(a,b) % min(a,b),min(a,b));
    }
}

class P implements Comparable<P>{
    int id, d;
    P(int  id, int d) {
        this.id=id;
        this.d=d;
    }
    public int compareTo(P p){
        return d-p.d; //des
    }
}

class Reader
{ 
    private BufferedReader x;
    private StringTokenizer st;
    
    public Reader(InputStream in)
    {
        x = new BufferedReader(new InputStreamReader(in));
        st = null;
    }
    public String nextString() throws IOException
    {
        while( st==null || !st.hasMoreTokens() )
            st = new StringTokenizer(x.readLine());
        return st.nextToken();
    }
    public int nextInt() throws IOException
    {
        return Integer.parseInt(nextString());
    }
    public long nextLong() throws IOException
    {
        return Long.parseLong(nextString());
    }
    public double nextDouble() throws IOException
    {
        return Double.parseDouble(nextString());
    }
}


Measured memory_bytes: 29032
#include <stdio.h>
#include <iostream>

using namespace std;

int main() {
	int N;
	int *ri, *li;
	int gest_sum = 0;
	
	ri = new int;
	li = new int;

	//Nとli,riの入力
	//cout << "input N" << endl;
	cin >> N;

	ri[N] = {};
	li[N] = {};

	for (int i = 0; i < N; i++) {
		//cout << "i=" << i << endl;
		//cout << "input li" << endl;
		cin >> li[i];
		//cout << "input ri" << endl;
		cin >> ri[i];
                gest_sum += (ri[i] - li[i])+1;
	}
	cout << gest_sum << endl;
	return 0;
}

Measured memory_bytes: 256
n, k = gets.chomp.split.map(&:to_i)
ws = Array.new

n.times do
    ws << gets.chomp.to_i
end

row  = ws.max
high = ws.sum

def mlc(row, high, ws, k)
    mid = (row + high) / 2

    if high - row <= 1 then
        if loadable?(k, ws, row) then
            row
        else
            high
        end
    else
        if loadable?(k, ws, mid) then
            mlc(row, mid, ws, k)
        else
            mlc(mid, high, ws, k)
        end
    end
end

def loadable?(k, ws, p)
    track = 1
    loaded = 0

    ws.each do |w|
        if loaded + w > p then
            track += 1
            loaded = w
        else
            loaded += w
        end
    end
    track <= k
end

p mlc(row, high, ws, k)


Measured memory_bytes: 8916
#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[i];
  }
  int count =0;
  for(int i=1;i<N-1;i++){
    if(a[i]>a[i-1]&&a[i+1]>a[i]) count++;
    else if(a[i]<a[i-1]&&a[i+1]<a[i]) count++;
  }
  cout<<count<<endl;


}


Measured memory_bytes: 256
package main

import "fmt"

var n int
var ps, qs []int
var used []bool
var count int
var a, b int

func main() {
	fmt.Scan(&n)
	ps = make([]int, n)
	qs = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&ps[i])
	}
	for i := 0; i < n; i++ {
		fmt.Scan(&qs[i])
	}
	used = make([]bool, n+1)
	for i := 1; i <= n; i++ {
		used[i] = true
		dfs([]int{i})
		used[i] = false
	}

	fmt.Println(abs(a - b))
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

func dfs(vs []int) {
	if len(vs) == n {
		count++
		check(vs)
		return
	}
	for i := 1; i <= n; i++ {
		if !used[i] {
			used[i] = true
			dfs(append(vs, i))
			used[i] = false
		}
	}
}

func check(vs []int) {
	flag := true
	for i := 0; i < len(vs); i++ {
		if ps[i] != vs[i] {
			flag = false
			break
		}
	}
	if flag {
		a = count
	}
	flag = true
	for i := 0; i < len(vs); i++ {
		if qs[i] != vs[i] {
			flag = false
			break
		}
	}
	if flag {
		b = count
	}
}


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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

ll rec(int cur, const int n, const int m, vector<int> &a, const vector<vector<int>> &req) {
    if (cur == n+1) {
        ll res = 0;
        for (auto v : req) {
            if (a.at(v.at(1)) - a.at(v.at(0)) == v.at(2)) res += v.at(3);
        }
        return res;
    } else {
        ll res = -1;
        int s = 1;
        if (cur > 1) s = a.at(cur-1);
        for (int i=s; i<=m; ++i) {
            a.at(cur) = i;
            chmax(res, rec(cur+1, n, m, a, req));
        }
        return res;
    }
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> req(q, vector<int>(4));
    for (int i=0; i<q; ++i) cin >> req.at(i).at(0) >> req.at(i).at(1) >> req.at(i).at(2) >> req.at(i).at(3);
    vector<int> a(n+1);
    cout << rec(1, n, m, a, req) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 3648
n,*a=map(int,open(0).read().split())
a.sort()
s=[0]*n
s[0]=a[0]
for i in range(1,n):
  s[i]=s[i-1]+a[i]
ans=1
for i in range(1,n)[::-1]:
  if s[i-1]>=(a[i]+1)//2:
    ans+=1
  else:
    break
print(ans)

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

ll INF = 1e18;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N; cin >> N;
  ll ans = 1;
  vector<ll> A(N, 0);
  bool flag = false;
  REP(i, N){
    cin >> A[i];
    if(A[i] == 0) flag = true;
  }
  if(flag){
    cout << 0 << endl;
    return 0;
  }

  REP(i, N){
    ll tmp = ans;
    ans *= A[i];
    if(ans > INF || ans < tmp){
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_poizcy.hpp>
typedef long long  ll;
#define pb                push_back
#define mp                make_pair
#define all(a)            (a).begin(), (a).end()
#define mem(a,h)          memset(a, (h), sizeof(a))
#define se second
#define fi first
#define por(a,b) (((a%MOD) * (b%MOD))%MOD)
#define forg(i, b, e, c)    for (ll i = (ll)b; i < (ll)e; i+=c)
#define forr(i, b, e)    for (ll i = b; i < e; i++)
 
 
using namespace std;
//using namespace __gnu_pbds;
typedef double lldb;
typedef pair<ll, ll>  ii;
typedef pair<ll, ii>  iii;
typedef pair<double, double>  iidb;
//typedef tree<ii,null_type,less<ii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const ll INF = 1e9+7;
const double PI = acos(-1);
#define initseg ll new_nodo=(pnodo*2),mid=(iz+der)/2;
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define offset 3000
#define ptr nodo*
const ll MOD=998288383;

using namespace std;
const ll inf=1e15;
const ll cmplog=19;
const ll tam = 20010;

ll S, T;
ll n, m;
ll dist[tam], q[tam], work[tam];

struct Edge {
	ll to, rev;
	ll f, cap;
};

vector<Edge> G[tam];

void addEdge(ll s, ll t, ll cap)
{
	
	Edge a = {t, (ll)G[t].size(), 0, cap};
	Edge b = {s, (ll)G[s].size(), 0, 0};
	G[s].pb(a);
	G[t].pb(b);
}

bool dinic_BFS(){
	fill(dist, dist + n + 2, -1);
	dist[S] = 0;
	ll qt = 0;
	q[qt++] = S;
	for (ll qh = 0; qh < qt; qh++)
	{
		ll u = q[qh];
		for (ll j = 0; j < G[u].size(); j++)
		{
			Edge &e = G[u][j];
			ll v = e.to;
			if (dist[v] < 0 && e.f < e.cap)
			{
				dist[v] = dist[u] + 1;
				q[qt++] = v;
			}
		}
	}
	return dist[T] >= 0;
}

ll dinic_DFS(ll u, ll f)
{
	if (u == T || f == 0) return f;
	for (ll &i = work[u]; i < G[u].size(); i++)
	{
		Edge &e = G[u][i];
		if (e.cap <= e.f) continue;
		ll v = e.to;
		if (dist[v] == dist[u] + 1)
		{
			ll df = dinic_DFS(v, min(f, e.cap - e.f));
			if (df > 0)
			{
				e.f += df;
				G[v][e.rev].f -= df;
				return df;
			}
		}
	}
	return 0;
}

ll maxFlow()
{
	ll flow = 0;
	while ( dinic_BFS() )
	{
		fill(work, work + n + 2, 0);
		while (true)
		{
			ll df = dinic_DFS(S, INF);
			if (df == 0) break;
			flow += df;
		}
	}

	return flow;
}
ll v[tam];
int main()
{	
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	set<ll> s;
	forr(j,0,n)
	{
		cin>>v[j];
	}

	S=0;
	T=n+20;
	ll total=0;
	forr(i,0,n)
	{
		if (v[i]>0)
		{
			total+=v[i];
			addEdge(S,i+1,v[i]);
		}
		else
		{
			addEdge(i+1,T,-v[i]);
		}
		forr(j,0,n)
		{
			if (i!=j && (i+1)%(j+1)==0)
				addEdge(i+1,j+1,inf);
		}
	}
	n+=22;
	total-=maxFlow();
	cout<<total<<endl;
	
}

Measured memory_bytes: 4140
#include<stdio.h>
int main()
{
    long long int a,b,c;
    char op;

    scanf("%lld %c %lld",&a,&op,&b);
    if(op=='+')
    {
        c=a+b;
    }
    else if(op=='-')
    {
        c=a-b;
    }
    printf("%lld",c);
    return 0;
}


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

int a[100000];

int main() {
    int n;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        int k;
        cin >> k;
        a[k]++;
    }
    vector<int> v;
    for(int i = 0; i < 100000 - 2; i++) {
        v.push_back(a[i] + a[i+1] + a[i+2]);
    }
    sort(v.begin(), v.end());
    cout << v.back() << endl;
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >> d;

  bool ans = (abs(a - c) <= d) || ( (abs(a - b) <= d) && (abs(b - c) <= d) );
  cout << (ans ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size()){cout << a[i];cout << (i == a.size() - 1 ? "\n":" ");}
#define rep(i,x) for(ll i = 0;i<x;i++)
#define REP(i,x) for(ll i = 1;i<=x;i++)
#define mp make_pair
#define debug(x) cerr << #x << ": " << x << "\n"
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const dou pi = 3.14159265358;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
template<class T, class U> inline bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; }
template<class T, class U> inline bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; }
template<class T, class U> inline bool change(T& a,U& b){if(a > b){swap(a,b);return 1;}return 0;}
//0の場合のアレンジに注意
template<class T>
T gcd(T a,T b){
    if(a == 0)return b;
    else if(b == 0)return a;
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a / gcd(a,b) * b;
}

//素数判定O(sqrt(N))
template<class T>
inline bool isp(T n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
vector<ll> fac(cmax),finv(cmax),inv(cmax);

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if(fac[0] == 0)COMinit();
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logm)
ll modpow(ll n,ll m,ll MOD){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}
ll mypow(ll n,ll m){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n);
        m >>= 1;
        n *= n;
    }
    return res;
}

template<class T = ll>
T in(){T x;cin >> x;return x;}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll A = in(),B = in(),C = in();
    if(A == B)cout << C << "\n";
    else if(A == C)cout << B << "\n";
    else cout << A << "\n";
}

Measured memory_bytes: 26560
#include <bits/stdc++.h>
#if 1
#define int long long
#define MAX LLONG_MAX
#define MIN LLONG_MIN
#define stoi stoll
#else
#define MAX INT_MAX
#define MIN INT_MIN
#endif
#define INF MAX/2
#define ALL(obj) (obj).begin(), (obj).end()
#define fi first
#define se second
const int NIL = -1;
const int MOD = 1000000007;
#define REP(i,n) for (int (i)=0; (i) < (n); ++(i))
#define FOR(i,a,b) for (int (i)=(a); (i) < (b); ++(i))
using namespace std;

int pow(int x, int n) {int res=1; while(n){if(n&1)res*=x;x*=x;n>>=1;} return res;}
int get_gcd(int a, int b) {while(1){if (a < b) swap(a, b); if (b == 0) return a; a %= b;}}
int get_lcm(int a, int b) {return a * b / get_gcd(a, b);}
bool chmin(int &a, int b) {if(a>b){a=b; return true;} else return false;}
bool chmax(int &a, int b) {if(a<b){a=b; return true;} else return false;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

//-------------------------テンプレここまで-------------------------//

signed main () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int N,W;
  cin >> N >> W;
  static pair<int,int> a[1000];
  REP(i,N) cin >> a[i].fi >> a[i].se;

  // dp[n][w] ... n番目の種類の品物で、w以下の制限の元で
  // 最大化されたときの価値の合計値 (1-based indexing)
  static int dp[101][10001];
  for (int n=1; n<=N; n++) {
    for (int w=0; w<=W; w++) {
      // n番目を選ぶ場合
      if(w-a[n-1].se >= 0) chmax(dp[n][w], dp[n][w-a[n-1].se] + a[n-1].fi);

      // n番目を選ばない場合
      if(n>0) chmax(dp[n][w], dp[n-1][w]);
    }
  }

  cout << dp[N][W] << endl;

  return 0;
}



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

template<typename T, typename U> void cmax(T &a, U b) { if (a < b) a = b; }
template<typename T, typename U> void cmin(T &a, U b) { if (a > b) a = b; }

signed main() {
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);

  int N;
  cin >> N;

  cout << ((N == 0) ? 1 : 0) << "\n";
}

Measured memory_bytes: 3648
# Problem C - One Quadrillion and One Dalmatians

# input
N = int(input())

# initialization
alphabet = "zabcdefghijklmnopqrstuvwxy"
ans = ""

# check
if N>=1 and N<=26:
    ans = alphabet[N%26]
else:
    while N>0:
        if N%26==0:
            ans += alphabet[0]
            N = N // 26 -1
        else:
            ans += alphabet[N%26]
            N = N // 26

# output
ans = ans[::-1]
print(ans)


Measured memory_bytes: 9176
N, M, Q = map(int, input().split())

X = [[0 for j in range(510)] for i in range(510)]
C = [[0 for j in range(510)] for i in range(510)]

LR = []
for i in range(M):
    L, R = map(int, input().split())
    X[L][R] += 1

for i in range(1, N+1):
    for j in range(1, N+1):
        C[i][j] = C[i][j-1]+X[i][j]


for i in range(Q):
    p, q = map(int, input().split())
    sum = 0
    for j in range(p, q+1):
        sum += C[j][q]-C[j][p-1]
    print(sum)


Measured memory_bytes: 56612
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <math.h> // sqrt
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <iomanip> // setprecision
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<long long>;
using pii = pair<int, int>;
using psi = pair<string, int>;

ll gcd (ll a, ll b) {
    ll x = min(a, b);
    ll y = max(a, b);
    if (y % x == 0) {
        return x;
    }
    else {
        return gcd(y % x, x);
    }
}

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

int main() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    ll ans = B - A + 1;
    ans -= (B / C) - (A / C);
    if (A % C == 0) {
        ans--;
    }
    ans -= (B / D) - (A / D);
    if (A % D == 0) {
        ans--;
    }
    ll E = lcm(C, D);
    ans += (B / E) - (A / E);
    if (A % E == 0) {
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
//
#include <vector>
#include <set>
#include <map>
#include <array>
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <numeric>
#include <bitset>
#include <iomanip>
//
using ll = long long;
using namespace std;
#define rep(i,n) for(ll i=0;i<(n);++i)
#define outD(fpv) cout << setprecision(20) << fpv << endl;
inline void yes(bool cond) { cond ? puts("Yes") : puts("No"); }
inline void YES(bool cond) { cond ? puts("YES") : puts("NO"); }
template<typename Type> inline void chmin(Type& a, Type b) { if (a > b) a = b; }
template<typename Type> inline void chmax(Type& a, Type b) { if (a < b) a = b; }
template<typename Arr, typename Type> inline void fill(Arr& arr, Type v) { std::fill(arr.begin(), arr.end(), v); }
template<typename Type> inline void sort(Type& arr) { std::sort(arr.begin(), arr.end()); }
template<typename Type> inline void reverse(Type& arr) { reverse(arr.begin(), arr.end()); }
template<typename Type> inline Type nth(vector<Type>& arr, size_t pos) { std::nth_element(arr.begin(), arr.begin() + pos, arr.end()); return arr[pos]; }
template<typename Type> inline void unique(Type& arr) { sort(arr); arr.erase(unique(arr.begin(), arr.end()), arr.end()); }
constexpr ll INF_I = std::numeric_limits<ll>::max();
constexpr ll BIGP = 1000000007L;
constexpr double INF_F = std::numeric_limits<float>::infinity();
constexpr double PI = 3.14159265358979323846L;
using P = pair<ll, ll>;
//
int main()
{
    cin.tie(0); ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    string name;
    while (N != 0)
    {
        N -= 1;
        char ch = (N % 26) + 'a';
        name.push_back(ch);
        N /= 26;
    }
    reverse(name);
    cout << name;

    return 0;
}

Measured memory_bytes: 3100
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;

string s;

int main()
{
    ios_base::sync_with_stdio(0);

    cin >> s;
    int N = s.length();

    int ans = 1, cloc = 1;
    while (cloc < N)
    {
        if (s[cloc] == s[cloc-1])
        {
            if (cloc == N - 1)
                break;
            cloc += 2;
            ans++;
            if (cloc < N)
            {
                cloc++;
                ans++;
            }
        }
        else
        {
            cloc++;
            ans++;
        }
    }
    cout << ans << "\n";
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


vector<LL> b(1<<17),l(1<<17),u(1<<17);
LL n,x;

bool f(LL m){
    LL e = m%x;
    LL k = m/x;
    vector<P> a;
    for (int i = 0; i < n; i++) {
        a.pb(mp((x-b[i])*u[i]+l[i]*b[i],i));
    }
    sort(RALL(a));
    LL sum = 0;
    for (int i = 0; i < k; i++) {
        sum += (x-b[a[i].sc])*u[a[i].sc];
    }
    for (int i = k; i < n; i++) {
        sum -= b[a[i].sc]*l[a[i].sc];
    }
    if(e==0) return sum>=0;
    for (int i = 0; i < n; i++) {
        int nx = a[i].sc;
        if(i<k){
            sum-=(x-b[nx])*u[nx];
            sum+=(x-b[a[k].sc])*u[a[k].sc]+l[a[k].sc]*b[a[k].sc];
            if(e>=b[nx]){
                sum+=(e-b[nx])*u[nx];
                if(sum>=0) return true;
                sum-=(e-b[nx])*u[nx];
            }
            else{
                sum+=(e-b[nx])*l[nx];
                if(sum>=0) return true;
                sum-=(e-b[nx])*l[nx];
            }
            sum+=(x-b[nx])*u[nx];
            sum-=(x-b[a[k].sc])*u[a[k].sc]+l[a[k].sc]*b[a[k].sc];
        }
        else{
            sum+=l[nx]*b[nx];
            if(e>=b[nx]){
                sum+=(e-b[nx])*u[nx];
                if(sum>=0) return true;
                sum-=(e-b[nx])*u[nx];
            }
            else{
                sum+=(e-b[nx])*l[nx];
                if(sum>=0) return true;
                sum-=(e-b[nx])*l[nx];
            }
            sum-=l[nx]*b[nx];
        }
    }
    return false;
}


int main(){
    cin >> n >> x;
    LL sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> b[i] >> l[i] >> u[i];
        sum+=b[i];
    }
    LL ll=-1,rr=sum;
    while(abs(rr-ll)>1){
        LL mm = ll+(rr-ll)/2;
        if(f(mm)) rr = mm;
        else ll = mm;
    }
    cout << rr << endl;
    return 0;
}


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

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

typedef struct node * Node;

#define NIL NULL

Node root = NIL;
Node treeMinimum(Node);
Node treeMaximum(Node);
Node treeSearch(Node , int);
Node treeSuccessor(Node);
void treeDelete(Node);
void insert(int);
void inorder(Node);
void preorder(Node);

int count1 = 1,count2 = 1,ak;

int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);
ak = n;

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
    if ( com[0] == 'f' ){
      scanf("%d", &x);
      Node t = treeSearch(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    } else if ( com[0] == 'd' ){
      scanf("%d", &x);
      treeDelete(treeSearch(root, x));
    }
  }

  return 0;
}

Node treeMinimum(Node x){

  while(x->left != NIL) x = x->left;
  return x;
}

Node treeMaximum(Node x){

  while(x->left != NIL ) x = x->right;
  return x;
}

Node treeSearch(Node x , int k){

  while( x!= NIL){
    if(k < x->key) x = x->left;
    else x = x->right;
  }
  return x;
}

Node treeSuccessor(Node x){
  Node y;
  if(x->right != NIL) return treeMinimum(x->right);

  y = x->parent;
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}


void treeDelete(Node z){
  Node y;
  Node x;

  if(y->left == NIL || z->right == NIL) y = z;
  else y = treeSuccessor(z);

  if(y->left != NIL) x = y->left;
  else x = y->right;

  if(x != NIL) x->parent = y->parent;

  if(y->parent == NIL) root = x;
  else if(y == y->parent->left) y->parent->left = x;
  else y->parent->right = x;

  if(y != z) z->key =y->key;

}

void insert(int k){
  Node y  = NIL;
  Node x = root ; //current
  Node z; //temp

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

if(root == NIL) root = z;
else {
  x = root;
  y = NIL;
}
  while(x != NIL){
    y = x;
    if(z->key < x->key){
      x = x->left;
      if(x == NIL){
       y->left = z;
       return;
     }
   }else{
x = x->right;

    if(x == NIL) {
      y->right = z;
return;
}
  }
}
}

void inorder(Node u){

  if(u != NIL){

    inorder(u->left);

    printf(" %d",u->key);

    inorder(u->right);
  }

}

void preorder(Node u){

  if(u != NIL){
        printf(" %d",u->key);
    preorder(u->left);
    preorder(u->right);
  }
}



Measured memory_bytes: 25144
N,K=map(int,input().split())
D=[]
N=[False for i in range(N)]
for i in range(K):
    a=input()
    A=list(map(int,input().split()))
    for i in range(len(A)):
        N[A[i]-1]=True
ans=0
for i in N:
    if not i:
        ans+=1
print(ans)

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

vector<int> A;
int N;
int calc(int x){
	int ret=0;
	for(int i=0;i<N;i++) ret+=(A[i]-x)*(A[i]-x);
	return ret;
}

int main(void){
	int ans=999999999;
	scanf("%d",&N);
	A.resize(N);
	for(int i=0;i<N;i++) scanf("%d",&A[i]);
	for(int i=-100;i<=100;i++) ans=min(ans,calc(i));
	printf("%d\n",ans);
}

Measured memory_bytes: 256
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
typedef pair<int,int> P;
int main(void)
{
	int n,i,j,nn;
	long long sum,k;
	P pp[100000];
	scanf("%d %lld",&n,&k);
	for(i=0;i<n;i++)	{
		scanf("%d %d",&pp[i].first,&pp[i].second);
	}
	sort(pp,pp+n);
	sum=0;
	for(i=0;i<n;i++)	{
		sum+=pp[i].second;
		if(sum>=k)	{
			nn=pp[i].first;
			break;
		}
	}
	printf("%d\n",nn);
	return 0;
}

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

#ifdef LOCAL
#define debug(var) cerr << (#var) << " = " << (var) << endl;
#else
#define debug(var)
#endif

void init() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
}

const int mod = 1e9+7;
const int N = 2e3+23;

int a[N];

void solve() {
  long long n, k; scanf("%lld%lld", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a+i);
  }
  long long ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j) continue;
      if (a[j] >= a[i]) continue;
      if (j > i) {
	ans = (ans + k*(k+1)/2) % mod;
      } else {
	ans = (ans + (k-1)*k/2) % mod;
      }
    }
  }
  printf("%lld", ans);
}

int main() {
  init();
  int t = 1; //scanf("%d", &t);
  while (t--) {
    solve();
  }
  return 0;
}


Measured memory_bytes: 3792
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    final int n = scanner.nextInt();
    Map<String, Integer> s = new TreeMap<>();

    for (int i = 0; i < n; i++) {
      String tmp = scanner.next();
      if(!s.containsKey(tmp)) {
        s.put(tmp,1);
      } else {
        s.put(tmp, s.get(tmp) + 1);
      }
    }
    int max = s.values().stream().mapToInt(e -> e).max().getAsInt();
    s.entrySet().stream().filter(e->e.getValue() == max).forEach(e -> System.out.println(e.getKey()));
  }
}


Measured memory_bytes: 88536
#include <iostream>
#include <cmath>
#include<algorithm>
using namespace std;
int a[200005];
long long int s[200005],r[200005],m[200005],sum=0;
int main()
{
	int n;
	r[0]=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	    {
		scanf("%d",&a[i]);
	    sum=sum+a[i];
	    s[i]=s[i-1]+a[i];
	    }
	for(int j=1;j<n;j++)
	{
		r[j]=sum-s[j];
		m[j]=abs(s[j]-r[j]);
	}
	sort(m,m+n);
	printf("%d\n",m[1]);
}

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

int main(){
  int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k; cin>>k;
  
  cout<<a[k-1];
  
  return 0;
}

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

typedef long long ll;
using namespace std;

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

	int m,f,b; cin >> m >> f >> b;
	if(m+f < b) cout << "NA" << endl;
	else cout << max(0,b-m) << endl;

	return 0;

}




Measured memory_bytes: 3232
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=(a);i<(b);++i)

template<class T> inline void chmin(T& a, T b) {if (a > b) a = b;}
template<class T> inline void chmax(T& a, T b) {if (a < b) a = b;}

//vector出力
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){
  o<<"{";
  for(int i=0;i<(int)v.size();i++) o << (i>0?", ":"") << v[i];
  o<<"}";
  return o;
}

//約数列挙
vector<ll> divisor(ll n) {
  vector<ll> ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

ll const mod =1e9+7;
int main() {
  int X;
  cin >> X;
  rep2(i,1,1000000) {
    if (i*(i+1)/2>=X){
      cout << i << endl;
      return 0;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <algorithm>
#include <ctime>
#include <vector>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;

#define PI 3.14159265358979323846264338327950L

int res=0;

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

    int N,K;
    cin >> N>>K;
    vector<int> payment(N);
    for(int i = 0; i < N; i++ )
    {
        cin >> payment[i];
    }
    sort(payment.begin(), payment.end());
    for(int i = 0; i < K; i++ )
    {
        res += payment[i];
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=200050;
vector<int> E[N];
set<int> st[N];
void Del(int u, int p, int mx, int id)
{
	if(u>mx) return;
	if(st[id].count(u)) st[id].erase(u);
	else return;
	for(int i=0;i<E[u].size();i++)
	{
		int v=E[u][i];
		if(v!=p)
		{
			if(v<=mx) Del(v,u,mx,id);
			else break;
		}
	}
}
int dep[N],par[N],anc[N];
void DFS(int u, int p)
{
	dep[u]=dep[p]+1;
	par[u]=p;
	anc[u]=max(anc[p],p);
	for(int v:E[u]) if(v!=p) DFS(v,u);
}
int add[N],sub[N];
void SolvePlus(int u, int p)
{
	for(int v:E[u]) if(v!=p)
	{
		SolvePlus(v,u);
		if(st[u].size()<st[v].size()) st[u].swap(st[v]);
		for(int x:st[v]) st[u].insert(x);
	}
	vector<int> del;
	for(auto it=st[u].end();it!=st[u].begin();)
	{
		it--;
		if(*it>anc[u]) del.pb(*it);
		else break;
	}
	for(int x:del) Del(x,par[x],x,u);
	add[u]=st[u].size();
	st[u].insert(u);
}
void SolveMinus(int u, int p)
{
	for(int v:E[u]) if(v!=p)
	{
		SolveMinus(v,u);
		if(st[u].size()<st[v].size()) st[u].swap(st[v]);
		for(int x:st[v]) st[u].insert(x);
	}
	vector<int> del;
	st[u].insert(u);
	for(auto it=st[u].end();it!=st[u].begin();)
	{
		it--;
		if(*it>anc[par[u]]) del.pb(*it);
		else break;
	}
	for(int x:del) Del(x,par[x],x,u);
	sub[u]=st[u].size();
}
int ans[N];
void Solve(int u, int p)
{
	ans[u]=ans[p]+add[u]-sub[u];
	for(int v:E[u]) if(v!=p) Solve(v,u);
}
int main()
{
	int n,i,u,v;
	scanf("%i",&n);
	for(i=1;i<n;i++) scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	for(i=1;i<=n;i++) sort(E[i].begin(),E[i].end());
	DFS(1,0);
	SolvePlus(1,0);
	for(i=1;i<=n;i++) st[i].clear();
	SolveMinus(1,0);
	Solve(1,0);
	for(i=2;i<=n;i++) printf("%i ",ans[i]+dep[i]-1);
	return 0;
}

Measured memory_bytes: 67968
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 3e5 + 10; 
const double pi = acos(-1.0);

inline ll read()
{
    ll kk=0,f=1;
    char cc=getchar();
    while(cc<'0'||cc>'9'){if(cc=='-')f=-1;cc=getchar();}
    while(cc>='0'&&cc<='9'){kk=(kk<<1)+(kk<<3)+cc-'0';cc=getchar();}
    return kk*f;
}

/*
struct apple
{
	int n;//a0,b1,c2
	int dv;//deliciousness 
}ap[maxn];
*/
int p[maxn],q[maxn],r[maxn];
bool cmp(int a,int b);
int main(void)
{
	int x,y,a,b,c;
	x =read();
	y =read();
	a =read();
	b =read();
	c =read();
	
	int cnt=0,sum=a+b+c;
	for(int i=0;i<a;i++){
		p[i]=read();
	//	ap[cnt].n=0;
	//	ap[cnt++].dv=read();
	}
	sort(p,p+a,cmp);
	for(int i=0;i<b;i++){
		q[i]=read();
	//	ap[cnt].n=1;
	//	ap[cnt++].dv=read();
	}
	sort(q,q+b,cmp);
	for(int i=0;i<c;i++){
		r[i]=read();
	//	ap[cnt].n=2;
	//	ap[cnt++].dv=read();
	}
	for(int i=0;i<x;i++)r[c+i]=p[i];
	for(int i=0;i<y;i++)r[c+x+i]=q[i];
	sort(r,r+c+x+y,cmp);
//	sort(ap,ap+sum,cmp);
	
	sum=x+y;
	cnt=0;
	ll ans= 0;
	for(int i=0;i<sum;i++)
	{
		ans+=r[i];
	}
/*	while(sum)//(x>0||y>0) )//&&cnt<sum)
	{
		if(ap[cnt].n==0)
		{
			if(x>0)
			{
				ans+=ap[cnt].dv;
			//	printf("\nx:%d",ans);
				x--;
				sum--;
			}
		}
		else if(ap[cnt].n==1)
		{
			if(y>0)
			{
				ans+=ap[cnt].dv;
			//	printf("\ny:%d",ans);
				y--;
				sum--;
			}
		}
		else
		{
				ans+=ap[cnt].dv;
			//	if(ap[cnt])
			//	printf("\nc:%d",ans);
				sum--;
		}	
		cnt++;
	}
*/
	printf("%lld",ans);
	return 0;
}
bool cmp(int a,int b)//(apple a,apple b)
{
	return a>b;//a.dv>b.dv;
}

Measured memory_bytes: 2176
L=10**5+3
MOD=10**9+7
fac=[1]*(L+1)
for i in range(1,L+1):
  fac[i]=fac[i-1]*i%MOD
inv_fac=[1]*(L+1)
inv_fac[L]=pow(fac[L],MOD-2,MOD)
for i in range(L-1,0,-1):
  inv_fac[i]=inv_fac[i+1]*(i+1)%MOD

def cmb(n,r):
  if n<0 or r<0 or r>n:
    return 0
  return fac[n]*inv_fac[r]%MOD*inv_fac[n-r]%MOD

N=int(input())
A=list(map(int,input().split()))

used=[0]*N
for i in range(N+1):
  a=A[i]
  if used[a-1]==0:
    used[a-1]=[1,i]
  else:
    x=a
    y=used[a-1][1]
    z=i
    break

print(N)
for i in range(2,N+2):
  ans=cmb(N+1,i)-cmb(N-z+y,i-1)
  print(ans%MOD)

Measured memory_bytes: 32528
#define DEBUG 0

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

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

int b[100000],l[100000],r[100000];
LLI diff[100000];
plli best[100000];
int yes[100000];
int main() {
    int i;
    int N,X;
    scanf("%d %d",&N,&X);
    for (i = 0; i < N; i++) scanf("%d %d %d",&b[i],&l[i],&r[i]);

    LLI s = 0,e = (LLI) N*X;
    while (s < e) {
        LLI m = (s+e) / 2;

        int c = m / X,z = m % X;
        LLI sum = 0;
        for (i = 0; i < N; i++) {
            sum -= (LLI) l[i]*b[i];
            diff[i] = (LLI) r[i]*(X-b[i])+(LLI) l[i]*b[i];
            best[i] = mp(diff[i],i),yes[i] = 0;
        }
        sort(best,best+N,greater<plli>());
        LLI sum2 = 0;
        for (i = 0; i < c; i++) sum2 += best[i].first,yes[best[i].second] = 1;
        for (i = 0; i < N; i++) {
            LLI x = max((LLI) l[i]*(z-b[i]),(LLI) r[i]*(z-b[i]))+sum;
            x += (LLI) l[i]*b[i];
            if (yes[i]) x += sum2-diff[i]+best[c].first;
            else x += sum2;
            if (x >= 0) break;
        }
        if (i < N) e = m;
        else s = m+1;
    }
    printf("%lld\n",s);

    return 0;
}



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

using namespace std;

int main(){
  string s;
  int o=0,z=0;
  
  cin >> s;
  for(int i=0;i<s.length();i++){
    if(s[i]=='0')
      z++;
    else
      o++;
  }
  cout << 2*min(o,z);

  return 0;
}

Measured memory_bytes: 512
#include<stdio.h>
int main()
{
    int A1,A2,A3;
    scanf("%d %d %d",&A1,&A2,&A3);
    A2=A1+A2+A3;
    if(A2>=22){
        printf("bust");
    }
    else if(A2<22){
        printf("win");
    }
    return 0;
}


Measured memory_bytes: 128
#include "iostream"
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <cstring>
#include <math.h>
#include <cctype>
#include <stack>
#include <vector>
#include <list>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
using namespace std;
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};


int main(int argc, char const *argv[]) {
  string t; std::cin >> t;
  int n=t.size(),c0=0,c1=0;
  for(int i=0; i<n; i++){
    if(t[i]=='0') c0++;
    else c1++;
  }

  std::cout << min(c0,c1)*2 << '\n';
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<vector>
#include<array>
#include<string>
#include<stack>
#include<queue>
#include<algorithm>
#include<cassert>
#include<functional>
#include<random>
#include<complex>
#include<bitset>
#include<chrono>
#include<boost/multiprecision/cpp_int.hpp>
#define int int64_t
#define uint uint64_t
#define REP(i, a, b) for (int64_t i = (int64_t)(a); i < (int64_t)(b); i++)
#define rep(i, a) REP(i, 0, a)
#define EACH(i, a) for (auto i: a)
#define ITR(x, a) for (auto x = a.begin(); x != a.end(); x++)
#define ALL(a) (a.begin()), (a.end())
#define HAS(a, x) (a.find(x) != a.end())
#define Min(x) *min_element(ALL(x))
#define Max(x) *max_element(ALL(x))
#define Unique(L) (L.erase(unique(ALL(L)), L.end()))
#define veccat(v1, v2) std::copy((v2).begin(),(v2).end(),std::back_inserter(v1)/*v1の後ろにv2を入れる*/)
#define intmax (std::numeric_limits<int64_t>::max() / 4)
using namespace std;
typedef boost::multiprecision::cpp_int bigint;
const double EPS = 1e-9;
const double PI = acos(-1.0);


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

	int N, K;
	cin >> N >> K;
	double answer = 0.0;

	for (int i = 1; i <= N; ++i) {
		double prob = 1.0;
		for (int j = i; j < K; j *= 2)prob *= 0.5;
		answer += prob / double(N);
	}
	cout << setprecision(20) << answer << endl;


	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
 
int main(){
  int n, x, i, j, k, c = 0;
  while(scanf("%d%d", &n, &x)){
    if(n == 0 && x == 0) break;
    for(i = 1;i < n - 1;i++)
      for(j = i + 1;j < n;j++)
        for(k = j + 1;k < n + 1;k++)
          if((i + j + k) == x) c++;
    printf("%d\n", c);
    c = 0;
  }
  return 0;
}


Measured memory_bytes: 2088
#include <iostream>

using namespace std;
int main(int argc, char const *argv[]) {
  int n, a, b, answer;
  cin >> n;
  cin >> a;
  cin >> b;

  if (n*a >= b) {
    answer = b;
  } else {
    answer = n*a;
  }

  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int TH,TS,AH,AS;
  cin>>TH>>TS>>AH>>AS;
  bool flag=true;
  while(!(TH<=0 || AH<=0))
  {
    if(flag)
    {
      AH-=TS;
      flag=!flag;
    }
    else{
      flag=!flag;
      TH-=AS;
    }
  }
  if(TH<=0) cout<<"No";
  else cout<<"Yes";
  
}

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

using namespace std;
typedef long long ll;

int main() {
	string value;
	cin >> value;
	if (value[2] == value[3] && value[4] == value[5]) {
		cout << "Yes";
	}
	else {
		cout << "No";
	}
	return 0;
}

Measured memory_bytes: 256