akhauriyash/Code-Regression huggingface dataset:
# coding: utf-8

def selectionSort(A, N):
	A = A[:]
	count = 0
	for i in xrange(N):
		minj = i
		for j in xrange(i, N):
			if A[j] < A[minj]:
				minj = j
		if minj != i:
			A[i], A[minj] = A[minj], A[i]
			count += 1
	return A, count

def main():
	N = input()
	A = map(int, raw_input().split())
	sorted_, count = selectionSort(A, N)
	print ' '.join(map(str, sorted_))
	print count

if __name__ == '__main__':
	main()

Measured memory_bytes: 4236
from operator import mul
from functools import reduce
MOD = 10 ** 9 + 7

N, K = map(int, input().split())

def cmb(n, r):
    if n < r:
        return 0
    r = min(r, n-r)
    if r == 0:
        return 1
    nume = reduce(mul, range(n, n-r, -1))
    deno = reduce(mul, range(1, r+1))
    
    return nume // deno % MOD

# 赤いボールの間と両端（N-K+1）の中からi個を選ぶ
for i in range(1, K+1):
    print(cmb((N-K+1), i) * cmb((K-1), i-1) % MOD)

Measured memory_bytes: 3944
#include <iostream>
#include <vector>
#include <iomanip>
#include <stack>
#include <array>
#include <deque>
#include <forward_list>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <iterator>
#include <string>
#include <cstring>
//#include <fstream>
#include <complex>
#define _USE_MATH_DEFINES
#include <cmath>
#include <math.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n;i>0;i--)
#define arep(a,i,n) for(int i=(a);i<(n);i++)
#define SORT(v) sort((v).begin(),(v).end())
const ll INF = (1LL << 50);
typedef pair<int, int> P;

int main() {

	int a, b;
	cin >> a >> b;

	int x = a;
	REP(i, b-1) {
		x *= 10;
		x += a;
	}

	int y = b;
	REP(i, a - 1) {
		y *= 10;
		y += b;
	}


	if(x>=y) cout << x << endl;
	else cout << y << endl;

	return 0;

}

Measured memory_bytes: 256
//#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 9;
const int infint = 1e9 + 7;
const int MAXN = 3e5 + 7;
const double eps = 1e-9;
const long double pi = 3.1415926535897932384626433832795;
const long double e = 2.71828182845904523536028747135266;
inline ll read()
{
    ll kr = 1, xs = 0;char ls;ls = getchar();
    while (!isdigit(ls)){
        if (!(ls ^ 45)) kr = -1;
        ls = getchar();
    }
    while (isdigit(ls)){
        xs = (xs << 1) + (xs << 3) + (ls ^ 48);ls = getchar();
    }return xs * kr;
}
// inline __int128 read128()
// {
//     __int128 kr=1,xs=0;char ls;ls=getchar();
//     while(!isdigit(ls)){
//         if(!(ls^45)) kr=-1;ls=getchar();
//     }
//     while(isdigit(ls)){
//         xs=(xs<<1)+(xs<<3)+(ls^48);ls=getchar();
//     }
//     return xs*kr;
// }
inline ull readull()
{
    ull xs = 0;char ls;ls = getchar();
    while (!isdigit(ls))ls = getchar();
    while (isdigit(ls)){
        xs = (xs << 1) + (xs << 3) + (ls ^ 48);ls = getchar();
    }return xs;
}
inline void writeull(ull x)
{
    if (x < 0){
        x *= -1;putchar('-');
    }
    if (x >= 10) writeull(x / 10);
    putchar('0' + x % 10);
}
inline void write(ll x)
{
    if (x < 0){
        x *= -1;putchar('-');
    }
    if (x >= 10) write(x / 10);
    putchar('0' + x % 10);
}
// inline void write(__int128 x){
//     if(x<0){x*=-1;putchar('-');}
//     if(x>=10) write(x/10);
//     putchar('0'+x%10);
// }
///////////////////////////////////////////////////////////////////////////////////////
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b){
        if(b&1) ans=a*ans%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(0),cout.tie(0);
    int t = 1;
    // t = read();
    while (t--)
    {
        ll n=read();
        if(n==0||n==1) {
            cout << 0 << endl;
            continue;
        }
        ll ans=qpow(10,n)-2ll*qpow(9,n)+qpow(8,n);
        ans%=mod;
        ans+=mod;
        ans%=mod;
        cout << ans <<endl;
    }
    return 0;
}


Measured memory_bytes: 3628
#include<iostream>

