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

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

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcountll

#define INF 1e16
#define mod 1000000007

vector<int> g[100010];
int sz[100010];
bool dame[100010];
vector<int> cent;
int a[100010];
ll res;

void compute_subtree_size(int v,int pre){
  sz[v]=1;
  for(int nv : g[v]){
    if(nv==pre||dame[nv])continue;
    compute_subtree_size(nv,v);
    sz[v]+=sz[nv];
  }
}

void search_centroid(int v,int pre,int tot){
  bool is_cent=true;
  for(int nv : g[v]){
    if(nv==pre||dame[nv])continue;
    search_centroid(nv,v,tot);
    if(sz[nv]>tot/2)is_cent=false;
  }
  if(tot-sz[v]>tot/2)is_cent=false;
  if(is_cent)cent.push_back(v);
}

void dfs(ll v,ll pre,vector<ll>& down,ll sum,ll summn){
  sum+=a[v]; minch(summn,sum);
  if(sum-summn<=0){
    assert(-sum>=0);
    down[-sum]++;
  }
  for(int nv : g[v]){
    if(nv==pre||dame[nv])continue;
    dfs(nv,v,down,sum,summn);
  }
}

void dfs2(ll v,ll pre,const vector<ll>& down,ll sum,ll summx,ll i){
  sum+=a[v]; maxch(summx,sum);
  if(sum-summx>=0){
    ll up=sum;
    assert(up>=0);
    res+=down[up];
    if(up==0&&i==0){
      res++;
    }
  }
  for(int nv : g[v]){
    if(nv==pre||dame[nv])continue;
    dfs2(nv,v,down,sum,summx,i);
  }
}

void dfs3(ll v,ll pre,ll sum,ll summn){
  sum+=a[v]; minch(summn,sum);
  if(sum-summn<=0){
    if(sum==0)res++;
  }
  for(int nv : g[v]){
    if(nv==pre||dame[nv])continue;
    dfs3(nv,v,sum,summn);
  }
}

void solve_subprob(ll v){ // main
  compute_subtree_size(v,-1);
  cent.clear();
  search_centroid(v,-1,sz[v]);
  int c=cent[0];
  dame[c]=true;

  // devide
  for(int nv : g[c]){
    if(dame[nv])continue;
    solve_subprob(nv);
  }

  //dbg(c);
  dame[c]=false;
  compute_subtree_size(c,-1);
  ll szc=sz[c];
  // conquer
  rep(i,2){
    reverse(all(g[c]));
    vector<ll> down(szc+1,0);
    for(int nv : g[c]){
      if(dame[nv])continue;
      dfs2(nv,c,down,a[c],max(a[c],0),i);
      dfs(nv,c,down,0,0);
    }
  }
  dfs3(c,-1,0,0);
}


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

  int N;
  string s;
  cin>>N;
  cin>>s;
  rep(i,N){
    if(s[i]=='(')a[i]=1;
    else a[i]=-1;
  }
  rep(i,N-1){
    int b,c;
    cin>>b>>c;
    b--; c--;
    g[b].push_back(c);
    g[c].push_back(b);
  }
  solve_subprob(0);
  cout<<res<<endl;

  return 0;
}



Measured memory_bytes: 18128
#include <bits/stdc++.h>
#define lol long long
using namespace std;
int main(){
  lol n,m,ans;
  string s,t,a;
  cin>>s>>t>>n>>m>>a;
  if(a==s){
    cout<<n-1<<" "<<m<<"\n";
  }
  else if(a==t){
    cout<<n<<" "<<m-1<<"\n";
  }
  else{
    cout<<n<<" "<<m<<"\n";
  }
  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 puts(i) cout<<i<<endl
#define pi 3.14159265358979323846264338
#define pb push_back
#define mp make_pair
#define inf 10000
using ll = long long;
using P = pair<int,int>;
using Pll = pair<ll,ll>;

ll divisor=1000000007;

int main(){
	int n,k;
	cin>>n>>k;
	int a[n];
	rep(i,n)cin>>a[i];
	sort(a,a+n);
	int sum=0;
	rep(i,k)sum+=a[i];
	puts(sum);
}


Measured memory_bytes: 3556
/*
　　こんにちは。あたしはｶｳｶﾞｰﾙ。
　　redcoderになるためAtCoderを巡る旅をしてます。

　　　 　 ＿_
　　　 ヽ|＿_|ノ　　　　ﾓｫ
　　　　||‘‐‘||ﾚ　　_)_, ―‐ 、
　　　　/(Ｙ (ヽ＿ /・ ヽ　　 ￣ヽ
　　　　∠ ＿ ゝ　 ｀^ヽ ﾉ.::::_(ノヽ
　　　　 _/ヽ　 　　  /ヽ￣￣/ヽ
*/

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define dump(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl

#define rep(i, n) REP(i, 0, n)                              // 0, 1, ..., n-1
#define REP(i, x, n) for(int i = x; i < n; i++)             // x, x + 1, ..., n-1
#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(v) (v).begin() , (v).end()
#define RALL(v) (v).rbegin(), (v).rend()

#define COUT(x) cout << (x) << endl

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

    vector<int> order(8); // Queenの位置 順列
    vector<vector<int>> board(8, vector<int>(8, 0));

bool isCheck() {
    rep(i, 8) {
        board[i][order[i]] = 1;
    }

    rep(i, 8) {
        rep(j, 8) {
            // 右ななめ下
            if(!board[i][j]) continue;
            int y = i;
            int x = j;
            int cnt = 0;
            while(y < 8 && x < 8) {
                cnt += board[y][x];
                y++;
                x++;
            }
            if(cnt > 1) return false;

            // 左ななめ下
            cnt = 0;
            y = i;
            x = j;
            while(y < 8 && x >= 0) {
                cnt += board[y][x];
                y++;
                x--;
            }
            if(cnt > 1) return false;
        }
    }
    return true;
}

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

    int k; cin >> k;
    vector<pair<int,int>> rc(k);

    rep(i, k) {
        cin >> rc[i].first >> rc[i].second;
    }

    rep(i, 8) order[i] = i;

    do {
        // 与えられたQの位置が異なる順列であるのならばスキップ
        bool flg = false;
        rep(i, k) {
            if(order[rc[i].first] != rc[i].second) {
                flg = true;
                break;
            }
        }
        if(flg) continue;

        if(isCheck()) break;
        else board.assign(8, vector<int>(8, 0));
    } while(next_permutation(ALL(order)));

    rep(i,8) {
        rep(j, 8) {
            if(board[i][j]) cout << "Q";
            else cout << ".";
        }
        cout << endl;
    }
}




Measured memory_bytes: 3212
import java.util.*;

public class Main {

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int count = 0;

    for (int i = a; i <= b; i++) {
      String s = String.valueOf(i);
      char[] c = s.toCharArray();
      if (c[0] == c[4] && c[1] == c[3]) count++;
    }

    System.out.println(count);
  }

}


