akhauriyash/Code-Regression huggingface dataset:
import copy
from itertools import product, combinations

N = int(input())

dp = []
for _ in range(N):
    dp.append(list(map(int, input().split(' '))))

original = copy.deepcopy(dp)

for k, i, j in product(range(N), repeat=3):
    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

if dp == original:
    cost = 0
    for i in range(N):
        for j in range(i + 1, N):
            for k in range(N):
                if k == i or k == j:
                    continue
                if dp[i][j] == dp[i][k] + dp[k][j]:
                    break
            else:
                cost += dp[i][j]
    print(cost)
else:
    print(-1)


Measured memory_bytes: 56544
import itertools
n = int(input())
a = list(map(int,input().split()))
g = itertools.groupby(sorted(a))
for i,(k,v) in enumerate(g):
    if n%2==1:
        f1 = i==0 and k==0 and len(list(v))==1
        f2 = i!=0 and k==i*2 and len(list(v))==2
        if not (f1 or f2):
            print(0)
            exit()
    else:
        if k!=2*i+1 or len(list(v))!=2:
            print(0)
            exit()
print((2**(n//2))%(10**9+7))


Measured memory_bytes: 14260
N,M = map(int,input().split())
ab = []
pre = 0
ans = 0
for _ in range(M):
    a,b = map(int,input().split())
    ab.append([a-1,b-1])
ab = sorted(ab, key=lambda x: x[1])
for i in ab:
    if i[0] >= pre:
        ans +=1
        pre = i[1]
print(ans)


Measured memory_bytes: 22108
#include <iostream>
#include <cctype>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <string>
#include <functional>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
typedef long long ll;
const int INF = 100000000, mod = 1000000007;
const ll LLINF = 1LL << 50;
using namespace std;

int main() {
    int n, a[2][100], t = 0, maxc;
    cin >> n;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            if (i == 1 && j != n - 1) t += a[i][j];
        }
    }
    maxc = t;
    for (int i = 0; i < n-1; i++) {
        t -= a[1][i];
        t += a[0][i + 1];
        maxc = max(maxc, t);
    }
    cout << maxc + a[0][0] + a[1][n - 1] << endl;
    return 0;
}

Measured memory_bytes: 256
n,m = map(int,input().split())
divisors = []
for i in range(1,int(m**0.5)+1):
    if m % i == 0:
        divisors.append(i)
        divisors.append(m//i)
divisors.sort()
k = 0
for i in range(len(divisors)):
    if divisors[i] > m/n:
        k = i - 1
        break
    if i == len(divisors) - 1:
        k = len(divisors) - 1
print(divisors[k])

Measured memory_bytes: 3064
q=[]
qq=[]
def dfs(j,q,icnt,count,n,qq):
    if len(qq)==n:
        count+=1
#        print("1",n,j,icnt,count,q[j],qq)
        return count
    icnt+=1
    
    for j2 in q[j]:
        if not j2 in qq:
            qq.append(j2)
#            print("2",n,j,icnt,count,q[j],qq)
            count=dfs(j2,q,icnt,count,n,qq)
            qq.pop()
#        print("3",n,j,icnt,count,q[j],qq)
    return count

n,m=map(int,input().split())
ab=[[0]*2 for i in range(m)]
for i in range(m):
    ab[i]=list(map(int,input().split()))

#n=3
#m=3
#ab=[[1,2],[1,3],[2,3]]

#n=7
#m=7
#ab=[[1,3],[2,7],[3,4],[4,5],[4,6],[5,6],[6,7]]

q=[[]*2 for i in range(n)]
for i in range(m):
    if not q[ab[i][1]-1] in q[ab[i][0]-1]:
        q[ab[i][0]-1].append(ab[i][1]-1)    
    if not q[ab[i][0]-1] in q[ab[i][1]-1]:
        q[ab[i][1]-1].append(ab[i][0]-1)    
#print(q)    

count=0
j=0
qq=[j]
icnt=1
count=dfs(j,q,icnt,count,n,qq)
print(count)

Measured memory_bytes: 3064
L,R = map(int,input().split(" "))
min = 1000000000000
if (R-L >= 2019):
    print("0")
    quit()
for i in range(L%2019,R%2019 + 1):
  for j in range(i+1, R%2019 + 1):
    tmp = (i * j)%2019
    if min > tmp:
      min = tmp
print(min)


Measured memory_bytes: 2940
def euclid(a, b):
    global l
    if b == 0:
        return a
    else:
        ch = l[a][b]
        if ch == 0:
            return euclid(b, a%b)
        else:
            return ch

def gcd(a, b, c):
    global l
    d = l[c][b]
    if d == 0:
        d = euclid(c, b)
        l[c][b] = d

    e = l[max(d, a)][min(d, a)]
    if e == 0:
        e = euclid(max(d, a), min(d, a))
        l[max(d, a)][min(d, a)] = e

    return e

K = int(input())
ans = 0
l = []
for i in range(K+1):
    l.append([0]*(K+1))

for i in range(1, K+1):
    for j in range(i, K+1):
        for k in range(j, K+1):
            num = gcd(i, j, k)
            if i == j:
                if j == k:
                    ans += num
                else:
                    ans += 3*num
            else:
                if j == k:
                    ans += 3*num
                else:
                    ans += 6*num

print(ans)

Measured memory_bytes: 9540
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef pair<int,int> pii;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
template<class Type> void line(const Type &a){int cnt=0;for(auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

int main(){
	int n;
	cin>>n;
	
	vector<string> s(n);
	vi t(n);
	REP(i,n) cin>>s[i]>>t[i];
	
	string x;
	cin>>x;
	
	int sum=0;
	bool flag=false;
	REP(i,n){
		if(flag){
			sum+=t[i];
		}else{
			if(s[i]==x) flag=true;
		}
	}
	
	cout<<sum<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstdlib>
#include<utility>
using namespace std;

int main(){
	int n, m;
	int a[100100];
	int b[100100];
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i];
	}
	cin >> m;
	for(int i=0; i<m; i++){
		cin >> b[i];
	}

	int cnt = 0;
	for(int i=0; i<m; i++){
		int lb = 0;
		int ub = n;

		for(;;){
			if(lb+1>=ub) break;
			int mid = (lb+ub)/2;
			if(a[mid]>b[i]){
				ub = mid;
			}else if(a[mid]<=b[i]){
				lb = mid;
			}
		}

		if(a[lb]==b[i]) cnt++;
	}
	cout << cnt << endl;
	return 0;
}

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

int main(){
	int i, j, num_problems, num_submission;
	int num_AC=0, num_penalty_sum=0;
	
	cin >> num_problems >> num_submission;
	vector<int> num_problem_challenged(num_submission);
	vector<string> results(num_submission);
	
	for(i=0;i<num_submission;i++){
		cin >> num_problem_challenged.at(i)
		>> results.at(i);
	}
	
	// AC問題数の計算
	// ACにならなかった問題番号の初期化
	vector<int> num_problem_notAC(num_problems);
	for(i=0;i<num_problems;i++){
		num_problem_notAC.at(i) = i+1;
	}
	
	// 各問題のACになるまでのペナルティ数の初期化
	vector<int> num_penalty(num_problems);
	for(i=0;i<num_problems;i++){
		num_penalty.at(i) = 0;
	}
	
	for(i=0;i<num_submission;i++){
		// もしACだった場合，該当する問題番号に0を上書きする．
		if(results.at(i)=="AC"){
			num_problem_notAC.at(num_problem_challenged.at(i)-1)=0;
			
		// もしWAかつまだACが出てない場合，該当する問題番号に対するペナルティを加算
		}else if(num_problem_notAC.at(num_problem_challenged.at(i)-1)!=0){
			num_penalty.at(num_problem_challenged.at(i)-1)++;
		}
	}
	
	// 0の数がAC問題の数
	vector<int> num_problem_penalty(0);
	for(i=0;i<num_problems;i++){
		if(num_problem_notAC.at(i)==0){
			num_AC++;
		}
	}
	
	// 各問題におけるペナルティ数の合計を計算
	for(i=0;i<num_problems;i++){
		// 一度以上ACが出てる問題のみ総ペナルティ数に加算
		if(num_problem_notAC.at(i)==0){
			num_penalty_sum += num_penalty.at(i);
		}
	}
	
	
	cout << num_AC << " " << num_penalty_sum << endl;
	
	return 0;
}

Measured memory_bytes: 6912
#include <algorithm>
#include <climits>
#include <cmath>
#include <csignal>
#include <cstdio>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>

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

constexpr long long mod = 1e9 + 7;

long long inv(long long n) {
    long long res = 1;
    while (n > 1) {
        res *= (mod - mod/n);
        res %= mod;
        n = mod % n;
    }
    return res;
}

long long comb_mod(long long n, long long r) {
    long long nume = 1;
    long long deno = 1;
    long long r_buf = (r <= n/2) ? r : n-r;
    for (long long i=1; i<=r_buf; i++) {
        deno *= i % mod;
        deno %= mod;
    }
    for (long long i=n-r_buf+1; i<=n; i++) {
        nume *= i % mod;
        nume %= mod;
    }
    deno = inv(deno);
    return (deno * nume) % mod;
}
 
int main() {
    ll x = 0, y = 0;
    cin >> x >> y;
    if ((2*x-y)%3 != 0 || (2*y-x)%3 != 0 || 2*x-y < 0 || 2*y-x < 0) {
        cout << 0 << endl;
    } else {
        ll a = (2*x-y)/3, b = (2*y-x)/3;
        cout << comb_mod(a+b, a) << endl;
    }
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <map>
#include <numeric>
using namespace std;
typedef long long ll;
ll mod=998244353;

int main(){
    ll n;cin>>n;
    vector<pair<ll,ll> > a(n),b(n);
    vector<int> c(n);
    for(int i=0;i<n;i++)cin>>a[i].first,a[i].second=i;
    for(int i=0;i<n;i++)cin>>b[i].first,b[i].second=i;
    sort(a.begin(),a.end());
    sort(b.begin(),b.end());
    for(int i=0;i<n;i++)if(a[i].first>b[i].first){cout<<"No";return 0;}
    bool ok=0;
    for(int i=0;i<n-1;i++)if(a[i+1].first<=b[i].first){cout<<"Yes";return 0;}
    if(ok)cout<<"Yes";
    else {
        int len=0,cur=0;
        for(int i=0;i<n;i++)c[a[i].second]=b[i].second;
        do{
            len++;
            cur=c[cur];
        }while(cur);
        if(len==n)cout<<"No";
        else cout<<"Yes";
    }

}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
#define MAXN	100005
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
int n, a[MAXN];
int gcd(int x, int y) {
	if (y == 0) return x;
	else return gcd(y, x % y);
}
bool work() {
	int cnt = 0;
	for (int i = 1; i <= n; i++)
		cnt += (a[i] & 1) ^ 1;
	if (cnt & 1) return true;
	if (cnt != n - 1) return false;
	for (int i = 1; i <= n; i++)
		if (a[i] % 2 != 0) {
			a[i]--;
			if (a[i] == 0) return false;
		}
	int g = a[1];
	for (int i = 2; i <= n; i++)
		g = gcd(g, a[i]);
	for (int i = 1; i <= n; i++)
		a[i] /= g;
	return !work();
}
bool check(int x, int y) {
	if ((x + y) % 2) return true;
	else return false;
}
int main() {
	read(n);
	if (n == 1) {
		printf("Second\n");
		return 0;
	}
	for (int i = 1; i <= n; i++)
		read(a[i]);
	if (n == 2) {
		if (check(a[1], a[2])) printf("First\n");
		else printf("Second\n");
		return 0;
	}
	if (work()) printf("First\n");
	else printf("Second\n");
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
long long mo = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

ll X[3];
ll Y[3];

int main(){
    ll S;
    cin >> S;
    X[1] = 1;
    Y[1] = 1e9;
    X[2] = (S+ll(1e9)-1)/ll(1e9);
    ll r = S%ll(1e9);
    Y[2] = (ll(1e9) - r)%ll(1e9);
    cout << X[0] <<" "<<Y[0]<<" "<<X[1]<<" "<<Y[1]<<" "<<X[2]<<" "<<Y[2]<< endl;
}

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

//define-----------------------------------------------------------------------------------------------------------------------
#define rep(i, n) for(int i = 0; i < (int)n; i++)
#define FOR(i, s, n) for(int i = s; i < (int)n; i++)
#define per(i, n) for(int i = n; i >= 0; i--)
#define ROF(i, s, n) for(int i = s; i >= (int)n; i--)
#define FORIT(i, A) for (auto i : A)
#define PRINT(x) cout << (x) << "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define EACH(i, n) for (__typeof((n).begin()) i = (n).begin(); i != (n).end(); ++i)
#define SZ(a) int((a).size())
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define CLR(a) memset((a), 0 ,sizeof(a))
#define dump(x) cout << #x << " = " << (x) << "\n";
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << "\n";
#define sq(n) (n) * (n)

//typedef----------------------------------------------------------------------------------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef priority_queue<int> maxpq;
typedef priority_queue< int, vector<int>, greater<int> > minpq;
//const------------------------------------------------------------------------------------------------------------------------
static const double EPS = 1e-10;
static const double PI = acos( -1.0 );
static const int mod = 1000000007;
static const int INF = 1 << 25;

//global-----------------------------------------------------------------------------------------------------------------------
int a, b;

//function--------------------------------------------------------------------------------------------------------------------
int main() {
	while ( scanf( "%d %d", &a, &b ) ) {
		if ( !a && !b ) {
			break;
		}
		rep( i, a ) {
			rep( j, b ) {
				if ( i % ( a - 1 ) && j % ( b - 1 ) ) {
					printf( "." );
				}
				else {
					printf( "#" );
				}
			}
			printf( "\n" );
		}
		printf( "\n" );
	}
	return 0;
}

Measured memory_bytes: 1160
using System;
using System.IO;
using System.Linq;
using System.Numerics;
using System.Collections;
using System.Collections.Generic;

public class E512IO {
    public char separator = ' ';
    private string[] reads;
    private int index;
    public E512IO (bool autoflush = true) {
        StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());
        sw.AutoFlush = autoflush;
        Console.SetOut(sw);
        this.reads = new string[0];
        this.index = 0;
    }
    ~E512IO () { Console.Out.Flush(); }
    private string NextValue () {
        this.index += 1;
        if (this.index > this.reads.Length) {
            this.reads = Console.ReadLine().Split(separator);
            this.index = 0;
        }
        return this.reads[this.index];
    }
    private string[] NextLine () {
        this.reads = Console.ReadLine().Split(separator);
        this.index = this.reads.Length;
        return this.reads;
    }
    public int[] NextIntArray () { return this.NextLine().Select(x => int.Parse(x)).ToArray(); }
    public long[] NextLongArray () { return this.NextLine().Select(x => long.Parse(x)).ToArray(); }
    public double[] NextDoubleArray () { return this.NextLine().Select(x => double.Parse(x)).ToArray(); }
    public string[] NextStringArray () { return this.NextLine(); }
    public List<int> NextIntList () { return this.NextLine().Select(x => int.Parse(x)).ToList(); }
    public List<long> NextLongList () { return this.NextLine().Select(x => long.Parse(x)).ToList(); }
    public List<double> NextDoubleList () { return this.NextLine().Select(x => double.Parse(x)).ToList(); }
    public List<string> NextStringList () { return this.NextLine().ToList(); }
    public int NextInt () { return int.Parse(this.NextValue()); }
    public long NextLong () { return long.Parse(this.NextValue()); }
    public double NextDouble () { return double.Parse(this.NextValue()); }
    public string NextString () { return this.NextValue(); }
}

public class Program {
    static void Main (string[] args) {
        E512IO io = new E512IO(false);
        var a = io.NextLong();
        var b = io.NextLong();
        var c = io.NextLong();
        var k = io.NextLong();
        if (k % 2 == 0) {
            Console.WriteLine(a-b);
        } else {
            Console.WriteLine(b-a);
        }
    }
}

Measured memory_bytes: 13140
import java.io.IOException;
import java.util.Scanner;

class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int num1 = 1, num2 = 1;


		while (true) {

			num1 = scan.nextInt();
			num2 = scan.nextInt();

			if((num1 ==0) && (num2 ==0)){
				break;
			}


			if(num1 > num2){
				System.out.println(num2+" "+num1);
			}else {
				System.out.println(num1+" "+num2);
			}
		}

	}

}

Measured memory_bytes: 35940
alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
num2alp = {}
alp2num = {}
for i, a in enumerate(alphabet):
  num2alp[i] = a
  alp2num[a] = i
  
n = int(input())
sss = input()

out = ''
for s in sss:
  num = alp2num[s]
  num = (num + n) % 26
  s = num2alp[num]
  out += s
  
print(out)

Measured memory_bytes: 3064
n, m = map(int, input().split())
edge = [list(map(int, input().split())) for i in range(m)]
gragh = [[] for i in range(n+1)]
for e in edge:
    gragh[e[0]].append(e[1])
    gragh[e[1]].append(e[0])
start = 1
for k in gragh[start]:
    if n in gragh[k]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 66844
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long N;
  cin >> N;
  
  long long A[N+1]={0},B[N+1]={0};
  
  for(long long i=2;i<=N;i++){
    cin >> A[i];
    B[A[i]]++;
  }
  
  for(long long j=1;j<=N;j++){
  	cout << B[j] << endl;
  }
}


Measured memory_bytes: 6748
/* Blog: https://misteer.hatenablog.com/entry/diverta2019-2-D */

#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

using lint = long long;

int main() {
    /* ----- 入力 ----- */
    lint N;
    cin >> N;
    vector<vector<lint>> val(2, vector<lint>(3));
    for (auto& v : val) {
        for (auto& m : v) cin >> m;
    }

    /* ----- 変換 ----- */
    for (int i = 0; i < 2; ++i) {
        vector<lint> from = val[i], to = val[(i + 1) % 2];
        // fromで金属に変換してからtoでどんぐりに戻す

        /* ----- 個数無制限ナップザックDP ----- */
        vector<lint> dp(N + 1);
        iota(dp.begin(), dp.end(), 0LL);
        // dp[i] = どんぐりi個から得られるどんぐりの最大個数
        //         無変換でi個は確実に得られることに注意

        for (int i = 0; i < 3; ++i) {
            lint F = from[i], T = to[i];
            for (int m = 0; m + F <= N; ++m) {
                dp[m + F] = max(dp[m + F], dp[m] + T);
            }
        }
        N = dp[N];
    }

    cout << N << endl;
    return 0;
}


Measured memory_bytes: 195584
def solve(N, T, V):
    from itertools import accumulate
    ds = [0] + list(accumulate(T))
    vs = [0] + [min(V[i], V[i + 1]) for i in range(len(V) - 1)] + [0]
    for i in range(len(vs)):
        d = ds[i]
        vs[i] = min([v + abs(d - ds[j]) for j, v in enumerate(vs)])
    def calc(t, v0, v1, maxv):
        t0 = maxv - v0
        t1 = maxv - v1
        if t0 + t1 < t:
            return t * maxv - t0 * t0 / 2 - t1 * t1 / 2
        else:
            t0 = (t + v1 - v0) / 2
            t1 = (t + v0 - v1) / 2
            v = (t + v0 + v1) / 2
            S = v * t - t0 * t0 / 2 - t1 * t1 / 2
            return S
    r = 0
    for i in range(N):
        c = calc(T[i], vs[i], vs[i + 1], V[i])
        r += c
    return r
    
if __name__ == '__main__':
    N = int(input())
    T = [int(_) for _ in input().split()]
    V = [int(_) for _ in input().split()]
    print(solve(N, T, V))


Measured memory_bytes: 3064
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		int n = stdIn.nextInt();
		
		int[] a = new int[n];
		
		for(int i = 0; i < n; i++) {
			a[i] = stdIn.nextInt();
		}
		
		
		Map<Integer,Long> map = new HashMap<>();
		
		for(int i = 0; i < n; i++) {

				
				if(!map.containsKey(a[i])) {
					map.put(a[i],(long)0);
				}
				map.put(a[i],map.get(a[i])+1);
		}
			
		long cnt = 0;
		for(Integer k: map.keySet()) {
			cnt += (map.get(k)*(map.get(k)-1))/2;
		}

		for(int i = 0; i < n; i++) {
			long tmp = map.get(a[i]);
			
			System.out.println(cnt - (tmp -1));
		}
		

	

	}

}


