akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = long long;
using P = pair<int,int>;

vector<P> g[200];
int d[8][8];
int r;
int dfs(int u=-1,int b=0){
  if(b==(1<<r)-1) return 0;
  int res = 1e9;
  rep(v,r){
    if(b>>v&1)continue;
    res = min(res,dfs(v,b|(1<<v))+d[u][v]);
  }
  return res;
}
int main() {
  int n,m;
  cin >> n >> m >> r;
  vector<int> t(r);
  rep(i,r) cin >> t[i], --t[i];
  rep(i,m){
    int a,b,c;
    cin >> a >> b >> c;
    --a; --b;
    g[a].emplace_back(b,c);
    g[b].emplace_back(a,c);
  }
  rep(i,r){
    vector<int> di(n,1e9);
    queue<P> q;
    auto push = [&](int nd,int v){
      if(di[v]<=nd) return;
      di[v] = nd;
      q.emplace(nd,v);
    };
    push(0,t[i]);
    while(!q.empty()){
      P u = q.front(); q.pop();
      for(auto v:g[u.second]) push(u.first+v.second,v.first);
    }
    rep(j,r) d[i][j] = di[t[j]];
  }
  cout << dfs() << endl;
}

Measured memory_bytes: 640
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
int cnt[200010];
int main()
{
	int n,k;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) cnt[i%k]++;
	ll ans=0;
	for(int i=0;i<=k;i++)//a%k
	{
		if((i+i)%k==0)//a%k==c%k
		{
			ans+=(ll)cnt[i]*cnt[(k-i+k)%k]*cnt[i];//a%k + b%k = 0 or k
		}
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,j,k) for(int i=j;i<k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define ll long long
#define ull unsigned long long int
#define ld long double
//Make sure no overflow problems
#define pii  pair<int, int>
#define vi vector<int >
#define pb push_back
#define mp make_pair
#define endl '\n'
#define x first
#define y second
#define VAR(i,n) __typeof(n) i = (n)
#define FOREACH(i,c) for(VAR(i,(c).begin());i!=(c).end();i++)
#define FORDEACH(i,c) for( VAR(i,(c).rbegin()),i!=(c).rend();i++)
#define REP(i,n) FOR(i,0,n)
#define mod 1000000007
#define MEM(a, b) memset(a, (b), sizeof(a))
#define addmod(a,b,mod) (a%mod + b%mod)%mod
#define submod(a,b,mod) (a%mod - b%mod + mod)%mod
//const long long INFLL = (ll)INF * (ll)INF;
const ld EPS = 10e-9;
const int MAX = 1e6;


int main(){
    ios_base:: sync_with_stdio(0); 
    cin.tie(0);
    
    ll x, cnt = 0, k;
    cin >> k;
    queue<ll> q;
    FOR(i,1,10)
		q.push(i);
	while(cnt != k){
		x = q.front();
		q.pop();
		if(x%10 != 0)
			q.push(10*x + x%10 - 1);
		q.push(10*x + x%10);
		if(x%10 != 9)
			q.push(10*x + x%10 + 1);
		cnt++;
	}
	cout << x << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define trace(x) cerr<<#x<<": "<<x<<" "<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define sa(a, n) for(int i =0 ; i<n ; i++) cin>>a[i]
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a  ,min(b, c))
#define scan() int n; cin>>n ; int a[n]; for(int i = 0 ; i<n ; i++) cin>>a[i]
#define print(a, n) for(int i = 0 ; i < n ; i++) cout<<a[i]<<' '
using namespace std;



int32_t main()
{
    int n, w;
    cin>>n>>w;
    int weight[n+1];
    int value[n+1];
    for(int i=1;i<n+1;i++)
    {
        cin>>weight[i]>>value[i];
    }
    int dp[n+1][w+1];
    for(int i=1;i<w+1;i++)
    {
        dp[0][i] = 0;
        if(i>=weight[1])
        {
            dp[1][i] = value[1];
        }
        else
        {
            dp[1][i] = 0;
        }
    }
    for(int i=0;i<n+1;i++)
    {
        dp[i][0] = 0;
    }
    for(int i=2;i<n+1;i++)
    {
        for(int j=1;j<w+1;j++)
        {
            if(weight[i] <= j)
            {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i]);
            }
            else
            {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    cout<<dp[n][w];
    return 0;
}


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

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll, ll> P;


int main()
{
	vector<int> a(3);
	cin >> a[0] >> a[1] >> a[2];
	sort(a.begin(), a.end());
	cout << (a[1] - a[0]) + (a[2] - a[1]) << endl;
	return 0;
}


Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))

A=[(A[i],i) for i in range(0,N)]
A.sort(reverse=True)


dp=[[0 for i in range(0,N)] for j in range(0,N)]

for i in range(0,N-1):
    a,index=A[-1]
    dp[N-1][i]=a*abs(index-i)

for _ in range(1,N):
    i=N-1-_
    for j in range(0,i+1):
        left=j
        right=i-j
        a,index=A[i]
        ans=0
        if index>left-1:
            ans=max(ans,dp[i+1][j+1]+a*(index-left))

        if N-right>index:
            ans=max(ans,dp[i+1][j]+a*(N-right-1-index))

        dp[i][j]=ans

print(dp[0][0])

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

