akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;


int root(vector<int> &uf, int v) {
  while (uf[v] != v) {
    v = uf[v];
  }
  return v;
}

void join(vector<int> &uf, vector<int> &w, int v, int u) {
  int rv = root(uf, v);
  int ru = root(uf, u);
  if (ru != rv) {
    if (w[rv] < w[ru]) {
      uf[rv] = ru;
      w[ru] += w[rv];
    } else {
      uf[ru] = rv;
      w[rv] += w[ru];
    }
  }
}
				  

void print(vector<int> &a) {
  for (auto e: a) {cout << e << " ";}
  cout << endl;
}


int main() {

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

  vector<int> uf(n);
  vector<int> w(n);

  for (int i = 0; i < n; ++i) uf[i] = i;
  for (int i = 0; i < n; ++i) w[i] = 1;

  for (int j = 0; j < m; ++j) {
    int a, b;
    cin >> a >> b;
    join(uf, w, a - 1, b - 1);
  }

  vector<int> cnt(n);

  for (int i = 0; i < n; ++i) {
    ++cnt[root(uf, i)];
  }

  int ans = *max_element(cnt.begin(), cnt.end());

  cout << ans << endl;
}




Measured memory_bytes: 5632
n = int(input())
*h, = map(int, input().split())

dp = [float("inf")]*n
dp[0] = 0

for i in range(1, n):
    if i == 1:
        dp[i] = dp[i-1] + abs(h[i-1] - h[i])
    else:
        dp[i] = min(dp[i-1] + abs(h[i-1] - h[i]), dp[i-2] + abs(h[i-2] - h[i]))

print(dp[n-1])


Measured memory_bytes: 53752
#coding: utf-8
N, M = map(int, input().split())
H = list(map(int, input().split()))
ans = [True for _ in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    if H[a-1] <= H[b-1]:
        ans[a-1] = False
    if H[b-1] <= H[a-1]:
        ans[b-1] = False
print(sum(ans))



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

using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;

ll INF = 1 << 29;

struct N {
  int now;
  ll d;
};

bool operator<(const N &l, const N &r) {
  return l.d > r.d;
}

struct M {
  int a, b;
  ll d;
};

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int n, m;
  ll p;
  cin >> n >> m >> p;
  vector<vector<int>> inv(n), invinv(n);
  vector<M> path;
  for (int i = 0; i < m; i++) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--;
    b--;
    inv[b].push_back(a);
    invinv[a].push_back(b);
    path.push_back(M{a, b, p - c});
  }
  vector<ll> d(n, INF);
  priority_queue<N> q;
  q.push(N{n - 1, 0});
  vector<bool> ok(n), ok2(n);
  while (q.size()) {
    N now = q.top();
    q.pop();
    if (ok[now.now]) continue;
    ok[now.now] = true;
    for (auto &v : inv[now.now]) {
      if (ok[v]) continue;
      q.push(N{v, 0});
    }
  }
  q.push(N{0, 0});
  while (q.size()) {
    N now = q.top();
    q.pop();
    if (ok2[now.now]) continue;
    ok2[now.now] = true;
    for (auto &v : invinv[now.now]) {
      if (ok2[v]) continue;
      q.push(N{v, 0});
    }
  }

  d[0] = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (d[path[j].b] > d[path[j].a] + path[j].d) {
        d[path[j].b] = d[path[j].a] + path[j].d;
        if (i == n - 1 && ok[path[j].b] && ok2[path[j].b]) {
          cout << -1 << endl;
          return 0;
        }
      }
    }
  }

  cout << max(0LL, -d[n - 1]) << endl;

  return 0;
}


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

using namespace std;

#define ll long long
int main()
{
	int n, k;
	cin >> n >> k;
	
	
	vector<ll>h(n);
	for (auto &x : h) cin >> x;
	
	if (k >= n)
	{
		cout << 0;
		return 0;
	}
	
	sort(h.begin(), h.end());
	
	for (int i = 0; i < k; i++)
	{
		h.pop_back();
	}
	
	ll sum = 0;
	for (auto &x : h) sum += x;
	
	cout << sum;
	return 0;
}


Measured memory_bytes: 1792
x1, y1, x2, y2 = gets.split.map(&:to_f)
ux = x2 - x1
uy = y2 - y1
d = ux**2 + uy**2
gets.to_i.times do
  x, y = gets.split.map(&:to_f)
  vx, vy = x - x1, y - y1
  k = (vx * ux + vy * uy) / d
  a, b = vx - k * ux, vy - k * uy
  puts '%.8f %.8f' % [x - 2 * a, y - 2 * b]
end

Measured memory_bytes: 8992
# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
geta = lambda fn: map(fn, readline().split())
gete = lambda fn: fn(readline())

def main():
	n=gete(int)
	dp=[[0]*3 for _ in range(n+1)]
	
	
	for i in range(n):
		a,b,c = geta(int)
		dp[i+1][0] = max(dp[i][1], dp[i][2]) + a
		dp[i+1][1] = max(dp[i][2], dp[i][0]) + b
		dp[i+1][2] = max(dp[i][0], dp[i][1]) + c
		
	print(max(dp[n][0],dp[n][1],dp[n][2]))
	
	
	
if __name__ == "__main__":
	main()

Measured memory_bytes: 53612
inp = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n')
l = inp.shift().split(' ')
N = l.shift() * 1
M = l.shift() * 1 
a = []
b = []
for (i=0;i<N;i++) {
    a[i] = inp[i].split('')
}
for (i=0;i<M;i++) {
    b[i] = inp[i+N].split('')
}
f = 0
for (i=0;i<=N-M;i++) {
    for (j=0;j<=N-M;j++) {
        g = 1
        for (k=0;k<M;k++) {
            for (l=0;l<M;l++) {
                if (a[i+k][j+l] != b[k][l]) {
                    g = 0
                    break;
                } 
            }
            if (!g) {
                break;
            }
        }
        if (g) {
            f = 1
            break;
        }
    }
    if (g) {
        f = 1
        break;
    }
}
console.log(f ? 'Yes' : 'No')