Measured memory_bytes: 108440
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;
 
int main(){
  int n;
  cin >> n;
  vector<int> a(n),b(n),c(n);
  rep(i,n){cin>>a[i];} sort(a.begin(),a.end());
  rep(i,n){cin>>b[i];} sort(b.begin(),b.end());
  rep(i,n){cin>>c[i];} sort(c.begin(),c.end());

  ll ans=0;
  rep(i,n){ ans += (lower_bound(a.begin(),a.end(),b[i])-a.begin())*(c.end()-upper_bound(c.begin(),c.end(),b[i])); }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1916
#include<stdio.h>

int main(void){
  long long a,b,c,d;
  long long count1 = 0;
  long long count2 = 0;
  long long count3 = 0;
  long long pro1,pro2,pro3;
  long long gcm,lcm;
  scanf("%lld" "%lld" "%lld" "%lld",&a,&b,&c,&d);
    
    if(c >= d){
        pro1 = c;
        pro2 = d;
    }else if(d >= c){
        pro1 = d;
        pro2 = c;
    }
  pro3 = 1;
        while(pro3 > 0){
            pro3 = pro1 % pro2;
            pro1 = pro2;
            pro2 = pro3;
        }
        gcm = pro1;
    
    lcm = c * d / gcm;
   
    count1 = b / c - (a-1) / c;
    count2 = b / d - (a-1) / d;
    count3 = b / lcm - (a-1) / lcm;
    
    printf("%lld\n",b-a+1-(count1+count2-count3));
    
  return(0);
}


Measured memory_bytes: 128
import java.math.BigInteger;
import java.util.Arrays;

public class Main {
	private static void solve() {

		int n = ni();
		int[] a = na(n);

		BigInteger one = BigInteger.ONE;
		for (int v : a) {
			one = one.or(one.shiftLeft(v));
		}

		for (int i = (Arrays.stream(a).sum() + 1) / 2;; i ++) {
			if (one.testBit(i)) {
				System.out.println(i);
				return;
			}
		}
	}

	public static void main(String[] args) {
		new Thread(null, new Runnable() {
			@Override
			public void run() {
				long start = System.currentTimeMillis();
				String debug = args.length > 0 ? args[0] : null;
				if (debug != null) {
					try {
						is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
					} catch (Exception e) {
						throw new RuntimeException(e);
					}
				}
				reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
				solve();
				out.flush();
				tr((System.currentTimeMillis() - start) + "ms");
			}
		}, "", 64000000).start();
	}

	private static java.io.InputStream is = System.in;
	private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
	private static java.util.StringTokenizer tokenizer = null;
	private static java.io.BufferedReader reader;

	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new java.util.StringTokenizer(reader.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	private static double nd() {
		return Double.parseDouble(next());
	}

	private static long nl() {
		return Long.parseLong(next());
	}

	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}

	private static char[] ns() {
		return next().toCharArray();
	}

	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}

	private static int[][] ntable(int n, int m) {
		int[][] table = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				table[i][j] = ni();
			}
		}
		return table;
	}

	private static int[][] nlist(int n, int m) {
		int[][] table = new int[m][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				table[j][i] = ni();
			}
		}
		return table;
	}

	private static int ni() {
		return Integer.parseInt(next());
	}

	private static void tr(Object... o) {
		if (is != System.in)
			System.out.println(java.util.Arrays.deepToString(o));
	}
}


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

