akhauriyash/Code-Regression huggingface dataset:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

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

long long  a, b, n;

long long  f(long long  x) {
	return ((a * x) / b) - (a * (x / b));
}

int  main() {

	cin >> a >> b >> n;

	long long  x = min(n, b - 1);
	cout << f(x);

	return 0;
}

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

int main() {
    /* code */
    int n, s, s1, s2, s3;
    cin >> n;
    s = n / 1.08;
    s1 = s * 1.08;
    s2 = (s - 1) * 1.08;
    s3 = (s + 1) * 1.08;
    if(s1 == n) cout << s << endl;
    else if (s2 == n) cout << s - 1 << endl;
    else if (s3 == n) cout << s + 1 << endl;
    else puts(":\(");
    return 0;
}

Measured memory_bytes: 256
/***************************************************
 * Problem Name : B.cpp
 * Problem Link :
 * OJ           :
 * Verdict      : Trying
 * Date         : 2020-04-19
 * Problem Type :
 * Author Name  : Saikat Sharma
 * University   : CSE, MBSTU
 ***************************************************/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <cstdlib>
#include <deque>
#include <stack>
#include <bitset>
#include <cassert>
#include <map>
#include <set>
#include <cassert>
#include <iomanip>
#include <random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;

#define __FastIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define __FileRead freopen ("input.txt", "r", stdin)
#define __FileWrite freopen ("output.txt", "w", stdout)
#define SET(a,v) memset(a,v,sizeof(a))
#define SZ(v) (int)v.size()
#define pii pair<int,int>
#define pil pair <int, ll>
#define pli pair <ll, int>
#define pll pair <ll, ll>
#define debug cout <<"######\n"
#define debug1(x) cout <<"### " << x << " ###\n"
#define debug2(x,y) cout <<"# " << x <<" : "<< y <<" #\n"
#define nl cout << "\n";
#define sp cout << " ";
#define sl(n) scanf("%lld", &n)
#define sf(n) scanf("%lf", &n)
#define si(n) scanf("%d", &n)
#define ss(n) scanf("%s", n)
#define pf(n) scanf("%d", n)
#define pfl(n) scanf("%lld", n)
#define all(v) v.begin(), v.end()
#define rall(v) v.begin(), v.end()
#define srt(v) sort(v.begin(), v.end())
#define r_srt(v) sort(v.rbegin(), v.rend())
#define rev(v) reverse(v.rbegin(), v.rend())
#define Sqr(x) ((x)*(x))
#define Mod(x, m) ((((x) % (m)) + (m)) % (m))
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define pb push_back
#define mk make_pair
#define MAX 100005
#define INF 1000000009
#define MOD 1000000007

template<class T>
using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>;
template<typename T>
using ordered_set  = tree<T, null_type, less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

template <typename T> string toString ( T Number ) {
    stringstream ss;
    ss << Number;
    return ss.str();
}
template<typename T> int toInt (T str) {
    stringstream ss;
    ss << str;
    int num;
    ss >> num;
    return num;
}
ll lcm ( ll a, ll b ) {
    return ( a / __gcd ( a, b ) ) * b;
}
/************************************ Code Start Here ******************************************************/
int main () {
    //~ __FastIO;
    //~ cout << setprecision (10) << fixed;
    ll n, m;
    cin >> n >> m;
    ll sum = 0;

    for (int i = 0; i < m; i++) {
        ll x;
        cin >> x;
        sum += x;
    }

    if (n - sum >= 0) {
        cout << n - sum << "\n";

    } else {
        cout << -1 << "\n";
    }

    return 0;
}


Measured memory_bytes: 3624
module.exports=function(e){var r={};function t(n){if(r[n])return r[n].exports;var o=r[n]={i:n,l:!1,exports:{}};return e[n].call(o.exports,o,o.exports,t),o.l=!0,o.exports}return t.m=e,t.c=r,t.d=function(e,r,n){t.o(e,r)||Object.defineProperty(e,r,{enumerable:!0,get:n})},t.r=function(e){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(e,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(e,"__esModule",{value:!0})},t.t=function(e,r){if(1&r&&(e=t(e)),8&r)return e;if(4&r&&"object"==typeof e&&e&&e.__esModule)return e;var n=Object.create(null);if(t.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:e}),2&r&&"string"!=typeof e)for(var o in e)t.d(n,o,function(r){return e[r]}.bind(null,o));return n},t.n=function(e){var r=e&&e.__esModule?function(){return e.default}:function(){return e};return t.d(r,"a",r),r},t.o=function(e,r){return Object.prototype.hasOwnProperty.call(e,r)},t.p="",t(t.s=0)}([function(e,r,t){t(1)(t(2).readFileSync("/dev/stdin","UTF-8"))},function(e,r){e.exports=function(e){var r=e.split("\n"),t=Number(r[0]),n=r[1].split(""),o=new Array(t);o[0]="E"==n[0]?1:0;for(var u=1;u<t;u++)o[u]=o[u-1],"E"==n[u]&&(o[u]+=1);var i=new Array(t);i[t-1]="W"==n[t-1]?1:0;for(var f=t-2;f>=0;f--)i[f]=i[f+1],"W"==n[f]&&(i[f]+=1);for(var l=0,a=0;a<t;a++)l<o[a]+i[a]&&(l=o[a]+i[a]);console.log(t-l)}},function(e,r){e.exports=require("fs")}]);

Measured memory_bytes: 15308
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<map>
using namespace std;

int a, b, c;
int main()
{
	scanf("%d%d%d", &a, &b, &c);
	for(int i = 1; i < 1000000; i++)
	{
		if(((i * b) + c) % a == 0)  
    	{
    		printf("YES\n");
    		return 0;
		}
	}
	printf("NO\n");
}


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

