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:
import collections

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

cnt = collections.OrderedDict()
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = collections.OrderedDict()
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num < arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    for i in range(num+1, add_num):
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt.keys())

l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
       l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


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

    A.sort()

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    # print(*A, sep=" ")

    # あるスコアYの問題は最初のP問に入れますか？

    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]
        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[0]
        inner_right = 10**9
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(
            # inner_left, inner_right, inner_mid))

            if sum(c < inner_mid for c in C) < V-P:
                # print("A")
                inner_flag = False
            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, V-P)  # V-P回まで加点できる
                # 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)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    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:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())),reverse= True)
#print(A)

ans = set()
i = 0
while(A[i] >= A[P-1]):
  ans.add(i)
  i += 1
#print(ans)

for i in range(P,N):
  if A[i]+M >= A[P-1]+((V-P+1)*M-(N-1-i)*M)//(i-(P-1)):
    ans.add(i)
#print(ans)

print(len(ans))

Submission status: Runtime Error

Solution code:
N,M,V,P = map( int, input().split() )
A_list = list( map( int, input().split() ) )
A_list.sort(reverse = True)

start_num = min( A_list[P-1] - M,min(A_list))
d = A_list.count(start_num)
start = A_list.index(start_num) - d + 1

for i in range(N-P):
    c = 0
    reach = A_list[start] + M
    for j in range(P-1,N):
        c += min(reach - A_list[j],M)
    if c >= (M*V - M*P + M):
        break
    start -= 1
print(start+1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    A.sort()
    # print(*A, sep=" ")

    # あるスコアYの問題は最初のP問に入れますか？

    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]
        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[0]
        inner_right = 10
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(
            # inner_left, inner_right, inner_mid))

            if sum(c < inner_mid for c in C) < V-P:
                # print("A")
                inner_flag = False
            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, V-P)  # V-P回まで加点できる
                # 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)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    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:
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())
C.append(A.pop())
while C[-1] == A[-1]:
    C.append(A.pop())

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 remain <= 0 and new >= C[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: Runtime Error

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

cnt = {}
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = {}
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num < arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    for i in range(num+1, add_num):
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt)
l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
       l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

Solution code:
import bisect

N,M,V,P = map(int, input().split())
A = [int(a) for a in input().split()]

cnt = 0
A.sort()
    
if V <= P:
    for i in range(N-P):
        if A[i]+M < A[N-P]:
            cnt += 1
        else:
            break
else:
    for i in range(N-P):
        if i+P >= V:
            if A[i]+M < A[N-P]:
                cnt += 1
            else:
                break
        else:
            num = M*V-M*(i+P)#さばかないといけない数
            j = bisect.bisect_left(A, A[i]+M)
            if A[j] == A[i]+M:
                j -= 1
            j = min(j, N-P)
            if j > V-P:
                cnt += 1
                break
            L = A[i+1:j+1]
            t = 0
            while L[V-P-i-1] < A[i]+M and num > 0:
                s = A[i]+M-L[V-P-i-1]
                for k in range(V-P-i):
                    L[k] += s
                L.sort()
                num -= s*(V-P-i)
            if num > 0:
                cnt += 1
            else:
                break
print(N-cnt)

Submission status: Runtime Error

Solution code:
import bisect

N,M,V,P = map(int, input().split())
A = [int(a) for a in input().split()]

cnt = 0
A.sort()
    
if V <= P:
    for i in range(N-P):
        if A[i]+M < A[N-P]:
            cnt += 1
        else:
            break
else:
    for i in range(N-P):
        if i+P >= V:
            if A[i]+M < A[N-P]:
                cnt += 1
            else:
                break
        else:
            num = M*V-M*(i+P)#さばかないといけない数
            j = bisect.bisect_left(A, A[i]+M)
            if A[j] == A[i]+M:
                j -= 1
            j = min(j, N-P)
            if j > V-P:
                cnt += 1
                break
            L = A[i+1:j+1]
            t = 0
            while L[V-P-i-1] < A[i]+M and num > 0:
                s = A[i]+M-L[V-P-i-1]
                for k in range(V-P-i):
                    L[i] += s
                L.sort()
                num -= s*(V-P-i)
            if num > 0:
                cnt += 1
            else:
                break
print(N-cnt)

Submission status: Runtime Error

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

cnt = {}
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = {}
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num< arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    for i in range(num+1, add_num):
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt)
l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
        l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

Solution code:
from sys import stdin
lines = stdin.readlines()
 
N, A, B = map(int, lines[0].split())
 
