akhauriyash/Code-Regression huggingface dataset:
import java.io.BufferedReader
import java.io.InputStreamReader
import java.io.PrintWriter
import java.util.*
import kotlin.math.abs
import kotlin.math.cos
import kotlin.math.max
import kotlin.math.min

val br = BufferedReader(InputStreamReader(System.`in`))
val out = PrintWriter(System.out)

fun main() {
    br.use { out.use {
        solve()
        out.flush()
    } }
}

fun solve() {
    val (n, k) = readIntegerList()
    val aList = readIntegerList().sorted()

    val c = Combination(100000)
    var min = 0L
    for ((i, a) in aList.withIndex()) {
        min = (min + ((a * c.value(n - 1 - i, k - 1)) % 1000000007)) % 1000000007
    }

    var max = 0L
    for ((i, a) in aList.sortedDescending().withIndex()) {
        max = (max + ((a * c.value(n - 1 - i, k - 1)) % 1000000007)) % 1000000007
    }

    val ans = (((max - min) % 1000000007) + 1000000007) % 1000000007
    out.println(ans)
}

/** n <= 20000000 */
class Combination(n: Int = 20000000, val MOD: Long = 1000000007L) {
    val fact = LongArray(n + 1)
    val ifact = LongArray(n + 1)

    /** O(n) */
    init {
        fact[0] = 1L
        for (i in 1..n) { fact[i] = (fact[i - 1] * i) % MOD }
        ifact[n] = modInverse(fact[n], MOD)
        for (i in n downTo 1) { ifact[i - 1] = (ifact[i] * i) % MOD }
    }

    /** O(1) */
    fun value(n: Int, k: Int) = if (k < 0 || k > n) 0 else (((fact[n] * ifact[k]) % MOD) * ifact[n-k]) % MOD

    /**
     * O(log(MOD))
     */
    fun modInverse(n: Long, mod: Long = 1000000007L): Long {
        var a = n % mod
        if (a < 0) a += mod

        if (a == 0L) throw ArithmeticException("n is not relatively prime to mod")

        var b = mod
        var u = 1L
        var v = 0L
        while (b > 0) {
            val t = a / b
            a -= t * b
            a = b.also { b = a } // swap(a, b)
            u -= t * v
            u = v.also { v = u } // swap(u, v)
        }
        u %= mod
        if (u < 0) u += mod
        return u
    }
}

fun readInteger() = Integer.parseInt(br.readLine())
fun readLong() = java.lang.Long.parseLong(br.readLine())
fun readStringList() = br.readLine()!!.split(' ')
fun readIntegerList() = readStringList().map(Integer::parseInt)
fun readLongList() = readStringList().map(java.lang.Long::parseLong)
fun readDoubleList() = readStringList().map(java.lang.Double::parseDouble)


Measured memory_bytes: 63840
def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return c1[-1]


n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")


Measured memory_bytes: 5636
program name
    use,intrinsic :: iso_fortran_env
    implicit none
    integer(int32):: r,g,b,n,ans
    integer(int32):: ri,gi,bi

    read*, r,g,b,n
    ans=0
    do ri=0,n
        do gi=0,n
            bi = n-ri*r-gi*g
            ! print*, ri,gi,bi
            if (mod(bi,b)==0 .and. bi >= 0)then
                ans=ans+1
            end if
        end do
    end do

    print*, ans
end program name

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
int N, X, arr[105], result;

int main()
{
    scanf("%d %d", &N, &X);
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &arr[i]);
    }
    int start = 0;
    for(int i = 1; i <= N; i++)
    {
        start += arr[i];
        if(start <= X)
            result++;
    }
    printf("%d", result + 1);
}

Measured memory_bytes: 384
s = input()
q = int(input())
string = []
is_normal = 1
saq = ""
sol = ""
for i in range(q):
    emir = input()
    if emir[0] == '1':
        is_normal *= -1
    elif emir[0] == '2':
        if is_normal == 1:
            if emir[2] == '1':
                sol += emir[4]
            elif emir[2] == '2':
                saq += emir[4]
        else:
            if emir[2] == '1':
                saq += emir[4]
            elif emir[2] == '2':
                sol += emir[4]
s = sol[::-1] + s + saq
if is_normal == -1:
    s = s[::-1]

print(s)

Measured memory_bytes: 4320
#include <bits/stdc++.h>
using namespace std;
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef pair<int, int> Pint;
typedef pair<int64_t, int64_t> Pll;
  
int main() {
    int N, L;
    cin >> N >> L;
    vector<string> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S.at(i);
    }
    sort(ALL(S));
    for (int i = 0; i < N; i++) {
        cout << S.at(i);
    }
    cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
ll dp[400][400][135],c[405][405],f[405],r[405],rui[405][405][135];
int n,a[405],b[405],pos[405],pos2[405],t[405][405];
ll modpow(ll x,ll n){
	ll res=1;
	while(n>0){
		if(n&1) res=res*x%mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}
int main(){
	cin>>n;
	repn(i,n)cin>>a[i],pos[a[i]]=i;
	repn(i,n)cin>>b[i],pos2[b[i]] = i;\
	rep(i,405)rep(j,i+1){
		if(j==0||j==i) c[i][j]=1;
		else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
	}
	f[0]=r[0]=1;
	repn(i,400) f[i]=f[i-1]*1LL*i%mod,r[i]=modpow(f[i],mod-2);
	rep(i,n+1)rep(j,n+1){
		repn(k,n){
			if(pos[k]<=i||pos2[k]<=j) t[i][j]++;
		}
	}
	dp[0][0][0] = 1;
	repn(k,n/3){
		repn(x,n){
			repn(y,n){
				rui[x][y][k]=rui[x-1][y][k]+rui[x][y-1][k]-rui[x-1][y-1][k];
				if(x<pos[b[y]] && y<pos2[a[x]] && 2*k<=t[x][y] && t[x][y]<=3*k-1){
					dp[x][y][k]=rui[x-1][y-1][k-1];
					if(k==1)dp[x][y][k]++;
					dp[x][y][k]=dp[x][y][k]%mod*r[3*k-3-t[x-1][y-1]]%mod;
					rui[x][y][k] += dp[x][y][k]*f[3*k-t[x][y]]%mod;
				}
				rui[x][y][k]%=mod;
			}
		}
	}
	ll ans=0;
	rep(i,n+1)rep(j,n+1)ans = (ans+dp[i][j][n/3]*f[n-t[i][j]]%mod)%mod;
	rep(i,n)if(i%3!=0)ans=ans*1LL*i%mod;
	cout<<(ans%mod+mod)%mod<<endl;
}


Measured memory_bytes: 341760
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ff first
#define ss second
#define eb emplace_back
#define MP make_pair
#define pb push_back
#define pf push_front
#define ins insert
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define mset(m,v) memset(m,v,sizeof(m))
#define tr(c,it) for(auto it=c.begin();it!=c.end();it++)
#define fr(i,n) for(lli i=0;i<(n);i++)
#define inc(i,a,b) for(lli i=a;i<=b;i++)
#define dec(i,a,b) for(lli i=a;i>=b;i--)
#define fr2(i,n) for(int i=0;i<(n);i++)
#define inc2(i,a,b) for(int i=a;i<=b;i++)
#define dec2(i,a,b) for(int i=a;i>=b;i--)
#define ymin(a,b)  (a=min((a),(b)))
#define ymax(a,b)  (a=max((a),(b)))
#define sz(x) (lli)(x).size()
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr<< *it << " = " << a << endl;
	err(++it, args...);
}