int main() {
	int N;
	cin >> N;
	int a[100000];
	for (int i = 0; i < N; i++) cin >> a[i];
	bool log[100000]; // 光ったことがあるかどうか
	for (int i = 0; i < N; i++) log[i] = false;

	bool is_possible = true;
	int counter = 0, now_light = 1; // 初期状態
	while (is_possible) {

		if (log[now_light - 1]) {
			counter = -1;
			break;
		}
		log[now_light-1] = true; // 状態を記録
		
		now_light = a[now_light-1]; // 状態の更新
		counter++;
		if (now_light == 2) break; // 2になった終了
	}
	cout << counter << endl;
	return 0;
}

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


int main() {
    int N, M, C;
    cin >> N >> M >> C;
    vector<int> B(M);
    vector<vector<int>> A(N, vector<int> (M));
    rep(i,M) cin >> B.at(i);
    rep(i,N) rep(j,M) cin >> A.at(i).at(j);

    int ans = 0;
    rep(i,N) {
        int sum = 0;
        rep(j,M) sum += A.at(i).at(j) * B.at(j);
        if (sum + C > 0) ++ans;
    }
    cout << ans << endl;
}



Measured memory_bytes: 3632
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int main()
{
  while (1) {
    int n;
    cin >> n;
    if (n == 0) break;
    double ave = 0.0, sum = 0.0, a;
    int s[1000];
    for (int i=0; i<n; i++) {
      cin >> s[i];
      ave += s[i];
    }
    ave /= n;
    for (int i=0; i<n; i++) sum += (s[i]-ave) * (s[i]-ave);
    a = sqrt(sum/n);
    printf("%f\n", a);
  }
  return 0;
}



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

using namespace std;
using ll = long long;

#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define REP(i,n) FOR(i, 0, n)
#define FORR(i,n,a) for(int i=(n); i>=(a); i--)
#define REPR(i,n) FOR(i, n, 0)

#define ALL(o) (o).begin(), (o).end()

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
template<class T> using PQ = priority_queue<T>;
template<class T> using PQR = priority_queue<T, vector<T>, greater<T> >;

const ll MOD = 1000000007;


int main() {
	int n,t;
	cin >> n;
	V<int> v;
	REP(i,n) {
		cin >> t;
		v.push_back(t);
	}

	V<int> w;
	w.push_back(0);
	FOR(i,0,n-1) {
		w.push_back((v[i]-w[i]/2)*2);
	}
	cout << endl;

	int last = (v[n-1]+w[n-1]/2);
	V<int> ans;

	ans.push_back((v[n-1]-last/2)*2);
	cout << ans[0];

	FOR(i,0,n-1) {
		ans.push_back((v[i]-ans[i]/2)*2);
		cout << " " << ans[i+1];
	}
	cout << endl;
}



Measured memory_bytes: 2680
// Ver19.03
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define INF 1 << 29
#define LLINF 4545454545454545454
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
int upll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? -1 : *(ll *)a > *(ll *)b ? 1 : 0; }
int downll(const void *a, const void *b) { return *(ll *)a < *(ll *)b ? 1 : *(ll *)a > *(ll *)b ? -1 : 0; }
void sortup(ll *a, int n) { qsort(a, n, sizeof(ll), upll); }
void sortdown(ll *a, int n) { qsort(a, n, sizeof(ll), downll); }

int main()
{
  double t, x;
  scanf("%lf%lf", &t, &x);
  printf("%lf\n", t / x);
  return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1e18

int main() {
    ll N, K;
    cin >> N >> K;
    vector<vector<int>> t(60, vector<int>(N));
    for (int i = 0; i < N; i++) cin >> t[0][i], t[0][i]--;
    for (int k = 0; k < 59; k++)
        for (int i = 0; i < N; i++) {
            t[k + 1][i] = t[k][t[k][i]];
        }
    int ans = 0;
    for (ll i = 59; i >= 0; i--) {
        if (K & (1ll << i)) {
            ans = t[i][ans];
        }
    }
    cout << ans + 1 << endl;
    return 0;
}

Measured memory_bytes: 51044
<?php
$arr = array();
for($i = 0; $i < 10; $i++){
    fscanf(STDIN, "%d", $arr[$i]);
}

rsort($arr);

$count = 0;
foreach($arr as $row){
    echo $row."\n";
    $count++;
    if($count >= 3){
        break;
    }
}

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

namespace easy_Atcoder
{
    class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            Dictionary<string,int> dict = new Dictionary<string,int>();
            var dictMax = 0;
            for(int i = 0 ; i<N;i++){
                string S = Console.ReadLine();
                if(dict.ContainsKey(S)){
                    dict[S]++;
                }else{
                    dict.Add(S,1);
                }
                dictMax = Math.Max(dictMax,dict[S]);
            }
            // int dictMax =dict.Values.Max();
            // IOrderedEnumerable<KeyValuePair<string,int>> sorted =  dict.OrderBy(x=>x.Key);
            var ans = new List<string>();
            foreach(var s in dict){
                if(s.Value == dictMax){
                    ans.Add(s.Key);
                }
            }
            ans.Sort(StringComparer.Ordinal);
            Console.WriteLine(string.Join("\n",ans));
        }   
            // float[] ABN = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // long[] NK = Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // long N = NK[0];
            // long K = NK[1];
            // long K = long.Parse(Console.ReadLine());
            // int[] abc = Array.ConvertAll(Console.ReadLine().Split(),int.Parse);
            // string S = Console.ReadLine();
            // int x = int.Parse(Console.ReadLine());
            // int b = int.Parse(Console.ReadLine());
            // int N = int.Parse(Console.ReadLine());
            // float N = float.Parse(Console.ReadLine());
            // string c = Console.ReadLine();
            // string B = Console.ReadLine();
            // string[] s = Console.ReadLine().Split();
            // var s = (new string[] { Console.ReadLine(), Console.ReadLine(), Console.ReadLine() }).Select(float.Parse);
            // float[] a = Array.ConvertAll(Console.ReadLine().Split(),float.Parse);
            // var X = Console.ReadLine();
            // int[,] abcd = new int[NMQ[2],4];
            // int[] A = new int[NMQ[0]];
            // int[] A_num = new int[NMQ[0]];
            // long[] s=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            // var hs=new Dictionary<long,long>();
            // for(int i=0;i<s[0];i++){
            //     long[] q=Array.ConvertAll(Console.ReadLine().Split(),long.Parse);
            //     if(hs.ContainsKey(q[0])){hs[q[0]]+=q[1];}
            //     else{hs.Add(q[0],q[1]);}
            // }
        
        // //最小公倍数
        // static long Lcm(long a, long b)
        // {
        //     return a/Gcd(a,b)*b;
        // }

        // //最大公約数
        // static long Gcd(long m, long n)
        // {
        //     if(n==0)return m;
        //     return Gcd(n,m%n);
        // }
    }
}

