Problem:


Score : 700 points

Problem Statement

N problems are proposed for an upcoming contest. Problem i has an initial integer score of A_i points.

M judges are about to vote for problems they like. Each judge will choose exactly V problems, independently from the other judges,
and increase the score of each chosen problem by 1.

After all M judges cast their vote, the problems will be sorted in non-increasing order of score, and the first P problems will be chosen for the problemset.
Problems with the same score can be ordered arbitrarily, this order is decided by the chief judge.

How many problems out of the given N have a chance to be chosen for the problemset?

Constraints

2 \le N \le 10^5

1 \le M \le 10^9

1 \le V \le N - 1

1 \le P \le N - 1

0 \le A_i \le 10^9

Input

Input is given from Standard Input in the following format:

N M V P
A_1 A_2 ... A_N

Output

Print the number of problems that have a chance to be chosen for the problemset.

Sample Input 1

6 1 2 2
2 1 1 3 0 2

Sample Output 1

5

If the only judge votes for problems 2 and 5, the scores will be 2 2 1 3 1 2.
The problemset will consist of problem 4 and one of problems 1, 2, or 6.

If the only judge votes for problems 3 and 4, the scores will be 2 1 2 4 0 2.
The problemset will consist of problem 4 and one of problems 1, 3, or 6.

Thus, problems 1, 2, 3, 4, and 6 have a chance to be chosen for the problemset. On the contrary, there is no way for problem 5 to be chosen.

Sample Input 2

6 1 5 2
2 1 1 3 0 2

Sample Output 2

3

Only problems 1, 4, and 6 have a chance to be chosen.

Sample Input 3

10 4 8 5
7 2 3 6 1 6 5 4 6 5

Sample Output 3

8



Sample input:
6 1 2 2
2 1 1 3 0 2


Sample output:
5

Submission status: Accepted

Solution code:
input = raw_input


def answer():
    n, m, v, p = map(int, input().split(" "))
    nums = sorted(map(int, input().split(" ")), reverse=True)

    num_last = nums[p-1]

    nokori_sum = sum(nums[p-1:n])

    out = p
    count = 0
    if v > p:
        cumsum = {}
        cur = 0
        
        cur = 0
        for i in range(p-1, n):
            x = nums[i]
            cur += x
            cumsum[i] = cur

        for i in range(p, n):
            x = nums[i]
            if x + m < num_last:
                break

            #nokori_yoyuu = ( (x + m) * (n-p+1- 1) ) - (nokori_sum-x)
            #nokori_yoyuu = 0
            #for j in range(p-1, n):
            #    if j == i:
            #        continue
            #    x2 = nums[j]
            #    cur_yoyuu = max(0, min(x+m-x2, m))
            #    nokori_yoyuu += cur_yoyuu

            area1 = (x+m) * (i-p+1) - cumsum[i-1]
            #print("n", n, "i", i, "m", m)
            area2 = (n - i - 1) * m
            #print(area1, area2, nokori_yoyuu)

            nokori_yoyuu = area1 + area2

            cost = (v-p) * m
            if cost > nokori_yoyuu:
                break

            count += 1

        out += count

    else:
        for x in nums[p:]:
            if x + m < num_last:
                break
            count += 1
        out += count

    print(out)

answer()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, bisect_left
input = sys.stdin.readline
n, m, v, p = [int(x) for x in input().strip().split()]
araw = sorted([int(x) for x in input().strip().split()])
a = list(reversed(araw))

def f(x, n, m, v, p, a, araw):
    c = p - (n - bisect_right(araw, a[x-1]+m)) - 1
    if c < 0:
        return False
    vote = m * (v - 1)
    a[x-1] += m
    thr = a[x-1]
    for i, aa in enumerate(a, start=1):
        if vote <= 0:
            break
        if i == x:
            continue
        if aa > thr:
            a[i-1] += m
            vote -= m
        elif aa == thr:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
        elif thr - aa < m:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
            else:
                v_ = min(vote, thr - aa, m)
                a[i-1] += v_
                vote -= v_
        else:
            a[i-1] += m
            vote -= m
    return vote <= 0

x = 0
l = 1
r = n + 1
while l < r:
    x = (l + r) // 2
    if f(x, n, m, v, p, a[:], araw):
        l = x + 1
    else:
        r = x
