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:
import bisect
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)
if (v<=p):
    limit = a[n-p]
    if (a[n-p] <= m):
        print(n)
    else:
        x = bisect.bisect_left(a,a[n-p]-m)
        print(n-x)
else:
    limit = a[n-p]
    #print(1,limit)
    wa = [0]*n
    wa[0] = a[0]
    for i in range(1,n):
        wa[i] = wa[i-1] + a[i]
    #print(limit,wa)
    ans = 0
    for i in range(n-p-1,-1,-1):
        sa = limit - a[i]
        if (sa==0):
            ans += 1
            continue
        elif (sa > m):
            continue
        if (i>=v):
            ans += 1
            
        else:
            nokori = (v-i-1-(p-1))*m
            #x = bisect.bisect_left(a,a[i]+m)
            #print(i,nokori)
            if (nokori <= (a[i]+m)*(n-p-1-i) - (wa[n-p-1]-wa[i])):
                ans += 1
                #print(i)
              
    print(ans + p)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m,v,p = map(int,readline().split())
a = [int(i) for i in readline().split()]
a.sort(reverse=True)
ans = p
v -= (p-1)
g = a[p-1]
L = 1
use = m-g

if v > 0:
  for i in range(p,n):
    mar = g-a[i]
    V = v-(n-1-i)
    if mar > m:
      break
    if V <= 1:
      if mar <= m:
        ans += 1
        L += 1
        use += m-a[i]
      else:
        break
    else:
      if use+a[i]*L >= (V-1)*m:
        ans += 1
        L += 1
        use += m-a[i]
      else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m,v,p = map(int,readline().split())
a = [int(i) for i in readline().split()]
a.sort(reverse=True)
ans = p
v -= (p-1)
g = a[p-1]
L = 1
use = m-g

if v > 0:
  for i in range(p,n):
    mar = g-a[i]
    V = v-(n-1-i)
    if V <= 1:
      if mar <= m:
        ans += 1
        L += 1
        use += m-a[i]
      else:
        break
    else:
      if use+a[i]*L >= (V-1)*m:
        ans += 1
        L += 1
        use += m-a[i]
      else:
        break
        
else:
  for i in range(p,n):
    if a[i] + m >= g:
      ans += 1
    else:
      break
      
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m,v,p = map(int,readline().split())
a = [int(i) for i in readline().split()]
a.sort(reverse=True)
ans = p
v -= (p-1)
g = a[p-1]
L = 1
use = m-g

for i in range(p,n):
  mar = g-a[i]
  V = v-(n-1-i)
  if V <= 1:
    if mar <= m:
      ans += 1
      L += 1
      use += m-a[i]
    else:
      break
  else:
    if use+a[i]*L >= (V-1)*m:
      ans += 1
      L += 1
      use += m-a[i]
    else:
      break
      
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)

ok = p - 1
ng = n

while ng - ok > 1:
  mid = (ok + ng) // 2
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  if not (p - 1 <= mid <= n - 1):
    for i in range(p - 1, n):
      used += min(m, max(0, A[mid] + m - A[i]))

  if used >= m * v:
    ok = mid
  else:
    ng = mid

print(ok + 1)

Submission status: Wrong Answer

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

ok = p - 1
ng = n

while ok - ng > 1:
  mid = (ok + ng) // 2
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i == mid:
      continue

    used += min(m, max(0, A[mid] + m - A[i]))

  if used >= m * v:
    ok = mid
  else:
    ng = mid

print(ok + 1)

Submission status: Wrong Answer

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

ls.sort()
total=m*v
for i in range(min(v-1,p-1)):
    ls[-i-1]+=m
    total-=m

ac = [0]*n
for i in range(n-1):
    ac[i+1] = ac[i]+(ls[i+1]-ls[i])*(i+1)

ans=p
for i in range(n-p):
    idx=bisect.bisect_right(ls,ls[i]+m)
    if n-idx>=p:
        continue
    totalnow=total-m*(i+1)
    if totalnow <= 0:
        ans += 1
        continue
    if ac[-p]-ac[i]-(ls[-p]-ls[i])*(i+1)+(ls[i]+m-ls[-p])*(n-p-i-1)< totalnow:
        continue
    ans += 1

