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: Runtime Error

Solution code:
N,M,V,P = map(int, input().split())
As = list(map(int, input().split()))
As.sort(reverse=True)
# print(As)
"""
M人がV問のスコアを1挙げられる
N問のうち降順に並べたP問が採用される

6 1 2 2
2 1 1 3 0 2
方針
最小の数(-1)にVを足す
上からP-1番目までの数にMを足す
P番目の数がVを超えているかどうか判定
最小の数からindex-1
"""


x = N - (P-1)
y = max(0, V - P - 1) #除外対象
# print(P-1,y)
if y == 0:
    As = As[P-1:]
else:
    As = As[P-1:-y]
# 同じは弾く
As = [a for a in As if a > As[y]]
# print(As)
mx = max(As)
cnt = 0
for a in As:
    if a + M >= mx:cnt+=1
print(P-1+cnt)

Submission status: Runtime Error

Solution code:
def check_pickedup(M: int, V: int, P: int, A: list, accum_score: list, i: int) -> bool:
    th_score = A[P-1]
    if A[i] >= th_score:
        return True
    sum_surplus = accum_score[i-1] - accum_score[P-2]
    if th_score - A[i] <= M and sum_surplus <= M*V:
        return True
    return False

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    
    accum_score = [A[0]] * N
    for i in (1, N):
        accum_score[i] = accum_score[i-1] + A[i]
    
    # Reduce N-V scores each judge
    ans = 0
    was_checked = {}
    for i, a in enumerate(A):
        # Check a will be picked up
        if a in was_checked:
            ans += 1
            continue
        if check_pickedup(M, V, P, A, accum_score, i):
            ans += 1
            was_checked[a] = True
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

A.sort()

def condition(num):
    save=A[num]
    A[num]+=M
    x=A[num]
    A.sort(reverse=True)
    index=A.index(x)
    k=index+1
    if k>P:
        A[index]=save
        A.sort()
        return False
    else:
        B=[x-A[i] for i in range(index+1,len(A))]
        count=0
        n=len(B)
        if 0>=V-k:
            A[index]=save
            A.sort()
            return True
        q=n%(V-k)
        r=n%(V-k)
        for i in range(0,q):
            if i>0:
                count+=(B[r-1+q*i]-B[r-1+q*i-q])*(q-i)
            else:
                count+=B[r-1]*q
        A[index]=save
        A.sort()
        return count>=M

start=0
end=N-1
while end-start>1:
    test=(end+start)//2
    if condition(test):
        end=test
    else:
        start=test
if condition(start):
    print(N-start)
else:
    print(N-end)

Submission status: Runtime Error

Solution code:
import bisect

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

Ap = A[-P] # 初期状態でP番目に大きい点数
idx = bisect.bisect_left(A, Ap) # 初期状態で得点がApより小さい問題の数
ans = N - idx # 初期状態で得点がAp以上であれば候補に入る


for i, a in enumerate(A[:idx]):
  j = 1
  b = a + M
  if b < Ap:
    continue
  n0 = bisect.bisect_right(A, a) # M人全員から投票されてもbを超えない問題の数
  n1 = N - bisect.bisect_left(A, b+1) # 投票されない状態で既にbより点数が高い問題の数
  mv = (V - n0) * M # 上の問題達には取り敢えず投票しておいて、他に選べる問題の数
  if mv <= 0:
    j = 0
    break
  else:
    res = False
    p = P - 1
    for _a in A[n0:][::-1]:
      if p:
        p -= 1
        diff = M
      else:
        diff = b - _a
      if diff <= 0:
        break
      else:
        mv -= diff
        if mv <= 0:
          res = True
          j = 0
          break
    if res:
      break

ans += idx - i - j # 一度候補に入る数を発見したら、それ以降も当然候補に入る
print(ans)

Submission status: Runtime Error

Solution code:
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
     
def is_ok(i):
  if i<0: return False
  cur,rival = A[i]+M, A[N-P]
  if cur < rival: return False
  rem_p = V - P - i
  if rem_p <= 0: return True
  j = 0
  for k in range(i+1,N-P+1):
    z = min(M, cur-A[k])
    j += z
    if j >= rem_p * M: return True
    return False
     