Measured memory_bytes: 30932
#![allow(unused_mut, non_snake_case,unused_imports,dead_code)]
use std::iter;
use std::cmp::{max, min, Ordering};
use std::mem::{swap};
use std::collections::{HashMap,BTreeMap,HashSet,BTreeSet,BinaryHeap,VecDeque};
use std::iter::FromIterator;

//　高速 EOF要
//macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();input_inner!{iter, $($r)*}};($($r:tt)*) => {let mut s = {use std::io::Read;let mut s = String::new();std::io::stdin().read_to_string(&mut s).unwrap();s};let mut iter = s.split_whitespace();input_inner!{iter, $($r)*}};}
//macro_rules! input_inner {($iter:expr) => {};($iter:expr, ) => {};($iter:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($iter, $t);input_inner!{$iter $($r)*}};}
//macro_rules! read_value {($iter:expr, ( $($t:tt),* )) => {( $(read_value!($iter, $t)),* )};($iter:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()};($iter:expr, chars) => {read_value!($iter, String).chars().collect::<Vec<char>>()};($iter:expr, usize1) => {read_value!($iter, usize) - 1};($iter:expr, $t:ty) => {$iter.next().unwrap().parse::<$t>().expect("Parse error")};}
// 低速 EOF不要
macro_rules! input {(source = $s:expr, $($r:tt)*) => {let mut iter = $s.split_whitespace();let mut next = || { iter.next().unwrap() };input_inner!{next, $($r)*}};($($r:tt)*) => {let stdin = std::io::stdin();let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));let mut next = move || -> String{bytes.by_ref().map(|r|r.unwrap() as char).skip_while(|c|c.is_whitespace()).take_while(|c|!c.is_whitespace()).collect()};input_inner!{next, $($r)*}};}
macro_rules! input_inner {($next:expr) => {};($next:expr, ) => {};($next:expr, $var:ident : $t:tt $($r:tt)*) => {let $var = read_value!($next, $t);input_inner!{$next $($r)*}};}
macro_rules! read_value {($next:expr, ( $($t:tt),* )) => {( $(read_value!($next, $t)),* )};($next:expr, [ $t:tt ; $len:expr ]) => {(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()};($next:expr, chars) => {read_value!($next, String).chars().collect::<Vec<char>>()};($next:expr, usize1) => {read_value!($next, usize) - 1};($next:expr, $t:ty) => {$next().parse::<$t>().expect("Parse error")};}

// 非常時
fn read_line() -> String{ let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); s.trim().to_string() }

/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */
fn main(){
    input!(N:usize,K:usize,h:[usize;N]);
    let N:usize = N;
    let K:usize = K;
    let mut h :Vec<usize> = h;
    h.sort();
    let mut ans = usize::max_value();
    for i in 0..(N-K+1){
        ans = min(ans,h[i+K-1]-h[i]);
    }
    println!("{}",ans);
}

Measured memory_bytes: 4352
def f(x1, x2):
  W = [[i, 1001] for i in range(n)]
  W[x1] = [x1, 0]
  W[x2] = [x2, 2000]
  G = range(n)
  while 1:
    A = sorted([W[e] for e in G], key = lambda x:x[1])
    p1, w1 = A[0]
    G.remove(p1)
    if p1 == x2: break
    for p2, w2 in A[1:]:
      way=(p1, p2)
      if way in cost:
        W[p2] = [p2, min([w2, w1+cost[way]])]
  return W[x2][1]
def g(): return map(int, raw_input().split(","))

n = int(raw_input())
m = int(raw_input())
cost = {}
for _ in [0] * m:
  a, b, c, d = g()
  cost[(a-1, b-1)] = c
  cost[(b-1, a-1)] = d
x1, x2, y1, y2 = g()
x1 -= 1
x2 -= 1
print y1-y2-f(x1,x2)-f(x2,x1)

Measured memory_bytes: 4292
#include <bits/stdc++.h>
using namespace std;
int main () {
  int H, W;
  cin >> H >> W;

  string frame = "";
  for(int i = 0; i < W + 2; i++){
    frame += "#" ;
  }

  cout << frame << endl;
 
  for(int i = 0; i < H; i++){
    string image;
    cin >> image;
    cout << "#" << image << "#" << endl;
  }

  cout << frame << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll N;
  cin >> N;
  ll A = 0, tot = 0;
  map<ll, ll> cnt;
  rep(i, N){
    cin >> A;
    cnt[A]++;
    tot += A;
  }
  ll Q;
  cin >> Q;
  ll B, C;
  vl ans;
  rep(i, Q){
    cin >> B >> C;
    tot += cnt[B] * (C - B);
    ans.push_back(tot);
    cnt[C] += cnt[B];
    cnt[B] = 0;
  }

  rep(i, Q)
    cout << ans[i] << "\n";
  
  return 0;
}


