akhauriyash/Code-Regression huggingface dataset:
input_line = input().split()
a = int(input_line[0])
b = int(input_line[1])
c = int(input_line[2])
k = int(input_line[3])

def return_answer(a,b,c,k):
    answer = 0
    if a < k:
        answer += a
        count = k - a

        if b < k:
            count -= b
            answer -= count

    elif a >= k:
        answer = k

    return answer

print(return_answer(a,b,c,k))


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

int main(){
  int n;
  cin >> n;
  char a[n];
  for(int i=0;i<n;i++){
    cin >> a[i];
  }
  int ans=0;
  for(int i=0;i<n-2;i++){
    if(a[i] == 'A' && a[i+1] == 'B' && a[i+2] == 'C' ){++ans;}
  }
  cout << ans << endl;
}

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w,K = LI()
s = [input() for _ in range(h)]

ans = inf
for i in range(2**(h-1)):
    bit = [0]*(h-1)
    cnt = 0
    for j in range(h-1):
        if (i >> j) & 1:
            bit[j] = 1
            cnt += 1
    lst = [[0]*w for _ in range(cnt+1)]
    preans = cnt
    C = cnt
    tmp = 0
    cnt = 0
    for j in range(h-1):
        if bit[j]:
            for l in range(w):
                for k in range(tmp, j+1):
                    if s[k][l] == '1':
                        lst[cnt][l] += 1
            tmp = j+1
            cnt += 1

    for j in range(w):
        for k in range(tmp,h):
            if s[k][j] == '1':
                lst[-1][j] += 1
    T = [0]*(C+1)
    flg = True
    for k in range(w-1):
        for j in range(C+1):
            T[j] += lst[j][k]
            if lst[j][k] > K:
                flg = False
            if T[j] + lst[j][k+1] > K:
                preans += 1
                T = [0]*(C+1)
                break
    for j in range(C+1):
        if lst[j][-1] > K:
            flg = False
    if flg:
        ans = min(ans, preans)
print(ans)
            


Measured memory_bytes: 49756
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <climits>
#include <math.h>
#include <bitset>

#define X first
#define Y second
#define vsort(v) sort(v.begin(), v.end())
#define vrev(v) reverse(v.begin(), v.end())
#define vmax_p(v) max_element(v.begin(), v.end())
#define vmin_p(v) min_element(v.begin(), v.end())
#define vmax_idx(v) distance(v.begin(), vmax_p(v))
#define vmin_idx(v) distance(v.begin(), vmin_p(v))
#define vcopy(src, dst) copy(src.begin(), src.end(), back_inserter(dst))
#define P pair

// stoi(s): string to int
// stod(s): string to double

// INT_MAX
// INT_MIN
// LLONG_MAX
// LLONG_MIN
// DBL_MIN
// DBL_MAX
// LDBL_MIN
// LDBL_MAX

// A-Z: 65~90
// a-z: 97~122
// |a-z| = 26

// 2進数変換
// string s = bitset<20>(x).to_string();

using namespace std;
using ll = long long;

void display_vec(vector<int> v)
{
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << endl;
    }
    cout << endl;
}

int main(int argc, const char *argv[])
{
    int a, b, c;
    cin >> a >> b >> c;
    if (c > a && c < b || c > b && c < a)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
import sys

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

def main():
    s = S()
    if s == "Sunny":
        print("Cloudy")
    elif s == "Cloudy":
        print("Rainy")
    else:
        print("Sunny")

if __name__ == '__main__':
    main()

Measured memory_bytes: 3064
import java.io.BufferedReader;
import java.io.Closeable;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Map.Entry;

import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;


public class Main {
	
	public static void main(String[] args) throws IOException {	
		try(final Scanner sc = new Scanner(System.in)){
			System.out.println(1 - sc.nextInt());
		}
	}

	public static class Scanner implements Closeable {
		private BufferedReader br;
		private StringTokenizer tok;

		public Scanner(InputStream is) throws IOException {
			br = new BufferedReader(new InputStreamReader(is));
		}

		private void getLine() throws IOException {
			while(!hasNext()){
				tok = new StringTokenizer(br.readLine());
			}
		}

		private boolean hasNext() {
			return tok != null && tok.hasMoreTokens();
		}

		public String next() throws IOException {
			getLine();
			return tok.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public int[] nextIntArray(int n) throws IOException {
			final int[] ret = new int[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextInt();
			}
			return ret;
		}

		public long[] nextLongArray(int n) throws IOException {
			final long[] ret = new long[n];
			for(int i = 0; i < n; i++){
				ret[i] = this.nextLong();
			}
			return ret;
		}

		public void close() throws IOException {
			br.close();
		}
	}
}


Measured memory_bytes: 32712
def main():
    import sys
    input = sys.stdin.readline
    A, V = [int(x) for x in input().strip().split()]
    B, W = [int(x) for x in input().strip().split()]
    T = int(input())
    if A == B:
        print('YES')
        return
    if W > V:
        print('NO')
        return
    if (V - W) * T >= abs(A - B):
        print('YES')
    else:
        print('NO')

if __name__ == '__main__':
    main()

Measured memory_bytes: 9188
import java.util.Arrays;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        sc.nextLine();
        int[] arr = Arrays.stream(sc.nextLine().split("\\s")).mapToInt(Integer::parseInt).sorted().toArray();
        double prev = arr[0];
        for (int i = 1; i < arr.length; i++) {
            int next = arr[i];
            prev = (prev + next) / 2.0;
        }
        System.out.println(prev);
    }
}