typedef long long int lli;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<lli,lli> plli;
typedef vector<lli> vlli;
typedef vector<int> vi;
//typedef  vector<vector<lli> >ncr(1001,vector<lli>(1001,0))
typedef vector<plli> vplli;
long long MOD=1000000009;
#define addm(x,y) (x+y>=MOD? (x+y-MOD):(x+y))
lli n;
lli a[401];
lli dp[401][401];
int main()
{
	// 	#ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	IOS
	// clock_t start,end;
	// start=clock();
	// int t;
	// cin>>t;
	// for(int i=1;i<=t;i++)
	// {
	// 	cout<<"Case #"<<i<<": ";
	// 	solve();

	// }
	
	
	// end=clock();
	
	// double time_taken=double(end-start)/double(CLOCKS_PER_SEC);
	// cout<<fixed<<setprecision(10)<<time_taken<<" sec"<<endl;

	cin>>n;
	for(int i=0;i<n;i++)
		cin>>a[i];
	mset(dp,-1);
	for(lli len=1;len<=n;len++)
	{
		for(lli st=0;st<=n-len;st++)
		{
			lli en=len+st-1;
			if(len==1)
			{
				dp[st][en]=0;
				continue;
			}

			else
			{
				dp[st][en]=MOD*MOD;
				lli s=0;
				for(lli p=st;p<=en;p++)
					s+=a[p];
				for(lli k=st;k<en;k++)
					dp[st][en]=min(dp[st][k]+dp[k+1][en]+s,dp[st][en]);
			}

		}
	}
	cout<<dp[0][n-1]<<endl;


	
}


Measured memory_bytes: 4916
N = int(input())
As = list(map(int, input().split()))

maxA = max(As)
minA = min(As)

if minA >= 0:
    # 全ての要素が0以上の場合
    flg = 'GE'
    print(N-1)
elif maxA <= 0:
    # 全ての要素が0以下の場合
    flg = 'LE'
    print(N-1)
else:
    if -minA <= maxA:
        flg = 'GE'
        print(2*N-1)
        # 全ての要素を0以上にする
        iMax = As.index(maxA) + 1
        for i in range(1, N+1):
            print(iMax, i)
    else:
        flg = 'LE'
        print(2*N-1)
        # 全ての要素を0以下にする
        iMin = As.index(minA) + 1
        for i in range(1, N+1):
            print(iMin, i)

if flg == 'GE':
    # 先頭から累積和を取る
    for i in range(1, N):
        print(i, i+1)
else:
    # 末尾から累積和を取る
    for i in reversed(range(1, N)):
        print(i+1, i)


Measured memory_bytes: 3064
import std.stdio, std.string, std.conv;
import std.array, std.algorithm, std.range;

void main()
{
    string s;
    do{
        char[][] m;
        while((s=readln()).chomp().length) m~=s.chomp().to!(char[]);
        void update(int x, int y)
        {
            if(x<0 || m.length<=x || y<0 || m[x].length<=y)
                return;
            if(m[x][y]=='0') return;
            m[x][y]='0';
            foreach(a;[[1,0],[-1,0],[0,1],[0,-1]])
                update(x+a[0],y+a[1]);
        }
        int c=0;
        foreach(x;0..cast(int)(m.length))
            foreach(y;0..cast(int)(m[x].length))
                if(m[x][y]=='1') ++c,update(x,y);
        writeln(c);
    }while(s.length);
}

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


int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    bool ok = true;
    rep(i,n){
        if(a[i]%2==1) continue;
        if(a[i]%3!=0&&a[i]%5!=0) ok=false;
    }
    if(ok) cout << "APPROVED" << endl;
    else cout << "DENIED" << endl;
    return 0;
}

Measured memory_bytes: 3604
# Problem D - Multiple of 2019

from collections import Counter

# input
S = input()
s_len = len(S)

# initialization
ans = 0

# mod count
nums_2019 = [0]*2019
nums_2019[0] = 1
tmp_num = 0
for i in range(s_len-1, -1, -1):
    tmp_num += int(S[i]) * pow(10, s_len-i-1, 2019)
    nums_2019[tmp_num%2019] += 1

# output
for m_c in nums_2019:
    if m_c>=2:
        ans += m_c * (m_c-1) // 2
print(ans)