int c[4][13];

int main(void)
{
	int n;
	int i, j;
	char rank;
	int num;
	
	cin >> n;
	
	for (i = 0; i < n; i++){
		cin >> rank >> num;
		
		switch (rank){
		  case 'S':
		  	c[0][num - 1] = 1;
			break;
			
		  case 'H':
		  	c[1][num - 1] = 1;
			break;
			
		  case 'C':
		  	c[2][num - 1] = 1;
			break;
			
		  case 'D':
		  	c[3][num - 1] = 1;
			break;
		}
	}
	
	for (i = 0; i < 4; i++){
		for (j = 0; j < 13; j++){
			if (c[i][j] != 1){
				if (i == 0){
					cout << "S";
				}
				else if (i == 1){
					cout << "H";
				}
				else if (i == 2){
					cout << "C";
				}
				else if (i == 3){
					cout << "D";
				}
				cout << " " << j + 1 << endl;
			}
		}
	}
	return (0);
}

Measured memory_bytes: 1160
#include <iostream>

using namespace std;

class Vector{
public:
	double x,y;

	Vector( double dx, double dy ) : x( dx ), y( dy ) {}
	Vector(){}

	Vector& operator-=( const Vector& rhs ){
		x -= rhs.x; y -= rhs.y;
		return *this;
	}
	double operator*( const Vector& rhs ){
		return x * rhs.x + y * rhs.y;
	}
};
int main(int argc, char const* argv[])
{
	Vector A,B,C,D;

	while( cin >> A.x >> A.y >> B.x >> B.y >> C.x >> C.y >> D.x >> D.y ){
		B -= A;
		D -= C;

		if( B * D == 0 ) cout << "YES" << endl;
		else cout << "NO" << endl;
	}


	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <vector>
using namespace std;

int main(){
    int a, b, c;
    cin>>a>>b>>c;
    if (a>b) swap(a, b);
    if (c>=a && c<=b) printf("Yes\n");
    else printf ("No\n");
    

    return 0;
}

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


int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int N,K,max=1000000000;
  cin>>N>>K;
  int h[N];
  for(int i=0;i<N;i++){
    cin>>h[i];
  }
  sort(h,h+N); //昇順ソート

  for(int i=0;i<=N-K;i++){
    if(max>=h[i+K-1]-h[i]){
      max=h[i+K-1]-h[i];
    }
  }

  cout<<max;


  return 0;
}

Measured memory_bytes: 640
n=int(input())
m=input()
alf=["A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z"]
ans=""
for i in m:
    for j in alf:
        if i==j:
            ans=ans+alf[alf.index(j)+n]
            break

print(ans)

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

using namespace std;

int main(){
  int N, K;
  cin >> N >> K;
  vector<long long> p(N);
  for(int i = 0; i < N; i++){
    cin >> p[i];
    p[i]++;
  }
  
  for(int i = 1; i < N; i++) p[i] += p[i - 1];
  
  long long m = p[K - 1];
  for(int i = K; i < N; i++){
    m = max(p[i] - p[i - K], m);
  }
  
  cout << fixed << setprecision(10) << (double)m / 2.0 << endl;
  
  return 0;
}

Measured memory_bytes: 1792
sss = input()
min_a = 0
max_s = 0
for i in range(len(sss)):
    if sss[i] == 'A':
        min_a = i
        break
# for i in range(len(sss)-1, 0, -1):
for i in reversed(range(len(sss))):
    if sss[i] == 'Z':
        max_s = i
        break
print(max_s - min_a + 1)


Measured memory_bytes: 3516
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <ctime>
#include <map>
#include <iomanip>
using namespace std;
 
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define REP(i,n) FOR(i,0,n)
 
long gcd(long a, long b){
	if (a%b==0){
		return b;
	}
	else{
		return gcd(b,a%b);
	}
}
 
long lcm(long a, long b){
	return (a*b) / gcd(a,b);
}
 
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a < b) { a = b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a > b) { a = b; return 1; } return 0; }
 
typedef long long ll;
 
const ll INF = 1ll<<60;
const ll MOD = 1000000007;
const double EPS = 1e-10;

int main(){
	int n;
	
	cin >> n;
	
	cout << n*n*n << endl;
	
	return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from collections import *
from bisect import *

def judge(x):
    tak = N-x
    aoki = x-bisect_left(A, 2*X-A[x])+1
    
    return tak<=aoki

def binary_search():
    l, r = mark, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

N, Q = map(int, input().split())
A = list(map(int, input().split()))
acc = [0]
acc_e = [0]

for i in range(N):
    acc.append(acc[-1]+A[i])
    acc_e.append(acc_e[-1]+(A[i] if i%2==0 else 0))

for _ in range(Q):
    X = int(input())
    mark = bisect_left(A, X)
    border = binary_search()
    ans = acc[-1]-acc[border]
    c = N-border
    
    if 2*c>=N:
        print(ans)
        continue
    
    if (N-2*c-1)%2==0:
        ans += acc_e[N-2*c]
    else:
        ans += acc[N-2*c]-acc_e[N-2*c]
    
    print(ans)

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

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
  COMinit();
  long N,M;cin>>N>>M;
  long n=N;
  N=M;
  vector<long>prime(0);
  vector<long>pow(100000,0);
  long now=2;
  long rn=0;
  int kind=-1;
  while(true){
  	if(N==1)break;
    if(now*now>N){
      if(rn==N){
        pow[kind]++;
      }else{
      	prime.push_back(N);
      	kind++;
      	pow[kind]=1;
      }
  	  break;
    }
    if(N%now==0){
      N/=now;
      if(rn==now){
      	pow[kind]++;
        rn=now;
      }else{
      	kind++;
      	prime.push_back(now);
        pow[kind]=1;
        rn=now;
      }
      now=1;
    }
    now++;
  }
  long ans=1;
  for(int i=0;i<prime.size();i++){
    //cout<<prime[i]<<" "<<pow[i]<<endl;
    ans=(ans*COM(pow[i]+n-1,pow[i]))%MOD;
  }
  cout<<ans%MOD<<endl;
}


