akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define ppb pop_back
#define vll vector<ll>
#define vi vector<int>

const ll INF = 1000000007;

/*
const int max_size = 100001;
int parent[max_size];
int Size[max_size];

int root(int x){
    while(x!=parent[x]){
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

void sunion(int x,int y){
    int rx = root(x);
    int ry = root(y);
    if(rx != ry){
        if(Size[rx] > Size[ry]){
            parent[ry] = parent[rx];
            Size[rx] += Size[ry];
        }
        else{
            parent[rx] = parent[ry];
            Size[ry] += Size[rx];
        }
    }
}
*/

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t=1;
    //cin >> t;
    while(t--){
        int n,m;
        cin >> n >> m;
        int a[m];
        for(auto &it : a) cin >> it;
        ll sum=0;
        for(int i=0;i<m;i++){
            sum += a[i];
        }
        ll ans = n-sum;
        if(ans<0) ans=-1;
        cout << ans << "\n";
    }
    return 0;
}

Measured memory_bytes: 3616
l, r = gets.split(' ').map(&:to_i)

isBreak = false
min = 2019
(r-l).times do |i|
    (r-l-i).times do |j|
        tmp = ((l+i)*(l+i+j+1))%2019
        min = tmp if min > tmp
        if min == 0 then
            isBreak = true
            break
        end
    end
    break if isBreak
end

print min

Measured memory_bytes: 1788
#include "bits/stdc++.h"
using namespace std;
const int MAX = 700000;
const int MOD = 1000000007;

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

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