print(ans)

Submission status: Wrong Answer

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

ls.sort()
total=m*v
for i in range(p-1):
    ls[-i-1]+=m
    total-=m

ac = [0]*n
for i in range(n-1):
    ac[i+1] = ac[i]+(ls[i+1]-ls[i])*(i+1)

ans=p
for i in range(n-p):
    idx=bisect.bisect_right(ls,ls[i]+m)
    if n-idx>=p:
        continue
    totalnow=total-m*(i+1)
    if ac[-p]-ac[i]-(ls[-p]-ls[i])*(i+1)+(ls[i]+m-ls[-p])*(n-p-i-1)< totalnow:
        continue
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
eps = 0.1
def func(k):
    # print("tsrget:"+str(k))
    used = 0
    tmp = a[:k]+a[k+1:]
    val = a[k]+M
    x1 = N-1-bisect.bisect(tmp, val+eps)
    x2 = bisect.bisect(tmp, val-eps)
    x3 = N-(x1+x2+1)
    # print(tmp,val,x1,x2,x3)
    if x1 >= P:
        return False
    v = V - (x1+1)
    p = P - (x1+1)
    used += x1+1
    if v <= 0:
        return True
    # x2+x3問からあとp問はa[k]+Mを超えてもよい
    # x3が十分ある
    if x3 >= p and p > 0:
        x3 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x3
        v -= x3
        used += x3
        x3 = 0
    if p>0:
        p -= x2
        v -= x2
        used += x2
    if v <= 0:
        return True
    # x2問からあとp問はa[k]+Mを超えてもよい
    tmp2 = tmp[:N-used]
    rest = sum([min(M,val-val2) for val2 in tmp2])
    # print(tmp2,N,x1,x3,p,v, rest)
    if rest >= M*v:
        return True
    return False

ok = N-1  # exist
ng = -1  # not exist
while abs(ok - ng) > 1:
    cnt = (ok + ng) // 2
    t = func(cnt)
    # print(t)
    if t:
        ok = cnt
    else:
        ng = cnt
print(N-ok)

Submission status: Wrong Answer

Solution code:
import bisect
def main():

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

    if P == 1:
        ans = 0
        for i in range(N):
            if A[i] + M >= A[N-1]:
                ans += 1
        return ans

    prefix = [0]
    for i in range(N):
        prefix.append(prefix[-1] + A[i])

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

    return ans

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():

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

    if P == 1:
        ans = 0
        for i in range(N):
            if A[i] + M >= A[0]:
                ans += 1
        return ans


    prefix = [0]
    for i in range(N):
        prefix.append(prefix[-1] + A[i])

    ans = P
    for i in range(P, N):
        v = P * M + (N-1-i-1+1) * M
        v += (A[i] + M) * (i-(P-1))
        v -= prefix[i-1] - prefix[P-2]
        if v >= M * V:
            ans += 1
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():

    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):
        v = P * M + (N-1-i-1+1) * M
        for j in range(P, i):
            v += min(A[i] + M - A[j], M)
        if v >= M * V:
            ans += 1
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():

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

    ans = 0
    for i in range(N):
        v = P * M + (N-1-i-1+1) * M
        for j in range(P, i):
            v += min(A[i] + M - A[j], M)
        if v >= M * V:
            ans += 1
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

Solution code:
def main():

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

    ans = 0
    for i in range(N):
        v = P * M + (N-1-i-1+1) * M
        for j in range(P, i):
            v += A[i] + M - A[j]
        if v >= M * V:
            ans += 1
    return ans
    
if __name__ == '__main__':
    print(main())

Submission status: Wrong Answer

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

s = 0

b = sorted(a)
b.reverse() 

behind = 0
flag = False

for i in range(p, n):
    behind = behind + (b[i-1] - b[i]) * (i-p+1)

    if n*m - behind < m * v:
        s = i
        flag = True
        break

ans = 0

if flag == False:
    ans = n
else:
    ans = i

print(ans)

Submission status: Wrong Answer

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

s = 0

b = sorted(a)
b.reverse()