print(l-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    A.sort(reverse=True)

    I = N

    for i in range(P, N):
        if A[P-1] > A[i] + M:
            I = i
            break

    l = P-1
    r = I
    m = (l + r)//2

    while l + 1 != r:

        k = (V-P)*M - M*(N-I)
        for i in range(P-1, I):
            if i == m:
                continue
            k -= min(A[m] + M -A[i], M)
            if k <= 0:
                l = m
                m = (l+r)//2
                break
        if k > 0:
            r = m
            m = (l+r)//2

    print(l+1)







    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
# 0 ~ (p-1) は問題に選ばれる可能性が既にある（数が同じならそれ以降も）
# その他で逆転できるのはどれか
ans = [0] * n
for i in range(p):
    ans[i] = 1

index = p # まだ定まっていないもの
for i in range(p, n):
    if a[i] == a[p-1]:
        ans[i] = 1
        index += 1
    else:
        break

if index == n:
    print(sum(ans))
    exit()

# 選ばれていない中で最大: a[index]
# 選ばれている中で最小: a[index-1] => a[p-1] と考えることに修正
mn = a[p-1]

# 0 ~ (index-2)の index-1個 は必ず選ぶ。index-1は選ばない
# 残り、v - (index-1 + 1) 個をどう選ぶか

# 簡単な場合を先に処理
if v - p <= 0:
    for i in range(p, n):
        if a[i] + m >= mn:
            ans[i] = 1
        else:
            break
    print(sum(ans))
    exit()

# 小さいものにもvoteする必要がある場合（v - (index-1 + 1))個

# それより大きいものが何個あるかを求めておく
# それ以下のものも把握しておく（それ以下のものには何個配っても良い）:

large = [0] * n
small = [0] * n
for i in range(p, n):
    if i == p:
        large[p] = 0
        small[p] = n - 1 - p
    else:
        if a[i] == a[i-1]:
            large[i] = large[i-1]
            small[i] = small[i-1]
        else:
            large[i] = i - p
            small[i] = n - 1 - i


acum = [0] * (n+1)
for i in range(p-1, n):
    acum[i+1] = acum[i] + a[i]

for i in range(p, n):
    unvote = v - p - small[i]
    if unvote <= 0:
        if a[i] + m >= mn:
            ans[i] = 1
    else:
        if a[i] + m < mn:
            break
        # 分配する個数 large[i] -> index ~ index + large[i] - 1
        sm = acum[p + large[i]] - acum[p-1]
        if sm + unvote * m <= (a[i] + m) * (large[i]+1):
            ans[i] = 1

print(sum(ans))

Submission status: Accepted

Solution code:
n, m, v, p = [int(_) for _ in input().split()]
l = [int(_) for _ in input().split()]

l = sorted(l, reverse=True)

# print(l)

s = [0]


for i in range(1, n+1):
    s.append(s[-1] + l[-i])
s = sorted(s, reverse=True)

# print(s)

for i in range(p, n):
    if l[i] + m < l[p - 1]:
        ans = i
        break
    x = (l[i] + m) * (i - p + 1) - (s[p - 1] - s[i])
    # print('i',i)
    # print('(l[i] + m)', (l[i] + m))
    # print('(i - p + 1)', (i - p + 1))
    # print('(s[p - 1] - s[i])', (s[p - 1] - s[i]))
    # print('x',x)
    y = 0
    if v >= (n - i) + (p - 1):
        y = v - (n - i) - (p - 1)

    # print('y * m', y * m)

    if x < y * m:
        ans = i
        break

    if i == n-1:
        ans = n

print(ans)

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
S=[int(i) for i in input().split()]
S.sort(reverse=True)

def binary_search(S,k,m,v,p):
  test=S[k]+m
  cnt=m*(p-1)
  l=0
  for i in range(p-1,n):
    if i==k:
      continue
    elif test<S[i]:
      l=1
      return False
      break
    elif test-S[i]>=m:
      cnt+=m
    else:
      cnt+=test-S[i]
      
  if l==0:
    if cnt>=m*(v-1):
      return True
    else:
      return False

l=p-1
r=n
while r-l>1:
  mid=(r+l)//2
  if binary_search(S,mid,m,v,p):
    l=mid
  else:
    r=mid
print(l+1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
B = []
C = []

A.sort()
for _ in range(P-1):
    B.append(A.pop())

try:
    C.append(A.pop())
    while C[-1] == A[-1]:
        C.append(A.pop())
except:
    pass

A_length = len(A)
B_length = len(B)
C_length = len(C)
sm = sum(C)
count = 0

for _ in range(len(A)):
    now = A[-1]
    new = now + M
    threshhold = C
    remain = V - B_length - (A_length - count)
    if new >= C[0]:
        if remain <= 0:
            val = A.pop()
            C.append(val)
            sm += val
            count += 1
        elif sm <= new * (C_length + count) - remain*M:
            val = A.pop()
            C.append(val)
            sm += val
            count += 1
print(len(B+C))

Submission status: Accepted

Solution code:
import bisect
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
A.reverse()

AP = A[P-1]
D = [AP - A[i] for i in range(N)]
if V <= P:
	for i in range(N):
		if D[i] > M:
			print(i)
			exit()
l,r = P-1,N
while r - l > 1:
	p = (l+r)//2
	# A[p] + M < A[P]
	if D[p] > M:
		r = p
		continue
	n = P + (N-1 - p)
	if V <= n:
		l = p
		continue
	v = V - n
	d = []
	m = A[p] + M
	sumd = []
	nonzero = p
	for i in range(P-1, p):
		diff = min(M, m - A[i])
		if nonzero == p and diff > 0:
			nonzero = i
		d.append(diff)
		if i == P-1:
			sumd.append(diff)
		else:
			sumd.append(sumd[-1] + diff)
	if sumd[-1] < v * M or p - nonzero < v:
		r = p
	else:
		l = p

print(r)

Submission status: Accepted

Solution code:
from collections import Counter


def solve(n, m, v, p, aaa):
    aaa.sort(reverse=True)
    count = Counter(aaa)
    scores = sorted(count.keys(), reverse=True)

    tmp_cnt = 0
    for pi, s in enumerate(scores):
        c = count[s]
        tmp_cnt += c
        if tmp_cnt >= p:
            ans = tmp_cnt
            rival = s
            htm_cnt = tmp_cnt - (p - 1)  # higher than me excluding top p-1
            htm_sum = s * htm_cnt
            break
    else:
        raise RuntimeError

    # print(ans)
    # print(rival)
    # print(htm_cnt, htm_sum)

    for s in scores[pi + 1:]:
        c = count[s]
        upper = s + m
        if upper < rival:
            break

        v4mtm = v - (n - htm_cnt)  # remaining vote for higher than s excluding top p-1
        if v4mtm <= 0:
            ans += c
        else:
            space = upper * htm_cnt - htm_sum
            if space >= m * v4mtm:
                ans += c

        htm_cnt += c
        htm_sum += s * c

    return ans


n, m, v, p = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, m, v, p, aaa))