Measured memory_bytes: 29012
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define INF 0x3f3f3f3f
#define mod 1000000009
#define e  2.718281828459045
#define eps 1.0e18
#define PI acos(-1)
#define lowbit(x) (x&(-x))
#define memset(x,y) memset(x,y,sizeof(x))
#define lson i << 1,l,m
#define rson i << 1 | 1,m + 1,r
#define ll long long
using namespace std;
int main(){
	ios::sync_with_stdio(false);
	string s1,s2;
	int n1,n2;
	cin>>s1>>s2;
	cin>>n1>>n2;
	string x;
	cin>>x;
	if(x==s2) cout<<n1<<" "<<n2-1;
	else cout<<n1-1<<" "<<n2;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");

private:
	using ll = long long;

	int v;

	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}

public:

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}

	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}

	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};
using num = modnum<int(1e9)+7>;

const int MAXN = 2.1e5;
const int MAXC = 2.1e5;
int N;
int C[MAXN];
num dp[MAXC];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> C[i];
	}
	N = int(unique(C, C + N) - C);
	
	num curCnt = 1;
	for (int i = 0; i < N; i++) {
		dp[C[i]] += curCnt;
		curCnt = dp[C[i]];
	}
	cout << curCnt << '\n';

	return 0;
}


Measured memory_bytes: 1920
N = int(input())
A = list(map(int, input().split()))
A = [list(map(int, list('{:031b}'.format(x)))) for x in A]
total = []
for B in zip(*A):
    total.append(sum(B))

ans = []
for a in A:
    tmp = []
    for i in range(31):
        tmp.append(str((total[i]-a[i])%2))
    ans.append(int(''.join(tmp), 2))
print(*ans)

Measured memory_bytes: 242556
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using ll = long long;
ll d=1e9+7;

int main(){
    int n;cin>>n;
    ll A[n],B[n];
    rep(i,n){cin>>A[i];B[i]=A[i];}
    for(int i=1;i<n;i++){
        A[i]+=A[i-1];
        A[i]%=d;
    }
    ll ans=0;
    for(int j=1;j<n;j++){
        ans+=B[j]*(A[j-1]);
        ans%=d;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6740
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
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; }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1, 0), ans;
    rep(i,n) cin >> a[i+1];
    for(int i = n; i > 0; --i){
        int sum = 0;
        for(int j = i+i; j <= n; j += i){
            sum += b[j];
        }
        if(sum%2 == a[i]) b[i] = 0;
        else{
            b[i] = 1;
            ans.push_back(i);
        }
    }
    cout << ans.size() << endl;
    for(auto p : ans){
        cout << p << " ";
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 5252
import numpy as np

N = int(input())

ans = N
res = 0
for i in range(N+1):
    res = 0
    t = i
    while t > 0:
        res += t%6
        t //= 6
    t = N - i
    while t > 0:
        res += t%9
        t //= 9

    if res < ans:
        ans = res



print(ans)


Measured memory_bytes: 12396
/**
     **author : _KMS_
     **created : 05-03-2020
**/
#include<bits/stdc++.h>
using namespace std;
const long long M =6e5,MOD=1e9+7;
typedef long long ll;
string s,p="",q;
map<ll,ll>mp;
ll k;
int main() {
      
   ios::sync_with_stdio(false);
   cin.tie(0);
          int x1, y1, x2, y2;
	cin>>x1>>y1>>x2>>y2;
	int h = y2 - y1;
	int w = x2 - x1;
	for(int i = 0; i < h; i++)
	{
		cout<<"U";
	}
	for(int i = 0; i < w; i++)
	{
		cout<<"R";
	}
	for(int i = 0; i < h; i++)
	{
		cout<<"D";
	}
	for(int i = 0; i < w; i++)
	{
		cout<<"L";
	}
	cout<<"D";
	for(int i = 0; i < w + 1; i++)
	{
		cout<<"R";
	}
	for(int i = 0; i < h + 1; i++)
	{
		cout<<"U";
	}
	cout<<"L";
	cout<<"U";
	for(int i = 0; i < w + 1; i++)
	{
		cout<<"L";
	}
	for(int i = 0; i < h + 1; i++)
	{
		cout<<"D";
	}
	cout<<"R";
	cout<<'\n';
         
  
   
   return 0;
}

Measured memory_bytes: 256
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <functional>
#include <numeric>
#include <math.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void) {
	int N, M, X;
	cin >> N >> M >> X;
	vector<int> C(N);
	vector<vector<int>> A(N, vector<int>(M));
	int ans = 0;
	for (int i = 0; i < N; i++) {
		cin >> C.at(i);
		ans += C.at(i);
		for (int j = 0; j < M; j++) {
			cin >> A.at(i).at(j);
		}
	}
	//bit全探索
	int ok = 0;
	for (int bit = 0; bit < (1<<N); bit++) {
		int tmp = 0;
		vector<int> vec(M);
		for (int i = 0; i < N; i++) {
			if (bit & (1 << i)) {
				for (int j = 0; j < M; j++) {
					vec.at(j) += A.at(i).at(j);
				}
				tmp += C.at(i);
			}
		}
		int flag = 0;
		for (int i = 0; i < M; i++) {
			if (vec.at(i) < X) flag++;
		}
		if (flag == 0) {
			ans = min(ans, tmp);
			ok++;
		}
	}
	if(ok) cout << ans << endl;
	else cout << -1 << endl;
	return 0;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define ull unsigned long long int
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define mx *max_element
#define mn *min_element
#define fo(i,n) for(ll i=0;i<n;i++)
#define of(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sortall(x) sort(all(x))
#define mem(x,p) memset(x,p,sizeof(x))
#define w(t) ll t;cin>>t;while(t--)
#define kk "\n"
const ll mod=1e9+7;
int main()
{
  IOS
  ll n,m,x;
  cin>>n>>m>>x;
  ll c[n],a[n][m];
  fo(i,n)
  {
    cin>>c[i];
    fo(j,m)
    cin>>a[i][j];
  }
  vector <ll> v;
  for(ll i=1;i<=1ll<<n;i++)
  {
    bitset <15> b(i);
    ll aa[m]={0};ll s=0;
    for(ll j=0;j<15;j++)
    {
      if(j>=n)
        break;
      if(b[j])
      {
        s+=c[j];
        for(ll k=0;k<m;k++)
          aa[k]+=a[j][k];
      }
    }
    ll f=0;
    for(ll j=0;j<m;j++)
    {
      if(aa[j]<x)
      {
        f=1;
        break;
      }
    }
    if(!f)
      v.pb(s);
  }
  if(!v.size())
  {
    cout<<-1;
    return 0;
  }
  sortall(v);
  cout<<v[0];
  return 0;
}


Measured memory_bytes: 3704
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define mod (1000000000+7)
#define N (10007)
#define INF 1e16
typedef long long ll;
typedef pair<ll,ll> P;


int main(void){
	int n;
	string s;
	while(true){
		cin>>n;
		if(n==0)break;
		int l=0,r=0,now=0;
		int ans=0;
		for(int i=0;i<n;i++){
			cin>>s;
			if(s=="lu")l++;
			if(s=="ld")l--;
			if(s=="ru")r++;
			if(s=="rd")r--;
			if(now==0){
				if(l==1&&r==1){
					ans++;
					now=1;
				}
			}
			else{
				if(l==0&&r==0){
					ans++;
					now=0;
				}
			}
		}
		cout<<ans<<endl;
	}
    return 0;
}


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

using ll = long long;
using ull = unsigned long long;
const int inf = 2e9;
const ll INF = 4e18;
const ll MOD = 1e9+7;

int n, k;
bool dp[100010];
int a[110];

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

  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j < n; j++) {
      if (i + a[j] > k) continue;
      dp[i+a[j]] |= (!dp[i]);
    }
  }
  cout << (dp[k]? "First": "Second") << endl;
  return 0;
}