// 二項係数計算
long long COM(int n, int k) {
	if (n < k) return 0;
	if (n < 0 || k < 0) return 0;
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
/*第二引数で第一引数を割ったときの切り上げの計算*/
long long int maxtime(long long int x, long long int y){
	return(x + y - 1) / y;

}
/*最大公約数*/
long long int lcm(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;

	if (number2 > number1) {
		m = number2;
		n = number1;
	}
	long long int s = -1;
	while (s != 0) {
		s = m % n;
		m = n;
		n = s;
	}
	return m;
}
/*最大公倍数*/
long long int gcd(long long int number1, long long int number2) {
	long long int m = number1;
	long long int n = number2;
	return m / lcm(m, n) * n;
}
/*逆元計算*/
long long int  modinv(long long a, long long m) {
	long long int b = m, u = 1, v = 0;
	while (b) {
		long long int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}
// index が条件を満たすかどうか
vector<long long int >meguru;
bool isOK(int index, int key) {
	if (meguru[index] >= key) return true;
	else return false;
}
// 汎用的な二分探索のテンプレ
int binary_search(int key) {
	int left = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
	int right = (int)meguru.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()
	/* どんな二分探索でもここの書き方を変えずにできる！ */
	while (right - left > 1) {
		int mid = left + (right - left) / 2;

		if (isOK(mid, key)) right = mid;
		else left = mid;
	}
	/* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
	return right;
}
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}
int main() {
	long long int x;
	cin >> x;
	int sum = 0;
	for (int i = 1; i <= 100000000; i++) {
		sum = sum + i;
		if (x <= sum) {
			cout << i;
			return 0;
		}
	}
}

Measured memory_bytes: 384
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 10010010010010;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a / gcd(a, b) * b ;
}

int main() {
    int H,W;cin >> H >> W;
    vector<vector<int>> retu(H,vector<int>(W));
    for(int i = 0;i<H;i++)for(int j = 0;j<W;j++) cin >> retu.at(i).at(j);
    vector<tuple<int,int,int,int>> ans;
    for(int i = 0;i<H;i++){
        if(i % 2 == 0){
            for(int j = 0;j<W-1;j++){
                if(retu.at(i).at(j) % 2 == 1){
                    retu.at(i).at(j+1)++;
                    ans.push_back(make_tuple(i,j,i,j+1));
                }
            }
            if(retu.at(i).at(W-1) % 2 == 1){
                if(i != H-1){
                    retu.at(i+1).at(W-1)++;
                    ans.push_back(make_tuple(i,W-1,i+1,W-1));
                }
            }
        }
        else{
            for(int j = W-1;j>=1;j--){
                if(retu.at(i).at(j) % 2 == 1){
                    retu.at(i).at(j-1)++;
                    ans.push_back(make_tuple(i,j,i,j-1));
                }
            }
            if(retu.at(i).at(0) % 2 == 1){
                if(i != H-1){
                    retu.at(i+1).at(0)++;
                    ans.push_back(make_tuple(i,0,i+1,0));
                }
            }
        }
    }
    cout << ans.size() << endl;
    for(int i = 0;i<ans.size();i++){
        cout << get<0>(ans.at(i))+1 << " "  << get<1>(ans.at(i))+1 << " " << get<2>(ans.at(i))+1 << " " << get<3>(ans.at(i))+1 << endl; 
    }
}


Measured memory_bytes: 5232
#include<stdio.h>
 
int main(){
  int len = 0, i, j, count = 0;
  char s[201];
  
  scanf("%s", s);
  while(s[len]){
    len++;
  }
  
  for (i = len - 2; i >= 0; i -= 2){
    count++;
    s[i] = '\0';
    for (j = 0; j < i/2; j++){
      if(s[j] != s[j + i/2]){
        break;
      }
    }
    if(i/2 == j){
      printf("%d\n", len - count*2);
      return 0;
    }
  }
}

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

#define ll long long int
#define INF 1000000007


int main(){
	string s;
	cin >> s;
	int n = s.length();
	string ans = "";
	for ( int i = 0; i < n ; i++ ){
		if( s[i] == 'B' ){
			if( ans.size() == 0 )
				continue;
			else
				ans.pop_back();
		}
		else if( s[i] == '1' )
			ans += '1';
		else
			ans += '0';
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3576
"""
author : halo2halo
date : 18,Oct,2019
"""

import sys
input = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 7)

S = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
ans = sum(B)
num = -1
for i in A:
    if num + 1 == i:
        ans += C[num - 1]
    num = i


print(ans)


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

using namespace std;

int main() {
    int city[5];
    for (int i = 0; i < 5; i++) {
        cin >> city[i];
    }
    int k;
    cin >> k;
    
    for (int i = 0; i < 5; i++) {
        for (int j = 1; j < 5; j++) {
            if (city[j] - city[i] > k) {
                cout << ":(" << endl;
                return 0;
            }
        }
    }
    
    
    cout << "Yay!" << endl;
    return 0;
}

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

MOD = 10 ** 9 + 7

C.sort()
C = C[::-1]

a0 = pow(2, N - 1, MOD)
d = pow(2, N - 2, MOD) if N - 2 >= 0 else 0
answer = 0
for i in range(N):
  answer = (answer + (a0 + d * i) * C[i]) % MOD
answer = (answer * pow(2, N, MOD)) % MOD
print(int(answer))

Measured memory_bytes: 89036
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int> d;
int w[100],v[100];
int n,W;
int dp(int i,int j){
	pair<int,int> p=make_pair(i,j);
	if(d.count(p)) return d[p];
	long long res;
	if(i==n) res=0;
	else if(j<w[i]) res=dp(i+1,j);
	else res=max(dp(i+1,j),dp(i+1,j-w[i])+v[i]);
	return d[p]=res;
}
int main(){
	cin >> n >> W;
	for(int i=0;i<n;i++){
		cin >> w[i] >> v[i];
	}
	cout << dp(0,W) << endl;
}

Measured memory_bytes: 6400
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }


int main() {
    int n, m; cin >> n >> m;
    vector<int> lvec;
    vector<int> rvec;
    if(n%2 == 0) {
        lvec.emplace_back(2); rvec.emplace_back(n);
        int half = (n-1)/2;
        half /= 2;
        if(half == 0) rvec[0] = lvec[0]+1;
        if(half > m) {
            for(int i =1; i < m; ++i) {
                lvec.emplace_back(lvec[i-1]+1);
                rvec.emplace_back(rvec[i-1]-1);
            }
        }else {
            for(int i = 1; i < half; ++i) {
                lvec.emplace_back(lvec[i-1]+1);
                rvec.emplace_back(rvec[i-1]-1);
            }
            int now = lvec.size();
            lvec.emplace_back(lvec[now-1]+2);
            rvec.emplace_back(rvec[now-1]-1);
            for(int i = now+1; i < m; ++i) {
                lvec.emplace_back(lvec[i-1]+1);
                rvec.emplace_back(rvec[i-1]-1);
            }
        }
    }else {
        lvec.emplace_back(2); rvec.emplace_back(n);
        for(int i = 1; i < m; ++i) {
            lvec.emplace_back(lvec[i-1]+1);
            rvec.emplace_back(rvec[i-1]-1);
        }
    }

    for(int i = 0; i < m; ++i ) {
        cout << lvec[i] << " " << rvec[i] << endl;
    }
}

Measured memory_bytes: 3900
import sys

sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))
def II(): return int(sys.stdin.readline())
def LS(): return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]

def main():
    s = S()
    for i, v in enumerate(s):
        if i % 2 == 0:
            if v not in ("R", "U", "D"):
                print("No")
                return
        else:
            if v not in ("L", "U", "D"):
                print("No")
                return
    print("Yes")


if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
/** 
 *                                                                   
 *   |    |                        ,   .              ,--.,--.,--.,--.
 *   |    |    ,---..    ,,---.    |   |,---..   .      -||  ||  ||  |
 *   |    |    |   | \  / |---'    `---'|   ||   |       ||  ||  ||  |
 *   `    `---'`---'  `'  `---'      |  `---'`---'    `--'`--'`--'`--'
 *                                   `                                
**/
#include <bits/stdc++.h>
using namespace std;

int n, k, a[105];
bool dp[2][100005], visited[2][100005];

bool solve(int org, int batu) {
	if (batu < 0) return 1;
	if (visited[org][batu]) return dp[org][batu];

	bool res = 0;
	for (int i = 0; i < n; i++) {
		res |= !solve(1 - org, batu - a[i]);
	}

	visited[org][batu] = 1;
	return dp[org][batu] = res;
}

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

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

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

	if (solve(0, k)) {
		cout << "First\n";
	} else {
		cout << "Second\n";
	}

	return 0;
}

Measured memory_bytes: 6912
#include <bits/stdc++.h>
#define int long long
#define ll long long
using ull = unsigned long long;
using namespace std;
const int INF = 1e10;
const int MOD = 1e9 + 7;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i <= (b); ++i)
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(), (v).end()
#define SZ(x) ((int)(x).size())
#define P pair<int, int>
#define V vector<int>
#define S set<int>
#define itn int
bool dbg = false;
void solve() {
}

signed main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int r;
    cin >> r;
    cout << r * r << endl;
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <random>
#include <cassert>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
#define MEM(a,b) memset((a),(b),sizeof(a))
const LL INF = 1e9 + 7;
const int N = 4e4 + 10;

int main()
{
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int ans = 0;
	LL x, y;
	cin >> x >> y;
	while (x <= y)
		ans++, x <<= 1;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
ary_original = []
ary_answers  = []
tempmaxi = 0
maxi = 0
n, *ary_original = $<.map(&:to_i)
c=0

while tempmaxi < n
  max = 0
  min = 1E9+10

  for i in tempmaxi...n
    if max < ary_original[i]
      max  = ary_original[i]
      maxi = i
    end
  end

  for i in tempmaxi..maxi
    if min > ary_original[i] then min = ary_original[i] end
  end

  if max == min then c += 1 end

  ary_answers << max - min
  tempmaxi = maxi + 1
end

if c == n
  max = - (1E9 + 10)

  for i in 0..n-2
    x = ary_original[i+1] - ary_original[i]
    if max < x then max = x end
  end

  puts max
else

  puts ary_answers.max
end



Measured memory_bytes: 10136
import scala.io.StdIn
import scala.annotation.tailrec
import scala.collection.mutable.HashMap

object Main extends App {
  val Array(h, w) = StdIn.readLine.split(" ").map(_.toInt)
  val table = Iterator.continually(StdIn.readLine)
    .take(h)
    .map(_.map(_ == '#').toArray)
    .toArray

  @inline
  def flat(i:Int, j:Int):Int = i * w + j

  val ans = {
    val dx = Array(0, 1, 0, -1)
    val dy = Array(-1, 0, 1, 0)
    val uft = new UnionFindTree(flat(h, w))

    for{
      i <- 0 until h
      j <- 0 until w
    } {
        (0 until 4).foreach(k => {
          val y = i + dy(k)
          val x = j + dx(k)
          if(0 <= y && y < h && 0 <= x && x < w &&
              table(i)(j) != table(y)(x) &&
              !uft.same(flat(i, j), flat(y, x))) {
            uft.unite(flat(i,j), flat(y,x))
          }
        })
    }
    uft.map.values./:(0L)((acc,e) => {
      acc + e._1.toLong * e._2.toLong
    })
  }

  println(ans)

  class UnionFindTree(n:Int) {
    private val par  = Array.range(0, n)
    private val rank = Array.fill(n)(1)
    val map = HashMap.empty[Int,(Int,Int)]

    def root(x:Int):Int = {
      if(par(x) == x) x
      else { par(x) = root(par(x)); par(x) }
    }

    def same(x:Int, y:Int):Boolean = root(x) == root(y)

    def unite(x:Int, y:Int):Unit = {
      val rx = root(x)
      val ry = root(y)
      if(rx == ry) return

      if(!map.contains(ry)) map(ry) = if(table(ry/w)(ry%w)) (1,0) else (0,1)
      if(!map.contains(rx)) map(rx) = if(table(rx/w)(rx%w)) (1,0) else (0,1)

      if(rank(rx) < rank(ry)) {
        par(rx) = ry
        map(ry) = (map(ry)._1 + map(rx)._1, map(ry)._2 + map(rx)._2)
        map -= rx
      }
      else {
        par(ry) = rx
        if(rank(rx) == rank(ry)) rank(rx) += 1
        map(rx) = (map(rx)._1 + map(ry)._1, map(rx)._2 + map(ry)._2)
        map -= ry
      }
    }
  }
}

Measured memory_bytes: 47588
#include <iostream>
#include <string>
#include <cstdlib>
#include <vector>
#include <array>
#include <map>
#include <set>
#include <algorithm>
#include <queue>
#include <stack>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdio>
#include <iomanip>
#include <utility>
#include <unordered_map>

using namespace std;
typedef long long int ll;

#define SP(x) setprecision((int)x)
#define SW(x) setw(x)    // 桁数指定
#define SF(c) setfill(c) // 埋め文字指定('0')
#define ALL(v) v.begin(), v.end()

int main(int argc, char const *argv[])
{
    ll n;
    cin>>n;
    vector<ll> a(n);
    ll s = 0;
    for (ll i = 0; i < n; i++)
    {
        cin >> a[i];
        s ^= a[i];
    }

    for (ll i = 0; i < n; i++)
    {
        cout << (s ^ a[i]);
        if (i != n - 1)
        {
            cout << ' ';
        }
    }
    cout << endl;
}

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

//    int n=132;
//    bitset<16>binar(n);
//    int a = bitset<16>(binar).to_ulong();
//    cout<<a;

#define int long long
#define pb push_back
#define rep(i,a,b) for ( int i = a; i < b; i++)
#define all(c) (c).begin(),(c).end()

using namespace std;

signed main()
{
   int a,b,x;
   int ans;
   cin>>a>>b>>x;
   if(x<b){
   	 ans = x*a/b;
   }
   else{
   	x = b-1;
   	 ans = x*a/b;
   }
   cout<<ans;
}
        
        
    

    





Measured memory_bytes: 3608
s = input()
ans = 'Yes'
odd = ['R', 'U', 'D']
even = ['L', 'U', 'D']
for i in range(len(s)):
    if (i+1)%2 == 0:
        if not s[i] in even:
            ans = 'No'
    else:
        if not s[i] in odd:
            ans = 'No'
print(ans)


Measured memory_bytes: 2940
package main

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

var nextString func() string

func init() {
	nextString = newReadString(os.Stdin)
}

func main() {
	n := nextInt()
	for i := 1; ; i *= 2 {
		if i > n {
			fmt.Println(i / 2)
			break
		}
	}
}

func nextInt() (result int) {
	result, _ = strconv.Atoi(nextString())
	return
}

func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
		}
		return r.Text()
	}
}