Submission status: Accepted

Solution code:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
B = A[:N-P+1]
S = sum(B)
accum = [0]
for i in range(N-P+1):
    accum.append(accum[-1]+B[i])

ans = P-1

for i in range(N-P+1):
    if B[i]+M-B[-1]<0:
        continue
    if B[i]*(N-P-i)-S+accum[i+1]+M*(N-P)>=max(M*(V-P),0):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import math
N, M, V, P = map(int, input().split())
A_ = list(map(int, input().split()))
A = sorted(A_)
temp = 0
requires = 0
for i in range(N-P):
  requires += A[N-P] - A[i]
for i in range(N):
  points = V - P - i
  if points < 0:
    points = 0
  requires -= A[N-P] - A[i]
  kabe = N - P - i
  if kabe == 0:
    temp = i
    break
  else:
    wall = points * M - requires
    if wall < 0:
      wall = 0
    wall_2 = math.ceil(wall / kabe)
    wall_3 = A[N-P] + wall_2
    i_points = A[i] + M
    if i_points >= wall_3:
      temp = i
      break
print(N - temp)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
#n = int(input())
n,m,v,p = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]


def number(res,w):
    ans = 0
    for i in res:
        ans += min(m,i)
    
    #print(ans)
    if ans < w*m: return False
    else: return True
    



def check(c):
    M = a[c]+m
    if a[n-p] > M: return False

    w = v-c-1-(p-1)
    if w <= 0: return True
    
    res = []
    for i in range(c+1, n-p+1):
        res.append(M-a[i])
    
    
    #print(res,"w",w,"m",m,"c",c)
    return number(res,w)


a.sort()

ok = n-p
ng = -1
while ok-ng > 1:
    mid = (ok+ng)//2
    if check(mid):
        ok = mid
    else:
        ng = mid

