akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cmath>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>

#ifdef _DEBUG
#define DMP(x) cerr << #x << ": " << x << "\n"
#else
#define DMP(x) ((void)0)
#endif

using namespace std;
using lint = long long;

#pragma GCC optimize ("-O3", "unroll-loops")
constexpr int nmax = 204800, block = 4096, unrl = 8;
int a[nmax], b[nmax];

int main() {

	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) scanf("%d", &a[i]);
	for (int i = 0; i < N; i++) scanf("%d", &b[i]);

	int ans = 0;
	for (int i = 0; i + unrl <= N; i += unrl) {
		for (int j = 0; j + block <= N; j += block) {
			for (int k = j; k < block + j; k++) {

				ans ^= (a[i + 0] + b[k]) ^ (a[i + 1] + b[k]);
				ans ^= (a[i + 2] + b[k]) ^ (a[i + 3] + b[k]);
				ans ^= (a[i + 4] + b[k]) ^ (a[i + 5] + b[k]);
				ans ^= (a[i + 6] + b[k]) ^ (a[i + 7] + b[k]);

			}
		}
	}

	for (int i = 0; i < N / unrl * unrl; i++) {
		for (int j = N / block * block; j < N; j++) {
			ans ^= a[i] + b[j];
		}
	}	
	for (int i = N / unrl * unrl; i < N; i++) {
		for (int j = 0; j < N; j++) {
			ans ^= a[i] + b[j];
		}
	}

	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 1792
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]

def Eratosthenes(n):
    from math import sqrt
    res = [True] * (n+1)
    res[0] = False
    res[1] = False
    
    for i in range(2,int(sqrt(n))+1):
        if res[i]:
            for j in range(2*i,n+1,i):
                res[j] = False
    return res

class BIT():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    #bit_indexにxをO(log(n))で加算する
    def add(self,i,x):
        #if(i<=0 or i>n):return iに0以下の数字は代入しない
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)
    #bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    def sum(self,i):
        s = 0
        #iに0以下の数字は代入しない。
        while i > 0:
            s+=self.bit[i]
            i -= (i & -i)
        return s
    
    def rangesum(self,i,k):
        return self.sum(k) - self.sum(i)
    #a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    #xが0以下の場合は該当するものなし→0を返す
    def lower_bound(self,x):
        if x <= 0:
            return 0
        else:
            i = 0
            r = 1
            #最大としてありうる区間の長さを取得する
            #n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<self.n):
                r=r<<1
            len = r
            while len > 0:
                if(i+len<self.n and self.bit[i+len]<x):
                    x-=self.bit[i+len]
                    i+=len
                len = len >> 1
            return i+1

def main():
    max_num = 100000
    Q = I()
    S = Eratosthenes(max_num)
    bit = BIT(max_num)
    
    #bitの初期化
    for a in range(1,max_num, 2):
        b = (a+1) // 2
        if S[a] and S[b]:
            bit.add(a, 1)
    
    #queryの処理
    
    for q in range(Q):
        l, r = MI()
        print(bit.sum(r)-bit.sum(l-1))

if __name__ == "__main__":
    main()


Measured memory_bytes: 80528
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}


int main(){
  int n;
  cin>>n;
  vector<int> v(n);
  rep(i,n){
    cin>>v[i];
  }

  vector<int> ans;
  rep(_,n){
    int t=-1;
    rrep(i,v.size()-1){
      if(v[i]==i+1){
        t=i;
        ans.PB(i+1);
        break;
      }
    }
    if(t==-1) continue;
    v.erase(v.begin()+t);
  }

  if(v.empty()){
    reverse(all(ans));
    rep(i,n){
      cout<<ans[i]<<endl;
    }
  }
  else{
    cout<<-1<<endl;
  }
}


Measured memory_bytes: 256
# abc105_b.py
# https://atcoder.jp/contests/abc105/tasks/abc105_b

# B - Cakes and Donuts /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点: 200点

# 問題文
# ABC 洋菓子店では, 1個 4 ドルのケーキと 1 個 7 ドルのドーナツが売られている.
# このとき, 合計金額が Nドルとなる買い方はあるか, 判定せよ. ただし, 同じ商品を二個以上買っても良く, 買わない商品があっても良いものとする.

# 制約
#     Nは 1 以上 100以下の整数

# 入力
# 入力は以下の形式で標準入力から与えられる.
# N

# 出力
# 合計が Nドルとなる買い方がある場合 Yes, そうでない場合 No と出力せよ.

# 入力例 1
# 11

# 出力例 1
# Yes

# ケーキを 1個, ドーナツを 1 個買えば合計 4+7=11ドルとなる.

# 入力例 2
# 40

# 出力例 2
# Yes

# ケーキを 10個買えば 4×10=40ドルとなる.

# 入力例 3
# 3

# 出力例 3
# No

# ケーキの値段は 4ドル, ドーナツの値段は 7 ドルと, どちらも 3 ドルより高いためそのような買い方は存在しない. 