Measured memory_bytes: 20552
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
   int a,b,c;
   cin>>a>>b>>c;
   int sm=a+b+c;
   int mx=max(a,max(b,c));
   if ((sm+mx)%2)
        mx++;
    cout<<(mx*3-sm)/2<<endl;
    return 0;
}

Measured memory_bytes: 384
using System;
using System.Collections.Generic;

public class CSharp
{
    public static void Main()
    {
        Kyopuro chokudai = new Kyopuro();
        chokudai.AtCoder();
    }
}

public class Kyopuro
{

    int L, R;

    public void AtCoder()
    {
        string[] input;
        input = Console.ReadLine().Split(' ');
        L = int.Parse(input[0]);
        R = int.Parse(input[1]);
        long ans = 0;
        if(R - L < 2019)
        {
            if((R % 2019) - (L % 2019) > 0)
            {
                ans = 2020;
                long tmp = 0;
                for(int i=L; i<R; i++)
                {
                    for(int j=i+1; j<=R; j++)
                    {
                        tmp = i % 2019;
                        tmp *= j;
                        tmp %= 2019;
                        if (tmp < ans) ans = tmp;
                    }
                }
            }
        }

        Console.WriteLine(ans);
    }
    public static void DebugWL(object x) { System.Diagnostics.Debug.WriteLine(x); }
}

Measured memory_bytes: 13140
def mozi(S):
    s = list(S)
    s2 = list(set(s))
    if len(s2) != 2:
        ans = 'No'
        return ans
    else:
        p = 0
        q = 0
        for item in s:
            if item == s2[0]:
                p+=1
            if item == s2[1]:
                q+=1
        if p == 2 and q == 2:
            ans = 'Yes'
            return ans
        else:
            ans = 'No'
            return ans

#args = sys.argv
#S = args[0]
S = input()
print(mozi(S))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define ll long long
#define mod 1000000007
#define upperlimit 1000100
#define INF 1000000100
#define INFL 1000000000000000100
#define eps 1e-8
#define endl '\n'
#define sd(n) scanf("%d",&n)
#define slld(n) scanf("%lld",&n)
#define pd(n) printf("%d",n)
#define plld(n) printf("%lld",n)
#define pds(n) printf("%d ",n)
#define pllds(n) printf("%lld ",n)
#define pdn(n) printf("%d\n",n)
#define plldn(n) printf("%lld\n",n)
#define REP(i,a,b) for(i=a;i<=b;i++)
#define mp make_pair
#define pb push_back
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define F first
#define S second
#define clr(a) memset(a,0,sizeof(a))
using namespace std;
 
ll gcd(ll n1,ll n2){
    if(!n1)return n2;
    if(!n2)return n1;
    if(n1%n2==0)return n2;
    return gcd(n2,n1%n2);
}
ll powmod(ll base,ll exponent){
    base%=mod;
    ll ans=1;
    while(exponent){
        if(exponent&1)ans=(ans*base)%mod;
        base=(base*base)%mod;
        exponent/=2;
    }
    ans%=mod;
    return ans;
}
int main()
{
    int A,B;
    
    cin>>A>>B;
    
   if(A<=8 && B<=8)cout<<"Yay!"<<endl;
   else cout<<":("<<endl;
    
    
  return 0;
}

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

int main(){
  string s;
  cin >> s;
  int n = s.size();
  vector<int> d(n+1);
  int ten = 1;
  for(int i=n-1; i>=0; --i){
    int a = (s[i]-'0') * ten % MOD;
    d[i] = (d[i+1]+a) % MOD;
    ten *= 10;
    ten %= MOD;
  }
  vector<int> cnt(MOD);
  ll ans = 0;
  for(int i=n; i>=0; --i){
    ans += cnt[d[i]];
    cnt[d[i]]++;
  }
  cout << ans << endl;
}

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

int main(){
  int n;
  cin >> n;
  int x[n];
  for(int i = 0;i < n;i++){
    cin>>x[i];
  }
  for(int i = n-1;i > 0;i--){
    cout<<x[i]<<' ';
  }
  cout<<x[0]<<endl;
  return 0;
}


Measured memory_bytes: 3092
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

L, R = MAP()
if R-L+1 >= 2019:
	print(0)
else:
	ans = 10000
	for i in range(L, R+1):
		for j in range(i+1, R+1):
			ans = min(ans, (i*j)%2019)
	print(ans)


Measured memory_bytes: 5396
package main
import "fmt"
func main() {
  var n,q int
  var k int64
  fmt.Scan(&n,&q)
  p := []int64{0,int64(n)}
  for i:=0;i<q;i++ {
    fmt.Scan(&k)
    j := len(p)
    for k <= p[j-1] { j-- }
    p = append(p[:j],k)
  }
  q = len(p)-1
  t := make([]int64,q+1)
  t[q] = 1
  ans := make([]int64,n+1)
  for i:=q;i>0;i-- {
    j := i
    k = p[i]
    for k > p[1] {
      l,r := 1,j
      for r-l > 1 {
        m := (l+r)/2
        if p[m] > k {
          r = m
        } else {
          l = m
        }
      }
      j = l
      t[j] += t[i]*(k/p[j])
      k %= p[j]
    }
    ans[k] += t[i]
  }
  for i:=n-1;i>0;i-- { ans[i] += ans[i+1] }
  for i:=1;i<n+1;i++ { fmt.Println(ans[i]) }
}

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