#print(ng,ok)    
print(n-ng-1)

Submission status: Accepted

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M, V, P = inpl()
A = inpl()
A.sort(reverse=True)
s = 0
S = []
for i in range(N):
    s += A[i]
    S.append(s)
S.append(0)
OK = P-1
NG = N
while NG - OK > 1:
    x = (NG+OK)//2
    if A[P-1] > A[x] + M:
        NG = x
    elif P + (N-1-x) >= V:
        OK = x
    else:
        remain = M * (V-P-(N-1-x))
        space = (x-P+1)*(A[x]+M) - (S[x-1] - S[P-2])
        if remain <= space:
            OK = x
        else:
            NG = x
print(OK+1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
# print(A)
B=A[:]
A.append(inf)
for i in range(n-1):
    B[i+1]+=B[i]
i=0
while i < n:
    count=1
    while A[i]==A[i+1]:
        i+=1; count+=1
    K=v-p-(i)
    # print(i,K,ans)
    if i>=n-p:
        ans+=count; i+=1
        continue
    if K<=0:
        if bisect.bisect_right(A,A[i]+m)>=n-p+1:
            ans += count
            i+=1
        else:
            i+=1
    else:
        if A[n-p]>A[i]+m:
            i+=1
        else:
            S=B[n-p]-B[i]
            if (A[i]+m)*(n-p-i)>=S+K*m:
                ans+=count
                i+=1
            else: i+=1
print(ans)

Submission status: Accepted

Solution code:
n, m, v, p = [ int(v) for v in input().split() ]
a_list = [ int(v) for v in input().split() ]
a_list.sort()

# 選ばれる可能性のある最低点を求める
# 選びかた　・目標のやつには審査員だけ入れてやる
#          ・上よりP-1番目以下のやつらも入れられるだけ入れてやる
# 　　　　　・残りの奴らにはなでるように入れてやる
#          ・これでP番目以上になるやつがあったらご愁傷さま

def vote(x):
    if x >= n - p:
        return True
    elif x == -1:
        return False
    else:
        total_vote = m * (v-1)
        b_list = a_list[::]
        b_list[x] += m

        if b_list[x] < b_list[n-p]:
            return False

        for i in range(p-1):
            a = min(total_vote, m)
            b_list[-i-1] += a
            total_vote -= a
            if total_vote == 0:
                break
        
        for i in range(n-p+1):
            if i != x and b_list[x] > b_list[i]:
                a = min(total_vote, m, b_list[x] - b_list[i])
                b_list[i] += a
                total_vote -= a
                if total_vote == 0:
                    break

        if total_vote == 0:
            return True
        else:
            return False

if vote(0):
    print(n)
else:
    ok = n-1
    ng = 0
    while ok - ng > 1:
        mid = (ok+ng)//2
        if vote(mid):
            ok = mid
        else:
            ng = mid
    print(n- ok)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo

@mt
def slv(N, M, V, P, A):
    A.sort(reverse=True)
    def f(i):
        if i < P:
            return 0

        if V - P <= 0:
            if A[i] + M >= A[P-1]:
                return 0
            else:
                return 1
        else:
            am = A[i] + M
            r = V - P
            B = []
            for j in range(P-1, N):
                if j != i:
                    B.append(A[j])
                j += 1
            heapq.heapify(B)
            C = []
            rm = M * r
            while B:
                b = heapq.heappop(B)
                d  = am - b
                if d > 0:
                    if d > M:
                        d = M
                    if d <= rm:
                        rm -= d
                        C.append(b+d)
                    else:
                        C.append(b+rm)
                        rm = 0
                else:
                    C.append(b)
            return 0 if max(C) <= am and rm == 0 else 1

    b = Bisect(f)
    i = b.bisect_right(0.5, lo=0, hi=N)
    return i


def main():
    N, M, V, P = read_int_n()
    A = read_int_n()
    print(slv(N, M, V, P, A))

    # N = 10**5
    # M = random.randint(0, 10**9)
    # V = random.randint(1, N-1)
    # P = random.randint(1, N-1)
    # A = [random.randint(0, 10**9) for _ in range(N)]
    # print(slv(N, M, V, P, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n, m, v, p = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = -np.sort(-a)
rest = a[p-1:]
sa = np.cumsum(rest)
nr = len(sa)
ans = p
r0 = rest[0]

for i, (sl, ai) in enumerate(zip(sa, rest)):
    if i == 0:
        continue
    nsmalls = nr-i
    nlarges = i
    rm = max(v-nsmalls-(p-1), 0)
    slarges = sl+rm*m-ai
    mean_larges = slarges/nlarges
    aim = ai+m
    if mean_larges <= aim and r0 <= aim:
        ans += 1
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, M, V, P = rl() #Vは選べる問題
A = rl()
A.sort(reverse=True)
INF = 10 ** 10
A = A[P-1:] + [-INF] #上位P-1問は捨てる
V -= (P-1)
N = len(A)
answer = P-1

# 残りの問題からトップに立てるかどうか二分探索
high = N-1 #不可能
low = 0 #可能
while high > low + 1:
    mid = (high+low)//2
    num = max(0, V - (N-1-mid)) #INFは捨てる   
    B = np.array(A[:mid])
    #Bの中からM人のジャッジがnum問選ぶ
    count = ((A[mid] + M) - B).sum()
    if count <  M * num:
        high = mid #不可能
    # 他に不可能な場合がある
    elif A[0] > A[mid] + M:
        high = mid
    else:
        low = mid

answer += (low + 1)
print(answer)

Submission status: Accepted

Solution code:
import math
n,m,v,p=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
def is_ok(N,m,v,p):
    counter=0
    howadd=0
    not_avoid=0
    judge=lists[N]+m
    for k in range(n-1,-1,-1):
        if k!=N:
            if judge<lists[k]:
                counter+=m
                howadd+=1
                not_avoid+=1
            elif judge==lists[k] and howadd<p-1:
                counter+=m
                howadd+=1
            elif judge==lists[k] and howadd==p-1:
                pass
            elif judge>lists[k] and howadd<p-1:
                howadd+=1
                counter+=m
            elif judge>lists[k] and howadd==p-1:
                counter+=min(judge-lists[k],m)    
    if not_avoid>=p:
            return False
    elif not_avoid<p:
        if counter<(m)*(v-1):
            return False
        elif counter>=(m)*(v-1):
            return True
start=0
end=n-1
for _ in range(30):
    c=(start+end)/2
    if is_ok(math.floor(c),m,v,p):
        end=c
    elif not (is_ok(math.floor(c),m,v,p)):
        start=c       
print(n-math.floor(end))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    A.sort(reverse = True)

    used_vote = (P-1)*M
    res = M*V-used_vote

    # res を振り分けていく
    a = A[P-1:]
    r = a[0]+1
    l = -1
    while r - l > 1:
        mid = (r+l)//2
        goal = mid+M

        # 絶対入れない
        if a[0] > goal:
            l = mid
            continue

        need= 0 
        for aa in a:
            need+=min(M,goal-aa)
        
        if need >=res: ##成功
            r = mid
        else:
            l = mid
    
    # l が最小の値
    for i in range(N):
        if A[i] > l:
            continue
        else:
            print(i)
            return
    print(N)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
wa = [a[0]]
for i in range(1,n):
    wa.append( wa[i-1] + a[i] )
border = a[n-p]
j = bisect.bisect_right(a,border)
for i in range(n):
    if a[i] + m >= border:
        if n-j+i+1 >= v:
            print(n-i)
            break
        else:
            if (j-i-1)*(a[i]+m)-(wa[j-1]-wa[i]) >= (v-(n-j+i+1))*m:
                print(n-i)
                break

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))