Measured memory_bytes: 12928
#include <bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; i++)
#define ALL(v) v.begin(),v.end()
#define ll long long

using namespace std;

int main(){

    int n,k;

    cin >> n >> k;

    vector<ll> v;

    REP(i,n){
        ll tmpv;
        cin >> tmpv;
        v.push_back(tmpv);
    }

    ll ans = 0;

    REP(i,k + 1){
        REP(j,k + 1 - i){
            
            if(i + j > n) break;
            
            int discard = k - i - j;
            vector<ll> minus;
            ll tmpans = 0;

            REP(l, i){
                tmpans += v[l];
                if(v[l] < 0){
                    minus.push_back(v[l]);
                }
            }

            REP(l, j){
                tmpans += v[v.size() - 1 - l];
                if(v[v.size() - 1 - l] < 0){
                    minus.push_back(v[v.size() - 1 - l]);
                }
            }

            sort(ALL(minus));
            discard = min(discard,(int)minus.size());

            REP(l, discard){
                tmpans = tmpans - minus[l];
            }

            ans = max(ans,tmpans);
        }
    }

    cout << ans << endl;

    return 0;
}

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

int main(){
    int n,d,p,total=0;
    
    cin >> n >> d;
    for (int i=0;i<n;i++) {
        cin >> p;
        if (p>d) total += p-d;
    }
    
    if (total == 0) cout << "kusoge" << endl;
    else cout << total << endl;
    
    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
using namespace std;
int main(){
	string s;
	cin>>s;
	map<int,int>mp;
	for(int i=0;i<4;i++)
		mp[s[i]]++;
	if(mp.size()!=2){
		cout<<"No"<<endl;
		return 0;
	}
	for(auto x:mp){
		if(x.second!=2){
			cout<<"No"<<endl;
			return 0;
		}
	}
	cout<<"Yes"<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
/* 変数名を被らせない
   デバッグコードを取り除く 
　　提出する問題を間違えない */
#define ANSWER(x) cout<<x<<endl
#define debug(x) cout<<#x<<": "<<x
int main(){
  stack<int> train;
  int a;
  while(1){
    cin >> a;
    if(a){
      train.push(a);
    }else{
      if(cin.eof())break;
      cout << train.top() << endl;
      train.pop();
    }
  }
}

Measured memory_bytes: 1200
import java.io.IOException;
import java.io.InputStream;
import java.util.*;

public class Main {
	public static void main(String[] args) {
		FastScanner sc = new FastScanner();
		int n = sc.nextInt();
		int[] r = new int[n];
		for (int i = 0; i < n; i++) {
			r[i] = sc.nextInt();
		}
		int[] max = new int[n];
		int[] min = new int[n];
		max[n - 1] = r[n - 1];
		min[0] = r[0];
		for (int i = 1; i < n; i++) {
			min[i] = Math.min(min[i - 1], r[i]);
		}
		for (int i = n - 2; i >= 0; i--) {
			max[i] = Math.max(max[i + 1], r[i]);
		}
		int ans = -1000000007;
		for (int i = 0; i < n - 1; i++) {
			ans = Math.max(max[i + 1] - min[i], ans);
		}
		System.out.println(ans);
	}
}

class FastScanner {
	private final InputStream in = System.in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		} else {
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() {
		if (hasNextByte()) {
			return buffer[ptr++];
		} else {
			return -1;
		}
	}
	private static boolean isPrintableChar(int c) {
		return 33 <= c && c <= 126;
	}
	public boolean hasNext() {
		while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
			ptr++;
		}
		return hasNextByte();
	}
	public String next() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while (isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) {
			throw new NoSuchElementException();
		}
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while (true) {
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			} else if (b == -1 || !isPrintableChar(b)) {
				return minus ? -n : n;
			} else {
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || Integer.MAX_VALUE < nl) {
			throw new NumberFormatException();
		}
		return (int) nl;
	}
	public double nextDouble() {
		return Double.parseDouble(next());
	}
}


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

int main(){
  int a[100][100];
  int n;
  cin>>n;
  for(int i=0;i<100;i++){
    for(int j=0;j<100;j++){
      a[i][j]=0;
    }
  }
  for(int i=0;i<n;i++){
    int u,k;
    cin>>u>>k;
    for(int j=0;j<k;j++){
      int v;
      cin>>v;
      a[u-1][v-1]=1;
    }
  }
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(j!=(n-1)) cout<<a[i][j]<<" ";
      else cout<<a[i][j];
    }
    cout<<endl;
  }
  return 0;
}