Measured memory_bytes: 9924
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <list>
#include <ctime>
#include <complex>
#include <bitset>
#include <tuple>
using namespace std;

typedef long long int lli;

lli X, rem = 100, ans;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> X;
    for(ans = 0; ; ++ans){
        if(rem >= X)
            break;
        rem = rem + rem / 100;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 62) - 1;

int main(void)
{
    int n;
    
    cin>>n;
    
    if (n%2==1) {
        cout<<n/2+1<<endl;
    }
    else{
        cout<<n/2<<endl;
    }
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var w string
	fmt.Scanf("%s", &w)

	count := make(map[int32]int)

	for _, c := range w {
		if _, ok := count[c]; ok {
			count[c]++
			continue
		}
		count[c] = 1
	}

	ans := true
	for _, v := range count {
		if v%2 != 0 {
			ans = false
			break
		}
	}
	if ans {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#[allow(unused_macros)]
macro_rules! input {
    ( $($t:ty),* ) => {{
        let mut s = String::new();
        std::io::stdin().read_line(&mut s);
        let mut splits = s.trim().split_whitespace();
        ($( { splits.next().unwrap().parse::<$t>().unwrap() },)*)
    }}
}

#[allow(unused_must_use)]
#[allow(unused_variables)]
fn solve() {
    let (n, k, q) = input!(usize, u64, u64);
    let mut a = vec![0; n];

    for _ in 0..q {
        let (ans,) = input!(usize);
        a[ans - 1] += 1;
    }

    for correct in a {
        if k <= q - correct {
            println!("No");
        } else {
            println!("Yes");
        }
    }
}

fn main() {
    solve();
}


Measured memory_bytes: 4732
#include <iostream>

using namespace std;

int main()
{
    int r;
    scanf("%d", &r);
    if(r<=1199)
    {
        printf("ABC");
    }
    else if(r<=2799)
    {
        printf("ARC");
    }
    else
    {
        printf("AGC");
    }
    
}

Measured memory_bytes: 3832
import sys
import numpy as np
from numba import njit

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

@njit
def fact_table(N, MOD):
    inv = np.empty(N, np.int64)
    inv[0] = 0
    inv[1] = 1
    for n in range(2, N):
        q, r = divmod(MOD, n)
        inv[n] = inv[r] * (-q) % MOD
    fact = np.empty(N, np.int64)
    fact[0] = 1
    for n in range(1, N):
        fact[n] = n * fact[n - 1] % MOD
    fact_inv = np.empty(N, np.int64)
    fact_inv[0] = 1
    for n in range(1, N):
        fact_inv[n] = fact_inv[n - 1] * inv[n] % MOD
    return fact, fact_inv, inv

@njit
def main(K, N, MOD):
    fact, fact_inv, inv = fact_table(3_000_000, MOD)
    f = np.zeros(K + 1, np.int64)
    f = fact[N - 1:K + N] * fact_inv[N - 1] % MOD * fact_inv[0:K + 1] % MOD
    x = 1
    for i in range(1, K + 1):
        x = (x * 25) % MOD
        f[i] = f[i] * x % MOD
    for i in range(1, K + 1):
        f[i] += f[i - 1] * 26
        f[i] %= MOD
    return f[-1]

K = int(readline())
N = len(read().rstrip())

print(main(K, N, MOD))

Measured memory_bytes: 185240
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int h,n;
  cin>>h>>n;
  int c,sum=0;
  for(int i=0;i<n;i++)
  {
    cin>>c;
    sum +=c;
  }
  if(sum>=h)
     cout<<"Yes"<<endl;
  else
     cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
from operator import itemgetter
n = int(input())
x =[]
y =[]
info = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
  x.append([i,info[i][0]])
  y.append([i,info[i][1]])

x = sorted(x,key=itemgetter(1))
y = sorted(y,key=itemgetter(1))
tree = []
#for i in range(n):
#  if i==0:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#  elif i==n-1:
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
#  else:
#    tree[x[i][0]].append([x[i+1][0],abs(x[i][1]-x[i+1][1])])
#    tree[x[i][0]].append([x[i-1][0],abs(x[i][1]-x[i-1][1])])
#    tree[y[i][0]].append([y[i+1][0],abs(y[i][1]-y[i+1][1])])
#    tree[y[i][0]].append([y[i-1][0],abs(y[i][1]-y[i-1][1])])
    
for i in range(n-1):
    tree.append([x[i][0],x[i+1][0],abs(x[i][1]-x[i+1][1])])
    tree.append([y[i][0],y[i+1][0],abs(y[i][1]-y[i+1][1])])

#UnionFindクラス
class UnionFind(object):

  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]

  def find(self, x):
  
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
  
  # xとyの根を結合させる
  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)
    if x != y:
      if self.rank[x] < self.rank[y]:
        x, y = y, x
      if self.rank[x] == self.rank[y]:
        self.rank[x] += 1
      self.par[y] = x
  
  # x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
  def is_same(self, x, y):
    return self.find(x) == self.find(y)

uf = UnionFind(len(tree))
tree = sorted(tree,key=itemgetter(2))
ans = 0

for i in tree:
  x,y,kyori = i
  if not uf.is_same(x,y):
    uf.union(y,x)
    ans += kyori
print(ans)


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