Measured memory_bytes: 384
#include <stdio.h>

int main()
{
    long long K;
    long long A;
    long long B;

    scanf("%lld %lld %lld", &K, &A, &B);

    if(A >= B) {
        printf("%lld\n", 1 + K);
        return 0;
    }

    if((B-A) == 1) {
        printf("%lld\n", 1 + K);
        return 0;
    }

    K -= (A-1);
    if((K%2) == 1) {
        printf("%lld\n", A+(B-A)*(K/2) + 1);
    } else {
        printf("%lld\n", A+(B-A)*(K/2));
    }

    return 0;
}

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

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

signed main(){
    int n,k;
    cin>>n>>k;
    int res=0;
    for(int i=0;i<k;i++){
        if((i+1)*2%k!=0)continue;
        int t=0;
        for(int a=i+1;a<=n;a+=k){
            t++;
        }
        res+=t*t*t;
    }
    cout<<res<<endl;
}


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

int main()
{	
	while(true){
		int n,a[10000]={},b[10000]={},ascore=0,bscore=0;
		cin>>n;
		if(n==0) break;
		for(int i=0;i<n;i++){
			cin>>a[i];
			cin>>b[i];
			if(a[i]>b[i]){
				ascore+=a[i]+b[i];
			}else if(a[i]<b[i]){
				bscore+=a[i]+b[i];
			}else if(a[i]==b[i]){
				ascore+=a[i];
				bscore+=b[i];
			}
		}
		cout<<ascore<<" "<<bscore<<endl;
	}
	return 0;
}

Measured memory_bytes: 1244
def func(x,y):
    return  x+y

class SegmentTree:
    def __init__(self, n): #a1, a2, ..., an
        n_ = 1
        while n_ < n:
            n_ *= 2

        self.n = n_
        self.arr = [0] * (2*self.n-1)

    def update(self, k, a): #0_indexed
        k += self.n - 1
        self.arr[k] += a

        while k > 0:
            k = (k-1) // 2
            self.arr[k] = func(self.arr[2*k+1], self.arr[2*k+2])

    def query(self, l, r):#[l,r)の値を返す
        L, R = l+self.n, r+self.n
        res = 0
         #ex) 最小値のセグ木 → +inf
         #　和のセグ木 → 0
         #　積のセグ木 → 1
         #  gcdのセグ木 → 0

        while L < R:
            if R & 1:
                R -= 1
                res = func(res, self.arr[R-1])

            if L & 1:
                res = func(res, self.arr[L-1])
                L += 1

            L >>= 1
            R >>= 1

        return res
#0-indexedな気がする
n,q=map(int,input().split())
sg=SegmentTree(n)
for _ in range(q):
    c,x,y=map(int,input().split())
    if c==0:
        sg.update(x-1,y)
    else:
        print(sg.query(x-1,y))