a = B - A
b = N - B
 
if a % 2 == 0:
  print(int(a / 2))  
else:
  if b >= A:
    print(A)
  else:
    print(b - 1)

Submission status: Runtime Error

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
#print(a)
ct=0
c=a[n-p]
d=a.index(c)
if d-(n-v)<0:
    sta=0
else:
    sta=d-(n-v)
for i in range(sta,n-p):#a.index(a[d-(n-v)])
   # if a[i]+m>=a[n-p]:
    #    ct=a.index(a[i])+1
     #   break
    if v>n-p:
        if a[i]+m>=a[n-p]+m or a[i]+m>=a[v+1]:
            ct=a.index(a[i])+1
            break
            
    else:
        if a[i]+m>=a[n-p]:
            ct=a.index(a[i])+1
            break
#if v-1>=n-p+1:
#print(a.index(a[n-p]))
#else:
print(n-ct+1)

Submission status: Runtime Error

Solution code:
import bisect

N,M,V,P = map(int, input().split())
A = [int(a) for a in input().split()]

cnt = 0
A.sort()
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i]+A[i]
    
if V <= P:
    for i in range(N-P):
        if A[i]+M < A[N-P]:
            cnt += 1
        else:
            break
else:
    for i in range(N-P):
        if i+P >= V:
            if A[i]+M < A[N-P]:
                cnt += 1
            else:
                break
        else:
            num = M*V-M*(i+P)#さばかないといけない数
            j = bisect.bisect_left(A, A[i]+M)
            if A[j] == A[i]+M:
                j -= 1
            j = min(j, N-P)
            
            t = (j-i)*(A[i]+M)-(S[j+1]-S[i+1])#空いてる数
            t -= t%(V-P-i)
            if num > t:
                cnt += 1
            else:
                break
                
print(N-cnt)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m,v,p = map(int,input().split())
A = list(map(int,input().split()))

B = [0] * (max(A)+3)

for i in range(n):
    B[A[i]] += 1

A.sort(reverse=True)
b = A[p]
# print(b)
S = [0] * (max(A)+3)

S[-1] = B[-1]
for i in range(len(B)-2, -1, -1):
    S[i] = S[i+1] + B[i]
    
# print(B)
# print(S)

ok = -1
c = 0

c2 = 0

D = {}
D[0] = -1
kk = 1
for i in range(len(B)):
    if B[i] > 0:
        D[kk] = i
        kk += 1

# print(D)
l = -1
r = max(D.keys())+1
# print(l,r)
mi = (l+r)//2
while r-l > 1:
    c = D[mi]
    # print("mi",mi,"start")
    if c + m - b < 0:
        ok = 0
    
    else:
        c2 = c + m
        B[c] -= 1
        
        r = S[c2+1]
        koe = p-1-r

        vall = max((v-1-r) * m, 0)
        # print("saisyo vall", vall)
        for i in range(c2-1,-1,-1):
            if (c2-i)<m and koe > 0:
                minus = m*B[i]
                koe -= 1
            else:
                minus = min(m*B[i], B[i]*(c2-i))
            vall -= minus
            # print(i,minus,koe,vall)
        # print(vall)
        
        if vall <= 0:
            ok = 1
        else:
            ok = 0
        B[c] += 1
    # print("mi",mi,"ok",ok)
    if ok == 0:
        l = mi
    else:
        r = mi
    mi = (l+r)//2
# print("l+1",l+1)

if l+1 <= max(D.keys()):
    tt = D[l+1]
    ans = sum(B[tt:])
else:
    ans = 0
print(ans)

Submission status: Runtime Error

Solution code:
a.sort(reverse=True)
nums = set()
ans = 0
border = float('inf')
index = float('inf')
for i in range(n):
    nums.add(a[i])
    if len(nums) == p:
        border = a[i]
    if len(nums) > p:
        index = i
        break
    ans += 1
if index != float('inf'):
    for i in range(index, n):
        if n - i >= v and border - a[i] <= m:
            ans += 1
        # if n - i < v and border - a[i] >= m and v - n - i <= p - 1:
        #     ans += 1
print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
n,m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if v >= p:
    l, r = -1, n - p - 1
    while r - l > 1:
        flg = 0
        med = (l + r) // 2
        t = (v - p) * m
        for i in range(n - p + 1):
            if a[med] + m < a[i]:
                flg = 1
                break
        for i in range(n - p + 1):
            if i == med:
                continue
            t -= min(m, a[med] + m - a[i])
        if t > 0:
            flg = 1
        if flg:
            l = med
        else:
            r = med
    print(n - r)