Measured memory_bytes: 640
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
from itertools import accumulate

def main():
    n = int(input().strip())
    v = list(map(int, input().strip().split()))
    v.sort()
    s = [0] + list(accumulate(v))
    ans = 0
    for i in range(1, n):
        if 2 * s[i] >= v[i]:
            ans += 1
        else:
            ans = 0
    ans += 1
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 63984
n = int(input())
c, d = [], []
for i in range(n):
    a, b = [int(i) for i in input().split()]
    c.append(a)
    d.append(b)

count = 0

for i in range(0, n):
    if c[i] == d[i]:
        count += 1
    else:
        count = 0
    if count == 3:
        break

if count == 3:
    print('Yes')

else:
    print('No')


Measured memory_bytes: 9152
#include <bits/stdc++.h>
#define lli long long int
using namespace std;



int main(){
    int n;
    cin>>n;
    int arr[4] = {0};
    string s;
    for(int i=0; i<n; ++i){
        cin>>s;
        if(s== "AC") arr[0]++;
        else if(s== "WA") arr[1]++;
        else if(s== "TLE") arr[2]++;
        else arr[3]++;
    }
    cout<<"AC x "<<arr[0]<<endl;
    cout<<"WA x "<<arr[1]<<endl;
    cout<<"TLE x "<<arr[2]<<endl;
    cout<<"RE x "<<arr[3];
}