Measured memory_bytes: 3128
#include <algorithm>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <string>
#include <utility>
#include <vector>

using namespace std;

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

  // vector<pair<double, double>> M;
  int counter = 0;
  for (int i = 0; i < N; i++) {
    double x, y;
    cin >> x >> y;
    double d = sqrt((x * x) + (y * y));
    if (d <= D) {
      counter++;
    }
  }

  cout << counter << endl;

  return 0;
}


Measured memory_bytes: 3168
#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <iomanip>
using namespace std;

const long long MAX_N = 3e3 + 9, MAX_K = 1e5 + 5;
long long n;
long long a[MAX_N];
long long dp[MAX_N][MAX_N][2];

int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (long long i = 0; i < n; i++)
		cin >> a[i];

	for (long long i = 0; i < n; i++) {
		dp[i][i][0] = a[i];
		dp[i][i][1] = -a[i];
	}

	for (long long i = 1; i < n; i++)
		for (long long j = 0; j + i < n; j++) {
			dp[j][j + i][0] = max(a[j] + dp[j + 1][j + i][1], a[j + i] + dp[j][j + i - 1][1]);	
			dp[j][j + i][1] = min(-a[j] + dp[j + 1][j + i][0], -a[j + i] + dp[j][j + i - 1][0]);
		}

	cout << dp[0][n - 1][0] << "\n";
	return 0;
}

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

int main() {
  int H, W;
  cin >> H >> W;
  vector<vector<char>> S(H, vector<char>(W));
  int cnt = 0;
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> S.at(i).at(j);
      if (S.at(i).at(j) == '.') cnt++;
    }
  }
  vector<vector<int>> dist(H, vector<int>(W, -1));
  int h = 0;
  int w = 0;
  dist.at(h).at(w) = 1;
  vector<int> mh(4), mw(4);
  mh = {-1, 0, 1, 0};
  mw = {0, 1, 0, -1};
  queue<pair<int,int>> Q;
  Q.push({h, w});
  while (Q.size()) {
    int h = Q.front().first;
    int w = Q.front().second;
    Q.pop();
    for (int i = 0; i < 4; i++) {
      int nh = h + mh.at(i);
      int nw = w + mw.at(i);
      if (nh < 0 || nh >= H || nw < 0 || nw >= W) continue;
      if (S.at(nh).at(nw) == '#') continue;
      if (dist.at(nh).at(nw) == -1) {
        dist.at(nh).at(nw) = dist.at(h).at(w) + 1;
        Q.push({nh, nw});
      }
    }
  }
  if (dist.at(H - 1).at(W - 1) == -1) cout << -1 << "\n";
  else cout << cnt - dist.at(H - 1).at(W - 1) << "\n";
}

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

typedef long long ll;
typedef unsigned long long ull;

ll MOD = 1000000007;

template <typename T>
class ModCalc{
public:
    ModCalc(T MOD){
        mod = MOD;
    }

    T add(T a, T b){
        return (a + b) % mod;
    }

    T sub(T a, T b){
        return (a - b) % mod;
    }

    T multi(T a, T b){
        return ((a % mod) * (b % mod)) % mod;
    }

    T power(T a, T n){
        T res = 1;
        while(n){
            if(n&1) res = multi(res, a);
            a = multi(a, a);
            n >>= 1;
        }
        return res;
    }

    T div(T a, T b){
        return multi(a, power(b, mod-2));
    }

    T comb(T n, T k){
        T res = 1;
        for(int i=0; i<k; i++){
            res = multi(res, n-i);
            res = div  (res, i+1);
        }
        return res;
    }
private:
    T mod;
};


int main()
{
    ll N, M, K;
    cin >> N >> M >> K;

    ModCalc<ll> mod(MOD);

    ll res_N = 0;
    ll res_M = 0;
    for(ll i=1;i<N;i++){
        res_N = mod.add(res_N, mod.multi(i, N-i));
    }
    res_N = mod.multi(res_N, mod.power(M,2));
    for(ll i=1;i<M;i++){
        res_M = mod.add(res_M, mod.multi(i, M-i));
    }
    res_M = mod.multi(res_M, mod.power(N,2));

    auto res = mod.add(res_N, res_M);
    res = mod.multi(res, mod.comb(N*M-2, K-2));
    cout<<res<<endl;
    return 0;
}




Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Stream;

public class Main {
//    private static Scanner sc = new Scanner(System.in);
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        // 解答ここから
        int N = nextInt();
        int[] X = arrayOfInt();
        int[] x = X.clone();
        Arrays.sort(x);
        // 中央値の境界を取る
        int floor = N/2 - 1;
        int border = x[floor];

        int a = x[floor + 1];
        int b = x[floor];
        for(int i = 0;i < N;i++){
            if(X[i] <= border){
                println(a);
            }else{
                println(b);
            }
        }

    }
    // 入力受け取り
    static String next() throws IOException {return br.readLine();}
    static int nextInt() throws IOException{return getInt(br.readLine());}
    static long nextLong() throws IOException{return getLong(br.readLine());}
    static String[] arrayOfString() throws IOException{return br.readLine().split(" ");}
    static int[] arrayOfInt() throws IOException{return toIntArray(arrayOfString());}
    // 変換
    static long getLong(String val) {return Long.parseLong(val);}
    static int getInt(String val) {return Integer.parseInt(val);}
    static int[] toIntArray(String[] array) {return Stream.of(array.clone()).mapToInt(Integer::parseInt).toArray();}
    // 出力
    static void println(Object val){System.out.println(val);}
}