using namespace std;
int main()
{
	int N,K;
	cin >> N >> K;
	if(N % 2 == 1 && K % 2 == 1){
		cout << "Yes" << endl;
		return 0;
	}
	cout << "No" << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include<map>
#include<queue>
#include<time.h>
#include<limits.h>
#include<cmath>
#include<ostream>
#include<iterator>
#include<set>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define rep_1(i,m,n) for(int i=m;i<=n;i++)
#define mem(st) memset(st,0,sizeof st)
inline int read()
{
	int num=0, w=0;
	char ch=0;
	while (!isdigit(ch))
	{
		w|=ch=='-';
		ch = getchar();
	}
	while (isdigit(ch))
	{
		num = (num<<3) + (num<<1) + (ch^48);
		ch = getchar();
	}
	return w? -num: num;
}
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef pair<double,double> pdd;
const int inf = 0x3f3f3f3f;
const int N=2e5+10;
void solve()
{
	ll n;
	cin>>n;
	ll ans=0;
//	for(ll i=0; i<=n; i++)	
//		ans+=(n-i)*(i+1);
	for(ll i=1;i<=n;i++)
	{ 
//		for(int j=i;j<=n;j++)
//			ans+=j-i+1;
		ans+=(i+n)*(n-i+1)/2+(n-i+1)-i*(n-i+1); 
	} 
	for(ll i=1;i<=n-1;i++)
	{
		ll l,r;
		cin>>l>>r;
		if(l>r)
			swap(l,r);
		ans-=l*(n-r+1);
	}
	cout<<ans<<endl;
}
signed main()
{
	int t=1;
	while(t--)
		solve();
	return 0;
}



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

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    static int64_t a[200000], cnt[200001];
    int n;
    cin >> n;
    for(int i=0;i<n;++i){ cin >> a[i]; ++cnt[a[i]]; }
    int64_t ptn = 0;
    for(int x=1;x<=n;++x){ ptn += cnt[x] * (cnt[x]-1) / 2; }

    for(int i=0;i<n;++i){
        cout << ptn - cnt[a[i]] * (cnt[a[i]]-1) / 2 + (cnt[a[i]]-1) * (cnt[a[i]]-2) / 2 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 4736
#include <stdio.h>

int a[60], b[60];
int main(void)
{
    while (1) {
        int n, r, i;
        scanf("%d%d", &n, &r);
        if (n==0 && r==0) break;
        for(i=0;i<n;++i) a[n-i]=i+1;
        while (r--) {
            int p, c;
            scanf("%d%d", &p, &c);
            for(i=1;i<=n;++i) b[i]=a[i];
            for(i=1;i<=c;++i) a[i]=b[i+p-1];
            for(i=1;i<p;++i) a[i+c]=b[i];
        }
        printf("%d\n", a[1]);
    }
    return 0;
}

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

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

    string s, t;
    cin >> s >> t;

    int ans = 0;
    for(int i = 0; i < s.size(); i++){
        ans += (s[i] != t[i]);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3884
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;


int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<vector<long long int>> v(c + 1, vector<long long int>(d + 1, 0));
    v[a][b] = 1;
    const int mod = 998244353;
    for (int i = a; i <= c; i++) {
        for (int j = b; j <= d; j++) {
            if (a == i && b == j) {
                v[i][j] = 1;
                continue;
            }
            v[i][j] = v[i - 1][j] * j % mod + v[i][j - 1] * i % mod - v[i - 1][j - 1] * (j - 1) * (i - 1) % mod;
            v[i][j] %= mod;
        }
    }
    v[c][d] += mod;
    v[c][d] %= mod;
    cout << v[c][d] << endl;
}


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

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

    int N = scanner.nextInt();
    Restaurant[] restaurants = new Restaurant[N];
    for (int i = 0; i < N; i++) {
      restaurants[i] = new Restaurant(i + 1, scanner.next(), scanner.nextInt());
    }
    Arrays.sort(restaurants, (r1, r2) -> {
      if (!r1.s.equals(r2.s)) return r1.s.compareTo(r2.s);
      return r2.p - r1.p;
    });
    for (int i = 0; i < N; i++) {
      System.out.println(restaurants[i].id);
    }
  }

  private static class Restaurant {
    private final int id;
    private final String s;
    private final int p;

    private Restaurant(int id, String s, int p) {
      this.id = id;
      this.s = s;
      this.p = p;
    }
  }
}


Measured memory_bytes: 27092
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f first
#define s second
#define mp make_pair
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
const int mod = (int)1e9 + 7;
int n, m;
vector<int> a;
int main () {
	cin >> n >> m;
	a.resize(m);
	for(int i = 0; i < m; i++) cin >> a[i];
	sort(a.begin(), a.end());
	if(m <= 2) {
		for(int i = 0; i < m; i++) {
			if(i > 0) cout << " ";
			cout << a[i];
		}
		cout << "\n";
		if(a[0] == 1) {
			cout << 1 << "\n" << n <<"\n";
		} else if(m == 1) {
			cout << "2\n" << n-1 << " 1\n";
		}
		else {
			cout << 2 << "\n" << a[0] + 1 << " " << a[1] - 1 << "\n";
		}
		return 0;
	}
	int cnt = 0;
	for(int &x: a) cnt += x % 2;
	if(cnt > 2) {
		cout << "Impossible\n";
		return 0;
	}
	for(int i = 0; i < m; i++) {
		if(a[i] % 2) {
			swap(a[0], a[i]);
			break;
		}
	}
	for(int i = 1; i < m; i++) {
		if(a[i] % 2) {
			swap(a[m-1], a[i]);
			break;
		}
	}
	for(int i = 0; i < m; i++) {
		if(i > 0) cout << " ";
		cout << a[i];
	}
	cout << "\n";
	if(a[0] == 1) {
		a.back()+=1;
		a.erase(a.begin());
	}else {
		a[0] -= 1;
		a.back() += 1;
	}
	cout << a.size() << "\n";
	for(int i = 0; i < a.size(); i++) {
		if(i > 0) cout << " ";
		cout << a[i];
	}
	cout << "\n";
 	return 0;
}



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

namespace c
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var s = Console.ReadLine().ToCharArray();

            var l = new List<char>();
            var i = 0;
            while(i < n){
                var c = s[i];
                while(i < n && s[i] == c){
                    i++;
                }
                l.Add(c);
            }

            var s2 = string.Join("",l);
            Console.WriteLine(s2.Length);
        }
    }
}


Measured memory_bytes: 14560
import java.util.Scanner;

public class Main implements Runnable {

    private static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Thread(null, new Main(), "", 128 * 1024 * 1024).start();
    }

    public void run() {
        int n = sc.nextInt(), k = sc.nextInt();
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < n - k + 1; i++) {
            int diff = Math.abs(x[i] - x[i + k - 1]);
            int tmp = diff + Math.min(Math.abs(x[i]), Math.abs(x[i + k - 1]));
            ans = Math.min(tmp, ans);
        }
        System.out.println(ans);
    }
}


Measured memory_bytes: 53520
import java.io.*;
import java.util.*;

public class Main {

	final static long MOD = 1000000007;
	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static void main(String[] args) throws Exception {
		solution(args);
		if(in!=null){
			in.close();
		}
	}

