akhauriyash/Code-Regression huggingface dataset:
# input()
# int(input())
# map(int, input().split())
# list(map(int, input().split()))
# list(map(int, list(input()))) # スペースがない数字リストを読み込み
import math
import fractions
import sys
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)
import collections
from collections import Counter
from collections import deque
import pprint

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


# a^n
def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod


# n*(n-1)*...*(l+1)*l
def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


inf = 10 ** 18
mod = 10 ** 9 + 7


# segment tree

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x, y: x + y, default=0):
        self.size = 2 ** (size - 1).bit_length()  # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default] * (self.size * 2)  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i * 2], self.dat[i * 2 + 1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres)  # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


n = ir()
a = lr()
seg1 = SegmentTree(n, lambda x, y: x + y, 0)
seg2 = SegmentTree(n, lambda x, y: x + y, 0)
for i, num in enumerate(a):
    seg1.update(i, num)  # 0オリジンのi個目をnumに更新 O(n)
    seg2.update(i, num)  # 0オリジンのi個目をnumに更新 O(n)
ans1 = 0
ans2 = 0
pflag = True
pflag2 = False
for i in range(1,n+1):
    now1 = seg1.query(0,i)
    if pflag and now1 <= 0:
        seg1.update(i-1, a[i-1]-now1+1)
        ans1+=(1-now1)
    elif (not pflag) and now1 >= 0:
        seg1.update(i-1, a[i-1]-now1-1)
        ans1+=(now1+1)
    now2 = seg2.query(0,i)
    if pflag2 and now2 <= 0:
        seg2.update(i-1, a[i-1]-now2+1)
        ans2+=(1-now2)
    elif (not pflag2) and now2 >= 0:
        seg2.update(i-1, a[i-1]-now2-1)
        ans2+=(now2+1)
    pflag = not pflag
    pflag2 = not pflag2
print(min(ans1,ans2))


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

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    int n, k;
    cin >> n >> k;
    vector <int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    int res = 1;
    set <int> s;
    for (int i = 1; i < k; ++i) s.insert(p[i]);
    int all = 0, sum = 0;
    for (int i = 1; i < k; ++i) {
        sum += (p[i] > p[i - 1]);
    }
    if (sum == k - 1) ++all;
    for (int i = 1; i + k <= n; ++i) {
        sum -= (p[i] > p[i - 1]);
        sum += (p[i + k - 1] > p[i + k - 2]);
        if (sum == k - 1) ++all;
        ++res;
        if (p[i + k - 1] > (*s.rbegin()) && (*s.begin()) > p[i - 1]) {
            --res;
        } else if (sum == k - 1 && all > 1) {
            --res;
        }
        s.erase(p[i]);
        s.insert(p[i + k - 1]);
    }

    cout << res << '\n';
}

Measured memory_bytes: 10368
function main()
  
  (a,b,c) = map(x -> parse(Int,x), split(readline()))
  
  n = [a,b,c]
  
  sort!(n, rev = true)
  
  if n[2] + n[3] == n[1]
    println("Yes")
  else
    println("No")
  end
  
end
 
main()

Measured memory_bytes: 114820
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int,int>;


const long long INFLL = 1LL << 60;
const int INFI = 1000000000;

pair<int,int> func(map<int,int> m){
    int MAX = -1; int IDX;
    for(auto i=m.begin();i!=m.end();i++){
        if(MAX<i->second){IDX=i->first; MAX=i->second;}
    }
    pair<int, int> p = make_pair(IDX,MAX);
    return p;
}

int main() {
    int n; cin >> n;
    map<int,int> m1{};
    map<int ,int> m2{};
    for(int i=0;i<n;i++){
        int m; cin>>m;
        if(i%2==0)m1[m]++;
        else m2[m]++;
    }
    pair<int, int> M1 = func(m1);
    pair<int, int> M2 = func(m2);
    //cout << M1.first << M2.first << endl;
    if(M1.first == M2.first){
        m1[M1.first]=0; m2[M2.first]=0;
        pair<int, int> M3 = func(m1);
        pair<int, int> M4 = func(m2);
        cout << n-max(M1.second+M4.second, M2.second+M3.second) << endl;
    }
    else cout << n-M1.second- M2.second << endl;
}



Measured memory_bytes: 7296
def nextprime(x):
    if pow(2, x-1, x) != 1:
        return nextprime(x+1)
    for i in range(2, x):
        if x % i == 0:
            return nextprime(x+1)
    return x


x = int(input())

if x == 2:
    print("2")
else:
    print(nextprime(x))


Measured memory_bytes: 2940
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#define rg register
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;
typedef long long LL;
template < class T > inline void chkmax(T& a, T b) { a = max(a, b); }
template < class T > inline void read(T& s) {
	s = 0; int f = 0; char c = getchar();
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
	s = f ? -s : s;
}

const int _ = 2e5 + 2, p = 1e9 + 7, LIM = 2e3 + 1, inv2 = 500000004;

int n, a[_], b[_];
int dp[LIM * 2 + 5][LIM * 2 + 5];
int fac[LIM * 4 + 5], inv[LIM * 4 + 5];

