akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int e;

int xy(int ee){
	if(ee==0){
		return 0;
	}
	int min=ee;
	int x,y;
	for(y=0;y*y<=ee;y++){
		x=ee-y*y;
		if(min>x+y){
			min=x+y;
		}
	}
	return min;
}

void solve(){
	int x,y,z;
	for(z=0;z*z*z<=e;z++);
	int min=e;
	for(z--;z>=0;z--){
		if(min>(z+xy(e-z*z*z))){
			min=z+xy(e-z*z*z);
		}
	}
	printf("%d\n",min);
}

int main(void){
	while(scanf("%d",&e),e){
		solve();
	}
	return 0;
}

Measured memory_bytes: 600
#include<stdio.h>
#include<string.h>
int main(){
    
    char a[11];
    char b[11];
    char c[11];
    
    scanf("%s",a);
    scanf("%s",b);
    scanf("%s",c);
    
    int len1 = strlen(a);
    int len2 = strlen(b);
    int len3 = strlen(c);
    
    if(a[len1-1] == b[0]  &&  b[len2-1] == c[0]){
        printf("YES");
    }
    else{
        printf("NO");
    }
    
    return 0;
}

Measured memory_bytes: 3164
# 2020/08/10
# AtCoder Beginner Contest 086 - B

# Input
a, b = input().split()
ab = int(a + b)

# Calc
if ab ** (1/2) - int(ab ** (1/2)) == 0:
    ans = 'Yes'
else:
    ans = 'No'

# Output
print(ans)


Measured memory_bytes: 9324
package main

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

func nextInt(scanner *bufio.Scanner) int {
	scanner.Scan()
	num, _ := strconv.Atoi(scanner.Text())
	return num
}

func scanIntArray() []int {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)
	result := []int{}
	for i := 0; i < n; i++ {
		result = append(result, nextInt(sc))
	}

	return result
}

var pre []int
var in []int

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n := nextInt(sc)

	for i := 0; i < n; i++ {
		pre = append(pre, nextInt(sc))
	}

	for i := 0; i < n; i++ {
		in = append(in, nextInt(sc))
	}

	idx = 0

	// fmt.Println(n)
	// fmt.Println(pre)
	// fmt.Println(in)

	rec(0, n)

	for i, v := range result {
		if i != 0 {
			fmt.Print(" ")
		}
		fmt.Print(v)
	}
	fmt.Println()
}

var result []int

func rec(l int, r int) {
	if l >= r {
		return
	}

	c := next(pre)
	m := find(in, c)
	rec(l, m)
	rec(m+1, r)
	result = append(result, c)
}

var idx int

func next(pre []int) int {
	result := pre[idx]
	idx++
	return result
}

func find(in []int, c int) int {
	for i, v := range in {
		if c == v {
			return i
		}
	}
	return -1
}



Measured memory_bytes: 1092
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using namespace std;

typedef tree<int, null_type, less<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;

#define f first
#define se second
#define pb push_back
#define mp make_pair
#define vi vector<int>
#define pi pair<int, int>
#define all(x) x.begin(), x.end()
#define lp(i, n) for (int i = 0; i < n; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define X real()
#define Y imag()
#define angle(a) (atan2(a.Y, a.X))
#define vec(a, b) ((b) - (a))
//#define length(a) (hypot(a.Y , a.X))
#define normalize(a) (a) / length(a)
#define dotP(a, b) ((conj(a) * b).X)
#define crossP(a, b) ((conj(a) * b).Y)
#define same(p1, p2) (dotP(vec(p1, p2), vec(p1, p2)) < EPS)
#define lengthSqr(a) dotP(a, a)
#define rotate0(p, ang) ((p)*exp(point(0, ang)))
#define rotateA(p, ang, about) (rotate0(vec(about, p), ang) + about)
#define reflect0(v, m) conj(v / m) * m
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
const double PI = acos(-1.0);
const double EPS = (1e-10);
const long long int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
typedef long long int ll;
typedef unsigned long long ull;
typedef complex<double> point;
long long fastpow(ll n, ll x) {
  if (!x)
    return 1;
  if (x % 2)
    return n * fastpow(n, x - 1);
  ll p = fastpow(n, x / 2);
  p %= mod;
  p *= p;
  p %= mod;
  return p;
}

ll my_mod(ll num, ll mod) {
  ll ret = num % mod;
  while (ret < 0)
    ret += mod;
  return ret;
}

ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
long double dist(pair<ll, ll> &a, pair<ll, ll> &b) {
  return sqrt(
      ((a.f - b.f) * (a.f - b.f) * 1.0 + (a.se - b.se) * (a.se - b.se)));
}
/*vector<int> ap;
bool np[MX];
void s(){
    mem(np , 1);
    np[1] = np[0] = 0;
    for(ll i = 2 ; i*i<= MX ;i++){
        if(np[i]){
            for(ll j= i*i ; j <MX; j+=i) np[j] = 0;
        }
    }
    for(ll i = 2 ; i< MX ; i++) if(np[i]) ap.pb(i);
}*/
const ll MX = 1e5+5;

int main()
{
    IO;
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
    for(int i = 0 ; i < n ; i++) cin>>a[i];
    vector<bool> dp(k+1);
    for(int left = 0 ; left <= k ; left++){
		for(int take : a){
			if(take <= left && !dp[left-take]){
				dp[left] = 1;
			}
		}
	}
	cout<<(dp[k]?"First":"Second");
    
    return 0;
}



Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read() {
	int x=0;char c=getchar();
	while (c<'0'||c>'9') c=getchar();
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x;
}
int main() {
	int n=read(),m=read();
	int tot=0;
	for (register int i=1;i<=m;++i) {
		int x=read();
		tot+=x; 
	}
	int ret=n-tot;
	printf("%d\n",ret>=0?ret:-1);
}

Measured memory_bytes: 3760
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

//string lines = q"[
//abcdeffg]";

void main()
{
  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
    
  int N = array[0].split(" ")[0].to!int;
  int W = array[0].split(" ")[1].to!int;
    
  long[] Wi = new long[](N+1);
  long[] Vi = new long[](N+1);
  Wi[0] = 0L;
  Vi[0] = 0L;

  for (int i=1; i<array.length; i++) {
    string s = array[i];
    Wi[i] = s.split(" ")[0].to!int;
    Vi[i] = s.split(" ")[1].to!int;
  }
  
  long[][] dp = new long[][](N+1,W+1);
  for (int i = 1; i < N+1; i++) {
    for (int j = 1; j < W+1; j++) {
      if (j < Wi[i]) {
        dp[i][j] = dp[i-1][j];
      } else {
        dp[i][j] = max(dp[i-1][j], dp[i-1][j-Wi[i]] + Vi[i]);
      }
    }
  }
  writeln(dp.reduce!(max).reduce!(max));
}

