akhauriyash/Code-Regression huggingface dataset:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
X = list(input())

# xが0になるまで何回かかるか
def calc(x):
    n = len(x)
    c = x.count('1')
    now = 0
    for i in range(n):
        if x[i] == '1':
            now += 2**(n-1-i)
            now %= c
    if now == 0:
        return 1
    else:
        return calc(list(format(now,'b')))+1

count = X.count('1')

a = [1]*(N+1)
if count >= 2:
    a[0] = 1%(count-1)
    for i in range(1,N+1):
        a[i] = a[i-1]*2
        a[i] %= count-1

b = [1]*(N+1)
b[0] = 1%(count+1)
for i in range(1,N+1):
    b[i] = b[i-1]*2
    b[i] %= count+1

suma = 0
sumb = 0
for i in range(N):
    if X[i] == '1':
        suma += a[N-i-1]
        sumb += b[N-i-1]
        sumb %= (count+1)
        if count >= 2:
            suma %= (count-1)

ans = [0]*N
for i in range(N):
    if X[i] == '1':
        if count == 1:
            ans[i] = 0
            continue
        val = (suma-a[N-i-1])%(count-1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1
    else:
        val = (sumb+b[N-i-1])%(count+1)
        if val == 0:
            ans[i] = 1
        else:
            ans[i] = calc(list(format(val,'b')))+1

for a in ans:
    print(a)

Measured memory_bytes: 87156
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define ll int64_t
#define _GLIBCXX_DEBUG
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
int main(){
  bool bo=false;
  int a,b,c;
  cin >>a>>b>>c;
  rep(i,b)
    if((i*a)%b==c)bo=true;
  if(bo)cout <<"YES"<<endl;
  else cout << "NO" << endl;
}

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

using namespace std;

typedef long long ll;

double getTime() {
  return clock() / (double) CLOCKS_PER_SEC;
}

void read() {};

template<typename T, typename... Args>
void read(T& a, Args&... args) {
  cin >> a;
  read(args...);
}

void print() {};

template <typename T, typename... Args>
void print(T a, Args... args) {
  cout << a << " \n"[sizeof...(args) == 0];
  print(args...);
}

bool can(ll x, ll p) {
  while(x % p == 0) {
    x /= p;
  }
  return x % p == 1;
}

double getSum(double x) {
  return x * (x + 1.0) / 2.0;
}

int main() {
  string s; cin >> s;
  string x = "";
  string y = "";
  for(int i = 0; i < 4; i++) {
    if(i <= 1) {
      x += s[i];
    }
    else y += s[i];
  }
  int X = stoi(x), Y = stoi(y);
  if(1 <= X and X <= 12) {
    if(1 <= Y and Y <= 12) {
      print("AMBIGUOUS");
    }
    else {
      print("MMYY");
    }
  }
  else if(1 <= Y and Y <= 12) {
    print("YYMM");
  }
  else {
    print("NA");
  }
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-

s = list(input())
t = list(input())

ans = len(t)

for i in range(len(s) - len(t) + 1):
    n_replace = 0
    for j in range(len(t)):
        if s[i + j] != t[j]:
            n_replace += 1
    ans = min(ans, n_replace)

print(ans)



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

int main(){
  int n,k,q;
  cin >> n >> k >> q;
  vector<int> p(n, k-q);//p(配列の長さ, 初期値)。初期値がk-qなのはq回みんな、-1されるから予めkからq引いとくってこと。kだと計算量が大変なことになる
  rep(i,q) {
    int a;
    cin >> a;
    --a;//みんな、-1する
    p[a]++;//a番目の人を1点加算
  }
  rep(i,n) {
    if (p[i]<=0) puts("No");//putsは文字列を出力し、自動で改行してくれるもの
    else puts("Yes");
    }
    return 0;
}


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

int main(){
    unsigned N, K;
    scanf("%u %u", &N, &K);
    int V[N];
    for(int i = 0; i < N; ++i){
        scanf("%d", V + i);
    }
    unsigned take_out_max = min(N, K);
    int ruiseki[N+1];
    ruiseki[0] = 0;
    for (size_t i = 0; i < N; i++){
        ruiseki[i+1] = ruiseki[i] + V[i];
    }
    int answer = 0;
    for (size_t take_out_from_left = 0; take_out_from_left <= take_out_max; take_out_from_left++){
        int take_out[take_out_max];
        for (size_t tmp = 0; tmp < take_out_from_left; tmp++){
            take_out[tmp] = V[tmp];
        }
        for (size_t take_out_from_right = 0; take_out_from_left + take_out_from_right <= take_out_max; take_out_from_right++){
            if(take_out_from_right) take_out[take_out_from_left + take_out_from_right - 1] = V[N - take_out_from_right];
            sort(take_out, take_out + take_out_from_left + take_out_from_right);
            int candidate = ruiseki[take_out_from_left] + ruiseki[N] - ruiseki[N - take_out_from_right];
            unsigned n_put_back = 0;
            while(n_put_back + take_out_from_left + take_out_from_right < K && n_put_back < take_out_from_left + take_out_from_right && take_out[n_put_back] < 0){
                candidate -= take_out[n_put_back];
                n_put_back++;
            }
            if(candidate > answer) answer = candidate;
        }
    }
    printf("%d\n", answer);
	return 0;
}

Measured memory_bytes: 256
#pragma target("avx")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef unordered_map<ll, ll> U_MAP;
typedef priority_queue<ll> pq;
typedef priority_queue<ll, vector<ll>, greater<ll>> rpq;
constexpr ll INF = 1e9, MOD = 1e9 + 7, ohara = 1e6 + 10;
constexpr ll LINF = 1e18;

#define rep(i, n) for (ll(i) = 0; (i) < (int)(n); (i)++)
#define rrep(i, a, b) for (ll i = (a); i < (b); i++)
#define rrrep(i, a, b) for (ll i = (a); i >= (b); i--)
#define all(v) (v).begin(), (v).end()
#define Size(n) (n).size()
#define Cout(x) cout << (x) << endl
#define doublecout(a) cout << fixed << setprecision(15) << a << endl;
#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

//------ Believe yourself as a genius!!!!!! ------

int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
// int dy[]={-1,0,1,-1,1,-1,0,1};int dx[]={-1,-1,-1,0,0,1,1,1};
string alph("abcdefghijklmnopqrstuvwxyz"), s;
ll n, cnt, ans[ohara], a, b, c, d, tmp, m, h, w, x, y, sum, k, q;

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

  cin >> n;
  rrep(i, 1, 100 + 10) {
    rrep(j, 1, 110) {
      rrep(k, 1, 110) {
        cnt = i * i + j * j + k * k + i * j + j * k + i * k;
        if (cnt > n) continue;
        ans[cnt]++;
      }
    }
  }
  rep(i, n) Cout(ans[i + 1]);
  return 0;
}

Measured memory_bytes: 3624
from heapq import heappush, heappop
N, K, *L = map(int, open(0).read().split())
ls = []
for t,d in zip(*[iter(L)]*2):
  ls += [(d,t)]
used = []
cnt = [0]*(N+1)
hq = []
S = set()
ls.sort(reverse=True)
m = 0
for i in range(K):
  d,t = ls[i]
  cnt[t] += 1
  m += d
  if cnt[t]>1:
    used.append(d)
  S.add(t)
used.sort(reverse=True)
m += len(S)**2
for i in range(K,N):
  d,t = ls[i]
  if t not in S:
    heappush(hq,(-d,t))
ans = [m]
while used:
  d = used.pop()
  while hq:
    if hq[0][1] not in S:
      break
    heappop(hq)
  else:
    break
  m -= d
  n,s = heappop(hq)
  m += -n+2*len(S)+1
  ans.append(m)
  S.add(s)
print(max(ans))

Measured memory_bytes: 28096
package main

import (
	"container/list"
	"fmt"
)

func main() {
	var h, w int
	fmt.Scan(&h, &w)

	s := make([]string, h)
	ans := 0
	passed := make([][]bool, h)
	for i := range passed {
		passed[i] = make([]bool, w)
	}
	for i := range s {
		fmt.Scan(&s[i])
		for j, r := range s[i] {
			if r == '.' {
				ans++
				continue
			}
			passed[i][j] = true
		}
	}

	type point struct{ x, y, d int }
	ps := list.New()
	ps.PushBack(point{0, 0, 1})

	dx := [4]int{1, 0, -1, 0}
	dy := [4]int{0, 1, 0, -1}
	for {
		p := ps.Remove(ps.Front()).(point)
		if p.x == h-1 && p.y == w-1 {
			ans -= p.d
			break
		}

		for i := 0; i < 4; i++ {
			if nx, ny := p.x+dx[i], p.y+dy[i]; nx >= 0 && nx < h && ny >= 0 && ny < w && !passed[nx][ny] {
				ps.PushBack(point{nx, ny, p.d + 1})
				passed[nx][ny] = true
			}
		}

		if ps.Len() == 0 {
			fmt.Println(-1)
			return
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 768
n = int(input())
D = [int(d) for d in input().split()]
DD = []
S = [0] * n
for u in range(n):
	S[u] = D[u] ** 2
for s in range(n):
	for t in range(n):
		DD.append(D[s] * D[t])
for v in range(n):
	DD.remove(S[v])
print(int(sum(DD) / 2))


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

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        if (a % 2 == 1) {
            cout << "first" << endl;
            return 0;
        }
    }
    cout << "second" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define hell1 1e9+7
#define hell2 1e9+9
#define pi 3.1415926535
#define ms(s, n) memset(s, n, sizeof(s))
#define prec(n) fixed<<setprecision(n)
#define eps 0.000001
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define ll long long
#define ld long double 
#define no_of_digits(n) floor(log10(n)) + 1
#define see(x) cout << (#x) << " is " << (x) << endl
#define INF 1e9

using namespace std;

ll mult(ll a,ll b, ll p=hell1){   return ((a%p)*(b%p))%p; }
ll multbig(ll a,ll b,ll mod=hell1){   if(a==0 or b==0) return 0;if(a==1 or b==1) return (a*b)%mod;ll cur=multbig(a,b/2,mod);cur=(2*cur)%mod;if(b%2) cur=(cur+a)%mod;return cur;
}
ll add(ll a, ll b, ll p=hell1){ if(a>=p) a%=p; if(b>=p) b%=p; if(a+b>p) return (a + b)%p; else return a+b;}
ll sub(ll a, ll b, ll p=hell1){return (a%p - b%p + p)%p;}
ll fpow(ll n, ll k, ll p = hell1) {ll r = 1; for (; k; k >>= 1) {if (k & 1) r = mult(r,n,p); n = mult(n,n,p);} return r;}
ll inv(ll a, ll p = hell1) {return fpow(a, p - 2, p);}
ll inv_euclid(ll a, ll m = hell1){ll m0 = m;ll y = 0, x = 1;if (m == 1)return 0;while (a > 1){ll q = a / m;ll t = m;m = a % m, a = t;t = y;y = x - q * y;x = t;}if (x < 0)x += m0;return x;}
int isPowerof2(ll x) { return (x && !(x & x-1)); } 
ll log2(ll x) { ll res = 0; while (x >>= 1) res++; return res; } 

// max({a, b, c, d})

vector<ll>adj[200005];
ll update[200005];
ll ans[200005];

int binaryToDecimal(string n) 
{ 
    string num = n; 
    int dec_value = 0; 
  
    // Initializing base value to 1, i.e 2^0 
    int base = 1; 
  
    int len = num.length(); 
    for (int i = len - 1; i >= 0; i--) { 
        if (num[i] == '1') 
            dec_value += base; 
        base = base * 2; 
    } 
  
    return dec_value; 
} 

bool isPerfectSquare(long double x) 
{   
  // Find floating point value of  
  // square root of x. 
  long double sr = sqrt(x); 
  
  // If square root is an integer 
  return ((sr - floor(sr)) == 0); 
}

int main()
{
    int n;

    cin >> n;

    ll a[n+1];
    for(int i=1;i<=n;i++)
        cin >> a[i];

    ll dp[n+1]={0};

    // dp[0] = 0;
    dp[1] = 0;
    dp[2] = abs(a[2]-a[1]);

    for(int i=3;i<=n;i++)
    {
        dp[i] = min(dp[i-2]+abs(a[i]-a[i-2]), dp[i-1]+abs(a[i]-a[i-1]));
    }

    cout << dp[n] << "\n";
}




Measured memory_bytes: 7552
#include <stdio.h>
#include <math.h>
#define PI 3.14159265358979

int main(void){
	int step, deg;
	double x, y, angle;
	
	x = 0;
	y = 0;
	
	while(1){
		scanf("%d,%d", &step, &deg);
		if(step == 0 && deg ==0)	break;
		x = x + (double)step * sin(angle * (PI / 180));
		y = y + (double)step * cos(angle * (PI / 180));
		angle = angle + (double)deg;
	}
	
	printf("%d\n%d\n", (int)x, (int)y);
	
	return 0;
}

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

const int MAX_N = 90000;

struct P{
	int x,y;
}A[MAX_N+1];

int d[MAX_N+1];

int my_abs(int p){return p>0?p:-p;}

int main() {
	int H,W,D,a;
	scanf("%d %d %d",&H,&W,&D);
	int i,j;
	for(i=1;i<=H;i++)
		for(j=1;j<=W;j++){
			
			scanf("%d",&a);
			A[a].x = i; A[a].y = j;
		}
	int Q,n,m,sum = 0;
	scanf("%d ",&Q);
	
	for(i=D+1;i<=H*W;i++){
		d[i]=d[i-D]+my_abs(A[i].x-A[i-D].x)+my_abs(A[i].y-A[i-D].y);
	}
		
	
	
	for(i=0;i<Q;i++){
		scanf("%d %d",&n,&m);
		printf("%d\n",d[m]-d[n]);
	}
	
	return 0;
}

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

int main() {

	vector<int> v;
	int ans = 0;
	for(int i = 0; i < 5; i++) {
		int a;
		scanf("%d", &a);
		if(a % 10 == 0) {
			ans += a;
		}else {
			ans += a + (10 - a % 10);
			v.push_back(a);
		}
	}
	int mi = 10;
	for(int i = 0; i < (int)v.size(); i++) {
		int b = v[i] % 10; 
		mi = min(mi, b);
	}
	ans -= 10 - mi;
	printf("%d\n", ans);
}


Measured memory_bytes: 256
from operator import attrgetter
# Python3 code to find number of
# distinct numbers in a subarray
MAX = 6 * 10**5


# structure to store queries
class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx


# updating the bit array
def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx


# querying the bit array
def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):

    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of
    # any number as numbers of a[i]
    # are less than or equal to 10^6
    last_visit = [-1] * MAX

    # answer for each query
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the
        # idx equal to last_visit[arr[i]]
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

        # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer
        # for that query in ans[]
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                        query(queries[query_counter].r + 1, bit, n) - \
                        query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query
    for i in range(q):
        print(ans[i])


def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        queries.append(Query(l, r, i))
    queries.sort(key=attrgetter('r'))

    answeringQueries(c, n, queries, q)


if __name__ == "__main__":
    main()


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

using namespace std;

typedef long long ll;
typedef long double ld;

const int MX = 2007;

char a[MX][MX];
int lcp[MX][MX][2];
int gol[MX], gor[MX];
int main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int n, m;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%s", a[i]);
		for (int j = m; j >= 1; j--) {
			a[i][j] = a[i][j - 1];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			if (a[i][j] == a[i][j - 1]) {
				lcp[i][j][0] = lcp[i - 1][j][0] + 1;
			} else {
				lcp[i][j][1] = lcp[i - 1][j][1] + 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			lcp[i][j][0] = max(lcp[i][j][0], lcp[i][j][1]);
		}
	}
	int res = max(n, m);
	for (int it = 1; it <= 2; it++) {
		for (int i = 1; i <= n; i++) {
			vector<pair<int, int> > st;
			st.push_back(make_pair(1, -1));
			for (int j = 2; j <= m; j++) {
				while (!st.empty() && st.back().second >= lcp[i][j][0]) st.pop_back();
				gol[j] = st.back().first;
				st.push_back(make_pair(j, lcp[i][j][0]));
			}
			st.clear();
			st.push_back(make_pair(m + 1, -1));
			for (int j = m; j >= 1; j--) {
				while (!st.empty() && st.back().second >= lcp[i][j][0]) st.pop_back();
				gor[j] = st.back().first;
				st.push_back(make_pair(j, lcp[i][j][0]));
			}
			for (int j = 1; j <= m; j++) {
				res = max(res, lcp[i][j][0] * (gor[j] - gol[j]));
			}
		}
		for (int i = 1; i <= n; i++) {
			reverse(a[i] + 1, a[i] + 1 + m);
		}
	}
	printf("%d\n", res);
}



Measured memory_bytes: 35712
a = (gets).to_i
b = (gets).to_i
c = (gets).to_i
d = (gets).to_i
e = (gets).to_i
k = (gets).to_i

antenas = [a,b,c,d,e]

chk = true
antenas.combination(2) do |p,q|
    if (p-q).abs > k then
        chk = false
        break
    end
end

if chk then
    puts "Yay!"
else
    puts ":("
end

Measured memory_bytes: 1788
#include <iostream>

using namespace std;

int main()
{
    int x, y;
    
    do
    {
        cin  >> x >> y;
        
        if(x == 0 && y == 0)
            break;
            
        else if(x <= y)
            cout << x << ' ' << y << endl;
        
        else if(x >= y)
            cout << y << ' ' << x << endl;
        
        
    }while(true);

    return 0;
}

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

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 305;

int n, cnt[4];
double dp[N][N][N];

double solve(int a, int b, int c) {
    int s = a + b + c;
    if(s == 0)
        return 0;
    if(dp[a][b][c] != -1) return dp[a][b][c];
    double ans = (double)(n) / (double)(a + b + c), tempa = (double)(a) / (double)(s), tempb = (double)(b) / (double)(s), tempc = (double)(c) / (double)(s);
    dp[a][b][c] = 0;
    if(a > 0)
        dp[a][b][c] +=  tempa * (solve(a - 1, b, c) + ans);
    if(b > 0)
        dp[a][b][c] += tempb * (solve(a + 1, b - 1, c) + ans);
    if(c > 0)
        dp[a][b][c] += tempc * (solve(a, b + 1, c - 1) + ans);
    return dp[a][b][c];
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    cin >> n;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            for(int k = 0; k < N; k++)
                dp[i][j][k] = -1;
        }
    }
    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    cout << fixed << setprecision(10) << solve(cnt[1], cnt[2], cnt[3]);
}