int main() {
  double p[220000][2], min[32], max[32];
  
  int n;
  cin >> n;
  
  for (int i = 0; i < n; i++){
    for (int j = 0; j < 2; j++){
      cin >> p[i][j];
    }
  }
  
  int ans = 0, dat;
    for (int i = 0; i < (1 << 2); i++){
      for (int j = 0; j < n; j++){
        dat = 0;
        for (int k = 0; k < 2; k++){
          if ((i >> k) & 1){
            dat += p[j][k];
          }
          else {
            dat -= p[j][k];
          }
        }
      if (j == 0){
        min[i] = max[i] = dat;
      }
      else {
        if (dat < min[i]){
          min[i] = dat;
        }
        if (dat > max[i]){
          max[i] = dat;
        }
      }
    }
    ans = ans > max[i] - min[i] ? ans : max[i] - min[i];
  }
  
  cout << ans << '\n';
}

Measured memory_bytes: 6744
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <cmath>
typedef long long ll;
using namespace std;

void solve(){
  string s, t; cin >> s >> t;
  for(int i = 0; i < s.size(); i++){
    if(s[i] != t[i]){
      cout << "No" << endl;
      return;
    }
  }
  cout << "Yes" << endl;
  return;
}

int main(){
  solve();
  return 0;
}


Measured memory_bytes: 3628
package main

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

func main() {
	sc := NewScanner()

	A := sc.NextInt()
	B := sc.NextInt()
	C := sc.NextInt()
	D := sc.NextInt()

	if D == B || C == A {
		fmt.Println(0)
		return
	}

	S := max(D, B) - min(D, B)
	T := max(C, A) - min(C, A)

	g := gcd(S, T)

	S /= g
	T /= g

	fmt.Println(g * (S + T - 1))

}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func gcd(a, b int) int {
	for b > 0 {
		a, b = b, a % b
	}
	return a
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a int, b int) int {
	if a < b {
		return b
	}
	return a
}

type Scanner struct {
	r   *bufio.Reader
	buf []byte
	p   int
}

func NewScanner() *Scanner {
	rdr := bufio.NewReaderSize(os.Stdin, 1000)
	return &Scanner{r:rdr}
}
func (s *Scanner) Next() string {
	s.pre()
	start := s.p
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			break
		}
	}
	result := string(s.buf[start:s.p])
	s.p++
	return result
}
func (s *Scanner) NextLine() string {
	s.pre()
	start := s.p
	s.p = len(s.buf)
	return string(s.buf[start:])
}
func (s *Scanner) NextInt() int {
	v, _ := strconv.Atoi(s.Next())
	return v
}

func (s *Scanner) NextIntArray() []int {
	s.pre()
	start := s.p
	result := []int{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			result = append(result, v)
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	result = append(result, v)

	return result
}

func (s *Scanner) NextMap() map[int]bool {
	s.pre()
	start := s.p
	mp := map[int]bool{}
	for ; s.p < len(s.buf); s.p++ {
		if s.buf[s.p] == ' ' {
			v, _ := strconv.Atoi(string(s.buf[start:s.p]))
			mp[v] = true
			start = s.p + 1
		}
	}
	v, _ := strconv.Atoi(string(s.buf[start:s.p]))
	mp[v] = true

	return mp
}

func (s *Scanner) pre() {
	if s.p >= len(s.buf) {
		s.readLine()
		s.p = 0
	}
}
func (s *Scanner) readLine() {
	s.buf = make([]byte, 0)
	for {
		l, p, e := s.r.ReadLine()
		if e != nil {
			panic(e)
		}
		s.buf = append(s.buf, l...)
		if !p {
			break
		}
	}
}




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

#define PI 4*atan(1)
#define INF 1e8

typedef long long ll;

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

int main(){
  int N;
  cin >> N;
  vector<int> c(100000 + 2, 0);
  for(int i = 0; i < N; i++){
    int a, b;
    cin >> a >> b;
    c[a - 1]++;
    c[b]--;
  }
  int sum = 0, ans = 0;
  for(int i = 1; i <= N; i++){
    sum += c[i];
    if(i <= sum)ans = i;
  }
  cout << ans << endl;
}

Measured memory_bytes: 3104
#include<stdio.h>
int main(void){
	int no,kane[30][2],cap,cnt;
	int i,j,temp[2];

	for(;;){
		scanf("%d",&no);
		for(i=0;i<30;i++){
			for(j=0;j<2;j++){
				kane[i][j]=0;
			}
		}
		if(no==0){
			return 0;
		}
		for(i=0;i<no;i++){	
			scanf("%d %d",&kane[i][0],&kane[i][1]);
		}
		for(i=0;i<no-1;i++){
			for(j=no-1;j>i;j--){
				if(kane[j-1][1]>kane[j][1]){
					temp[1]=kane[j][1];
					kane[j][1]=kane[j-1][1];
					kane[j-1][1]=temp[1];
					temp[0]=kane[j][0];
					kane[j][0]=kane[j-1][0];
					kane[j-1][0]=temp[0];
				}
			}
		}
		cnt=0;
		cap=0;
		for(i=0;i<no;i++){
			cap+=kane[i][0];
			if(cap<=kane[i][1]){
				cnt++;
			}
		}
		if(cnt==no){
			puts("Yes");
		}else{
			puts("No");
		}
	}
	return 0;
}

Measured memory_bytes: 0
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s= sc.next();
        int ans = 0;
       for (int i = 0 ; i< 4 ; i++) {
           if (s.substring(i, i+1).equals("2")) {
               ans++;
           }
       }
        System.out.println(ans);
    }

}


Measured memory_bytes: 22228
w = int(raw_input())
n = int(raw_input())
r = range(1,w+1)
for _ in range(n):
    (a, b) = map(int, raw_input().split(','))
    r[a-1], r[b-1] = r[b-1], r[a-1]
for i in r:
    print i

Measured memory_bytes: 4228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

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

  ll n , m;
  cin >> n >> m;

  cout << n * m << endl;
}