Measured memory_bytes: 49912
import Data.List

solve ct n [] = ct 
solve ct n (x:xs) = 
  if n == x then ct 
  else solve (ct+1) n xs

main = do
  n <- readLn
  p <- map read . words <$> getLine :: IO [Int]
  q <- map read . words <$> getLine :: IO [Int]
  let nl = [1..n]
  let pidx = solve 1 p (sort $ permutations nl)
  let qidx = solve 1 q (sort $ permutations nl)

  print $ abs $ pidx-qidx



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

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

    int n, c;
    cin >> n >> c;

    int d[30][30];
    for (int x = 0; x < c; x++) {
        for (int y = 0; y < c; y++) {
            cin >> d[x][y];
        }
    }

    int k[3][30] = {};
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int x;
            cin >> x;
            x--;

            int r = (i + j) % 3;
            k[r][x]++;
        }
    }

    int s[3][30] = {};
    for (int r = 0; r < 3; r++) {
        for (int x = 0; x < c; x++) {
            for (int y = 0; y < c; y++) {
                s[r][y] += d[x][y] * k[r][x];
            }
        }
    }

    int ans = 1 << 30;
    for (int i = 0; i < c; i++) {
        for (int j = 0; j < c; j++) {
            if (j == i) continue;
            for (int k = 0; k < c; k++) {
                if (k == i || k == j) continue;
                ans = min(ans, s[0][i] + s[1][j] + s[2][k]);
            }
        }
    }

    cout << ans << endl;

    return 0;
}

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

const int PMAX = 10000000;

template <typename T>
class PersistentSegmentTree {
	struct node {
		T val;
		node *l, *r;
		node() {}
		node(T val) : val(val), l(nullptr), r(nullptr) {}
		void init(T v, node *left, node *right) {
			val = v;
			l = left;
			r = right;
		}
	};
	using func_t = function<T(T, T)>;
	const int n;
	const T id;
	func_t merge;
	vector<node> pool;
	int it;
	vector<node*> root;
	int size(int n) {
		int res = 1;
		while (res < n) res <<= 1;
		return res;
	}
	node *new_node(int val = 0, node *l = nullptr, node *r = nullptr) {
		pool[it].init(val, l, r);
		return &pool[it++];
	}
	node *fix(node *x, int p, T val, int lb, int ub) {
		if (p < lb || ub <= p) return x;
		if (lb + 1 == ub) return new_node(val);
		int c = (lb + ub) / 2;
		auto nl = fix(x->l, p, val, lb, c);
		auto nr = fix(x->r, p, val, c, ub);
		return new_node(merge(nl->val, nr->val), nl, nr);
	}
	T sub(node *x, int l, int r, int lb, int ub) {
		if (ub <= l || r <= lb) return id;
		if (l <= lb && ub <= r) return x->val;
		int c = (lb + ub) / 2;
		return merge(sub(x->l, l, r, lb, c), sub(x->r, l, r, c, ub));
	}
public:
	PersistentSegmentTree(int n_, T id_, func_t merge_) : n(size(n_)), id(id_), merge(merge_), pool(PMAX) {
		for (int i = 1; i < n * 2; i++) {
			pool[i - 1].init(id, i < n ? &(pool[i * 2 - 1]) : nullptr, i < n ? &(pool[i * 2]) : nullptr);
		}
		it = n * 2 - 1;
		root.push_back(&pool[0]);
	}
	void update(int p, T val, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		root.push_back(fix(root[rt], p, val, 0, n));
	}
	T find(int l, int r, int rt = -1) {
		if (rt == -1) rt = root.size() - 1;
		assert(0 <= rt && rt < (int)root.size());
		return sub(root[rt], l, r + 1, 0, n);
	}
	int getversion() {
		return root.size() - 1;
	}
};

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n, q, com, x, y;
	cin >> n >> q;
	PersistentSegmentTree<int> st(n, 0, [](int l, int r) { return l + r; });
	while (q--) {
		cin >> com >> x >> y;
		if (com) {
			printf("%d\n", st.find(x - 1, y - 1));
		}
		else {
			st.update(x - 1, st.find(x - 1, x - 1) + y);
		}
	}
	return 0;
}