Measured memory_bytes: 3624
#include <bits/stdc++.h> 
using namespace std; 
typedef long long ll;
const int mxN=1e9;
const ll mod = 1e9+7;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	
    int n;
    cin>>n;

    vector<double> v(n);

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

    double dp[n+1][n+1];
    memset(dp,0,sizeof(dp));

    dp[0][0]=1;

    for(int i=1;i<=n;i++){
        for(int j=0;j<=i;j++){
            dp[i][j] = dp[i-1][j]*(1-v[i-1]);
            if(j>0) dp[i][j] += dp[i-1][j-1]*v[i-1];
        }
    }

    double ans = 0;
    for(int i=n/2+1;i<=n;i++) ans+=dp[n][i];

    cout<<setprecision(10)<<ans;
}

Measured memory_bytes: 74088
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>

using namespace std;

int main()
{
    int A, B;
    int ans = 0;
    cin >> A >> B;
    ans = max(ans, A + B);
    ans = max(ans, A + A - 1);
    ans = max(ans, B + B - 1);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 888
import java.util.Scanner;
public class Main {
    static int isPerfectNumber(int num) {
        int sum = 1;
        for(int i = 1; i <= num / 2; i++) {
            if(num % i == 0) {
               // sum += i;
            	++sum;
            }
        }
        return sum;
    }
	public void run() throws Exception {
		int anw = 0;

	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int cont = 0;
	    for(int i=1;i<=N;i++){
	    	anw = isPerfectNumber(i);
	    	if(anw == 8 && i%2==1){
	    		++cont;
	    	}
	    }
	    


	    System.out.println(cont);
	}
    public static void main(String[] args) throws Exception {
        new Main().run();
    }

}

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

A.append(K+A[0])

maxdist,maxindx = 0,0
for i,a in enumerate(A):
    dist = -a
    if i+1 == len(A):
        dist += K
    else:
        dist += A[i+1]
    if dist > maxdist:
        maxdist = dist
        maxindx = i
ans = 0
num=0
for x,a in enumerate(A):
    if num==len(A)-2:
        break
    if x == maxindx:
        continue
    num+=1
    if x+1 == len(A):
        ans += K-a
    else:
        ans += A[x+1]-a
print(ans)

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

int main(){
    int N;
    cin>>N;
    string S,T={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    cin>>S;
    for (int i=0;i<S.size();i++){
        bool flag = true;
        for(int j=0;j<T.size();j++){
            if (T.at(j)==S.at(i)&&flag==true){
                S.at(i)=T.at(j+N);
                flag = false;
            }
        }
    }
    cout<<S<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
struct nibab
{
    long long x,y,z;
} a[100005];
 
long long x,y,z,p[100005],q[100005],t,u[100005],v[100005],ans;
 
multiset <long long> s;
 
bool comp(nibab a, nibab b)
{
    return (a.x-a.y)>(b.x-b.y);
}
 
int main()
{
    cin >> x >> y >> z;
    for(int i=1;i<=x+y+z;i++)
        cin >> a[i].x >> a[i].y >> a[i].z;
    sort(a+1,a+x+y+z+1,comp);
    for(int i=1;i<=x+y+z;i++)
	{
        p[i]=a[i].x-a[i].z;
        q[i]=a[i].y-a[i].z;
    }
    for(int i=1;i<=x;i++)
	{
        s.insert(p[i]);
        p[i]+=p[i-1];
        u[i]=u[i-1]+a[i].z;
    }
    for(int i=x+1;i<=x+y+z;i++)
	{
        t=*(s.begin());
        if(p[i]<=t) p[i]=p[i-1];
        else s.erase(s.begin()),s.insert(p[i]),p[i]+=p[i-1]-t;
        u[i]=u[i-1]+a[i].z;
    }
    s.clear();
    for(int i=1;i<=y;i++)
	{
        s.insert(q[x+y+z-i+1]);
        q[x+y+z-i+1]+=q[x+y+z-i+2];
        v[x+y+z-i+1]=v[x+y+z-i+2]+a[x+y+z-i+1].z;
    }
    for(int i=y+1;i<=x+y+z;i++)
	{
        t=*(s.begin());
        if(q[x+y+z-i+1]<=t) q[x+y+z-i+1]=q[x+y+z-i+2];
        else s.erase(s.begin()),s.insert(q[x+y+z-i+1]),q[x+y+z-i+1]+=q[x+y+z-i+2]-t;
        v[x+y+z-i+1]=v[x+y+z-i+2]+a[x+y+z-i+1].z;
    }
    for(int i=x;i<=x+z;i++)
        ans=max(ans,u[i]+p[i]+v[i+1]+q[i+1]);
    cout << ans;
}

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

using namespace std;

#define all(x) x.begin(), x.end()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define reps(i, m, n) for (int i = m; i <= n; ++i)

using i64 = long long;
using pii = pair<i64, i64>;

template<class A, class B>inline bool chmax(A &a, const B &b){return b > a ? a = b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b < a ? a = b,1 : 0;}

constexpr int INF = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD = int(1e9) + 7;

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

  string a, b, c;
  cin >> a >> b >> c;
  cout << (a[a.length()-1] == b[0] && b[b.length()-1] == c[0] ? "YES" : "NO") << "\n";

  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
	try (Scanner sc = new Scanner(System.in)) {
	    double r = sc.nextDouble();
	    System.out.printf("%f %f\n", areaOfCircle(r), lengthOfCircumference(r));
	} catch (Exception e) {
	    e.printStackTrace();
	}
    }

    private static double areaOfCircle(Double r) {
	return Math.pow(r, 2) * Math.PI;
    }

    private static double lengthOfCircumference(Double r) {
	return 2 * Math.PI * r;
    }
}

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

#define ll long long
#define INF 99999999
#define rep(i,n) for(int i=0,temp=(int)(n);i<temp;++i) 
#define repi(i,start,end) for(int i=start,temp=(int)(end);i<end;++i)
#define rfor(v,x) for(const auto& x : v) //xは値を表す
#define all(x) (x).begin(),(x).end()
#define SORT(v, n) sort(v, v+n)
#define vsort(v) sort(v.begin(), v.end())
#define vfsort(v,lambda) sort(v.begin(),v.end(),lambda)
#define vint vector<int>
#define vvint vector<vector<int>>
#define vin(v) rep(i,v.size()) {cin >> v[i];}

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 (b<a) { a=b; return 1; } return 0; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int ctoi(char c) {return c-'0';}
//(lambda (x y) (< x y)) => [](int x, int y) -> int { return x<y; }

#define tri pair<string,pair<int,int>> 
bool cmp(tri x, tri y){
  if(x.first!=y.first) return x.first<y.first;
  return x.second.first > y.second.first;
}

int main(void){
  int n;cin >> n;
  vector<tri> sp(n);
  rep(i,n){ 
    cin >> sp[i].first >> sp[i].second.first;
    sp[i].second.second = i+1;
  }
  sort(all(sp),cmp);
  rep(i,n){
    cout << sp[i].second.second << endl;
  }


  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define sz(arr) (int)arr.size()
#define all(arr) arr.begin(), arr.end()

using namespace std;

void _cin() {}
template <class Head, class... Tail>
void _cin(Head&& head, Tail&&... tail) {
  cin >> head;
  _cin(forward<Tail>(tail)...);
}

#define Cin(T, ...) \
  T __VA_ARGS__;    \
  _cin(__VA_ARGS__)

int main() {
  Cin(int, a, b, t);

  cout << t / a * b << endl;

  return 0;
}

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

int cnt = 0;

void SelectionSort(int *A, int N) {
	for (int i = 0; i <= N - 1; ++i) {
		int minj = i;
		for (int j = i; j <= N - 1; ++j) {
			if (A[j] < A[minj]) minj = j;
		}
		if (A[i] != A[minj]) {
			int tmp;
			tmp = A[i];
			A[i] = A[minj];
			A[minj] = tmp;
			cnt++;
		}
	}
}

int main() {
	int N; cin >> N;
	int A[110];

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

	SelectionSort(A, N);

	for (int i = 0; i < N; ++i) {
		cout << A[i];
		if (i != N - 1) cout << " ";
	}
	cout << endl << cnt << endl;
}


Measured memory_bytes: 3096
#include <iostream>
#include <cstdio>
#define EPS 1e-9
using namespace std;

int main(){
	int n;
	cin >> n;
	for(int i = 0;i < n;i++){
		int a,b;
		scanf("%d:%d",&a,&b);
		double d1 = a * 30.0 + b * 0.5,d2 = b * 6.0;
		if(d2 < d1){
			double t = d1;
			d1 = d2;
			d2 = t;
		}
		if(d2 - d1 < 30.0 || d2 - d1 > 330.0) cout << "alert" << endl;
		else if(d2 - d1 < 90.0 || d2 - d1 > 270.0) cout << "warning" << endl;
		else cout << "safe" << endl;
	}
	return 0;
}

Measured memory_bytes: 3140
#include "bits/stdc++.h"
#define int long long
#define endl '\n'
using namespace std;

typedef long long ll;
#define prr(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << endl;
	err(++it, args...);
}

#define read(a) int a; cin >> a;
#define readb(a, b) int a, b; cin >> a >> b;
#define readc(a, b, c) int a, b, c; cin >> a >> b >> c;
#define readarr(a, n) int a[(n) + 1] = {}; FOR(i, 1, (n)) {cin >> a[i];}
#define readmat(a, n, m) int a[n + 1][m + 1] = {}; FOR(i, 1, n) {FOR(j, 1, m) cin >> a[i][j];}

#define pri(a) cout << a << endl;
#define print(a, n) FOR (i, 1, n) cout << a[i] << " "; cout << endl;
#define printv(a) for (int i: v) cout << i << " "; cout << endl;
#define printmat(a, n, m) FOR (i, 1, n) {FOR (j, 1, m) cout << a[i][j] << " "; cout << endl;} cout << endl;
#define all(v) v.begin(), v.end()
#define sz(v) (int)(v.size())
#define pb push_back
#define fi first
#define se second
#define vi vector <int>
#define pi pair <int, int>
#define vpi vector <pi>
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll N = 2e4 + 1;

signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	read(n);
	readarr(a, n);
	
	int mn = inf;
	FOR (i, 1, 100)
	{
	    int sum = 0;
	    FOR (j, 1, n) sum += (a[j] - i)*(a[j] - i);
	    mn = min(sum, mn);
	}
	
	cout << mn;
}