int main() {
    long long  n, ans=0, x, y;
    cin >> n;
    vector<long long> a(n);
    for(int i=0; i<n; i++) cin >> a[i];
    sort(a.begin(), a.end());
    reverse(a.begin(), a.end());
    queue<long long> q;
    for(int i=0; i<n-1; i++) {
        if(a[i]==a[i+1]) {
            q.push(a[i]);
            i++;
        }
    }
    if(q.size()>=2) {
        x=q.front();
        q.pop();
        y=q.front();
        ans=x*y;
    }
    cout << ans;
}

Measured memory_bytes: 1408
import numpy as np
MAX_N=10**5
prime=np.full(MAX_N+1,True)
prime[:2]=False #0,1をFalseにしてる
for p in range(2,int(MAX_N**.5)+1):
  if prime[p]:
    prime[p*p::p]=False #p:素数の倍数をFalseに変える

like2017=np.zeros(MAX_N+1,dtype=np.int64)
for p in range(1,MAX_N+1):
  if 2*p>MAX_N:  #(p+1)//2をpとよみかえると、pと2*p-1になる
    break
  if prime[p] and prime[2*p-1]:
    like2017[2*p-1]=1

like2017_cumsum=like2017.cumsum()

q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  print(like2017_cumsum[r]-like2017_cumsum[l-1])


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

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