Measured memory_bytes: 36508
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long xor=0;
        for(int i=0;i<n;i++){
            xor^=sc.nextInt();
        }
        if(xor==0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


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

#define print cout <<
#define printl(s) cout << s << endl;
#define rep(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;

const ll modseed = pow(10,9) + 7;

template <typename T>
vector<T> getValues(int num){
    vector<T> values(num);
    for(int i=0;i<num;i++){
        cin >> values.at(i);
    }
    return values;
}

bool isAGCT(char c){
  if(c=='A' || c =='G' || c =='C' || c == 'T'){
    return true;
  }
  return false;
}

int main(){
    string S;
    cin >> S;
    int maxsize = 0;
    int size = 0;
    rep(i,S.size()){
      if(isAGCT(S.at(i))){
        size++;
        if(size > maxsize){
          maxsize = size;
        }
      }else{
        size = 0;
      }
    }
    printl(maxsize);
}


Measured memory_bytes: 3620
import sys
H_W = list(map(int,input().split()))
H = H_W[0]
W = H_W[1]
b = [[0 for i in range(W)] for j in range(H)]
a = [[str(c) for c in l.strip()] for l in sys.stdin]

# .を0に, #を1にした新しい配列bを作る
for i in range(H):
    for j in range(W):
        if a[i][j] == '#':
            b[i][j] = 1

# 列と行ごとにすべて0のものを探す
w = [0] * W
h = [0] * H
for i in range(H):
    for j in range(W):
        h[i] = h[i] + b[i][j]
        w[j] = w[j] + b[i][j]

#print(h)
#print(w)
# 全ての要素が0の列と行を削除する
i = 0
c = 0
j = 0
for i in range(H):
    if h[i] == 0:
        del a[j]
        H = H - 1
        j = j - 1
    j = j + 1
#print(a)

k = 0
for i in range(W):
    if w[i] == 0:
        for j in range(H):
            del a[j][k]
        W = W - 1
        k = k - 1
    k = k + 1
#print(a)
# 答え
for i in range(H):
    flag = 0
    for j in range(W):
        if flag == 0:
            ans = a[i][j]
            flag = 1
        else:
            ans = ans + a[i][j]
    print(ans)
    

Measured memory_bytes: 3316
#include<iostream>
#include<string>

using namespace std;

const static int HEIGHT_MAX = 50;
const static int WIDTH_MAX = 50;


int main(){

	int height;
	int width;
	int semi[HEIGHT_MAX][WIDTH_MAX];

	cin >> height >> width;

	for (int i = 0; i < height; ++i){
		string s;
		cin >> s;
		for (int j = 0; j < s.length(); ++j){
			semi[i][j] = (int)s[j] - 48;
		}

	}

	for (int i = 0; i < width; ++i){
		if (i != 0){
			semi[0][i] += semi[0][i - 1];
		}
	}

	for (int i = 0; i < height; ++i){
		if (i != 0){
			semi[i][0] += semi[i - 1][0];
		}
	}

	for (int i = 1; i < height; ++i){
		for (int j = 1; j < width; ++j){
			// いっこ上
			int UE = semi[i - 1][j];
			int HIDARI = semi[i][j - 1];
			semi[i][j] += (UE >= HIDARI) ? HIDARI : UE;
			
		}
	}


	cout << semi[height - 1][width - 1] << endl;


	return 0;

}

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

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

  bool flag = true;
  int c = 0;
  while(flag){
    for(int i = 0; i < n; i++){
      if(a[i] % 2 == 0)
        a[i] /= 2;
      else
        flag = false;
    }

    if(flag == false)
      break;
    c++;
  }
  cout << c << endl;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-


from sys import stdin



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


# read data for n sequences.
n = stdin.readline()
N = int(n)
n = stdin.readline()
S = str(n)
n = stdin.readline()
K = int(n)
#data = [int(stdin.readline().rstrip()) for _ in range(n)]
key = S[K-1]

out=[]
for i,l in enumerate(S):
	if i < N:
		
		if l != key:
			out.append("*")
		elif l =="\n":
			x=1
		else:
			out.append(l)
out1=''
for o in out:
	out1+=o
print(out1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  int H , N;
  cin >> H >> N;
  vector<int> vec(N);
  for(int i = 0; i < N; i++){
    cin >> vec[i];
  }
  int sum = 0;
  for(int i = 0; i < N; i++){
    sum = sum + vec[i];
  }
  if (H - sum > 0){
    cout << "No";
  }
  if (H - sum <= 0){
    cout << "Yes";
  }
}

Measured memory_bytes: 640
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, X = lr()
burger = [0] * (N+1)
burger[0] = 1
patty = [0] * (N+1)
patty[0] = 1
for i in range(1, N+1):
    burger[i] = burger[i-1] * 2 + 3
    patty[i] = patty[i-1] * 2 + 1

def solve(N, take):
    """レベルNバーガーのtake層目までのpattyの数を返す"""
    if N == 0:
        return min(1, take)
    mid = burger[N] // 2 + 1
    if take == mid:
        return patty[N-1] + 1
    if take > mid:
        return patty[N-1] + 1 + solve(N-1, take-mid)
    else:
        return solve(N-1, max(0, take-1))

answer = solve(N, X)
print(answer)
# 31

Measured memory_bytes: 3064
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
using namespace std;
using Int = int_fast64_t;

Int a, b;

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> a >> b;
	cout << max<Int>(a - 2*b, 0) << "\n";
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define mod 1000000007
using namespace std;
ll power(ll x,ll n)
{
	ll res =1;
	while(n>0)
	{
		if(n%2==1)
	res=res*x;
	x=x*x;
	n=n/2;
	}
	return res;
	
}

int main(){

ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s,k;
    cin>>s;
    int q,flag=0;
    cin>>q;
    while(q--)
    {
    	int t;
    	cin>>t;
    	if(t==1)
    	{
    		if(flag==0)
    		flag=1;
    		else
    		flag=0;
		}
		else
		{
			int x;
			char c;
			cin>>x>>c;
			
			
			if(x==1)
			{
				if(flag==0)
				{
					k.push_back(c);
				}
				else
				{
					s.push_back(c);
				}
			}
			else
			{
				if(flag==0)
				{
					s.push_back(c);
				}
				else
				{
					k.push_back(c);
				}
			}
		}
	}
	for(int i=0;i<k.length()/2;i++)
	{
		swap(k[i],k[k.length()-1-i]);
	}
	s=k+s;
	if(flag==0)
	cout<<s;
	else
	{
		for(int i=s.length()-1;i>=0;i--)
		cout<<s[i];
	}
	
}


Measured memory_bytes: 1196
#input of int(split by space)
def get_i()
  return gets.chomp.split(" ").map(&:to_i)
end
#input of float(split by space)
def get_f()
  return gets.chomp.split(" ").map(&:to_f)
end
#input of string(split by space)
def get()
  return gets.chomp.split(" ")
end
#input of string(split per one character)
def get_nsp()
  return gets.chomp.split("")
end
#yes or no decision
def yn_judge(bool,y="Yes",n="No")
  return bool ? y : n 
end
#create of array
def array(size1,init=nil,size2=-1)
  if size2==-1
      return Array.new(size1){init}
  else
      return Array.new(size2){Array.new(size1){init}}
  end
end

def max(a,b)
    return a>b ? a : b
end

def min(a,b)
    return a>b ? b : a
end

INF=Float::INFINITY

N=gets.to_i
a=array(N)
N.times do|i|
    a[i]=gets.to_i
end
if N==1
    puts a[0]/2
    exit
end
ans=0
(N-1).times do|i|
  val=(a[i]+a[i+1])/2
  #p val
  ans+=val
  val*=2
  if val>a[i]
      val-=a[i]
      a[i]=0
  else
      a[i]-=val
      val=0
  end
  a[i+1]-=val
end
puts ans

Measured memory_bytes: 15112
#include<iostream>
using namespace std;
#define MAX 13

int main()
{
	int n,i,x;
	int S[MAX]={0},H[MAX]={0},C[MAX]={0},D[MAX]={0};
	char str;

	cin >> n;
	for(i=0;i<n;i++)
	{
		cin >> str >> x;

		if(str=='H') H[x-1] = 1;
		if(str=='S') S[x-1] = 1;
		if(str=='C') C[x-1] = 1;
		if(str=='D') D[x-1] = 1;
	}

	for(i=0;i<MAX;i++)
	{
		if(S[i]==0) cout << "S " << i+1 << endl ; 
	}

	for(i=0;i<MAX;i++)
	{
		if(H[i]==0) cout << "H " << i+1 << endl ; 
	}
	for(i=0;i<MAX;i++)
	{
		if(C[i]==0) cout << "C " << i+1 << endl ; 
	}
	for(i=0;i<MAX;i++)
	{
		if(D[i]==0) cout << "D " << i+1 << endl ; 
	}

	return 0;
}

Measured memory_bytes: 1160
from collections import deque
from collections import Counter
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
#pypyではscipy, numpyは使えない
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
#from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
#import numpy as np
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n = int(readline())
  d = list(map(int, readline().split()))
  d.sort()
  mid = n//2
  print(d[mid]-d[mid-1])
  
  
  
if __name__ == '__main__':
  main()

Measured memory_bytes: 14424
#include <cstdio>
#include <algorithm>
typedef long long ll;

int n,L,t,v,l=1,r=0;
ll qv[500005],Aw;
double qt[500005],Ns;

int main()
{
    //freopen("in.txt","r",stdin);
    for(scanf("%d%d",&n,&L);n--;)
    {
        scanf("%d%d",&t,&v);
        while(Aw+v>L)
        {
            ll Po=std::min(qv[l],Aw+v-L);
            qv[l]-=Po,Aw-=Po,Ns-=qt[l]*Po;
            if(!qv[l])++l;
        }
        Aw+=v,Ns+=(ll)t*v,qv[++r]=v,qt[r]=t;
        for(;l<r&&qt[r-1]>qt[r];--r)qt[r-1]=(qt[r-1]*qv[r-1]+qt[r]*qv[r])/(qv[r-1]+qv[r]),qv[r-1]+=qv[r];
        printf("%.7f\n",Ns/L);
    }
    return 0;
}


Measured memory_bytes: 16768
#define MOD_TYPE 1

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;

#include <boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
using multiInt = boost::multiprecision::cpp_int;
using lld = boost::multiprecision::cpp_dec_float_100;

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
//constexpr ll MOD = 1;
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr double PI = acos(-1.0);
constexpr double EPS = 1e-10;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define REPI(i, m, n) for (int i = m; i < (int)(n); ++i)
#define repi(i, n) REPI(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

inline void init_main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(30) << setiosflags(ios::fixed);
}
template <typename T>
inline bool chmin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
inline bool chmax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}
inline ll CEIL(ll a, ll b)
{
  return (a + b - 1) / b;
}
template <typename A, size_t N, typename T>
inline void Fill(A (&array)[N], const T &val)
{
  fill((T *)array, (T *)(array + N), val);
}
template <typename T, typename U>
constexpr ostream &operator<<(ostream &os, pair<T, U> &p) noexcept
{
  os << p.first << " " << p.second;
  return os;
}
#pragma endregion