inline void init() {
	fac[0] = inv[0] = inv[1] = 1;
	for (rg int i = 1; i <= LIM * 4; ++i) fac[i] = 1ll * fac[i - 1] * i % p;
	for (rg int i = 2; i <= LIM * 4; ++i) inv[i] = 1ll * (p - p / i) * inv[p % i] % p;
	for (rg int i = 1; i <= LIM * 4; ++i) inv[i] = 1ll * inv[i - 1] * inv[i] % p;
}

inline int C(int n, int m) { return 1ll * fac[n] * inv[m] % p * inv[n - m] % p; }

int main() {
	init(), read(n);
	int ma = 0, mb = 0;
	for (rg int i = 1; i <= n; ++i) {
		read(a[i]), read(b[i]);
		chkmax(ma, a[i]), chkmax(mb, b[i]);
		++dp[-a[i] + LIM][-b[i] + LIM];
	}
	for (rg int x = -ma; x <= ma; ++x)
		for (rg int y = -mb; y <= mb; ++y) {
			int i = x + LIM, j = y + LIM;
			(dp[i][j] += dp[i - 1][j]) %= p;
			(dp[i][j] += dp[i][j - 1]) %= p;
		}
	int ans = 0;
	for (rg int o = 1; o <= n; ++o) {
		int i = a[o] + LIM, j = b[o] + LIM;
		(ans += dp[i][j]) %= p, (ans += p - C(2 * (a[o] + b[o]), 2 * a[o])) %= p;
	}
	printf("%lld\n", 1ll * ans * inv2 % p);
	return 0;
}


Measured memory_bytes: 64640
import java.util.Scanner;

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

    while (true) {
      a = scanner.nextInt();
      b = scanner.nextInt();
      if (a == 0 && b == 0) break;
      for (int i = 0; i < a; ++i) {
        for (int j = 0; j < b; ++j) System.out.printf("#");
        System.out.println();
      }
      System.out.println();
    }
  }
}


Measured memory_bytes: 59092
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N = get_int
A = get_ints

count = 0
num = 1
A.each do |a|
  if a != num
    count += 1
  else
    num += 1
  end
end

puts count == N ? '-1' : count


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

void answer()
{
    short a,b,c;

    cin>>a>>b>>c;
    //if(((a+b+c)==17)&&((17-(a+b))<=5))
    if(((a+b+c)==17)&&(17-(a+b)>=5))
    {
        cout<<"YES";
    }
    else
        cout<<"NO";
}

int main() {

//  int t;
//  cin>>t;
//  while(t--)
    answer();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>

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

using namespace std;

ll n,k;


int main() {

	cin >> n >> k;
	
	
	if (k % 2) {
		ll x = n / k;
		cout << x*x*x << "\n";
		return 0;
	}
	else {
		ll x=2 * n / k;
		ll y = n / k;
		x -= y;
		cout << x * x*x + y * y*y << "\n";

		return 0;
	}

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define LL long long
#define PII pair<int,int>
using namespace std;
const int MAXN = 100005;
const int INF = (LL)1e9 + 5;
const LL MOD = 998244353;

int N, W;
LL dp[MAXN];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin >> N >> W;
	for (int i = 0; i < N; i++) {
		int w, v;
		cin >> w >> v;
		for (int j = W; j >= w; j--) {
			dp[j] = max(dp[j], dp[j - w] + v);
		}
	}
	
	cout << dp[W] << "\n";
}


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

int main()
{
    array<long, 3> Edge;

    long result = 0;
    bool odd = true;

    cin >> Edge[0] >> Edge[1] >> Edge[2];

    for (long i : Edge)
    {
        if (i % 2 == 0)
        {
            odd = false;
        }
    }

    if (odd)
    {
        sort(Edge.begin(), Edge.end());
        result = Edge[0] * Edge[1];
    }

    cout << result << endl;
    return 0;
}


Measured memory_bytes: 256
MOD = 1000000007
N, K = map(int, input().split())
edge = {}
for _ in range(N - 1):
    a, b = map(int, input().split())
    if a not in edge:
        edge[a] = set()
    edge[a].add(b)
    if b not in edge:
        edge[b] = set()
    edge[b].add(a)


ans = K
q = [(1, None, 1)]
while len(q) > 0:
    par, parpar, depth = q.pop()
    if par not in edge:
        continue
    children = edge[par] - set([parpar])
    if len(children) == 0:
        continue
    if depth == 1:
        start = K - 1
    else:
        start = K - 2
    for i in range(len(children)):
        if start - i <= 0:
            ans = 0
            print(0)
            exit()
        else:
            ans *= start - i
        ans %= MOD
    for c in children:
        q.append((c, par, depth + 1))

print(ans)


Measured memory_bytes: 54168
#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define endl '\n'
#define pb push_back
#define mod 1000000007
#define mp make_pair
#define pi acos(-1)
#define line cout<<"----------------------------"<<endl
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL)
#define filein freopen("input.txt","r",stdin)
#define fileout freopen("output.txt","w",stdout)
#define bug(x) cerr << "[" << #x << "] = ["<<x<<"]"<<'\n'
using namespace std;
int main()
{
        char a,b;
        cin>>a>>b;
        string ans,ans1;
        for(int i=0;i<a-'0';i++)
        {
            ans+=b;
        }
        for(int i=0;i<b-'0';i++)
        {
            ans1+=a;
        }
        if(ans<ans1) cout<<ans<<endl;
        else cout<<ans1<<endl;
}


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

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 1e4+10;