ok = N-P
ng = -1
while ok-ng > 1:
  m = (ok+ng)//2
  if is_ok(m):
    ok = m
    else:
      ng = m
     
print(N-ok)

Submission status: Runtime Error

Solution code:
from collections import Counter
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
l = 0
r = n+1
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r:
    mid = (l+r)//2
    a[n]

Submission status: Runtime Error

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

for i in range(n):
  if a[i] + m >= a[n-p]:
    b = a[:i] + a[i+1:n-p]
    for j in range(m):
      for k in range(v-p):
        b[k] += 1
        b.sort()
    if a[i] + m >= b[-1]:
      ans = n-i
      break
      
print(ans)

Submission status: Runtime Error

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-P)

    if s<A[-P]:
        return(0)
    else:
        if a>0:
            tempSUM+=a*M
            if s>tempSUM//(N-P)) or s==tempSUM//(N-P)) and tempSUM%(N-P)) == 0:
                return(1)
        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Runtime Error

Solution code:
N,A,B=map(int,input().split())
if (B-A)%2==0:
    ans=(B-A)/2
else:
    #2人のどちらかが卓1,Nのいずれかに到達するのに必要なラウンド数
    #1は偶奇を調整するためのラウンド
    #(B-A-1)/2は偶奇の調整後に2人が出会うまでのラウンド数
    ans=min(A-1,N-B)+1+(B-A-1)/2 
print(int(ans))

Submission status: Runtime Error

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

A.sort(reverse=True)

cum_A = [0]
for ai in A:
    cum_A.append(cum_A[-1] + ai)

cur_Ai = A[P]
ans = P
j = 0
for i in range(P, N):
    if (i + 1 < N) and (A[i] == A[i + 1]):
        continue

    while A[j] >= A[i] + M:
        j += 1

    if A[i] + M < A[P - 1]:
        break
    elif (
        M * (P - 1)
        + (A[i] + M) * (i + 1 - j)
        - (cum_A[i + 2] - cum_A[j])
        + M * (N - i - 1)
        >= M * V
    ):
        ans = i + 1
    else:
        break

print(ans)

Submission status: Runtime Error

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

A.sort(reverse=True)

cum_A = [0]
for ai in A:
    cum_A.append(cum_A[-1] + ai)

cur_Ai = A[P]
j = 0
for i in range(P, N):
    if (i + 1 < N) and (A[i] == A[i + 1]):
        continue
        
    while A[j] >= A[i] + M:
        j += 1

    print(i, j)
    if A[i] + M < A[P - 1]:
        break
    elif (
        M * (P - 1) + (A[i] + M) * (i + 1 - j) - sum(A[j : i + 1]) + M * (N - i - 1)
        >= M * V
    ):
        ans = i + 1
    else:
        break

print(ans)

Submission status: Runtime Error

Solution code:
#%%
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)

def check(i, n, m, v, p, a):
    if (v + i + 1 - p - n) <= 0:
        if a[i] + m >= a[p]:
            return True
        else:
            return False
    else:
        after = a[i] + m
        s = 0
        for j in range(p, i):
            s += after - a[j]
        if s >= (v + i + 1 - p - n) * m:
            return True
        else:
            return False

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

ans = l
if check(l, n, m, v, p, a):
    ans = l + 1
    if check(l+1, n, m, v, p, a):
        ans += 1
print(ans)

"""
print(a)
for i in range(n):
    print(check(i, n, m, v, p, a))
"""

Submission status: Runtime Error