a = sorted(a)[::-1]

minp = a[p-1]
result = 0
td = 0
count = 0
tpcount = 1
tptd = 0
pre = minp
for i in range(p, n):
    if pre != a[i]:
        td += tptd
        count += tpcount
        tptd = 0
        tpcount = 0
    if m * min(n-v, count) >= (minp - a[i]) * count - td and minp <= a[i] + m:
        result+=1
        tpcount+=1
        tptd+= minp - a[i]
        pre = a[i]
    else:
        break
print(result+p)

Submission status: Accepted

Solution code:
# B
import numpy as np
N, M, V, P = map(int, input().split())
A = np.array(input().split(), dtype=int)

A = np.sort(A)[::-1]

# X(1-origin)が再録される可能性があるか
def f(X):
    # M人が, Pに票を入れず、Xに全振りして可能性がないなら終了
    if (A[P-1] > A[X-1] + M):
        # print("C1")
        return False

    # M人がV2回投票を行う
    V2 = V - (P-1) - 1 - (N-X)
    if V2 < 0: V2 = 0
    # A[P:X]の範囲にM人がV2回投票を行ったとき、Ax = A[X-1] + Mを超えたら終了(同点はOK)
    # 自明に小さいAに票を入れる
    Ax = A[X-1] + M
    RANGE = Ax - A[P-1:X-1]
    # 先にAxから引いておくので、負数になったら終了
    
    # RANGEの各要素はPまで吸収できる→Mとmaxをとって、合計値がM*V以下ならOK
    # print(RANGE)
    RANGE = np.minimum(RANGE, M)
    # print(RANGE)
    # print(np.sum(RANGE), M*V2)
    return np.sum(RANGE) >= M*V2

