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: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
border = a[p-1]
to_border = 0
for i in range(p,n):
    new_border = a[i] + m
    if new_border < border:
        print(ans)
        exit()
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    possible_votes += to_border
    possible_votes += (new_border-border)*(i-p)
    if possible_votes >= m*v:
        ans += 1
        to_border += border-a[i]
    else:
        print(ans)
        exit()
print(ans)
exit()

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
border = a[p]
to_border = 0
for i in range(p,n):
    new_border = a[i] + m
    if new_border < border:
        print(ans)
        exit()
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    possible_votes += to_border
    possible_votes += (new_border-border)*(i-p)
    if possible_votes >= m*v:
        ans += 1
        to_border += border-a[i]
    else:
        print(ans)
        exit()
print(ans)
exit()

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
border = a[p]
to_border = 0
for i in range(p,n):
    new_border = a[i] + m
    if new_border < border:
        print(ans)
        exit()
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    possible_votes += to_border
    possible_votes += (new_border-border)*(i-p)
    print((i,possible_votes))
    if possible_votes >= m*v:
        ans += 1
        to_border += border-a[i]
    else:
        print(ans)
        exit()
print(ans)
exit()

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
border = a[p]
to_border = 0
for i in range(p,n):
    new_border = a[i] + m
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    possible_votes += to_border
    possible_votes += (new_border-border)*(i-p)
    if possible_votes >= m*v:
        ans += 1
        to_border += border-a[i]
    else:
        print(ans)
        exit()
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
border = a[p]
to_border = 0
for i in range(p,n):
    new_border = a[i]+m
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    possible_votes += to_border
    possible_votes += (new_border-border)*(i-p)
    if possible_votes >= m*v:
        ans += 1
        to_border += border-a[i]
    else:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
border = a[p]
to_border = 0
for i in range(p,n):
    new_border = a[i]+m
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    possible_votes += to_border
    possible_votes += (new_border-border)*(i-p)
    if possible_votes >= m*v:
        ans += 1
    else:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
ans = p
for i in range(p,n):
    border = a[i]+m
    possible_votes = 0
    possible_votes += (p+n-i-1)*m
    for j in range(p-1,i-1):
        possible_votes += border-a[j]
    if possible_votes >= m*v:
        ans += 1
    else:
        print(ans)
        exit()

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse = True)
border = a[p-1]
ans = p
toborder = 0
for i in range(p,n):
    if border - a[i] > m:
        print(ans)
        exit()
    if (p-1)+(n-1-i) >= v-1:
        ans += 1
        toborder += border-a[i]
        continue
    x = (v-1)-((p-1)+(n-1-i))
    if x*m - toborder >= (a[i]+m-border)*(i-p):
        print(ans)
        exit()
    else:
        ans += 1
        toborder += border-a[i]
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok(x):
        # x問目が選ばれるか判定
        voted = (P-1)*M + (N-x)*M + M
        for i in range(P, x):
            voted += min(max((A[x-1] + M - A[i-1]), 0), M)
        if M*V <= voted:
            return True
        else:
            return False

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

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()

n_surr = min(V - 1, P - 1)
for i in range(n_surr):
    A[-1 - i] += M

sum_tab = [0]
sum_tmp = 0
for i, Ai in enumerate(A):
    sum_tmp += Ai
    sum_tab.append(sum_tmp)

import bisect
    
acceptable = [False] * N
for i, Ai in enumerate(A):
    if i < N - 1 and Ai == A[i + 1]: continue
    #
    A_targ = Ai + M
    idx = bisect.bisect_right(A, A_targ)
    #
    n_vote = M * V - (n_surr + 1) * M
    n_safe = A_targ * idx - (sum_tab[min(idx + 1, N)] - sum_tab[0] - Ai)
    #
    # print("#", i, (n_vote, n_safe))
    if n_vote <= n_safe:
        acceptable[i] = True
    else:
        acceptable[i] = False

for i in range(N - 1):
    if A[-1 - i] == A[-2 - i]:
        acceptable[-2 - i] = acceptable[-2 - i] | acceptable[-1 - i]

# print("#", A)
# print("#", acceptable)

print(sum([int(flag) for flag in acceptable]))

Submission status: Wrong Answer

Solution code:
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok(x):
        # x問目が選ばれるか判定
        voted = (P-1)*M + (N-x)*M + M
        for i in range(P, x):
            voted += min((A[x-1] + M - A[i-1]), M)
        if M*V <= voted:
            return True
        else:
            return False

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

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)

    def is_ok(x):
        # x問目が選ばれるか判定
        voted = (P-1)*M + (N-x)*M + M
        for i in range(P, x):
            voted += (A[x-1] + M - A[i-1])
        if M*V <= voted:
            return True
        else:
            return False

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

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    print(a)
    while l+1 < r:
        i = (l+r) >> 1
        A = a[i]+m
        ri = bisect.bisect_right(a,A)
        j = n-ri
        if j >= p:
            l = i
            continue
        li = bisect.bisect_right(a,a[i])
        res = v-j-li
        if res <= 0:
            r = i
            continue
        res -= (p-j-1)
        s = 0
        for j in range(li,ri-(p-j-1)):
            s += A-a[j]
        if s >= res*m:
            r = i
        else:
            l = i
    print(n-r)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