Measured memory_bytes: 80404
#include <bits/stdc++.h>
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll=long long;
int main(){
    int n,k,r,s,p; string t;
    cin>>n>>k>>r>>s>>p>>t;
    int ans=0;
    string ss;
    rep(i,n){
        if(t[i]=='r'){
            ans+=p;
            ss+='p';
        }
        else if(t[i]=='s'){
            ans+=r;
            ss+='r';
        }
        else{
            ans+=s;
            ss+='s';
        }
    }
    for(int i=k; i<n; ++i){
        if(ss[i]==ss[i-k]){
            if(t[i]=='r'){
                ans-=p;
                ss[i]='z';
            }
            else if(t[i]=='s'){
                ans-=r;
                ss[i]='z';
            }
            else{
                ans-=s;
                ss[i]='z';
            }
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
 
#define f(i,a,b) for( ll i = a; i < b ; i++ ) 
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(a) (ll) a.size()
#define all(a) a.begin(), a.end()
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define inter ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nuintptr)
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> ii ;
typedef vector<ll>  vi ;
typedef vector<ii> vii ;
 
const int MAX= 4e5+6;
const ll inf =1e18;
 
 
 

int main(){
	fastio;
	ll n,k,a,b;
	cin>>k>>a>>b;
	f(i,a,b+1){
		if(i%k==0) {
			cout<<"OK\n";
			return 0;
		}
	}
	cout<<"NG\n";
}

Measured memory_bytes: 3644
#pragma warning(disable: 4996)
#include <string>
#include <vector>
#include <iostream>
#include <cstdio>
#include <sstream>
#include <fstream>
#include <math.h>
#include <algorithm>

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

struct UnionFind {
    // comment: https://youtu.be/TdR816rqc3s?t=6822　解説動画
    vector<int> d;
    UnionFind(int n = 0) : d(n, -1) {}//根は-サイズを値として持ち、子は根のIDを値として持つ、最初はすべてが根(dの中身)
    int find(int x) {//それぞれの要素に対して根を探索する関数
        if (d[x] < 0) return x;//マイナス(根)であればxそのものを返す
        return d[x] = find(d[x]);//そうでなければd[x]つまり親のIDを返す
    }
    bool unite(int x, int y) {//要素を結び付ける関数
        x = find(x); y = find(y);//まずそれぞれの要素の根を探索、入力された要素そのものを根のIDに変換
        if (x == y) return false;//根が同じであれば終了
        if (d[x] > d[y]) swap(x, y);//サイズが小さいほうを大きいほうに結びつける(x,yは根のIDに変換されているため)
        d[x] += d[y];//サイズの更新(x,yは根のIDに変換されているため)
        d[y] = x;//根の更新(x,yは根のIDに変換されているため)
        return true;
    }
    bool same(int x, int y) { return find(x) == find(y); }//同じグループに属するかを判定
    int size(int x) { return -d[find(x)]; }//サイズを計算する関数
};

int main() {
    int n, m;
    cin >> n >> m;
    UnionFind uf(n);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        uf.unite(a, b);//入力された番号を結び付ける
    }
    int ans = 0;
    rep(i, n) ans = max(ans, uf.size(i));//作られた木に対してサイズを求め、その最大値が答え。
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3672
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define mod 998244353
#define int long long
#define inf 200000000
const int maxnodes=1005;
#define ll long long
#define N 301
#define EPS 0.01
#define ld long double



int32_t main()
{
    IOS;

    int n;
    cin >> n;
    string s;
    cin >> s;
    if(n < 3200)
        cout << "red";
    else
        cout << s;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()	{
  long long s, c;
  cin >> s >> c;
  if (s > c / 2) {cout << c / 2 << endl; return 0;}
  c = (c - (2 * s)) / 4;
  cout << s + c << endl;
  return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string str;
  int n;
  n = 0;
  cin >> str;
 
 for(int i =0; i < str.size(); i++){
  if (str.at(i) == 'R') {
    n = n + 1;
    }
  }

  if(n != 2){
      cout << n << endl;
  }else if(str.at(1) == 'R'){
      cout << n << endl;

  }else{
      cout << 1 << endl;
  }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const ll MOD = 1000000007;

/*
  dp1[i+1] : a+bが、Lの上からi桁と等しい組み合わせの数
  dp2[i+1] : a+bが、Lの上からi桁より小さい組み合わせの数
  
*/

ll dp1[100005];
ll dp2[100005];

int main(){
	string L;
	cin >> L;
	
	ll sum = 0;
	dp1[0] = 1;
	dp2[0] = 0;
	
	for ( size_t i = 0; i < L.size(); i++ ){
		if ( L[i] == '0' ){
			dp1[i+1] = dp1[i];
			dp2[i+1] = dp2[i]*3 % MOD;
		}
		else {
			dp1[i+1] = dp1[i]*2 % MOD;
			dp2[i+1] = (dp2[i]*3+dp1[i]) % MOD;
		}
		
		//cout << dp1[i+1] << "     " << dp2[i+1] << endl;
	}
	
	cout << (dp1[L.size()]+dp2[L.size()])%MOD << endl;
	
	return 0;
}



Measured memory_bytes: 2048
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 510000;
const int MOD = 1000000007;

/*long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}*/
int main() {
   ll dp[1000000];
   int S;
   cin >> S;

   for (int i = 0; i < 1000000; i++)
   {
        dp[i] = 0;
   }
   
   dp[0] = 1;

   for (int i = 0; i <= S; i++)
   {
       for (int j = 3; j <= S; j++)
       {
           dp[i + j] += dp[i]; 
           dp[i + j] %= 1000000007;
       }
       
   }
   cout << dp[S] << endl;
    return 0;
}

Measured memory_bytes: 11368
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(sc.next());
        }
        print(arr);
        for (int i = 1; i < n; i++) {
            int v = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > v) {
                arr[j+1] = arr[j];
                j --;
            }
            arr[j+1] = v;
            print(arr);
        }
    }

    private static void print(int[] arr) {
        for (int k = 0; k < arr.length; k++) {
            if (k != arr.length-1) {
                System.out.print(arr[k] + " ");
            } else {
                System.out.print(arr[k]);
            }
        }
        System.out.println();
    }
}