Measured memory_bytes: 81660
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n,k,s,ans,term,ans_t;
vector<int> a_n;
int m,t;

int main()
{

  while(1){
    m = 0;
    ans_t =	0;

    cin>>n>>k;

    if(n == 0 && k == 0){
      break;
    }

    for(int q = 0;q < n;++q){
      cin>>term;
      a_n.push_back(term);
    }

    for(int q =	0;q < n;++q){
      if(q < k){
        ans_t += a_n[q];
        ans = ans_t;
      }
      else{
        m = ans_t	+ a_n[q] - a_n[q-k];
        if(m > ans){
          ans = m;
	}
        ans_t = m;
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}

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

#define rep(i, n) for(long long i=0;i<(long long)(n);i++)
#define rep2(i, s, n) for(long long i=(s);i<(long long)(n);i++)
#define repi(i, n) for(int i=0;i<(int)(n);i++)
#define rep2i(i, s, n) for(int i=(s);i<(int)(n);i++)
#define all(v) v.begin(), v.end()

#define deg2rad(deg) (((deg)/360)*2*M_PI)
#define rad2deg(rad) (((rad)/2/M_PI)*360)

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

const ll INF = (1LL<<60);
const int INFi = (1<<29);

/*素数判定*/
bool is_prime(ll n){
    if(n==1) return false;
    for(ll i=2;i*i<=n;i++){
        if(n%i==0) return false;
    }
    return true;
}

/*約数列挙*/
vll enum_divisors(ll n){
    vll l;
    for(ll i=1;i*i<=n;i++){
        if(n%i==0){
            l.push_back(i);
            if(n/i != i) l.push_back(n/i);
        }
    }
   sort(all(l));
   return l;
}

/*素因数分解*/
vector<P> prime_factorize(ll n){
    vector<P> l;
    for(ll i=2;i*i<=n;i++){
        if(n%i!=0) continue;
        ll e = 0;
        while(n%i==0){
            e++;
            n /= i;
        }
        l.push_back({i, e});
    }
    if(n!=1) l.push_back({n, 1});
    return l;
}

/*最小公倍数*/
ll lcm(ll a, ll b){
    return a*b/__gcd(a,b);
}

/*最大公約数*/
ll gcd(ll a, ll b){
    return __gcd(a,b);
}

/*組み合わせ(Combination)*/
const ll CMAX = 1010000;
const ll CMOD = 1e9+7;
ll fac[CMAX], finv[CMAX], inv[CMAX];
// テーブルを作る前処理
void combinit() {
	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 % CMOD;
		inv[i] = CMOD - inv[CMOD%i] * (CMOD / i) % CMOD;
		finv[i] = finv[i - 1] * inv[i] % CMOD;
	}
}
// 二項係数計算
ll comb(ll n, ll k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % CMOD) % CMOD;
}


const ll FMOD = 1e9+7;
ll factorial(ll n){
    vll dp(n+1);
    dp[0] = dp[1] = 1;
    rep2(i, 2, n+1) dp[i] = (dp[i-1] * i)%FMOD;
    return dp[n];
}

int main(){

    ll n, m; cin >> n >> m;

    if(abs(n-m)>1){
        cout << 0 << endl;
        return 0;
    }
    ll ans = factorial(n)*factorial(m)%(ll)(1e9+7);
    cout << (n==m?ans*2%(ll)(1e9+7):ans) << endl;

    return 0;
}

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

#define int long long
#define REP(i, n) for (int i = 0; i < (n); i++)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)

void init() {}

int N;
int W[303];
int dp[303][303];
bool done[303][303];
int rec(int l, int r) {
    if (r - l < 2) return 0;
    if (r == l + 2) {
        if (abs(W[l] - W[l + 1]) <= 1)
            return dp[l][r] = 2;
        else
            return dp[l][r] = 0;
    }
    if (done[l][r]) return dp[l][r];
    done[l][r] = true;
    if (abs(W[l] - W[r - 1]) <= 1) {
        if (rec(l + 1, r - 1) == r - l - 2) {
            return dp[l][r] = r - l;
        }
    }
    int res = 0;
    FOR(i, l + 1, r) { res = max(res, rec(l, i) + rec(i, r)); }
    return dp[l][r] = res;
}
bool solve() {
    cin >> N;
    if (N == 0) return false;
    REP(i, N) cin >> W[i];
    REP(i, N + 1) REP(j, N + 1) {
        done[i][j] = false;
        dp[i][j] = 0;
    }
    cout << rec(0, N) << endl;
    return true;
}
signed main() {
    init();
    while (solve())
        ;
}


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

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

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

    int now_max = 0;
    for(int i=0;i<n;i++){
        // max-1より小さい場合、単調非減少でなくなるので終了
        if(math_height[i]<now_max-1){
            cout << "No" << endl;
            return 0;
        }
        // maxより現在の要素が大きい場合はmaxを更新
        if(math_height[i]>now_max) now_max = math_height[i];
    }

    cout << "Yes" << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int n;
    //cin>>n;
    while(cin>>n){
        vector<int> a1(n);
        vector<int> a2(n);
        for(int i=0;i<n;i++){
            cin>>a1[i]>>a2[i];
        }
        long long s=a1[0], t=a2[0];
        for(int i=1;i<n;i++){
            long long ta=max(s/a1[i], t/a2[i]);
            while(!(s<=ta*a1[i]&&t<=ta*a2[i])){
                ta+=1;
            }
            s=ta*a1[i];
            t=ta*a2[i];
        }
        cout<<s+t<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ; ++i)
using namespace std;
using ll = long long ;
using P = pair<int, int> ;
#define PI 3.14159265358979323846264338327950
int main () {
    int N ;
    cin >> N ;
    vector<int> vec(N);
    rep(i,N){
        cin >> vec[i];
    }
    bool acc = true;
    rep(i,N){
        if(vec[i] % 2 == 0){
            if (vec[i] % 3 != 0 && vec[i] % 5 != 0){
                acc = false;
            }
        }
    }
    if (acc){
        cout << "APPROVED" << endl;
    }
    else {cout << "DENIED" << endl;}
}



Measured memory_bytes: 256
use proconio::fastout;
use proconio::input;

const MOD: u32 = 2019;

// 理解してない

#[fastout]
fn main() {
    input! { s: String, }
    let mut ss: Vec<u32> = s.chars().flat_map(|c| c.to_digit(10)).collect();
    ss.reverse();
    let n = ss.len();
    let mut x = 1;
    let mut tot = 0;
    let mut cnt = vec![0; MOD as usize];
    let mut ans = 0;
    for i in 0..n {
        cnt[tot as usize] += 1;
        tot += ss[i] * x;
        tot %= MOD;
        ans += cnt[tot as usize];
        x = x * 10 % MOD;
    }
    println!("{}", ans);
}


Measured memory_bytes: 3280
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,minn;
int gcd(int a,int b)
{
	if(!b)
		return a;
	return gcd(b,a%b);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d",&t);
		minn=gcd(abs(t-m),minn);
	}
	printf("%d",minn);
	return 0;
}