int main(){ _

	int n, k; cin >> n >> k;
	vector<int> h(n);
	for(int& i : h) cin >> i;

	vector<int> memo(n,INF);
	memo[0] = 0;

	for(int i=0; i<n; i++) {
		for(int j=1; j <= k; j++) if(i-j >= 0) {
			memo[i] = min(memo[i], memo[i-j] + abs(h[i]-h[i-j]));
		}
	}
	
	cout << memo[n-1] << endl;

	return 0;
}


Measured memory_bytes: 3988
/* Dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005

int main()
{
	ios
	ll a,b,c;
	cin>>a>>b>>c;
	cout<<c-min(c,a-b);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define fs first
#define sc second
#define INF 1000000000
#define MOD 1000000007
#define EPS 0.00000001


int main() {
    string S; cin >> S;
    int N = (int)S.size();
    
    vector<vector<ll>> dp(N+1, vector<ll>(13));
    dp[0][0] = 1;
    
    
    for(int i=0; i<N; i++){
        for(int j=0; j<13; j++){
            if(S[i]=='?'){
                for(int k=0; k<10; k++){
                    dp[i+1][(10*j+k)%13] += dp[i][j];
                    dp[i+1][(10*j+k)%13] %= MOD;
                }
            }else{
                dp[i+1][(10*j+(S[i]-'0'))%13] += dp[i][j];
                dp[i+1][(10*j+(S[i]-'0'))%13] %= MOD;
            }
        }
    }

    cout << dp[N][5] << endl;
    
    return 0;
}



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

typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m,i,sum=0;
    cin>>n>>m;
    ll a[m];
    for(i=0;i<m;++i)
    {
        cin>>a[i];
        sum+=a[i];
    }
    if(n>=sum)
        cout<<(n-sum);
    else
        cout<<"-1";
}

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

#define MAX_N 10
typedef long long ll;
const ll INF = 1000000000;

ll N, A, B, C;
std::vector<ll> l(MAX_N);

int dfs(ll cur, ll a, ll b, ll c){
    //cout << cur << endl;
    ll ret0, ret1, ret2, ret3;
    if(cur == N){
        if(min({a, b, c}) > 0){
            return abs(a - A) + abs(b - B) + abs(c - C) - 30;
        }else{
            return INF;
        }
    }
    ret0 = dfs(cur + 1, a, b, c);
    ret1 = dfs(cur + 1, a + l[cur], b, c) + 10;
    ret2 = dfs(cur + 1, a, b + l[cur], c) + 10;
    ret3 = dfs(cur + 1, a, b, c + l[cur]) + 10;
    return min({ret0, ret1, ret2, ret3});
}

void solve(){
    cout << dfs(0, 0, 0, 0) << endl;
}

int main(){
    cin >> N >> A >> B >> C;
    for(ll i = 0 ; i < N ; i++){
        cin >> l[i];
    }
    solve();
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <queue>
#include <stack>
#include <climits>
#include <map>
#include <set>

const int mod = 1e9 + 7;
const int inf = 1e9;
const long long INF = 1LL << 60;
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
using namespace std;

struct edge {ll from,to,cost;};

int main()
{
    string s,t;
    cin >> s >>t;
    int a,b;
    cin >> a >> b;
    string u;
    cin >> u;
    if(s == u){
        cout << a-1 << ' ' << b;
    }else{
        cout << a << ' ' << b-1;
    }
}

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

#define int long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

signed main(){
	fastio
	int n,cp;
	cin >> n >> cp;
	int w[n], v[n];
	for(int i = 0;i < n;i++) cin >> w[i] >> v[i];
	int dp[n][cp+1];
	memset(dp,0,sizeof dp);
	for(int i = w[0]; i <= cp; i++) dp[0][i] = v[0];
	for(int i = 1;i < n;i++){
		for(int j = 1;j <= cp;j++){
			dp[i][j] = max({dp[i][j],dp[i][j-1]});
			dp[i][j] = max(dp[i][j],dp[i-1][j]);
			if(j >= w[i]) dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]] + v[i]);
		}
	}
	int ans = 0;
	for(int i = 0;i <= cp;i++) ans = max(ans,dp[n-1][i]);
	cout << ans << "\n";
}

Measured memory_bytes: 81688
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define FORqr(i, m , n) for(int i = (n);i >=(m);--i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
int main(){
    int A,B,C;
    SCD3(A,B,C);
    if (A+B >= C-1){
        PRINTD(B+C);
    }else{
        PRINTD(A+B+1+B);
    }
}

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

int main() {
char a;
char X;
cin >> a;

  
  if(a == 'A' || a == 'B' || a == 'C' || a == 'D' || a == 'E' || a == 'F' || a == 'G' || a == 'H' || a == 'I' || a == 'J' || a == 'K' || a == 'L' || a == 'M' || a == 'N' || a == 'O' || a == 'P' || a == 'Q' || a == 'R' || a == 'S' || a == 'T' || a == 'U' || a == 'V' || a == 'W' || a == 'X' || a == 'Y' || a == 'Z'){
  X = 'A';
  }
   else{
   X = 'a';
   }
cout << X << endl;

}


Measured memory_bytes: 3628
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.stream.IntStream;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class TaskC {
        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int[] s = in.nextString().chars().map(c -> c - 'a').toArray();
            int[] t = in.nextString().chars().map(c -> c - 'a').toArray();

            int[] map = new int[26];
            int[] rev = new int[26];
            Arrays.fill(map, -1);
            Arrays.fill(rev, -1);
            for (int i = 0; i < s.length; i++) {
                if (map[s[i]] == -1) {
                    map[s[i]] = t[i];
                } else {
                    if (map[s[i]] != t[i]) {
                        out.println("No");
                        return;
                    }
                }

                if (rev[t[i]] == -1) {
                    rev[t[i]] = s[i];
                } else {
                    if (rev[t[i]] != s[i]) {
                        out.println("No");
                        return;
                    }
                }
            }

            out.println("Yes");
        }

    }

    static class InputReader {
        private BufferedReader br;
        private StringTokenizer st;

        public InputReader(InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
            st = new StringTokenizer("");
        }

        public String nextString() {
            while (!st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine(), " ");
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return st.nextToken();
        }

    }
}



Measured memory_bytes: 33100
public class Main {
  private static void solve() {
    int n = ni();
    int[] a = na(n);

    int cnt = 0;
    int min = Integer.MAX_VALUE;
    for (int i = 0; i < n; i++) {
      min = Math.min(min, a[i]);
      if (min >= a[i])
        cnt++;
    }
    System.out.println(cnt);
  }

  public static void main(String[] args) {
    new Thread(null, new Runnable() {
      @Override
      public void run() {
        long start = System.currentTimeMillis();
        String debug = args.length > 0 ? args[0] : null;
        if (debug != null) {
          try {
            is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
          } catch (Exception e) {
            throw new RuntimeException(e);
          }
        }
        reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
        solve();
        out.flush();
        tr((System.currentTimeMillis() - start) + "ms");
      }
    }, "", 64000000).start();
  }

  private static java.io.InputStream is = System.in;
  private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
  private static java.util.StringTokenizer tokenizer = null;
  private static java.io.BufferedReader reader;

  public static String next() {
    while (tokenizer == null || !tokenizer.hasMoreTokens()) {
      try {
        tokenizer = new java.util.StringTokenizer(reader.readLine());
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }
    return tokenizer.nextToken();
  }

  private static double nd() {
    return Double.parseDouble(next());
  }

  private static long nl() {
    return Long.parseLong(next());
  }

  private static int[] na(int n) {
    int[] a = new int[n];
    for (int i = 0; i < n; i++)
      a[i] = ni();
    return a;
  }

  private static char[] ns() {
    return next().toCharArray();
  }

  private static long[] nal(int n) {
    long[] a = new long[n];
    for (int i = 0; i < n; i++)
      a[i] = nl();
    return a;
  }

  private static int[][] ntable(int n, int m) {
    int[][] table = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[i][j] = ni();
      }
    }
    return table;
  }

  private static int[][] nlist(int n, int m) {
    int[][] table = new int[m][n];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        table[j][i] = ni();
      }
    }
    return table;
  }

  private static int ni() {
    return Integer.parseInt(next());
  }

  private static void tr(Object... o) {
    if (is != System.in)
      System.out.println(java.util.Arrays.deepToString(o));
  }
}


Measured memory_bytes: 48028
s=input()
K=int(input())
listA=[]


for j in range(1,K+1):
    for i in range(len(s)):
        listA.append(s[i:i+j])
listA.sort()
x=""
count=0
for i in range(len(listA)):
    if(x!=listA[i]):
        count+=1
        x=listA[i]
    if(count==K):
        print(x)
        break;

Measured memory_bytes: 4340
#include<bits/stdc++.h>
#define rep(i, n) for (int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
 
const int  mod = 998244353;
struct mint{
    ll x;
    mint (ll x=0) : x((x%mod+mod)%mod){}//カッコの中で初期化している
    mint& operator+=(const mint a){//operatorは構造体同士の比較に用いられる
        if((x +=a.x)>=mod) x-=mod;
        return *this;//thisとは現在のオブジェクトのこと
    }
    mint& operator-=(const mint a){
        if((x +=mod-a.x)>=mod) x-=mod;
        return *this;
    }
    mint& operator*=(const mint a){
        (x*=a.x)%=mod;
        return *this;
    }
    mint operator+(const mint a){
        mint res(*this);
        return res+=a;
    }
    mint operator-(const mint a){
        mint res(*this);
        return res-=a;
    }
    mint operator*(const mint a){
        mint res(*this);
        return res*=a;
    }
    mint pow(ll t) const{
        if(!t) return 1;
        mint a=pow(t>>1);
        a*=a;
        if(t&1) a*=*this;
        return a;
    }
    mint inv() const{
        return pow(mod-2);//逆元
    }
    mint&operator/=(const mint a) {
        return (*this)*=a.inv();
    }
    mint&operator/(const mint a) const{
    mint res(*this);
    return res/=a;
    }
};


int main(void){
    ll n, m ,k;
    cin>>n>>m>>k;
    vector<mint>comb(k+5);
    comb[0] = 1;
    rep(i, k+1){
        comb[i+1] = comb[i];
        comb[i+1] *= (n-1-(ll)i);
        comb[i+1] /= ((ll)i+1); 
    }
    vector<mint> beki(n+5);
    beki[0] = 1;
    rep(i, n+1){
        beki[i+1] = beki[i];
        beki[i+1] *= (m-1);
    }
    mint ans = 0;
    rep(i, k+1){
        mint tmp = comb[i];
        tmp *= beki[n-1-i];
        ans += tmp;
    }
    ans *= m;
    cout<<ans.x<<endl;
    return 0;
}

Measured memory_bytes: 6220
#include"cstdio"
long long gcd(long long x , long long y)
{
	if(!y)
		return x;
	else return gcd(y,x%y);
}
int main(){
	int n;
	long long a[105];
	scanf("%d",&n);
	long long temp,ans;
	scanf("%lld",&a[0]);
	temp=a[0];
	for(int i=1;i<n;i++)
	{
		scanf("%lld",&a[i]);
			if(temp>a[i])
				ans=gcd(temp,a[i]);
			else ans=gcd(a[i],temp);
			temp=temp/ans;
			temp=temp*a[i];
	}
	printf("%lld\n",temp);
	return 0;
}

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

int N;
vector<int> A;


int solve(){
	vector<int> ansv;
	long long ans=0;

	sort(A.begin(),A.end());

	int small = 1;
	int large = N-2;

	ansv.push_back(A[0]);
	ansv.push_back(A[N-1]);

	bool flag = true;
	for(int i=0; i<N/2-1; i++){
		if(flag){
			ansv.push_back(A[small]);
			ansv.insert(ansv.begin(),A[large]);
			small++;large--; 
		}else{
			ansv.insert(ansv.begin(),A[small]);
			ansv.push_back(A[large]);	
			small++; large--;		
		}
		flag ^= true;
	}

	if(N%2==1) {
		if(abs(ansv[0]-A[N/2]) > abs(ansv[ansv.size()-1]-A[N/2])) ansv.insert(ansv.begin(), A[N/2]);
		else ansv.push_back(A[N/2]);
	}

	for(int i=0;i<N-1;i++){
		ans += abs(ansv[i]-ansv[i+1]);
	}

	// for(int i=0; i<N; i++){
	// 	cout << ansv[i] << " ";
	// }

	cout << ans << endl;
	return 0;
}


int main(){
	cin >> N;
	A.resize(N);
	for(int i=0;i<N;i++){
		cin >> A[i];
	}

	solve();
	return 0;
}


Measured memory_bytes: 1276
fun main(args: Array<String>){
    val n = readLine()!!.toInt()
    val a = readLine()!!.split(" ").map { it.toLong() }

    var ans = 0
    for (ae in a){
        var b = ae
        while(b % 2 == 0L){
            b /= 2
            ans++
        }
    }
    println(ans)
}

Measured memory_bytes: 42000
#include <iostream>
using namespace std;
typedef long long ll;

signed main(){
	ll N,A,B;
	cin>>N>>A>>B;
	ll a,b,sum=0;
	cin>>b;
	for(ll i=2;i<=N;i++){
		cin>>a;
		sum+=min((a-b)*A,B);
		swap(a,b);
	}
	cout<<sum<<endl;
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int zs(int n)
{
	int i;
	if(n<=1)
		return 0;
	for(i=2;i<=n/2;i++)
	{
		if(n%i==0)
			return 0;
	}
	return 1;
}
int main()
{
	int i,n;
	scanf("%d",&n);
	printf("11");
	n--;
	for(i=31;n>0;i+=10)
	{
		if(zs(i))
		{
			n--;
			printf(" %d",i);
		}
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

  public static void main(String[] args) { 
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      int[] cntArr = new int[n+1];
      boolean[] hasBall = new boolean[n+1];
      Arrays.fill(cntArr, 1);
      hasBall[1] = true;

      for(int i = 0; i < m; i++) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        if(hasBall[x]) {
          hasBall[y] = true;
          if(cntArr[x] == 1)
            hasBall[x] = false;
        }
        cntArr[x]--;
        cntArr[y]++;
      }
      int cnt = 0;
      for(int i = 1; i <= n; i++)
        if(hasBall[i])
          cnt++;
      System.out.println(cnt);
  }
}

Measured memory_bytes: 64872
n = int(input())
A = list(map(int, input().split()))

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[j], A[i] = A[i], A[j]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

j = partition(A, 0, n - 1)
A = [str(i) for i in A]
A[j] = '[{}]'.format(A[j])
print(' '.join(A))


Measured memory_bytes: 16388
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <iomanip>
#include <vector>
#include <queue>
#include <map>
#include <set>

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb push_back
#define in insert
#define er erase
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define le(x) (int) x.length()
#define rsz resize

using namespace std;
typedef vector <int> vi;
typedef vector <vector <int> > vii;
typedef pair <int, int> pii;
typedef queue <int> qi;
typedef double db;
typedef long long ll;
typedef long double ld;
 
const long double PI=3.141592653589793238462643383279502884;
const long long PRIME1=1e9+787;
 
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll minll(ll a,ll b) {return a<=b?a:b;}
ll maxll(ll a,ll b) {return a>=b?a:b;}

int main () {
    fast;
    double a,b,c,k;
    cin>>a>>b>>c>>k;
    double a1=ceil((a+1)/b);
    int count=ceil(log2(a1));
    b*=pow(2,count);
    a1=(db)ceil((b+1)/c);
    int k1=ceil(log2(a1));
    c*=pow(2,k1);
    if (count+k1<=k) {
        cout<<"Yes";
    } else {
        cout<<"No";
    }
    return 0;
}
 
 


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

int main(){
	/*input*/
	char s[10];
	cin >> s;
	/*calculation*/
	int i = 0;
	int max = 0;
	int dmax = 0;
	while(s[i]){
		switch(s[i]){
			case 'A':
			case 'C':
			case 'G':
			case 'T':
				dmax++;	
			break;
			default:
				if(max < dmax){
					max = dmax;
				}
				dmax = 0;
			break;
		}
		if(max < dmax){
			max = dmax;
		}
		i++;
	}
	/*output*/
	cout << max << endl; 
}


Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(1)
	s = input()
	t = sys.stdin.readline().rstrip()
	if s == t[:-1]:
		print("Yes")
	else:
		print("No")
	