def calculation(lines):
    N = int(lines[0])
    result = 'No'
    for i in range(25):
        for j in range(15):
            if i*4 + j*7 == N:
                result = 'Yes'
    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['11']
        lines_export = ['Yes']
    if pattern == 2:
        lines_input = ['40']
        lines_export = ['Yes']
    if pattern == 3:
        lines_input = ['3']
        lines_export = ['No']
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9236
#include<bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(0)
#define pb push_back
#define digit(x) floor(log10(x))+1
#define mod 1000000007
#define L_MAX 1e18
using ll = long long;
using ld = long double;
using ii = pair<ll,ll>;
using iii = tuple<ll,ll,ll>;
using matrix = vector<vector<ll>>;
using arr = vector<ll>;
using vs = vector<string>;
using pv = vector<ii>;
using umap = unordered_map<ll,ll>;
#define in1(x) scanf("%lld",&x)
#define in2(x,y) scanf("%lld %lld",&x,&y)
#define in3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define all(x) x.begin(),x.end()
#define debug(x) cerr << #x << " is " << x << endl;
void showArr(arr a){
    for(auto i : a) cout<<i<<" ";
    cout<<endl;
}
ll dx[]={-1,1,-1,1,0,0,-1,1};
ll dy[]={-1,1,0,0,-1,1,1,-1};
ll Solve(ll index,arr a,ll n,ll dp[]){
    if(index>=n-1)
        return 0;
    if(dp[index]!=-1)
        return dp[index];
    ll left=L_MAX,right=L_MAX;
    if(index+1<n){
        if(dp[index+1]==-1)
            dp[index+1]=Solve(index+1,a,n,dp);
        left=dp[index+1]+abs(a[index]-a[index+1]);
    }
    if(index+2<n){
        if(dp[index+2]==-1)
            dp[index+2]=Solve(index+2,a,n,dp);
        right=dp[index+2]+abs(a[index]-a[index+2]);
    }
    return dp[index]=min(left,right);
}
int main(){
    fast;
    ll n;
    cin>>n;
    arr a;
    ll dp[100009];
    for(int i=0;i<n;i++){
        ll x;
        cin>>x;
        a.pb(x);
    }
   // memset(dp,-1,sizeof(dp));
   // cout<<Solve(0,a,n,dp)<<endl;
    dp[n-1]=0;
    dp[n-2]=abs(a[n-1]-a[n-2]);
    for(int i=n-3;i>=0;i--){
        dp[i]=min(dp[i+2]+abs(a[i]-a[i+2]),abs(a[i]-a[i+1])+dp[i+1]);
    }
    cout<<dp[0]<<endl;
    return 0;
}

Measured memory_bytes: 1908
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <string>
#include <iostream>
#include <complex>
#include <ctime>
#include <cmath>
#include <cstdio>
#include <stack>
#include <map>
#include <list>
#include <queue>
#include <deque>
#include <random>
#include <set>
#include <vector>
#include <unordered_map>
#include <bitset>
#include <unordered_set>
#include <array>
#include <forward_list>
#include <chrono>
#include <iomanip>
#include <utility>
#include <assert.h>

#pragma GCC optimize("Ofast")
#pragma target("sse", "sse1")

#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

mt19937 gen(34);

ll n, a, b;

int main()
{
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#else
	//freopen("meetings.in", "r", stdin);
	//freopen("meetings.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> a >> b;
	if ((b - a) % 2ll == 0)
	{
		cout << (b - a) / 2ll;
		return 0;
	}
	ll d = a + b - 1;
	d = min(d, (n - a) + (n - b) + 1);
	if (d & 1)
		d++;
	cout << d / 2;
	return 0;
}

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

using ld=long double;
int LOOP=100;
const int DAY=86400;
ld solve(int n,ld l){
    vector<ld> sum(DAY,0);
    for(int i=0;i<n;i++){
        int s,t,u;
        cin>>s>>t>>u;
        sum[s]+=u;
        if(t<DAY) sum[t]-=u;
    }
    for(int i=0;i+1<DAY;i++){
        sum[i+1]+=sum[i];
    }
    ld lb=0,ub=1e6;
    for(int i=0;i<LOOP;i++){
        ld mid=(lb+ub)/2;
        ld rest=l;
        bool isok=true;
        for(int i=0;i<DAY;i++){
            rest=min(rest-sum[i]+mid,l);
            if(rest<1e-9){
                isok=false;
                break;
            }
        }
        ld prerest=rest;
        for(int i=0;i<DAY;i++){
            rest=min(rest-sum[i]+mid,l);
            if(rest<1e-9){
                isok=false;
                break;
            }
        }
        if(abs(rest-prerest)<1e-9 && isok) ub=mid;
        else lb=mid;
    }
    return ub;
}
int main(){
    int n;
    ld l;
    while(cin>>n>>l,n){
        cout<<setprecision(10)<<fixed;
        cout<<solve(n,l)<<endl;
    }
    return 0;
}


Measured memory_bytes: 4644
package main

import (
	"fmt"
	"io"
	"os"
)

func ufRoot(e []int, x int) int {
	if e[x] == x {
		return x
	}
	return ufRoot(e, e[x])
}

func ufUnite(e []int, x int, y int) {
	rx := ufRoot(e, x)
	ry := ufRoot(e, y)
	if rx != ry {
		e[rx] = ry
		e[x] = ry
	}
}

func answer(reader io.Reader, writer io.Writer) {
	var n, m int
	_, _ = fmt.Fscan(reader, &n, &m)
	t := make([]int, n)
	for i := 0; i < n; i++ {
		t[i] = i
	}

	for i := 0; i < m; i++ {
		var x, y, z int
		_, _ = fmt.Fscan(reader, &x, &y, &z)
		x--
		y--
		ufUnite(t, x, y)
	}
	//fmt.Printf("%v\n", t)
	count := 0
	for i := 0; i < n; i++ {
		if t[i] == i {
			count++
		}
	}
	_, _ = fmt.Fprintf(writer, "%d", count)
}