Measured memory_bytes: 256
from itertools import product
H, W, K = map(int, input().split())
c = [list(input()) for _ in range(H)]

ans = 0

for row_bit in product(range(2), repeat=H):
    for col_bit in product(range(2), repeat=W):
        count = 0
        for h in range(H):
            for w in range(W):
                if c[h][w] == "#" and (row_bit[h] == 0 and col_bit[w] == 0):
                    count += 1
        if count == K:
            ans += 1


print(ans)

Measured memory_bytes: 9216
#include<bits/stdc++.h>
using namespace std;
 
int main() {
  int N,i;
  cin>>N;
  
  vector<int> a(N);
  for(i=0;i<N;i++)cin>>a[i];
  sort(a.begin(), a.end());
  cout << a[N-1]-a[0] << endl;
}

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

using namespace std;

int countDigits(long long n) {
  int count = 0;

  while (n > 0) {
    n /= 10;
    count += 1;
  }

  return count;
}

int main() {
  long long N;
  cin >> N;

  int answer = countDigits(N);
  for (int A = 1; A <= sqrt(N); A++) {
    if (N % A != 0) {
      continue;
    }

    answer = min(answer, max(countDigits(A), countDigits(N / A)));
  }

  cout << answer << endl;
}


Measured memory_bytes: 256
S=str(input())
N=len(S)
T=S[0:int((N-1)/2)]
U=S[int((N+1)/2):N]
B=0
for i in range(len(T)):
 if T[i]==T[len(T)-1-i]:
  B+=1
if B==len(T) and T==U:
 print("Yes")
else:
 print("No")

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