int main() {
	int n;
	long long k;
	cin >> n >> k;
	vector<int> a(n), b(n);
	for (int &e : a) { cin >> e; e--; }
	
	int ans = 0;
	
	while (k > 0) {
		if (k & 1) ans = a[ans];
		for (int i = 0; i < n; i++) b[i] = a[a[i]];
		swap(a, b);
		k >>= 1;
	}
	
	cout << ans + 1 << '\n';
	
	return 0;
}

Measured memory_bytes: 4844
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
using ll = long long;
#define int long long
using P = pair<int,int>;
set<int> st;
signed main(){
    int n;cin >> n;
    int p[n];
    rep(i,n)cin >> p[i];
    rep(i,n)p[i]--;
    int idx[n];
    rep(i,n)idx[p[i]] = i;
    //rep(i,n){
    //    cin >> p[i];
    //    p[i]--;
    //    
    //    idx[p[i]] = i;
    //}
    int ans = 0;
    for(int i = n-1;i >= 0;i--){
        int c = 0;
        vector<int> l(2,-1);
        vector<int> r(2,n);
        st.insert(idx[i]);
        {
            auto hoge = st.find(idx[i]);
            rep(j,2){
                if(hoge == st.begin())break;
                hoge--;
                l[j] = *hoge;
            }

        }
        {
            auto hoge = st.find(idx[i]);
            rep(j,2){
                hoge++;
                if(hoge == st.end())break;
                r[j] = *hoge;
            }
            
        }
        vector<int> ls(2),rs(2);
        ls[0] = idx[i] -l[0];
        ls[1] = l[0] - l[1];
        rs[0] = r[0] - idx[i];
        rs[1] = r[1] - r[0];
        c =ls[0]*rs[1]+ls[1]*rs[0];
        



        
        ans += c*(i+1);
    }
    cout << ans << endl;
    
    
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define DIM 107
#define DIMM 100007
#define INF 1000000009.0
#define X 500007
#define epc 0.0000001
#define pi 3.14159265358979323846
#define MAX 25
#define MODULO 10009
const long double gr=(1+sqrt(5))/2;

typedef int I;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

typedef pair<I,I> pII;
typedef pair<ll,ll> pllll;
typedef pair<ld,ld> pldld;

typedef vector<I> vI;
typedef vector<ll> vll;
typedef vector<pllll> vpllll;

typedef char cr;
typedef string str;

typedef tree<
I,
null_type,
less<I>,
rb_tree_tag,
tree_order_statistics_node_update> mset;

ll n,W,sumv,w[DIM],v[DIM],d[DIM][DIMM],maxv;

int main()
{
    //freopen("suffarray.in", "r", stdin);
    //freopen("suffarray.out", "w", stdout);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //cout<<"ops"<<endl;

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //ll x1,y1,xs,ys,y1,y2,x3,x4,y3,y4;

    cin>>n>>W;
    for(int i=1;i<=n;i++){
     cin>>w[i]>>v[i];
     sumv+=v[i];
    }

    for(int j=1;j<=sumv;j++)d[0][j]=INF;

    for(int i=1;i<=n;i++){
     for(int j=0;j<=sumv;j++){
      d[i][j]=d[i-1][j];
      if(j>=v[i] && d[i-1][j-v[i]]!=INF)d[i][j]=min(d[i-1][j-v[i]]+w[i],d[i][j]);
     }
    }
    for(int j=0;j<=sumv;j++)if(d[n][j]<=W && j>maxv)maxv=j;
    cout<<maxv<<endl;
}


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

int parse(string a) {
	int s = 0;
	for (int b = 0; b < a.length(); b++) {
		s *= 10;
		s += a[b] - 48;
	}
	return s;
}
vector<int>split(string a) {
	vector<int>s;
	string b = "";
	for (int c = 0; c < a.length(); c++) {
		if (a[c] == ',') { s.push_back(parse(b)); b = ""; }
		else b += a[c];
	}
	s.push_back(parse(b));
	return s;
}
int main() {
	vector<vector<int>>masu(10,vector<int>(10));
	int xp[5]{ -1,0,0,0,1 };
	int yp[5]{0,-1,0,1,0 };
	int xq[13]{ -2,-1,-1,-1,0,0,0,0,0,1,1,1,2 };
	int yq[13]{ 0,-1,0,1,-2,-1,0,1,2,-1,0,1,0 };
	string a;
	while (cin >> a) {
		vector<int>b;
		b = split(a);
		if (b[2] == 1){
			for (int l = 0; l < 5; l++) {
				if (b[0] + xp[l] < 10 && b[0] + xp[l]>-1 && b[1] + yp[l] < 10 && b[1] + yp[l]>-1)masu[b[0] + xp[l]][b[1] + yp[l]]++;
		}
		}
		else if (b[2] == 2) {
			for (int l = b[0] - 1; l < b[0] + 2; l++) {
				for (int r = b[1] - 1; r < b[1] + 2; r++) {
					if (l < 10 && l>-1 && r < 10 && r>-1) masu[l][r]++;
				}
			}
		}
		else {
			for (int l = 0; l < 13; l++) {
				if (b[0] + xq[l] < 10 && b[0] + xq[l]>-1 && b[1] + yq[l] < 10 && b[1] + yq[l]>-1)masu[b[0] + xq[l]][b[1] + yq[l]]++;
			}
		}
	}
	int zero, n;
	zero = n = 0;
	for (auto j : masu) {
		for (int i : j) {
			if (!i)zero++;
			else if (i > n)n = i;
		}
	}
	cout << zero << endl << n << endl;
}

Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9
#define PI 3.14159265359
#define MOD 1000000007
#define ALL(v) v.begin(),v.end()
#define ALLR(v) v.rbegin(),v.rend()
typedef long long ll;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
//isPrime
//modpow modinv
//getDigit
int main() {
  cout << fixed << setprecision(10);
  int a,b,c;
  cin >> a >> b >> c;
  if(b-a==c-b){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
n, m = map(int, input().split())
ll = 1
rr = n
for i in range(m):
  l, r = map(int, input().split())
  ll = max([ll, l])
  rr = min([rr, r])

if rr-ll+1 < 0:
  print(0)
else:
  print(rr-ll+1)


Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) FOR(i,0,n)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define PQ priority_queue
#define UM unordered_map
#define ALL(a) (a).begin(),(a).end()
typedef vector<ll> vi;
typedef vector<vector<ll>> vvi;
const ll INF = (1ll << 60);
typedef pair<ll,ll> pii;
struct Edge{ll s,t,d; Edge(ll s,ll t,ll d):s(s),t(t),d(d){}};
typedef vector<vector<Edge>> Graph;
typedef vector<pii> vpii;

int main() {
  ll N; cin>>N;
  vi a(N); REP(i,N) cin>>a[i];
  ll asum=0; REP(i,N) asum+=a[i];
  ll x=max(0ll,asum-N*N);
  while(1) {
    ll y=0;
    REP(i,N) y+=(x+1+a[i])/(N+1);
    if(y<=x) {cout<<x<<endl; return 0;}
    x++;
  }
}


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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

static inline ll f(ll x) {
    if (x == -1) return 0;
    if (x % 4 == 0) return x;
    if (x % 4 == 1) return 1;
    if (x % 4 == 2) return x + 1;
    return 0;
}

ll a, b;
int main() {
    cin >> a >> b;
    cout << (f(b) ^ f(a - 1)) << endl;
    return 0;
}


Measured memory_bytes: 3660
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) (a).begin(), (a).end()


int main() {
    char s;
    cin >> s;
    if(s == 'A') puts("T");
    else if(s == 'T') puts("A");
    else if(s=='G') puts("C");
    else puts("G");
}


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

#define llong long long /*{{{*/
#define ii pair<int, int>
#define xx first
#define yy second
#define len(x) ((int)x.size())
#define rep(i,n) for (int i = -1; ++ i < n; )
#define rep1(i,n) for (int i = 0; i ++ < n; )

template<typename a> ostream& operator<<(ostream& cout, const vector<a>& b) {
  cout << "[";
  if (len(b)) cout << b[0];
  rep1(i, len(b) - 1) cout << ", " << b[i];
  return cout << "]";
}

template<typename u, typename v> ostream& operator<<(ostream& cout, const pair<u, v> a) {
  return cout << "(" << a.xx <<", " << a.yy << ")";
}/*}}}*/

#define maxn 111
int n;
int x[maxn], y[maxn], h[maxn];
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n;
  int n0 = -1;
  rep(i, n) {
    cin >> x[i] >> y[i] >> h[i];
    if (h[i]) n0 = i;
  }
  if (n0 == -1) {
    cout << "0 0 1";
    return 0;
  }

  rep(u, 101) rep(v, 101) {
    int ch = h[n0] + abs(u - x[n0]) + abs(v - y[n0]);
    bool ok = true;
    rep(i, n) {
      if (max(ch - abs(u - x[i]) - abs(v - y[i]), 0) != h[i]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      cout << u << ' ' << v << ' ' << ch;
      return 0;
    }
  }
  
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n,k;
  cin>>n>>k;
  int p[n],c[n],nex;
  int ans=(-2000000000);
  rep(i,n){cin>>p[i];p[i]--;}
  rep(i,n){cin>>c[i];ans=max(ans,c[i]);}
  rep(i,n){
    int cnt=1;
    int np=p[i];
    while(np!=i){
      np=p[np];
      cnt++;
    }
    //cout<<cnt<<" "<<i<<endl;
    nex=p[i];
    int rop=(k-1)/cnt;
    int amari=k%cnt;
    int table,table2;
    if(amari==0) amari=cnt;
    //cout<<rop<<" "<<amari<<endl;
    rep(j,cnt){
      if(j==0) table2=c[nex];
      else table2=table2+c[nex];
      if(j<k) ans=max(ans,table2);
      nex=p[nex];
    }
    nex=p[i];
    
    if(table2>0){
      table=table2*rop;
      ans=max(ans,table);
      
      rep(j,amari){
	
	table=table+c[nex];
	ans=max(ans,table);
	nex=p[nex];
      }
    }
  }
  cout<<ans<<endl;

  return 0;
}


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

char x[] = { 'a', 'i', 'u', 'e', 'o' };

int main() {
	bool flag = false;
	char c;
	cin >> c;
	for (int i = 0; i < 5; i++) {
		if (x[i] == c)flag = true;
	}

	if (flag) {
		cout << "vowel" << endl;
	}
	else {
		cout << "consonant" << endl;
	}
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>

using namespace std;

int main() {

	int A = 0;
	int B = 0;
	int C = 0;
	int maxnum = 0;

	cin >> A >> B >> C;

	if (A % 2 == B % 2 && B % 2 == C % 2) {

		maxnum = max({ A, B, C });

		cout << (maxnum * 3 - A - B - C) / 2 << endl;

	}
	else {

		if (A % 2 == B % 2) {

			A++;
			B++;

		}
		else {

			if (A % 2 == C % 2) {

				A++;
				C++;

			}
			else {

				B++;
				C++;

			}

		}

		maxnum = max({ A, B, C });

		cout << 1 + (maxnum * 3 - A - B - C) / 2 << endl;

	}

	return 0;

}

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

using namespace std;

//typedef pair<int, int> P;
#define int long long
#define ll long long
#define mod 1000000007
#define INF (1LL<<60)


signed main(){

	int N, M;
	int a[1000], b[1000];

	cin >> N >> M;
	for (int i = 0; i < N; i++) cin >> a[i];
	for (int i = 0; i < M; i++) cin >> b[i];

	sort(a, a + N);
	sort(b, b + M);

	int ans = 1;
	for (int n = N*M; n >= 1; n--){
		
		int su = upper_bound(a, a + N, n) - a;
		int sl = lower_bound(a, a + N, n) - a;
		int tu = upper_bound(b, b + M, n) - b;
		int tl = lower_bound(b, b + M, n) - b;

		if (su-sl>1 || tu-tl>1){ 
			cout << 0 << endl; return 0; }
		if (su-sl == 1 && tu-tl == 1) ans *= 1;
		else if (su - sl == 1) (ans *= (M-tu))%=mod;
		else if (tu - tl == 1) (ans *= (N-su))%=mod;
		else (ans *= (M - tu)*(N - su) - (N*M - n))%=mod;
	}

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


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner((System.in));
		int N = sc.nextInt();
		long ans = N % 1000000007;

		for (int i = N-1; i > 0; i--) {
			ans = ans*i%1000000007;

		}
		System.out.println(ans);
		sc.close();
	}
}


Measured memory_bytes: 21972
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>

#include <iostream>
#include <string>

#include <algorithm>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <vector>

#define PB push_back
#define MP make_pair

#define FOR(i, b, e) for(int i=(b);i<(e);i++)
#define REP(i, n) FOR(i,0,n)

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> PII;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VPII;

const int MOD = 1000000007;
const int INF = 1e9;

const double EPS = 1e-9;
const double PI = acos(-1.0);

LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; }
LL lcm(LL a, LL b) { return a / gcd(a, b) * b; }