func main() {
	answer(os.Stdin, os.Stdout)
}


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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  rep(i,n){
    cin>>a[i];
    b[i]=a[i];
  }
  sort(b.begin(),b.end());
  int max1 = b[n-1];
  int max2 = b[n-2];
  if(max1==max2){
    rep(i,n) cout<<max1<<endl;
  }
  else{
  rep(i,n){
    if(a[i]==max1)cout<<max2<<endl;
    else cout<<max1<<endl;
  }
  }
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//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; }
 
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
*/

int main(){
    int N; cin >> N;
    vector<int> a(N+1), pos(N+1);
    for(int i=1; i<=N; i++){
        cin >> a[i];
        pos[a[i]] = i;
    }

    ll ans = 0LL;
    set<int> se{0, N+1};

    for(int i=1; i<=N; i++){
        int r = *(se.lower_bound(pos[i]));
        int l = *(--se.lower_bound(pos[i]));
        ans += (ll)i*(pos[i]-l)*(r-pos[i]);
        se.insert(pos[i]);
    }

    cout << ans << endl;
}

Measured memory_bytes: 11136
#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
    int n, a[100000], ai, res = 0;
    scanf("%d", &n);
    fill_n(a, n, 0);
    for(int i = 0; i < n; i++){
        scanf("%d", &ai);
        if(ai > n) res++;
        else a[ai-1]++;
    }

    for(int i = 1; i <= n; i++){
        if(a[i-1] >= i) res += (a[i-1] - i);
        else res += a[i-1];
    }

    printf("%d", res);
    return 0;
}

Measured memory_bytes: 512
/*input
2
0 0 2 3 3 2 3 2 1 3
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 305;
double dp[N][N][N];
int main()
{
	int n;cin>>n;
	vector<int> cnt(4,0);
	for(int i=1;i<=n;i++) 
	{
		int x;cin>>x;
		cnt[x]++;
	}

	dp[0][0][0] = 0;
	for(int c=0;c<=n;c++) 
	{
		for(int b=0;b<=n;b++)
		{
			for(int a=0;a<=n;a++)
			{
				dp[a][b][c]=0;
				if(a+b+c==0) continue;
				if(a>0) dp[a][b][c] += ((double)a)*(dp[a-1][b][c]);
				if(b>0) dp[a][b][c] += ((double)b)*(dp[a+1][b-1][c]);
				if(c>0) dp[a][b][c] += ((double)c)*(dp[a][b+1][c-1]);
				dp[a][b][c]+=(double)n;
				dp[a][b][c]/=(double)(a+b+c);
			}
		}
	}
	// cout<<cnt[1]<<" "<<cnt[2]<<" "<<cnt[3]<<"\n";
	cout<<setprecision(15)<<dp[cnt[1]][cnt[2]][cnt[3]]<<"\n";

	return 0;
}


Measured memory_bytes: 220792
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>

using namespace std;

int main(){
  int N;
  vector<int> x;
  vector<int> dx;
  int a,outnum;
  int more,less;
  cin >> N;
  for(int i=0;i<N;++i){
    cin >> a;
    x.push_back(a);
    dx.push_back(a);
  }
  sort(dx.begin(),dx.end());
  for(int i=0;i<N;++i){
    outnum = x[i];
    less = dx[(N/2)-1];
    more = dx[(N/2)];
    if(outnum<=less){
      cout << more << endl;
    }else{
      cout << less << endl;
    }
  }
}

Measured memory_bytes: 3948
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args)throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(input.readLine());
        StringTokenizer tokenizer = new StringTokenizer(input.readLine());
        int d = Integer.parseInt(tokenizer.nextToken());
        int x = Integer.parseInt(tokenizer.nextToken());
        int sum, count, index;

        for (int i = 0; i < n; i++) {
            sum = 0;
            count = 0;
            index = 1;
            int value = Integer.parseInt(input.readLine());
            while (count <= d){
                sum++;
                count  = (index * value) + 1;
                index++;
            }
            x+= sum;
        }
        System.out.println(x);
    }
}


Measured memory_bytes: 22996
def area(p)
  x, y = p[0]
  s = 0.0
  oldV = [p[1][0]-x, p[1][1]-y]
  p[2..-1].each do |x1, y1| # 点の数が3以上であることに依存
    va = [x1-x, y1-y]
    s += triangleArea(va, oldV)
    oldV = va
  end
  s.abs
end

def triangleArea(a, b)
  (a[0] * b[1] - a[1] * b[0])/2.0
end

if __FILE__ == $0
  points = gets.to_i.times.map{ gets.split.map(&:to_i) }
  p area(points)
end

Measured memory_bytes: 6152
import sys
from collections import Counter
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    S = list(input() for _ in range(n))
    D = Counter(S)
    print(len(D))

if __name__ == '__main__':
    resolve()


Measured memory_bytes: 132568
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        Deque <Integer> deque = new ArrayDeque<Integer>();
        for(int i = 0; i < n; i++){
            String command = sc.next();
            if(command.equals("insert")){
                Integer number = Integer.parseInt(sc.next());
                deque.push(number);
            }else if(command.equals("delete")){
                Integer number = Integer.parseInt(sc.next());
                deque.remove(number);
            }else if(command.equals("deleteFirst")){
                deque.removeFirst();
            }else{
                deque.removeLast();
            }
        }
        StringBuilder sb = new StringBuilder();
        sb.append(deque.poll());
        for(int num : deque)
            sb.append(" ").append(num);
        
        System.out.println(sb);

    }
}


Measured memory_bytes: 328356
from collections import Counter

def resolve():
    N=int(input())
    A=list(map(int,input().split()))

    ans=0
    c = Counter(A)
    values, counts = zip(*c.most_common())
    for j in counts:
        if j >= 2:
            ans += j * (j - 1) // 2

    for i in A:
        if c[i]>=3:
            print(ans-(c[i]*(c[i]-1)//2-(c[i]-1)*(c[i]-2)//2))
        elif c[i]==2:
            print(ans-1)
        else:
            print(ans)






resolve()

Measured memory_bytes: 119244
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=1e9+7;
#define N 205050

ll n;
ll p;
ll a[N];
ll c[4]={1,9,7,4};
string t="keyence";
main(){
    string s;cin>>s;
    int l=0;
    while(l<=6&&s[l]==t[l])l++;
    int r=0;
    while(r<=6&&s[s.size()-1-r]==t[6-r])r++;
    if(l+r>=7)cout<<"YES";
    else cout<<"NO";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
const ll INF = 1e10;

int main() {
    string s; cin >> s;
    int n = s.size();
    int cnt = 0;
    for (int i = 0; i < n; i ++) {
        if (s.at(i) == 'p') cnt ++;
    }
    cout << n/2 - cnt << endl;
}



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

int main() {
  string str;
  cin >> str;
  string N,M;
  N = "AAA";
  M = "BBB";
  
  if (str == M) {
    cout << "No" << endl;
  }
  else if (str == N) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
  
  
}


Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <string>
#include <math.h>
using namespace std;
#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define printV(vec) for(int i = 0; i < SZ(vec); i++){cout << vec[i];if (i==SZ(vec)-1){cout<<endl;}else{cout << " ";}}
#define printA(arr,n) for(int i = 0; i < n; i++){cout << arr[i];if (i==n-1){cout<<endl;}else{cout << " ";}}
typedef long long ll;

int main()
{
  int A;
  int B;

  cin >> A >> B;

  int C = B-A;

  int D = ((1+C)*C)/2;

  cout << D-B << endl;

  return 0;
}


Measured memory_bytes: 256
loop do
  n, q = gets.split.map(&:to_i)
  break if n == 0
  count = Hash.new(0)
  n.times do
    gets.split.map(&:to_i)[1..-1].each do |d|
      count[d] += 1
    end
  end
  m = count.values.max
  if m == nil || m < q
    puts 0
  else
    puts count.keys.select {|d| count[d] == m}.min
  end
end


Measured memory_bytes: 7020
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD (1'000'000'007)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
typedef long long ll;
typedef pair<int, int> pii;

int main(void)
{
  int x,a;
  cin >> x >> a;
  pr(x < a ? 0 : 10);  
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second

ll gcd(ll a,ll b){//最大公約数を求める関数
    if(a<b){
        swap(a,b);
    }

    if(a%b == 0){
        return b;
    }else{
    return gcd(b,a%b);
    }
}
/*問題文を言い換えると、A1からANのうち一つの数を除いた時の、
A1からAN(全部でN-1個）の最大公約数の最大値を求める
とりあえず一つずつ除いてみて、最大公約数を求め、最大値を出力すればよい

同じ部分のgcdを何度も計算したくない→累積gcd(先に計算しておいて後で利用）
同じ処理を何度もしたくない時は先に計算しておいて後で参照できるようにしておく*/