Measured memory_bytes: 256
X = int(input())
A = [i**5 for i in range(-118,120)]
A_posi = [i for i in range(-118,120)]
B = [i**5 for i in range(-119,119)]
B_posi = [i for i in range(-119,119)]
result = [0]*2
for i in range(len(A)):
    for j in range(len(B)):
        if A[i] -B[j] ==X:
            result[0] = A_posi[i]
            result[1] = B_posi[j]
            break
print(*result)


Measured memory_bytes: 9220
#include<iostream>
#include<vector>
#include<math.h>
#include<map>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
#define INF int(1e9)
#define MP make_pair
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
typedef pair<int, int> P;
typedef pair<pair<P, P>, P>PP;
typedef long long LL;
LL q, h, s, d, n, min2[4], min1[3], ans;
int main()
{
	cin >> q >> h >> s >> d >> n;
	min2[0] = q * 8;
	min2[1] = h * 4;
	min2[2] = s * 2;
	min2[3] = d;
	min1[0] = q * 4;
	min1[1] = h * 2;
	min1[2] = s;
	sort(min2, min2 + 4);
	sort(min1, min1 + 3);
	ans = n / 2 * min2[0];
	if (n % 2)
		ans += min1[0];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int,ii> iii;
typedef pair<int, iii> iiii;
typedef pair<double, ii> dii;
typedef long long ll;
typedef pair<ll, ii> lii;
const int INF = 1000000000;
const double EPS = 1e-9;
#define LSOne(S) (S & (-S))
int mods(int a, int b) { return (b + (a%b)) % b; }


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n, f = 0, a;

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a;
        if (a != i) f++;
    }

    if (f <= 2) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}

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

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            new Program().Solve(new ConsoleInput(Console.In, ' '));
        }

        public void Solve(ConsoleInput cin)
        {
            // 解答はココに書く
            var N = cin.ReadInt;
            var a = cin.ReadIntArray(N);
            Array.Sort(a);
            Array.Reverse(a);
            var alice = 0;
            var bob = 0;
            for (int i = 0; i < N; ++i)
            {
              if(i % 2 == 0) alice += a[i];
              else bob += a[i];
            }
            WriteLine(alice - bob);
        }
    }

    public class ConsoleInput
    {
        private readonly System.IO.TextReader _stream;
        private char _separator = ' ';
        private Queue<string> inputStream;
        public ConsoleInput(System.IO.TextReader stream, char separator = ' ')
        {
            this._separator = separator;
            this._stream = stream;
            inputStream = new Queue<string>();
        }
        public string Read
        {
            get
            {
                if (inputStream.Count != 0) return inputStream.Dequeue();
                string[] tmp = _stream.ReadLine().Split(_separator);
                for (int i = 0; i < tmp.Length; ++i)
                    inputStream.Enqueue(tmp[i]);
                return inputStream.Dequeue();
            }
        }
        public string ReadLine { get { return _stream.ReadLine(); }}
        public int ReadInt { get { return int.Parse(Read); }}
        public long ReadLong { get { return long.Parse(Read); }}
        public double ReadDouble { get { return double.Parse(Read); }}
        public string[] ReadStrArray(long N) { var ret = new string[N]; for (long i = 0; i < N; ++i) ret[i] = Read; return ret;}
        public int[] ReadIntArray(long N) { var ret = new int[N]; for (long i = 0; i < N; ++i) ret[i] = ReadInt; return ret;}
        public long[] ReadLongArray(long N) { var ret = new long[N]; for (long i = 0; i < N; ++i) ret[i] = ReadLong; return ret;}
    }
}