int main(){
    int N;

    scanf("%d", &N);

    int *A = (int *) malloc(sizeof(int) * N);

    for(int i = 0; i < N; i ++){
        scanf("%d", A + i);
    }
    long long int ans = 1;

    int color[3] = {0, 0, 0};

    for(int i = 0; i < N; i ++){
        int count = 0;

        for(int j = 0; j < 3; j ++){
            if(color[j] == A[i]){
                count ++;
            }
        }
        ans *= count;
        ans %= 1000000007;

        for(int j = 0; j < 3; j ++){
            if(color[j] == A[i]){
                color[j] ++;

                break;
            }
        }
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 512
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [[int(a) for a in input().split()] for _ in range(2)]
    M = ((1, 0), (0, 1))
    q = deque()
    q.append((0, 0, 0))
    C = [[0] * N for _ in range(2)]
    while q:
        i, j, n = q.popleft()
        if n + A[i][j] > C[i][j]:
            C[i][j] = n + A[i][j]
            for di, dj in M:
                if 0 <= i + di < 2 and 0 <= j + dj < N:
                    q.append((i + di, j + dj, C[i][j]))
    print(C[1][N-1])


    return 0

if __name__ == "__main__":
    solve()

Measured memory_bytes: 3316
#include<iostream>
#include<cstdio>
using namespace std;
#define max(x,y) ((x)>(y)?(x):(y))
#define dfr(x,y) ((x)>(y)?((x)-(y)):((y)-(x)))
int main()
{
long long max=0,mind=100000000001,p,n,i;
long long inv[100000];
cin>>n;
for(i=0;i<n;i++)
{
cin>>inv[i];
if(inv[i]>max)max=inv[i];
}
for(i=0;i<n;i++)
{
int ndfr=dfr(inv[i]*2,max);
if((ndfr<mind)&&(inv[i]!=max))
{
mind=ndfr;
p=inv[i];
}
}
cout<<max<<" "<<p;
return 0;
}

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

int main() {
  int N,K;
  cin >> N >> K;
  
  vector<int> balls(N);
  for (int i=0;i<N;i++){
    int temp;
    cin >> temp;
    balls[temp-1] += 1;
  }
  
  sort(balls.begin(),balls.end(),greater<int>());
    
  int ans = 0;
  for (int i=K;i<N;i++){
      ans += balls[i];
  }
  
  cout << ans << endl;
}



Measured memory_bytes: 1024
#include<iostream>

using namespace std;

typedef long long ll;

namespace comb {
	ll fact[500001];
	ll fact_inv[500001];
	const ll MOD = 1000000007;

	ll modpow(ll a, ll b) {
		ll base = 1, kakeru = a;
		while (b > 0) {
			if (b & 1)base *= kakeru, base %= MOD;
			kakeru *= kakeru, kakeru %= MOD;
			b >>= 1;
		}
		return base;
	}

	void setup() {
		fact[0] = 1, fact[1] = 1;
		for (int i = 2; i <= 500000; i++) {
			fact[i] = (fact[i - 1] * i) % MOD;
		}

		fact_inv[500000] = modpow(fact[500000], MOD - 2);

		for (int i = 499999; i >= 0; i--) {
			fact_inv[i] = fact_inv[i + 1] * (i + 1);
			fact_inv[i] %= MOD;
		}

	}

	ll combination(int a, int b) {
		if (a - b < 0)return 0;
		ll ret = fact[a];
		ret *= fact_inv[b], ret %= MOD;
		ret *= fact_inv[a - b], ret %= MOD;
		return ret;
	}

	ll permutation(int a, int b) {
		if (a - b < 0)return 0;
		ll ret = fact[a];
		ret *= fact_inv[a - b], ret %= MOD;
		return ret;
	}

	ll homogeneous(int a, int b) {
		return combination(a + b - 1, b);
	}

}

int N, A, B, C, D;

ll dp[1000 + 10][1000 + 10];//dp[i][j] := (i > 0)ならi + A - 1人のグループを作り終えて、合計j人使った時, i == 0の時はなにも使ってないとき

int main() {
	comb::setup();
	cin >> N >> A >> B >> C >> D;

	dp[0][0] = comb::fact[N];

	for (int i = 1; i <= (B - A + 1); i++) {
		for (int j = 0; j <= N; j++) {
			dp[i][j] += dp[i - 1][j];
			dp[i][j] %= comb::MOD;
			for (int k = C; k <= D; k++) {
				if (k * (A + i - 1) <= j) {
					dp[i][j] += (((dp[i - 1][j - k * (A + i - 1)] * comb::modpow(comb::fact_inv[A + i - 1], k)) 
						% comb::MOD) * comb::fact_inv[k]) % comb::MOD;
					dp[i][j] %= comb::MOD;
				}
				else break;
			}
			//cout << i << " " << j << " " << dp[i][j] << endl;
		}
	}
	cout << dp[B - A + 1][N] << endl;
	return 0;
}

Measured memory_bytes: 16000
#include <bits/stdc++.h>
#define inf 8000000000000000000LL
using namespace std;
int T,a,b,c,d;
long long n;
map<long long,long long> mp;
long long solve(long long x)
{
    if (mp.find(x)!=mp.end()) return mp[x];
    if (x<=1LL) return 1LL*x*d;
    long long res=inf;
    if (x%2==0) 
    {
        if (solve(x/2)<=inf) res=min(res,solve(x/2)+a);
    }
    else if (x%2==1) 
    {
        if (solve(x/2)<=inf) res=min(res,solve(x/2)+a+d);
        if (solve((x+1)/2)<=inf) res=min(res,solve((x+1)/2)+a+d);
    }
    if (x%3==0) 
    {
        if (solve(x/3)<=inf) res=min(res,solve(x/3)+b);
    }
    else if (x%3==1) 
    {
        if (solve(x/3)<=inf) res=min(res,solve(x/3)+b+d);
    }
    else if (x%3==2) 
    {
        if (solve((x+1)/3)<=inf) res=min(res,solve((x+1)/3)+b+d);
    }
    if (x%5==0) 
    {
        if (solve(x/5)<=inf) res=min(res,solve(x/5)+c);
    }
    else if (x%5==1) 
    {
        if (solve(x/5)<=inf) res=min(res,solve(x/5)+c+d);
    }
    else if (x%5==2) 
    {
        if (solve(x/5)<=inf) res=min(res,solve(x/5)+c+d+d);
    }
    else if (x%5==3) 
    {
        if (solve((x+2)/5)<=inf) res=min(res,solve((x+2)/5)+c+d+d);
    }
    else if (x%5==4) 
    {
        if (solve((x+1)/5)<=inf) res=min(res,solve((x+1)/5)+c+d);
    }
    if (x<=res/d) res=1LL*x*d;
    mp[x]=res;
    return res;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        mp.clear();
        scanf("%lld%d%d%d%d",&n,&a,&b,&c,&d);
        printf("%lld\n",solve(n));
    }
    return 0;
}

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

using namespace std;
vector<int> fib(50);

int makefib(int n){
  if(n==0||n==1) return fib[n]=1;
  if(fib[n]!=-1) return fib[n];
  else return fib[n]=makefib(n-1)+makefib(n-2);
}
		  
int a;
int main(void){
  cin>>a;
  for (int i=0; i<50; i++) fib[i]=-1;
  cout<<makefib(a)<<endl;
  return 0;
}

Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define mod 1000000007
#define mod998 998244353
#define sp ' '
#define intmax 2147483647
#define llmax 9223372036854775807
#define mkp make_pair
typedef long long ll;
using namespace std;

int N, M;
ll f[2000001], res;

ll pw(ll x, int y) {
	ll a = 1;
	while (y) {
		if (y & 1)a = a*x%mod998;
		x = x*x%mod998;
		y /= 2;
	}
	return a;
}

ll modinv(ll x) {
	return pw(x, mod998 - 2);
}

ll comb(int n, int r) {
	if (n < r)return 0;
	return f[n] * modinv(f[r] * f[n - r] % mod998) % mod998;
}

int main() {
	cin >> N >> M;
	f[0] = 1;
	for (int i = 1; i <= 2000000; ++i) {
		f[i] = f[i - 1] * i%mod998;
	}
	for (int i = 0; i <= min(N, M); ++i) {
		if ((3 * M - i) % 2)continue;
		int t = M + (M - i) / 2;
		res += (comb(t + N - 1, N - 1) + mod998 - comb(t - M + N - 1, N - 1)*i%mod998 + mod998 - comb(t - M - 1 + N - 1, N - 1)*(N - i) % mod998) % mod998*comb(N, i);
		res %= mod998;
	}
	cout << res << endl;
}

Measured memory_bytes: 15872
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <functional>
#define SIZE 25
#define BT 1<<20
#define MOD 1000000007
#define MX 205

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

ll dp[BT],way[BT];
ll C[MX][MX];
vector <P> vec[SIZE];
int cnt[BT],cnt2[BT];
int memo[SIZE][BT];

void make()
{
	for(int i=0;i<MX;i++)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
		{
			C[i][j]=(C[i-1][j-1]+C[i-1][j])%MOD;
		}
	}
}
int dfs(int v,int p,int goal)
{
	if(v==goal) return 0;
	for(int i=0;i<vec[v].size();i++)
	{
		int to=vec[v][i].first;
		if(to!=p)
		{
			int ret=dfs(to,v,goal);
			if(ret!=-1) return ret|(1<<vec[v][i].second);
		}
	}
	return -1;
}
int main()
{
	make();
	int n,m;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n-1;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--,b--;
		vec[a].push_back(P(b,i));
		vec[b].push_back(P(a,i));
	}
	for(int i=n-1;i<m;i++)
	{
		int a,b;
		scanf("%d %d",&a,&b);a--,b--;
		int S=dfs(a,-1,b);
		cnt[S]++;
	}
	int sz=n-1;
	for(int i=0;i<sz;i++)
	{
		for(int S=0;S<1<<sz;S++) memo[i][S]=cnt[S];
		for(int j=0;j<sz;j++)
		{
			if(j==i) continue;
			for(int S=0;S<1<<sz;S++) if(S>>j&1) memo[i][S]+=memo[i][S-(1<<j)];
		}
	}
	memset(dp,0,sizeof(dp));
	memset(way,0,sizeof(way));
	way[(1<<sz)-1]=1;
	for(int S=(1<<sz)-1;S>=0;S--)
	{
		int nm=0;
		for(int i=0;i<sz;i++) if(!(S>>i&1)) nm++;
		for(int i=0;i<sz;i++)
		{
			if(S>>i&1)
			{
				//printf("%d %d : %d\n",i,S,memo[i][S]);
				ll w=way[S],d=dp[S],c=cnt2[S];
				for(int j=0;j<memo[i][S];j++)
				{
					ll c2=c+1;
					ll w2=w*(c+1)%MOD;
					ll d2=d*(c+2)%MOD;
					c=c2,w=w2,d=d2%MOD;
				}
				int T=S-(1<<i);
				cnt2[T]=cnt2[S]+memo[i][S]+1;
				dp[T]+=(d+w*(ll) (nm+1))%MOD;
				if(dp[T]>=MOD) dp[T]-=MOD;
				way[T]+=w;
				if(way[T]>=MOD) way[T]-=MOD;
			}
		}
		//printf("%d : %lld %lld\n",S,way[S],dp[S]);
	}
	printf("%lld\n",dp[0]);
	return 0;
}


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