Measured memory_bytes: 9428
from math import*
A,B=sorted(map(int,input().split()))
prime=[]
i=1
while i**2<=A:
    if A%i==0:
        prime.append(i)
        prime.append(A//i)
    i+=1

prime=list(set(prime))
prime.sort()
L=len(prime)
ans=[1]*L
j=1
while j<L:
    now=prime[j]
    if B%now:
        ans[j]=0
    if ans[j]==0:
        j+=1
        continue
    k=j+1
    while k<L:
        if prime[k]%now==0:
            ans[k]=0
        k+=1
    j+=1

print(sum(ans))

Measured memory_bytes: 9616
def main():
    INF = float('inf')
    N, M = map(int, input().split())
    dist = [0] + [INF] * (N-1)
    abc = []
    
    for i in range(M):
        a, b, c = map(int, input().split())
        abc.append((a, b, -c))
        
    for i in range(N-1):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            dist[b-1] = min(dist[b-1], dist[a-1]+c)
            
    ans = dist[-1]
    negative = [False] * N
    
    for i in range(N):
        for a, b, c in abc:
            if dist[a-1] == INF:
                continue
            elif dist[b-1] > dist[a-1]+c:
                dist[b-1] = dist[a-1]+c
                negative[b-1] = True
            if negative[a-1]:
                negative[b-1] = True
            
    if negative[-1]:
        print('inf')
    else:
        print(-ans)

if __name__ == '__main__':
    main()
    

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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  int z;
  cin >> z;

  while (z--) {
    int n;
    cin >> n;

    vector<array<ll, 3>> a;

    rep(i,0,n) {
      ll k, l, r;
      cin >> k >> l >> r;
      a.pb({k, l, r});
    }

    sort(all(a), [&](array<ll, 3> x, array<ll, 3> y) { return abs(x[1]-x[2]) > abs(y[1]-y[2]); });

    int ls = 0, rs = 0;
    rep(i,0,n) if (a[i][1] >= a[i][2]) ++ls; 

    ll ans = 0;
    set<int> lids, rids;
    rep(i,0,ls) lids.insert(i);
    rep(i,ls,n) rids.insert(i);

    rep(i,0,n) {
      ll delt = a[i][1] - a[i][2];
      ll k = a[i][0]-1;

      if (delt >= 0) {
        auto it = lids.upper_bound(k);
        if (it==lids.begin()) {
          it = prev(lids.end());
          lids.erase(it);
          ans += min(a[i][1], a[i][2]);
        } else {
          --it;
          lids.erase(it);
          ans += max(a[i][1], a[i][2]);
        }
      } else {
        auto it = rids.upper_bound(k);
        if (it==rids.end()) {
          it = rids.begin();
          ans += min(a[i][1], a[i][2]);
          rids.erase(it);
        } else {
          rids.erase(it);
          ans += max(a[i][1], a[i][2]);
        }
      }
    }

    cout << ans << '\n';

  }
}

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

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

  int64_t L0 = 2LL;
  int64_t L1 = 1LL;
  int64_t L2 = 1LL;

  for(int i = 1; i < N; i++)
  {
    L2 = L0 + L1;
    L0 = L1;
    L1 = L2;
  }

  cout << L2 << endl;
  return 0;
}