Measured memory_bytes: 3180
#include<bits/stdc++.h>
using namespace std;
#define MAXN	2000005
#define P	1000000007
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
struct number {long long x; };
number operator + (number a, number b) {return (number) {(a.x + b.x) % P}; }
number operator - (number a, number b) {return (number) {(a.x - b.x + P) % P}; }
number operator * (number a, number b) {return (number) {(a.x * b.x) % P}; }
number fac[MAXN], inv[MAXN];
long long X1, X2, X3, X4, X5, X6;
long long Y1, Y2, Y3, Y4, Y5, Y6;
number power(number x, long long y) {
	if (y == 0) return (number) {1};
	number tmp = power(x, y / 2);
	if (y % 2 == 0) return tmp * tmp;
	else return tmp * tmp * x;
}
number Count(long long x, long long y) {
	return fac[x + y] * inv[x] * inv[y];
}
number solve(long long sx, long long sy, long long xl, long long yl, long long xr, long long yr, long long tx, long long ty) {
	number ans = (number) {0};
	for (long long i = xl; i <= xr; i++) {
		ans = ans + Count(i - sx, yr - sy) * Count(tx - i, ty - yr - 1) * (number) {i + yr};
		ans = ans - Count(i - sx, yl - sy - 1) * Count(tx - i, ty - yl) * (number) {i + yl - 1};
	}
	for (long long i = yl; i <= yr; i++) {
		ans = ans + Count(xr - sx, i - sy) * Count(tx - xr - 1, ty - i) * (number) {i + xr};
		ans = ans - Count(xl - sx - 1, i - sy) * Count(tx - xl, ty - i) * (number) {i + xl - 1};
	}
	return ans;
}
void init() {
	fac[0].x = 1;
	for (number i = (number) {1}; i.x < MAXN; i.x++)
		fac[i.x] = fac[i.x - 1] * i;
	inv[MAXN - 1] = power(fac[MAXN - 1], P - 2);
	for (number i = (number) {MAXN - 2}; i.x >= 0; i.x--)
		inv[i.x] = inv[i.x + 1] * (number) {i.x + 1};
}
int main() {
	init();
	read(X1), read(X2), read(X3), read(X4), read(X5), read(X6);
	read(Y1), read(Y2), read(Y3), read(Y4), read(Y5), read(Y6);
	X1--, Y1--, X6++, Y6++;
	number ans = (number) {0};
	ans = ans + solve(X1, Y1, X3, Y3, X4, Y4, X6, Y6);
	ans = ans - solve(X1, Y2, X3, Y3, X4, Y4, X6, Y6);
	ans = ans - solve(X2, Y1, X3, Y3, X4, Y4, X6, Y6);
	ans = ans + solve(X2, Y2, X3, Y3, X4, Y4, X6, Y6);
	ans = ans - solve(X1, Y1, X3, Y3, X4, Y4, X5, Y6);
	ans = ans + solve(X1, Y2, X3, Y3, X4, Y4, X5, Y6);
	ans = ans + solve(X2, Y1, X3, Y3, X4, Y4, X5, Y6);
	ans = ans - solve(X2, Y2, X3, Y3, X4, Y4, X5, Y6);
	ans = ans - solve(X1, Y1, X3, Y3, X4, Y4, X6, Y5);
	ans = ans + solve(X1, Y2, X3, Y3, X4, Y4, X6, Y5);
	ans = ans + solve(X2, Y1, X3, Y3, X4, Y4, X6, Y5);
	ans = ans - solve(X2, Y2, X3, Y3, X4, Y4, X6, Y5);
	ans = ans + solve(X1, Y1, X3, Y3, X4, Y4, X5, Y5);
	ans = ans - solve(X1, Y2, X3, Y3, X4, Y4, X5, Y5);
	ans = ans - solve(X2, Y1, X3, Y3, X4, Y4, X5, Y5);
	ans = ans + solve(X2, Y2, X3, Y3, X4, Y4, X5, Y5);
	cout << ans.x << endl;
	return 0;
}

Measured memory_bytes: 31488
import sys
input = sys.stdin.readline
INF = 10**64

Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