Measured memory_bytes: 221952
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

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

const int MOD = 1e9 + 7;

inline int add(int x, int y){
	int res = x + y;	
	while(res >= MOD)res-=MOD;
	return res;
}

inline int mul(int x,int y){
	return (1LL * x * y) % MOD;
}

int modpow(int x,int p){
	int res = 1;
	while(p){
		if(p&1)gmul(res,x);
		gmul(x,x);
		p/=2;
	}
	return res;
}

inline int invert(int x){
	return modpow(x,MOD - 2);
}

const int N = 1e6;

int fac[N], inv[N];

void init(int n){
	fac[0] = inv[0] = 1;
	for(int i = 1;i < n; ++i){
		fac[i] = mul(fac[i-1], i);	
		inv[i] = invert(fac[i]); 
	}
}

int comb(int n,int k){
	return mul(fac[n],mul(inv[k], inv[n-k]));	
}

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n,a,b;
	cin >> n;
	if(n == 2){
		cout << 0 << '\n';
		return 0;
	}
	int ans = modpow(2,n);
	rep(cnt,0,2){
		cin >> a;
		int one = 1;
		rep(i,1,a+1){
			gmul(one,invert(i));
		}
		rep(i,n-a+1,n+1){
			gmul(one,i);
		}
		gadd(ans,MOD-one);
	}
	gadd(ans,MOD-1);
	cout << ans << '\n';
}