main()

Measured memory_bytes: 68428
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int seisu;
	int a[4];
	char hugou[3];
	scan(seisu);
	rep(i,4){
		a[4-i-1]=seisu%10;
		seisu/=10;
	}
	rep(i,2){
		rep(j,2){
			rep(k,2){
				int ans=a[0];
				if(i%2) ans+=a[1];
				else ans-=a[1];
				if(j%2) ans+=a[2];
				else ans-=a[2];
				if(k%2) ans+=a[3];
				else ans-=a[3];
				if(ans==7){
					hugou[0]=(i%2 ? '+' : '-');
					hugou[1]=(j%2 ? '+' : '-');
					hugou[2]=(k%2 ? '+' : '-');
									goto gomi;
				}
			}
		}
	}
	gomi:
	rep(i,3){
		printf("%d",a[i]);
		printf("%c",hugou[i]);
	}
	printf("%d=7\n",a[3]);
	return 0;
}


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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

signed main() {
  string s;
  cin>>s;
  rep(i,0,3){
    if (s[i] == s[i+1]) {
      cout<<"Bad"<<endl;
      return 0;
    }
  }
  cout<<"Good"<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n);i++)
#define sz(x) int(x.size())
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr int INF = 2e9;
typedef tuple<int,int,int> TP;
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    ll res = 0;
    vector<vector<int>> left(n), right(n);
    rep(i,n) {
      int x, l, r;
      cin >> x >> l >> r;
      x--;
      res += min(l, r);
      if (l - r < 0) right[x].emplace_back(r - l);
      else left[x].emplace_back(l - r);
    }
    priority_queue<int, vector<int>, greater<int>> pq;

    for (int i = 0; i < n; i++) {
      for (auto v : left[i]) pq.push(v);
      while (pq.size() > (i + 1)) {
        pq.pop();
      }
    }
    while (!pq.empty()) res += pq.top(), pq.pop();

    for (int i = n - 1; i >= 0; i--) {
      for (auto v : right[i]) pq.push(v);
      while (pq.size() > (n - i - 1)) {
        pq.pop();
      }
    }
    while (!pq.empty()) res += pq.top(), pq.pop();

    cout << res << "\n";
  }
  return 0;
} 