int main(){
    ll n,ans=0;
    cin >> n;
    vector<ll> v(n),g(n,0),c(n,0);//gは左からの,cは右からの累積テーブル
    for(int i=0;i < n;i++)//入力
    {
        cin >> v.at(i);
    }

    g.at(1)=v.at(0);
    for(int i=2;i < n;i++)
    {
        g.at(i)=gcd(g.at(i-1),v.at(i-1));
    }//g.at(i)はv.at(0)からv.at(i-1)のgcd

    c.at(n-2)=v.at(n-1);
    for(int i=n-3;0<=i;i--)
    {
        c.at(i)=gcd(c.at(i+1),v.at(i+1));
    }//c.at(i)はv.at(i+1)からv.at(n)のgcd

    for(int i=1;i < n-1;i++)
    {
        ans=max(ans,gcd(g.at(i),c.at(i)));
        //gcd(g.at(i),c.at(i)) はv.at(i)を除いたときの最大公約数
        //g.at(i)はv.at(0)からv.at(i-1)の最大公約数、同様に
        //c.at(i)はv.at(i+1)からv.at(n-1)の最大公約数
        //v.at(0)とv.at(n-1)を除くときは下で別の処理をしてる（それぞれ左側,右側のgcdがないので)
    }
    ans=max(ans,g.at(n-1));
    ans=max(ans,c.at(0));
    cout << ans << endl;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<int> x, y, h;
int main() {
	cin >> n;
	for(int i = 0; i < n; i++) {
		int xs, ys, hs;
		cin >> xs >> ys >> hs;
		x.push_back(xs);
		y.push_back(ys);
		h.push_back(hs);
	}

  for (ll k = 0;k < n;k++) {
		if (h[k] > 0) {
			for (ll i = 0;i <= 100;i++) {
				for (ll j = 0;j <= 100;j++) {
					ll H = h[k] + abs(x[k] - i) + abs(y[k] - j);
					bool flag = true;
					for (ll l = 0;l < n;l++) {
						if (h[l] != max(H - abs(x[l] - i) - abs(y[l] - j), (ll)0))flag = false;
					}
					if (flag) {
						cout << i << " " << j << " " << H << endl;
						return 0;
					}
				}
			}
		}
	}
}

Measured memory_bytes: 256
#include "iostream"
#include "string"

using namespace std;

int main() {
	string a, b;
	cin >> a >> b;
	int num = stoi(a + b);
	bool flag = false;
	for (int i = 0; i < 1001; i++) {
		if (num == i*i) flag = true;
	}
	if (flag) cout << "Yes" << endl;
	else cout << "No" << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define int long long int
using namespace std;
#define pb push_back
int32_t main()
{
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	int d,t,s;
	cin >> d >> t >> s;
	if(t*s>=d){
		cout << "Yes";
	}
	else{
		cout << "No";
	}


	return 0;
}


Measured memory_bytes: 3572
#pragma region Macros
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define rep2(i, a, b) for(ll i = a; i <= b; ++i)
#define rep(i, n) for(i = 0; i < n; ++i)
#define rep3(i, a, b) for(ll i = a; i >= b; --i)
using namespace std;

// _________コーディングはここから！！___________

int n, m, k, i;
constexpr int N = 200010;
int a[N], b[N];
constexpr int sz = 5000000;
char reader[sz];
char *pos = reader;
int nn,now,ans;
int kk;
main() {
    reader[fread(reader, sizeof(char), sizeof(char) * sz, stdin)];
    while('0' <= *pos and *pos <= '9') n = n * 10 + *pos++ - '0';
    pos++;
    while('0' <= *pos and *pos <= '9') m = m * 10 + *pos++ - '0';
    pos++;
    while('0' <= *pos and *pos <= '9') k = k * 10 + *pos++ - '0';
    nn = n;
    pos++;
    rep(i, n) {
        while('0' <= *pos and *pos <= '9') a[i + 1] = a[i + 1] * 10 + *pos++ - '0';
        pos++;
        a[i + 1] += a[i];
        if(a[i + 1] > k) {
            nn = i;
            ++i;
            for(; i < n; ++i) {
                while('0' <= *pos and *pos <= '9') pos++;
                pos++;
            }
            break;
        }
    }
    while(*pos and *pos <= 32) pos++;
    rep(i, m) {
        while('0' <= *pos and *pos <= '9') b[i + 1] = b[i + 1] * 10 + *pos++ - '0';
        pos++;
        b[i + 1] += b[i];
        if(b[i + 1] > k) {
            m = i;
            break;
        }
    }
    now = ans = nn;
    for(i = 1; i <= m; i++) {
        kk = k - b[i];
        while(a[now] > kk) now--;
        ans = max(ans, i + now);
    }
    pos = reader;
    i = 0;
    do {
        *pos++ = ans % 10 + '0';
        ans /= 10;
        i++;
    } while(ans);
    reverse(reader, reader + i);
    fwrite(reader, sizeof(char), sizeof(char) * i, stdout);
}


Measured memory_bytes: 7744
#include<stdio.h>
#define N 250

typedef struct{
  int p;
  int l;
  int r;
  int k;
}Node;

Node node[N];

int main(){
  int i,n;
  scanf("%d",&n);
  
  for(i = 1; i < n+1; i++){
    scanf("%d",&node[i].k);
  }
  
  for(i = 1; i < n+1; i++){
    if(i == 1){
      node[i].p = -1;
    }else{
      node[i].p = i/2;
    }
    if(2*i > n){
      node[i].l = node[i].r = -1;
    }else{
      node[i].l = 2*i;
    }
    if(2*i+1 > n){
      node[i].r = -1;
    }else{
      node[i].r = 2*i+1;
    }
  }
  for(i = 1; i < n+1;i++){
    printf("node %d: key = %d, ",i,node[i].k);
    if(node[i].p != -1){
      printf("parent key = %d, ",node[node[i].p].k);
    }
    if(node[i].l != -1){
      printf("left key = %d, ",node[node[i].l].k);
    }
    if(node[i].r != -1){
      printf("right key = %d, ",node[node[i].r].k);
    }
    printf("\n");
    
  }
  return 0;
}

Measured memory_bytes: 604
#include"bits/stdc++.h"
using namespace std;
int main()
{
	int n=0;
	vector<vector<int>> grid(2);
	scanf("%d",&n);
	for(int i=0;i<2;i++)
	{
		vector<int> vec(n);
		for(int j=0;j<n;j++)
		{
			scanf("%d",&vec[j]);
		}
		grid[i]=vec;
	}
	int r=0;
	int max=0;
	int roffset=n-1;
	int j=0;
	while(roffset>=0)
	{
		for(int i=0;i<n;i++)
		{
			r+=grid[j][i];
			if(i==roffset&&j==0)
			{
				j++;
				roffset--;
				r+=grid[j][i];
			}

		}
		j=0;
		if(max<r)
		{
			max=r;
		}
		r=0;
	}
	printf("%d",max);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <assert.h>   
#include <vector>
#include <algorithm>
#include <time.h>
#include <numeric>
#include <string>
#include <cstring>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <numeric>
#include <deque>
#include <iomanip>
#include <cstdlib>
#include <climits>
#include <cmath>
#include <cstdio>
using namespace std;


//#define double long double
//#define int long long
//#define int unsigned long long

#define ll long long
#define ld long double 
#define pi pair<int, int> 
#define pl pair<ll,ll>  
#define pd pair<ld,ld> 
#define str string  
#define mp make_pair
#define vi vector<int> 
#define vl vector<ll> 
#define vd vector<ld> 
#define vs vector<str> 
#define vpi vector<pi> 
#define vpl vector<pl> 
#define vpd vector<pd> 
#define si set<int> 
#define FF(i,j,n) for(signed i=j;i<=n;i++)  
#define DD(i,j,n) for(signed i=j;i>=n;i--) 
#define F(i,j,n) for(signed i=j;i<n;i++)   
#define D(i,j,n) for(signed i=j;i>n;i--) 
#define mem(a,b) memset(a,b,sizeof(a))
#define ndl cout << endl
#define ull unsigned long long 

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;


#define sz(x) (signed)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back() 
#define fi first
#define se second
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

//math


const int mod = 1e9 + 7;

ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
int pct(int x) { return __builtin_popcount(x); } 
int bit(int x) { return 31-__builtin_clz(x); } // floor(log2(x)) 
int cdiv(int a, int b) { return a/b+!(a<0||a%b == 0); } // division of a by b rounded up, assumes b > 0 


//DEBUG, compile with -DLOCAL
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
  cerr << to_string(h); if (sizeof...(t)) cerr << ", ";
  DBG(t...); }
#ifdef LOCAL 
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define HERE cout << "===GOTHERE===" << endl
#else
#define dbg(...) 42
#define HERE 42
#endif


 /* ============== END OF HEADER ============== */





const int maxn = 1e5*3+20;

int n,_,q,k;
int a[1000];
double diff[1000];

void solve(){
	cin >> n;
	int sum = 0;
	FF(i,1,n){	
		cin >> a[i];
		sum += a[i];
	}
	double avg = sum / (double)n;
	double mind = inf;
	FF(i,1,n){
		diff[i] = abs(a[i] - avg);
		mind = min(mind, diff[i]);
	}

	int ans = -1;
	FF(i,1,n){
		if(diff[i] == mind){
			ans = i;
			break;
		}			
	}
	cout << ans - 1 << endl;

}

signed main(){
  //clock_t t1 = clock();  
	IOS
	solve();
  
  //cout << "THE ALGORITHM TOOK: " << (clock() - t1) * 1.0 / CLOCKS_PER_SEC * 1000 << "ms"<< endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int d = sc.nextInt();
        int[][] x = new int[n][d];
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < d ; j++){
                x[i][j] = sc.nextInt();
            }
        }
        int ebishu = 0;
        sc.close();
        for(int i = 0 ;i < n ; i++){
            for(int j = 0 ; j < i ; j++){
                double yono = 0;
                for(int k = 0 ; k < d ; k++){
                    yono += (x[i][k] - x[j][k]) * (x[i][k] - x[j][k]);
                }
                yono = Math.sqrt(yono);
                if(yono % 1 == 0){
                    ebishu++;
                }
            }
        }
        System.out.println(ebishu);
    }
}
//鶏になれ