using namespace std;
using ll = long long;

int main(){
    ll N;cin >> N;
    vector<ll> vec;
    vec.push_back(0);
    ll s = 0;
    for(int i = 0;i < N;i++){
        int a;cin >> a;
        s += a;
        vec.push_back(a);
    }
    ll ans = 1e18;
    ll q = 0;
    ll ins = 0;
    for(int i = 0;i < N+1;i++){
        ins += vec[i];
        ans = min(abs(s/2-ins) + abs(s/2 - (s - ins)), ans);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2420
using System;
using System.Collections.Generic;
using System.Linq;

namespace _039_RomanFigure
{
	class Program
	{
		static void Main ( string[] args )
		{
			Dictionary<char, int> map = new Dictionary<char, int> (7);
			map.Add ('I', 1);
			map.Add ('V', 5);
			map.Add ('X', 10);
			map.Add ('L', 50);
			map.Add ('C', 100);
			map.Add ('D', 500);
			map.Add ('M', 1000);

			string inputStr;

			while ((inputStr = Console.ReadLine ()) != null)
			{
				int result = 0;

				int value = map[inputStr[0]];
				result += value;

				for (int lp = 1; lp < inputStr.Length; lp++)
				{
					int nextValue = map[inputStr[lp]];

					if (value >= nextValue)
					{
						result += nextValue;
					}
					else
					{
						result += -value * 2 + nextValue;
					}

					value = nextValue;
				}

				Console.WriteLine (result);
			}
		}
	}
}

Measured memory_bytes: 9504
N, K = map(int, input().split())
X = list(map(int, input().split()))

def dist(i):
    a = abs(X[K - 1 + i]) + X[K - 1 + i] - X[i]
    b = abs(X[i]) + X[K - 1 + i] - X[i]
    return min(a, b)

ans = dist(0)
for i in range(N):
    if i + K > N:
        break
    ans = min(ans, dist(i))
print(ans)


Measured memory_bytes: 14228
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/


#include<bits/stdc++.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<iostream>
#include<vector>
#include<cstdlib>
using namespace std;
 
template <class T> using V = vector<T>;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
 
const long long INF = 1LL << 60;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using bl = bool;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
using vbl = V<bl>;

 
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>=(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
  
 

ll sum(ll n) {
ll m=0;
  while(n){
    m+=n%10;
    n/=10;
  }
  return m;
}
 
 
const int MAX = 510000;
const int MOD = 1000000007;
 
long long fac[MAX], finv[MAX], inv[MAX];
 
void Comuse() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; 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;
    }
}
 
 
#define comuse Comuse()
 
ll combi(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
 
 
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}

 
 

signed main() {
  long long h,w,a,b;
    cin>>h>>w>>a>>b;
  for(int i=0;i<h;i++){
    if(i<b){
    	string s(a,'0');
    	string t(w-a,'1');
    	s+=t;
    	cout<<s<<endl;
    }
    else{
      string s(a,'1');
    	string t(w-a,'0');
    	s+=t;
    	cout<<s<<endl;
    }
  }
}

Measured memory_bytes: 1280
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lpair = pair<ll, ll>;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i=(m);i<(n);i++)
#define rrep(i,m,n) for(ll i=(m);i>=(n);i--)
#define printa(x,n) for(ll i=0;i<n;i++){cout<<(x[i])<<" \n"[i==n-1];};
void print() {}
template <class H,class... T>
void print(H&& h, T&&... t){cout<<h<<" \n"[sizeof...(t)==0];print(forward<T>(t)...);}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    ll A[110];
    rep(i,0,N) cin >> A[i];
    sort(A, A+N);
    ll max_val = A[N-1];
    ll min_val = A[0];
    if(min_val != (max_val + 1) / 2){
        print("Impossible");
        return 0;
    }
    map<ll,ll> mp;
    rep(i,0,N) mp[A[i]]++;
    if(max_val % 2 == 0){
        bool ok = true;
        if(mp[min_val] != 1) ok = false;
        rep(i,min_val+1, max_val+1){
            if(mp[i] < 2) ok = false;
        }
        if(ok){
            print("Possible");
        }else{
            print("Impossible");
        }
    }else{
        bool ok = true;
        if(mp[min_val] != 2) ok = false;
        rep(i,min_val+1, max_val+1){
            if(mp[i] < 2) ok = false;
        }
        if(ok){
            print("Possible");
        }else{
            print("Impossible");
        }
    }

    

}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;
const LLONG MOD = 1000000007;