int main() {
    int N, M;
    cin >> N >> M;
    vector<int> result(N, -1);
    rep(i, M) {
        int s, c;
        cin >> s >> c;
        if(result[s-1]!=-1&&result[s-1]!=c){
            cout << "-1" << endl;
            return 0;
        }
        result[s-1] = c;
    }
    if (N==1) {
        cout << (result[0]==-1?0:result[0]) <<endl;
        return 0;
    }
    if (result[0]==-1) {
        result[0] = 1;
    } else if (result[0] == 0) {
        cout << "-1" << endl;
        return 0;
    }
    rep(i, N) {
        cout << (result[i]==-1?0:result[i]);
    }
    cout << endl;
}

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

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

using ll = long long;
#define INF 1e9

ll N, K, Q;
vector<ll> A;

int main(){
  cin >> N >> K >> Q;
  A.resize(Q);
  vector<ll> sum(N, 0);
  for(ll i = 0; i < Q; i++){
    cin >> A[i];
    A[i]--;
    sum[A[i]]++;
  }
  REP(i, N){
    if((Q-sum[i]) < K){
      cout << "Yes" << endl;
    }
    else{
      cout << "No" << endl;
    }
  }


  return 0;
}


Measured memory_bytes: 2176
def is_prime(num):
  i = 5
  while (i * i <= num):
      if num % i == 0 or num % (i+2) ==0:
          return False
      i+=6
  return True if num > 1 and num <=3 else False if num % 2 == 0 or num % 3 == 0 or num <=1 else True