# 二分探索
lo, up = P, N

while(lo!=up):
    ta = (lo + up + 1) // 2
    # print(lo, up, ta)

    if f(ta):
        lo = ta
    else:
        up = ta - 1

print(lo)

Submission status: Accepted

Solution code:
from itertools import accumulate
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
I = P
for i, a in enumerate(A[P:], P+1):
    if a + M >= A[P-1]:
        I = i
    else:
        break
J = K = P + N - V
B = [0] + list(accumulate(A))
# print(I, J)
for i in range(J+1, I+1):
    # print(i, B[i-1], B[P-1] , (i - P), (A[i-1] + M) , (i - J) * M)
    if (i - P) * (A[i-1] + M) - B[i-1] + B[P-1] < (i - J) * M:
        break
    K = i
print(min(I, K))

Submission status: Accepted

Solution code:
from collections import Counter
N,M,V,P = map(int,input().split())
cntA = Counter(list(map(int,input().split())))
keyA = sorted(cntA.keys(),reverse=True)

selected_num = 0
dif_val = 0
dif_num = 0
for key in keyA:
  if selected_num < P:
    selected_num += cntA[key]
    if selected_num>=P:
      last_val = key
      last_val_num = cntA[key]
      prv_val = key
      prv_val_num = cntA[key]
  else:
    if last_val-key > M:break
    dif_val += (dif_num+prv_val_num)*(prv_val-key)
    dif_num += prv_val_num
    if dif_val <= (N-V)*M:
      selected_num += cntA[key]
    else:break
    prv_val = key
    prv_val_num = cntA[key]
    #print(last_val, last_val_num, key, M, selected_num)
print(selected_num)

Submission status: Accepted

Solution code:
N,M,V,P = list(map(int,input().split()))
A = list(map(int,input().split()))

A.sort(reverse  = True)

B = [0]
b = 0

for i in range(N):
    b+=A[i]
    B.append(b)

count = 0