def f(x):
  if x>=n-p:
    return 1
  elif a[x]+m<a[n-p]:
    return 0
  else:
    ct=(p-1)*m+m+x*m
    for i in range(x+1,n-p):
      ct+=a[x]+m-a[i]
    if ct>=m*v:
      return 1
    else:
      return 0

L=-1;R=n
while R-L>1:
  x=(L+R)//2
  if f(x)==1:
    R=x
  else:
    L=x
print(n-L-1)

Submission status: Wrong Answer

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

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

A.sort()
border = max(0, N - P)
ind = np.searchsorted(A, A[max(0,V-P):] + M, side = 'right')
ans = np.count_nonzero(ind >= border)

if ind[0] >= border:
	for i in reversed(range(max(0,V-P))):
		B = np.minimum(M, A[border] - A[i + 1:border + 1])
		S = np.sum(B)
		if S < M:
			a, b = divmod(M - S, border - i)
			B += a
			B[-b:] += 1
		A[i + 1: border + 1] += B
		if A[i] + M >= A[border]:
			ans += 1
		else:
			break

print(ans)

Submission status: Wrong Answer

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

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

A.sort()
border = N - P
ind = np.searchsorted(A, A[V-P:] + M, side = 'right')
ans = np.count_nonzero(ind >= border)
print(ans)

Submission status: Wrong Answer

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

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

A.sort()
border = N - P
ind = np.searchsorted(A, A[V-P:] + M, side = 'right')
ans = np.count_nonzero(ind >= border)

if ind[0] >= border:
	for i in reversed(range(V-P)):
		B = np.minimum(M, A[border] - A[i + 1:border + 1])
		S = np.sum(B)
		if S < M:
			a, b = divmod(M - S, border - i)
			B += a
			B[:b] += 1
		A[i + 1: border + 1] += B
		tmp_max = np.max(A[i+1:border+1])
		if A[i] + M >= tmp_max:
			ans += 1

print(ans)

Submission status: Wrong Answer

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

def isAcceptable(x):
  if x<P:
    return True
  elif alist[x]+M<alist[P-1]:
    return False
  else:
    okvote=(P-1)*M+(N-x)*M
    for i in range(P,x):
      okvote+=alist[x]+M-alist[i]
    
    #print(x,okvote,M*V-M)
    if okvote<=M*V-M:
      return False
    else:
      return True

l,r=0,N-1
while(l<=r):
  mid=(l+r)//2
  if isAcceptable(mid) and mid==N-1:
    break
  elif isAcceptable(mid) and not isAcceptable(mid+1):
    break
  elif isAcceptable(mid+1):
    l=mid+1
  else:
    r=mid-1
    
print(mid+1)

Submission status: Wrong Answer

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

def isAcceptable(x):
  if x<P:
    return True
  elif alist[x]+M<alist[P-1]:
    return False
  else:
    okvote=(P-1)*M+(N-x)*M
    for i in range(P,x):
      okvote+=alist[x]+M-alist[i]
    
    if okvote<M*V:
      return False
    else:
      return True

l,r=0,N-1
while(l<=r):
  mid=(l+r)//2
  if isAcceptable(mid) and mid==N-1:
    break
  elif isAcceptable(mid) and not isAcceptable(mid+1):
    break
  elif isAcceptable(mid+1):
    l=mid+1
  else:
    r=mid-1
    
print(mid+1)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m, v, p = map(int, readline().split())
a = sorted(tuple(map(int, readline().split())))
sum_a = sum(a)
for i in range(n):
    x = a[i] + m
    y = (sum_a - a[i] + m * (v - 1))
    check = y // (n - 1)
    if x > check:
        print(n - i)
        break
    elif x == check:
        if y % (n - 1) >= p + 1:
            print(n - i)
            break

Submission status: Wrong Answer

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

def judge(x):
    if N-P<=x<=N-1:
        return True
    
    cnt = 0
    
    for i in range(N-P+1):
        if i==x:
            continue
        
        cnt += min(M, A[x]+M-A[i])
    
    return cnt>=M*(V-P)

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

print(N-binary_search())

Submission status: Wrong Answer

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

def judge(x):
    if N-P<=x<=N-1:
        return True
    
    cnt = 0
    
    for i in range(N-P):
        if i==x:
            continue
        
        cnt += min(M, A[x]+M-A[i])
    
    return cnt>=M*(V-P)

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