k = int(input())
if is_prime(k):
  print(k)
else:
  while(not is_prime(k)):
    k +=1
  print(k)

Measured memory_bytes: 3064
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n=int(input())
X,Y=[],[]
for _ in range(n):
    x,y=map(int,input().split())
    X.append(x)
    Y.append(y)
mod=(X[0]+Y[0])%2
for i in range(1,n):
    if (X[i]+Y[i])%2!=mod:
        print(-1)
        exit()
if not mod:
    X=[x+1 for x in X]
U=[X[i]+Y[i] for i in range(n)]
V=[X[i]-Y[i] for i in range(n)]
Mode=['L','D','U','R']
m=31
if mod:
    print(m)
    print(' '.join([str(2**i) for i in range(m)]))
else:
    print(m+1)
    print('1 '+' '.join([str(2**i) for i in range(m)]))
for i in range(n):
    w=''
    if not mod:
        w='L'
    ui=(U[i]+2**m-1)//2
    vi=(V[i]+2**m-1)//2
    for _ in range(m):
        u_bit,v_bit=ui&1,vi&1
        ui>>=1
        vi>>=1
        w+=Mode[u_bit*2+v_bit]
    print(w)

Measured memory_bytes: 3316
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define endl "\n"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T> using ordered_set = tree<T, null_type, std::less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const ll N = 1e5 + 10, inf = 1e18 + 10, mod = 1e9 + 7;
ll d[N][110][2];
int D;
string s;
int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("prices.in", "r", stdin);
    //freopen("prices.out", "w", stdout);
    cin >> s >> D;
    for(int i = 0; i < s[0] - '0'; i++)
    {
        d[0][i % D][0]++;
    }
    d[0][(s[0] - '0') % D][1]++;
    for(int i = 1; i <= s.size() - 1; i++)
    {
        for(int j = 0; j < D; j++)
        {
            for(int k = 0; k < s[i] - '0'; k++)
            {
                (d[i][(j + k) % D][0] += d[i - 1][j][1]) %= mod;
            }
            d[i][(j + s[i] - '0') % D][1] = d[i - 1][j][1];
            d[i][(j + s[i] - '0') % D][1] %= mod;
            for(int k = 0; k < 10; k++)
            {
                d[i][(j + k) % D][0] += d[i - 1][j][0];
                d[i][(j + k) % D][0] %= mod;
            }
        }
    }
    cout << (d[s.size() - 1][0][1] + d[s.size() - 1][0][0] - 1 + mod) % mod;
}


Measured memory_bytes: 18688
#include <bits/stdc++.h>
#include <vector>
#include <queue>

using namespace std;
typedef long long int64;

const int MAXN = 2e5 + 11;
int buc[MAXN];
int v[MAXN];
int64 ans;
int n;

inline void add(int x, int y) { ans += 1ll * y * x * (x - 1) >> 1; }

int main(void)
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	cin >> n;
	for (int i = 1;i <= n; ++i)
		cin >> v[i], buc[v[i]] ++;
	for (int i = 0;i < MAXN; ++i)
		ans += 1ll * buc[i] * (buc[i] - 1) >> 1;
	for (int i = 1;i <= n; ++i)
	{
		add(buc[v[i]], -1);
		--buc[v[i]];
		add(buc[v[i]], 1);
		cout << ans << '\n';
		add(buc[v[i]], -1);
		++buc[v[i]];
		add(buc[v[i]], 1);
	}
	
	return 0;
}