Solution code:
def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    sorted_A = sorted(A, reverse=True)

    def is_possible(i):
        # Aは降順 -> sorted_A、
        # i+1番目以降の問題のスコアをi番目の問題のスコア以下になるように投票すれば
        # i番目の問題に採用される可能性が生まれるという考え方

        # 投票前の上位P問は採用される可能性がある
        if i < P:
            return True

        # 残り投票数
        num_votes = V * M

        # i番目の問題を採用させようとする場合は、M人のジャッジ全員がi番目の問題に投票すればよい
        score_i = sorted_A[i] + M
        num_votes -= M

        # M人のジャッジ全員がi番目の問題に投票しても、上位P問にスコアが上がらない場合は採用される可能性がない
        if sorted_A[P - 1] > score_i:
            return False

        # 上の操作からi+1番目以降のの問題のスコアを、i番目の問題のスコアを超えることがないため、
        # M人のジャッジ全員がi+1番目以降の問題に投票してもよい
        num_votes -= (N - i - 1) * M

        # i番目の問題が上位P問に入ればよいので、P-1位の問題にもM人のジャッジ全員が投票してもよい
        num_votes -= (P - 1) * M

        # P番目からi番目
        # print('margin: {}, num_votes: {}'.format(sum(score_i - j for j in sorted_A[P-1 : i]), num_votes))
        return sum(score_i - j for j in sorted_A[P-1 : i]) >= num_votes

    # 1番目は必ず採用される
    # N番目は採用されるか
    if is_possible(N-1):
        print(N)
    # 1番目:採用、N番目:採用されない
    # -> [1:N-1]のどこに採用の境界があるかを二分探索する
    else:
        low = 0
        hight = N - 1

        while hight - low > 1:
            middle = (hight + low) // 2
            # print('PRE - low:{}, middle:{}, hight:{}'.format(low, middle, hight))
            if is_possible(middle):
                low = middle
            else:
                hight = middle
            # print('AFT - low:{}, middle:{}, hight:{}'.format(low, middle, hight))

    print(low + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    sorted_A = sorted(A, reverse=True)

    def is_possible(i):
        # Aは降順 -> sorted_A、
        # i+1番目以降の問題のスコアをi番目の問題のスコア以下になるように投票すれば
        # i番目の問題に採用される可能性が生まれるという考え方

        # 投票前の上位P問は採用される可能性がある
        if i < P:
            return True

        # 残り投票数
        num_votes = V * M

        # i番目の問題を採用させようとする場合は、M人のジャッジ全員がi番目の問題に投票すればよい
        score_i = sorted_A[i] + M
        num_votes -= M

        # M人のジャッジ全員がi番目の問題に投票しても、上位P問にスコアが上がらない場合は採用される可能性がない
        if sorted_A[P - 1] > score_i:
            return False

        # 上の操作からi+1番目以降のの問題のスコアを、i番目の問題のスコアを超えることがないため、
        # M人のジャッジ全員がi+1番目以降の問題に投票してもよい
        num_votes -= (N - i - 1) * M

        # i番目の問題が上位P問に入ればよいので、P-1位の問題にもM人のジャッジ全員が投票してもよい
        num_votes -= (P - 1) * M

        # P番目からi番目
        # print('margin: {}, num_votes: {}'.format(sum(score_i - j for j in sorted_A[P-1 : i]), num_votes))
        print((V - 1 - (N-i-1) - (P-1)) * M)
        return sum(score_i - j for j in sorted_A[P-1 : i]) >= num_votes

    # 1番目は必ず採用される
    # N番目は採用されるか
    if is_possible(N-1):
        print(N)
    # 1番目:採用、N番目:採用されない
    # -> [1:N-1]のどこに採用の境界があるかを二分探索する
    else:
        low = 0
        hight = N - 1

        while hight - low > 1:
            middle = (hight + low) // 2
            # print('PRE - low:{}, middle:{}, hight:{}'.format(low, middle, hight))
            if is_possible(middle):
                low = middle
            else:
                hight = middle
            # print('AFT - low:{}, middle:{}, hight:{}'.format(low, middle, hight))

    print(low + 1)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + u_cnt >= v-1:
        return True
    cnt = 0
    for ind,item in enumerate(a):
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    if cnt >= m*v:
        return True
    else:
        return False

ok = n-1
ng = 0
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-mid)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)

#NUM = [0] * N
#ACN = [0] * N
NUM = {}
ACN = {}
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    if d in NUM:
        NUM[d] += 1
    else:
        NUM[d] = 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)


NUM = [0] * N
#ACN = [0] * N
ACN = {}
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt


# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)


NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

print(1)
exit()
    
# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

print(1)
exit()

    
# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()
        
print(1)
exit()


#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

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

a.sort()

b = [a[x] for x in range(n - p)]

total = sum(b)

vote=(v - p) * m

ans = p

for n, i in enumerate(b):
    if (total - i + vote) // (len(b) - 1) <= i + m:
        ans += len(b) - n - 1
        break

print(ans)

Submission status: Runtime Error

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

a.sort()

b = [a[x] for x in range(n - p)]

total = sum(b)

vote=(v - p) * m