idx = 0
for i in range(n):
    if b[i] < b[p-1] - m:
        idx = i
        break


ok = n*m 

behind = 0

for i in range(p, n):
    behind = behind + (b[i-1] - b[i]) * (i-p+1)

    if n*m - behind < m * v:
        s = i
        break


print(i)

Submission status: Wrong Answer

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

b = sorted(a)
b.reverse()

s = p

f = 0
behind = 0

for i in range(p, n):
    f += 1
    behind = behind + (b[i-1] - b[i]) * f
    if (behind + (f-(n-v)) * m)/f  <= m:
        s += 1

print(s)

Submission status: Wrong Answer

Solution code:
def check(n):
    """
    if n <= P-1:
        return True
    """

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N
left = P


##
"""
if check(right):
    print(N)
    exit()
"""
while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Wrong Answer

Solution code:
def check(n):
    """
    if n <= P-1:
        return True
    """

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N
left = P


##
"""
if check(right):
    print(N)
    exit()
"""
while abs(right-left) > 1:

    mid = (right+left)//2
    print(mid)

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Wrong Answer

Solution code:
def check(n):
    """
    if n <= P-1:
        return True
    """

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = P

"""
if check(right):
    print(N)
    exit()
"""

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Wrong Answer

Solution code:
def check(n):

    if n <= P-1:
        return True
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])
    
    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Wrong Answer

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

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=min(m,a[x]+m-a[i])
    if tmp>=m*v:
        return True
    return False

left=-1
right=n*2
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Submission status: Wrong Answer

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

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=a[x]+m-a[i]
    if tmp>=m*v:
        return True
    return False

left=-1
right=n*2
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Submission status: Wrong Answer

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

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=a[x]+m-a[i]
    if tmp>=m*v:
        return True
    return False

left=0
right=n*2
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Submission status: Wrong Answer

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

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=a[x]+m-a[i]
    if tmp>=m*v:
        return True
    return False

left=0
right=n-1
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
broke = False
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            broke = True
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[bs+i]-cs[bs-1])
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    broke = True
                    break
    if broke == False:
        print(N)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
broke = False
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            broke = True
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[bs+i]-cs[bs-1])
                print(points_overflowed)
                print(points_limit)
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    broke = True
                    break
    if broke == False:
        print(N)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[bs+i]-cs[bs-1])
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    break

Submission status: Wrong Answer

Solution code:
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[bs+i]-P+1)
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    break

Submission status: Wrong Answer

Solution code:
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[-bs-1]-cs[-bs-2-i])
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    break

Submission status: Wrong Answer

Solution code:
# V <= N // 2のとき：
# 3 2 2 1 1 0
# P位(2位)までにいるのは2
# 初期状態2以上は合格
# ボーダーのグループ[1 1 0]のうち何人を救えるか
# 2まで上げることは必須である
# 投票者M = 1 V = 1のとき
# 2まで上げられる[1 1 0]が合格
# 投票者M = 2のときも
# 2まで上げられるのは[2 2 0]
# 投票者M = 3 V = 1のとき[2 2 1]でNG
# 投票者M = 2 V = 2のとき[1 1 0] -> [2 1 1] -> [2 2 2]でOK
# これは、M * V点上げられる・ただし一人あたりM点までと同値
# 例：
# ボーダーが5で[4 3 2 1]、M = 3 V = 2のとき
# [4 4 3 1]->[5 4 4 1]->[5 5 5 1]でOK
# ボーダーが5で[4 3 2 1]、M = 2 V = 3のとき
# [5 4 3 1]->[5 5 4 2]なので。
# 従い、ボーダー上にいる人を
# 前から順に見ていき、ボーダーとの差がM人の場合の差分を集計していき、
# 差分がV * Mに満ちるまでに救えた点数までが合格点