	public static void solution(String[] args) throws Exception{

		int A = nextInt();

		int B = nextInt();

		int ans = A+B;
		ans=Math.max(ans, A*B);
		ans=Math.max(ans, A-B);


		System.out.println(ans);

	}
	public static String[] toStringArray(String s) {
		String[] tmp = new String[s.length()];
		char[] c = s.toCharArray();
		for (int i = 0; i < tmp.length; i++) {
			tmp[i] = String.valueOf(c[i]);
		}
		return tmp;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}


Measured memory_bytes: 23124
// +build ignore
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []byte {
	return []byte(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

func gcd(x, y int) int {
	if x%y != 0 {
		return gcd(y, x%y)
	}
	return y
}

func run(input io.Reader, output io.Writer) int {
	sc := NewScanner()
	N := sc.nextInt()
	K := sc.nextInt()
	A := make([]int, N+1)
	for i := 1; i <= N; i++ {
		A[i] = sc.nextInt()
	}

	M := map[int]int{1: 0}
	T := []int{1}
	for i := 0; i < K; i++ {
		to := A[T[i]]
		if m, ok := M[to]; ok {
			k := len(T) - m
			fmt.Println(T[(K-(i+1))%k+m])
			return 0
		}
		M[to] = len(T)
		T = append(T, to)
	}

	fmt.Println(T[len(T)-1])

	return 0
}

func main() {
	os.Exit(run(os.Stdin, os.Stdout))
}


Measured memory_bytes: 18636
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;

bool is_lunlun(lint n) {
    string s = to_string(n);
    bool lunlun = true;
    for(lint i=0; i+1<s.size(); i++) {
        lunlun &= (abs(s[i] - s[i+1]) <= 1);
    }
    return lunlun;
}

lint next_lunlun(lint n) {
    if(is_lunlun(n+1)) {
        return n+1;
    } else {
        lint a = next_lunlun(n/10);
        if(a%10 == 0) {
            return a*10;
        } else {
            return a*10 + (a%10-1);
        }
    }
}

int main() {
    lint k;
    cin >> k;

    lint x = 1;
    for(lint i=0; i<k-1; i++) {
        x = next_lunlun(x);
    }
    cout << x << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int int_sort(const void *a,const void *b){
	if( *(int *)a < *(int *)b){
		return -1;
	}else 
	if(*(int *)a == *(int *)b){
		return 0;
	}
	return 1; 
}

int main(){
	int N,M,i;
	int sum=0,cnt=0;
	double vot=0;
	
	scanf("%d%d",&N,&M);
	vot=1.0/(4*M);
	
	int num[N];
	for(i=0;i<N;++i){
		scanf("%d",&num[i]);
		sum+=num[i];
	}
	for(i=0;i<N;++i){
		if(sum*vot<=num[i]) cnt++;
	}
	
	if(M<=cnt) puts("Yes");
	else	puts("No");
	
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int64_t i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int64_t i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007
#define INF 1000000000
typedef pair<int64_t, int64_t> PII;
typedef vector<int64_t> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

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

string X; cin >> X;
vector<char> x{X[0]}; 
rep(i, 1, X.size()){
    if (x.back() == 'S' && X[i] == 'T')
        x.pop_back();
    else 
        x.push_back(X[i]);
}
cout << x.size() << endl;
}

// 境界，出力文字列 チェック
// 可読性優先．高速化次点．
// まずは全探索，分割統治，次にDP
// 制限を見る．境界に注意．
// 偶奇，逆から，ソート，出現回数，出現位置，DP， 余事象，包除
// データ構造． 問題の特徴量．単調性，二分探索
// 存在判定：構成方法，入力の特徴
// gcd, lcm ,素因数分解．
// 例外を十分に含む一般化．想像力の限界
// 小さい系から例示
// 始めは過剰に例示・場合分けしてもいい．各場合を確実に対処．
// 自明な例から処理，除外．
// 小数のときは，精度の設定する．doubel 変数に数値を入力するときは 123. とする．
// テストケース作成は数表あり



Measured memory_bytes: 788
#include <bits/stdc++.h>
#define pb push_back
#define ld long double
#define ll long long
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ld,ld>
#define f first
#define s second
#define sz(x) (int)x.size()

using namespace std;

const ll N = 2e5 + 10;
const ll big = 1e18;
const ll block = 100;
const ll mod = 1e6;

ll n;
ll c;

ll h[N];
ll dp[N];

vector<pill> convex;

ld cross(pill a,pill b){
    return (b.s - a.s + 0.0) / (a.f - b.f + 0.0);
}

void add(ld k,ld b){
    bool was = 0;
    ll szs = sz(convex) ;
    while(sz(convex) > 1){
        if(cross({k,b} , convex[szs - 2]) > cross(convex[szs - 1] , convex[szs - 2]) )
            break;
        convex.pop_back();
        szs = sz(convex);
    }
    convex.pb({k, b});
}

int main() {
    speed;
    cin >> n >> c;
    for(int i = 0 ; i < n ; i++)
        cin >> h[i];
    for(int i = 0 ; i < n ; i++){
        if(i){
            ll l = 0 ,r = sz(convex) - 2;
            while(l <= r){
                ll m = (l + r) / 2;
                ld y = cross(convex[m] , convex[m + 1]);
                if(y > (ld)h[i])
                    r = m - 1;
                else
                    l = m + 1;
            }
            dp[i] = h[i] * h[i] + convex[l].s + c + convex[l].f * h[i];
        }
        add(-2 * h[i] , dp[i] + h[i] * h[i]);
    }
    cout << dp[n - 1] << '\n';
}

/*
    Code written by
    Codeforces : I_Love_Trott
    mail : dzhon.snoudin@mail.ru
*/

Measured memory_bytes: 13548
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
using namespace std;

int change(char c) {
	if ('a' <= c && c <= 'z') {
		return (c - 'a');
	}
}
long long dp[100000][26]; //ｊ番目までの星で、入り口がiの星へのアクセスは何通りか
int main() {
	int N;
	cin >> N;
	string s,t;
	cin >> s >> t;
	for (int j = 0; j < N; j++) {
		if (j == 0) {
			for (int i = 0; i < 26; i++) {
				if (change(s[0]) == i) {
					dp[0][i] = 1;
				}
				else {
					dp[0][i] = 0;
				}
			}
		}
		else {
			for (int i = 0; i < 26; i++) {
				dp[j][i] = dp[j - 1][i]%1000000007;
			}
			dp[j][change(s[j])] = (dp[j][change(s[j])]+dp[j - 1][change(t[j])])%1000000007;
		}
	}
	cout << dp[N-2][change(t[N-1])] << endl;
	return 0;
}


Measured memory_bytes: 23616
// abc060_a
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../cxx-prettyprint/prettyprint.hpp"
#endif
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))
#define ALL(x) x.begin(), x.end()

#define INF ((1 << 29)-1)
#define MOD (1000000007)

#define print2D(h, w, arr) REP(i, h) { REP(j, w) cout << arr[i][j] << " "; cout << endl; }
#define print_line(vec, n) {for(int i=0;i<(n-1);i++) cout << (vec)[i] << " "; cout << (vec)[(n)-1] << endl;}
template<class T> void print(const T& x){cout << x << endl;}
template<class T, class... A> void print(const T& first, const A&... rest) { cout << first << " "; print(rest...); }
struct PreMain {PreMain(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(20);}} premain;

int main() {
#ifdef LOCAL
    ifstream in("../arg.txt"); cin.rdbuf(in.rdbuf());
#endif

    string A, B, C;
    cin >> A >> B >> C;

    if (A.back() == B[0] && B.back() == C[0]){
        print("YES");
    } else{
        print("NO");
    }


    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define fit(x) for(auto it=x.begin();it!=x.end();++it)
#define se second
#define mp make_pair
#define ALP "abcdefghijklmnopqrstuvwxyz"
#define nline cout<<"\n"
#define rep(i,x) for(i=0;i<x;++i)
#define repr(i,a,b) for(i=a;i<=b;++i)
#define mi2 500000004
#define mi3 333333336
#define MOD 1000000007
#define N 1000005
#define pll pair<ll,ll>
#define Vll vector<ll>
#define W(t) while(t--)
#define modsum(a,b,M) (a%M + b%M)%M
#define modsub(a,b,M) (a%M - b%M + M)%M
#define modmul(a,b,M) (a%M * b%M)%M
#define moddiv(a,b,M) (a%M * modinv(b,M)%M)%M
using namespace std;
ll powermod(ll x,ll n,ll M)
{
	ll result=1;
	while(n>0)
	{
	  if(n % 2 ==1)
	    result=(result * x)%M;
	  x=(x*x)%M;
	  n=n/2;
	}
	return result;
}
vector<ll> readll() {
	cin>>ws;
	vector<ll> v;
	string input;
	getline(cin, input);
	cout<<input;
	istringstream is(input);
	ll num;
	while(is>>num) v.pb(num);
	return v;
}
ll modinv(ll n,ll p) {
	return powermod(n,p-2,p);
}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll fact[1000005],invf[1000005];
void facmod(ll n,ll M) {
	ll i;
	fact[0]=fact[1]=1;
	for(i=2;i<=n;++i) {
		fact[i]=((fact[i-1])%M * (i%M))%M;
	}
	invf[n]=modinv(fact[n],M);
	for (i=n-1;i>=0;--i){
		invf[i]=invf[i+1]*(i+1);
		invf[i]%=M;
	}
}
/*****
ll T=0;
ll p[200005], d[200005];
ll tin[200005], tout[200005];
vector<ll> g[200005];

void dfs(ll v, ll par = 1, ll dep = 0) {
	p[v] = par;
	d[v] = dep;
	tin[v] = T++;
	for (auto to : g[v]) {
		if (to == par) continue;
		dfs(to, v, dep + 1);
	}
	tout[v] = T++;
}
****/
void solve() {
	ll n;
	cin>>n;
	ll ans =(n/500)*1000;
	n%=500;
	ans+=(n/5)*5;
	cout<<ans;
}
int main() {
  	fastio;
	ll t=1;
	//cin>>t;
	W(t) {
		solve();
	}
	
  	return 0;
}


Measured memory_bytes: 256
//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define inf 1e+9
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define msg(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
#define pri(a) cout << a << endl;

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

  ll n,k,ans=0;
  cin >> n >> k;
  //ll n,k,ans=0;
  //cin >> n >> k;
  // string s;
  // cin >> s;

  if(n==1 && k==1){
    ans += 400000;
  }

  if(n==1){
    ans += 300000;
  }
  else if(n==2){
    ans += 200000;
  }
  else if(n==3){
    ans += 100000;
  }

  if(k==1){
    ans += 300000;
  }
  else if(k==2){
    ans += 200000;
  }
  else if(k==3){
    ans += 100000;
  }


  cout << ans << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
 
const int MAXN = 1005;
const int MAXV = MAXN*(MAXN-1)/2;
vector<int> to[MAXV];
int id[MAXN][MAXN];
int toId(int i, int j) {
  if (i > j) swap(i,j);
  return id[i][j];
}
 
bool visited[MAXV];
bool calculated[MAXV];
int dp[MAXV]; // max length of path from v
int dfs(int v) {
  if (visited[v]) {
    if (!calculated[v]) return -1;
    return dp[v];
  }
  visited[v] = true;
  dp[v] = 1;
  for (int u : to[v]) {
    int res = dfs(u);
    if (res == -1) return -1;
    dp[v] = max(dp[v], res+1);
  }
  calculated[v] = true;
  return dp[v];
}
 
int main() {
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(n-1));
  rep(i,n) {
    rep(j,n-1) {
      cin >> a[i][j];
      a[i][j]--;
    }
  }
  int V = 0;
  rep(i,n)rep(j,n) {
    if (i < j) {
      id[i][j] = V++;
    }
  }
  rep(i,n) {
    rep(j,n-1) {
      a[i][j] = toId(i,a[i][j]);
    }
    rep(j,n-2) {
      to[a[i][j+1]].push_back(a[i][j]);
    }
  }
  int ans = 0;
  rep(i,V) {
    int res = dfs(i);
    if (res == -1) {
      puts("-1");
      return 0;
    }
    ans = max(ans, res);
  }
  cout << ans << endl;
  return 0;
}

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

using namespace std;

template<typename S, typename T>
ostream& operator<<(ostream& out, const pair<S, T> p) {
    out << "(" << p.first << "," << p.second << ")";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    for (auto a: v)
        out << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const set<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename T>
ostream& operator<<(ostream& out, const multiset<T>& S) {
    for (auto a: S)
        cout << a << " ";
    return out;
}

template<typename S, typename T>
ostream& operator<<(ostream& out, const map<S, T>& M) {
    for (auto m: M)
        cout << "(" << m.first << "->" << m.second << ") ";
    return out;
}

template<typename S, typename T>
pair<S, T> operator+(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first + b.first, a.second + b.second);
}

template<typename S, typename T>
pair<S, T> operator-(pair<S, T> a, pair<S, T> b) {
    return make_pair(a.first - b.first, a.second - b.second);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    double r;
    cin >> r;
    cout << fixed << setprecision(10) << 2 * r * acos(-1.0) << endl;
    return 0;
}


Measured memory_bytes: 3756
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <set>
#include <cstdlib>
#include <deque>
#include <stack>

using namespace std;
const long long P = 1000000007;
const long long INF = 1LL << 60;

int main() {
  string s;
  cin >> s;
  int change = 0;
  for(int i = 0; i < s.size()-1; i++) {
    if(s[i] == s[i+1]) {
      if(s[i+1] == '0') {
        s[i+1] = '1';
      }
      else {s[i+1] = '0';} 
      change++;
    }
  }
  cout << change << endl;
  return 0;
}


Measured memory_bytes: 512
def c_triangular_relationship(N, K):
    # 1からNの整数のうち、Kで割って0あまる数の個数
    reminder_K = N // K
    # 1からNの整数のうち、Kで割ってK/2あまる数の個数
    reminder_halfK = 0 if K % 2 == 1 else N // (K // 2) - reminder_K
    ans = reminder_K**3 + reminder_halfK**3  # 重複順列の公式より
    return ans

N, K = [int(i) for i in input().split()]
print(c_triangular_relationship(N, K))

Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <queue>
#include <cmath>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
const int INF = 1e18;

using namespace std;


signed main() {
  int a, b, c;
  cin >> a >> b >> c;

  if(a+b+c > 21) cout << "bust" << endl;
  else cout << "win" << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

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

  int x=0;
  int max_x=0;
  for(int i=0;i<S.size();i++){
    if(S.at(i)=='I') ++x;
    else --x;
    max_x=max(max_x,x);
  }

  cout << max_x << endl;
  
  return 0;
}


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

template <typename T> void debug(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void debug(T t, Args... args) { cout<<t<<" "; debug(args...); }

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int32_t main()
{
    IOS;
    int n;
    cin>>n;
    int sum=0;
    vector<int>v;
    set<int>s;
    for(int i=1;;i++)
    {
        sum+=i;
        if(sum>n)
        {
            sum-=i;
            break;
        }
        v.push_back(i);
    }
    int left=n-sum;
    if(sum==0)
    {
        for(int i=0;i<v.size();i++)
            cout<<v[i]<<endl;
        return 0;
    }
    else
    {
        int maxval=v[v.size()-1];
        int minreach=1e18;
        int pos=0;
        for(int i=0;i<v.size();i++)
        {
            if(left+v[i]>maxval)
            {
                if(minreach>left+v[i])
                {
                    minreach=left+v[i];
                    pos=i;
                }
            }
        }
        set<int>s;
        for(int i=0;i<v.size();i++)
            if(i==pos)
                s.insert(v[i]+left);
            else
                s.insert(v[i]);
        for(auto i:s)
            cout<<i<<endl;
    }
}

Measured memory_bytes: 3900
#include <stdio.h>

int main(void)
{
  int n;
  int i, j;
  int dp[4001] = {0};
  int ans;

  for (i = 0; i <= 1000; i++){
    for (j = 0; j <= 1000; j++){
      dp[i + j]++;
    }
  }

  while (scanf("%d", &n) == 1){
    ans = 0;
    for (i = 0; i <= n; i++){
      ans += (dp[i] * dp[n - i]);
    }

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

  return (0);
}

Measured memory_bytes: 616
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void){
    int n,ptr = 0,g = 0;
    long long kei[2] = {};
    cin >> n;
    int a[n];
    for(int i = 0;i < n;i++)
    cin >> a[i];
    
    sort(a,a+n,greater<int>());
    while(ptr < n){
        int x = a[ptr],res = 0;
        while(ptr < n && a[ptr] == x){
            ptr++;
            res++;
        }
        if(res >= 4 && g == 0){
            kei[0] = x;
            kei[1] = x;
            break;
        }
        else if(res >= 2){
            kei[g] = x;
            g++;
        }
        if(g >= 2)
        break;
    }
    
    cout << kei[0]*kei[1]<<endl;
    return 0;
}

Measured memory_bytes: 640
from itertools import product
def count9(cur):
    count = 0
    for i in range(6)[::-1]:
        count += cur//(9**i)
        cur %= 9**i
    return count
n = int(input())
ans = count9(n)
for x in product("012345",repeat = 6):
    digitsum = 0
    SUM = 0
    for i in range(6):
        SUM += int(x[i])*6**(i+1)
        digitsum += int(x[i])
    if SUM <= n:
        ans = min(ans,digitsum+count9(n-SUM))
print(ans)
    

Measured memory_bytes: 42312
X, N =map(int, input().split())
if N != 0:
  p = list(map(int, input().split()))
  p.sort(reverse=True)
  abs_ans = 1000
  ans = 0
  j = 0
  for i in range(p[0]+1, p[len(p)-1]-2, -1):
    abs_i = abs(X-i)
    if i != p[j] and abs_ans >= abs_i:
      abs_ans = abs_i
      ans = i
    if i <= p[j] and j < len(p) -1:
      j += 1

  print(ans)
  # print(p)
else:
  print(X)

Measured memory_bytes: 61988
// Lec11-B Dice II
#include<iostream>
class Dice{
private:
  int d[6];
public:
  Dice(int *in){
    for(int i=0; i<6; i++) d[i] = in[i];
  }
  int question(int top, int front){
    int tmp;
    while(!(top==d[0] && front==d[1])){
      if(top == d[0]){ tmp=d[1];d[1]=d[2];d[2]=d[4];d[4]=d[3];d[3]=tmp; }
      else if(front == d[1]){ tmp=d[0];d[0]=d[2];d[2]=d[5];d[5]=d[3];d[3]=tmp; }
      else{ tmp=d[0];d[0]=d[1];d[1]=d[5];d[5]=d[4];d[4]=tmp; }
    }
    return d[2];
  }
};
int main(){
  int in1[6], n, top, front;
  for(int i=0; i<6; i++) std::cin >> in1[i];
  std::cin >> n;
  Dice sample(in1);
  for(int i=0; i<n; i++){
    std::cin >> top >> front;
    std::cout << sample.question(top, front) << std::endl;
  }
  return 0;
}

Measured memory_bytes: 3080
#include<bits/stdc++.h>
#include<string>
#include <iostream>
using namespace std;
int main()
{
    string s,t,z;
    int i,j,k,m,n;
    cin>>s;
    cin>>t;
    n=INT_MAX;
    int flag=0;
    for(i=0;i<s.size();i++)
    {
        m=0;
        for(j=0;j<t.size();j++)
        {
            if(i+j>=s.size())
            {
                flag=1;
                break;

            }
            if(t[j]!=s[i+j])
                m++;

        }
        if(flag==1)
                    break;
                    n=min(n,m);




    }
    cout<<n<<endl;
}


Measured memory_bytes: 3600
# coding: utf-8
# Here your code !

while 1:
    a = 0
    b = 0
    n = int(input())
    if n == 0:
        break
    else:
        e = [[int(i) for i in input().split()] for i in range(n)] 
        for i in e:
            if i[0] > i[1]:
                a += sum(i)
            elif i[1] > i[0]:
                b += sum(i)
            else:
                a += i[0]
                b += i[1]
        print(a,b)
                

Measured memory_bytes: 9208
/*
    Don't practice until you get it right. Practice until you can't get it wrong.
*/
 
#include<bits/stdc++.h>
using namespace std;
 
#define ll long long int
#define ld double
#define pii pair<ll,ll>
#define vl vector<ll>
#define vb vector<bool>
#define vs vector<string>
#define vp vector<pii>
#define pb push_back
#define mp make_pair
#define sc(a) scanf("%lld",&a);
#define sd(a) scanf("%lf",&a);
#define test() ll tt;cin>>tt;for(ll testcase=1;testcase<=tt;testcase++)
#define all(v) v.begin(),v.end()
#define vivek_ghosh ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000055
#define mod 1000000007
#define ff first
#define ss second
const int INF=0x3f3f3f3f;
 
ll power(ll x,ll n,ll M)
{
    if(n==0)
        return 1;
    else if(n%2 == 0)
        return power((x*x)%M,n/2,M);
    else
        return (x*power((x*x)%M,(n-1)/2,M))%M;
}
 
ll modinv(ll a,ll m)
{
    ll g =__gcd(a, m);
    ll res=power(a, m-2, m);
    return res;
}
 
vb prime(MAX,true);
vl prm;
void sieve()
{
	prime[0] = prime[1] = false;
	for(ll p=2;p*p<MAX;p++)
	{
		if(prime[p])
		{
			for(ll i=p*p;i<MAX;i+=p)
				prime[i] = false;
		}
	}
	for(ll p=2;p<MAX;p++)
	{
		if(prime[p])
			prm.pb(p);
	}
}

ll n,m,t,i,j,k,q,x,y,ans=0,cnt=0,sum=0,mx=-1,mn=INT_MAX;
string s;
 
int main()
{
	vivek_ghosh;
	
	char c;
	cin>>c;
	c++;
	cout<<(c)<<endl;
	
 
	
 
 
 
	return 0;
}



Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
int main() {
	int N, res = 0;
	cin >> N;
	N *= 2;
	int a[N];
	for (int i = 0; i < N; i ++) {
		cin >> a[i];
	}
	sort(a, a + N);
	for (int i = N - 2; i >= 0; i -= 2) {
		res += a[i];
	}
	cout << res << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include <cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

int main(){
  int N; cin >> N; int a[N], ans[N];
  rep(i, N){
    cin >> a[i];
  }
  bool check[N] = {};
  rep(i, N){
    int cnt = 0, tmpj = -1;
    rep(j, N){
      if(check[j]) continue;
      cnt++;
      if(a[j]==cnt){
        tmpj = j;
      }
    }
    if(tmpj==-1){
      cout << tmpj << endl; return 0;
    }
    ans[N-1-i] = a[tmpj];
    check[tmpj] = true;
  }
  rep(i, N){
    cout << ans[i] << endl;
  }
}
      

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

int main(void) {
	long long a, b, c, k;
	cin >> a >> b >> c >> k;

	long long rest = k;
	long long ans = 0;

	if (a >= k) {
		cout << k;
		return 0;
	}
	rest -= a;
	ans += a;

	if (b >= rest) {
		cout << ans;
		return 0;
	}
	rest -= b;

	ans -= rest;
	cout << ans;

	return 0;
}

Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define ll long long
#define mod7 1e9 + 7
#define mod5 1e5 + 5
using namespace std;
ll sum(int l, int r, ll* A){
    ll csum = 0;
    for(ll i = l; i <= r; ++i) csum += A[i];
    return csum;
}
int main() {
    int n;
    cin >> n;
    ll A[n];
    for(ll &x : A) cin >> x;
    ll dp[n][n];
    memset(dp, 0, sizeof(dp));
    for(int i = n - 1;i >= 0; --i){
        for(int j = i; j < n; ++j){
            if(i != j){
                ll tsum = sum(i, j, A);
                dp[i][j] = LONG_MAX;
                for(int k = 0; k < j - i; ++k) dp[i][j] = min(dp[i][j], dp[i][i + k] + dp[i + k + 1][j] + tsum);
            }
            else dp[i][j] = 0;
        }
    }
    cout << dp[0][n - 1] << endl;
    return 0;
}

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

typedef long long ll;
struct PQ{
	priority_queue<ll>pq;
	ll tag;
	ll top(){return pq.top()+tag;}
	void pop(){pq.pop();}
	void add(ll x){tag+=x;}
	void push(ll x){pq.push(x-tag);}
}L,R;
int n;
ll ans;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;L.push(0);R.push(-1e18);
	for(int i=1;i<=n;++i){
		int l,r;cin>>l>>r;R.add(l-r);
		ll u=L.top(),v=-R.top();
		if(u<=r&&r<=v)L.push(r),R.push(-r);
		else if(u<=r){
			ans+=r-v;R.pop();L.push(v);
			R.push(-r);R.push(-r);
		}else{
			ans+=u-r;L.pop();R.push(-u);
			L.push(r);L.push(r);
		}
		L.add(l-r);
	}
	cout<<ans<<'\n';
	return 0;
}


Measured memory_bytes: 2036
N = int(input())
matrices = [tuple(map(int, input().split())) for _ in range(N)]
R, C = zip(*matrices)
dp = [[float('inf')] * N for _ in range(N)]
for i in range(N): dp[i][i] = 0
for l in range(1, N):
    for i in range(N-l):
        r, c = R[i], C[i+l]
        dp[i][i+l] = min(r * C[j] * c + dp[i][j] + dp[j+1][i+l] for j in range(i, i+l))
print(dp[0][N-1])


Measured memory_bytes: 5668
#include <bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
int main(){
	ios::sync_with_stdio(false);
	int a,b;cin>>a>>b;
	int t=a*b;
	if(t&1) cout<<"Odd"<<endl;
	else cout<<"Even"<<endl; 
	return 0;
}


Measured memory_bytes: 764
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;

const int maxn = 1e5+5;
int n;
int a[maxn],s[maxn],b[maxn];

long long merge_sort(int l,int r){
	if (l == r) return 0;
	int mid = (l+r)/2;
	long long ret = merge_sort(l,mid) + merge_sort(mid+1,r);
	int i = l;
	int j = mid+1;
	int p = l;
	while (i <= mid || j <= r) {
		if (j > r || (i <= mid && s[i] <= s[j])){
			b[p++] = s[i++];
		}else{
			b[p++] = s[j++];
			ret += mid-i+1;
		}
	}
	for (int i = l; i <= r; i++) s[i] = b[i];
	return ret;
}

bool check(int x) {
	s[0] = 0;
	for (int i = 1; i <= n; i++) s[i] = s[i-1] + (a[i] < x? -1 : 1);
	return merge_sort(0,n)*2 <= (long long) n*(n+1)/2;
}

int main(){
	scanf("%d",&n);
	vector<int> vec;
	for (int i = 1; i <= n; i++) {
		scanf("%d",&a[i]);
		vec.push_back(a[i]);
	}
	sort(vec.begin(), vec.end());
	/*for (int i = 0; i < vec.size(); i++) {
		printf("%d ",vec[i]);
	}
	printf("\n");*/
	vec.erase(unique(vec.begin(),vec.end()),vec.end());
	int l = 0, r = vec.size() - 1;
	while (l < r) {
		int mid = (l+r+1)/2;
		if (check(vec[mid])) l = mid;
		else r = mid -1;
	}
	printf ("%d\n",vec[l]);
	return 0;
}

Measured memory_bytes: 1912
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i <(n); ++i)
#define REP2(i,x,n) for (int i = x; i <(n); ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int,int>;
static const double PI = acos(-1);
static const int INF = 1e9+7;


/*

*/
struct UnionFind {
vector<int> d;
UnionFind(int n = 0): d(n,-1) {}
int find(int x) {
  if (d[x] < 0) return x;
  return d[x] = find(d[x]);   //経路縮尺(メモ化再帰)
}
bool unite(int x, int y) {  //連結する
  x = find(x); y = find(y);
  if (x == y) return false;
  if (d[x] > d[y]) swap(x,y); //根の高さが小さい方に連結する
  d[x] += d[y];
  d[y] = x;
  return true;
}
bool same(int x, int y) { return find(x) == find(y);} //連結しているかを返す
int size(int x) { return -d[find(x)];}  //連結成分サイズを返す
};

int deg[100005];//直接接続している友人数のリスト
vector<int> to[100005]; //ブロック関係の連結リスト

int main(){
  int n, m, k;
  cin >> n >> m >> k;
  UnionFind uF(n);
  REP(i,m){
    int a, b;
    cin >> a >> b;
    --a; --b;
    deg[a]++;
    deg[b]++;
    uF.unite(a,b);
  }

  REP(i,k){
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  REP(i,n){
    //連結成分のサイズ　- 自分　- 直属の友人
    int ans = uF.size(i) - 1 -deg[i];

    //連結成分内のブロック関係ならマイナス
    for(int u: to[i]){
      if(uF.same(i,u)) --ans;
    }
    cout << ans << " ";
  }
  return 0;
}


Measured memory_bytes: 8968
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
)

type As [][]int

func (s As) Less(i, j int) bool {
	if s[i][0] == s[j][0] {
		return s[i][1] > s[j][1]
	}
	return s[i][0] > s[j][0]
}

func (s As) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s As) Len() int {
	return len(s)
}

func main() {
	var x, y, a, b, c int
	fmt.Scan(&x, &y, &a, &b, &c)

	var sc = bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	as := make(As, a+b+c)
	//fmt.Println(a, b, c, a+b+c)
	for i := 0; i < a; i++ {
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		as[i] = []int{k, 1}
	}
	for i := 0; i < b; i++ {
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		as[a+i] = []int{k, 2}
	}
	for i := 0; i < c; i++ {
		sc.Scan()
		k, _ := strconv.Atoi(sc.Text())
		as[a+b+i] = []int{k, 3}
	}
	sort.Sort(as)

	var sum, cnt, ac, bc int
	for i := range as {
		switch as[i][1] {
		case 1:
			if ac < x {
				ac++
				cnt++
				sum += as[i][0]
			}
		case 2:
			if bc < y {
				bc++
				cnt++
				sum += as[i][0]
			}
		case 3:
			if cnt < x+y {
				cnt++
				sum += as[i][0]
			}
		}
		if cnt == x+y {
			break
		}
	}

	fmt.Println(sum)
}


Measured memory_bytes: 14592
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>
#include <limits.h>

using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;


int diffabs(int a, int b)
{
	if (a > b)
		return a - b;
	else
		return b - a;
}

int dist(int N, int X, int Y, int i, int j)
{
	return min(j - i, diffabs(j, Y) + diffabs(i, X) + 1);
}

int main()
{
	int N, X, Y;
	cin >> N >> X >> Y;

	vi dists(N);
	for (int i = 1; i <= N; i++)
	{
		int baai = 0;
		for (int j = i + 1; j <= N; j++)
		{
			int d = dist(N, X, Y, i, j);
			++dists[d];
		}
	}

	for (int i = 1; i <= N - 1; i++)
	{
		cout << dists[i] << endl;
	}
}

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

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

    int n;cin>>n;

    int maxa=0;
    int maxb=0;
    for(int i=0;i<n;i++)
    {
        int a,b;cin>>a>>b;

        if(maxa<a)
        {
            maxa=a;
            maxb=b;
        }
    }

    cout<<maxa+maxb<<"\n";

    return 0;
}


Measured memory_bytes: 3632
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
using namespace std;
typedef long long LL;
int main(){
		LL n,k,x,y;
		cin >> n >> k >> x >> y;
		if(n <= k){
			cout << n*x << endl;
			}
		else {
			cout << k*x + (n-k)*y <<endl;
			}
		return 0;
	}//

Measured memory_bytes: 256
#include <stdio.h>

int BubbleSort(int elem[], int num)
{
    int i, j;
    int tmp;
    int cnt = 0;

    for (i = 0; i < num; i++) {
        for (j = num - 1; j > i; j--) {
            if (elem[j] < elem[j-1]) {
                tmp       = elem[j-1];
                elem[j-1] = elem[j];
                elem[j]   = tmp;
                ++cnt;
            }
        }
    }

    return cnt;
}

int main(void)
{
    int i;
    int num;
    int elem[100];
    int cnt;

    scanf("%d", &num);
    for (i = 0; i < num; i++) {
        scanf("%d", &elem[i]);
    }

    cnt = BubbleSort(elem, num);

    printf("%d", elem[0]);
    for (i = 1; i < num; i++) {
        printf(" %d", elem[i]);
    }
    printf("\n%d\n", cnt);

    return 0;
}

Measured memory_bytes: 1028
import java.util.*;
public class Main
{
    public static void main (String[] args)
    {
        Scanner scanner = new Scanner(System.in);
    	int num[] = new int[3];
    	for(int i=0;i<3;i++){
    	num[i] = scanner.nextInt();
    	}
    	
    	Arrays.sort(num);
    	for(int i=0;i<3;i++){
    		if(i < 2){
    			System.out.print(num[i]);
    			System.out.print(" ");
    		}else{
    			System.out.println(num[i]);
    		}
    	}
    }
}

Measured memory_bytes: 26172
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
	int x, a, b;
    cin >> x >> a >> b;
    if (a >= b) {
    	cout << "delicious";
    }
    else if (b <= (a + x)) {
    	cout << "safe";
    }
    else {
    	cout << "dangerous";
    }
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            (long N, long M) = Slice2<long>();
            var nums = new long[N];
            for (var i = 0; i < M; ++i)
            {
                (long a, long b) = Slice2<long>();
                ++nums[a - 1];
                ++nums[b - 1];
            }
            foreach (var n in nums) WriteLine(n);
        }

        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
    }
}

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

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

	vector<long long> c(n + 1);

	c[0] = 2;
	c[1] = 1;

	for (int i = 2; i <= n; i++) {
		c[i] = c[i - 1] + c[i - 2];
	}
	
	cout << c[n] << endl;

	return 0;
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ABC_113_B solver = new ABC_113_B();
        solver.solve(1, in, out);
        out.close();
    }

    static class ABC_113_B {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            int n = in.nextInt();

            int t = in.nextInt();
            int a = in.nextInt();

            double[] sub = new double[n];
            double min = Double.MAX_VALUE;
            int ans = -1;
            for (int i = 0; i < n; i++) {
                double dist = Math.abs(a - (t - 0.006 * in.nextInt()));
                if (dist < min) {
                    min = dist;
                    ans = i;
                }
            }

            out.print(ans + 1);
        }

    }
}



Measured memory_bytes: 23380