Measured memory_bytes: 3712
#https://atcoder.jp/contests/abc127
# -*- coding: utf-8 -*-

n = int(input())
s = []
for i in range(n):
    x,y=input().split()
    y = int(y)
    s.append([x,y])

s2=sorted(s,key=lambda x: (x[1]),reverse = True)
s2=sorted(s2,key=lambda x: (x[0]))
for i in s2:
    for j in range(n):
        if i==s[j]:
            print(j+1)

Measured memory_bytes: 3060
n = int(input())
c = [0] * 4
str = ['AC', 'WA', 'TLE', 'RE']
for _ in range(n):
    s = input()
    if s in str:
        i = str.index(s)
        c[i] += 1
for s, ct in zip(str, c):
    print('{} x {}'.format(s, ct))


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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define ld long double
#define pb push_back
#define eb emplace_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j
#define lbidx(x, y) lower_bound(x.begin(), x.end(), y) - x.begin()
#define ubidx(x, y) upper_bound(x.begin(), x.end(), y) - x.begin()
#define llbidx(x, y, z) lower_bound(x.begin(), x.end(), z) - lower_bound(x.begin(), x.end(), y) // 二要素間の距離
#define deg2rad(deg) ((((double)deg)/((double)360)*2*M_PI))
#define rad2deg(rad) ((((double)rad)/(double)2/M_PI)*(double)360)
#define Find(set, element) set.find(element) != set.end()
#define Decimal(x) printf("%.10f\n", x) // 小数点を10桁まで表示
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;
#define debug(x) cerr << #x << ": " << (x) << "\n";

typedef pair<int, int> PI;
typedef pair<ll, ll> PLL;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<vector<vector<int>>> vvvl;
typedef vector<PI> vpi;
typedef vector<vector<PI>> vvpi;
typedef vector<vector<vector<PI>>> vvvpi;
typedef vector<PLL> vpl;
typedef vector<vector<PLL>> vvpl;
typedef vector<vector<vector<PLL>>> vvvpl;

int POWINT(int x, int n) {
  int ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

ll POWLL(ll x, int n) {
  ll ret = 1;
  rep(i, 0, n) ret *= x;
  return ret;
};

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

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

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

  int X, t;
  cin >> X >> t;

  cout << max(0, X - t) << endl;

  return 0;
};


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

using namespace std;


class B {
	int X;

public:
	void solve()
	{
		cin >> X;

		int ans{ 1 }; // 1 is always an answer
		int tmp;
		for (int base{ 2 }; base <= (int)sqrt(X); base++)
		{
			tmp = base * base;

			while (X >= tmp)
			{
				tmp *= base;
			}
			tmp /= base;
			if (tmp > ans) ans = tmp;

		}

		cout << ans << endl;
	}
};


int main()
{
	B solution;
	solution.solve();

	return 0;
}

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

#define int long long

const int N=2e5+5;
int a[N];
vector<int> g[N];
int n;
int ans[N];
vector<int> d;
void dfs(int k,int par)
{
    ans[k]=d.size();
    for(auto &it:g[k])
    {
        int temp;
        if(it==par)
            continue;
        bool flag=1;    
        auto itr=lower_bound(d.begin(),d.end(),a[it]);
        int idx=itr-d.begin();
        if(itr==d.end())
            d.push_back(a[it]);
        else
        {
            flag=0;
            temp=*itr;
            *itr=a[it];
        }
        dfs(it,k);
        if(flag)
            d.pop_back();
        else
            d[idx]=temp;
    }
}

void solve(int tt)
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    d.push_back(a[1]);
    dfs(1,0);
    for(int i=1;i<=n;i++)
        cout<<ans[i]<<endl;
}

int32_t main()
{
    int t=1;
    //cin>>t;
    for(int i=1;i<=t;i++)
        solve(i);
}

Measured memory_bytes: 32104
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
    double a,b,c;
    cin>>a>>b>>c;
    if(a/c<=b){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
  return(0);
}

Measured memory_bytes: 3720
#include <iostream>
using namespace std;
typedef long long int lli;

lli halfComb[2001]; // 0 to 2000  init with 0

void init() {
  for(int i = 0; i < 1001; i++)
    for(int j = 0; j < 1001; j++)
      halfComb[i+j]++;
}

int main(){
  lli cnt;
  int n, mx;

  init();
  
  while(cin >> n) {
    cnt = 0;
    mx =  (n<2000?n:2000); // (a, b) の組合せそれぞれに対して(c, d) は高々2000通り
    for(int i = 0; i <= mx; i++) {  // 0 <= a+b <= 2000
      if(n-i <= 2000)       // 0 <= c+d <= 2000
	cnt += halfComb[i] * halfComb[n-i];
    }
    cout << cnt << endl;
  }
  return 0;
}

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

int H[200005];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);

    int n, k;
    cin >> n >> k;

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

    sort(H+1, H+1+n);
    reverse(H+1, H+1+n);

    long long sum = 0;

    for(int i=k+1; i<=n; i++)
        sum += H[i];

    cout << sum << "\n";
    return 0;
}


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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
//typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

const int INF = 1e7;

template <typename T>
struct MinCostFlow {
  struct Edge {
    int to, rev; T cap, cost;
    Edge(int to, int rev, T cap, T cost) : to(to), rev(rev), cap(cap), cost(cost) { }
  };

  struct Node {
    int v; T dist;
    Node(int v, T dist) : v(v), dist(dist) { };
    bool operator < (const Node &n) const {
      return dist > n.dist; // reverse
    }
  };

  typedef vector<Edge> Edges;
  vector<Edges> G;
  int V;
  vector<int> dist, h, prevv, preve;

  MinCostFlow(int V) : V(V) { G.resize(V); }

  void add_edge(int from, int to, T cap, T cost) {
    G[from].emplace_back(to, G[to].size(), cap, cost);
    G[to].emplace_back(from, (int)G[from].size()-1, 0, -cost);
  }