Measured memory_bytes: 11220
n=int(input())
x=1
X='abcdefghijklmnopqrstuvwxyz'
for i in range(1,100):
    if x<=n<x+26**i:
        n-=x
        cnt=i
        break
    else:
        x+=26**i
ans=''
for i in reversed(range(cnt)):
    ans+=X[n//(26**i)]
    n%=(26**i)
print(ans)

Measured memory_bytes: 61444
import java.util.Scanner;
class Main{
    public static void main(String[] args){
        String[] x = null;
        Scanner sc = new Scanner(System.in);
		String ip = sc.nextLine();
		x = ip.split(" ", 0);
		int a = Integer.parseInt(x[0]);
		int b = Integer.parseInt(x[1]);
		System.out.println(a*b+" "+(2*a+2*b));
    }
}


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

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

#define dump(x)  cerr << #x << " = " << (x) << endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back

int map[60][60]={};
bool visited[60][60]={false};
int w,h;

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

void dfs(int x,int y){
    if(x<0 || x>=w || y<0 || y>=h)return ;
    if(map[y][x]==0)return ;
    if(visited[y][x]==true)return ;
    
    visited[y][x]=true;
    rep(i,8){
        dfs(x+dx[i],y+dy[i]);
    }
}

int main(){
    while(cin>>w>>h){
        rep(i,60)rep(j,60)visited[i][j]=false;
        int c=0;
        if(w==0 || h==0)break;
        
        rep(i,h) rep(j,w) cin>>map[i][j];
        
        rep(i,h){
            rep(j,w){
                if(visited[i][j]==false && map[i][j]==1){
                    dfs(j,i);
                    c++;
                }
            }
        }
        cout<<c<<endl;
        
    }
    
    return 0;
}

Measured memory_bytes: 1248
def examC():
    ans = 0
    print(ans)
    return

def examD():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N = I()
    A = LI()
    D = {}
    l = -1; r = -1
    for i,a in enumerate(A):
        if a in D:
            l = D[a]
            r = i
            break
        D[a] = i
    #print(l,r)
    C = combination(N+2,mod)
    ans = [0]*(N+1)
    for i in range(1,N+2):
        ans[i-1] = (C.comb(N+1,i) - C.comb(l+N-r,i-1) + mod) % mod

    for v in ans:
        print(v)
    return

def examE():
    N, M = LI()
    A = LI()
    S = [0]*(M+2)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        S[a0+1] += 1
        S[a1] -= 1
        if a1<a0:
            S[0] += 1
    #print(S)
    for i in range(M):
        S[i+1] += S[i]
    for i in range(M+1):
        if S[i]<0:
            S[i] = 0
    D = defaultdict(int)
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = (a1 + M - a0) % M - 1
        D[a1] += cost
    start = 0
    for i in range(N-1):
        a0, a1 = A[i:i+2]
        cost = min(a1, (a1+M-a0)%M)
        start += cost
    #print(S)
    #print(D)
    #print(start)
    cost = start
    ans = start
    for i in range(1,M):
        cost += (D[i] - S[i])
        #print(cost)
        if ans>cost:
            ans = cost
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Measured memory_bytes: 34496
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
using ll=long long;
const int MOD=2019;
long long modpow(long long a, long long n, long long mod=2019) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}
int main(){
    string s;
    cin>>s;
    int n=s.size();
    vector<ll> k(s.size());
    for(int i=0;i<(int)s.size();i++){
        k[i]=s[i]-'0';
    }
    vector<ll> cnt(2019,0);
    cnt[0]=1;
    ll now=0;
    for(int i=n-1;i>0;i--){
        now+=k[i]*modpow(10,n-i-1)%MOD;
        now%=MOD;
        cnt[now]++;
    }
    now+=k[0]*modpow(10,n-1)%MOD;
    now%=MOD;
    ll ret=0;
    for(int i=0;i<n;i++){
        ret+=cnt[now];
        now-=k[i]*modpow(10,n-i-1)%MOD;
        now+=MOD;
        now%=MOD;
        cnt[now]--;
    }
    cout<<ret<<endl;
}