void solve()
{
  ll n;
  cin >> n;
  if (n == 1)
  {
    cout << 0 << "\n";
    return;
  }
  ll ans = 0;

  for (ll i = 2; i * i <= n; i++)
  {
    if (n % i != 0)
      continue;
    ll t = 0;
    while (n % i == 0)
    {
      t++;
      n /= i;
    }

    ll u = 0, add = 1, cnt = 0;
    while (u <= t)
    {
      u += add;
      add++;
      cnt++;
    }
    ans += cnt - 1;
  }
  if (n > 1)
    ans++;
  cout << ans << "\n";
}

int main()
{
  init_main();

  solve();

  return 0;
}

Measured memory_bytes: 3652
#include <stdio.h>
int main(){
    int a,b,c,i,d;
    a=b=c=d=0;
    scanf("%d %d %d",&a,&b,&c);
    for(i=a;i<=b;i++){
        if(c%i==0){
            d++;
        }
    }
    printf("%d\n",d);
    return 0;
}

Measured memory_bytes: 1852
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

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

const ll mod =  1000000007;  //出力は (ans % mod + mod) % mod  (負の剰余を正にする)
const int inf = 1e9;
const long long INF = 1LL << 60;   // INF = 11

ll cnt[100010];
int main()
{
    ll n; cin >> n;
    ll a[n];
    
    rep(i,n){
        cin >> a[i];
        cnt[a[i]]++;
    }
    ll sum = 0;
    rep(i,n) sum += a[i];
    int q; cin >> q;
    rep(i,q){
        int b,c; cin >> b >> c;
        sum += (c-b)*cnt[b];
        cout << sum << endl;
        cnt[c] += cnt[b];
        cnt[b] = 0;
    }

}

      

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