Measured memory_bytes: 10736
import java.util.*;
import java.util.stream.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		Set<String> set = new HashSet<>();
		int n = in.nextInt(); in.nextLine();
		String before = in.nextLine();
		set.add(before);
		for (int i = 1; i < n; i++) {
			String str = in.nextLine();
			if(set.contains(str) || before.charAt(before.length() - 1) != str.charAt(0)) {
				System.out.println("No");
				return;
			}
			set.add(str);
			before = str;
		}
		System.out.println("Yes");
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;

#define F first
#define S second
#define PB push_back
#define MP make_pair

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll n,k,d,x,cnt=0;
    cin >> n >> k;
    bool a[n+1] = {false};

    for(int i=0;i<k;i++){
        cin >> d;
        for(int j=0;j<d;j++){
            cin >> x;
            a[x]=true;
        }
    }
    for(int i=1;i<n+1;i++)
        if(a[i]==false)
            cnt++;
    cout << cnt;
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define ll long long
#define fr(i, n) for (int i = 0; i < n; i++)
#define frf(i, j, n) for (int i = j; i <= n; i++)
#define frd(i, n) for (int i = n; i >= 0; i--)
#define mp(i, j) make_pair(i, j)
#define pb(x) push_back(x)
using namespace std;
// typedef vector<vector<ll> > matrix;
// const ll S = 3e5 + 20;
// const ll N = 1e6 + 1;
// const ll PRIME = 1e9 + 7;
// const ll MAX = 1e6;

void solve()
{
    int n, k;
    cin >> n >> k;
    int a[n];
    fr(i, n)
    {
        cin >> a[i];
    }
    sort(a, a + n);
    int ans = 0;
    fr(i, k)
    {
        ans += a[i];
    }
    cout << ans;
}
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int t;
    // cin >> t;
    t = 1;
    while (t--)
    {
        solve();
    }
}


Measured memory_bytes: 3652
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cstring>
#include <iomanip>

using namespace std;
// ascending order
#define vsort(v) sort(v.begin(), v.end())
// descending order
#define vsort_r(v) sort(v.begin(), v.end(), greater<int>())
#define vunique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define mp make_pair
#define ts(x) to_string(x)
#define rep(i, a, b) for(int i = (int)a; i < (int)b; i++)
#define repm(i, a, b) for(int i = (int)a; i > (int)b; i--)
#define bit(a) bitset<8>(a)
#define des_priority_queue priority_queue<int, vector<int>, greater<int> >
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; }
typedef long long ll;
typedef pair<int, int> P;
const ll INF = 1e18;

#define MAX_V 1000000

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

  int n, k;
  cin >> n >> k;
  bool haveSnack[n];
  rep(i, 0, n) haveSnack[i] = false;
  rep(i, 0, k) {
    int d;
    cin >> d;
    rep(j, 0, d) {
      int a;
      cin >> a;
      haveSnack[a - 1] = true;
    }
  }

  int rsl = 0;
  rep(i, 0, n) {
    if(!haveSnack[i]) ++rsl;
  }
  cout << rsl << endl;

}


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

typedef long long LL;

const int N=100005;
const LL inf=(LL)1e15;

int n,a[N];
char op[N][2];
LL f[N][3];

int main()
{
	scanf("%d",&n);
	for (int i=1;i<n;i++) scanf("%d%s",&a[i],op[i]);
	scanf("%d",&a[n]);
	f[1][0]=a[1];f[1][1]=f[1][2]=-inf;
	for (int i=2;i<=n;i++)
		if (op[i-1][0]=='+')
		{
			f[i][0]=max(f[i-1][0],f[i-1][1])+a[i];
			f[i][1]=f[i-1][1]-a[i];
			f[i][2]=f[i-1][2]+a[i];
		}
		else
		{
			f[i][0]=-inf;
			f[i][1]=max(f[i-1][0],f[i-1][1])-a[i];
			f[i][2]=max(f[i-1][1],f[i-1][2])+a[i];
		}
	printf("%lld",max(f[n][0],max(f[n][1],f[n][2])));
	return 0;
}

Measured memory_bytes: 3200
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
double memo[301][301][301];
int n,arr[301];
double solve(int a,int b,int c,int n){
    if(a==0 && b==0 && c==0)
        return 0;
    double &cur=memo[a][b][c];
    if(cur!=-1)
        return cur;
    cur=(double)n/(double)(a+b+c);
    if (a > 0) cur += solve(a - 1, b, c, n) * a / (a+b+c);
    if (b > 0) cur += solve(a + 1, b - 1, c, n) * b / (a+b+c);
    if (c > 0) cur += solve(a, b + 1, c - 1, n) * c / (a+b+c);
    return cur;
}
int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    for(int i=0;i<=300;i++){
        for(int c=0;c<=300;c++){
            for(int k=0;k<=300;k++)
                memo[i][c][k]=-1.0;
        }
    }
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int a=0,b=0,c=0,d=0;
    for(int i=0;i<n;i++){
        if(arr[i]==1)
            a++;
        else if(arr[i]==2)
            b++;
        else if(arr[i]==3)
            c++;
        else
            d++;
    }
    cout<<fixed<<setprecision(10)<<solve(a,b,c,n);
}

Measured memory_bytes: 213376
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
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; }
//(a+b-1)/b
long double f(long double a,int b){
  if(b==0)return 1;
  if(b%2==0){
    long double t=f(a,b/2);
    return t*t;
  }
  return f(a,b-1)*a;
}