Measured memory_bytes: 5156
i=0
n,m=map(int,input().split())
arr=[]
while (i<n):
	a,b=map(int,input().split())
	arr.append([a,b])
	i+=1

arr.sort(key=lambda x:x[0])
s=0
money=0
i=0
left=m
while(left>0):
	if(arr[i][1]<left):
		left-=arr[i][1]
		money+=arr[i][1]*arr[i][0]
	else:
		money+=left*arr[i][0]
		left-=arr[i][1]
	i+=1

print(money)

Measured memory_bytes: 21224
var n,i,s:Longint;a:array[1..100000]of Integer;
begin
	read(n);
	for i:=1 to n do read(a[i]);
	s:=1;
	for i:=1 to n do begin
		s:=a[s];
		if s=2 then begin
			writeln(i);
			exit;
		end;
	end;
	writeln(-1);
end.


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define int         long long
#define ld          long double
#define endl        "\n"

const int mod = 998244353;


inline int add(int a, int b) { int res = a + b; if(res >= mod) res -= mod;  return res; }
inline int sub(int a, int b) { int res = a - b; if(res < 0) res += mod; return res;}
inline int mul(int a, int b) { return (a * b)%mod; }

const int N = 2e5+5;
int a[N];
int n, k;
vector<int> pos, neg, rpos, rneg;
int ps, ns, rps, rns;

int cnt(int x) {
    // CNT(X) -> # pairs with product < X
    int ans = 0;
    // For pos
    int l = 0, r = ps-1;
    while(l < r) {
        while(pos[l] * pos[r] >= x && l < r) {
            r--;
        }
        ans += max(0ll, (r-l));
        l++;
    }
    // For neg
    l = 0, r = ns-1;
    while(l < r) {
        while(rneg[l] * rneg[r] >= x && l < r) {
            r--;
        }
        ans += max(0ll, (r-l));
        l++;
    }
    // For pos-neg
    l = 0, r = ps-1;
    while(l < ns && r >= 0) {
        while(neg[l] * rpos[r] >= x && l < ns && r >= 0) {
            r--;
        }
        ans += r + 1;
        l++;
    }
    return ans;
}

void solve() {
    cin >> n >> k;
    for(int i=0; i<n; i++) {
        int x; cin >> x;
        if(x < 0) {
            neg.push_back(x); rneg.push_back(x);
        } else {
            pos.push_back(x); rpos.push_back(x);
        }
    }
    sort(neg.begin(), neg.end()); sort(rneg.rbegin(), rneg.rend());
    sort(pos.begin(), pos.end()); sort(rpos.rbegin(), rpos.rend());
    ps = pos.size(); ns = neg.size();
    int l = -1e18, r = 1e18;
    while(r - l > 1) {
        int mid = (l + r) / 2;
        int c = cnt(mid);
        if(c <= k-1) l = mid;
        else r = mid;
    }
    if(cnt(l) == k-1) cout << l << endl;
    else if(cnt(r) == k-1) cout << r << endl;
    else if(cnt(l) < k-1 && cnt(r) >= k) cout << l << endl;
}


signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(12);

    int T = 1;
    //cin >> T;

    while(T--) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 3720
import java.io.PrintWriter

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextList() = next().split(" ")
fun nextIntList() = nextList().map(String::toInt)
fun nextLongList() = nextList().map(String::toLong)
fun nextDoubleList() = nextList().map(String::toDouble)