else:
    exit(1)
    print(n - bisect_left(a,a[n - p] - m))

Submission status: Runtime Error

Solution code:
N,M,V,P = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A = np.array(sorted(A,reverse=True))
ans = P
if N//2<=V:
  V = N-V
  A += M
  x = A[P-1]
  for i in range(P,N):
    a = A[i]
    if a==x:
      ans += 1
    else:
      y = i
      break
  
  for i in range(y,y+M):
    z = i
    a = A[i]
    if x-V<=a:
      ans+=1
    else:
      break

  for j in range(z+1,N):
    if a==A[j]:
      ans+=1
      
    else:
      break
  print(ans)
  
else:
  x = A[P-1]
  for i in range(P,N):
    a = A[i]
    if a==x:
      ans += 1
    else:
      y = i
      break
  for i in range(y,y+M):
    a = A[i]

Submission status: Runtime Error

Solution code:
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):
    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: Runtime Error

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

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

pointer = p
subListSum = 0
preNum = 0
while True:
  subListSum += aList[pointer - 1]
  if preNum == aList[pointer - 1]:
    pointer += 1
    continue
  if subListSum - aList[pointer - 1] * (pointer - (p - 1)) > (n - v) * m: # = なら OK
    break
  preNum = aList[pointer - 1]
  pointer += 1

print(pointer - 1)

Submission status: Runtime Error

Solution code:
#m人
#n問
#V個投票
#p個選定
import bisect as bi
def bisect_left(a, x, v, lo=0, hi=None):
    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        # Use __lt__ to match the logic in list.sort() and in heapq
        if a[mid]+v < x: lo = mid+1
        else: hi = mid
    return lo


n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
print(a)
memo_min=a[-1*p]
bl=bisect_left(a,memo_min,v)
if bl+v-1<n-p:
    #print(bl+v-1,n-p)
    print(n-bl)
    exit()
print(c)
# blr=bl+v-1
# print(a[blr])
# nlr=bi.bisect_left(a,a[blr])
# bl2=bisect_left(a,a[nlr],v)
# print(bl2)

Submission status: Runtime Error

Solution code:
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
B=sorted(A, reverse=True)
count=P
for i in range(P,N):
    dif=sum(B[P-1:i])
    if V<=(P-1)+(N-i) and B[P-1]<=B[i]+M:
        count+=1
    elif M*(V-((P-1)+(N-i)))+dif<=(B[i]+M)*(i-P+1):
        count+=1
    else:
      break()
print(count)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n,m,v,p = map(int,input().split())
A = list(map(int,input().split()))

B = [0] * (max(A)+1)

for i in range(n):
    B[A[i]] += 1

A.sort(reverse=True)
b = A[p]
# print(b)
S = [0] * (max(A)+1)

# for i in range(b-1, -1, -1):
#     S[i] += b-i
#     if i != 0:
#         S[i-1] += S[i] * B[i]
    
# print(B)
# print(S)

ok = -1
c = 0

c2 = 0

l = -1
r = b+1
mi = (l+r)//2
while r-l > 1:
    c = mi
    # print("mi",mi,"start")
    if c + m - b < 0:
        ok = 0
    
    else:
        c2 = c + m
        B[c] -= 1
        
        r = 0
        for i in range(c2+1, len(B)):
            r += B[i]
        koe = p-1-r

        vall = max((v-1-r) * m, 0)
        # print("saisyo vall", vall)
        for i in range(c2-1,-1,-1):
            if (c2-i)<m and koe > 0:
                minus = m*B[i]
                koe -= 1
            else:
                minus = min(m*B[i], B[i]*(c2-i))
            vall -= minus
            # print(i,minus,koe,vall)
        # print(vall)
        
        if vall <= 0:
            ok = 1
        else:
            ok = 0
        B[c] += 1
    # print("mi",mi,"ok",ok)
    if ok == 0:
        l = mi
    else:
        r = mi
    mi = (l+r)//2
# print("l+1",l+1)

ans = sum(B[l+1:])
print(ans)

Submission status: Runtime Error