Measured memory_bytes: 36084
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        sc.close();
        String sub  = s.replaceAll("ABC","");
        int ans = (n - sub.length())/3;
        System.out.println(ans);
    }
}

Measured memory_bytes: 21844
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int x;
    cin >> x;
    ll ans = 0;
    for (int i = 1; i <= x+1; ++i) {
        ans += (1LL << i);
    }
    cout << ans << "\n";
    return 0;
}

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

#define IO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define m(a,b) memset(a,b,sizeof(a))
#define rep(i,n) for(int i=1;i<=n;i++)
typedef long long ll;
typedef pair<string,int> p;
const int MAXN=1e5+10;
int n;
ll a[MAXN];

int main(){
	IO;
	while(cin>>n){
		rep(i,n) cin>>a[i];
		if (n==2) cout<<a[1]<<' '<<a[0]<<endl;
		else{
			sort(a+1,a+1+n);
			int t=a[n]/2;
			int Min=1<<29;
			int p;
			rep(i,n)
				if (abs(a[i]-t)<=Min){
					Min=abs(a[i]-t);
					p=a[i];
				}
			cout<<a[n]<<' '<<p<<endl;
		}
	}
	return 0;
}

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

int main()
{
    int i,j,k;
    int sum = 0;
    scanf("%d %d",&i,&j);
    while(j--){
        scanf("%d",&k);
        sum+=k;
    }
    if(sum%(i+1) > 0) k = 1;
    else k = 0;
    printf("%d\n",sum/(i+1)+k);
}


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

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pint;