val pw = PrintWriter(System.out)
fun print(s: Any = "") = pw.print(s)
fun println(s: Any = "") = pw.println(s)

fun main(args: Array<String>) {
    main()
    pw.flush()
}

fun main() {
    val N = nextInt()
    val A = nextLongList()
    val B = A.map { Math.abs(it) }
    val minus = A.count { it < 0 }
    if (minus % 2 == 0) {
        println(B.sum())
    } else {
        val min = B.min()!!
        println(B.sum() - min * 2)
    }
}

Measured memory_bytes: 61648
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

#define int long long
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define FST first
#define SND second
#define SZ(a) (signed)((a).size())
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;

const int MOD = 1000000007;
const char ENDL = '\n';

#define dump(x) cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")"  << " " << __FILE__ << endl;

signed main(void) {
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed, ios::floatfield);
    cout.precision(10);
    cin.tie(0);

    string s;
    cin >> s;

    VVI b(26,VI(s.length()+3,0));
    REP(i,s.length()){
        b[s[i]-'a'][i+1]++;
    }

    REP(i,26){
        FOR(j,1,s.length()){
            if(b[i][j]==1 && b[i][j+1]==1){
                cout << j << " " << j+1 << ENDL;
                return 0;
            }
            if(b[i][j]==1 && b[i][j+2]==1){
                cout << j << " " << j+2 << ENDL;
                return 0;
            }
        }
    }

    cout << -1 << " " << -1 << ENDL;
    
    return 0;
}

Measured memory_bytes: 21584
#include<bits/stdc++.h>
#define REP(i,n) for(int (i)=0 ;(i)<(n);(i)++)
#define REPR(i,n) for(int (i)=(n);(i)>=0;(i)--)
#define FOR(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define ALL(x) x.begin(),x.end()
#define REVERSE(x) reverse(x.begin(),x.end())
#define P pair<int,int>
typedef long long LL;
const int INF=1000000007;
using namespace std;
int gcd(int a,int b){
  if(b==0){return a;}
  else{
  return gcd(b,a%b);
  }
}
int n;
int a[100000];
int b[100000];

int main(){
  cin>>n;
  REP(i,n){
    cin>>a[i];
  }
  b[0]=a[0];
  FOR(i,1,n){
  b[i]=gcd(a[i],b[i-1]);
  }
  cout<<b[n-1];
}

Measured memory_bytes: 1024
import java.util.*;
// warm-up
public class Main {

	static void solve() {
		Scanner sc = new Scanner(System.in);
		String[] p = {"012","021","102","120","201","210"};
		int[] b = {sc.nextInt(),sc.nextInt(),sc.nextInt()};
		boolean ok = false;
		for (String a: p) {
			int i=Character.getNumericValue(a.charAt(0)),
			j=Character.getNumericValue(a.charAt(1)),
			k=Character.getNumericValue(a.charAt(2));
			if (b[i]+b[j]==b[k]) {
				ok=true; break;
			}
		}
		System.out.println(ok ? "Yes" : "No");
		sc.close();			
	}

	public static void main(String args[]) {
		solve();
	}

}

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


int main()
{
    int x, a, b;
    while(cin >>x>>a>>b)
    {
        if (a<b)
        {
            if (x < b - a)
                cout<<"dangerous"<<endl;
            else
                cout<<"safe"<<endl;
        }
        else
            cout<<"delicious"<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int a,b,c,max;
  cin >> a >> b >> c;
  if(a<b){
    max=b;
  }else{
    max=a;
  }
  if(c>max){
    max=c;
  }
 cout << a+b+c+max*9 << endl;
}
  


Measured memory_bytes: 256
n,m=map(int,input().split())

wa=[0]*n
ac=[0]*n

for i in range(m):
    a,b=input().split()
    a=int(a)-1
    if not ac[a]:
        if b=="WA":
            wa[a]+=1
        else:
            ac[a]=1
a=0
w=0
for i in range(n):
    if ac[i]:
        a+=1
        w+=wa[i]
print(a,w)

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

int main(){
    int a,b,k;
    cin >> a >> b >> k;
    for(int i=a;i<a+k;i++){
        if(i>b)break;
        cout << i << endl;
    }
    for(int i=b-k+1;i<=b;i++){
        if(i<a+k)continue;
        cout << i << endl;
    }
}

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

using namespace std;

const int N = 2505;
const int inf = 1e9;

vector< int> conn[N];
bool reachable[N];
int dist[N];

void dfs(int x) {
	reachable[x] = true;
	for (const int &y : conn[x]) {
		if (!reachable[y]) {
			dfs(y);
		}
	}
}


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

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

	vector< pair< pair< int, int>, int>> edges;

	for (int i = 1; i <= m; i ++) {
		int a, b, c;
		cin >> a >> b >> c;
		conn[b].emplace_back(a);
		edges.emplace_back(make_pair(a, b), p - c);
	}

	dfs(n);

	for (int i = 2; i <= n; i ++) dist[i] = inf;
	dist[1] = 0;

	for (int i = 1; i <= n; i ++) {
		for (const auto &e : edges) {
			int a = e.first.first, b = e.first.second, c = e.second;
			if (dist[a] != inf) {
				dist[b] = min(dist[b], dist[a] + c);
			}
		}
	}

	for (const auto &e : edges) {
		int a = e.first.first, b = e.first.second, c = e.second;
		if (dist[a] != inf && dist[b] > dist[a] + c) {
			if (reachable[b]) return cout << "-1", 0;
		}
	}

	cout << (dist[n] > 0 ? 0 : -dist[n]) << endl;
}

Measured memory_bytes: 640