for N, A, B, C, D in Query:
    # ans = INF
    P = {}
    def solve(n):
        # print(n)
        if n == 0:
            return INF
        if n in P:
            return P[n]
        if n == 1:
            return D
        S = n*D
        if n%2 == 0:
            S = min(S, solve(n//2)+A)
        else:
            S = min(S, solve(n//2)+A+D)
            S = min(S, solve((n+1)//2)+A+D)
        if n%3 == 0:
            S = min(S, solve(n//3)+B)
        else:
            S = min(S, solve(n//3)+B+D*(n%3))
            S = min(S, solve(n//3+1)+B+D*(3-n%3))
        if n%5 == 0:
            S = min(S, solve(n//5)+C)
        else:
            S = min(S, solve(n//5)+C+D*(n%5))
            S = min(S, solve(n//5+1)+C+D*(5-n%5))
        P[n] = S
        # print(n, P)
        return S
    # print(P)
    print(solve(N))

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

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

typedef long long ll;

#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second　//pairの二つ目の要素


int main(){
    int n;
    cin>>n;
    int a;
    rep(i,n){
        cin>>a;
        if(!((a%2==0 && (a%3==0 || a%5==0) || a%2==1))){
            cout<<"DENIED"<<endl;
            return 0;
        }
    }
    cout<<"APPROVED"<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2], R[MAX/2+2];
int cnt;

void merge(int A[], int n, int left, int mid, int right){
  int n1 = mid - left;
  int n2 = right - mid;
  for ( int i = 0; i < n1; i++ ) L[i] = A[left + i];
  for ( int i = 0; i < n2; i++ ) R[i] = A[mid + i];
  L[n1] = R[n2] = SENTINEL;
  int i = 0, j = 0;
  for ( int k = left; k < right; k++ ){
    cnt++;
    if ( L[i] <= R[j] ){
      A[k] = L[i++];
    } else {
      A[k] = R[j++];
    }
  }
}

void mergeSort(int A[], int n, int left, int right ){
  if ( left+1 < right ){
    int mid = (left + right)/2;
    mergeSort(A, n, left, mid);
    mergeSort(A, n, mid, right);
    merge(A, n, left, mid, right);
  }
}

int main(){
  int A[MAX], n, i;
  cnt = 0;

  cin >> n;
  for ( i = 0; i < n; i++ ) cin >> A[i];

  mergeSort(A, n, 0, n);

  for ( i = 0; i < n; i++ ) {
    if ( i ) cout << " ";
    cout << A[i];
  }
  cout << endl;

  cout << cnt << endl;

  return 0;
}




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

int main(){
  int A, B, M;
  cin >> A >> B >> M;

  vector<int> a(A);
  int a_min = 1e5;
  for(auto& x: a){
    cin >> x;
    a_min = min(a_min, x);
  }

  vector<int> b(B);
  int b_min = 1e5;
  for(auto& x: b){
    cin >> x;
    b_min = min(b_min, x);
  }

  int ans = a_min + b_min;
  

  for(int i = 0; i < M; i++){
    int x, y, c;
    cin >> x >> y >> c;
    x--; y--;
    ans = min(ans, a[x] + b[y] - c);
  }

  cout << ans << endl;
}



Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cctype>
#define rep(i,a,b) for(int i=(a);i<b;i++)
#define INF 1000000000
#define MAX_N 105
using namespace std;
bool debug=false;

int main(){
  int N,L;
  string s[101];

  cin>>N>>L;

  rep(i,0,N)cin>>s[i];
  sort(s,s+N);

  rep(i,0,N)cout<<s[i];
  cout<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
          ll n,a=0,w=0,t=0,r=0,i;
          cin>>n;
          string s;
          for(i=0;i<n;i++)
          {
                    cin>>s;
                    if(s=="AC")a++;
                    else if(s=="WA")w++;
                    if(s=="TLE")t++;
                    if(s=="RE")r++;
          }
          cout<<"AC x "<<a<<endl;
           cout<<"WA x "<<w<<endl;
            cout<<"TLE x "<<t<<endl;
             cout<<"RE x "<<r<<endl;
}


Measured memory_bytes: 3616
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <map>
#define rep(i, n) for(int i=0;i<(int)(n);i++)
#define pb(a) push_back(a)
#define MAX(a, b) ((a < b)?b:a)
#define MIN(a, b) ((a > b)?b:a)
typedef long long int ll;
typedef unsigned long long int ull;
using namespace std;
ll N;

int main()
{
	// [a] = bはaからたどり着けるより高い展望台があったら１
	int relation[100000 + 2] = {0};
	// [a] はaの高さ
	map<int, int> height;
	int n, m;
	cin >> n >> m;
	rep(i, n) {
		int h;
		cin >> h;
		height[i + 1] = h;
		//cout << "height[" << i+1 << "] = " << height[i+1]<< endl;
	}

	rep (i, m) {
		int a, b, ah, bh;
		cin >> a >> b;
		ah = height[a];
		bh = height[b];
		//cout << "======a" << a << " b=" << b <<endl;
		if (ah <= bh) {
			relation[a] = 1; //cout << "a = 1" << endl;
		}
		if (bh <= ah) {
			relation[b] = 1; //cout << "b = 1" << endl;
		}
		//cout << "ah=" << ah << " bh=" << bh << endl;
	}

	int cnt = 0;
	rep (i, n) {
		//cout << "relation[" << i+1 << "] = " << relation[i+1]<< endl;
		if ( relation[i+1] == 0 ) cnt++;
	}

	cout << cnt << endl;

	return 0;
}


Measured memory_bytes: 8660
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner in = new FastScanner();
        int n = in.nextInt();
        int a = n % 10;
        n /= 10;
        int b = n % 10;
        n /= 10;
        int c = n % 10;
        n /= 10;
        if (a == b && a == c) {
            System.out.println("Yes");
        } else if (b == c && c == n) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(String s) {
            try {
                br = new BufferedReader(new FileReader(s));
            } catch (FileNotFoundException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String nextToken() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        String nextLine() {
            st = null;
            try {
                return br.readLine();
            } catch (IOException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            return null;
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        double nextDouble() {
            return Double.parseDouble(nextToken());
        }
    }
}


Measured memory_bytes: 21204
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
n = int(input())
sp = [None]*n
for i in range(n):
    sp[i] = [None]*3
# print(sp)
for i in range(n):
    sp[i] = input().split()
for i in range(n):
    sp[i][1] = int(sp[i][1])
for i in range(n):
    sp[i].append((i+1))
# print(sp)

sp2 = sorted(sp, key=lambda x: x[1], reverse=True)
# print(sp2)
sp3 = sorted(sp2, key=lambda x: x[0])

for i in range(n):
    print(sp3[i][2])


Measured memory_bytes: 60396
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0;i<n;i++)
#define rep2(i,a,n) for(int i=a;i<n;i++)
#define been(ix) (ix).begin(),(ix).end()
using namespace std;
typedef long long ll; 
typedef vector<int> vi;
typedef vector<long long> vl;
const ll INFL = 1e18;
const int INF = 1001001001; 
typedef pair<int,int> P;
#define foreach(ix,i) for(auto& (ix) : (i))
typedef long double ld;
const int mod =1000000007;
const double PI = acos(-1);
template<typename TypeInt>
std::string Itoa(const TypeInt v, int base)
{
    static const char table[] = "zabcdefghijklmnopqrstuvwxyz";
    string ret;
    static numeric_limits<TypeInt> t;
    TypeInt n = v;
    if (t.is_signed) {
        if (v < 0) n *= -1;
    }

    while (n >= base) {
        ret += table[n%base];
        n /= base;
    }
    ret += table[n];
    if (t.is_signed) {
        if (v < 0 && base == 10) ret += '-';
    }
    // 文字列の順番を逆にする
    std::reverse(ret.begin(), ret.end());

    return ret;
}
int main(){
	ll n;cin>>n;
    //n-=1;
    if(n==1){
        cout<<'a'<<endl;
        return 0;
    }
    string ans ="";
    //int i =1;
    char ta[26];
    ta[0]='z';
    rep(i,25)ta[i+1]='a'+i;
    for(int i = 1;n>0;i++){
        if(n%26==0){
            ans+=ta[0];
            n/=26;
            n--;
        }
        else{
            ans+=ta[n%26];
        n/=26;
    }
    }
    //ans+=ta[n%26-1];
    reverse(been(ans));
    cout<<ans<<endl;
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define loop(i, a, b) for(lli i=a; i<b; i++)
#define loopb(i, a, b) for(lli i=a; i>=b; i--)
#define pb push_back
#define umap unordered_map
typedef long long int lli;
typedef pair<lli, lli> pii;
typedef vector<lli> vll;
// use to avoid collision
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
// for pair in unordered_map
struct hash_pair {
    static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
	}
    template <class T1, class T2>
    size_t operator()(const pair<T1, T2>& p) const{
        auto hash1 = hash<T1>{}(p.first);
        auto hash2 = hash<T2>{}(p.second);
        uint64_t x = hash1 ^ hash2;
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
lli M = 1e9 + 7;
lli power(lli x, lli y){
    lli res = 1;
    x = x ;
    while (y > 0) {
        if (y & 1)
            res = (res*x)%M ;
        y = y>>1;
        x = (x*x)%M;
    }
    return res%M;
}
lli gcd(lli a, lli b, lli &x, lli& y){
	if(a == 0){
		x = 0;
		y = 1;
		return b;
	}
	lli x1, y1;
	lli d = gcd(b%a, a, x1, y1);
	x = y1 - (b/a)*x1;
	y = x1;
	return d;
}
lli solve(){
	lli n, k, s;
	cin>>n>>k>>s;
	lli N = 1e9;
	if(s == 1e9){
		loop(i, 0, k)
			cout<<N<<" ";
		loop(i, k, n)
			cout<<1<<" ";
		return 0;
	}
	else{
		loop(i, 0, k)
			cout<<s<<" ";
		loop(i, k, n)
			cout<<N<<" ";
		return 0;
	}
}
int main(){
	fastio;
	lli t;
	// cin>>t;
	t = 1;
	while(t>0){
		t--;
		solve();
	}
}

Measured memory_bytes: 1280
#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
#include <utility>
#include <functional>
#include <deque>
#include <cctype>
#include <stack>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, pair<ll, ll>> PP;

const ll MOD = 1e9 + 7;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
#define fr first
#define sc second


struct edge { ll to, cost; };
std::vector<edge>v[100010];
ll d[100010];

void dijkstra(ll n) {
	for (int i = 0;i <= n;i++) {
		d[i] = INF;
	}
	d[1] = 1;
	std::priority_queue<P, std::vector<P>, std::greater<P>>pq;
	pq.push(P(d[1], 1));
	while (!pq.empty()) {
		P a = pq.top();
		pq.pop();
		ll i = a.second;
		if (d[i] < a.first)continue;
		for (int k = 0;k < v[i].size();k++) {
			edge e = v[i][k];
			if (d[e.to] <= d[i] + e.cost)continue;
			d[e.to] = d[i] + e.cost;
			pq.push(P(d[e.to], e.to));
		}
	}
	return;
}


int main() {
	ll k;
	cin >> k;
	for (int i = 0;i < k;i++) {
		v[i].pb(edge{ (i + 1) % k, 1 });
	}
	for (int i = 1;i < k;i++) {
		if ((i * 10) % k != i)v[i].pb(edge{ (i * 10) % k,0 });
	}
	dijkstra(k);
	cout << d[0] << endl;
	return 0;
}


Measured memory_bytes: 9208
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(v) v.begin(), v.end()
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define Rep(n) for (ll _ = 0; _ < (ll)(n); _++) 
#define fs first
#define sc second
#define _GLIBCXX_DEBUG

template<class S>S sum(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
ll min(int a,ll b){return min((ll)a,b);} ll min(ll a,int b){return min(a,(ll)b);}

template <class S>
void print(vector<S> &v){for(ll i=0; i<(ll)v.size(); i++){
		cerr << v[i] << ' ';
	}
	cerr << endl;
}
template <class S>
void print(vector<vector<S>> &v) {
  	for (ll i = 0; i < (ll)v.size(); i++) {
    	for (ll j = 0; j < (ll)v[i].size(); j++) {
      		cerr << v[i][j] << ' ';
    	}
    	cerr << endl;
  	}
}

int main(void){
	ll x; cin >> x;
	vector<ll> m(1,0);
	ll i=1;
	while(1){
		m.push_back(i*i*i*i*i);
		if(m[i] - m[i-1] > x) break;
		i++;
	}
	rep(j, i){
		rep(k, j+1){
			if(m[j] - m[k] == x){
				cout << j << ' ' << k << endl;
				return 0;
			}else if(m[j] + m[k] == x){
				cout << j << " -" << k << endl;
				return 0;
			}
		}
	}
}

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

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



const long long INF = 1e17;

ll a[500];
ll dp[500][500];
ll pre[500];


int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pre[i] = a[i] + pre[i-1];
    }

    for (int l = 1; l < n; l++)
    {
        for (int i = 1; i+l <= n; i++)
        {
            int j = i + l;
            dp[i][j] = INF;
            for (int k = i; k < j; k++)
            {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + pre[j] - pre[i-1]);
            }
        }
    }

    cout << dp[1][n];

    return 0;
}


Measured memory_bytes: 1920
#include <cstdio>
#include <map>
#include <vector>
#include <algorithm>

int n, k, tmp;
std::map<int, int> m;
std::vector<int> v;

int main(){
    scanf("%d %d", &n, &k);

    for(int i = 0; i < n; i++){
        scanf("%d", &tmp);

        if(m.count(tmp) == 0){
            m[tmp] = 1;
            v.push_back(tmp);
        }else{
            m[tmp]++;
        }
    }

    int ans = 0;
    if(m.size() > k){
        int i = 0;
        for(auto var : m){
            v[i++] = var.second;
        }

        std::sort(v.begin(), v.end());

        for(i = 0; i < m.size() - k; i++){
            ans += v[i];
        }
    }

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

    return 0;
}


Measured memory_bytes: 10356
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <time.h>
#include <random>
#include <string>
#include <cassert>
#include <vector>
#include <ostream>
#include <istream>
#include <stack>
#include <deque>
#include <queue>
#include <functional>
#include <chrono>
#include <stack>

using namespace std;

#define int long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define ld long double

ostream& operator<< (ostream &a, const vector<int> &b) {
    for (auto k : b) cout << k << " ";
    return a;
}

istream& operator>> (istream& a, pii& b) {
    cin >> b.first >> b.second;
    return a;
}

ostream& operator<< (ostream& a, const pii& b) {
    cout << "{" << b.first << ", " << b.second << "}";
    return a;
}

template <typename T1, typename T2> inline void chkmin(T1 &x, const T2 &y) {if (x > y) x = y;}
template <typename T1, typename T2> inline void chkmax(T1 &x, const T2 &y) {if (x < y) x = y;}


#ifdef LOCAL
    #define dbg(x) cout << #x << " : " << (x) << "\n";
    const int INF = 1e5;
    // const int mod = 2600000069;
    // const int p = 10;
    // const ld PI = 3.1415926535;
#else
    #define dbg(x)
    const int INF = 1e18 + 10;
    // const int mod = 2600000069;
    // const int p = 179;
    // const ld PI = 3.1415926535;
#endif

// #pragma GCC optimize("Ofast,no-stack-protector")
// #pragma GCC target("sse,sse2,sse3,sse3,sse4")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("fast-math")
// #pragma GCC target("avx2")  
// #pragma GCC optimize("section-anchors")
// #pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
// #pragma GCC optimize("vpt")
// #pragma GCC optimize("rename-registers")
// #pragma GCC optimize("move-loop-invariants")
// #pragma GCC optimize("unswitch-loops")
// #pragma GCC optimize("function-sections")
// #pragma GCC optimize("data-sections")

mt19937 gen(chrono::high_resolution_clock::now().time_since_epoch().count());

int pow(int a, int p) {
    if (p == 0) return 1;
    if (p == 1) return a;
    int k = pow(a, p >> 1);
    if (INF / k < k) return INF;
    return k * k;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    n--;
    int l = 1;
    while (n >= pow(26, l)) {
        n -= pow(26, l);
        l++;
    }
    string ans(l, 'a');
    for (int i = l - 1; i >= 0; i--) {
        ans[i] = char('a' + n % 26);
        n /= 26;
    }
    cout << ans;
}
/*

*/

Measured memory_bytes: 4100
#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<random>
#include<functional>
#include<utility>

typedef long long ll;

#define rep(i,n) for(int i=0; i<n; i++)
#define pb push_back
#define P pair<int, int>
#define PLI pair<ll, int>
#define PLL pair<ll, ll>
#define VI vector<int>
#define VII vector<VI>

using namespace std;


int N;
ll a[3005], dp[3005][3005];
int main() {
	cin >> N;
	rep(i, N) cin >> a[i], dp[i][i] = 0;
	for (int len = 1; len <= N; len++) {
		for (int i = 0; i + len <= N; i++) {
			int j = i + len;
			if ((N - len) % 2 == 0) {
				dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1]);
			}
			else {
				dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1]);
			}
		}
	}
	cout << dp[0][N] << endl;

	return 0;
}



Measured memory_bytes: 70016
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int n;
ll k,a[225816];

bool judge(ll x){
	int i;
	ll y;
	ll cnt=0ll;
	for(i=0; i<n; ++i){
		if(a[i]>0){
			y = x/a[i];
			if(y*a[i]>x){
				--y;
			}
			cnt += (ll)(upper_bound(a,a+i,y)-a);
		}else if(a[i]<0){
			y = x/a[i];
			if(y*a[i]>x){
				++y;
			}
			cnt += (ll)(&a[i]-lower_bound(a,a+i,y));
		}else if(x>=0ll){
			cnt += i;
		}
	}
	return (cnt>=k);
}

int main(void){
	int i;
	ll l,r,m;
	cin >> n >> k;
	for(i=0; i<n; ++i){
		cin >> a[i];
	}
	sort(a,a+n);
	l = -INFLL;
	r = INFLL;
	while(r-l>1ll){
		m = (l+r)/2;
		if(judge(m)){
			r = m;
		}else{
			l = m;
		}
	}
	cout << r << endl;
	return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//typedef vector<vector<ll>> Graph;

const ll mod = 1e9 + 7;
//const ll mod = 998244353;

#define REP(i,n) for(ll i=0;i<(ll)n;i++)
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define spa << " " <<
#define fi first
#define se second

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

template<typename T> void debug(vector<vector<T>>&v,ll h,ll w){for(ll i=0;i<h;i++)
{cerr<<v[i][0];for(ll j=1;j<w;j++)cerr spa v[i][j];cerr<<endl;}};
template<typename T> void debug(vector<T>&v,ll n){if(n!=0)cerr<<v[0];
for(ll i=1;i<n;i++)cerr spa v[i];
cerr<<endl;};

string num2bit(ll num, ll len){
    string bit = "";
    REP(i, len){
    bit += char('0'+(num>>i & 1));
    }
    return bit;
}

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

    string S, T;
    cin >> S >> T;
    ll res = 0;
    REP(i, S.size()){
        if(S[i] != T[i]) res++;
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 3888
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    Int N; cin >> N;
    map<Int, Int> A;
    rep(i, 0, N) {
        Int a; cin >> a;
        A[a]++;
    }

    vector<Int> pairs;

    for(auto a : A) {
        if (a.second >= 2) pairs.emplace_back(a.first);
        if (a.second >= 4) pairs.emplace_back(a.first);
    }
    sort(pairs.begin(), pairs.end(), greater<Int>());

    if (pairs.size() >= 2) cout << pairs[0]*pairs[1] << endl;
    else cout << 0 << endl;
}


Measured memory_bytes: 6528
#include<bits/stdc++.h>
#include<string.h>
 
typedef long long int ll;
#define all(x) (x).begin(), (x).end()
 
using namespace std;

int nxt() {
    int x;
    cin >> x;
    return x;
}

ll nxtl(){
    ll x;
    cin>>x;
    return x;
}
 
void SieveOfEratosthenes(int n,vector <int> &primes) 
{ 
    // Create a boolean array "prime[0..n]" and initialize 
    // all entries it as true. A value in prime[i] will 
    // finally be false if i is Not a prime, else true. 
    bool prime[n+1]; 
    memset(prime, true, sizeof(prime)); 
  
    for (int p=2; p*p<=n; p++) 
    { 
        // If prime[p] is not changed, then it is a prime 
        if (prime[p] == true) 
        { 
            // Update all multiples of p greater than or  
            // equal to the square of it 
            // numbers which are multiple of p and are 
            // less than p^2 are already been marked.  
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
  
    // Print all prime numbers 
    for (int p=2; p<=n; p++) 
       if (prime[p]) 
          primes.push_back(p);
} 
 
ll max(ll a,ll b)
{
    if(a>b)
        return a;
    return b;
}
 
ll power(ll x, ll y,ll mod) 
{ 
    ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2,mod); 
    if (y%2 == 0) 
        return (temp*temp)%mod; 
    else
        return (((x*temp)%mod)*temp)%mod; 
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n=nxt(),k=nxt(),c=nxt();
    string s;
    cin>>s;
    set <int> s2;
    map <int,set <int> ,greater<int> > m2;
    set <int> r;
    vector <int> ans(n);
    for(int i=n-1;i>=0;i--)
    {
        if(s[i]=='o')
        {
            auto it=s2.lower_bound(i+c+1);
            int val=1;
            if(it!=s2.end())
                val+=ans[*it];
            if(val>k)
                val=k;
            if(m2.find(val)==m2.end())
                m2[val]=r;
            m2[val].insert(i);
            ans[i]=val;
            s2.insert(i);
        }
    }
    //cout<<"came"<<endl;
    auto it=m2.begin();
    int index=*((it->second).begin());
    
    it++;
    for(;it!=m2.end();it++)
    {
        while(*(it->second).begin()<index+c+1)
            (it->second).erase((it->second).begin());
        index=*(it->second).begin();

    }
    vector <int> test;
    int prev=-1e6;
    int cur=k;
    for(auto it=m2.begin();it!=m2.end();it++)
        {
            auto it2=it->second.begin();
            for(;it2!=it->second.end();it2++)
            {
                if(*it2>=prev+c+1)
                {
                    if(it->first==k&&it->second.size()==1)
                        test.push_back(*it2+1);
                    k--;
                    prev=*it2;
                }
            }
        }

    for(int i=0;i<test.size();i++)
        cout<<test[i]<<endl;
   
    
    return 0;   
}




 
 


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


#define MAX_N 10000000
bool is_prime[MAX_N+1];
void sieve(int n){
	memset(is_prime,true,sizeof(is_prime));
	is_prime[0]=is_prime[1]=false;
	for(int i=2;i<=n;i++){
		if(is_prime[i]){
			for(int j=2*i;j<=n;j+=i)is_prime[j]=false;
		}
	}
}


int main(){
	int n;
	sieve(MAX_N);
	vector<int> v;
	for(int i=13;i<=MAX_N;i++){
		if(is_prime[i-8]&&is_prime[i-6]&&is_prime[i-2]&&is_prime[i])
			v.push_back(i);
	}
	while(cin>>n,n){
		int ans=13;
		cout<<*(upper_bound(v.begin(),v.end(),n)-1)<<endl;
	}
	return 0;
}

Measured memory_bytes: 10992
#include <bits/stdc++.h>
using namespace std;
int main(void){
    
    //*
    int a, b;
    cin >> a >> b ;
    //*/

    /*
    vector<int> vec(3);
    cin >> vec.at(0) >> vec.at(1) >> vec.at(2) ;
    
    sort(vec.begin(), vec.end());
    */
    
    //*
    if( a * b % 2 == 0 ){
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    //*/
    
    //cout << ( a / 2 ) * ( a / 2 + a % 2 ) << endl;

    return 0; 
}


Measured memory_bytes: 3604
#include <iostream>
#include <vector>

int main(void){
	std::vector<int> trainID; //list of inputted trainID
	int tmp;

	std::cin >> tmp; //input trainID
	trainID.push_back(tmp); //add trainID

	while(std::cin >> tmp){  //input trainID or 0
		if(tmp == 0){
			std::cout << trainID.back() << std::endl; //output last trainID
			trainID.pop_back(); //delete outputted trainID
		}else{
			trainID.push_back(tmp); //add trainID
		}
	}

	return 0;
}

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

#define fi first
#define se second
#define pb push_back
using pii = pair <int, int>;

const int N = 1011;

char c[N][N];
int cnt[N][N];

int main() {
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i ++)
		scanf("%s", c[i] + 1);
	vector <pii> v;
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++) if(c[i][j] != '.') {
			for(int s : {-1, 0, 1}) for(int t : {-1, 0, 1})
				cnt[i][j] += (c[i + s][j + t] == '.');
			if(cnt[i][j] >= c[i][j] - '0')
				v.pb({i, j});
		}
	int ans = 0;
	while(v.size()) {
		vector <pii> u;
		for(pii p : v)
			for(int s : {-1, 0, 1}) for(int t : {-1, 0, 1}) {
				int i = p.fi + s, j = p.se + t;
				cnt[i][j] ++;
				if(c[i][j] != '.' && cnt[i][j] == c[i][j] - '0')
					u.pb({i, j});
			}
		v = u;
		ans ++;
	}
	cout << ans << '\n';
}

Measured memory_bytes: 8096