print(N-binary_search())

Submission status: Wrong Answer

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

def judge(x):
    if N-P<=x<=N-1:
        return True
    
    cnt = 0
    
    for i in range(N):
        if i>=N-P+1:
            cnt += M
        else:
            cnt += min(M, A[x]+M-A[i])
    
    return cnt>=M*V

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

print(N-binary_search())

Submission status: Wrong Answer

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

A.sort()

def ok(x):
    if x == -1:
        return False
    if x >= n-p:
        return True
    cnt = 0
    for i in range(x+1, n-p):
        cnt += max((A[x]+m)-A[i], 0)
    cnt += m*x
    cnt += m*(p-1)
    if cnt >= m*(v-1) and A[n-p] <= A[x]+m:
        return True
    else:
        return False

l = -1
r = n-1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(n-r)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i] + M
    B = [x - a for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    cnt = (i + 1) * M + (P - 1) * M
    for b in B:
        cnt += max(0, b)
    return min(B) >= 0 and cnt >= V * M

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i] + M
    B = [x - a for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    cnt = i * M + (P - 1) * M
    for b in B:
        cnt += max(0, b)
    return min(B) >= 0 and cnt <= V * M

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i]
    B = [a - x for a in A[i + 1:-(P - 1)]]
    B.sort()
    if not B:
        return True
    K = N - V
    ims = [0] * (len(B) + K + 10)
    now = 0
    cnt = 0
    for i, b in enumerate(B):
        now += ims[i]
        if now < b:
            ims[i + K] -= b - now
            cnt += b - now
            now = b
    return cnt <= M

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i]
    B = [a - x for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    K = N - V
    ims = [0] * (len(B) + K + 10)
    now = 0
    cnt = 0
    for i, b in enumerate(B):
        now += ims[i]
        if now < b:
            ims[i + K] -= b - now
            cnt += b - now
            now = b
    return cnt <= M

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i] + M
    B = [x - a for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    K = max(0, V - i - (P - 1))
    return min(B) >= 0 and K * M <= sum(B)

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i] + M
    B = [x - a for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    K = V - i
    return min(B) >= 0 and sum(B) <= K * M

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i]
    B = [a - x for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    return max(B) <= M and sum(B) <= M * (N - V)

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

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

def isOk(i):
    x = A[i]
    B = [a - x for a in A[i + 1:-(P - 1)]]
    if not B:
        return True
    return max(-(-sum(B) // (N - V)), *B) <= M

ok = N
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(N - ok)

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    B = A[N - P]
    low, high = -1, N
    while high - low > 1:
        mid = (low + high) // 2
        if mid >= N - P: high = mid
        elif A[mid] + M < B: low = mid
        else:
            border = A[mid] + M
            room = 0
            for i in range(N - P):
                if i != mid: room += min(M, max(0, border - A[i]))
            if room >= max(0, V - P) * M: high = mid
            else: low = mid
            #print(mid, room)
    print(N - high)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from bisect import *
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
f = [0] * (N+1)
for i in range(N):
    f[i+1] = f[i] + A[i]
ans = 0
for i in range(N):
    r = bisect_right(A, A[i]+M)
    if P < N-r:
        continue
    if V <= i+1+N-r:
        ans += 1
        continue
    if V*M-(i+P)*M-(A[i]+M)*(N-P-i)+(f[N-P+1]-f[i+1]) < 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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]
mx = max(As)
cnt = 0
for a in As:
    if a + M >= mx:cnt+=1
print(P-1+cnt)

Submission status: Wrong Answer

Solution code:
def check_pickedup(N: int, 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]) - ((i-1)-(P-2))*A[i]
    #print('i: ', i)
    #print('th_score: ', th_score)
    #print('sum_surplus: ', sum_surplus)
    #print('th_score - A[i]: ', th_score - A[i])
    if th_score - A[i] <= M and sum_surplus <= M*(N-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 range(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(N, M, V, P, A, accum_score, i):
            ans += 1
            was_checked[a] = True
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


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


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (p - 1) * m + (n - x - 1) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p, x):
            tmp += t - a[i]
        return tmp >= m * (v - 1)
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


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


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (p - 1) * m + (n - x) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p, x):
            tmp += t - a[i]
        return tmp >= m * v
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


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


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (p - 1) * m + (n - x - 1) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p, x):
            tmp += t - a[i]
        return tmp >= m * v
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


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


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


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n

    def f(x):
        tmp = (p - 1) * m + (n - x) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p, x):
            tmp += t - a[i]
        return tmp > m * (v - 1)
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


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

Submission status: Wrong Answer

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

#solve
def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (p - 1) * m + (n - x + 1) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p, x):
            tmp += t - a[i]
        return tmp >= m * v
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


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