signed main(){
  cout << fixed << setprecision(10);
	int n; cin>>n;
    int k; cin>>k;
	double ans=0;
  rep(i,1,n+1){
    double add=1.0/n;
    int now=i;
    while(now<k){
      now*=2;
      add/=2;
    }
    ans+=add;
  }
  cout<<ans<<endl;
	
	return 0;
}

Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n, k, cnt = 0;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    int h;
    cin >> h;
    if (h >= k) cnt++;
  }
  
  cout << cnt << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include <cstring>
using namespace std;
bool judge(int n)
{
    for (int i=2;i*i<=n;i++)
        if (n%i==0) return false;
        return true;
}
int main ()
{    int n;
     cin>>n;
    for (int i=11;;i=i+10)
    {
        if (judge(i))
        {
            cout<<i<<" ";
            n--;
        }
        if (n==0) {cout<<endl;break;}
    }
    return 0;
}


Measured memory_bytes: 256
#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-7
#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 N;
	string S;
	scan(S);
	N=S.size();
	for(int i=2;i<N;i+=2){
		string A=S.substr(0,(N-i)/2),B=S.substr((N-i)/2,(N-i)/2);
		if(A==B){
			prin(N-i);
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main() {
  string S;
  cin >> S;
  if(S[0] == 'S' && S[1] == 'S' && S[2] == 'S')cout << 0 << endl;
  else if((S[0] == 'S' && S[1] == 'R' && S[2] == 'R') || (S[0] == 'R' && S[1] == 'R' && S[2] == 'S'))cout << 2 << endl;
  else if(S[0] == 'R' && S[1] == 'R' && S[2] == 'R')cout << 3 << endl;
  else cout << 1 << endl;
}

Measured memory_bytes: 3604
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647
// MAX O(n) 10^18

int main() {
    vector<int> X(5);
    cin >> X.at(0) >> X.at(1) >> X.at(2) >> X.at(3) >> X.at(4);

    int ans = MOD;
    vector<int> indexes = {0, 1, 2, 3, 4};
    do {
        int sum = 0;
        rep(i, 5) {
            while (sum % 10 != 0) sum++;
            sum += X.at(indexes.at(i));
        }
        ans = min(ans, sum);
    } while (next_permutation(indexes.begin(), indexes.end()));

    cout << ans << endl;

    return 0;
}


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

int main()
{
    uint32_t N;
    std::cin >> N;

    std::vector<uint32_t> vec(N,0);

    for(int i = 0; i < N; i++){
        std::cin >> vec[i];
        if( (vec[i] % 2 == 0) && ((vec[i] % 6 != 0) && (vec[i] % 10 != 0)) ){
            //std::cout << vec[i] << std::endl;
            std::cout << "DENIED" << std::endl;
            return 0;
        }
    }

    std::cout << "APPROVED" << std::endl;
    return 0;
}

Measured memory_bytes: 888
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 c = sc.nextInt();
    int k = sc.nextInt();
    
    if( a < b && b < c) {
      System.out.print("Yes");
      return;
    }
    
    int cnt = 0;
      
    if(a >= b){
      while(true) {
        b *= 2;
        cnt++;
        if(a < b)
          break;
      }
    }
    
    if(b >= c){
      while(true) {
        c *= 2;
        cnt++;
        if(b < c)
          break;
      }
    }
    
    if(cnt <= k)
      System.out.print("Yes");
    else
      System.out.print("No");
  }
}


Measured memory_bytes: 27064
N = int(input())
H = [int(i) for i in input().split()]

current = H[0]

for i, h in enumerate(H):
    if (current > h):
        if (current > h + 1):
            print('No')
            break
        else:
            current = h + 1
    else:
        current = h
else:
    print('Yes')


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