# V > N // 2のとき：
# (N - V)人の点数を下げると考える
# V = N - V
# 3 2 2 1 1 0
# P位までにいるのは2点以上
# ボーダーの一つ下(1)を基準にする
# [3 2 2]のグループを操作して2位を変えられるか
# M = 1 (N - V) = 1のとき
# [3 2 1][3 1 2]
# 今回は2点のグループを全て1にできないとダメ
# [5 4 3 2 1]
# 3までが合格点の場合
# [3 2 1]
# M = 1, V = 1のとき
# [2 2 1]とし、新たなボーダーを2にする
# [5 [4 3 2 1]]で4がボーダーのとき
# M = 3,V = 2のとき
# [5 [3 2 2 1]]->[5 [2 2 1 1]]->[5 [1 1 1 1]]で全て合格ライン
# M = 2,V = 3のとき
# [5 [3 2 2 1]]->[5 [2 2 2 0]]で4つ合格ライン
# 従いボーダー - Mを新しいボーダーとしたときに、
# 前から最大M減らしていき、全体ではV * M減らせる
# M = 3,V = 2のとき
# 新しいボーダーは1
# [5 [4 3 2 1]]->[5 [1 3 2 1]]->[5 [1 1 2 1]]->[5 [1 1 1 1]]
# M = 2,V = 3のとき
# 新しいボーダーは2
# [5 [4 3 2 1]]->[5 [2 3 2 1]]->[5 [2 2 2 1]]これで2まで救える

N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())), reverse = True)

if V <= N//2:
  # ボーダーとなる得点を求める
  border = A[P-1]
  print("border",border)
  # ボーダー以下となるグループを求める
  ind = -1
  for i in range(P-1,N):
    if A[i] < border:
      ind = i
      break
  if ind == -1: # ボーダー以下となる人がいないのであれば全員可能性あり
    print(N)
    exit(0)
  B = A[ind:] # ボーダー以下となるグループ
#  print(B)
  allvote = V * M
  newborder = border
  for i in range(len(B)): 
    if (border - B[i]) > M:
#      print("border - B[i]",border - B[i])
      # ボーダーとの差がM超の人は絶対救えない
      break
#    print("border - B[i]",border - B[i],"allvote",allvote)
    if border - B[i] >= M and border - B[i] <= allvote: # i番目の人に投票可能か
#      print(B[i],"にvote")
      vote = border - B[i]
      allvote -= vote
      newborder = B[i]
    else:
      # 投票不可ならそこでループを抜ける
#      print("not vote")
      break
  ans = N - len(B)
  for i in range(len(B)):
    if B[i] >= newborder:
      ans += 1
  print(ans)

else:
  # 逆投票の場合
#  print("逆投票")
  V = N - V # 逆投票できる人数
  border = A[P-1] # 合格ボーダー
#  print("border",border)
  ok_ind = -1
  for i in range(len(A)):
    if A[i] == border:
      ok_ind = i
      break
  if ok_ind == -1: # 起こりえないけど
    print(N)
    exit(0)
  
  B = A[ok_ind:]
  Bsum = [[B[0],1]]
  for i in range(1,len(B)):
    if B[i] == Bsum[-1][0]:
      Bsum[-1][1] += 1
    else:
      Bsum += [[B[i],1]]
#  print(Bsum)
  allvote = V * M
  
  # 何点までボーダーを落とせるか二分探索
  ok = Bsum[0][0] - 0
  ng = Bsum[0][0] - (M + 1)
  while abs(ng - ok)>1:
    x = abs(ng + ok)//2
    # x点落とせるかを検証
#    print("x",x,"点まで落とせるか")
    can = True
    alls = allvote
    for i in range(len(Bsum)):
      if Bsum[i][0] <= x:
        break
      else:
        need = (Bsum[i][0] - x) * Bsum[i][1]
#        print(Bsum[i][0],"を",x,"まで落とすには",need,"必要")
        alls -= need
#        print("残り",alls)
        if alls < 0:
#          print("0未満なのでダメ")
          can = False
          break
    if can:
      ok = x
#      print("ok:",ok,"を代入:ng",ng)
    else:
      ng = x
#      print("ng:",ng,"を代入:ok",ok)
  # ok点まで落とすことが出来る
  newborder = ok
#  print("ok",ok,"newborder",newborder)
  ans = N - len(B)
#  print("確定",ans)
  for i in range(len(B)):
    if B[i] >= newborder:
      ans += 1
  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)