Measured memory_bytes: 17824
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

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


string s;

bool input(){
	cin>>s;
}

bool req(int st, int en){
	int count = 0;
	
	if(st>en)return true;
	if(s[st]!='m' || s[en]!='w')return false;
	
	bool ans = false;
	reps(i,st,en+1){
		if(s[i]=='m')count++;
		if(s[i]=='w')count--;
		
		if(count==1 && s[i]=='e'){
			ans = req(st+1, i-1) & req(i+1, en-1);
			break;
		}
	}
	
	return ans;
}

string solve(){
	bool ans = req(0, s.size()-1);
	
	if(ans)return "Cat";
	return "Rabbit";
}

int main(){
	input();
	cout<<solve()<<endl;
}

Measured memory_bytes: 1188
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N, K, ans=1;
    cin >> N >> K;

    for(int i=0;i<N;i++){
	if(ans<=K)
	    ans *= 2;
	else
	    ans+=K;
	
    }
    cout << ans<<endl;
}


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

signed main(){
    ll x,n;
    cin>>x>>n;
    vector<ll> p(n);
    rep(i,n) cin>>p[i];
    sort(p.begin(),p.end());
    ll mind=mod,minn=mod;
    rep(i,102){
        if(binary_search(p.begin(),p.end(),x-i)==false){
            minn = x-i;
            break;
        }
        if(binary_search(p.begin(),p.end(),x+i)==false){
            minn = x+i;
            break;
        }
    }
    cout<<minn<<endl;
}