int N, A;

map<int, int> m;

int main() {
    cin >> N;
    REP (i, N) {
        cin >> A;
        m.insert(MP(A, i + 1));
    }
    REP (i, N - 1) {
        cout << m.at(i + 1) << ' ';
    }
    cout << m.at(N) << endl;
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  vector<int> b(n);
  long long csum=0;
  for(int i=0;i<n;i++) {
    cin >> a.at(i);
  }
  for(int i=0;i<n;i++) {
    cin >> b.at(i);
  }
  vector<int> c(n);
  long long msum=0;
  int mnum=0;
  for(int i=0;i<n;i++) {
    c[i]=a[i]-b[i];
    csum+=c[i];
    if(c[i]<0) {
      msum+=c[i];
      mnum++;
    }
  }
  sort(c.rbegin(), c.rend());
  vector<long long> psum(n);
  for(int i=0;i<n;i++) {
    if(i==0) {
      psum.at(i)=c.at(i);
    }
    else {
      psum.at(i)=psum.at(i-1)+c.at(i);
    }
  }
  if(csum<0) {
    cout << -1 << endl;
  }
  else if(mnum==0) {
    cout << 0 << endl;
  }
  else {
    for(int i=0;i<n;i++) {
      if(psum.at(i)+msum>=0) {
        cout << mnum+i+1 << endl;
        break;
      }
    }
  }
}