int main() {
  int N, K;
  cin >> N >> K;
  vector<int> p(N);
  for(int i = 0; i < N; i++) {
    cin >> p.at(i);
  }
   sort(p.begin(), p.end()); 
  int cnt = 0;
  for(int i = 0; i < K; i++) {
    cnt += p.at(i);
  }
  
  cout << cnt << endl;
}


Measured memory_bytes: 3632
n, m = map(int, input().split())
h = list(map(int, input().split()))
ans = [1 for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if h[a] >= h[b]:
    ans[b] = 0
  if h[b] >= h[a]:
    ans[a] = 0
    
print (sum(ans))

Measured memory_bytes: 19900
import sys
sys.setrecursionlimit(10**5+1)
n,m = map(int,input().split())
tree = [[] for i in range(n)]
tree_rev = [[] for i in range(n)]
for i in range(n-1+m):
    x, y = map(int, input().split())
    tree[x-1].append(y-1)
    tree_rev[y-1].append(x-1)
# topological_sorted_n : トポロジカル順序に並んだリスト
topological_sorted_n = []
visited = [False]*n

def topological_sort(i):
    if not visited[i]:
        visited[i] = True
        for next_i in tree[i]:
            topological_sort(next_i)
        topological_sorted_n.append(i)

for i in range(n):
    topological_sort(i)
topological_sorted_n = topological_sorted_n[::-1]

memo = {}
for i in range(n):
    memo[topological_sorted_n[i]] = i

for i in range(n):
    index = -1
    ans = 0
    for pos in tree_rev[i]:
        if index < memo[pos]:
            index = memo[pos]
            ans = pos+1
    print(ans)

Measured memory_bytes: 90032
# -*- coding: utf-8 -*-

def solve(a, b, c):
    A = []
    A.append(a)
    A.append(b)
    A.append(c)
    print(len(set(A)))
                
if __name__ == '__main__':
    a, b, c = map(int, input().split())

    solve(a, b, c)

Measured memory_bytes: 2940
import java.util.*;

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

class Solver {

    public void run() {
        Scanner sc = new Scanner(System.in);
        char[] S = sc.next().toCharArray();


        int f = S[0] - '0';

        int ans = 0;
        if (S.length == 1) {
            ans = f;
        } else {
            f--;
            ans = (S.length - 1) * 9 + f;
        }

        int sum = 0;
        for (int i = 0; i < S.length; i++) {
            sum += S[i] - '0';
        }
        
        System.out.println(Math.max(ans, sum));


        return;
    }

}

Measured memory_bytes: 23892
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <tuple>
#define FOR0(var, max) for (ui (var) = 0; (var) < (max); ++(var))
#define FOR_INV(var, min, max) for (ui (var) = (max) - 1; (var) + 1 > (min); --(var))
#define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++)
#define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++)

using namespace std;

using uc = unsigned char;
using ui = unsigned int;
using ul = unsigned long long int;

const static ul NMAX = 100000;
const static ul AMAX = 1000000000;

static ul N;
static ul Ai[NMAX + 1];
static ul Fi[NMAX + 1];
static ul Li[NMAX + 1];

ul gcd(ul a, ul b) {
  while (b) {
    ul t = a % b;
    a = b;
    b = t;
  }
  return a;
}

void solve(void) {
  ul res = 0;
  Fi[0] = 0;
  Li[N] = 0;
  FOR0(i, N) {
    Fi[i + 1] = gcd(Fi[i], Ai[i]);
    Li[N - i - 1] = gcd(Li[N - i], Ai[N - i]);
  }
  FOR0(_i, N) {
    ui i = _i + 1;
    res = max(res, gcd(Fi[i], Li[i]));
  }
  cout << res << endl;
}

int main(void) {
  cin >> N;
  Ai[0] = 0;
  FOR0(i, N) {
    cin >> Ai[i + 1];
  }
  solve();
  return 0;
}

Measured memory_bytes: 2560
import java.util.Scanner;


public class Main {
	
	static int count(int index, int mod, int[] a) {
		if (index == a.length)
			return mod == 0 ? 1: 0;
		int ret = 0;
		for(int i = -1; i <= 1; i++)
			ret += count(index + 1, (mod * (a[index] + i)) % 2, a);
		return ret;
	}
	
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		for(int i = 0; i < N; i++)
			a[i] = sc.nextInt();
		System.out.println(count(0, 1, a));
		sc.close();
	}

}


Measured memory_bytes: 22612
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String[][] ab = new String[n][3];
        for (int i = 0; i < n; i++) {
            ab[i][0] = sc.next();
            ab[i][1] = sc.next();
            ab[i][2] = String.valueOf(i + 1);
        }
        
        Arrays.sort(ab, (a, b) -> Integer.compare(Integer.parseInt(b[1]), Integer.parseInt(a[1])));
        Arrays.sort(ab, (a, b) -> a[0].compareTo(b[0]));
        
        for (String[] a : ab) {
            System.out.println(a[2]);
        }
    }
}

Measured memory_bytes: 26964
#ifdef OJ_MISC_OFFLINE

#include "prolog.h"

#else
#define LOG
#define PRINT
#define LCERR
#include <iostream>
auto optimize_cpp_stdio = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::setvbuf(stdout, nullptr, _IOFBF, BUFSIZ);
    return 0;
}();
#endif

#include <algorithm>
#include <array>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