Measured memory_bytes: 256
#include <algorithm> //STLͨ���㷨
#include <cmath> //������ѧ����
#include <cstdio> //��������/�������
#include <iostream> //����������/���
#include <cstring> //�ַ�������
#include <string> //�ַ�����
#include <ctime> //�������ʱ��ĺ���
#define itn int
#define fro for
#define ll long long
#define reg register
#define inf 1234567890
#define rep(i,a,b,c) for (int i=a;i<=b;i+=c)
/*#include <bitset> //STLλ������
#include <cstype> //�ַ�����
#include <cerrno> //���������
#include <complex> //������
#include <clocale> //���屾�ػ�����
#include <cstdlib> //������������ڴ���亯��
#include <deque> //STL˫�˶�������
#include <exception> //�쳣������
#include <fstream> //�ļ�����/���
#include <functional> //STL�������㺯��(���������)
#include <limits> //�����������������ֵ����
#include <list> //STL�����б�����
#include <map> //STLӳ������
#include <iomanip> //����������/���
#include <ios> //��������/���֧��
#include <iosfwd> //����/���ϵͳʹ�õ�ǰ������
#include <istream> //����������
#include <ostream> //���������
#include <queue> //STL��������
#include <set> //STL��������
#include <sstream> //�����ַ�������
#include <stack> //STL��ջ����
#include <stdexcept> //��׼�쳣��
#include <streambuf> //�ײ�����/���֧��
#include <utility> //STLͨ��ģ����
#include <vector> //STL��̬��������
#include <cwchar.h>//���ַ�����������/���
#include <cwctype.h> //���ַ�����*/