Measured memory_bytes: 3628
from collections import Counter

import sys
input = sys.stdin.readline

N = int(input())

S = []
for i in range(N):
    s = input()
    S.append(s[:-1])

cc = Counter(S)

for v in ('AC', 'WA', 'TLE', 'RE'):
    print('{} x {}'.format(v, cc[v]))


Measured memory_bytes: 79776
import java.util.Scanner;

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

		//コンソールに入力した値を取得
		int n = sc.nextInt();
		int nn = n%10;

		if (nn == 3) {
			System.out.println("bon");
		} else if (nn == 0 || nn == 1 || nn == 6 || nn == 8) {
			System.out.println("pon");
		} else {
			System.out.println("hon");
		}

		sc.close();
	}
}


Measured memory_bytes: 26844
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long N = long.Parse(str[0]);
		long M = long.Parse(str[1]);
		long ans = M;
		if(N<10){
			ans = M+100*(10-N);
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <ctype.h>
#include <ios> 
#include <iomanip>
using namespace std;

#define N_MAX   (100000)
#define LL_MAX_NUM (1LL<<60)
#define INF 1e7

typedef long long ll;
typedef long long int lli;

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;
    string res;
    if (abs(a-c) <= d) {
        res = "Yes";
    } else {
        if (abs(a-b) <= d && abs(b-c) <= d) {
            res = "Yes";
        } else {
            res = "No";
        }
    }
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int p[3],j[2];
  cin >> p[0] >> p[1] >> p[2] >> j[0] >> j[1];
  sort(p,p+3);
  sort(j,j+2);
  cout << p[0]+j[0]-50 << endl;
  return 0;
}