sa = [0 for _ in range(n+1)]
for i in range(n):
    sa[i+1] = sa[i] + a[i]

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

    else:
        res = sa[i] - sa[p-1]
        if (a[i] + m) * (i - p + 1) - res >= x * m:
            ans += 1


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)
sa = [0 for _ in range(n+1)]
for i in range(n):
    sa[i+1] = sa[i] + a[i]
#print(sa)

ans = 0
for i in range(n):
    x = (v - 1) - (p - 1) - (n - 1 - i)
    #print(i, x)
    if x <= 0:
        if a[p-1] <= a[i] + m:
            ans += 1
            #print('True', i)
    else:
        res = sa[i] - sa[p-1]
        #print(i, res)
        if res + x * m <= (a[i] + m) * (i - p + 1):
            ans += 1
            #print('True', i)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, V, P = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    A.sort()
    
    def check(t):
        cnt = (t + 1) * M
        for idx in range(t + 1, N - P + 1):
            cnt += M - (A[idx] - A[t])
        cnt += (P - 1) * M
        return M * V <= cnt
    
    ok, ng = N - 1, -1
    while 1 < ok - ng:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(N - ok)


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する
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid - 1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += A[mid]+M-v

        if voted <=M*V:
            right = mid-1
        else:
            left= mid+1

print(left)

Submission status: Wrong Answer

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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid - 1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += min(max(A[mid]+M-v,0),M)

        if voted <=M*V:
            right = mid-1
        else:
            left= mid+1

print(left)

Submission status: Wrong Answer

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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        #right = mid - 1
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        #left = mid + 1
        right = mid - 1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += min(max(A[mid]+M-v,0),M)

        if voted <=M*V:
            right = mid-1
        else:
            left= mid+1

print(mid)

Submission status: Wrong Answer

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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid - 1
    else:
        voted = P * M
        voted += (N-mid-1)*M

        for v in A[P-1:mid]:
            voted += min(max(A[mid]+M-v,0),M)

        if voted <=M*V:
            right = mid-1
        else:
            left= mid+1

print(left)

Submission status: Wrong Answer

Solution code:
import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
cnt=p
from bisect import bisect_left
for i in range(p,n):
    if a[i]+m<a[p-1]:
        continue
    
    cnt+=((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)<=v*m  
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
cnt=p
from bisect import bisect_left
for i in range(p,n):
    if a[i]+m<a[p-1]:
        continue
    
    cnt+=(a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m<=v*m  
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
cnt=p
from bisect import bisect_left
for i in range(p,n):
    if a[i]+m<a[p-1]:
        continue
    
    cnt+=(a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-i-p-1)*m<=v*m  
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
cnt=p
#from bisect import bisect_left
for i in range(p,n):
    if a[i]+m<a[p-1]:
        continue
    
    cnt+=(a[i]+m)*(i-p)-sum(a[p:i])+(n-i-p-1)*m<=v*m  
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
cnt=0
from bisect import bisect_left
for i in range(p,n):
    if a[i]+m<a[p-1]:
        continue
    
    cnt+=(a[i]+m)*(i-p)-sum(a[p:i])+(n-i-p-1)*m<=v*m  
print(cnt)

Submission status: Wrong Answer

Solution code:
#2分探索は点数でなく順位
n,m,v,p = map(int, input().split( ))
a = list(map(int, input().split( )))###
a.sort(reverse = True)
mx = n-1##
mn = p-2##

while mx-mn>1:
    md = (mx+mn)//2
    sc = (p-1)*m+(n-md-1)*m
    for i in range(md):
        sc += max(a[md]+m-a[i],0)
    if sc>=v*m:
        mn = md
    else:
        mx = md
print(mx+1)##

Submission status: Wrong Answer

Solution code:
#2分探索は点数でなく順位
n,m,v,p = map(int, input().split( ))
a = list(map(int, input().split( )))###
a.sort(reverse = True)
mx = n-1##
mn = p-2##

while mx-mn>1:
    md = (mx+mn)//2
    sc = (p-1)*m+(n-md-1)*m
    for i in range(md):
        sc += max(a[md]+m-a[i],0)
    if sc>=v*m:
        mn = md
    else:
        mx = md
print(mn+1)