namespace {

using namespace std;

class Solution {
public:
    int64_t city_saver(vector<int>& mon, const vector<int>& atk) {
        const size_t N = atk.size();
        int64_t result = 0;
        for (size_t i = 0; i < N; ++i) {
            int remaining_atk = atk[i];
            int kill_1 = min(remaining_atk, mon[i]);
            result += kill_1;
            mon[i] -= kill_1;
            remaining_atk -= kill_1;
            int kill_2 = min(remaining_atk, mon[i + 1]);
            result += kill_2;
            mon[i + 1] -= kill_2;
        }
        return result;
    }
private:

};

int solve() {
    Solution solution;
    // handle IO here
    size_t N;
    cin >> N;
    vector<int> mon(N + 1);
    vector<int> atk(N);
    for (size_t i = 0; i < N + 1; ++i) {
        cin >> mon[i];
    }
    for (size_t i = 0; i < N; ++i) {
        cin >> atk[i];
    }
    cout << solution.city_saver(mon, atk) << '\n';
    return 0;
}

} // anonymous namespace

#ifdef OJ_MISC_OFFLINE

#include "epilog.h"

#else

int main() {
    return solve();
}

#endif


Measured memory_bytes: 1024
n, m = map(int, input().split())
ls_ab = [[int(_) for _ in input().split()] for _ in range(n)]
ls_cd = [[int(_) for _ in input().split()] for _ in range(m)]

ans = [0]*n

for i in range(n):
    dmin = 10**9
    for j in range(m):
        if dmin > abs(ls_ab[i][0] - ls_cd[j][0]) + abs(ls_ab[i][1] - ls_cd[j][1]):
            dmin = abs(ls_ab[i][0] - ls_cd[j][0]) + abs(ls_ab[i][1] - ls_cd[j][1])
            ans[i] = j + 1

for k in range(n):
   print(ans[k]) 

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
  while (1){
    int N;
    cin >> N;
    if (N == 0){
      break;
    }
    vector<string> a(N);
    for (int i = 0; i < N; i++){
      cin >> a[i];
    }
    bool ok = true;
    for (int i = 0; i < N - 1; i++){
      if (i % 2 == 0 && a[i] != "x" && a[i + 1] != "x"){
        if (stoi(a[i]) >= stoi(a[i + 1])){
          ok = false;
        }
      }
      if (i % 2 == 1 && a[i] != "x" && a[i + 1] != "x"){
        if (stoi(a[i]) <= stoi(a[i + 1])){
          ok = false;
        }
      }
      if (a[i] == "x" && a[i + 1] == "x"){
        ok = false;
      }
    }
    if (!ok){
      cout << "none" << endl;
    } else {
      int mn = -1100000000;
      int mx = 1100000000;
      for (int i = 0; i < N - 1; i++){
        if (i % 2 == 0){
          if (a[i] == "x" && a[i + 1] != "x"){
            mx = min(mx, stoi(a[i + 1]) - 1);
          }
          if (a[i] != "x" && a[i + 1] == "x"){
            mn = max(mn, stoi(a[i]) + 1);
          }
        }
        if (i % 2 == 1){
          if (a[i] == "x" && a[i + 1] != "x"){
            mn = max(mn, stoi(a[i + 1]) + 1);
          }
          if (a[i] != "x" && a[i + 1] == "x"){
            mx = min(mx, stoi(a[i]) - 1);
          }
        }
      }
      if (mx < mn){
        cout << "none" << endl;
      } else if (mx == mn){
        cout << mx << endl;
      } else {
        cout << "ambiguous" << endl;
      }
    }
  }
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define rep1(i,n) for (int i = 1; i <= (n); i++)
#define repi(i,a,b) for (int i = (a); i < (b); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;

int main() {
  int r, g, b;
  cin >> r >> g >> b;
  
  if ((r*100+g*10+b)%4 == 0) 
    cout << "YES" << endl;
  else 
    cout << "NO" << endl;
}

Measured memory_bytes: 256
from bisect import bisect_left, bisect_right

N, K = map(int, input().split())
*A, = map(int, input().split())
A = sorted(A)

neg_end = bisect_left(A, 0)
pos_start = bisect_right(A, 0)
n_pos = N - pos_start
n_neg = neg_end
n_zero = N - (n_pos + n_neg)