ans = p

for i in b:
    if (total - i + vote) // (len(b) - 1) < i + m:
        ans += 1
        
print(ans)

Submission status: Runtime Error

Solution code:
from inspect import currentframe

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)
    
    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    C = sorted_dic_A[P:]

    num_vote = M * V
    a = 0
    b = (N - (P - 1))
    i = (a + b) // 2
    pre_i = i
    while True:
        # input()
        # print("(a, i, b): ({}, {}, {})".format(a, i, b))
        v = C[i][1]
        if P_min_val > v + M:
            break
        margin = num_vote
        margin -= M * (P-1)
        margin_list = [v+M-w for (j,w) in C if j!=i]
        mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
        margin -= M
        margin -= sum(mod_margin_list)
        # print("margin: {}".format(margin))
        if margin > 0:
            # break
            b = i
            i = (a + i) // 2
        else:
            a = i
            i = (i + b) // 2

        if pre_i == i:
            i += 1
            break
        pre_i = i

    print(i + P)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read = sys.stdin.buffer.read

n,m,v,p = map(int,input().split())
lis = np.array(read().split(),np.int64)



lis.sort()

def test(i):
    if n-i <= p:
        return True

    num = lis[i] + m
    li = np.zeros(n,np.int64)
    li = num-lis
    li = np.minimum(li,m)
    li[n-p+1:] = m
    if(li < 0).any():
        return False
    li[i] = 0
    x = li.sum()
    return li.sum() >= m * (v-1)

low = -1
high = n-1

while low +1 < high:
    mid = (low + high) // 2
    if test(mid):
        low = mid
    else:
        high = mid

ans = n-high

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np

n,m,v,p = map(int,input().split())
lis = list(map(int,input().split()))



lis.sort()

def test(i):
    if n-i <= p:
        return True
    
    num = lis[i] + m
    li = np.zeros(n,np.int64)
    li = num-lis
    li = np.minimum(li,m)
    li[n-p+1:] = m
    if(li < 0).any():
        return False
    li[i] = 0
    x = li.sum()
    return li.sum() >= m * (v-1)
    
low = -1
high = n-1

while low +1 < high:
    mid = (low + high) // 2
    if test(mid):
        low = mid
    else:
        high = mid

ans = n-high

print(ans)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

print(1)
exit()

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

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

A=list(map(int,input().split()))

A=sorted(A,reverse=True)

l=p-1
r=min(p-1+(n-v)+1,n-1)
r=k
print(A)
while(r-l>1):
  if A[(r+l)//2]+m >= A[p-1]:
    l=(r+l)//2
  else:
    r=(r+l)//2
if r=n-1:
  print(l+1)
else:
  
print(l,r)
print(A[r],m,A[p-1])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
from collections import deque

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

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

A = list(map(int, input().split()))
A.sort(reverse=True)

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    if P == N-1:
        A = list(set(A))
        A.sort()
        if A[1] <= A[0] + M:
            print(N)
        else:
            print(N-1)

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    A = A[:-(P-1)]
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        C = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        # C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = bisect_left(C, inner_mid)
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < C[0]:
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # M回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(N-bisect_left(A, Y))

    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: Runtime Error

Solution code:
a = sorted(list(map(int, input().split())), reverse=True)

#　せっかくなのであとでpossibleを前計算してm*v以上をbisectでもやる
def isOK(x):
  x -= 1
  if a[x] + m < a[p-1]:
    return False
  elif x+1 <= p:
    return True
  else:
    pos = m * n
    for i in range(p-1,x):
      pos -= a[i] - a[x]
    if pos >= m * v:
      return True
    else:
      return False

def binary_search():
    ok = p-1
    ng = n
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans = binary_search()  
print(ans)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int, input().split())
pre = list(map(int, input().split()))
li = sorted(pre)
total = M * V
tf = False
for i in range(N):
	if li[i] + M >= li[-P]:
		tmp = i+1 + P - 1
		nokori = total - (M * tmp)
		count = i + 1
		while count <= N - P:
			if nokori <= 0:
				ans = N-i
				tf = True
				break	
			sa = (li[i]+M) - li[count]
			if sa <= 1:
				count += 1
				continue
			nokori -= sa-1
			count += 1
		if tf == True:
			break
print(ans)