Measured memory_bytes: 30988
#include <iostream>


using namespace std;

int main()
{
	int n[3];
	for(int i = 0; i < 3; ++i)
	{
		cin >> n[i];
	}
	qsort(n, 3, sizeof(int), [](const void *a, const void *b)
		  {
			  return *(int*)a - *(int*)b;
		  });
	cout << n[0] << " " << n[1] << " " << n[2] << endl;
	return 0;
}


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

int main() {
  int N;
  cin >> N;
  int ans = 0;
  vector<int> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S.at(i);
    ans += S.at(i);
  }
  if (ans % 10) {
    cout << ans << "\n";
    return 0;
  }
  sort(S.begin(), S.end());
  for (int i = 0; i < N; i++) {
    if (S.at(i) % 10) {
      ans -= S.at(i);
      cout << ans << "\n";
      return 0;
    }
  }
  cout << 0 << "\n";
}

Measured memory_bytes: 256
package main

import "fmt"

func roundUp1000(dept float64) float64 { 
	iDept := int(dept)
	if iDept-(iDept/1000*1000) != 0 { 
		iDept = ((iDept / 1000) + 1) * 1000 
	}
	return float64(iDept)
}

func main() {
	var week int
	fmt.Scan(&week)

	dept := 100000.0
	for i := 0; i < week; i++ {

		dept *= 1.05
		dept = roundUp1000(dept)
	}

	fmt.Println(int(dept))
}



Measured memory_bytes: 1108
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }


template <typename T> map<T, T> prime_factor(T n) {
    map<T,T> ret;
    for (T i = 2; i * i <= n; i++) {
        T tmp = 0;
        while (n % i == 0) {
            tmp++;
            n /= i;
        }
        if(tmp != 0) ret[i] = tmp;
    }
    if (n != 1) ret[n] = 1;
    return ret;
}
// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
int main(){
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];
    vector<map<int,int>> pf_map(n);
    map<int,int> lcm;
    rep(i,n) {
        pf_map[i] = prime_factor(a[i]);
        for(auto mp : pf_map[i]) {
            if(lcm.count(mp.first) == 0) lcm[mp.first] = mp.second;
            else chmax(lcm[mp.first], mp.second);
        }
    }
    mint ans = 0;
    rep(i,n) {
        mint tmp = 1;
        for(auto mp : lcm) {
            int a = mp.first;
            int b = mp.second;    
            if(pf_map[i].count(a) != 0) b -= pf_map[i][a];
            rep(i,b) tmp *= a;
        }
        ans += tmp;
    }
    cout << ans << endl;
}


Measured memory_bytes: 5904
def bmi(a):
	return a[0], abs(22-a[2]/((a[1]/100.0)**2))
	
while 1:
	n=input()
	if n==0:break
	d=[bmi(map(int,raw_input().split())) for i in range(n)]
	print sorted(sorted(d),key=lambda x:x[1])[0][0]

Measured memory_bytes: 4504
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000001


int main(){
	
	int A,B;
	cin>>A>>B;
	if(A==1)A=14;
	if(B==1)B=14;
	
	if(A==B){
		cout<<"Draw"<<endl;
	}
	else if(A>B){
		cout<<"Alice"<<endl;
	}
	else{
		cout<<"Bob"<<endl;
	}
	
    return 0;
}



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

int main() {
  int N, L;
  string S[N];
  cin >> N >> L;
  for(int i = 0; i < N; ++i) cin >> S[i];
  
  sort(S, S+N); // 昇順にソート
  
  for(int i = 0; i < N; ++i)
    cout << S[i];
  
  cout << endl;
  
  return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        double[] array = new double[n];
        for (int i = 0; i < n; i++) {
            array[i] = Double.parseDouble(sc.next());
        }
        double sum = 0;
        for (int i = 0; i < n; i++) {
            sum += 1 / array[i];
        }
        System.out.println(1.0 / sum);
    }
}