Measured memory_bytes: 1176
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n) - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a); i > (b); i--)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N, C[20], V[20];
    cin >> N;
    REP(i, N) cin >> V[i];
    REP(i, N) cin >> C[i];
    int ans = 0;
    REP(i, N) if (V[i] - C[i] > 0) ans += V[i] - C[i];
    cout << ans << endl;
    return 0;
}

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

// エイリアス
using  ll = long signed long;
using ull = long unsigned long;
using  ld = long double;
using   P = pair<int, int>;
using llP = pair<ll, ll>;
using DoP = pair<double, double>;

// 汎用マクロ
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define FOREACH(i,q) for (auto &i : q)
#define UNIQUE(v) do { sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end()); } while (false)
#define SZ(x) ((int)(x).size())
template <class T>inline bool chmin(T &a, const T b) {if (a > b) { a = b; return true;} return false;}
template <class T>inline bool chmax(T &a, const T b) {if (a < b) { a = b; return true;} return false;}
template <class T>inline void line_out(const vector<T> vec) {int n = SZ(vec); rep(i, n) { cout << vec[i]; if(i < n-1) cout << " ";}cout << endl;}
const int di[] = {0, 1, 0, -1, 1, 1, -1, -1};
const int dj[] = {1, 0, -1, 0, 1, -1, 1, -1};
const int INF = 1 << 28;
const ll INF64 = 1ll << 60;
const int mod = 1000000007;
//const int mod = 998244353;
//const int mod = 100000;
struct mint
{
  ll x; // typedef long long ll;
  mint(ll x = 0) : x((x % mod + mod) % mod) {}
  mint operator-() const { return mint(-x); }
  mint &operator+=(const mint a)
  {
    if ((x += a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator-=(const mint a)
  {
    if ((x += mod - a.x) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator*=(const mint a)
  {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const
  {
    mint res(*this);
    return res += a;
  }
  mint operator-(const mint a) const
  {
    mint res(*this);
    return res -= a;
  }
  mint &operator++()
  {
    if ((x += 1) >= mod)
      x -= mod;
    return *this;
  }
  mint &operator--()
  {
    if ((x += mod - 1) >= mod)
      x -= mod;
    return *this;
  }
  mint operator*(const mint a) const
  {
    mint res(*this);
    return res *= a;
  }
  mint pow(ll t) const
  {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const
  {
    return pow(mod - 2);
  }
  mint &operator/=(const mint a)
  {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const
  {
    mint res(*this);
    return res /= a;
  }
};

int main()
{
  int a, b, c;
  cin >> a >> b >> c;
  bool ok = true;
  if(a == b && a != c) ok = false;
  if(a == c && a != b) ok = false;
  if(b == c && a != b) ok = false;

  if(!ok) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 3620
use proconio::{fastout, input};
use std::vec::Vec;

#[fastout]
fn main() {
    input! {
        n: usize,
        k: i64,
        a: [i64; n],
    }

    let mut ng: i64 = 0; let mut ok: i64 = 1_000_000_000;
    while num::abs(ok - ng) > 1 {
        let cen: i64 = (ok + ng) / 2;
        if is_ok(&a, cen, k) { ok = cen } else { ng = cen }
    }

    println!("{}", ok);
}

fn is_ok (a: &Vec<i64>, x: i64, k: i64) -> bool {
    let mut cut_num: i64 = 0;
    for &elem in a {
        cut_num += (elem - 1) / x;
    }
    cut_num <= k
}


Measured memory_bytes: 5356
// Hail god Yato
 
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX = 100001;
//
//
void solve(){
    int a, b;
    cin>>a>>b;
    int pw = pow(100, a);
    int ans = pw*b;
    if(a == 0){
        if(b == 100){
            cout<<"101";
            return ;
        }
    }
    if(a == 1){
        if(b == 100){
            cout<<"10100";
            return ;
        }
    }
    if(a == 2){
        if(b == 100){
            cout<<"1010000";
            return ;
        }
    }
    cout<<ans;
}
int main(){ 
        hs;
        ll t;
        t=1;
        // cin>>t;
        for (int i=1; i<=t; i++){
                //cout<<"Case #"<<i<<": ";
                solve();
         }
        return 0; 
}

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

#define rep(i,n) for(i = 0;i < n;++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main()
{
    ll i,j;
    char a;
    cin >> a;
    if(a <= 'Z') cout << 'A' << endl;
    else cout << 'a' << endl;

    return 0;
}

Measured memory_bytes: 3600
// +build ignore
package main

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

func solve(sc *scanner, wr *bufio.Writer) int {
	b := []byte(sc.s())[0]

	if 0x40 <= b && b <= 0x5a {
		fmt.Println("A")
	} else {
		fmt.Println("a")
	}

	return 0
}

func main() {
	sc := newScanner(os.Stdin)
	wr := bufio.NewWriter(os.Stdout)
	ret := solve(sc, wr)
	wr.Flush()
	os.Exit(ret)
}

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

func newScanner(input io.Reader) *scanner {
	sc := bufio.NewScanner(input)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &scanner{sc}
}

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

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

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

func (s *scanner) bs() []byte {
	return []byte(s.s())
}

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

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


Measured memory_bytes: 1772
/**
 * agc039a
 * A - Connection and Disconnection
 */

fun main(args: Array<String>){
	val s: String = readLine()!!.toString()
	val k = readLine()!!.toInt()
	println(agc039a(s, k))
}

fun agc039a(s: String, k: Int): Long{
	val s1 = opeCounter(s, 1)
	val s2 = opeCounter(s, 2)
	val s3 = opeCounter(s, 3)
	val d1 = s2 - s1
	val d2 = s3 - s2
	val d = d1 + d2

	var ans: Long
	if(d1 == d2) ans = s1 + d1 * (k-1)
	else
		if(k%2 != 0) ans = s1 + d * ((k+2-1)/2-1) //(k/2):roundup
		else ans = s2 + d * (k/2-1)
	return ans;
}

fun opeCounter(s: String, k:Int): Long{
	var t = s
	for(i in 1..k-1) t += s
	var c = 0L
	var i = 1
	while(i<t.length){
		if(t[i-1] == t[i]){ c++; i++ }
		i++
	}
	return c;
}

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

//短縮
#define rep(i,n) for(int i=0;i<(n);++i)
//sort()用
#define all(v) v.begin(), v.end()

#define PB(N) push_back(N)

using namespace std;

using Graph = vector<vector<int>>;

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

  vector<int> count(N);
  for(int n=1;n<=N;n++){
    double buffer=pow(n,0.5);
    for(int x=1;x<buffer;x++){
      for(int y=x;y<buffer;y++){
        double z = pow(n-(double)3.0*(x*x+y*y)/4.0-(double)x*y/2.0,0.5)-(double)(x+y)/2;
        if(floor(z)==z && (z>=1)){
          if(x==y) count[n-1]++;
          else count[n-1]+=2;
          //count[n-1]++;
        }
      }
    }
  }

  rep(i,N) cout << count[i] << endl;

  return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
map<string,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int ma=0;
	cin>>N;
	FOR(i,N) {
		cin>>s;
		M[s]++;
		ma=max(ma,M[s]);
	}
	FORR(m,M) if(m.second==ma) cout<<m.first<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 23808
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
typedef long long ll;
using namespace std;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;
#define repi(i, n, init) for (ll i = init; i < (n); i++)

int main()
{
    int n, m;
    cin >> n >> m;
    vector<string> A(n), B(m);
    repi(i, n, 0)
    {
        cin >> A[i];
    }
    repi(i, m, 0)
    {
        cin >> B[i];
    }
    repi(i, n - m + 1, 0)
    {
        repi(j, n - m + 1, 0)
        {

            //solve
            int cnt = 0;
            repi(k, m, 0)
            {
                repi(l, m, 0)
                {
                    if (A.at(k + i).at(l + j) == B.at(k).at(l))
                    {
                        cnt++;
                    }
                }
            }
            if (cnt == m * m)
            {
                puts("Yes");
                return 0;
            }
        }
    }
    puts("No");
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
	int n,k;
	cin>>n>>k;
	int arr[n];
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	ll sum=0;
	sort(arr,arr+n);
	for(int i=0;i<k;i++){
		sum+=arr[i];
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

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

__attribute__((constructor)) void initial() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int main() {
    rep(i, 7) {
        int A, B;
        cin >> A >> B;
        cout << (A - B) << endl;
    }
}


Measured memory_bytes: 3124
#include<bits/stdc++.h>
using namespace std;
int main (){
int a;
	int b;
	int c;
	cin>>a>>b>>c;
	if(a==5 && b==5 && c==7){
		cout<<"YES"<<endl;
	}else if(a==5 && b==7 && c==5){
		cout<<"YES"<<endl;
	}else if(a==7 && b==5 && c==5){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 256