Measured memory_bytes: 3572
{-# LANGUAGE PartialTypeSignatures #-}
module Main (main) where

import Data.Array
import Control.Monad
import qualified Data.ByteString.Char8 as C8
import qualified Data.Char as C
import qualified Data.List as L

main :: IO ()
main = do
  [n,m,q] <- readInts
  replicateM q readInts >>= output . solve n m

solve :: Int -> Int -> [[Int]] -> _
solve n m xs = maximum . map (go . listArray (1,n)) $ genAscList m n
  where
    go arr = sum [ d | [a,b,c,d] <- xs, (arr!b) - (arr!a) == c ]

genAscList :: Int -> Int -> [[Int]]
genAscList = gen 1
  where
    gen _ m 0 = [ [] ]
    gen a m n = [ i:is | i <- [a..m], is <- gen i m (pred n) ]

output :: _ -> IO ()
output = print

-- utils
readInts :: IO [Int]
readInts = L.unfoldr (C8.readInt . C8.dropWhile C.isSpace) <$> C8.getLine

Measured memory_bytes: 6596
#include<iostream>
#include<bits/stdc++.h>
#define int long long
using namespace std;
int32_t main()
{
	string S;
    cin>>S;

    int n = S.size();

    vector<int > ans(n, 1);

    int prev_r = 0, prev_l = 0;

    vector<int > pr(n, 0);
    vector<int > pl(n, 0);

    for(int i=0;i<n-1;i++){
        if(S[i] == 'R' && S[i+1] == 'L'){
            int temp = prev_r/2;
            int temp2 = prev_r - temp;
            ans[i] += temp;
            ans[i+1] += temp2;
            prev_r = 0; 
            continue;
        }
        if(S[i] == 'R') {
            ans[i] = 0;
            prev_r++;
        }
    }

    for(int i=n-1;i>0;i--){
        if(S[i] == 'L' && S[i-1] == 'R'){
            int temp = prev_l/2;
            int temp2 = prev_l - temp;
            ans[i] += temp;
            ans[i-1] += temp2;
            prev_l = 0;
            continue;
        } 
        if(S[i] == 'L') {
            ans[i] = 0;
            prev_l++;
        }
    }

    for(int i=0;i<n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
	return 0;
}

Measured memory_bytes: 3072
#include <bits/stdc++.h>
    using namespace std;
    #define INF 2000000000
    typedef long long int ll;
    typedef pair<ll,ll> ii;
    typedef pair<ii,ll> iii;
    typedef vector<ll> vi;
    typedef vector<ii> vii;
    #define getbit(n,i) (((n)&(1<<(i)))!=0)
    #define setbit0(n,i) ((n)&(~(1<<(i))))
    #define setbit1(n,i) ((n)|(1<<(i)))
    #define togglebit(n,i) ((n)^(1<<(i)))
    #define lastone(n) ((n)&(-(n)))
    #define read freopen("debug\\in.txt","r",stdin)
    #define write freopen("debug\\out.txt","w",stdout)
    #define fi first
    #define se second
    #define getI(a) scanf("%d",&a)
    #define getII(a,b) scanf("%d%d",&a,&b)
    #define PI (acos(-1))
    #define fastread ios_base::sync_with_stdio(false);cin.tie(NULL)
    #define mod (1000000007)
    #define asz 500005
    #define pb push_back
    #define ppf pop_front
    #define ppb pop_back
    #define pf push_front
    ll n;
    ll W;
    ll a[200005];
    ll val[200005];
    ll b[200005];
    ll c[200005];
    ll dp[200][100005];
    ll recurse(ll pos,ll value){
       if(value<=0)
       return 0;
       if(pos>n)
       return 2e9;
       if(dp[pos][value]!=-1)
       return dp[pos][value];
       return dp[pos][value]=min(recurse(pos+1,value),a[pos]+recurse(pos+1,value-val[pos]));
	}
    int main()
    {
        fastread;
        ll i,j,k,l,m;
        cin>>n>>W;
        for(i=1;i<=n;i++){
        	for(j=0;j<=100004;j++)
        	dp[i][j]=-1;
		}
		ll sum=0;
        for(i=1;i<=n;i++){ 
            cin>>a[i]>>val[i];
            sum+=val[i];
			}
			while(sum){
				ll kola=recurse(1,sum);
				if(kola<=W){
					//cout<<kola<<endl;
					cout<<sum;
					return 0;
				}
				sum--;
			}
        return 0;
    }

Measured memory_bytes: 83456
#include <math.h>
#include <stdio.h>

int rel_l_l( double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4 ) {
	int rel;

	if ( fabs( ( x1 - x2 ) * ( y3 - y4 ) - ( y1 - y2 ) * ( x3 - x4 ) ) < 1e-10 ) {
		rel = 2;
		if ( fabs( ( x1 - x3 ) * ( y3 - y4 ) - ( y1 - y3 ) * ( x3 - x4 ) ) < 1e-10 )
			rel = 3;
	} else {
		rel = 0;
		if ( fabs( ( x1 - x2 ) * ( x3 - x4 ) + ( y1 - y2 ) * ( y3 - y4 ) ) < 1e-10 )
			rel = 1;
	}

	return rel;
}

int main( void ) {
	int q;

	scanf( "%d", &q );
	while ( q-- ) {
		int rel;
		double x1, y1, x2, y2, x3, y3, x4, y4;

		scanf( "%lf %lf %lf %lf %lf %lf %lf %lf", &x1, &y1, &x2, &y2, &x3, &y3, &x4, &y4 );

		rel = rel_l_l( x1, y1, x2, y2, x3, y3, x4, y4 );
		printf( "%d\n", rel >= 2 ? 2 : rel );
	}

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int d;
  cin >> d;
  if(d==25) cout << "Christmas" << endl;
  if(d==24) cout << "Christmas Eve" << endl;
  if(d==23) cout << "Christmas Eve Eve" << endl;
  if(d==22) cout << "Christmas Eve Eve Eve" << endl; 
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
#include <math.h>
#include <map>
#include <iomanip>
#include <queue>
#include <numeric>
#define repl(i, l, r) for (ll i = l; i < r; i++)
#define rep(i, n) repl(i, 0, n)

using namespace std;
using ll = long long;

int main() {

    ll N, tmp = 0;
    cin >> N;

    vector<ll>a(N);
  
    rep(i, N) {
        cin >> a[i];
        tmp += a[i];
    }

    ll A = tmp / N;

    ll ans = pow(10, 9);

    rep(j, 3) {
        tmp = 0;
        rep(i, N) {
            tmp += pow(a[i] - A + (j - 1), 2);
        }
        ans = min(ans, tmp);
    }
    cout << ans;

    return 0;
}


Measured memory_bytes: 3632
a,b = map(int,input().split())

d = [["."]*100 for i in range(100)]

i = 0
j = 0
while b > 1:

    count = 0
    while count < 50 and b > 1:
        d[i][j] = "#"
        count += 1
        b -= 1
        j += 2
    i += 2
    j = 0

for i in range(50,100):
    for j in range(100):
        d[i][j] = "#"

i = 0
j = 0
while a > 1:

    count = 0
    while count < 50 and a > 1:
        d[-i-1][-1-j] = "."
        count += 1
        a -= 1
        j += 2
    i += 2
    j = 0
print(100,100)
for i in d:
    print(*i,sep="")

Measured memory_bytes: 4468
def main():
    N = int(input())
    p = list(map(float, input().split()))
    dp = [[0] * (N+1) for _ in range(N+1)]
    dp[0][0] = 1.0
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j] += dp[i][j] * (1-p[i])
            dp[i+1][j+1] += dp[i][j] * p[i]
    ans = sum(dp[N][N//2+1:])
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 263048
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll sum;
int gcd(int a,int b){
	return   a%b?gcd(b,a%b):b;
     
}
int main()
{
 cin>>n;
 for(int a=1;a<=n;a++)
    for(int b=1;b<=n;b++)
     for(int c=1;c<=n;c++)
 {

	  //sum+=y;
	sum+=gcd(a,gcd(b,c));
 }
 cout<<sum;
return 0;
}


Measured memory_bytes: 3652
import math

n, d = map(int, input().split())
x = [list(map(int, input().split())) for _ in range(n)]
ans = 0

for i in range(n):
    for j in range(i + 1, n):
        add, dis = 0, 0
        for k in range(d):
            add += (x[i][k] - x[j][k]) ** 2
        dis = math.sqrt(add)
        if dis % 1 == 0:
            ans += 1

print(ans)


Measured memory_bytes: 3060
#include <bits/stdc++.h> 
using namespace std;
typedef long long ll;
//typedef pair<int,int> P;
typedef pair<ll, ll> P;
//typedef pair<int, pair<int, pair<int, int>>> P;
//typedef pair<int, pair<int, int>> P;
//typedef tuple<int,int,int> T;
ll INFL = 1000000000000000010;//10^18 = 2^60
int INF = 2147483600;//10^9
int INFM =100000000;
ll MOD  = 1000000007;

void solve(){
    int N,M;
    cin >> N >> M;
    vector<vector<int>> edge(N, vector<int>(N, -1));
    vector<vector<int>> d(N, vector<int>(N, INFM));
    for(int i = 0; i < N; i++){
        d[i][i] = 0;
    }
    for(int i = 0; i < M; i++){
        int a,b,c;
        cin >> a >> b >> c;
        a--, b--;
        edge[a][b] = c;
        d[a][b] = c;
        d[b][a] = c;
    }
    for(int k = 0; k < N; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    int res = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(edge[i][j] == -1) continue;
            if(edge[i][j] != d[i][j]) res++;
        }
    }
    cout << res << endl;
}



int main(void){
    solve();
}


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

using namespace std;


const int inf=1e9+10;
const int N=2e5+10;
int n,a[N][2];
long long solve(){
        bool equ=1;
        for(int i=1;i<=n;i++) equ&=a[i][0]==a[i][1];
        if (equ) return 0;

        long long sum=0;
        for(int i=1;i<=n;i++) sum+=a[i][0];
        int subx=inf,suby=0;
        for(int i=1;i<=n;i++) {
                if (a[i][0]<a[i][1]) suby=max(suby,a[i][0]);
                if (a[i][0]>a[i][1]) subx=min(subx,a[i][1]);
        }
        return sum-subx;
}
int main(){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i][0]>>a[i][1];
        cout<<solve();
}


Measured memory_bytes: 384
import collections
import sys

input = sys.stdin.readline

n = int(input())
v = list(map(int,input().split()))

v_e = []
v_o = []

for i in range(0,n,2):
    v_e.append(v[i])
for j in range(1,n,2):
    v_o.append(v[j])

if len(collections.Counter(v)) == 1:
    print (n//2)
else:
    v_e_1 = collections.Counter(v_e)
    v_o_1 = collections.Counter(v_o)

    V_E = v_e_1.most_common()
    V_O = v_o_1.most_common()

    if V_E[0][0] == V_O[0][0]:
        a = V_O[1][1] + V_E[0][1]
        b = V_O[0][1] + V_E[1][1]
        print(min([n-a,n-b]))
    else:
        print(n-V_E[0][1]-V_O[0][1])

Measured memory_bytes: 72792
module ABC133

  ! <module>s to import
  use, intrinsic :: iso_fortran_env

  ! require all variables to be explicitly declared
  implicit none

  ! accessibility of <subroutine>s and <function>s in this <module>
  public :: task_C

  ! contained <subroutine>s and <function>s are below
  contains

  subroutine task_C

    ! variables for this <subroutine>
    integer(INT64) :: range_min
    integer(INT64) :: range_max
    integer(INT64) :: buffer
    integer(INT64) :: answer

    ! support variables for this <subroutine>
    integer(INT64) :: itr_sml, itr_lrg

    ! STEP.01
    ! read out given data
    read(unit=INPUT_UNIT, fmt=*) range_min, range_max

    ! STEP.02
    ! calculate the answer of this task
    answer = huge(answer)

    loop_sml: do itr_sml = range_min,         range_max - 1_INT64, 1_INT64
    loop_lrg: do itr_lrg = itr_sml + 1_INT64, range_max,           1_INT64
      buffer = mod(itr_sml * itr_lrg, 2019_INT64)
      if (buffer .lt. answer ) answer = buffer
      if (answer .eq. 0_INT64) exit loop_sml
    end do loop_lrg
    end do loop_sml

    ! STEP.03
    ! output the answer of this task
    write(unit=OUTPUT_UNIT, fmt='(I0)', advance='yes') answer

    ! STEP.END
    return

  end subroutine task_C

end module ABC133

program main

  ! <module>s to import
  use, non_intrinsic :: ABC133

  ! require all variables to be explicitly declared
  implicit none

  call task_C

end program main

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#define N 8
#define Free 0
#define Not_Free 1
#define TRUE 1
#define FALSE -1

int row[N],col[N],dpos[2*N-1],dneg[2*N-1],B[N][N];

void printBoad(){
  int i,j;
  for(i =0;i < N;i++){
    for(j =0;j < N;j++){
      if(B[i][j] == TRUE){
          if(row[i] != j){
             return;
           }
        }
    }
  }
  for(i =0;i < N;i++){
    for(j =0;j < N;j++){
      if(row[i] == j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}int putQueen(int i){
  int j;
  if(i == N){
    printBoad();
    return 0;
  }
  for(j =0;j < N;j++){
    if(col[j] == Not_Free||dpos[i + j] == Not_Free||dneg[i -j+N-1] == Not_Free){
      continue;
    }
    row[i] = j;
    col[j] = dpos[i + j] = dneg[i-j+N-1] = Not_Free;
    putQueen(i + 1);
    row[i] = col[j] = dpos[i + j]  = dneg[i-j+N-1] = Free;
  }
  return 0;
}

int main(){
  int i,j,k,r,c;
  for(i =0;i < N;i++){
    row[i] = Free;
    col[i] = Free;
  }
  for(i =0;i < 2*N -1;i++){
    dpos[i] = Free;
    dneg[i] = Free;
  }
  for(i =0;i < N;i++){
    for(j =0;j < N;j++){
      B[i][j] = FALSE;
    }
  }
  scanf("%d",&k);
  for(i =0;i < k;i++){
    scanf("%d%d",&r,&c);
    B[r][c] = TRUE;
  }
  putQueen(0);
  return 0;
}



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

ll d[305][305], cost[305][305];
int main()
{
    int n, i, j, k;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            scanf("%d", &cost[i][j]);


    for(i = 0; i < n; i++)
        for(j = 0; j < n; j++)
            d[i][j] = INT_MAX;

    for(k = 0; k < n; k++)
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                d[i][j] = min(d[i][j], cost[i][k] + cost[k][j]);


      int flag = 1, road;
      ll sum = 0;
      for(i = 0; i < n; i++)
        for(j = i+1; j < n; j++)
            if(d[i][j] != cost[i][j]) flag = 0;

       if(flag)
       {
          for(i = 0; i < n; i++)
                for(j = i+1; j < n; j++)
                {
                    road = 1;
                    for(k = 0; k < n; k++)
                    {
                        if((d[i][j] == d[i][k] + d[k][j]) && (d[i][j] != d[i][k]) && (d[i][j] != d[k][j])) road = 0;
                    }
                    if(road) sum += d[i][j];
                }

            printf("%lld\n", sum);
       }
       else printf("-1\n");



    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


constexpr array<int, 4> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int h, w; cin >> h >> w;
  V<string> s(h); for (int i = 0; i < h; ++i) cin >> s[i];
  VV<> g(h * w);
  for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {
    for (int k = 0; k < 4; ++k) {
      int ni = i + dx[k], nj = j + dy[k];
      if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;
      if (s[i][j] == s[ni][nj]) continue;
      g[i * w + j].push_back(ni * w + nj);
    }
  }
  V<bool> vis(h * w);
  lint black, white;
  auto dfs = [&](const auto& dfs, int v) -> void {
    ++(s[v / w][v % w] == '#' ? black : white);
    for (int u : g[v]) if (!vis[u]) {
      vis[u] = true;
      dfs(dfs, u);
    }
  };
  lint res = 0;
  for (int v = 0; v < h * w; ++v) if (!vis[v]) {
    black = white = 0;
    vis[v] = true;
    dfs(dfs, v);
    res += black * white;
  }
  cout << res << '\n';
}

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

int main(){
  int n; cin>>n;
  vector<int> a(n);
  for(int i=0; i<n; ++i)cin>>a[i];

  vector<int> b(n);
  for(int i=0; i<n; ++i)b[i]=a[i];

  sort(b.begin(), b.end());

  for(int i=0; i<n; ++i){
    if(a[i]==b[n-1])cout<<b[n-2]<<endl;
    else cout<<b[n-1]<<endl;
  }
}


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int n; cin >> n;
	string s; cin >> s;
	int l = 0;
	int r = n - 1;
	int ret = 0;
	while (l < r) {
		while (s[l]=='R' && l < n) l++;
		while (s[r]=='W' && r > -1) r--;
		if (s[l]=='W' && s[r]=='R' && l < r) {
			ret++;
			l++;
			r--;
		}
	}
	cout << ret << endl;
	return 0;
}

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

using namespace std;

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

#define MOD ll(1e9 + 7)
#define MAXN 100010
#define inf (ll)1e18

template<typename T> inline T smin(T &a, const T &b) { return a > b ? a = b : a; }
template<typename T> inline T smax(T &a, const T &b) { return a < b ? a = b : a; }
inline void add(ll &l, const ll &r) { l = (l + r) % MOD; }
ll gcd(ll v, ll u) { return u ? gcd(u, v % u) : v; }
ll po(ll v, ll u) { return u ? (po(v * v % MOD, u >> 1) * (u & 1 ? v : 1) % MOD) : 1; }

ll x[MAXN], dif[MAXN], dag[MAXN], d[MAXN], cc[MAXN];
vector<ll> dor[MAXN];
ll answer[MAXN];
ll n, m, k;

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> x[i];
	cin >> m >> k;
	for (int i = 1; i < n; i++)
		dif[i] = i;
	for (int i = 0; i < m; i++) {
		int z; cin >> z;
		swap(dif[z], dif[z - 1]);
	}
	for (int i = 1; i < n; i++)
		dag[dif[i]] = i;
	for (int i = 1; i < n; i++) {
		int v = i, cnt = 0;
		while (!d[v]) {
			d[v] = i; cc[v] = cnt++;
			dor[i].push_back(v);
			v = dag[v];
		}
	}
	for (int i = 1; i < n; i++) 
		answer[dor[d[i]][(k + cc[i]) % (int)dor[d[i]].size()]] = i;
	answer[0] = x[0];
	for (int i = 1; i < n; i++)
		answer[i] = answer[i - 1] - x[answer[i] - 1] + x[answer[i]];
	for (int i = 0; i < n; i++)
		cout << answer[i] << '\n';
	//system("pause");
	return 0;
}

Measured memory_bytes: 11392
a,b,c,d = map(int,input().split(' '))

flg = 0

if a == 1 or b == 1 or c == 1 or d ==1:
    flg = flg +1
if a == 9 or b == 9 or c == 9 or d ==9:
    flg = flg +1
if a == 7 or b == 7 or c == 7 or d ==7:
    flg = flg +1
if a == 4 or b ==4 or c  ==4 or d ==4:
    flg = flg +1

if flg == 4:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main(){
    int n;
    cin >> n;
    int a[n];
    int s = 0;
    int S[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        s += a[i];
        S[0] = a[0];
        if(i != 0) S[i] = S[i-1] + a[i];
    }
    int m = abs(s-2*S[0]);
    for(int i = 0; i < n; i++){
        m = min(m, abs(s-2*S[i]));
    }
    cout << m;

}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(int argc, char const *argv[])
{
	int a;
	cin >> a;

	// for(int a = 1; a <= 179; a++ ){
	// cout << "a= " << a << " ";
	if(360 % a == 0){
		cout << 360 / a;
		cout << endl;
	}else{
		int x = 360;
		int ans = 0;
		while(x != 0){
			if(x > 0) x -= a;
			else{
				x += 360;
				x -= a;
			}
			ans++;
		}
		cout << ans;
	}
	// }
	return 0;
}


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

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int N;

int main()
{
	scanf("%d",&N);
	map<int,int> mp;
	vector<int> A(N);
	FOR(i,0,N){
		scanf("%d",&A [i]);
		mp [A [i]]++;
	}

	int cnt = 0;
	for(const auto& it : mp){
		cnt += it.second - 1;
	}
	if(cnt % 2) cnt++;

	printf("%d\n",N - cnt);

	return 0;
}


Measured memory_bytes: 5376
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <cstdint>
#include <algorithm>
#include <utility>
#include <cmath>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
int64_t Q , H , S ,D; cin >> Q >> H >> S >> D;
int64_t N; cin >> N;
int64_t count = 0;
if(min(8*Q,min(4*H,2*S))> D){
	if(N != 1){
		count = D * (N / 2);
		if(N % 2 == 1){
			count += min(4*Q,min(2*H,S));
		}

	}
	else{
		count = min(4*Q,min(2*H,S))*N;
	}
}
else{
	count = min(4*Q,min(2*H,S)) * N;
}

cout << count << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

int* calc(int *l,int n,int a){
  int *dp=(int *)calloc(1<<n,sizeof(int));
  dp[0]=1000000;
  for(int i=1;i<(1<<n);i++){
    int sum=0;
    int cost=-10;
    int j;
    for(j=0;j<n;j++){
      if((i>>j)&1){
	sum+=l[j];
	cost+=10;
      }
    }
    dp[i]=ABS(sum-a)+cost;
  }
  return dp;
}

void run(void){
  int n,a,b,c;
  scanf("%d%d%d%d",&n,&a,&b,&c);
  int l[8];
  int i,j,k;
  for(i=0;i<n;i++) scanf("%d",l+i);
  int *dpA=calc(l,n,a);
  int *dpB=calc(l,n,b);
  int *dpC=calc(l,n,c);
  int min=1000000;
  for(i=1;i<(1<<n);i++){
    for(j=1;j<(1<<n);j++){
      for(k=1;k<(1<<n);k++){
	if((i&j)==0 && (j&k)==0 && (k&i)==0){
	  min=MIN(min,dpA[i]+dpB[j]+dpC[k]);
	}
      }
    }
  }
  printf("%d\n",min);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
using namespace std;
int main(void){
    int x, y, W, H, r;
    cin >> W >> H >> x >> y >> r;
    
    if ( x - r  < 0 || y - r < 0 || W < x + r || H < y + r) {
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
}



Measured memory_bytes: 3088
#include<iostream>

using namespace std;

int main(){
	
	int x,i;
	i=0;
	for(;;){
		cin>>x;
		i=i+1;
		if(x==0)break;
		else{
			cout<<"Case "<<i<<": "<<x<<endl;
		}
	}
	return 0;

}

Measured memory_bytes: 1156
package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)
	s := make([]int, n)
	max1 := 0
	max2 := 0
	for i := 0; i < n; i++ {
		fmt.Scan(&s[i])
		if s[i] > max1 {
			max1, max2 = s[i], max1
		} else if s[i] > max2 {
			max2 = s[i]
		}
	}
	for _, n := range s {
		if n == max1 {
			fmt.Println(max2)
		} else {
			fmt.Println(max1)
		}
	}
}


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

class Procon
{
    public Procon() { }
    static void Main(string[] agrs)
    {
        new Procon().Do();
    }

    Scanner cin;

    public void Do()
    {
        cin = new Scanner();
        long N = cin.nextLong();
        long K = cin.nextLong();

        long pos = 0;
        for (int i = 0; i < N; i++)
        {
            long a = cin.nextLong();
            if (a == 1)
            {
                pos = i;
            }
        }

        long ret = 1000000000;
        for (int i = 0; i < K; i++)
        {
            long left_num = pos - i;
            long right_num = N - pos - 1 - (K - 1 - i);
            if (left_num == 0 && right_num == 0)
            {
                ret = Math.Min(1, ret);
                continue;
            }
            if (left_num < 0 || right_num < 0)
            {
                continue;
            }
            ret = Math.Min(1 + (left_num + K - 2) / (K - 1) + (right_num + K - 2) / (K - 1), ret);
        }
        Console.WriteLine(ret);
    }
}

class Scanner
{
    string[] s;
    int i;
    int max_i;

    public Scanner()
    {
        s = new string[0];
        max_i = 0;
        i = 0;
    }

    public string nextString()
    {
        if (i >= s.Length)
        {
            s = Console.ReadLine().Split(' ');
            max_i = s.Length;
            i = 0;
            if (max_i == 0)
            {
                return "";
            }
            return s[i++];
        }
        else
        {
            return s[i++];
        }
    }

    public int nextInt()
    {
        return int.Parse(nextString());
    }


    public long nextLong()
    {
        return long.Parse(nextString());
    }

    public double nextDouble()
    {
        return double.Parse(nextString());
    }

    public string[] arrayString()
    {
        return Console.ReadLine().Split(' ');
    }

    public int[] arrayInt()
    {
        string[] str = Console.ReadLine().Split(' ');
        int[] array = new int[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = int.Parse(str[i]);
        }
        return array;
    }

    public long[] arrayLong()
    {
        string[] str = Console.ReadLine().Split(' ');
        long[] array = new long[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = long.Parse(str[i]);
        }
        return array;
    }

    public double[] arrayDouble()
    {
        string[] str = Console.ReadLine().Split(' ');
        double[] array = new double[str.Length];
        for (int i = 0; i < str.Length; i++)
        {
            array[i] = double.Parse(str[i]);
        }
        return array;
    }
}

Measured memory_bytes: 20448
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;
using INT = mp::cpp_int;

int main() {
	INT a;
	cin >> a;
	string s;
	cin >> s;
	int b = stoi(s.substr(0, 1)) * 100 + stoi(s.substr(2, 2));
	cout << a * b / 100 << endl;
}


Measured memory_bytes: 3688
class PQueue
  def initialize(n)
    @ar = Array.new(n)
    @c = 0
  end
 
  def push(x)
    i = @c
    @c += 1
    while (i > 0)
      parent = (i - 1) / 2
      break if @ar[parent] <= x
      @ar[i] = @ar[parent]
      i = parent
    end
    @ar[i] = x
  end
 
  def pop
    ans = @ar[0]
    @c -= 1
    x = @ar[@c]
    i = 0
    while (i * 2 + 1 < @c)
      a = i * 2 + 1
      b = a + 1
      a = b if b < @c && @ar[b] < @ar[a]
      break if @ar[a] >= x
      @ar[i] = @ar[a]
      i = a
    end
    @ar[i] = x
    ans
  end
end
 
N = gets.to_i
A = gets.split.map(&:to_i)
 
q = PQueue.new(N)
totB = 0
A.take(N).each do |a|
  q.push a
  totB += a
end

L = A.drop(N).sort
totC = L.take(N).inject(:+)
c = N - 1
mark = Array.new(N * 2, true)
score = totB - totC
A[N, N].each do |a|
  q.push a
  totB += (a - q.pop)
  ind = L.bsearch_index{|l| l >= a}
  if ind > c
    mark[ind] = false
  else
    c += 1
    while !mark[c]
      c += 1
    end
    totC += (L[c] - a)
  end
  tmp = totB - totC
  score = tmp if tmp > score
end
puts score

Measured memory_bytes: 28280
# -*- coding: utf-8 -*-
def inpl(): return tuple(map(int, input().split()))
INF = float("inf")
V, E, r = inpl()

edges = [inpl() for _ in range(E)]

def belman_ford(V, edges, r):
    "If glaph contains negative cycles then return True"
    D = [INF]*(V)
    D[r] = 0
    if V == 1:
        return False, [0]
    
    for _ in range(V-1):
        update = False
        for s, t, d in edges:
            if D[t] > D[s] + d:
                D[t] = D[s] + d
                update = True
        if not update:
            break
    else:
        return True, D
    return False, D
    
NEGATIVE, D = belman_ford(V, edges, r)

if NEGATIVE:
    print("NEGATIVE CYCLE")
else:
    for d in D:
        print("INF") if d == INF else print(d)


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

int main(){
   	long long int a, b, n;
    cin >> a >> b >> n;
    long long int p = min(n,b);
    if(p % b == 0)
        cout << a*(p-1)/b << "\n";
    else
        cout << a*(p)/b << "\n";
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
int main () {
  long N;
  cin >> N;
  vector<long> data(101);
  long a;
  for(int i = 1; i <= N; i++){
    a = i;
    for(int j = 2; j <= 100; j++){
      while(a % j == 0){
        a /= j;
        data.at(j)++;
      }
    }
  }
  vector<long> ans(5);
  for(int i = 0; i <= N; i++){
    if(data.at(i) >= 2)ans.at(0)++;
    if(data.at(i) >= 4)ans.at(1)++;
    if(data.at(i) >= 14)ans.at(2)++;
    if(data.at(i) >= 24)ans.at(3)++;
    if(data.at(i) >= 74)ans.at(4)++;
  }
  cout << ans.at(4) + ans.at(3) * (ans.at(0) - 1) + ans.at(2) * (ans.at(1) - 1) + ans.at(1) * (ans.at(1) - 1) * (ans.at(0) - 2) / 2<< endl;
  return 0;
}

Measured memory_bytes: 256
import sys

a1i = list(map(int, input().split()))
a2i = list(map(int, input().split()))
a3i = list(map(int, input().split()))
n = int(input())
bi = [int(input()) for i in range(n)]

for b in bi:
    a1i = [0 if a == b else a for a in a1i]
    a2i = [0 if a == b else a for a in a2i]
    a3i = [0 if a == b else a for a in a3i]
    
for i in range(3):
    if (a1i[i] == 0 and a2i[i] == 0 and a3i[i] == 0):
        print('Yes')
        sys.exit()

if (a1i[0] == 0 and a2i[1] == 0 and a3i[2] == 0) \
    or (a1i[2] == 0 and a2i[1] == 0 and a3i[0] == 0):
        print('Yes')
        sys.exit()
        
if (len(set(a1i)) == 1 or len(set(a2i)) == 1 or len(set(a3i)) == 1):
    print('Yes')
    sys.exit()

print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <tuple>

#define rep(i,n) for(ll i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
using Graph = vector<vector<ll>>;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
//	std::cout<<std::fixed<<std::setprecision(10);

ll f(ll n) {
	ll res = 0;
	ll tmp_n = n;
	while(tmp_n%2==0) {
		res++;
		tmp_n = tmp_n >> 1;
	}
	return res;
}

int main() {
	ll N, M;
	cin >> N >> M;
	vector<ll> a(N);
	
	ll tmp_a;
	cin >> tmp_a;

	ll fa = f(tmp_a);
	if(fa==0) {
		cout << 0 << endl;
		return 0;
	}

	a[0] = tmp_a>>fa;

	for(ll i = 1; i<N; i++) {
		cin >> tmp_a;
		if(fa == f(tmp_a)) {
			a[i] = tmp_a>>fa;
		} else {
			cout << 0 << endl;
			return 0;
		}
	}

	ll L = 1;
	rep(i, N) {
		L = lcm(L, a[i]);
		if(L > M) {
			cout << 0 << endl;
			return 0;
		}
	}
	
	M >>= fa-1;

	ll ans = dup(M/L, 2);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
""" import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(int(not_d))
 """

a, b, c, d = map(int, input().split())

total = b - a + 1


def lem(A, B):
	AB = A * B
	while B != 0:
		A, B = B, A % B
	return AB // A


bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = total - bsep + asep
print(ans)


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main(){
	int data[101],n,ans;
	for(int i=1;i<101;i++){
		data[i]=0;
	}
	while(cin>>n){
		data[n]++;
	}
	for(int i=1;i<101;i++){
		ans=max(ans,data[i]);
	}
	for(int i=1;i<101;i++){
		if(data[i]==ans)cout<<i<<endl;
	}
	return 0;
}

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

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

    string ans = "No";
    while(n > 0) {
        if (n % 4 == 0) ans = "Yes";
        n -= 7;
    }

    if (n == 0) ans = "Yes";

    cout << ans << endl;
}

Measured memory_bytes: 3600
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.StringTokenizer;
import java.util.Scanner;
import java.lang.*;
import java.io.*;
import java.util.*;
import java.lang.Integer;
import java.util.HashMap;

public class Main {
    // driver function to test the above functions
    public static void main(String args[]) throws IOException {
        Reader.init(System.in);
        int n = Reader.nextInt();
        int m = Reader.nextInt();
        int[] arr = new int[n];

        double sum  = 0;
        for (int i=0; i<n; i++){
            arr[i] = Reader.nextInt();
            sum = sum+arr[i];
        }
        sum = (double)(sum/(4*m));
        int ans=0;
        for (int i=0; i<n; i++){
            int val = arr[i];
            if (val>=sum){
                ans++;
            }
        }
        if (ans>=m) {
            System.out.println("Yes");
        }
        else {
            System.out.println("No");
        }

    }
}

class Node{
    char val;
    Node nxt = null;
    Node prev=null;


}



class solu{

}

/** Class for buffered reading int and double values */
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }

    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }

    static String line() throws IOException {
        return reader.readLine();
    }
}

Measured memory_bytes: 20692