const int INF = 1 << 30;
const ll LINF = 1LL << 60;
const int MOD = 1e9 + 7;


int main() {
    ll n, k; cin >> n >> k;
    vector<ll> a(n); rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());

    ll r = 1e18 + 1;
    ll l = -1e18 - 1;
    ll mid;
    while (r-l>1) {
        mid = (r+l) / 2;
        ll cnt = 0;
        rep(i, n) {
            if (a[i] > 0) {
                cnt += partition_point(a.begin(), a.begin()+i, [&](const ll v) {return v * a[i] <= mid;}) - a.begin();
            } else if (a[i] == 0) {
                if (mid >= 0) cnt += i;
            } else {
                cnt += a.begin()+i - partition_point(a.begin(), a.begin()+i, [&](const ll v) {return v * a[i] > mid;});
            }
        }
        if (cnt < k) l = mid;
        else r = mid;
    }
    
    cout << r << endl;



    return 0;
}


    


Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;

#define ll long long

int main() {
	ll a, b, c, k;
	ll sum = 0;
	cin >> a >> b >> c >> k;
	if (a > 0) {
		if (k >= a) {
			sum += a;
			k -= a;
		}
		else {
			sum = k;
			a -= k;
			k = 0;
		}
	}
	if (k > 0) {
		if (k >= b)k -= b;
	}
	if (k > 0) {
		sum -= k;
	}
	cout << sum;
	return 0;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
string s,t;
int x,y;
bool yes=false;
int main()
{
    cin>>s>>t;
    for (int i=0,j=s.size()-1;i<s.size()/2;i++,j--)
    {
        if (s[i]!=s[j])
        {
            x++;
            break;
        }
    }
    if (x==0)
        y++;
    x=0;
    while (s!=t)
    {
        if (s[s.size()-1]=='9')
        {
            for (int i=s.size()-1;i>=0;i--)
            {
                if (s[i]!='9')
                {
                    yes=true;
                    s[i]++;
                    for (int j=i+1;j<s.size();j++)
                        s[j]='0';
                    break;
                }
            }
            if (yes==false)
            {
                for (int i=0;i<s.size();i++)
                    s[i]='0';
                s+='1';
                reverse(s.begin(),s.end());
            }
        }
        else
            s[s.size()-1]++;
        for (int i=0,j=s.size()-1;i<s.size()/2;i++,j--)
        {
            if (s[i]!=s[j])
            {
                x++;
                break;
            }
        }
        if (x==0)
            y++;
        x=0;
    }
    cout<<y;
    return 0;
}


Measured memory_bytes: 256
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define int long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define divup(a,b) ( ( (a) + ( (b) - 1u) ) / (b) ) // a/b の余り切り上げ
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
ll mod = 1000000007;
ll mod9 = 1000000009;


signed main(){
    ll n;
    scanf("%lld",&n);
    pair<ll,ll> x[10];
    rep(i,n) scanf("%lld %lld",&x[i].first,&x[i].second);
    vector<ll> array(n);
    rep(i,n) array[i]=i;
    double dist[10][10];
    rep(i,n) rep(j,n) dist[i][j]= sqrt(pow(x[i].first-x[j].first,2)+pow(x[i].second-x[j].second,2));
    double ans = 0;
    ll cnt = 0;
    do{
        rep(i,n-1){
            ans += dist[array[i]][array[i+1]];
        }
        cnt++;
    }while(next_permutation(array.begin(),array.end()));
    ans /= 1.0*cnt;
    printf("%.8lf\n",ans);
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
        long long w,h,ans,i,cok,sisa;
        cin>>w>>h;
        if(w%3==0) {cout<<0<<endl; return 0;}
        if(h%3==0) {cout<<0<<endl; return 0;}
        ans=min(w,h);
        for(i=1;i<=w;++i)
        {
            cok=i*h;
            sisa=w-i;
            if(h%2==0)
            {
                ans=min(ans,abs(cok-h/2*sisa));
            }
            else
            {
                 ans=min(ans,max(max(abs(cok-h/2*sisa),sisa),abs(cok-(h/2*sisa+sisa))));

            }
        }
        swap(w,h);
        for(i=1;i<=w;++i)
        {
            cok=i*h;
            sisa=w-i;
            if(h%2==0)
            {
                ans=min(ans,abs(cok-h/2*sisa));
            }
            else
            {
                ans=min(ans,max(max(abs(cok-h/2*sisa),sisa),abs(cok-(h/2*sisa+sisa))));

            }
        }
        cout<<ans<<endl;
}


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

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#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 REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

//グローバル変数
    vector<long long> fact, fact_inv, inv;
    
//二項係数前処理計算量O(SIZE)
void init_nCk(int SIZE) {
    fact.resize(SIZE + 5);
    fact_inv.resize(SIZE + 5);
    inv.resize(SIZE + 5);
    fact[0] = fact[1] = 1;
    fact_inv[0] = fact_inv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < SIZE + 5; i++) {
        fact[i] = fact[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        fact_inv[i] = fact_inv[i - 1] * inv[i] % MOD;
    }
}

// xのn乗%modを計算
ll mod_pow(ll x, ll n, ll mod){
    ll res = 1;
    while(n > 0){
        if(n & 1) res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}

//nCk　計算量(1)
ll nCk(int n, int k) {
    assert(!(n < k));
    assert(!(n < 0 || k < 0));
    return fact[n] * (fact_inv[k] * fact_inv[n - k] % MOD) % MOD;
}

int main(){
    int N,M,K;
    cin>>N>>M>>K;
    ll tmp=0;
    REP2(i,1,N){
        tmp+=((i*(N-i))%MOD*mod_pow(M,2,MOD))%MOD;
        tmp%=MOD;
    }

    init_nCk(M*N);
    
    REP2(i,1,M){
        tmp+=((i*(M-i))%MOD*mod_pow(N,2,MOD))%MOD;
        tmp%=MOD;
    }
    tmp*=nCk(M*N-2,K-2);
    tmp%=MOD;
    cout<<tmp<<endl;

}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n, w;
        cin >> n >> w;
        vector<pair<int, int>> v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i].ff >> v[i].ss;
        }
        vector<int> ans[4];
        for(int i = 0; i < n; i++){
            ans[v[i].ff - v[0].ff].pb(v[i].ss);
        }
        for(int i = 0; i < 4; i++){
            sort(all(ans[i]), greater<int> ());
            // for(auto &it : ans[i]){
            //     cout << it << ' ';
            // }
            // cout << '\n';
        }
        vector<vector<int>> pre(n + 1, vector<int> (4));
        for(int i = 0; i < 4; i++){
            for(int j = 0; j < ans[i].size(); j++){
                pre[j + 1][i] = pre[j][i] + ans[i][j];
            }
            // for(int j = 0; j < ans[i].size(); j++){
            //     cout << pre[j + 1][i] << ' '; 
            // } 
            // cout << '\n';
        }
        int res = 0;
        for(int i = 0; i < ans[0].size() + 1; i++){
            for(int j = 0; j < ans[1].size() + 1; j++){
                for(int k = 0; k < ans[2].size() + 1; k++){
                    for(int l = 0; l < ans[3].size() + 1; l++){
                        int sum = pre[i][0] + pre[j][1] + pre[k][2] + pre[l][3];
                        if((i + j + k + l) * v[0].ff + (j + 2 * k + 3 * l) <= w){
                            res = max(res, sum);
                        }
                    }
                }
            }
        }
        cout << res << '\n';
    }
}