int main(){
    int N, M; cin >> N >> M; 
    vector<vector<int>> G(N);
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    vector<int> ord(N);
    for(int i=0; i<N; i++) ord[i]=i;
    int res=0;
    do{
        if(ord[0] != 0) continue;
        bool ok=true;
        for(int i=0; i<N-1; i++){
            auto it=find(G[ord[i]].begin(), G[ord[i]].end(), ord[i+1]);
            if(it == G[ord[i]].end()) ok=false;
        }
        if(ok) res++;
    }while(next_permutation(ord.begin(),ord.end()));
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main() {
  ll n, t, a;
  cin >> n >> t >> a;
  vector<ll> h(n);
  rep(i, n) cin >> h[i];

  ll m = 10000000000000;
  int j = 1;
  rep(i, n) {
    ll tmp;
    tmp = 1000*t - h[i]*6;
    if (m > abs(tmp - a * 1000)) {
      m = abs(tmp - a * 1000);
      j = i + 1;
    }
  }
  
  cout << j << endl;
  return 0;
}

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

def dfs(s, mx, N):
    if len(s) == N:
        print(s)
    else:
        for i in range(97, ord(mx) + 1):
            dfs(s + chr(i), chr(max(i + 1, ord(mx))), N)

N = int(input())

dfs('', 'a', N)

Measured memory_bytes: 4412
#include <bits/stdc++.h>
using namespace std;
vector<int>P;
int pr[30001];
void era(){
	pr[0]=pr[1]=1;
	for(int i=2;i*i<=30000;i++){
		if(pr[i]==0){
			for(int j=i+i;j<=30000;j+=i){
				pr[j]=1;
			}
		}
	}
	for(int i=2;i<=30000;i++){
		if(pr[i]==0)P.push_back(i);
	}
}
int main(){
	era();
	for(int t;cin>>t,t;){
		int ans=0;
		for(int i=0;i<P.size();i++){
			if(t<P[i]*3)break;
			for(int j=i;j<P.size();j++){
				int k=t-P[i]-P[j];
				if(k<P[j])break;
				if(k<P[i]+P[j] && pr[k]==0){
					//cout<<P[i]<<" "<<P[j]<<" "<<k<<endl;
					ans++;
				}
			}
		}
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 1364
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define ALL(v) (v).begin(), (v).end()
using ll = long long;
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;

vector<int> f(string s) {
    ll num = 0;
    int ten = 0;
    bool flag = false;
    rep(i, (int)s.size()) {
        if (flag) ten++;
        if (s[i] == '.') {
            flag = true;
            continue;
        }
        num *= 10;
        num += s[i] - '0';
    }
    vector<int> res;
    int two = 0, five = 0;
    while (num % 2LL == 0) {
        num /= 2LL;
        two++;
    }
    while (num % 5LL == 0) {
        num /= 5LL;
        five++;
    }
    res.emplace_back(five);
    res.emplace_back(two);
    res.emplace_back(ten);
    return res;
}

int cnt[100][100][100];

signed main() {
    int n;
    cin >> n;
    string a[n];
    rep(i, n) {
        cin >> a[i];
    }
    ll ans = 0;
    rep(i, n) {
        auto v = f(a[i]);
        for (int five = 0; five <= 31; five++) {
            for (int two = 0; two <= 51; two++) {
                for (int ten = 0; ten <= 11; ten++) {
                    if (min(v[0] + five, v[1] + two) < v[2] + ten) continue;
                    ans += cnt[five][two][ten];
                }
            }
        }
        cnt[v[0]][v[1]][v[2]]++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 9956
# AOJ 0033 Ball

n = gets.to_i
n.times do
  balls = gets.split.map(&:to_i).reverse
  left, right = [0], [0]

  failed = false
  until balls.empty?
    ball = balls.pop

    if ball > left.last
      left << ball
    elsif ball > right.last
      right << ball
    else
      failed = true
      break
    end
  end

  puts failed ? "NO" : "YES"
end

Measured memory_bytes: 6104
#include<bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long int ll;
typedef long double ld;
const ll INF=(1LL<<62);
const ld pi=acosl((ld)-1);
const ll mod = 1000000007;
// const ll mod = 1234567;
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
#define endn "\n"
#define TO_STRING(VariableName) # VariableName

template <typename T>ostream &operator<<(ostream &out,const vector<T> &v) {rep(i,(int)v.size()-1)cout<<v[i]<<" ";cout<<v[(int)v.size()-1];return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const map<T1, T2> &p) {out << "(" << p.first << ", " << p.second << ")";return out;}
template <typename T1, typename T2>ostream &operator<<(ostream &out, const pair<T1, T2> &p){out << "(" << p.first << ", " << p.second << ")";return out;}
template<class T>void debag(const T &obj){cout<<obj<<endl;}

bool solve(){
  ll n;cin>>n;
  cout<<n+n*n+n*n*n<<endl;
  return false;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout<<fixed<<setprecision(30);
  solve();
}


Measured memory_bytes: 3644
#include <iostream>
#include <string>
#include <sstream>
#include <iomanip> 
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>

using namespace std;

#define MAXN 300010

int ct[MAXN], ans[MAXN];

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


	return 0;
}


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

using namespace std;

typedef long long ll;

int own_max(int a, int b) {
    if (abs(a) > abs(b)) {
        return a;
    } else {
        return b;
    }
}

int main() {
    string s;
    cin >> s;
    int ind = 0;
    vector<int> a(s.size() + 1, 0);
    int cur = 0;
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] == '<') {
            cur++;
            a[i + 1] = max(a[i + 1], cur);
        } else {
            cur = 0;
        }
    }
    cur = 0;
    for (int i = static_cast<int>(s.size()) - 1; i >= 0; --i) {
        if (s[i] == '>') {
            cur++;
            a[i] = max(a[i], cur);
        } else {
            cur = 0;
        }
    }
    ll ans = 0;
    for (const auto &i:a) {
        ans += i;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 2820
#include <iostream>
using namespace std;
int main(){
  char str[100+1];
  bool tap=true;
  cin >> str;
  for(int i=0;str[i] != '\0';i++){
    if(i%2==1 && str[i]=='R')tap=false;
    if(i%2==0 && str[i]=='L')tap=false;
  }
  if(tap)cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

unsigned seed128[4];
void seed(unsigned s){
	for(int i=1; i<=4; i++)
		seed128[i-1] = s = 1812433253U * (s^(s>>30)) + i;
}

unsigned xor_shift() {
	unsigned t;
	t=(seed128[0]^(seed128[0]<<11));
	seed128[0]=seed128[1];
	seed128[1]=seed128[2];
	seed128[2]=seed128[3];
	return seed128[3]=(seed128[3]^(seed128[3]>>19))^(t^(t>>8));
}

// Randomized Binary Search Tree
// infix, 0-based

typedef int type;
constexpr int INF = (1 << 29);
constexpr type INIT = INF;

// update function
inline type func(type a, type b) {
	return min(a, b);
}

struct RBST {
	type value, res;
	int size;
	RBST *left, *right;

	RBST(int v):value(v), res(v), size(1), left(nullptr), right(nullptr) {}

	void update() {
		size = 1;
		res = value;

		if(left) {
			size += left->size;
			res = func(res, left->res);
		}

		if(right) {
			size += right->size;
			res = func(res, right->res);
		}
	}
};

inline int node_size(const RBST *x) {
	return x ? x->size : 0;
}

RBST *merge(RBST * x, RBST * y) {
	if(!x) return y;
	if(!y) return x;

	if(xor_shift() % (x->size + y->size) < x->size) {
		x->right = merge(x->right, y);
		x->update();
		return x;
	}
	else {
		y->left = merge(x, y->left);
		y->update();
		return y;
	}
}

typedef pair<RBST *, RBST *> P;

P split(RBST *x, int num) {
	if(!x) return P(nullptr, nullptr);

	const int l_size = node_size(x->left);
	if(l_size < num) {
		const P tmp = split(x->right, num - l_size - 1);
		x->right = tmp.first;
		x->update();
		return P(x, tmp.second);
	}
	else {
		const P tmp = split(x->left, num);
		x->left = tmp.second;
		x->update();
		return P(tmp.first, x);
	}
}

RBST *insert(RBST *x, int pos, type value) {
	RBST *new_node = new RBST(value);
	const P tmp = split(x, pos);
	return merge(merge(tmp.first, new_node), tmp.second);
}

RBST *erase(RBST *x, int pos) {
	P tmp = split(x, pos);
	RBST *left = tmp.first;
	tmp = split(tmp.second, 1);
	delete tmp.first;
	return merge(left, tmp.second);
}

// [l, r)
type query(RBST *x, int l, int r) {
	if(!x) return INIT;
	if(r <= 0 || x->size <= l) return INIT;
	if(l <= 0 && x->size <= r) return x->res;

	const int l_size = node_size(x->left);
	const type res = (l <= l_size && l_size < r ? x->value : INIT);
	const type vl = query(x->left, l, r);
	const type vr = query(x->right, l - l_size - 1, r - l_size - 1);
	return func(res, func(vl, vr));
}

enum { SHIFT, QUERY, UPDATE };

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

	seed(time(NULL));

	int n, q;
	cin >> n >> q;

	RBST *root = nullptr;
	for(int i = 0; i < n; ++i) {
		int a;
		cin >> a;
		root = insert(root, i, a);
	}

	while(q--) {
		int x, y, z;
		cin >> x >> y >> z;
		switch(x) {
		case SHIFT:
		{
			const auto value = query(root, z, z + 1);
			root = erase(root, z);
			root = insert(root, y, value);
			break;
		}
		case QUERY:
		{
			cout << query(root, y, z + 1) << '\n';
			break;
		}
		case UPDATE:
		{
			root = erase(root, y);
			root = insert(root, y, z);
			break;
		}
		}
	}

	return EXIT_SUCCESS;
}

Measured memory_bytes: 10584
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define all(v) v.begin(),v.end()
#define inf (int)(3e18)
#define P pair<int,int>
#define mod (int)(1e9+7)

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

template<class T> inline void chmin(T &a, T b) {
	a = min(a, b);
}
template<class T> inline void chmax(T &a, T b) {
	a = max(a, b);
}

int N,M,V,p;
int A[100005];
signed main() {
	cin>>N>>M>>V>>p;
	rep(i,N)cin>>A[i];
	sort(A,A+N,greater<>());
	int ok=0,ng=N;
	while(ng-ok>1){
		int mid=(ok+ng)/2;
		if(mid<p){ok=mid;continue;}
		if(A[mid]<A[p-1]-M){ng=mid;continue;}
		int sum=(p-1)*M+(N-mid)*M;
		for(int i=p-1;i<mid;i++){
			sum+=A[mid]+M-A[i];
		}
		if(sum>=V*M)ok=mid;
		else ng=mid;
	}
	cout<<ok+1<<endl;
}



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

using namespace std;

#define ll long long
#define ar array



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

    int a, b;
    cin >> a >> b;    
    if(2*b >= a){
        cout << 0;
        return 0;
    }
    cout << a - 2*b;
    return 0;
}


Measured memory_bytes: 3648
using System;
class p
{
  static void Main()
  {
    string master = @"abcdefghijklmnopqrstuvwxyz";
    string s = Console.ReadLine();
    for (int i = 0; i < s.Length; i++) {
      master = master.Replace(s[i].ToString(), "");
    }
    Console.WriteLine(0 < master.Length ? master[0].ToString() : "None");
  }
}

Measured memory_bytes: 13280
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll a;
    string sb;
    cin >> a >> sb;
    ll b = 100 * (sb[0] - '0') + 10 * (sb[2] - '0') + (sb[3] - '0');
    ll ans = a * b;
    ans /= 100;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <vector>
#include <array>
#include <set>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <stack>
#include <unordered_map>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cassert>
#include <cctype>  // std::islower(), std::isupper(), std::tolower, std::toupper
#include <iomanip> // std::std::setprecision(X)
#include <limits>  //std::numeric_limits<int>::max(), min()

typedef long long ll;

int chk (ll k, const ll t){
  int rtn = 0;
  while( k%t == 0 && k >= t ) {
    k /= t;
    rtn++;
  }
  return rtn;
}

int main (void) {
  int D, N; std::cin >> D >> N;
  ll cnt = 0;
  for(int j=1; ; j++) {
    if ( chk(j,100) == D ) {
      cnt++;
    }
    else continue;

    if ( cnt == N ) {
      std::cout << j << std::endl;
      return 0;
    }
  }
  assert(0);
  return 0;
}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <int,int>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

int n,n2=1,tmp[30],son[2000000][30],num[2000000][30],sv,ans=0;
string s[200010];

bool cmp(string a,string b)
{
	return a.size()>b.size();
}

void add(int k)
{
	rep(i,26) if(tmp[i]>0) num[k][i]++;
}

int main()
{
	cin>>n;
	rep(i,n) cin>>s[i];
	sort(s,s+n,cmp);
	rep(i,n)
	{
		int cur=1,ok=1;
		for(int j=s[i].size()-1;j>0;j--)
		{
			if(son[cur][s[i][j]-'a']==0)
			{
				ok=0;
				break;
			}
			cur=son[cur][s[i][j]-'a'];
			//if(i==1) cout<<cur<<" hhh\n";
		}
		if(ok) ans+=num[cur][s[i][0]-'a'];//,cout<<s[i]<<" stane\n";
		
		rep(j,28) tmp[j]=0;
		rep(j,s[i].size()) tmp[s[i][j]-'a']++;
		cur=1;
		add(cur);
		for(int j=s[i].size()-1;j>=0;j--)
		{
			sv=cur;
			if(son[cur][s[i][j]-'a']==0) son[sv][s[i][j]-'a']=cur=++n2;
			else cur=son[sv][s[i][j]-'a'];
			tmp[s[i][j]-'a']--;
			//if(i==0) cout<<cur<<" kkk\n";
			add(cur);
		}
	}
	cout<<ans<<endl;
	return 0;
}

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

/* 大文字を小文字に変換 */
char tolower(char c) {return (c + 0x20);}
/* 小文字を大文字に変換 */
char toupr(char c) {return (c - 0x20);}

// if('A'<=s[i] && s[i]<='Z') s[i] += 'a'-'A';

/*
string s = "abcdefg"
s.substr(4) "efg"
s.substr(0,3) "abc"
s.substr(2,4) "cdef"

// イテレータ要素のインデックス
distance(A.begin(), itr);
*/

const int INF = 1000100100;

int main()
{
    int n; cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    // 初期化
    vector<int> l(n);
    rep(i,n) l[i] = -1;
    int lind = n-1;

    l[lind] = a[0];

    int ans = 1;
    for(int i=1; i<n; i++){
        if(l[lind] >= a[i]){
            ++ans;
            --lind;
            l[lind] = a[i];
        }else{
            auto itr = lower_bound(l.begin(), l.end(), a[i]);
            --itr;
            *itr = a[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 4024
from collections import deque

N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)

A = deque(A)
L = deque()

# print(A, L)
ans = A.popleft()
L.append(A.popleft())
F = True
for i in range(2, N):
    if F:
        ans += L[0]
        F = not F
    else:
        ans += L.popleft()
        L.append(A.popleft())
        F = not F
print(ans)
    

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

int main() {
    using namespace std;
    constexpr unsigned int maxN = 200010;
    unsigned int N;
    scanf("%u", &N);
    array<unsigned int, maxN> perm;
    {
        array<pair<int, int>, maxN> p;
        for(unsigned int i = 0; i < N; ++i)scanf("%d%d", &p[i].first, &p[i].second);
        sort(p.begin(), p.begin() + N);
        for(unsigned int i = 0; i < N; ++i)p[i] = {p[i].second, i + 1};
        sort(p.begin(), p.begin() + N);
        transform(p.cbegin(), p.cbegin() + N, perm.begin(), [](auto i){return i.second;});
    }

    constexpr unsigned long MOD = 998244353;
    array<unsigned long, maxN> binary;
    unsigned long n = binary[0] = 1;
    generate(binary.begin() + 1, binary.end(), [&n](){if(n >= MOD)n -= MOD;return n <<= 1;});

    array<unsigned int, maxN> fenwick_tree{};
    auto que = [&fenwick_tree, &N](unsigned int i){
        unsigned int s{0}, j{i};
        while(i){
            s += fenwick_tree[i];
            i -= i & -i;
        }
        while(j <= N){
            ++fenwick_tree[j];
            j += j & -j;
        }
        return s;
    };

    array<unsigned int, maxN> coef{};
    coef[N] = N + MOD - 4;
    for(unsigned int i = 0; i != N; ++i){
        auto p = perm[i], q = que(p);
        ++coef[q];
        ++coef[i - q];
        ++coef[p - q - 1];
        ++coef[N - i - p + q];
    }

    cout << inner_product(binary.begin(), binary.begin() + N + 1, coef.begin(), 4 + MOD - N) % MOD << endl;
    return 0;
}

Measured memory_bytes: 4096
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b;
  string s;
  cin>>a>>b>>s;
  bool f=1;
  for(int i=0;i<s.size();i++)
      f&=(i==a?(s.at(i)=='-'):(s.at(i)>='0'&&s.at(i)<='9'));
  cout<<(f?"Yes":"No")<<endl;
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define ll long long
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define testcase ll T; cin >> T; for (ll tc = 1; tc <= T; tc++)
#define M 1000000007
#define MM 2000000000000000000
#define eps 1e-8
#define eq(x,y) (fabs((x)-(y)) < eps)
#define r2 1.41421356237
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod;assert(b>=0);for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}

int main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  //testcase {
  string s;
  cin>>s;
  if(s[s.size()-1]=='s') { s+="es"; }
  else { s+='s'; }
  cout<<s;
  //}
  return 0;
}


Measured memory_bytes: 3652