akhauriyash/Code-Regression huggingface dataset:
import java.io.*
import java.util.*

const val MOD = 1000000007L
fun solve(N: Int, K: Int, A: LongArray) {
    // Sum[i in 0..N-1, j in i+k..N-1](Aj - Ai) * j-i-1 C k-2
    // j-i=pを固定する p in k..N-k-1
    if (K == 1) {
        println(0)
        return
    }
    A.sort()
    val accSum = A.toList().scanLeft(0L) { a, b -> a + b }.toList()
    val invs = calcModInvs(N, MOD)
    val binomials = LongArray(N) // i C K-2
    binomials[K - 2] = 1L
    for (i in K - 1 until N) {
        // i C k - 2 = i-1 C k-2 * i/(i - k + 2)
        binomials[i] = (((binomials[i - 1] * i) % MOD) * invs[i - K + 2]) % MOD
    }
    // println(invs.toList())
    // println(binomials.toList())
    var ans = 0L
    for (p in K - 1 until N) {
        val ret = ((accSum[N - 1] - accSum.getOrElse(p - 1) { 0L } - accSum.getOrElse(N - p - 1) { 0L }) % MOD) * binomials[p - 1]
        ans = (ans + ret % MOD) % MOD
    }
    println(ans)
    return
}

fun calcModInvs(num: Int, mod: Long): LongArray {
    // num以下のmodで割った余りの逆元を計算
    val invs = LongArray(num + 1)
    invs[1] = 1L
    for (i in 2L..num.toLong()) {
        invs[i.toInt()] = (invs[(mod % i).toInt()] * (mod - mod / i)) % mod
    }
    return invs
}

fun <T, R> Iterable<T>.scanLeft(initial: R, operation: (acc: R, T) -> R): Sequence<R> {
    var last = initial
    return this.asSequence().map { last = operation(last, it); last }
}
fun Long.modPow(x: Long, mod: Long): Long {
    // this ^ x % mod
    tailrec fun binModPow(a: Long, exp: Long): Long = when (exp) {
        // a ^ (2^(exp)) % mod
        0L -> a % mod
        else -> binModPow(a * a % mod, exp - 1)
    }
    return (0..63).asSequence()
        .map { (x shr it) and 1 }
        .withIndex()
        .filter { it.value > 0 }
        .map { binModPow(this, it.index.toLong()) }
        .reduce { a, b -> a * b % mod }
}

// 1 / x % mod (x ⊥ mod)
fun Long.modInv(mod: Long): Long = this.modPow(mod - 2, mod)

fun binomialMod(n: Int, k: Int, mod: Long): Long = when (k) {
    // nCk % mod
    0, n -> 1L
    else -> {
        val numer = (n downTo n - k + 1)
            .map { it.toLong() }
            .reduce { a, b -> (a * b) % mod }
        val denom = (1..k)
            .map { it.toLong() }
            .reduce { a, b -> (a * b) % mod }
        (numer * denom.modInv(mod)) % mod
    }
}

fun main(args: Array<String>) {
    fun StringArray(size: Int, init: (Int) -> String = { "\u0000" }): Array<String> {
        return Array<String>(size, init)
    }
    class Scanner(stream: InputStream) {
        private val reader = BufferedInputStream(stream).bufferedReader()
        private var st: StringTokenizer? = null
        fun next(): String {
            while (!(st?.hasMoreTokens() ?: false)) st = StringTokenizer(reader.readLine())
            return st!!.nextToken()
        }
    }
    val sc = Scanner(System.`in`)
    val N = sc.next().toInt()
    val K = sc.next().toInt()
    val A = LongArray(N.toInt())
    for (i in 0 until N.toInt()) {
        A[i] = sc.next().toLong()
    }
    solve(N, K, A)
}


Measured memory_bytes: 54844
import heapq
n,m=[int(i) for i in input().split()]
a=[int(i) for i in input().split()]
heap=[]
for i in a:
    heapq.heappush(heap,10**5-i)

for i in range(m):
    tmp=heapq.heappop(heap)
    tmp=(10**5-tmp)//2
    heapq.heappush(heap,10**5-tmp)

ans=0
for i in range(n):
    ans+=10**5-heap[i]
print(ans)

Measured memory_bytes: 64920
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <complex> // complex<double> a(1.2 , 2.3);// real(): 1.2, imag()2.3
using namespace std;

#define MOD 1000000007
#define ll long long
#define ld long double
#define FOR(i,a,b) for(ll i=(ll)a;i<(ll)b;i++)
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rmsame(a) sort(all(a)),a.erase(unique(all(a)), a.end())
#define rmvector(a,b) rep(i,a.size())rep(j,b.size())if(a[i]==b[j]){a.erase(a.begin()+i);i--;break;}
template<typename X> bool exist(vector<X> vec, X item){return find(all(vec), item)!=vec.end();}

ll N, C;
ll cost[31][31]; // cost[from][to]