Measured memory_bytes: 2176
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    def f(x):
        tmp = a[x]
        for i in range(n):
            if i != x:
                if tmp * 2 >= a[i]:
                    tmp += a[i]
                else:
                    return False
        return True
    n = II()
    a = LI()
    a.sort()
    ok = n - 1
    ng = -1
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(n - ok)
    return


#main
if __name__ == '__main__':
    solve()


Measured memory_bytes: 61936
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <numeric>
#include <regex>
#include <tuple>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
#define MOD 1000000007 // 10^9 + 7
#define INF 1000000000 // 10^9
#define LLINF 1LL<<60


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

	int N;
	int H[21];
	int ans = 0;
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> H[i];
	H[0] = 0;

	for (int i = 1; i <= N; i++) {
		bool flag = true;
		for (int j = 0; j < i && flag; j++) {
			if (H[j] > H[i]) flag = false;
		}
		if (flag) ans++;
	}

	cout << ans << endl;


	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//#define int long long

template <class T>
bool INRANGE(T x, T a, T b) { return a <= x && x <= b; }
template <class T>
bool chmax(T &a, const T &b) {if (a < b){ a = b; return 1;} return 0;}
template <class T>
bool chmin(T &a, const T &b) {if (a > b){ a = b; return 1;}return 0;}
template <class T>
void printv(vector<T> v) {for (T t : v) {cout << t << " ";}cout << '\n';}

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); 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(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" <<endl;

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

int main()
{
    string s;
    cin >> s;

    if (s == "Sunny") {
        cout << "Cloudy" << endl;
    } else if (s == "Rainy") {
        cout << "Sunny" << endl;
    } else {
        cout << "Rainy" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
  
int main() {
  int N,M;
  cin >> N >> M;
  vp key(M);
  rep(i,M) {
    int a,b;
    cin >> a >> b;
    int s = 0;
    rep(j,b) {
      int c;
      cin >> c;
      c--;
      s |= 1<<c;
    }
    key[i] = P(s,a);
  }
  vi dp(1<<N,INF);
  dp[0] = 0;
  rep(s,1<<N) {
    rep(i,M) {
      int t = s | key[i].first;
      int c = dp[s] + key[i].second;
      dp[t] = min(dp[t],c);
    }
  }
  int ans = dp.back();
  if(ans == INF) ans = -1;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
using System;

namespace abc087_b
{
    class Program
    {
        static void Main(string[] args)
        {
            int a = int.Parse(Console.ReadLine());
            int b = int.Parse(Console.ReadLine());
            int c = int.Parse(Console.ReadLine());
            int x = int.Parse(Console.ReadLine());
            int ret = 0;
            for (int i = 0; i <= a; i++)
            {
                for (int j = 0; j <= b; j++)
                {
                    for (int k = 0; k <= c; k++)
                    {
                        if (i * 500 + j * 100 + k * 50 == x) ret++;
                    }
                }
            }
            Console.WriteLine(ret);
        }
    }
}

Measured memory_bytes: 11092
#include <vector>

using namespace std;

typedef vector<int> vi;

// ?????£?????????????§£ (Strongly Connected Component)
// ????????°???????????°????????????????????£??¬??????????????? ???????????§
struct SCCGraph: public vector<vi> {

	vector<int> order;    // ?±????????????£??????????????????(????????????????????????????????£?????????) ??????????????????????????????-1
	vector<int> vs;       // ??°????????????

	using vector::vector;	// ?¶?????????????????????????
	SCCGraph(const vector<vi> &v): vector::vector(v) {}	// ??????????????????????????????????????¨???????????????

	// a -> b ????????????????????????push_back()??§?????????
	void add_edge(int a, int b){
		(*this)[a].push_back(b);
	}

	// scc()??§??????
	void dfs(int n, int k, vector<vi> &v, vector<vi> &rv){
		order[n] = k;
		for(auto t: v[n]){
			rv[t].push_back(n);	// ???????????°???????????????
			if( order[t] < 0 ) dfs(t, k, v, rv);
		}
		vs.push_back(n);
	}

	// ?????£?????????????§£?????????
	int scc(){
		int N = size();
		order.assign(N, -1);
		vs.clear();
		vector<vi> rG(N), tmp(N);   // ????????????????????°????????¨
		for(int n=0; n < N; n++){
			if( order[n] < 0 ) dfs(n, n, (*this), rG);
		}
		order.assign(N, -1);
		int k = 0;		// ?????£??????????????????
		for(int i = vs.size()-1; i >= 0; i--){
			if( order[ vs[i] ] < 0 ) dfs(vs[i], k++, rG, tmp);
		}
		return k;
	}

	// ?±????????????£????????????????????????????????????
	bool find(int x, int y){
		return order[x] == order[y];
	}

};
// ??¢??°??¨??????scc??????????????????????????????????????????????±????????????£??????????????????
vector<int> scc(const vector<vi> &v){
	SCCGraph g(v);
	g.scc();
	return g.order;
}



// test
// AOJ GRL_3_C (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_C&lang=jp)
#include <iostream>
#define rep(i,n) for(int i=0; i<(n); i++)
int main(){
	int V, E;
	SCCGraph graph(10005);

	cin >> V >> E;
	rep(i,E){
		int s, t;
		cin >> s >> t;
		graph.add_edge( s, t );
	}

	graph.scc();
	//rep(i,V) cout << "graph: " << i << " " << graph.order[i] << endl;

	int Q;
	cin >> Q;
	rep(i,Q){
		int u, v;
		cin >> u >> v;
		cout << (int)graph.find(u, v) << endl;
	}

	return 0;
}

// scc()??¢??°????????¨????????????
/*
int main(){
	int V, E;
	vector<vi> edge(10005);

	cin >> V >> E;
	rep(i,E){
		int s, t;
		cin >> s >> t;
		edge[s].push_back( t );
	}

	auto g = scc(edge);

	int Q;
	cin >> Q;
	rep(i,Q){
		int u, v;
		cin >> u >> v;
		cout << (int)(g[u] == g[v]) << endl;
	}

	return 0;
}
*/

Measured memory_bytes: 4928
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws InterruptedException {
		FastScanner fs=new FastScanner();
		int n=fs.nextInt();
		int k=fs.nextInt();
		int[] a=fs.readArray(n);
		int min=1, max=(int)1e9+100;
		while (min!=max) {
			int mid=(min+max)/2;
			if (possible(mid, a, k)) {
				max=mid;
			}
			else {
				min=mid+1;
			}
		}
		System.out.println(min);
	}
	
	static boolean possible(int ans, int[] a, int k) {
		for (int i:a) {
			k-=(i+ans-1)/ans-1;
		}
		return k>=0;
	}
	
	void sort(int[] a) {
		ArrayList<Integer> list=new ArrayList<>();
		for (int i:a) list.add(i);
		Collections.sort(list);
		for (int i=0; i<a.length; i++) a[i]=list.get(i);
	}
	
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		
		public String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
			
		}
		
		public int nextInt() {
			return Integer.parseInt(next());
		}
		
		public int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
		
		public long[] readLongArray(int n) {
			long[] a=new long[n];
			for (int i=0; i<n; i++) a[i]=nextLong();
			return a;
		}
	}

}


Measured memory_bytes: 55020
N, M = map(int, input().split())
lists = []
for _ in range(M):
    lists.append(list(map(int, input().split()))[1:])
p_list = list(map(int, input().split()))
num = 0
len_m = N
for n in range(2 ** N):
    flag = True
    for p, lis in zip(p_list, lists):
        flag = int(flag) * int((sum([str(bin(n)[2:]).zfill(len_m)[l - 1] == '1' for l in lis]) % 2) == p)
    num += flag
print(num)


Measured memory_bytes: 3064
num = list(map(int,input().split()))
num.sort(reverse=True)
M = max(num)
l = [M-i for i in num]
gap = l[2] - l[1]
ans = 0

if gap % 2 == 0:
    ans = l[1] + int(gap/2)
else:
    ans = l[1] + int(gap/2)+2
print(ans)

Measured memory_bytes: 9156
/**
 *    author:  otera    
**/
#include<iostream>
#include<string> 
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm> 
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

//#define int long long
typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void solve() {
	int a, b; string s; cin >> a >> b >> s;
    rep(i, a + b + 1) {
        if(i < a) {
            if('0' <= s[i] && s[i] <= '9') continue;
            else {
                cout << "No" << endl;
                return;
            }
        } else if(i == a) {
            if(s[i] != '-') {
                cout << "No" << endl;
                return;
            }
        } else {
            if('0' <= s[i] && s[i] <= '9') continue;
            else {
                cout << "No" << endl;
                return;
            }
        }
    }
    cout << "Yes" << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//int t; cin >> t; rep(i, t)solve();
	solve();
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <set>
#define repi(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,a) repi(i,0,a)

constexpr int MAX_N = 200000;

using ll = long long;

int N;
ll a[MAX_N];
ll p[MAX_N+1];
std::set<ll> S;

int main()
{
  scanf( "%d", &N );
  rep( i, N )
    scanf( "%lld", a+i ), p[a[i]] = i+1;

  S.insert( 0 );
  S.insert( N+1 );

  ll ans = 0;
  repi( i, 1, N+1 )
  {
    auto it = S.lower_bound( p[i] );
    ll r = *it;
    --it;
    ll l = *it;
    ans += (r-p[i])*(p[i]-l)*(ll)i;
    S.insert( p[i] );
  }

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

  return 0;
}

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

// 最大公約数
ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

// 最小公倍数
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

int main() {
    int n;
    cin >> n;
    int a;
    int l = 1;
    for (int i = 0; i < n; i++) {
        cin >> a;
        l = lcm(l, a);
    }
    cout << l << "\n";  
    return 0;
}


Measured memory_bytes: 3116
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <string>
#include <queue>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define P pair<int,int>
#define vsort(v) sort(v.begin(),v.end)
using namespace std;
signed main() {
	int n, in, cnt = 0;
	cin >> n;
	rep(i, n) {
		cin >> in;
		if (in % 2 == 0)cnt++;
	}
	cout << cnt << endl;
}


Measured memory_bytes: 3088
#include<stdio.h>
#include<string.h>
const char c[]={'m','c','x','i'};
const int v[]={1000,100,10,1};

int decode(char s[]){
	int x=0;
	int n;
	int tmp=1;
	int i,j;

	n=strlen(s);

	for(i=0;i<n;i++){
		if(s[i]>='0' && s[i]<='9'){
			tmp=s[i]-'0';
			continue;
		}
		for(j=0;j<4;j++){
			if(s[i]==c[j]){
				x=x+v[j]*tmp;
				tmp=1;
				break;
			}
		}
	}
	return x;
}
void encode(int sum){
	int i;
	int d;

	for(i=0;i<4;i++){
		d=0;
		while(sum>=v[i]){
			sum-=v[i];
			d++;
		}
		if(d>1){
			printf("%d",d);
		}
		if(d>0){
			printf("%c",c[i]);
		}
	}
		printf("\n");
	return;
}
int main(void){
	char s1[1024],s2[1024];
	int sum;
	int n;

	scanf("%d",&n);
	fflush(stdin);
	while(n--){
	scanf("%s %s",s1,s2);
	sum=decode(s1)+decode(s2);
	encode(sum);
	}
	return 0;
}

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

using namespace std;
int n;
int a[100000][4];
int dp[1000002][4];
int mincost(int x,int ty)
{
	if(dp[x][ty]!=-1)
		return dp[x][ty];
	if(x==n)
	{
		dp[x][ty]=0;
	}
	else if(ty==1)
	{
		dp[x][ty]=max(mincost(x+1,2)+a[x+1][2],mincost(x+1,3)+a[x+1][3]);
	}
	else if(ty==2)
	{
		dp[x][ty]=max(mincost(x+1,1)+a[x+1][1],mincost(x+1,3)+a[x+1][3]);
	}
	else if(ty==3)
	{
		dp[x][ty]=max(mincost(x+1,2)+a[x+1][2],mincost(x+1,1)+a[x+1][1]);
	}
	return dp[x][ty];

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

	}
	cout<<max(mincost(1,1)+a[1][1],max(mincost(1,2)+a[1][2],mincost(1,3)+a[1][3]));
	cout<<'\n';
}

Measured memory_bytes: 9344
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
typedef struct pair<int,int> P;
typedef long long ll;
bool k[100001]={};
ll x[100001];
ll y[100001];
int main() {
	int n,m;
	cin>>n>>m;
	int a[51]={};
	int b[51]={};
	int c[51]={};
	int d[51]={};
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];
	for(int i=0;i<m;i++)cin>>c[i]>>d[i];
	for(int i=0;i<n;++i){
		int t=500000000;
		int r=0;
		for(int j=0;j<m;++j){
			if(t>(abs(a[i]-c[j])+abs(b[i]-d[j]))){
				t=abs(a[i]-c[j])+abs(b[i]-d[j]);
				r=j+1;
			}
		}
		cout<<r<<endl;
	}
	return 0;
}


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


int main(){
    long long t_k,t_t,a_k,a_t;
    bool aoki = true;
 
    cin >> t_t >> t_k >> a_t >> a_k;

  while(t_t > 0 && a_t > 0){
    if(aoki == true){
      a_t -= t_k;
      aoki = false;
    }else{
      t_t -= a_k;
      aoki = true;
    }
  }

  if(aoki == true){
    cout << "No";
  }else{
    cout << "Yes";
  }
}

Measured memory_bytes: 3592
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int w = sc.nextInt();
        for (int i = 0; i < s.length(); i += w) {
            System.out.print(s.charAt(i));
        }
    }
}


Measured memory_bytes: 36328
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <string.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define INF 2147483647
#define LLINF 9223372036854775807
typedef long long ll;
using namespace std;
int main(){
	ll n,m;
	cin>>n>>m;
	if(n==1||m==1){
		cout<<1<<endl;
		return 0;
	}
	ll ans=(n+1)/2;
	ans*=(m+1)/2;
	ll cnt=n/2;
	cnt*=m/2;
	cout<<ans+cnt<<endl;
	return 0;
}

Measured memory_bytes: 256