Measured memory_bytes: 21972
#include<iostream>
#include<algorithm>
using namespace std;
int a[100010];
int main()
{
    int n;
    long long ans,a1=-2,a2=-2;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=n;i>=2;i--)
    {
        if(a[i]==a[i-1])
        {
            a1=a[i];
            a[i]=a[i-1]=-1;
            break;
        }
    }
    for(int i=n;i>=2;i--)
    {
        if(a[i]==a[i-1]&&a[i]!=-1)
        {
            a2=a[i];
            break;
        }
    }
    if(a1!=-2&&a2!=-2)
    {
        cout<<a1*a2<<endl;
    }
    else
    {
        cout<<0<<endl;
    }
    return 0;
}

Measured memory_bytes: 640
# abcde	s=input()	s='abcde'
# abcde	s=list(input())	s=['a', 'b', 'c', 'd', 'e']
# 5(1つだけ)	a=int(input())	a=5
# 1 2	| x,y = s_inpl()   |	x=1,y=2
# 1 2 3 4 5 ... n 　	li = input().split()	li=['1','2','3',...,'n']
# 1 2 3 4 5 ... n 　	li = inpl()	li=[1,2,3,4,5,...,n]
# FFFTFTTFF 　	li = input().split('T')	li=['FFF', 'F', '', 'FF']

# INPUT
# 3
# hoge
# foo
# bar
# ANSWER
# n=int(input())
# string_list=[input() for i in range(n)]

import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]

def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

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


N = i_inpl()
A = l_inpl()

# dp[i][0]: i-1まで-1を偶数回乗算
# dp[i][1]: i-1まで-1を奇数回乗算
dp = [[-INF] * 2 for _ in range(N+1)]
dp[0][0] = 0

for i in range(N):
    dp[i+1][0] = max(dp[i][0] + A[i], dp[i][1] - A[i])
    dp[i+1][1] = max(dp[i][0] - A[i], dp[i][1] + A[i])

print(dp[N][0])

Measured memory_bytes: 82528
using System;
using System.Collections.Generic;
using System.Text;
using System.Numerics;
using System.IO;

namespace SolutionCS
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int N = int.Parse(s[0]);
            int A = int.Parse(s[1]);
            int B = int.Parse(s[2]);

            Console.WriteLine(Math.Min(N * A, B));
        }
    }
}


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

int main() {
  int N;
  cin >> N;
  
  vector<int> vec(N);
  for(int i = 0; i < N; i++){
    cin >> vec.at(i);
  }
  
  sort(vec.begin(), vec.end());
  reverse(vec.begin(), vec.end());
  
  int a = 0;
  int b = 0;
  for(int j = 0; j < N; j++){
    if(j % 2 == 0){
      a += vec.at(j);
    }
    else{
      b += vec.at(j);
    }
  }
  cout << a - b << endl;
}
      

Measured memory_bytes: 256
/** "Ever tried.
         Ever failed.
               No matter.
                   Try Again.
                        Fail again.
                             Fail better.**/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define bp  __builtin_popcount
#define endl "\n"
#define oo 0x3f3f3f3f3f3f3f3fLL
#define pb push_back
#define loop(i,n) for(int i = 0;i < int(n);i++)
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define sz(s) (int)(s.size())
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define debug(x) cout<<" LOOK "<<(#x)<<" = "<<x <<'\n'
#define NumofDigits(n)   ((long long)log10(n)+1)

using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;
const int maxn=1e5+5;
const  double EPS = 1e-9;
const int MOD = 1e9+7;
/*
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
ll fastpow(ll b, ll p)
{if(!p)return 1;ll ret = fastpow(b, p >> 1);ret *= ret;if(p&1)ret*= b;return ret;}
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};*/
inline void File()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
}


int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    //File();
    ll n;
    cin >> n;
    vector <ll> a(n), b(n);
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = a[i] - (i + 1);
    }
    sort(all(b));
    ll item = b[n/2];
    ll ans = 0;
    for(int i = 0; i <n; i++)
        ans += abs(a[i] - (i + 1 + item));
    cout << ans << "\n";
}


Measured memory_bytes: 6364
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.IOException;
import java.util.stream.Stream;
import java.util.Arrays;
import java.util.function.Function;
import java.util.stream.Collectors;
import java.util.List;
import java.util.Collections;

public class Main {
    
    public static long cnt = 0;
    
    public static void main(String[] args) throws Exception {
        int[] A = getContents().stream().skip(1).mapToInt(Integer::parseInt).toArray();
        shellSort(A);
        System.out.println(cnt);
        for(int n : A)
            System.out.println(n);
    }
    
    public static ArrayList<String> getContents() throws IOException{
        String line;
        ArrayList<String> list = new ArrayList<String>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while((line = br.readLine()) != null) list.add(line);
        
        return list;
    }
    
    public static void swap(int[] A, int i, int j){
        int v = A[j];
        A[j] = A[i];
        A[i] = v;
    }
    
    public static void insertionSort(int[] A, int g){
        for(int i = g, len = A.length; i < len; ++i){
            int v = A[i];
            int j = i - g;
            while(j >= 0 && A[j] > v){
                A[j + g] = A[j];
                j -= g;
                ++cnt;
            }
            A[j + g] = v; 
        }
    }
    