  T primal_dual(int source, int sink, T f) {
    T res = 0;
    h.resize(V, 0);
    prevv.resize(V), preve.resize(V);
    while (f > 0) {
      priority_queue<Node> pque;
      dist.assign(V, INF);
      dist[source] = 0;
      pque.emplace(source, 0);
      while (not pque.empty()) {
        Node n = pque.top(); pque.pop();
        int v = n.v; T cost = n.dist;
        if (dist[v] < cost) continue;
        for (int i = 0; i < (int)G[v].size(); i++) {
          Edge e = G[v][i];
          if (e.cap > 0 and dist[v] - h[e.to] < dist[e.to] - e.cost - h[v]) {
            dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
            prevv[e.to] = v, preve[e.to] = i;
            pque.emplace(e.to, dist[e.to]);
          }
        }
      }
      if (dist[sink] == INF) return -1;
      for (int v = 0; v < V; v++) h[v] += dist[v];

      T d = f;
      for (int v = sink; v != source; v = prevv[v]) {
        d = min(d, G[prevv[v]][preve[v]].cap);
      }
      f -= d;
      res += d * h[sink];
      for (int v = sink; v != source; v = prevv[v]) {
        Edge &e = G[prevv[v]][preve[v]];
        e.cap -= d;
        G[v][e.rev].cap += d;
      }
    }
    return res;
  }
};


int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int V, E, F; cin >> V >> E >> F;
  MinCostFlow<int> mcf(V);

  REP(_, E) {
    int u, v, c, d; cin >> u >> v >> c >> d;
    mcf.add_edge(u, v, c, d);
  }

  cout << mcf.primal_dual(0, V-1, F) << endl;
  return 0;
}

Measured memory_bytes: 3232
import java.util.*;

class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
      
        String array[][] = new String[3][3];
        
        for(int i = 0; i < 3; i++) {
            array[i] = sc.next().split("");
        }
        
        for(int i = 0; i < 3; i++) {
            System.out.print(array[i][i]);
        }
		}
	}

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

int main() {
    int K,N;
    cin>>K>>N;
    vector<int>A(N);
    vector<int>B(N);
    for(int i=0;i<N;i++){
        cin>>A.at(i);
        B.at(i)=A.at(i)+K;
    }


    int mini=A.at(N-1)-A.at(0);
    for(int i=N-2;i>=0;i--){
        int tmp=B.at(i)-A.at(i+1);
        if(mini>tmp)mini=tmp;
    }
    cout<<mini<<endl;

    return 0;
}

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

int main() {
  ll N;
  cin>>N;
  ll A[N];
  for(int i=0;i<N;i++){
    cin>>A[i];
  }
  ll ans=1;
  sort(A,A+N);
  for(int i=0;i<N;i++){
    if(A[i]==0){
      ans=0;break;
    }
    if(ans>1000000000000000000/A[i]){
      ans=-1;
      break;
    }
    ans*=A[i];
    if(ans>1000000000000000000){
      ans=-1;
      break;
    }
    if(ans<0){
      ans=-1;break;
    }
  }
  cout<<ans;
}