int main()
{
    int N; cin >> N;
    if (N == 0)
    {
        // 根ノードのみの場合
        int a0; cin >> a0;
        cout << (a0 == 1 ? 1 : -1) << endl;
        return 0;
    }
    vector<LLONG> as(N + 1); for (auto &ai : as) cin >> ai;
    if (as[0] != 0)
    {
        // 深さN>0のとき，A0はゼロでなければならない
        cout << -1 << endl;
        return 0;
    }
	vector<LLONG> sums(N + 1);	// sums[i] = Ai + ... + AN
	LLONG sum = 0;
	for (int i = N; i >= 0; --i)
	{
		sums[i] = sum;
		sum += as[i];
	}
	// 各深さdにおいて葉でない頂点数bs[d]を計算する
	vector<LLONG> bs(N + 1);
	bs[0] = 1;
	for (int d = 1; d <= N; ++d)
	{
		bs[d] = min(sums[d], bs[d - 1] * 2 - as[d]);
	}
	LLONG ans = 0;
	for (int d = 0; d <= N; ++d)
	{
		if (bs[d] < 0)
		{
			ans = -1;
			break;
		}
		ans += as[d] + bs[d];
	}
	cout << ans << endl;
}

Measured memory_bytes: 5620
H,W = map(int,input().split())
grid = [input() for i in range(H)]

INF = 10 ** 18

ans = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            continue
        dist = [[INF] * W for _ in range(H)]
        dist[h][w] = 0
        q = [(h,w)]
        d = 1
        while q:
            qq = []
            for y,x in q:
                for dy,dx in [(-1,0),(1,0),(0,-1),(0,1)]:
                    yy,xx = y+dy, x+dx
                    if not (0 <= yy < H and 0 <= xx < W):
                        continue
                    if grid[yy][xx] == '#':
                        continue
                    if dist[yy][xx] != INF:
                        continue
                    dist[yy][xx] = d
                    qq.append((yy,xx))
            q = qq
            d += 1
        for i in range(H):
            for j in range(W):
                if dist[i][j] != INF:
                    ans = max(ans,dist[i][j])

print(ans)

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#include <random>
#include <cassert>
using namespace std;
 
#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<int, ll> i_ll;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
typedef vector<int> vi;
struct edge { int v; ll w; };
 
const int MOD = 1000000007;
ll _MOD = 1000000009;
double EPS = 1e-10;
int INF = INT_MAX / 2;

ll solve(int N, vector<int> a, bool z) {
	ll sum = 0, ans = 0;
	rep(i, N) {
		sum += a[i];
		if (z) {
			ll k = max(0LL, 1 - sum);
			sum += k;
			ans += k;
		}
		else {
			ll k = max(0LL, sum - (-1));
			sum -= k;
			ans += k;
		}
		z = !z;
	}
	return ans;
}

int main() {
	int N; cin >> N;
	vector<int> a(N);
	rep(i, N) scanf("%d", &a[i]);
	ll ans = min(solve(N, a, true), solve(N, a, false));
	cout << ans << endl;
}


Measured memory_bytes: 1408
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
r = ['.'] * w

for i in range(h-1, -1, -1):
    if a[i] == r:
        del(a[i])

h = len(a)
for i in range(w-1, -1, -1):
    allw = True
    for j in range(h):
        if a[j][i] != '.':
            allw = False
    if allw:
        for j in range(h):
            del(a[j][i])

for ai in a:
    print(''.join(ai))


Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e12;
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
namespace std{
    bool operator < (const P& a, const P& b){
        return (a.X!=b.X) ? a.X<b.X : a.Y<b.Y;
    }
    bool operator == (const P& a, const P& b){
        return abs(a-b) < EPS;
    }
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}
VP convex(VP v){
    VP ret;
    int n = v.size();
    sort(v.begin(), v.end());
    for(int i=0; i<n; i++){
        while((int)ret.size()>1 && cross(ret.back()-ret[ret.size()-2], v[i]-ret.back()) < EPS){
            ret.pop_back();
        }
        ret.push_back(v[i]);
    }
    int t = ret.size();
    for(int i=n-2; i>=0; i--){
        while((int)ret.size()>t && cross(ret.back()-ret[ret.size()-2], v[i]-ret.back()) < EPS){
            ret.pop_back();
        }
        ret.push_back(v[i]);
    }
    if((int)ret.size() > 1) ret.pop_back();
    return ret;
}

struct UnionFindTree{
    vector<int> v;
    vector<int> rank;
    
    UnionFindTree(int n): v(n, -1), rank(n, 0){}
    int Find(int x){
        if(v[x] < 0) return x;
        return v[x] = Find(v[x]);
    }
    void Union(int a, int b){
        a = Find(a);
        b = Find(b);
        if(a == b) return;
        if(rank[a] < rank[b]) swap(a, b);
        if(rank[a] == rank[b]) rank[a]++;
        v[b] = a;
    }
};

struct edge{
    int s,t;
    double d;
    edge(int s, int t, double d):s(s),t(t),d(d){}
    edge(){}
    bool operator<(const edge &a){
        return d < a.d;
    }
};

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

    VP p(v);
    for(int i=0; i<v; i++){
        int x,y;
        cin >> x >> y;
        p[i] = P(x, y);
    }
    vector<edge> e(r);
    for(int i=0; i<r; i++){
        int s,t;
        cin >> s >> t;
        s--; t--;
        e[i] = edge(s, t, abs(p[s] -p[t]));
    }
    sort(e.begin(), e.end());

    VP con = convex(p);
    int n = con.size();
    vector<int> conidx(n);
    for(int i=0; i<n; i++){
        conidx[i] = find(p.begin(), p.end(), con[i]) -p.begin();
    }

    double ans = 0;
    UnionFindTree uft(v);
    for(int i=0; i<n; i++){
        uft.Union(conidx[i], conidx[(i+1)%n]);
        ans += abs(p[conidx[i]] -p[conidx[(i+1)%n]]);
    }
    for(int i=0; i<r; i++){
        if(uft.Find(e[i].s) != uft.Find(e[i].t)){
            uft.Union(e[i].s, e[i].t);
            ans += e[i].d;
        }
    }
    cout << fixed << setprecision(10);
    cout << ans << endl;
    return 0;
}


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

typedef long long LL;
const int N = 100005;
int n, m, top;
LL q[N], c[N], ans[N];

void solve(LL len, int id) {
	if (!len) return;
	if (len <= q[1]) ans[0] += c[id], ans[len] -= c[id];
	else {
		int t = std::upper_bound(q + 1, q + m + 1, len) - q - 1;
		c[t] += len / q[t] * c[id], solve(len % q[t], id);
	}
}
int main() {
	std::ios::sync_with_stdio(0), std::cin.tie(0);
	std::cin >> n >> m, q[top = 1] = n;
	for (int i = 1; i <= m; ++i) {
		LL x; std::cin >> x;
		while (top && q[top] >= x) --top;
		q[++top] = x;
	}
	c[m = top] = 1;
	for (int i = m - 1; i; --i)
		c[i] += q[i + 1] / q[i] * c[i + 1], solve(q[i + 1] % q[i], i + 1);
	ans[0] += c[1], ans[q[1]] -= c[1];
	for (int i = 1; i < n; ++i) ans[i] += ans[i - 1];
	for (int i = 0; i < n; ++i) std::cout << ans[i] << '\n';
	return 0;
}

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