def bisect(x,l,r):
    if A[l]<=x:
        return l-1
    elif A[r]>x:
        return r
    while r-l > 1:
        if A[(l+r)//2]>x:
            l = (l+r)//2
        else:
            r = (l+r)//2
    return l

for i in range(N):
    if i <= N-V+P-1:
        if A[i]+M>=A[P-1]:
            count+=1
    else:
        if A[i]+M>=A[P-1]:
            """
            index = bisect(A[i]+M,0,i-1)
            if index==-1:
                if (i*(A[i]+M) - B[i])%(V-(N-i)) == 0:
                    if (i*(A[i]+M) - B[i])//(V-(N-i)) >= M:
                        count+=1
                        print(A[i])
                else:
                    if (i*(A[i]+M) - B[i])//(V-(N-i)) >= M-1:
                        count+=1
                        print(A[i])
            else:
                if ((i-index-1)*(A[i]+M) - (B[i]-B[index+1]))%(V-(N-i)-(index+1)) == 0:
                    if ((i-index-1)*(A[i]+M) - (B[i]-B[index+1]))//(V-(N-i)-(index+1)) >= M:
                        count+=1
                        print(A[i])
                else:
                    if ((i-index-1)*(A[i]+M) - (B[i]-B[index+1]))//(V-(N-i)-(index+1)) >= M-1:
                        count+=1
                        print(A[i])
            """
            #print("x",A[i])
            #print(((i-P+1)*(A[i]+M) - (B[i]-B[P-1])))
            #print((V-(N-i)-(P-1)))
            if ((i-P+1)*(A[i]+M) - (B[i]-B[P-1]))%(V-(N-i)-(P-1)) == 0:
                if ((i-P+1)*(A[i]+M) - (B[i]-B[P-1]))//(V-(N-i)-(P-1)) >= M:
                    count+=1
            else:
                if ((i-P+1)*(A[i]+M) - (B[i]-B[P-1]))//(V-(N-i)-(P-1)) >= M:
                    count+=1

print(count)

Submission status: Accepted

Solution code:
import bisect
import sys
import math
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

K = A[-P]
R = bisect.bisect_left(A, K)
RL = bisect.bisect_right(A, K)
L = bisect.bisect_left(A, K - M)
ans = N - R
table = [0]*N
for i in range(L, R):
    table[i] = K - A[i]
table2 = [0]*N
for i in range(L, R):
    table2[i] = table2[i-1] + table[i]

X = table2[R-1]

for i in range(L, R):
    # print("i:", i, P+i, V > P+i)
    if V > P+i:
        v = V - (P+i)
        D = N-P - i
        # print(A[i], v*M, -(v*M - (X - table2[i])))
        if (-((-(v*M - (X - table2[i]))) // D)) + K <= A[i]+M:
            ans += 1

    else:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s=[None]*N
t=0
for i in range(N):
    t+=A[i]
    s[i]=t
S=M*(N-V)
l=P
r=N
if P==1:
    a=0
else:
    a=s[P-2]
while l<r:
    m=(r - l) // 2 + l
    if A[P-1]-M>A[m]:
        r=m
        continue
    if s[m-1]-a-(m-P+1)*A[m]>S:
        r=m
        continue
    l=m+1
print(l)

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
 
lim_A = A[p-1]
res_A = A[p:]
res_n = len(res_A)
 
for i in range(res_n):
    res_A[i] = lim_A - res_A[i]
 
ans = p
cnt = 0
for i in range(res_n):
    if m >= res_A[i] and m * max(v-p-(res_n-i-1), 0) <= cnt + (m-res_A[i])*(i+1):
        ans += 1
    cnt += res_A[i]
 
print(ans)

Submission status: Accepted

Solution code:
import bisect
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
kijun=a[p-1]
s=[0]*n
for i in range(n):
  s[i]+=s[i-1]+a[n-i-1]
if p>=v:
  print(n-bisect.bisect_left(a[::-1],kijun-m))
else:
  for i in range(n)[::-1]:
    rem=m*max(0,v-(n-i+p-1))
    if rem+(s[n-p]-s[n-1-i]) <= (a[i]+m)*(i-p+1) and a[i]+m >= kijun:
      print(i+1)
      break
    else:
      pass

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def judge(i):
    thres = a[i] + m
    rem = m * v - (n - i) * m
    rank = 0
    memo = 0
    for j in range(i):
        if a[j] > thres:
            rank += 1
            rem = max(rem-m, 0)
        else:
            if rank < p-1:
                rank += 1
                rem = max(rem-m, 0)
            else:
                rem = max(rem-(thres-a[j]), 0)
        if rank > p -1:
            break
    # print(i, a[i], thres, rem)
    if rank <= p - 1 and rem == 0:
        return True
    else:
        return False
l = 0
r = n-1

while True:
    if r - l == 1:
        if judge(r):
            print(r+1)
        else:
            print(l+1)
        break
    i = (r + l) // 2
    if judge(i):
        l = i
    else:
        r = i

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

B = [0] * N
B[0] = A[0]
for i in range(1, N):
    B[i] = B[i - 1] + A[i]

if V <= P:
    tmp = bisect_left(A[:-P], A[-P] - M)
    print (N - tmp)
    exit()

v = V - (P - 1) #P-1個は関係ないところですでに使用済み

#大丈夫かどうかの確認
def check(x):
    if A[x] + M < A[-P]:
        return False
    if v - 1 <= x:
        return True
    
    zan = M * (v - (x + 1))
    # print ('zan', zan)
    if x > 0:
        used = B[-P] - B[x]
    else:
        used = B[-P]
    # print ('used', used)
    if (A[x] + M) * ((N - P) - x) - used >= zan:
        return True
    return False     

#二分探索の初期値
l = 0
r = N - P
while r - l > 1:
    # print (l, r)
    # s = str(input())
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid
# print (A)
# print (B)
if check(l):
    print (N - l)
    exit()
if check(r):
    print (N - r)

# for i in range(N - P):
#     print (i, check(i))

# print ('v', v)