Measured memory_bytes: 31488
#include<iostream>
#include<string>
using namespace std;
int main(){
	int b, f, r, v, n, i, j, k;
	int h[120];
	for (i = 120; i; i--)h[i - 1] = 0;
	cin >> n;
	for (i = 0; i < n; ++i){
		cin >> b >> f >> r >> v;
		h[b * 30 + f * 10 + r - 41] += v;
	}

	for (i = 0; i < 4; ++i){
		for (j = 0; j < 3; ++j){
			for (k = 0; k < 10; ++k){
				cout << " "<<h[i * 30 + j * 10 + k];
			}
			cout << endl;
		}
		if(i<3)cout << "####################" << endl;
	}
	cin >> i;
}

Measured memory_bytes: 1160
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=998244353;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int san[13];
vector<int>ans;
class hito{
public:
	bool sru;
	int moto;
	hito* go[3];
	hito(int in,int dep,int n){
		//cerr<<in<<" "<<dep<<" "<<n<<endl;
		moto=in;sru=false;
		if(dep<n){
			go[0]=new hito(in, dep+1,n);
			go[1]=new hito(in+san[dep],dep+1,n);
			go[2]=new hito(in+san[dep]*2,dep+1,n);
		}else{go[0]=nullptr;}
	}
	void dance(void){
		if(go[0]==nullptr){return;}
		if(sru){
			go[0]->sru=!go[0]->sru;
			go[1]->sru=!go[1]->sru;
			go[2]->sru=!go[2]->sru;
			swap(go[1],go[2]);
			sru=false;
		}
	}
	void runba(void){
		//cerr<<moto<<endl;
		if(go[0]==nullptr){return;}
		this->dance();
		auto aaa=go[2];
		go[2]=go[1];
		go[1]=go[0];
		go[0]=aaa;
		go[0]->runba();
	}
	void solve(int in,int dep){
		//cerr<<moto<<endl;
		if(go[0]==nullptr){ans[moto]=in;return;}
		this->dance();
		go[0]->solve(in,dep+1);
		go[1]->solve(in+san[dep],dep+1);
		go[2]->solve(in+san[dep]*2,dep+1);
	}
};
int main(void){
	int n,i;cin>>n;
	san[0]=1;
	for(i=1;i<=n;i++){san[i]=san[i-1]*3;}
	hito wa(0,0,n);
	string T;cin>>T;
	for(auto it:T){
		if(it=='S'){wa.sru=!wa.sru;}
		else {wa.runba();}
	}
	ans.res(san[n]);
	wa.solve(0,0);
	for(i=0;i<san[n];i++){cout<<ans[i]<<" ";}cout<<endl;
	return 0;
}