n_prod_neg = n_pos * n_neg
n_prod_zero = n_zero * (n_pos + n_neg) + (n_zero * (n_zero - 1) // 2)

if K <= n_prod_neg: # answer is negative
    # binary search
    def cond(x):
        # two pointers technique
        counter = 0; r = pos_start
        for l in range(neg_end): # (A[l] * A[r] > x) -> (A[l+1] * A[r] > x)
            while r < N and A[l] * A[r] > x: r += 1
            counter += n_pos - (r - pos_start) # (A[l] * A[r] <= x) -> (A[l] * A[r+1] <= x)
        return counter >= K
    MAX = 0
    MIN = -10**18
    left, right = MIN, MAX # search range
    while right - left > 1:
        mid = (left + right) // 2
        if cond(mid): right = mid
        else: left = mid
    print(right)
elif K <= n_prod_neg + n_prod_zero: # answer is zero
    print(0)
else: # answer is positive
    K -= n_prod_neg + n_prod_zero
    # binary search
    def cond(x):
        # two pointers technique
        counter = 0
        r = N - 1
        for l in range(pos_start, N): # (A[l] * A[r] > x) -> (A[l+1] * A[r] > x)  (l < r)
            while l < r and A[l] * A[r] > x: r -= 1
            counter += max(0, r - l) # (A[l] * A[r] <= x) -> (A[l] * A[r-1] <= x)  (l + 1 < r)
            if l >= r: break
        l = 0
        for r in range(neg_end - 1, -1, -1): # (A[l] * A[r] > x) -> (A[l] * A[r-1] > x)  (l < r)
            while l < r and A[l] * A[r] > x: l += 1
            counter += max(0, r - l) # (A[l] * A[r] <= x) -> (A[l+1] * A[r] <= x)  (l < r - 1)
            if l >= r: break
        return counter >= K
    MAX = 10**18
    MIN = 0
    left, right = MIN, MAX # search range
    while right - left > 1:
        mid = (left + right) // 2
        if cond(mid): right = mid
        else: left = mid
    print(right)

Measured memory_bytes: 95492
#include<stdio.h>
int main(){
	char c[3][3];
	scanf("%s",&c[0][0]);
	scanf("%s",&c[1][0]);
	scanf("%s",&c[2][0]);
	printf("%c",c[0][0]);
	printf("%c",c[1][1]);
	printf("%c",c[2][2]);
}

Measured memory_bytes: 128
import java.io.PrintWriter
import java.util.*

val pw = PrintWriter(System.out)
val sc = Scanner(System.`in`)

class Node {
    var parent :Int = -1
    var leftChi :Int = -1
    var rightSib :Int = -1
}

fun main(args: Array<String>) {
    val n = nextInt()
    val fig = (0 until n).map { nextListOfInt() }
    val str = Array(n){Node()}
    for(i in 0 until n){
        val id = fig[i][0]
        val k = fig[i][1]
        for(j in 2 until k+2){
            if(j == 2) str[id].leftChi = fig[i][j]
            str[fig[i][j]].parent = id
            if(j == k+1) continue
            str[fig[i][j]].rightSib = fig[i][j+1]
        }
    }

    for(i in 0 until n){
        val type = if(str[i].parent == -1){
            "root"
        }else if(str[i].leftChi == -1){
            "leaf"
        }else {
            "internal node"
        }

        println("node $i: parent = ${str[i].parent}, depth = ${getDepth(i, str)}, $type, ${getChild(i, str)}")
    }

}

fun getDepth(node :Int, str :Array<Node>) : Int{
    var d = 0
    var n = node
    while(str[n].parent != -1){
        n = str[n].parent
        d++
    }
    return d
}

fun getChild(node :Int, str :Array<Node>) : LinkedList<Int> {
    val ans = LinkedList<Int>()
    if(str[node].leftChi != -1){
        ans.add(str[node].leftChi)
        var n = str[node].leftChi
        while (str[n].rightSib != -1){
            ans.add(str[n].rightSib)
            n = str[n].rightSib
        }
    }

    return ans
}

fun abc000a() {
}

fun next() = readLine()!!
fun nextInt() = next().toInt()
fun nextLong() = next().toLong()
fun nextDouble() = next().toDouble()
fun nextListOfString() = next().split(" ")
fun nextListOfInt() = nextListOfString().map { it.toInt() }
fun nextListOfLong() = nextListOfString().map { it.toLong() }
fun nextListOfDouble() = nextListOfString().map { it.toDouble() }


Measured memory_bytes: 120256
#include<iostream>
#include<algorithm>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<cstdio>
#include<climits>
#include<cmath>
#include<cstring>
#include<string>
#include<sstream>
#include<complex>

#define f first
#define s second
#define mp make_pair

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,c) for(__typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define ALL(c) (c).begin(), (c).end()

using namespace std;

typedef unsigned int uint;
typedef long long ll;
typedef complex<double> P;

#define MAX 1010

int main(){
  int a,b;
  while( ~scanf("%d%d",&a,&b) ){
    int cnt[110] = { 0 };
    do{
      cnt[a]++;
      cnt[b]++;
    }while(scanf("%d%d",&a,&b), a+b );
    bool ans = true;
    if(cnt[1] != 1) ans = false;
    if(cnt[2] != 1) ans = false;
    for(int i=3; i<110; i++) if(cnt[i]%2 == 1) ans = false;
    puts(ans?"OK":"NG");
  }
  return 0;
}

Measured memory_bytes: 0
//#include <bits/stdc++.h>
//#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<cstring>
#include<bitset>
#include<stack>
#include<time.h>



#define X first
#define Y second
#define PB push_back
#define MP make_pair
#define scd(a) scanf("%d",&a)
#define scdd(a,b) scanf("%d%d",&a,&b)
#define scddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define ALL(x) x.begin(),x.end()
#define sz(a) ((int)a.size())
#define getmid ((l+r)>>1)
#define mst(var,val) memset(var,val,sizeof(var))
#define IOS ios::sync_with_stdio(false);cin.tie(0)
#define lowbit(x) x&(-x)
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
#ifdef local
#define dbg(args...) cout << #args << " -> ", err(args);
void err(){ cout << endl; }
template<typename T, typename... Args>
void err(T a, Args... args){ cout << a << ' '; err(args...); }
#else
#define dbg(args...)
#endif // local

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <double, double> pdd;
const int inf=0x3f3f3f3f;
const long long INF=0x3f3f3f3f3f3f3f3fLL;
const double PI=acos(-1.0);
const long double eps=1e-8;
const int mod=1e9+7;
const int maxn=3e5+100;
const int N=2e5+100;
const int M=500+10;
const ll mm=(1LL<<32);

template <class T>
inline void read(T &x)
{
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar())
        f ^= c == '-';
    for (; isdigit(c); c = getchar())
        x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10)
        ++len;
    for (; len; --len, x %= y, y /= 10)
        putchar(x / y + 48);
}
ll qpow(ll a,ll b,ll mod)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return ans;
}

ll a[N];
ll n,k;
bool check(ll x)
{
    ll res=0;
    for(int i=1;i<=n;++i)
    {
        res+=(a[i]-1)/x;
    }
    return res<=k;
}
int main()
{
#ifdef local
    freopen("in.txt","r",stdin);
#endif // local
    IOS;cout.tie(0);
    cin>>n>>k;
    rep1(i,n) cin>>a[i];
    if(check(1))
    {
        cout<<1<<endl;return 0;
    }
    ll l=0,r=1e9,ans;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}



Measured memory_bytes: 5216