using namespace std;

int n;
double d;
int ans=0;

int main(){
	scanf("%d%lf",&n,&d);
	for(int i=1;i<=n;i++){
		double x,y;
		double dis;
		scanf("%lf%lf",&x,&y);
		dis=sqrt(x*x+y*y);
		if(dis<=d){
			ans++;
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3880
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <vector>
#include <list>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
//#define cerr if(false) cerr
#ifdef DEBUG
#define show(...) cerr << #__VA_ARGS__ << " = ", debug(__VA_ARGS__);
#else
#define show(...) 42
#endif
using namespace std;
using ll = long long;
using pii = pair<int, int>;
template <typename T, typename S>
ostream& operator<<(ostream& os, pair<T, S> a) {
    os << '(' << a.first << ',' << a.second << ')';
    return os;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> v) {
    for (auto x : v) os << x << ' ';
    return os;
}
void debug() {
    cerr << '\n';
}
template <typename H, typename... T>
void debug(H a, T... b) {
    cerr << a;
    if (sizeof...(b)) cerr << ", ";
    debug(b...);
}
template <typename T>
vector<T> divisor(T n) {
    vector<T> res;
    for (T i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            res.push_back(i);
            if (i * i != n) {
                res.push_back(n / i);
            }
        }
    }
    sort(res.begin(), res.end());
    return res;
}
template <typename T>
map<T, int> prime_factor(T n) {
    map<T, int> res;
    for (T i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            res[i]++;
            n /= i;
        }
    }
    if (n != 1) {
        res[n]++;
    }
    return res;
}
template <typename T>
T gcd(T a, T b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}
template <typename T>
T lcm(T a, T b) {
    return a / gcd(a, b) * b;
}
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    ll m;
    cin >> n >> m;
    vector<ll> a(n);
    rep(i,n)cin >> a[i];
    rep(i,n)a[i] /= 2;
    vector<int>c(n);
    rep(i,n){
        while(a[i] % (1 << c[i]) == 0)c[i]++;
    }
    sort(c.begin(),c.end());
    if(c[0] != c.back()){
        cout << 0 << endl;
        return 0;
    }
    ll L = a[0];
    rep(i,n-1){
        L = lcm(L, a[i+1]);
        if(L > m){
            cout << 0 << endl;
            return 0;
        }
    }
    cout << 1 + (m - L) / (L * 2) << endl;
}


Measured memory_bytes: 1408
package main

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

func main() {
	N := readInt()
	a := make([][]int, N)
	for i := 0; i < N; i++ {
		a[i] = make([]int, N-1)
		for j := 0; j < N-1; j++ {
			a[i][j] = readInt() - 1
		}
	}

	nextIndex := make([]int, N)
	nextQueue := make([]int, 0, N)
	for i := 0; i < N; i++ {
		nextQueue = append(nextQueue, i)
	}
	result := 0
	finished := 0

	for len(nextQueue) > 0 {
		result++
		queue := nextQueue
		nextQueue = nil
		booked := make([]bool, N)
		for i := 0; i < len(queue); i++ {
			player := queue[i]
			if booked[player] {
				continue
			}
			if nextIndex[player] == N-1 {
				continue
			}
			opponent := a[player][nextIndex[player]]
			if booked[opponent] {
				continue
			}
			if a[opponent][nextIndex[opponent]] != player {
				continue
			}
			booked[player] = true
			booked[opponent] = true
			nextIndex[player]++
			nextIndex[opponent]++
			if nextIndex[player] == N-1 {
				finished++
			} else {
				nextQueue = append(nextQueue, player)
			}
			if nextIndex[opponent] == N-1 {
				finished++
			} else {
				nextQueue = append(nextQueue, opponent)
			}
		}
	}
	if finished == N {
		fmt.Println(result)
	} else {
		fmt.Println(-1)
	}
}

const (
	ioBufferSize = 1 * 1024 * 1024 // 1 MB
)

var stdinScanner = func() *bufio.Scanner {
	result := bufio.NewScanner(os.Stdin)
	result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	result.Split(bufio.ScanWords)
	return result
}()

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}


Measured memory_bytes: 19456
using System;
using System.Text;
using static ConsoleReader;

class Program
{
    static void Main(string[] args)
    {
        var s = Read<string>();
        var t = Read<string>();

        var result = 0;
        s.Length.Times(i =>
        {
            if (s[i] != t[i]) result++;
        });

        Console.WriteLine(result);
    }
}

public static class IntExtentions
{
    public static void Times(this int n, Action<int> action)
    {
        for (var i = 0; i < n; i++)
        {
            action(i);
        }
    }

    public static void Times(this (int n, int m) dimensions, Action<int, int> action)
    {
        var (n, m) = dimensions;
        n.Times(i => m.Times(j => action(i, j)));
    }
}

public static class ConsoleReader
{
    public static T Read<T>()
        where T : IConvertible
    {
        var inputBuffer = new StringBuilder();
        int currChar;

        while ((currChar = Console.Read()) != -1)
        {
            if (!char.IsWhiteSpace((char)currChar))
            {
                inputBuffer.Append((char)currChar);
            }
            else if (inputBuffer.Length != 0)
            {
                break;
            }
        }

        return (T)Convert.ChangeType(inputBuffer.ToString(), typeof(T));
    }

    public static T[] ReadArray<T>(int count)
        where T : IConvertible
    {
        if (count < 0)
        {
            throw new ArgumentOutOfRangeException(nameof(count), $"'{nameof(count)}' must be >= 0");
        }

        var result = new T[count];

        for (var i = 0; i < count; i++)
        {
            result[i] = Read<T>();
        }

        return result;
    }
}

Measured memory_bytes: 27588
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#define vll vector<ll>
#define vvvl vector<vvl>
#define vvl vector<vector<ll>>
#define VV(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define VVV(a, b, c, d) vector<vvl>(a, vvl(b, vll (c, d)));
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;