Measured memory_bytes: 43848
import java.util.*;

class Main {
    public static void main(String[] args) {
        new Solver().run();
    }
}

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] h = new int[N];
        for (int i = 0; i < N; i++) {
            h[i] = sc.nextInt();
        }
        Arrays.sort(h);

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < N - K + 1; i++) {
            min = Math.min(min, h[i + K - 1] - h[i]);
        }

        System.out.println(min);
        return;
    }

}


Measured memory_bytes: 59312
import sys,collections
sys.setrecursionlimit(10**7)
n,m = map(int,input().split())
vertices_in = [set() for _ in range(n+1)]
vertices_out = [set() for _ in range(n+1)]
nodes= [1]*(n+1)
done = set()
use = set()
dq = collections.deque([])
for i in range(m):
    a,b=map(int,sys.stdin.readline().split())
    vertices_in[a].add(b)
    vertices_in[b].add(a)
dq.append(1)
order = [1]
def factory(num):
    for v in vertices_in[num]:
        if v not in done:
            done.add(v)
            factory(v)
    for v in vertices_in[num]:
        if num not in vertices_out[v]:
            vertices_out[num].add(v)
            use.add(v)
    if len(vertices_out[num])%2!=0:
        for v in vertices_out[num]:
            if nodes[v]:
                vertices_out[num].remove(v)
                use.remove(v)
                break
    nodes[num]=0
if m%2==1:
    print(-1)
else:
    factory(1)
    for i in range(1,n+1):
        for v in vertices_out[i]:
            print(i,v)


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

typedef unsigned long long ull;
#define pii pair<ull, ull>
#define fi first
#define se second
#define watch(x) cout << (#x) << " is " << (x) << endl;
using namespace std;


int main() {
    ull N, M;
    cin >> N >> M;

    ull A[N+1];
    for(ull i = 1; i <= N; i++) cin >> A[i];

    vector<pii> ops;
    ops.emplace_back(numeric_limits<ull>::max(), 0);
    for(ull i = 1; i <= M; i++) {
        ull a, b;
        cin >> a >> b;
        ops.emplace_back(b, a);
    }

    sort(ops.rbegin(), ops.rend());
    sort(A+1, A+N+1);

    ull pos = 1;
    ull curOp = 1;

    while(curOp <= M && pos <= N) {
        ull k = 1;
        while(k <= ops[curOp].se && pos <= N) {
            if(A[pos] < ops[curOp].fi) {
                k++;
                A[pos] = ops[curOp].fi;
            }
            pos++;
        }
        curOp++;
    }

    ull ans = 0;
    for(ull i = 1; i <= N; i++) {
        ans += A[i];
    }

    cout << ans << endl;
}

/* 
3 2
4 4 3
2 4
1 5 
*/

Measured memory_bytes: 3188