Measured memory_bytes: 4412
/* dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pf          push_front
#define endl    '\n'
#define pii         pair<ll ,ll>
#define vll          vector<ll>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)  for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005

int main()
{
  ios
  ll a,b,i,j,f=0;
  string s;
  cin>>a>>b>>s;
  for(i=0;i<a;i++)if(s[i]<'0'||s[i]>'9')f=1;
  if(s[a]!='-')f=1;
  for(i=a+1;i<a+b+1;i++)if(s[i]<'0'||s[i]>'9')f=1;
    if(f)cout<<"No";else cout<<"Yes";
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define mod 1000000007
#define ll long long
#define N 100005
#define pb push_back
ll n, q, x, a[N], s[N], sum[N], l, r, ss;
int main ()
{
    scanf("%lld %lld", &n, &q);
    fo (i, 1, n) 
        scanf("%lld", &a[i]);
    s[1] = a[1]; s[2] = a[2];
    sum[1] = a[1]; sum[2] = a[1] + a[2];
    fo (i, 3, n)
    {
        s[i] = s[i - 2] + a[i];
        sum[i] = sum[i - 1] + a[i];
    }
    ss = sum[n];
    fo (i, 1, q)
    {
        scanf("%lld\n", &x);
        if (x <= a[1])
        {
            printf("%lld\n", ss - sum[n >> 1]);
            continue;
        }
        l = x; r = 1e9;
        ll rp, rpos, ans, lp, lpos;
        while (l < r)
        {
            rp = l + r >> 1;
            rpos = std::upper_bound(a + 1, a + n, rp) - a - 1;
            lp = x * 2 - rp;
            lpos = std::lower_bound(a + 1, a + n, lp) - a;
            if (n - rpos > rpos - lpos + 1)
                l = rp + 1;
            else
                r = rp;
        }
        rp = l;
        rpos = std::upper_bound(a + 1, a + n, rp) - a - 1;
        lp = x * 2 - rp;
        lpos = std::lower_bound(a + 1, a + n, lp) - a;
        if (n - rpos < rpos - lpos + 1)
            --rpos;
        ans = sum[rpos] - sum[lpos - 1];
        if (n - rpos == rpos - lpos + 1)
        {
            if (lpos > 2)
                ans += s[lpos - 2];
        }
        else
        {
            ans += s[lpos - 1];
        }
        printf("%lld\n", ss - ans);
    }
    return 0;
}

Measured memory_bytes: 4096
#-swank
(unless (member :child-sbcl *features*)
  (quit
   :unix-status
   (process-exit-code
    (run-program *runtime-pathname*
                 `("--control-stack-size" "128MB"
                   "--noinform" "--disable-ldb" "--lose-on-corruption" "--end-runtime-options"
                   "--eval" "(push :child-sbcl *features*)"
                   "--script" ,(namestring *load-pathname*))
                 :output t :error t :input t))))
(defmacro dp (name args memo-size &body body)
  (let ((memo (gensym)))
    `(let ((,memo (make-array ,memo-size :initial-element nil)))
       (defun ,name ,args
         (or (aref ,memo ,@args)
             (setf (aref ,memo ,@args)
                   ,@body))))))

(defun split (x str)
  (let ((pos (search x str))
        (size (length x)))
    (if pos
      (cons (subseq str 0 pos)
            (split x (subseq str (+ pos size))))
      (list str))))

(defmacro collect-times (time body)
  `(loop repeat ,time collect ,body))

(defun read-times (time)
  (collect-times time (read)))

(defun main (str)
  (count #\1 str))


(defun main (line)
  (abs (reduce (lambda (acc x)
                 (- x acc))
               (sort line #'>))))


(princ (main (read-times (read))))


Measured memory_bytes: 19252
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

int main(){
  ll Q[10],N,data,minimum=100000000,ans=0;
  for(int i=0;i<4;i++){
    cin>>data;
    if(i<2) Q[i]=data*(4-2*i);
    else Q[i]=data;
  }
  cin>>N;
  for(int i=0;i<3;i++){
    minimum=min(minimum,Q[i]);
  }
  if(minimum*2>Q[3]){
    if(N%2==0){
      ans=N/2*Q[3];
    }else{
      ans=N/2*Q[3]+minimum;
    }
  }else{
    ans=N*minimum;
  }
  cout<<ans<<endl;
  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()

ll ten(ll x) {
  ll count=0;
while(x/10>0) {
x/=10;
  count++;
}
  return count;
}

int main() {
  ll N;
  cin>>N;
  vector<ll> vec(N);
  for(ll i=0;i<N;i++) {
cin>>vec[i];
  }
  
  sort(all(vec));
  if(vec[0]==0) {
cout<<0<<endl;
    return 0;
  }
  ll ans=1;
  for(ll i=0;i<N;i++) {
if(ten(ans)+ten(vec[i])>=18&&ans*vec[i]!=1000000000000000000) {
cout<<-1<<endl;
  return 0;
}
   else {
ans*=vec[i];
   }
  }
  
  if(ans>1000000000000000000) {
    cout<<-1<<endl;
  }
  else{

  
  cout<<ans<<endl;
}
}
  
  
  


Measured memory_bytes: 3960
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <vector>

int main() {
  int numArray;
  std::cin >> numArray;
  assert(2 <= numArray and numArray <= 1.0e+5);

  std::vector<int> height(1 + numArray + 2);
  for (int i = 1; i <= numArray; ++i) {
    std::cin >> height[i];
    assert(height[i] <= 1.0e+4);
  }

  std::vector<int> dp(1 + numArray + 2);

  // Init
  for (int i = 2; i <= numArray + 2; ++i)
    dp[i] = 1.0e+9 + 7;

  // DP main
  for (int i = 1; i <= numArray; ++i) {
    if (dp[i] + abs(height[i + 1] - height[i]) <= dp[i + 1])
      dp[i + 1] = dp[i] + abs(height[i + 1] - height[i]);
    if (dp[i] + abs(height[i + 2] - height[i]) <= dp[i + 2])
      dp[i + 2] = dp[i] + abs(height[i + 2] - height[i]);
  }

  // Output
  std::cout << dp[numArray] << std::endl;

  return 0;
}


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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int a = Integer.parseInt(str[0]);
    int b = Integer.parseInt(str[1]);
    int sum = 1;
    int count = a;
    
    if(b==1) {
      System.out.println(0);
      System.exit(0);
    }
    
    for(sum=1; count<b; sum++) {
      count += (a-1);
    }
    
    System.out.print(sum);
  }
}

Measured memory_bytes: 21332
#include<bits/stdc++.h>
#define MOD (long long)(1e9+7)
using namespace std;
long long n,k,vis[5005];
long long p[5005],c[5005],sum[5005],ans=-1e18;
int main()
{
	cin >> n >> k;
	for(int i=1; i<=n; i++) cin >> p[i];
	for(int i=1; i<=n; i++) cin >> c[i];
	for(int i=1; i<=n; i++)
	{
		long long s=c[i];
		vector<long long> t; t.push_back(s);
		for(int j=p[i]; j!=i; j=p[j]) s+=c[j],t.push_back(s);
		int len=t.size();
		for(int j=0; j<len; j++)
		{
			long long rest=k-j-1;
			if(rest < 0) break;
			ans=max(ans,t[j]+(rest/len)*max(s,0LL));
		}
		
	}
	cout << ans;
	return 0;
}


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

int gcd(int,int);

int main(){
  int x,y,d,n;

  scanf("%d %d",&x,&y);

  //constraint
  if(x<1 || x>10000000000 || y<1 || y>10000000000){
    exit(1);
  }

  //min comparison
  if(x<y){
    n=x;
    x=y;
    y=n;
  }

  //calculate GCD 
  while(y>0){
    d=x%y;
    x=y;
    y=d;
  }
  
  printf("%d\n",x);

  return 0;
}

Measured memory_bytes: 592
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(ll i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(ll i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(ll i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
#define len(x) ((ll)(x).length())
#define endl "\n"

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    ll n, q;
    cin >> n >> q;
    vector<vector<ll>> g(n);
    rep(i, n - 1) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<ll> dp(n, 0);
    rep(i, q) {
        ll p, x;
        cin >> p >> x;
        p--;
        dp[p] += x;
    }
    vector<bool> seen(n, false);
    queue<ll> que;
    que.push(0);
    while(!que.empty()) {
        ll v = que.front(); que.pop();
        seen[v] = true;
        for(auto u : g[v]) {
            if (u == v) continue;
            if (seen[u]) continue;
            dp[u] += dp[v];
            que.push(u);
        }
    }
    rep(i, n) printf("%lld%s", dp[i], (i == (n - 1)) ? "\n" : " ");
    return 0;
}


Measured memory_bytes: 17904
#include<bits/stdc++.h>
using namespace std;
int main() {
	int a[4];
	while(cin>>a[0]>>a[1]>>a[2]>>a[3]) {
		sort(a,a+4);
		if(a[0]==1&&a[1]==4&&a[2]==7&&a[3]==9) {
			cout<<"YES"<<endl;
		} else {
			cout<<"NO"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 256