template <typename G>
struct HLD {
  G &g;
  vector<int> sz, in, out, head, rev, par;
  HLD(G &g) :
      g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}

  void dfs_sz(int idx, int p) {
    par[idx] = p;
    sz[idx] = 1;
    if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
    for(auto &to : g[idx]) {
      if(to == p) continue;
      dfs_sz(to, idx);
      sz[idx] += sz[to];
      if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
    }
  }

  void dfs_hld(int idx, int par, int &times) {
    in[idx] = times++;
    rev[in[idx]] = idx;
    for(auto &to : g[idx]) {
      if(to == par) continue;
      head[to] = (g[idx][0] == to ? head[idx] : to);
      dfs_hld(to, idx, times);
    }
    out[idx] = times;
  }

  void build() {
    dfs_sz(0, -1);
    int t = 0;
    dfs_hld(0, -1, t);
  }

  int la(int v, int k) {
    while(1) {
      int u = head[v];
      if(in[v] - k >= in[u]) return rev[in[v] - k];
      k -= in[v] - in[u] + 1;
      v = par[u];
    }
  }

  int lca(int u, int v) {
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) return u;
    }
  }

  template <typename T, typename Q, typename F>
  T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) {
    T l = ti, r = ti;
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v), swap(l, r);
      if(head[u] == head[v]) break;
      l = f(q(in[head[v]], in[v] + 1), l);
    }
    return f(f(q(in[u] + edge, in[v] + 1), l), r);
//  return {f(q(in[u] + edge, in[v] + 1), l), r};
  }

  template <typename Q>
  void add(int u, int v, const Q &q, bool edge = false) {
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) break;
      q(in[head[v]], in[v] + 1);
    }
    q(in[u] + edge, in[v] + 1);
  }
};


int main(int argc, char const *argv[]) {
  ll n, a, x, y;scanf("%lld", &n);
  vvl G = VV(n, 0, 0, ll);
  HLD<vvl> h(G);

  for(int i=0;i<n;i++){
    ll k;scanf("%lld", &k);
    for(int j=0;j<k;j++){
      scanf("%lldd", &a);
      G[i].push_back(a);
      G[a].push_back(i);
    }
  }
  h.build();
  ll q;scanf("%lld", &q);
  for(int i=0;i<q;i++){
    scanf("%lld %lld", &x, &y);
    printf("%d\n", h.lca(x, y));
  }
  return 0;
}



Measured memory_bytes: 15260
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
#include <math.h>
#include <queue>
#define rep(i,n) for (int i = 0; i < (n); ++i)
typedef long long ll;
using namespace std;

int f(int x, int y, int z) {
    return x*x + y*y + z*z + x*y + y*z +z*x; 
}

int main() {
    int n;
    cin >> n;
    for(int x=1; x<=n; x++) {
        int cnt=0;
        for(int i=1; i<sqrt(n); i++) {
            if(f(i,1,1)>x) break;
            for(int j=1; j<sqrt(n); j++) {
                if(f(i,j,1)>x) break;
                for(int k=1; j<sqrt(n); k++) {
                    if(f(i,j,k)==x) cnt++;
                    if(f(i,j,k)>=x) break;
                }
            }
        }
        cout << cnt << endl;
    }
}

Measured memory_bytes: 3144
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

def GCD(a,b):
    while b!=0:
        a,b = b,a%b
    return a

def LCM(a,b):
    return a * b // GCD(a,b)

def Eratosthenes(N):
    r = [True]*(N+1)
    r[0] = False
    r[1] = False
    i = 2
    while i*i<=N:
        if r[i]: 
            j = i
            while i*j<=N:
                r[i*j]=False
                j+=1
        i+=1
    return(r)

def main():
    prime = Eratosthenes(10**5)
    prime_2017 = [False]*(10**5+1)
    for i in range(3,10**5+1,2):
        if prime[i]:
            prime_2017[i] = prime[(i+1)//2]

    cnt = [0]*(10**5+1)
    nxt = 0

    for i in range(1,10**5+1):
        if prime_2017[i]:
            nxt += 1
        cnt[i] = nxt

    Q = I()
    for _ in range(Q):
        l,r = LI()
        print(cnt[r] - cnt[l-1])

            


if __name__ == "__main__":
    main()


Measured memory_bytes: 54488
#include<bits/stdc++.h>
#define rep(i,f,n) for(ll i=(f); (i) < (n); i++)
#define repe(i,f,n) for(ll i=(f); (i) <= (n); i++)
using namespace std;

typedef long long ll;
ll INF = 1LL << 60;

int
main() 
{
  int D; cin >> D;
  ll G; cin >> G;
  vector<vector<ll>> point(D);
  rep(i, 0, D){
    ll p; cin >> p;
    ll c; cin >> c;
    point[i].push_back((i + 1) * 100);
    point[i].push_back(p);
    point[i].push_back((i + 1) * 100 * p + c);
  }

  //sort(point.begin(), point.end(), [](const vector<long long>&alpha,const vector<long long> &beta){return alpha[2] > beta[2];});

  ll ans = INF;
  for(int bit = 0; bit < (1 << D); ++bit){
    ll tmp_sum = G;
    ll tmp_ans = 0;
    for(int i = 0; i < D; i++){
      if(bit & (1 << i)){
       tmp_sum -= point[i][2]; 
       tmp_ans += point[i][1];
      }
    }
    if(tmp_sum > 0){
      ll tmp_index = -1;
      rep(i, 0, D){
        if(!(bit & (1 << i))) tmp_index = i;
      }
      if(tmp_index != -1){
        rep(i, 0, point[tmp_index][1]){
          tmp_sum -= point[tmp_index][0];
          tmp_ans++;
          if(tmp_sum <= 0) break;
        }
      }
    }
    if(ans > tmp_ans && 0 >= tmp_sum) ans = tmp_ans;
  }

  cout << ans << endl;

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
ll n,m;
cin >> n >> m;
pair<ll, ll> pr[n];
for (ll i = 0; i < n; i++) {
    ll a,b;
    cin >> a >> b;
    pr[i] = make_pair(a, b);
}
sort(pr, pr + n);
ll ans = 0;
for (ll i = 0; i < n;i++) {
    m -= pr[i].second;
    ans += pr[i].first * pr[i].second;
    if (m == 0) break;
    if (m < 0) {
            ans += pr[i].first * m;
            break;
    }
}
cout << ans << endl;
}


Measured memory_bytes: 1792