    public static void shellSort(int[] A){
        int len = A.length / 9;
        int h = 1;
        List<Integer> G = new ArrayList<Integer>(Arrays.asList(h));
        while(h <= len){
            h = 3 * h + 1;
            G.add(h);
        }
        Collections.reverse(G);
        
        int m = G.size();
        System.out.println(m);
        System.out.println(G.stream().map(String::valueOf).collect(Collectors.joining(" ")));
        
        for(int i = 0; i < m; ++i){
            insertionSort(A, G.get(i));
        }
    }
}


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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);   
    int n;
    cin >> n;
    vector<P> m(n);
    vector<ll> x, y;
    rep(i,n) cin >> m[i].first >> m[i].second;
    rep(i,n){
        int X = m[i].first, Y = m[i].second;
        x.push_back(X-Y);
        y.push_back(X+Y);
    }
    
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());
    ll ans = max(x[n-1]-x[0], y[n-1]-y[0]);
    cout << ans << endl;
}

Measured memory_bytes: 8240
import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))
import heapq

def main():
    N, M = input_nums()
    A = input_nums()
    A = list(map(lambda x: -x, A))
    heapq.heapify(A)

    for _ in range(M):
        tmp_min = heapq.heappop(A)
        heapq.heappush(A, (-1)*(-tmp_min//2))
    print(-sum(A))

if __name__ == '__main__':
    main()

Measured memory_bytes: 14180
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    int A =0;
    if ( 1 <= N && N <= 9 ) {
        A += N;
    }
    else if (10 <= N && N <= 99) {
        A += 9;
    }
    else if (100 <= N && N<= 999) {
        A = 9 + N - 99;
    }
    else if (1000 <= N && N<= 9999) {
        A += 909;
    }
    else if (10000 <= N && N <= 99999){
        A += 909 + N - 9999;
    }
    else {
        A += 90909;
    }
    cout << A << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

vector<int> cy;
int i0 = -1;

struct Graph {
    struct Vertex { int n, f; };
    struct Edge { int i, n; };
    Graph(int n, int m) : v(n, { -1, 0 }), e(m), n(n), m(0) {}
    void add_edge(int i, int j) {
        e[m] = { j, v[i].n };
        v[i].n = m;
        m++;
    }
    void dfs(int i) {
        if (v[i].f) {
            if (v[i].f < 0) i0 = i;
            return;
        }
        v[i].f = -1;
        for (int j = v[i].n; j >= 0; j = e[j].n) {
            Edge &o = e[j];
            dfs(o.i);
            if (i0 != -1) break;
        }
        v[i].f = 1;
        if (i0 >= 0) {
            cy.push_back(i);
            if (i == i0) i0 = -2;
        }
    }
    void solve() {
        for (int i = 0; i < n; i++) {
            dfs(i);
            if (!cy.empty()) break;
        }
        if (cy.empty()) {
            cout << -1 << endl;
            exit(0);
        }
        reverse(cy.begin(), cy.end());
        int k = cy.size();
        while (1) {
            for (int i = 0; i < n; i++) {
                v[i].f = 0;
            }
            for (int h = 0; h < k; h++) {
                v[cy[h]].f = 1;
            }
            int b = 0, h0, h1;
            for (int h = 0; h < k; h++) {
                int i = cy[h], i1 = cy[(h + 1) % k];
                for (int j = v[i].n; j >= 0; j = e[j].n) {
                    Edge &o = e[j];
                    if (o.i != i1 && v[o.i].f) {
                        b = 1;
                        h0 = h;
                        h1 = find(cy.begin(), cy.begin() + k, o.i) - cy.begin();
                        break;
                    }
                }
                if (b) break;
            }
            if (!b) {
                cout << k << '\n';
                for (int h = 0; h < k; h++) {
                    cout << cy[h] + 1 << '\n';
                }
                exit(0);
            }
            rotate(cy.begin(), cy.begin() + h1, cy.begin() + k);
            k = (k + h0 - h1 + 1) % k;
        }
    }
    vector<Vertex> v;
    vector<Edge> e;
    int n, m;
};

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

    int n, m;
    cin >> n >> m;

    Graph g(n, m);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;

        g.add_edge(a, b);
    }

    g.solve();

    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        //var n = int.Parse(Console.ReadLine());
        int[] kt = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
        var k = kt[0];
        var t = kt[1];

        var max = a.Max();
        var tmp = max - (a.Sum() - max + 1);
        
        var ans = 0;
        if(tmp > 0) ans = tmp;

        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 28232
N = int(input())
p = list(map(int, input().split()))

isYes = False
for i in range(N):
    for j in range(N):
        p_ = p.copy()
        p_[i], p_[j] = p_[j], p_[i] # swap
        for n in range(N-1):
            if p_[n] > p_[n+1]:
                break
            elif n == N - 2:
                isYes = True
if isYes:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3064
S = list(input())
N = len(S)
D = {}
for i in range(N):
    D[S[i]] = D.get(S[i],[-1])
    D[S[i]].append(i)
out = 100
for L in D.values():
    L.append(N)
    LN = len(L)
    tmp = 0
    for i in range(LN-1):
        tmp = max(tmp, L[i+1]-L[i]-1)
    out=min(out,tmp)
print(out)


Measured memory_bytes: 61884