using namespace std;

ll ans;

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

int abs(int x){return x>0?x:-x;}

int gcd(int x,int y){return (!y)?x:gcd(y,x%y);}

void exgcd(int a,int b,int &d,int &x,int &y){if (!b){d=a,x=1,y=0;}else{exgcd(b,a%b,d,y,x);y-=x*(a/b);}}

int quick_power(ll a,int b){ll r=1;for (;b;b>>=1,a=a*a)if (b&1) r=r*a;return r;}

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = x * 10 + (c ^ '0');
	if (iosig) x = -x;
}

char sr[10000000],z[20];int C=-1,Z=0;
void Ot(){fwrite(sr,1,C+1,stdout),C=-1;}
void print(int x){
	if (x<0) sr[++C]='-',x=-x;
    while(z[++Z]=x%10+48,x/=10);
    while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
//int find(int x){return fa[x]=fa[x]==x?x:find(fa[x]);}

//void add(int x,int y,int z){to[++cnt]=y;v[cnt]=z;Next[cnt]=head[x];head[x]=cnt;}

const int N=1001000;
ll D[N],M[N],DM[N];
string s;

int main()
{
	ios::sync_with_stdio(false);
	int n;
	cin>>n>>s;
	s=' '+s;
	for (int i=1;i<=n;i++)
	{
		D[i]=D[i-1];
		M[i]=M[i-1];
		DM[i]=DM[i-1];
		if (s[i]=='D') D[i]++;
		if (s[i]=='M') M[i]++,DM[i]+=D[i];
	}
	int T;
	cin>>T;
	while (T--)
	{
		int x;
		cin>>x;
		ans=0;
		for (int i=1;i<=n;i++)
		{
			if (s[i]=='C')
			{
				int j=max(0,i-x);
				ans+=DM[i]-DM[j]-D[j]*(M[i]-M[j]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}









Measured memory_bytes: 25928
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>

using namespace std;

string toOct(long long  d)
{
	char c[30];
	string s = "";
	
	sprintf(c, "%o", d);
	s += c;

	return s;
}


string solve(long long  n)
{
	char c[30];
	string s;

	s = toOct(n);

	for( int i = 0; i < (int)s.length(); i++)
	{
		if( s[i] >= '4' )
			s[i] += '1' - '0';

		if( s[i] >= '6' )
			s[i] += '1' - '0';
	}

	return s;
}


int main()
{
	long long n;

	while( cin >> n, n)
	{
		cout << solve(n) << endl;
	}

	return 0;
}

Measured memory_bytes: 944
#include<cstdio>
#include<stack>
using namespace std;

int main(){
	int n;
	stack<int> st;
	while( scanf("%d", &n) != EOF ){
		if( n == 0 ){
			printf("%d\n", st.top() );
			st.pop();
		}else{
			st.push(n);
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define _USE_MATH_DEFINES
#include <math.h>
#include <iomanip>
#include <stdio.h>
#include <numeric>
#include <cmath>
#include <limits>
#include <bitset> 
#include <iterator> 
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;

int main()
{
	ll n,cnt=0,ans=0;
	cin >> n;
	vector<string>s(n);
	for (int i = 0; i < n; i++)cin >> s[i];

	for (int i = 0; i < n; i++) {
		sort(s[i].begin(), s[i].end());
	}
	sort(s.begin(), s.end());
	s.push_back("#");
	for (int i = 0; i < n; i++) {
		cnt++;
		if (s[i] != s[i + 1]) {
			ans += cnt * (cnt - 1) / 2;
			cnt = 0;
		}
	}
	cout << ans << endl;
}

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


int main() {
    int n, a, b;
    cin >> n >> a >> b;
    cout << min(n * a, b) << endl;
}


Measured memory_bytes: 3608
import java.util.*;
import java.math.*;

public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        long[] a = new long[1000001];
        for(int i = 1; i <= 9; i++){
        	a[i] = i;
        }
        int cnt = 10;
        int x = 0;
        for(int i = 1; i <= 9; i++){
    		long d = a[i]%10;
    		if(d == 0){
    			a[cnt++] = a[i]*10;
    			a[cnt++] = a[i]*10+1;
    			x+=2;
    		}
    		else if(d==9){
    			a[cnt++] = a[i]*10+8;
    			a[cnt++] = a[i]*10+9;
    			x+=2;
    		}
    		else{
    			a[cnt++] = a[i]*10+d-1;
    			a[cnt++] = a[i]*10+d;
    			a[cnt++] = a[i]*10+d+1;
    			x+=3;
    		}
    	}
        int l = 10,r = 10+x;
        x = 0;
        for(int i = l; i <= r; i++){
        	long d = a[i]%10;
    		if(d == 0){
    			a[cnt++] = a[i]*10;
    			a[cnt++] = a[i]*10+1;
    			x+=2;
    		}
    		else if(d==9){
    			a[cnt++] = a[i]*10+8;
    			a[cnt++] = a[i]*10+9;
    			x+=2;
    		}
    		else{
    			a[cnt++] = a[i]*10+d-1;
    			a[cnt++] = a[i]*10+d;
    			a[cnt++] = a[i]*10+d+1;
    			x+=3;
    		}
        }
        for(int k = 1; k <= 7; k++){
        	l = r+1;
            r = l+x;
            x = 0;
            for(int i = l; i <= r; i++){
            	long d = a[i]%10;
        		if(d == 0){
        			a[cnt++] = a[i]*10;
        			a[cnt++] = a[i]*10+1;
        			x+=2;
        		}
        		else if(d==9){
        			a[cnt++] = a[i]*10+8;
        			a[cnt++] = a[i]*10+9;
        			x+=2;
        		}
        		else{
        			a[cnt++] = a[i]*10+d-1;
        			a[cnt++] = a[i]*10+d;
        			a[cnt++] = a[i]*10+d+1;
        			x+=3;
        		}
            }
        }
        int n = cin.nextInt();
        System.out.println(a[n]);
    }
}




Measured memory_bytes: 32084
S = input() + 'R'

ans = [0] * len(S)

cur = 'R'
cur_i = 0
points = []


for i in range(len(S)):
    if cur != S[i]:
        if S[i] == 'L':
            diff = i - cur_i
            if diff % 2 == 0:
                ans[i-1] += int(diff/2)
                ans[i] += int(diff/2)
            else:
                ans[i-1] += int((diff+1)/2)
                ans[i] += int((diff-1)/2)

            cur_i = i
            cur = 'L'

        if S[i] == 'R':
            diff = i - cur_i
            if diff % 2 == 0:
                ans[cur_i-1] += int(diff/2)
                ans[cur_i] += int(diff/2)
            else:
                ans[cur_i-1] += int((diff-1)/2)
                ans[cur_i] += int((diff+1)/2)

            cur_i = i
            cur = 'R'


print(*ans[:-1])


Measured memory_bytes: 6376
//////////////////////////////
// Author: whatisit
// Date: 2020-05-14 01:32 
//////////////////////////////
#include <bits/stdc++.h>
using namespace std;

int k, n, a, cur_max, first;
void solve() {
	cin >> k >> n;
	int prev;
	cin >> prev;
	first = prev;
	for (int i = 2; i <= n; ++i) {
		cin >> a;
		cur_max = max(cur_max, a - prev);
		prev = a;
	}
	cur_max = max(cur_max, first + (k - prev));
	cout << k - cur_max;
}

int main() {
	//cin.tie(0); ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;

int main() {
    int n;
    cin >> n;
    int a[n];
    rep(i, n) {
        cin >> a[i];
        a[i]--;
    }

    int button = 0;
    int cnt = 0;
    rep(i, n) {
        button = a[button];
        cnt++;
        if(button == 1) {
            cout << cnt << endl;
            return 0;
        }
    }

    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <climits>
#include <string>
#include <bitset>
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define fin(ans) cout<<(ans)<<endl
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p,q)
#define pb(n) push_back(n)
#define Sort(a) sort(a.begin(),a.end())
#define Rort(a) sort(a.rbegin(),a.rend())
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
const int P = 1000000007;
const int INF = INT_MAX;
const long long LLINF = 1LL<<60;
//g++ -std=c++1z main.cpp
//.\a.exe

int main(void){ios::sync_with_stdio(false);cin.tie(0);
////////////////////////////////////////////////////////
int a;
double n;
cin >> n;
a=(n+1)/2;
cout << a/n << endl;
////////////////////////////////////////////////////////
return 0;}

Measured memory_bytes: 256
/**
 * There is a start and there is no end in the space. ---Infinilly.
 * It ruins and goes though there is also a start in stars. ---Finite.
 * Only the man who has wisdom can read the most foolish one from the history.
 * Fishes living in the sea doesn't know the life in the land.
 * It also ruins and goes if they have wisdom.
 * It funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */

#include <bits/stdc++.h>

const int N = 100010, MO = 1e9 + 7;

char str[N];
int bin[26];

int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", str);
    for(int i = 0; i < n; i++) {
        bin[str[i] - 'a']++;
    }
    int ans = 1;
    for(int i = 0; i < 26; i++) {
        ans = 1ll * ans * (bin[i] + 1) % MO;
    }
    printf("%d", (ans + MO - 1) % MO);

    return 0;
}


Measured memory_bytes: 384
# 全ての約数を列挙。o(√N)。
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

n = int(input())
ans = float('inf')
for i in make_divisors(n):
    j = n//i
    temp = i + j - 2
    ans = min(ans, temp)
print(ans)

Measured memory_bytes: 3268
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);++i)

using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100000000;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main(){
  int N,M;
  cin >> N >> M;
  vector<int> nodes(N);
  vector<P> branches(M);
  rep(i,N){
    nodes[i] = i;
  }
  rep(i,M){
    int x,y;
    cin >> x >> y;
    x--;y--;
    branches[i].first=x;
    branches[i].second=y;
  }
  int paths=0;    
  do{
    if(nodes[0]!=0)break;
    /*rep(i,N){
        cout << nodes[i] << " ";
    }*/
    int road=0;
    rep(i,N-1){
      rep(j,M){
        int a=nodes[i];
        int b=nodes[i+1];
        if(a>b){
          swap(a,b);
        }
        if(a==branches[j].first && b==branches[j].second){
          road++;
        }
      }
    }
    if(road==N-1){
      paths++;
      /*rep(i,N){
        cout << nodes[i] << " ";
      }*/
      //cout << endl;
    }
  }while(next_permutation(nodes.begin(),nodes.end()));
  cout << paths << endl;

  return 0;
}

Measured memory_bytes: 256
from string import ascii_lowercase
from functools import lru_cache
n = int(input())

@lru_cache(maxsize=10)
def make(n):
    if n == 1:
        return ['a']
    else:
        lst = []
        for s in make(n-1):
            for c in ascii_lowercase[:len(set(s))+1]:
                lst.append(s + c)
        return lst
for s in make(n):
    print(*s, sep='')

Measured memory_bytes: 16520
func main(text1: String = readLine()!, text2: String = readLine()!) {
    let text2Indices = text2.indices
    let text2Count = text2.count
    var searchText1 = text1
    searchText1.removeLast(text2Count - 1)
    var result = text2Count
    for text1Index in searchText1.indices {
        var difference = 0
        for (i, j) in zip(text1[text1Index...].indices, text2Indices) where text1[i] != text2[j] {
            difference += 1
        }
        if result > difference {
            result = difference
        }
    }
    print(result)
}

main()

Measured memory_bytes: 7780
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144 * 4LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

void init() {
    iostream::sync_with_stdio(false);
    cout << fixed << setprecision(20);
}


#define int ll

unsigned long xor128() {
    static unsigned long x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned long t = (x ^ (x << 11));
    x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void solve() {
    int n, t;
    cin >> n >> t;
    vector<int> zero;
    vector<pair<long double,pair<int, int>>> others;
    REP(i, n) {
        int a, b;
        cin >> a >> b;
        if (a == 0) {
            zero.push_back(b + 1);
        }
        else {
            long double hoge = (long double)a / (long double)(b + 1);
            b = a + b + 1;
            a++;
            others.push_back(make_pair(hoge,make_pair(a,b)));
            
        }
    }
    sort(ALL(zero));
    sort(ALL(others));
    int napsack[50] = {};
    REP(i, 50) {
        napsack[i] = t + 1;
    }
    napsack[0] = 0;
    reverse(ALL(others));
    REP(i, others.size()) {
        for (int q = 40; q >= 0; --q) {
            if (napsack[q] == t + 1) continue;
            int next = napsack[q];
            next *= others[i].second.first;
            next += others[i].second.second;
            napsack[q + 1] = min(napsack[q + 1], next);
        }
    }

    int goi = 0;
    REP(q, 40) {
        int now = napsack[q];
        if (now > t) continue;
        int ans = q;
        for (int q = 0; q < zero.size(); ++q) {
            now += zero[q];
            if (now <= t) ans++;
        }
        goi = max(goi, ans);
    }
    cout << goi << endl;
}

#undef int
int main() {
    init();
    solve();
}


Measured memory_bytes: 10604
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	sc.Split(bufio.ScanWords)

	X := nextInt()

	t := 0
	pos := 0
	for pos < X {
		t++
		pos = t * (t + 1) / 2
	}

	fmt.Println(t)

}


Measured memory_bytes: 640
# -*- coding: utf-8 -*-
 
N = input()

sum_digit = 0
for i in range( len(N) ):
  temp = N[i]
  #print(temp)
  sum_digit += int(temp)

#print(sum_digit)
if ( sum_digit % 9 == 0 ):
  print('Yes')
else:
  print('No')

Measured memory_bytes: 9276
import numpy as np

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

'''
以下、方針
・Aから、各要素の出現回数を取得する。
・出現回数から、組み合わせを計算する。
'''
unique_num, counts =np.unique(A,return_counts=True) #Aから、各要素の出現回数を取得する。

# print(unique_num)
# print(counts)
dic0={} #数字と出現回数の組合わせ辞書
dic1={} #数字と組合わせ個数の組合わせ辞書
dic2={} #回答用の辞書

Combination_pattern = []
for i in range(len(counts)):
    Combination = counts[i] * (counts[i]-1) // 2 #出現回数から、組み合わせを計算する。
    dic0[unique_num[i]]=counts[i]
    dic1[unique_num[i]]=Combination
    dic2.setdefault(unique_num[i])
    Combination_pattern.append(Combination)

totalcombination=sum(Combination_pattern)

# print(dic0)
# print(dic1)
# print(dic2)
# print(Combination_pattern)

'''
以下方針
・Aから数字を取得
・その数字の出現回数を1減らした状態の組み合わせの数を調べる。
・その数字に対応する元の組み合わせの数を減らし、1個前で計算した組合わせを足す。
・同じ数字を引いたときように答えを辞書に登録しておく。
・もし、過去に同じ数字を引いていたら、登録しておいた答えを回答する。
'''

for j in range (N):
    n=A[j] #Aから数字を取得
    if dic2[n]==None:
        reduced_pattern = (dic0[n]-1) * (dic0[n]-2) // 2 #その数字の出現回数を1減らした状態の組み合わせの数を調べる。
        ans=totalcombination-dic1[n]+reduced_pattern #その数字に対応する元の組み合わせの数を減らし、1個前で計算した組合わせを足す。
        dic2[n] = ans #同じ数字を引いたときように答えを辞書に登録しておく。
        print(ans)
    else:
        print(dic2[n]) #もし、過去に同じ数字を引いていたら、登録しておいた答えを回答する。

Measured memory_bytes: 76536
#include <stdio.h>

int main(void){
    int i, n;
    char *ans = "No";
    scanf("%d", &n);
    for(i = 1; i < 10; ++i){
        if(n % i == 0 && n / i <= 9){
            ans = "Yes";
            break;
        }
    }
    printf("%s\n", ans);
    return 0;
}

Measured memory_bytes: 128
package main

import (
        "fmt"
)

func solution(a, b, c, k int) int {
        if k&1 == 0 {
                return a - b
        } else {
                return b - a
        }
}

func main() {
        var a, b, c, k int
        fmt.Scan(&a, &b, &c, &k)
        fmt.Println(solution(a, b, c, k))
}

Measured memory_bytes: 512
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
#define vint vector<int>
#define vll vector<ll>
typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int from, to, cost; };
struct gNode { int from, to, cost; };
struct tNode { int value; int parent; vector<int> child; };

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

int gcd(int a, int b){ return a % b == 0 ? b : gcd(b, a%b); }
int lcm(int a, int b){ return a * b/ gcd(a, b); }
int extgcd(int a, int b, int& x, int& y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}
ll mod_pow(ll x, ll n){
	if(n == 0) return 1;
	ll res = mod_pow(x*x % MOD, n/2);
	if(n & 1) res = res * x % MOD;
	return res;
}

int main(void){
	int n; cin >> n;
	vector<vint> a(n);
	rep(i, n) a[i].resize(n-1);
	rep(i, n){
		rep(j, n-1){
			cin >> a[i][j];
			a[i][j]--;
		}
		reverse(a[i].begin(), a[i].end());
	}

	vector<int> prev_changed;
	rep(i, n) prev_changed.push_back(i);
	vector<int> can_game;
	vector<bool> flag(n);
	ll ans = 0;
	while(1){
		fill(flag.begin(), flag.end(), false);
		while(!prev_changed.empty()){
			int i = prev_changed[prev_changed.size()-1];
			prev_changed.pop_back();
			if(a[i].size() == 0) continue;
			if(flag[i]) continue;
			int opponent = a[i][a[i].size()-1];
			if(a[opponent][a[opponent].size()-1] == i){
				flag[i] = true;
				flag[opponent] = true;
				can_game.push_back(i);
				can_game.push_back(opponent);
			}
		}
		bool can = false;
		while(!can_game.empty()){
			int i = can_game[can_game.size()-1];
			can_game.pop_back();
			a[i].pop_back();
			prev_changed.push_back(i);
			can = true;
		}
		if(!can) break;
		ans++;
	}

	rep(i, n){
		if(!a[i].empty()){
			cout << -1 << endl;
			return 0;
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 4224
def solve():
    n = read()
    result = think(n)
    write(result)


def read():
    return read_int(1)[0]


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(n):
    return (n * (n - 1)) // 2


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 38484
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    string s;
    cin >> n >> s;
    vector<int> l(n+1);
    vector<int> r(n+1);
    for(int i = 0; i < n; i++)
    {
        l[i+1] = l[i];
        if(s[i] == '#')
        {
            l[i+1]++;
        }
    }
    for(int i = 0; i < n; i++)
    {
        r[i+1] = r[i];
        if(s[n-i-1] == '.')
        {
            r[i+1]++;
        }
    }
    int ans = 1e9;
    for(int i = 0; i <= n; i++)
    {
        ans = min(ans, l[i] + r[n-i]);
    }
    cout << ans << endl;
}


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

const int N = 1e5 + 7;
ll a[N];
int n;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
	}
	ll ans1 = 2, ans2 = 2;
	for (int i = n; i >= 1; i--) {
		ans1 = (ans1 - 1) / a[i] + 1, ans2 = ans2 / a[i];
		if (ans1 > ans2) {
			puts("-1");
			return 0;
		}
		ans1 *= a[i];
		ans2 = ans2 * a[i] + a[i] - 1;
	}
	printf("%lld %lld\n", ans1, ans2);
	return 0;
}

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

using namespace std;

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

typedef complex<double> P;
typedef vector<P> Polygon;

double const EPS = 1e-7;
double const inf = 1e10;

struct Line : public vector<P>
{
  Line() {}
  Line(P const& a, P const& b) {
    push_back(a), push_back(b);
  }
  P vectorize() { return (*this)[1]-(*this)[0]; }
  double length() { return abs((*this)[1]-(*this)[0]); }
};

inline double dot(P const& a, P const& b) { return real(conj(a)*b); }
inline double cross(P const& a, P const& b) { return imag(conj(a)*b); }

enum { counter_clockwise = +1, clockwise = -1, cab_online = +2, abc_online = -2, on_segment = 0 };
int ccw(P a, P b, P c) {
  b -= a, c -= a;
  if(cross(b, c) > 0) return counter_clockwise;
  if(cross(b, c) < 0) return clockwise;
  if(dot(b, c) < 0) return cab_online;
  if(norm(b) < norm(c)) return abc_online;
  return on_segment;
}

typedef Line Segment;


P crosspoint(Line const& l, Line const& m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  if(abs(A) < EPS && abs(B) < EPS) { return m[0]; } // same line
  if(abs(A) < EPS) { return P(inf, inf); }
  return m[0] + B / A * (m[1]-m[0]);
}

// Notice: Return left part of the polygon.
Polygon convex_cut(Polygon const& G, Line const& l) {
  Polygon left_part;
  rep(i, G.size()) {
    P const& a = G[i], b = G[(i+1)%G.size()];
    Line const& ab = Line(a, b);
    if(ccw(l[0], l[1], a) != clockwise) { left_part.push_back(a); }
    if(ccw(l[0], l[1], a) * ccw(l[0], l[1], b) < 0) {
      P r = crosspoint(ab, l);
      if(r == P(inf, inf)) { continue; }
      left_part.push_back(r);
    }
  }
  return left_part;
}

// Notice: The border of the polygon in counterclockwise order.
bool able_polygon(Polygon const& G, double x) {
  int N = G.size();
  Polygon A = {{-inf, -inf}, {inf, -inf}, {inf, inf}, {-inf, inf}};
  rep(i, N) {
    Line ln(G[i], G[(i+1)%N]);
    P shift = ln.vectorize()*polar(x, M_PI/2.) / ln.length();
    A = convex_cut(A, Line(G[i] + shift, G[(i+1)%G.size()] + shift));
  }
  return !A.empty();
}

double solve(Polygon const& G) {
  double L = 0., R = inf;
  rep(loop, 1000) {
    double M = (L+R) / 2.;
    if(able_polygon(G, M)) { L = M; }
    else { R = M; }
  }
  return L;
}

int main() {
  
  int N;
  while(cin >> N && N) {
    Polygon G(N);
    rep(i, N) {
      double x, y; cin >> x >> y;
      G[i] = P(x, y);
    }
    printf("%.8f\n", solve(G));
  }
  return 0;
}

Measured memory_bytes: 1272
#include <bits/stdc++.h>
#define ALL(v) v.begin(), v.end()
#define MOD 1000000007
#define INF 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define req(i, j, n) for(int i = j; i <= (int)(n); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
  ll n,k;
  cin>>n>>k;
  ll hp[n+1];
  for(int i=1;i<=n;i++){
    cin>>hp[i];}
  
  sort(hp+1, hp+n+1, greater<ll>());
  
  if(k>=n){
    cout<<0<<endl;
    return 0;}
  
 ll ans=0;
  for(int i=k+1;i<=n;i++){
    ans+=hp[i];}
  
  cout<<ans<<endl;
  
  
  
  


}

Measured memory_bytes: 1792
package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

//  長い入力を読む
func ReadLongLines(times int) ([]string, error) {
	result := make([]string, times)
	reader := bufio.NewReader(os.Stdin)
	buffer := bytes.NewBuffer(make([]byte, 0))
	readBytes := int64(2)
	for i := 0; i < times; i++ {
		for {
			readBuf, isPrefix, err := reader.ReadLine()
			// fmt.Printf("Reader.Read: %d\n", len(readBuf))
			readBytes += int64(len(readBuf) + 1)
			if err != nil {
				if err == io.EOF {
					fmt.Println("EOF")
					break
				} else {
					return result, err
				}
			}
			_, err = buffer.Write(readBuf)
			if err != nil {
				return result, err
			}
			// end of line
			if !isPrefix {
				result[i] = buffer.String()
				buffer.Reset()
				// reader = bufio.NewReader(os.Stdin)
				break
			}
		}
	}
	// 先読みしてしまうようなので、戻しておく
	os.Stdin.Seek(-int64(reader.Buffered()), os.SEEK_CUR)
	return result, nil
}

// 出力 for 競プロ
type Console struct {
	writer *bufio.Writer
}

func NewConsole() Console {
	return Console{bufio.NewWriter(os.Stdout)}
}
func (this *Console) Printf(format string, a ...interface{}) {
	fmt.Fprintf(this.writer, format, a...)
}
func (this *Console) Println(s string) {
	fmt.Fprintln(this.writer, s)
}
func (this *Console) Close() {
	this.Flush()
}
func (this Console) Flush() {
	this.writer.Flush()
}

func PrintList(list []int) {
	con := NewConsole()
	defer con.Flush()
	for i := range list {
		if i == 0 {
			con.Printf("%d", list[i])
		} else {
			con.Printf(" %d", list[i])
		}
	}
	con.Println("")
}


type Element struct {
	value int
	parent *Element
}

func (this *Element) Root() *Element {
	if this.parent == this {
		return this
	} else {
		return this.parent.Root()
	}
}

func Unite(lhs *Element, rhs *Element) {
	r := rhs.Root()
	r.parent = lhs.Root()
}

func Same(lhs *Element, rhs *Element) bool {
	return lhs.Root() == rhs.Root()
}

func main() {
	con := NewConsole()
	defer con.Close()

	var n int
	fmt.Scanf("%d", &n)

	list := make([]Element, n)
	for i := 0; i < n; i++ {
		e := Element{i, nil}
		e.parent = &e
		list[i] = e
	}


	var q int
	fmt.Scanf("%d", &q)
	lines, _ := ReadLongLines(q)
	for i := 0; i < q; i++ {
		args := strings.Split(lines[i], " ")
		command := args[0]
		lhs, _ := strconv.Atoi(args[1])
		rhs, _ := strconv.Atoi(args[2])
		switch command {
		case "0":
			Unite(&list[lhs], &list[rhs])
		case "1":
			areSame := Same(&list[lhs], &list[rhs])
			if areSame {
				con.Println("1")
			} else {
				con.Println("0")
			}
		}
	} 
}



Measured memory_bytes: 8700