ll color[3][31]; // [(i+j)%3][color] の数

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

    cin >> N >> C;
    rep(i, C)rep(j, C){
        cin >> cost[i][j];
    }
    rep(i, N)rep(j, N){
        ll inp;
        cin >> inp;
        inp--;
        color[(i+j)%3][inp] ++;
    }

    ll ans = 1e9;
    rep(p0, C)rep(p1, C)rep(p2, C){
        ll c[3];
        c[0] = p0; c[1] = p1; c[2] = p2;
        if(c[0] == c[1]) continue;
        if(c[1] == c[2]) continue;
        if(c[2] == c[0]) continue;

        ll ret = 0;
        rep(i,3){
            rep(j, C){
                ret += cost[j][c[i]] * color[i][j];
            }
        }
        ans = min(ret, ans);

    }


    cout << ans << endl;
    //cout << fixed << setprecision(16) << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma region
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << (#x) << "] = [", _print(x)
#else
#define debug(x...)
#endif
#pragma endregion
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define sz(v) int((v).size())
#define int ll
#pragma region
#define f first
#define s second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#pragma endregion


string s;
int dp[1'111'111][2];
void solve()
{
    cin>>s;
    int n = sz(s);
    dp[0][1] = 1e17;
    forn(i, n)
    {
        dp[i+1][0] = min(dp[i][0] + s[i]-'0', dp[i][1]+s[i]-'0');
        dp[i+1][1] = min(dp[i][0] + 10 - (s[i]-'0') + 1, dp[i][1] + 9 - (s[i] - '0') );
    }
    cout << min(dp[n][0], dp[n][1]) << '\n';
}

signed main()
{
    int T = 1;
    ios_base::sync_with_stdio(0); cin.tie(0);
    cout << fixed << setprecision(22);
    //cin >> T;
    for(int i=1;i<=T;++i)
    {
        //cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}


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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    ll x;
    cin >> x;
    if(x >= 30){
        cout << "Yes" << endl;
    }else cout << "No" << endl;

    return 0;
}

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

int main()
{
  int W, a, b;
  cin >> W >> a >> b;
  if (a < b)
  {
    if (b - (a + W) <= 0)
      cout << 0 << endl;
    else
      cout << b - (a + W) << endl;
  }
  else
  {
    if (a - (b + W) <= 0)
      cout << 0 << endl;
    else
      cout << a - (b + W) << endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
 
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)
 
typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;
 
constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
 
int main() {
    int N,M; cin>>N>>M;
    int X[M]; REP(i,M) cin>>X[i];
    if (N>=M) {
        cout<<0<<endl;
        return 0;
    }
    sort(X,X+M);
    int diff[M-1];
    REP(i,M-1) {
        diff[i] = X[i+1]-X[i];
        cerr<<diff[i]<<endl;
    }
    sort(diff,diff+M-1);
    int tmp = 0;
    REP(i,N-1) {
        tmp += diff[M-2-i];
    }
    cerr<<tmp<<endl;
    cout<<X[M-1]-X[0]-tmp<<endl;
}


Measured memory_bytes: 1024
//By Ralif Rakhmatullin
#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
#include<math.h>
#include<cassert>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<bitset>
#include<valarray>
#include<iterator>
#include<list>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define S second
#define ld long double
#define F first
#define y1 LOL
#define ld long double
#define pb push_back
#define len length
#define sz size
#define beg begin
const ll INF = (ll)1e18 + 123;
const int inf=(int)2e9 + 123; 
const int mod=1e9+7;
using namespace std;
int n, k;
map<ll, int> f;
ll a[400011], p[400011], b[400011], pref[400011];
vector<ll> v;
int sz = 0;
void add(int x){
	for(int i = x; i <= sz; i = (i | (i + 1))){
		p[i] ++;
	}
}
int sum(int x){
	int res = 0;
	for(int i = x; i > 0; i = (i & (i + 1)) - 1)
		res += p[i];
	return res;
}
vector<ll> :: iterator it;
int main(){
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  	srand(FOR);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
		b[i] = pref[i] - 1ll * k * i;
		v.pb(b[i]);
	}
	v.pb(0);
	sort(v.beg(), v.end());
	it = unique(v.beg(), v.end());
	v.resize(distance(v.beg(), it));
	for(int i = 0; i < v.sz(); i ++){
		if(i > 0 && v[i] == v[i - 1])
			break;
		sz ++;	
		f[v[i]] = i + 1;
	//	cout << v[i] << " " << i + 1 << endl;
	}
	add(f[0]);
	ll ans = 0;
	for(int i = 1; i <= n; i ++){
//		cout << f[b[i]] << " ";
		ans += sum(f[b[i]]);
		add(f[b[i]]);
	}
//	cout << endl;
	cout << ans;
	return 0;
}

Measured memory_bytes: 26096
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define MAX 1000
#define INF 1<<30
using namespace std;
int V,E,cost[MAX][MAX],from,to,Cost;
bool used[MAX];
int mincost[MAX];

int prim(){
  int ans = 0;
  for(int i=0;i<V;i++){
    used[i] = false;
    mincost[i] = INF;
  }
  mincost[0] = 0;

  while(true){
    int v = -1;
    for(int i=0;i<V;i++){
      if(!used[i] && (v == -1 || mincost[i] < mincost[v]))v = i;
    }
    if(v == -1)break;
    used[v] = true;
    ans += mincost[v];

    for(int i=0;i<V;i++){
      mincost[i] = min(mincost[i],cost[v][i]);
    }
  }


  return ans;

}

int main(){
  
  
  while(cin >> V && V){
    for(int i=0;i<MAX;i++)for(int j=0;j<MAX;j++)cost[i][j] = INF;
    cin >> E;
    for(int i=0;i<E;i++){
      scanf("%d,%d,%d\n",&from,&to,&Cost);
      cost[from][to] = cost[to][from] =  Cost;
    }
    
    cout <<  prim()/100 - (V-1) << endl;

  }
  return 0;
}

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

int main ()

{
    int n;
    cin >> n;
    n = n%10;
    if (n==0 || n==1 || n==6 || n==8)
        cout << "pon" << endl;
    else if (n==3)
        cout << "bon" << endl;
    else
        cout << "hon" << endl;
    return 0;
}


Measured memory_bytes: 3592
import bisect

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

a.sort()
c.sort()

ans = 0

for i in b:
	ans += (bisect.bisect_left(a,i)) * (len(c) - bisect.bisect_right(c,i))

print(ans)


Measured memory_bytes: 23328
/***********************
*  Author: xuziyuan    * 
***********************/

#include <bits/stdc++.h>

#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define replet(c) for(char c='a';c<='z';c++) 
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair
#define sqr(a) ((a)*(a))

using namespace std;

const LL MOD=1e9+7;

LL n,a[100010],dp[100010][2];

int main()
{
	cin>>n;
	repn(i,n) scanf("%I64d",&a[i]);
	rep(i,100005) rep(j,2) dp[i][j]=-1e18;
	dp[0][0]=0;
	repn(i,n)
	{
		if(a[i]==0)
		{
			dp[i][1]=-1e18;
			dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
			continue;
		}
		if(a[i]%2==0)
		{
			if(dp[i-1][1]>0) 
			{
				dp[i][0]=max(dp[i][0],max(dp[i-1][0]+a[i]/2,dp[i-1][1]+a[i]/2));
				dp[i][1]=max(dp[i][1],dp[i-1][1]+1+a[i]/2-1);
				//cout<<i<<' '<<0<<' '<<dp[i][0]<<endl<<i<<' '<<1<<' '<<dp[i][1]<<'a'<<endl;
			}
			else
			{
				dp[i][0]=max(dp[i][0],dp[i-1][0]+a[i]/2);
				dp[i][1]=-1e18;
				//cout<<i<<' '<<0<<' '<<dp[i][0]<<endl<<i<<' '<<1<<' '<<dp[i][1]<<'b'<<endl;
			}
		}
		else
		{
			if(dp[i-1][1]>0)
			{
				dp[i][0]=max(dp[i][0],dp[i-1][1]+1+a[i]/2);
				dp[i][1]=max(dp[i][1],max(dp[i-1][1]+a[i]/2,dp[i-1][0]+a[i]/2));
				//cout<<i<<' '<<0<<' '<<dp[i][0]<<endl<<i<<' '<<1<<' '<<dp[i][1]<<'c'<<endl;
			}
			else
			{
				dp[i][0]=-1e18;
				dp[i][1]=max(dp[i][1],dp[i-1][0]+a[i]/2);
				//cout<<i<<' '<<0<<' '<<dp[i][0]<<endl<<i<<' '<<1<<' '<<dp[i][1]<<'d'<<endl;
			}
		}
	}
	//cout<<dp[6][1]<<endl;
	cout<<max(dp[n][0],max(dp[n][1],0LL))<<endl;
	rt0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int n, count = 0;
	cin >> n;

	vector<double> a(n);
	for(int i=0;i<n;i++){
		cin >> a.at(i);
		if(a.at(i)==count+1) count++;
	}

	if(count==0) cout << -1 << endl;
	else cout << n - count << endl;
}

Measured memory_bytes: 1792
#include<deque>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<cmath>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){
  int i,j;
  int n,u;
  while(cin>>n>>u,n||u){
    int a[20],b[20]={};    
    for(i=0;i<n;++i){
      cin>>a[i];
      int m;
      cin>>m;
      for(j=0;j<m;++j){
	int p;
	cin>>p;
	b[i]|=1<<p;
      }
    }
    bool c[1<<20]={};
    c[0]=true;
    queue<pair<pair<int,int>,int> > d;
    d.push(make_pair(make_pair(0,0),0));
    while(!d.empty()){
      int p,q,r;
      p=d.front().first.first;
      q=d.front().first.second;
      r=d.front().second;
      if(q>=u)
	break;
      d.pop();
      for(i=0;i<n;++i){
	if((p&(1<<i))||(p&b[i])!=b[i]||c[p|(1<<i)])
	  continue;
	c[p|(1<<i)]=true;
	d.push(make_pair(make_pair(p|(1<<i),q+a[i]),r+1));
      }
    }
    cout<<d.front().second<<endl;
  }
  return 0;
}

Measured memory_bytes: 4244
#include<cstdio>
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 300
int a[MN+5][MN+5],l[MN+5],u[MN+5],s[MN+5];
int main()
{
	int n,m,i,j,ans;
	ans=n=read();m=read();
	for(i=1;i<=n;++i)for(j=1;j<=m;++j)a[i][j]=read();
	for(i=1;i<=n;++i)++s[a[i][l[i]=1]];
	while(true)
	{
		for(i=j=1;i<=m;++i)if(s[i]>s[j])j=i;
		if(s[j]<ans)ans=s[j];
		for(u[j]=i=1;i<=n;++i)
		{
			while(l[i]<=m&&u[a[i][l[i]]])
				--s[a[i][l[i]]],++s[a[i][++l[i]]];
			if(l[i]>m)return 0*printf("%d",ans);
		}
	}
}

Measured memory_bytes: 512
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
typedef long long int LL;
//typedef __int64 LL;

const LL MOD = 1000000007;
LL dp1[2010][2010];
LL sdp1[2010][2010];
LL dp2[2010][2010];

int main()
{
	for (int i = 0; i <= 2004; i++) {
		for (int j = 0; j <= 2004; j++) {
			if (i == 0 || j == 0) {
				sdp1[i][j] = 1;
			}
			else {
				sdp1[i][j] = (sdp1[i][j - 1] + sdp1[i - 1][j - 1]) % MOD;
			}
		}
	}

	for (int i = 0; i <= 2004; i++) {
		for (int j = 0; j <= 2004; j++) {
			sdp1[i][j] = (sdp1[i][j] + sdp1[i - 1][j]) % MOD;
		}
	}

	for (int i = 0; i <= 2004; i++) {
		for (int j = 0; j <= 2004; j++) {
			if (j) {
				dp1[i][j] = sdp1[i][j - 1];
			}
			else {
				dp1[i][j] = 1;
			}
		}
	}

	for (int i = 0; i <= 2004; i++) {
		for (int j = 0; j <= 2004; j++) {
			if (i == 0 && j == 0) {
				dp2[i][j] = 1;
			}
			else if (j == 0) {
				dp2[i][j] = 0;
			}
			else if (i == 0) {
				dp2[i][j] = 1;
			}
			else {
				dp2[i][j] = (dp2[i - 1][j - 1] + dp2[i][j - 1]) % MOD;
			}
		}
	}

	int AA, BB;
	scanf("%d %d", &AA, &BB);

	LL ans = 0;
	{
		for (int a = 0; a <= AA; a++) {
			// first, a ta r.
			// then, 1 ta b.
			int A = AA - a;
			int B = BB - 1;

			int j = B;
			for (int i = 0; i <= MIN(A, B); i++) {
				LL way1 = dp2[i][j];
				LL way2 = dp1[A - i][i];
				ans = (ans + way1 * way2) % MOD;
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}


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

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

    int n;
    cin >> n;
    vector<int> as(n);
    for (int i = 0; i < n; i++) {
        cin >> as[i];
    }
    sort(as.begin(), as.end());
    int ans = 0;
    for (int k = 0; k < 101010; k++) {
        if (lower_bound(as.begin(), as.end(), k) - as.begin() == n / 2) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
while True:
    n,k = map(int, input().split())
    if n == k == 0:
        break
    s = [int(x) for x in input().split()]
    for _ in range(n):
        b = [int(x) for x in input().split()]
        for i in range(k):
            s[i] -= b[i]
    print("Yes" if min(s) >= 0 else "No")

Measured memory_bytes: 7632
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <utility>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
using namespace std;
#define INF 1000000007
#define LINF 1000000000000000007
#define MOD 1000000007
#define int long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define repb(i, n) for (int i = n - 1; i >= 0; i--)
#define MODE 1
#ifdef MODE
#define DEB(X) cout << #X << ": " << X << " ";
#define ARDEB(i, X) cout << #X << "[" << i << "]: " << X[i] << " ";
#define END cout << endl;
#else
#define DEB(X) \
    {          \
    }
#define ARDEB(i, X) \
    {               \
    }
#define END \
    {       \
    }
#endif
typedef pair<int, int> P;
struct edge{int to,cost;};
typedef long long ll;

int ans,ans2;



signed main(){

    int n,a[111111];
    cin>>n;
    rep(i,n)cin>>a[i];
    sort(a,a+n);
    cout<<a[n/2]-a[n/2-1]<<endl;
    
}


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

using namespace std;
using ll = long long;
using ld = long double;

int main() {
    ios_base::sync_with_stdio(0);
    cout.tie(0); cin.tie(0);
    int n;
    cin >> n;
    vector<int> dp(n), v(n);
    for (int &e : v) {
        cin >> e;
    }
    dp[1] = abs(v[1] - v[0]);
    for (int i = 2; i < n; i++) {
        dp[i] = min(dp[i - 1] + abs(v[i] - v[i - 1]), dp[i - 2] + abs(v[i] - v[i - 2]));
    }
    cout << dp[n - 1];
}


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

using namespace std;

int main(){

    cin.sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //freopen("input.txt", "r", stdin);

    int a, b, t;

    cin >> a >> b >> t;

    cout << t / a * b;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <map>
using ll=long long;
using namespace std;
//const int INF = 7+(1e+9);
ll GCD(ll x, ll y)
{
    if (y == 0)
    {
        return x;
    }
    else
    {
        return GCD(y, x % y);
    }
}
ll LCM(ll x, ll y)
{
    return x / GCD(x, y) * y;
}
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};
vector<vector<char>> vec(12,vector<char>(12));

int dx[]={0,-1,0,1};
int dy[]={1,0,-1,0};
int dfs(int y,int x){
    vec[y][x]='5';
    for(int i=0;i<4;i++){
        if(x+dx[i]<12&&x+dx[i]>=0&&y+dy[i]<12&&y+dy[i]>=0&&vec[dy[i]+y][dx[i]+x]=='1'){
            dfs(y+dy[i],x+dx[i]);
        }
    }
    return 0;
}
int main(){
    int q;
    cin>>q;
    vector<int> vec;
    for(int i=0;i<q;i++){
        int x;
        cin>>x;
        if(x==0){
            int y;cin>>y;
            vec.push_back(y);
        }else if(x==1){
            int y;cin>>y;
            cout<<vec[y]<<endl;
        }else{
            vec.pop_back();
        }
    }
}


Measured memory_bytes: 3872
#!/usr/bin/env python
# -*- coding: utf-8 -*-


from sys import stdin
import math
N,D  = [int(x) for x in stdin.readline().rstrip().split()]

all_point = []
total_sq = 0
cnt = 0

for i in range(N):
    X  = [int(x) for x in stdin.readline().rstrip().split()]
    all_point.append(X)

for i in range(N):
    for j in range(i+1,N):
        total_sq = 0
        for k in range(D):
            total_sq += (all_point[i][k] - all_point[j][k])**2
        distance = math.sqrt(total_sq)
        if math.floor(distance) == math.ceil(distance):
            cnt += 1

print(cnt)


Measured memory_bytes: 3064
//Face Produces Unhappiness

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define nvarep(n,a) ll n;cin>>n;vector<ll>a(n);rep(i,0,n)cin>>a[i]
#define vecrep(n,a,type) vector<type>a(n);rep(i,0,n)cin>>a[i]
#define YN(flag) (flag?"Yes":"No")
#define lcm(a,b) (a/__gcd(a, b)*b)
#define range(a) (a).begin(),(a).end() 
#define pb push_back
#define mp make_pair
#define nnn "\n"
#define spa " "
using P = pair<ll,ll>;
using graph = vector<vector<ll>>;
const int inf = 2147483647;//2*10^9
const ll INF = 9223372036854775807;//9*10^18

signed main (){
    int n,k;string s;cin>>n>>k>>s;
    int t=0,h=0;
    rep(i,0,n){
        if(i==0){if(s[i]=='R'&&s[i+1]=='L')t++;else if(s[i]=='L')h++;}
        else if(i==n-1){if(s[i]=='L'&&s[i-1]=='R')t++;else if(s[i]=='R')h++;}
        else if(s[i]=='R'&&s[i+1]=='L')t++;
        else if(s[i]=='L'&&s[i-1]=='R')t++;
    }
    rep(i,0,k){
        if(t>0)t-=2;
        else if(h>1)h--;
        else break;
    }
    if(h==0&&t==0)h++;
    cout<<n-t-h<<nnn;
    return 0;
}

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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0) 

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }
    
    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}
int main() {
	int n = ri();
	int k = ri();
	s64 sum[n];
	s64 sum_g[n];
	int a[n];
	FOR(i,n) a[i] = ri(), sum[i] = i ? sum[i-1]+a[i] : a[i], sum_g[i] = i ? sum_g[i-1]+max(0,a[i]) : max(0,a[i]);
	
	s64 res = -LINF;
	FOR(i,n-k+1) {
		// do
		s64 r0 = sum[i+k-1];
		if (i) r0 -= sum[i-1];
		r0 = max((s64)0LL,r0);
		if (i) r0 += sum_g[i-1];
		r0 += sum_g[n-1];
		r0 -= sum_g[i+k-1];
		res = max(res,r0);
	}
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 2176
def c_same_integers(A, B, C):
    # A,B,Cの和と、これらのうち最大のもの(Mとする)との偶奇が一致するなら、
    # 最終的に3つの整数はMとなる
    # 偶奇が一致しないなら、最終的に3つの整数はM+1となる
    m = max(A, B, C)
    parity = 3 * max(A, B, C) % 2 == (A + B + C) % 2
    max_value = m if parity else m + 1
    # 3数の和は1回の操作で2増えるため,ans回の操作が必要
    ans = (3 * max_value - (A + B + C)) // 2
    return ans

A,B,C = [int(i) for i in input().split()]
print(c_same_integers(A, B, C))

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


int main(){
  int i,n;
  cin >> n;
  int ans=0;
  if(n%10==0){
    ans=10;
  }else{
    while(n>=1){
      ans=ans+n%10;
      n=n/10;
    }

  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

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

    sort(a, a+N, greater<int>());

    int A = 0;
    int B = 0;

    for (int i = 0; i < N; i++){
        if(i % 2 != 1){
            A += a[i];
        }else{
            B += a[i];
        }
    }

    //printf("%d,%d\n",A,B);

    int result;
    result = A-B;

    cout << result << endl;

    return 0;
}


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

int A,B,C,X,Y;

int main(){
	scanf("%d%d%d%d%d",&A,&B,&C,&X,&Y);
	if(C*2>A+B){
		printf("%d\n",A*X+B*Y);
	}
	else {
		int D=C*2,num=min(X,Y),ans=0;
		ans+=D*num;
		X-=num;Y-=num;
		if(X){
			if(D<A)ans+=D*X;
			else ans+=X*A;
		}
		else {
			if(D<B)ans+=D*Y;
			else ans+=B*Y;
		}
	printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include<functional>
#include<numeric>
#include<queue>
#include<stack>
#include<map>
#include<unordered_map>
#include<set>
#include<bitset>
#include<random>

#pragma region
using namespace std;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define rep(i,n) FOR(i,0LL,n)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define rrep(i,n) RFOR(i,0LL,n)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define COUNT(a,y,x) upper_bound(all(a), y) - lower_bound(all(a), x)
#define UNIQUE(a) sort(all(a)); a.erase(unique(all(a)), a.end())
#define pb push_back
typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef map<ll, ll> MAP;
const ll inf = 1LL << 61;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;

ll n = 0, m = 0, ans = 0, tmp = 0, ma = -inf, mi = inf;
string s;
bool ok;
ll dx[9] = { 0,1,0,-1,0,1,1,-1,-1 }, dy[9] = { 0,0,1,0,-1,1,-1,1,-1 };
#define endl '\n'
#pragma endregion
#define MAX 222222



ll a[MAX];


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


  cin >> n >> m;
  rep(i, n) cin >> a[i];

  rep(le, n + 1) FOR(ri, le, n + 1) {
    vll v;
    rep(i, le) v.pb(a[i]);
    FOR(i, ri, n) v.pb(a[i]);
    ll cnt = m - v.size();
    if (cnt < 0) continue;
    sort(all(v));
    rep(i, v.size()) {
      if (!cnt || v[i] >= 0) break;
      v[i] = 0;
      cnt--;
    }
    tmp = accumulate(all(v), 0LL);
    ans = max(ans, tmp);
  }
  cout << ans << endl;


  return 0;
}

Measured memory_bytes: 256
import java.util.*; 

class Main{
public static void main(String[] args){
	Scanner sc=new Scanner(System.in);
        double n=sc.nextDouble();
        double k=sc.nextDouble();
  		double kaku=1/n;
  		double ans=0;
  		int d=0;
		
  		
		for(int c=1;c<=n;c++){
          	d=c;
    		while(d<k){
             kaku*=0.5;
             d*=2;
            }
          ans+=kaku;
          
          kaku=1/n;
    	}
    
    	System.out.println(ans);
    }
}

Measured memory_bytes: 23252
#include<algorithm>
#include<bitset>
#include<cmath>
#include<complex>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<iterator>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;
typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define D()
#define INF 1000000000000
#define MOD 10000007
#define MAXR 100000
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INITA(a,i,j,v) for(ll k=i;k<=j;k++){a[k]=v;}

int main() {
    ll n;
    ll a[200001]; INITA(a, 0, 200000, 0);
    ll total = 0;
    cin >> n;
    REP(i, n) {
        cin >> a[i];
        total += a[i];
    }
    ll res = 1e17;
    ll current = 0;
    ll rest = 0;
    REP(i, n-1) {
        current += a[i];
        rest = total - current;
        res = min(res, abs(rest - current));
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 1792
import java.io.*;
class Main {
	public static void main(String[] args) {
		try {
			BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
			System.out.println(reader.readLine().toUpperCase());
		}
		catch(IOException e) {
			System.out.println(e);
		}
	}
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define FOR(i,a,b) for(ll (i)=(a);(i)<(b);(i)++)
#define FORR(i,a,b) for(ll (i)=(b)-1;(i)>=(a);(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
vl modinv;
void fillModInv(ll n, ll mod){
  modinv = vl(n+1);
  modinv[1] = 1;
  FOR(i,2,n+1){
    modinv[i] = modinv[mod%i] * (mod - mod/i) % mod;
  }
}
/*}}}*/
int main() {
  string s;
  cin >> s;

  string ans = "Yes";
  if(s[0]==s[1] && s[1]==s[2] && s[0]==s[2]) ans = "No";
  
  //cout << fixed << setprecision(10);
  cout << ans << endl;
  return 0;
}


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

int main()
{
	
	for (int i = 0; i < 3; i++)
	{
		int h, m, s;
		cin >> h >> m >> s;
		int a = h * 3600 + m * 60 + s;
		cin >> h >> m >> s;
		int b = h * 3600 + m * 60 + s;
		cout << (b - a) / 3600 << " " << ((b- a) % 3600) / 60 << " " << ((b - a) % 3600) % 60 << endl;
	}
	

}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

int main(void){
    ll n;
    cin >> n;
    
    ll a[n];
    for(ll i = 0; i < n; i++){
        cin >> a[i];
    }
    
    ll counter = 0;
    
    for(ll i = 0; i < n; i++){
        if(a[i] % 2 != 0){
            counter++;
        }
    }
    
    
    if(counter % 2 != 0){
        cout << "NO" << endl;
    } else {
        cout << "YES" << endl;
    }
}


Measured memory_bytes: 1024
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

# カードN枚
# 各カードには1か2が書かれている
N, M = getNM()
# A1 + A2 + 1は偶数
query = []

for i in range(M):
    a, b, c = getNM()
    query.append([a, b, c])

U = UnionFind(N)
for i in query:
    U.union(i[0] - 1, i[1] - 1)

print(U.group_count())

Measured memory_bytes: 96856
#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long

int32_t main(){
	IOS;
	int n;
	cin >> n;
	int arr[n];
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	sort(arr, arr+n);
	int ans = arr[n-1], pos = n-2, lft = n-3;
	while( lft >= 0 ){
		ans += arr[pos];
		lft--;
		if( lft >= 0 )
			ans += arr[pos], lft--;
		pos--;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 5236
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val N, K = sc.nextInt()
  val h = Array.fill(N)(sc.nextInt()).sorted
  println((0 to N - K).fold(Int.MaxValue)((acc, i) => (h(i + K - 1) - h(i)) min acc))
}


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

using namespace std;

long long Luca[87];

char S[9];

void make(int a, int b, int c, int d) {
	int i, j, k, l;
	int sum = a;
	int cnt = 0;

	for (cnt = 0;cnt < 8;cnt++) {
				if (cnt%2 == 0) sum += b;
				else sum -= b;
				if (cnt%4 <= 1) sum += c;
				else sum -= c;
				if (cnt%8 <= 3) sum += d;
				else sum -= d;
		if (sum == 7) break;
		sum = a;
	}
	S[0] = (char)(a+48);
	S[2] = (char)(b + 48);
	S[4] = (char)(c + 48);
	S[6] = (char)(d + 48);
	S[8] = '7';
	S[7] = '=';
	if (cnt%2 == 0) S[1] = '+';
	else S[1] = '-';
	if (cnt%4 <= 1) S[3] = '+';
	else S[3] = '-';
	if (cnt%8 <= 3) S[5] = '+';
	else S[5] = '-';

}

int main() {
	int a=0, b=0, c=0, d=0;
	int n;
	cin >> n;
	a = n / 1000;
	b = (n % 1000) / 100;
	c = (n % 100) / 10;
	d = n % 10;
	make(a, b, c, d);
	cout << S << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
typedef long long int64;
using namespace std;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
    while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return f*x;
}
const int N = 1e6+5, P = 998244353;
int n, m;
int64 fac[N], ifac[N], ans;
int64 inv(int i) { return i == 1?1:P-(P/i)*inv(P%i)%P; }
int64 C(int n, int m) { return fac[n]*ifac[m]%P*ifac[n-m]%P; }
int main()
{
    n = read(), m = read(), fac[0] = 1;
    for(int i = 1; i <= n+m; ++i) fac[i] = fac[i-1]*i%P;
    ifac[n+m] = inv(fac[n+m]);
    for(int i = n+m; i; --i) ifac[i-1] = ifac[i]*i%P;
    for(int i = min(n, m); i; --i) ans = (ans+C(n+m-(i<<1), n-i)*C(i<<1, i)%P)%P;
    ans = (ans*inv(C(n+m, n))%P*inv(2)%P+max(n, m))%P;
    printf("%lld\n", ans);
    return 0;
}

Measured memory_bytes: 15744
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO ?????????????????????????????????????????????

		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		
		if ((a < b) && (b < c)) System.out.println("Yes");
		else System.out.println("No");
	}

}

Measured memory_bytes: 26180
N = int(input())
A = list(map(int, input().split()))
B = set(A)
d = {}
for a in A:
  d[a] = d.get(a, 0) + 1
ans = 0
for b in B:
  s = d[b]
  if s >= b:
    ans += (s - b)
  else:
    ans += s
print(ans)

Measured memory_bytes: 113068
/*
**
*/

# include <cstdio>
# define NIL -1
# define MAX 30

struct Node {
    int parent, left, right;
} t[MAX];

int n, d[MAX], h[MAX], dgree[MAX];

void init_tree() { // 所有节点的父节点都设置为NIL
    for (int i = 0; i < n; i++) {
        t[i].parent = NIL;
    }
}

void create_tree() { // 设置所有节点的父节点和子节点
    int i, l, r;
    for (int j = 0; j < n; j++) {
        scanf("%d%d%d", &i, &l, &r);
        t[i].left = l;
        t[i].right = r;
        int dg = 0;
        if (l != NIL) {
            t[l].parent = i;
            dg++;
        }
        if (r != NIL) {
            t[r].parent = i;
            dg++;
        }
        dgree[i] = dg;
    }
}

void set_depth(int u, int dd) {
    if (u == NIL)
        return;
    d[u] = dd;
    set_depth(t[u].left, dd + 1);
    set_depth(t[u].right, dd + 1);
}

int set_height(int u) {
    int h1 = 0, h2 = 0;
    if (t[u].left != NIL)
        h1 = set_height(t[u].left) + 1;
    if (t[u].right != NIL)
        h2 = set_height(t[u].right) + 1;

    return h[u] = (h1 > h2 ? h1 : h2);
}

int getsibling(int u) {
    if (t[u].parent == NIL)
        return NIL;
    if (t[t[u].parent].left != u && t[t[u].parent].left != NIL)
        return t[t[u].parent].left;
    if (t[t[u].parent].right != u && t[t[u].parent].right != NIL)
        return t[t[u].parent].right;
    return NIL;
}

void print_tree() {
    for (int i = 0; i < n; i++) {
        printf("node %d: ", i);
        printf("parent = %d, ", t[i].parent);
        printf("sibling = %d, ", getsibling(i));
        printf("degree = %d, ", dgree[i]);
        printf("depth = %d, ", d[i]);
        printf("height = %d, ", h[i]);
        if (t[i].parent == NIL) {
            printf("root\n");
        }
        else if (t[i].left == NIL && t[i].right == NIL) {
            printf("leaf\n");
        }
        else {
            printf("internal node\n");
        }
    }
}

int main () {
    // freopen("infile", "r", stdin);
    // freopen("outfile", "w", stdout);
    scanf("%d", &n); 
        init_tree();
        create_tree();
        int root;
        for (root = 0; root < n; root++) { // 寻找根节点
            if (t[root].parent == NIL)
                break;
        }
        set_depth(root, 0);
        set_height(root);
        print_tree();
    
    return 0;
}


Measured memory_bytes: 2760
import re


def answer(a: int, b: int, s: str) -> str:
    pattern = fr'\d{{{a}}}-\d{{{b}}}'
    if re.match(pattern, s):
        return 'Yes'
    return 'No'


def main():
    a, b = map(int, input().split())
    s = input()
    print(answer(a, b, s))


if __name__ == '__main__':
    main()


Measured memory_bytes: 9868
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using ll = long long;
using lint = long long;
typedef pair<int,int> P;
const lint inf=1e18+7;
const int MOD=1000000007;
void update(vector<int> const& a,vector<int>& b,int n){
    rep1(i,n){
        int l=i-a[i];
        if(l<0)l=0;
        int r=i+a[i]+1;
        if(r>n)r=n+1;
        b[l]+=1;
        b[r]-=1;
    }
    rep1(i,n){
        b[i]=b[i-1]+b[i];
    }
}
signed main(){
  int n,k;cin>>n>>k;
  vector<int> a(n+10,0);
  rep1(i,n)cin>>a[i];
  vector<int> b(n+10,0);
  update(a,b,n);
  rep(x,k){
      int mn=inf;
      b[0]=0;
      rep1(i,n){
          a[i]=b[i];
          b[i]=0;
          mn=min(mn,a[i]);
      }
      update(a,b,n);
      if(mn==n)break;
  }
  rep1(i,n){
      cout<<a[i]<<" ";
  }
  cout<<endl;
  return 0;
}

Measured memory_bytes: 6428
#include <iostream>
static int MAX = 100;

void insertionSort(int *A,int N){
	int i,j;
	int v;
	std::cout << A[0];
	for(j = 1;j < N;j++){ 
		std::cout << " ";
		std::cout << A[j];
	}
	std::cout << std::endl;
	for (i = 1; i < N; i++) {
		v = A[i];
		j = i-1;
		while(j >= 0 && A[j] > v){
			A[j+1] = A[j];
			j--;
		}
		A[j+1] = v;
		std::cout << A[0];
		for(j = 1;j < N;j++){ 
			std::cout << " ";
			std::cout << A[j];
		}
		std::cout << std::endl;
	}
}
int main(){
	int A[MAX];
	int n;
	std::cin >> n;
	for(int i = 0;i < n;i++) std::cin >> A[i];

	insertionSort(A,n);

	return 0;
}

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

#define FORE(i, a) for (auto i = a.begin(); i != a.end(); ++i)
#define REPU(i, a, b) for (int i = (a); i < (b); ++i)
#define REPD(i, a, b) for (int i = (a); i > (b); --i)
#define MEM(a, x) memset(a, x, sizeof(a))
#define ALL(a) a.begin(), a.end()
#define UNIQUE(a) a.erase(unique(ALL(a)), a.end())

vector<string> split(const string &s, char c) {
	vector<string> v;
	stringstream ss(s);
	string x;
	while (getline(ss, x, c)) v.push_back(x);
	return v;
}

#define DEBUG(args...) { vector<string> _v = split(#args, ','); err(_v.begin(), args); }

void err(vector<string>::iterator it) {}

template<typename T, typename... Args>
void err(vector<string>::iterator it, T a, Args... args) {
	cerr << "[DEBUG] " << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << '\n';
	err(++it, args...);
}

typedef long long ll;
const int MOD = 1000000007;

template<class T, class U> inline T tmin(T a, U b) { return (a < b) ? a : b; }
template<class T, class U> inline T tmax(T a, U b) { return (a > b) ? a : b; }
template<class T, class U> inline void amax(T &a, U b) { if (b > a) a = b; }
template<class T, class U> inline void amin(T &a, U b) { if (b < a) a = b; }
template<class T> inline T tabs(T a) { return (a > 0) ? a : -a; }
template<class T> T gcd(T a, T b) { while (b != 0) { T c = a; a = b; b = c % b; } return a; }

typedef pair<int, int> P;
const int N = 100005;
vector<int> g[N];
int nums[N];

bool dfs(int v, int p, int f) {
	if (nums[v] != -1) {
		if (nums[v] % 2 != f) return false;
	}
	bool ans = true;
	for (int u : g[v]) if (u != p) {
		ans &= dfs(u, v, f ^ 1);
	}
	return ans;
}

int main(int argc, char *argv[]) {
	ios_base::sync_with_stdio(false);

	int n, k;
	MEM(nums, -1);

	cin >> n;
	REPU(i, 1, n) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	cin >> k;
	vector<int> v(k);
	set<P> st;
	REPU(i, 0, k) {
		int p;
		cin >> v[i] >> p;
		nums[v[i]] = p;
		st.insert(P(p, v[i]));
	}
	const bool ok = dfs(v[0], 0, nums[v[0]] % 2);
	if (!ok) {
		puts("No"); return 0;
	}
	while (st.size() > 0) {
		auto p = *st.begin(); st.erase(st.begin());
		for (int v : g[p.second]) {
			if (nums[v] == -1) {
				nums[v] = p.first + 1;
				st.insert(P(nums[v], v));
			}
		}
	}
	REPU(i, 1, n + 1) {
		for (int u : g[i]) {
			if (abs(nums[u] - nums[i]) != 1) {
				puts("No"); return 0;
			}
		}
	}
	puts("Yes");
	REPU(i, 1, n + 1) printf("%d\n", nums[i]);

	return 0;
}


Measured memory_bytes: 14080
n, k = map(int, input().split())
h = [int(input()) for _ in range(n)]
h.sort()
minVal = 10 ** 9 - 1
for i in range(n - k + 1):
    if h[i+k-1] - h[i] <= minVal:
        minVal = h[i+k-1] - h[i]
print(minVal)


Measured memory_bytes: 7384
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int A[100010],fir[100010],dis[200010],nxt[200010],id;
void link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
ll dfs(int x,int fa=-1){
	std::vector<int>son;ll sum=0;
	for(int i=fir[x];i;i=nxt[i]){
		if(fa==dis[i])continue;
		son.push_back(dfs(dis[i],x));
		sum+=son.back();
	}
	if(son.empty())return A[x];
	ll c=sum-A[x];
	if(c<0||c*2>sum)puts("NO"),exit(0);
	std::sort(son.begin(),son.end(),std::greater<int>());
	ll _=0,o;for(int i=1;i<son.size();++i)_+=son[i];
	if(son[0]>_)o=_;
	else o=sum/2;
	if(o<c)puts("NO"),exit(0);
	return sum-2*c;
}
int d[100010];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),a,b;
	for(int i=1;i<=n;++i)A[i]=gi();
	for(int i=1;i<n;++i)++d[a=gi()],++d[b=gi()],link(a,b),link(b,a);
	for(int i=1;i<=n;++i)
		if(d[i]>1){
			if(dfs(i))puts("NO");else puts("YES");
			return 0;
		}
	if(A[1]==A[2])puts("YES");else puts("NO");
	return 0;
}


Measured memory_bytes: 12288
#include <iostream>
using namespace std;
bool a[1000001];
int main()
{
  int i,j,m,n;
  for(i=1;i<1000001;i++){
    j = i;
    while(j % 2 == 0) j /= 2;
    while(j % 3 == 0) j /= 3;
    while(j % 5 == 0) j /= 5;
    if(j==1) a[i] = true;
  }
  for(;;){
    cin >> m;
    if(m==0) break;
    cin >> n;
    j = 0;
    for(i=m;i<=n;i++){
      if(a[i]) j++;
    }
    cout << j << endl;
  }
  return 0;
}

Measured memory_bytes: 0
N = $stdin.gets.chomp.to_i
from = [0,0,0]
N.times {
  r = $stdin.gets.chomp.split(" ").map(&:to_i)

  t1,x1,y1 = *from
  t2,x2,y2 = *r
  d = (t2 - t1) - ((x2-x1).abs + (y2-y1).abs)
  if d < 0 || d%2 == 1
    puts "No"
    exit
  end

  from = r
}

puts "Yes"

Measured memory_bytes: 1788