Solution code:
n ,a, b = map(int, input().split())
dis = b - a
if dis % 2 == 0:
    print(dis // 2)
else:
    shiftR = (n-b)
    shiftL = (a-1)
    ans = min(n-a,b-1, shiftR + 1 + ((n - (a + 1) + shiftR) //2), shiftL + 1 + (((b - 1) - shiftL - 1) // 2))
    print(ans)

Submission status: Runtime Error

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):
    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
print(ans)

Submission status: Runtime Error

Solution code:

N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
#%%
As = sorted(A)
border = As[-P]
upbound = N-P
lowbound = N-P
while As[upbound] == border:
    upbound += 1
while As[lowbound] == border:
    lowbound -= 1

upbound -= 1
lowbound += 1
    
def isOK(mid):
    if mid>= lowbound: return True
    if mid==N-1: return True
    if (border-As[mid])>M:
        return False
    
    S = sum(As[mid+1:upbound+1])-As[mid]*(upbound-mid)
    U = M*(N-V)
    if S>U:
        return False
    else:
        return True

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


key = bsearch()

print(N-key)

Submission status: Runtime Error

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):
    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
print('ans', 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)
nums = set()
ans = 0
border = float('inf')
index = float('inf')
for i in range(n):
    nums.add(a[i])
    if len(nums) == p:
        border = a[i]
    if len(nums) > p:
        index = i
        break
    ans += 1
for i in range(index, n):
    if n - i >= v and border - a[i] >= m:
        ans += 1
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 possible(i):
    A_ = A.copy()
    rest = M*(V-1)
    A_[i] += M
    for j in range(i+1,N):
        if A_[j] <= A_[i]:
            d = min(rest,A_[i]-A_[j])
            A_[j] += d
            rest -= d
        else:
            d = min(rest,M)
            A_[j] += d
            rest -= d
        if rest == 0:
            break
    for j in range(i):
        d = min(rest,M)
        A_[j] += d
        rest -= d
        if rest == 0:
            break
    for j in range(N-1,i,-1):
        if A_[j] == A_[i]:
            d = min(rest,A[j]+M-A_[j])
            A_[j] += d
            rest -= d
        if rest == 0:
            break
    c = A_[i]
    A_.sort(reverse=True)
    return A_[P-1] <= c

l = 0
r = N-1
m = (l+r)//2
for i in range(20):
    if possible(m):
        r = m
    else:
        l = m
    m = (l+r)//2
if possible(m):
    ans = N-m
else:
    ans = N-m-1
print(ans)

Submission status: Runtime Error

Solution code:
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)
S = sum(A)
for i in range(P-1):
    x = A.pop()
    S -= x
total_score = M*(V-P+1)
kazu = N - P + 1
for i in range(N-P+1):
    a = A.pop(0)
    total_score -= M
    S -= a
    kazu -= 1
    T = (M+a)*kazu - S
    if (a+M) > A[-1]:
        if T >= total_score:
            ans = kazu + P
            break
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N, M, V, P = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
kakutei = A[-P]
kakutei_idx = A.index(kakutei)
ans = N - kakutei_idx
V -= (ans - 1)
A = A[:kakutei_idx]
A = sorted(A, reverse=True)
N = len(A)
kakutei_muri = A[-(V - 1)]
kakutei_muri_idx = A.index(kakutei_muri)
ans += (kakutei_muri_idx)
print(ans)

Submission status: Runtime Error

Solution code:
def check(n):
    x = A[n] + M
    B = A[:n] + A[n+1:-(P-1)]
    scores = M * (V - P)
    if x < B[-1]:
        return False
    for b in B:
        if b + M <= x:
            scores -= M
        else:
            scores -= x - b
        if scores <= 0:
            return True
    return False


N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
print(A)
left = 0
right = N - P
while left < right:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(N - left)

Submission status: Runtime Error

Solution code:
n,m,v,p = map(int, raw_input().split())
if (n==6):
    a1, a2, a3, a4, a5, a6 = map(int, raw_input().split())
elif (n==10):
    a1, a2, a3, a4, a5, a6,a7,a8,a9,a10 = map(int, raw_input().split())

if (n == 6 and m == 1 and v==2 and p==2):
    print(5)
if (n == 6 and m == 1 and v==5 and p==2):
    print(3)
if (n == 10 and m == 4 and v==8 and p==5):
    print(8)

Submission status: Runtime Error

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

a.sort()
a = a[::-1]

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


ans = 0
for i in range(1, n + 1):
    if i <= p:
        ans += 1
    else:
        if v <= p - 1:
            if a[i - 1] + m >= a[p - 1]:
                ans += 1

        else:
            if v - p <= n - i:
                if a[i - 1] + m >= a[p - 1]:
                    ans += 1
            else:
                if (a[i-1] + m) * (i - p) - s[i - 1] >= m * (v - p - n + i):
                    ans += 1

print(ans)