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)
 
def solve(n):
    if n < P:
        return True
    
    if A[n-1] > A[n] + M:
        return False
    
    cnt = M * (P - 1 + N - n)
    for i in range(P-1,n):
        cnt += A[n] + M - A[i]
    return cnt >= M * V
 
left = 0
right = N
 
while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid
 
print(right)

Submission status: Wrong Answer

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

A.sort(reverse = True)

def solve(n):
    if n < P:
        return True
    if A[n-1] > A[n] + M:
        return False
    
    cnt = M * (P - 1 + N - n)
    for i in range(P-1,n):
        cnt += max(0, A[n] + M - A[i])
    
    return cnt >= M * V

left = 0
right = N

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Wrong Answer

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

A.sort(reverse = True)

def solve(n):
    if n < P:
        return True
    if A[n-1] > A[n] + M:
        return False
    
    cnt = M * (P - 1 + N - n)
    for i in range(P-1,n):
        cnt += max(0, A[n] + M - A[i])
    
    print(n, cnt)
    return cnt >= M * V

left = 0
right = N

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Wrong Answer

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

A.sort(reverse = True)

def solve(n):
    if n < P:
        return True
    cnt = M * (P - 1 + N - n)
    for i in range(P-1,n):
        cnt += A[n] + M - A[i]
    return cnt >= M * V

left = 0
right = N

while left + 1 < right:
    mid = (left + right) // 2
    if solve(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BORDER = A[P - 1]

# にぶたん: x番目の問題が採用される可能性があるか？
ok, ng = 0, N
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    x_score = A[x] + M
    remain_vote = M * (V - 1)

    for i, a in enumerate(A):
        if i == x:
            continue
        elif i < P and A[i] > BORDER:
            remain_vote -= M
        else:
            remain_vote -= max(0, min(M, x_score - a))

    if remain_vote <= 0:
        ok = x
    else:
        ng = x

print(ok + 1)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BORDER = A[P - 1]

# にぶたん: x番目の問題が採用される可能性があるか？
ok, ng = 0, N
while abs(ok - ng) > 1:
    x = (ok + ng) // 2
    x_score = A[x] + M
    remain_vote = M * (V - 1)

    for i, a in enumerate(A):
        if i == x:
            continue
        elif i < P and A[i] > BORDER:
            remain_vote -= M
        else:
            remain_vote -= min(M, x_score - a)

    if remain_vote <= 0:
        ok = x
    else:
        ng = x

print(ok + 1)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)[::-1]
P-=1
def f(x):
  if x<=P:
    return True
  elif A[x]+M<A[P]:
    return False
  c=0
  for i in range(N):
    c+=min(M,A[x]+M-A[i])
  return c>=M*V

l,r=0,N
while l+1!=r:
  m=(l+r)//2
  if f(m):
    l=m
  else:
    r=m
print(l+1)

Submission status: Wrong Answer

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0

    cumsum = [0 for i in range(N)]
    cumsum[0] = A[0]
    for n in range(N-1):
        cumsum[n+1] = A[n+1] + cumsum[n]

    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * P
            if affords <= 0:
                result += 1
                continue
            
            #affords -= sum([A[n] + M - A[p] for p in range(P, n)])
            sunmmation = A[n] * (n-P) + M * (n-P) - (cumsum[n-1] - cumsum[P-1])
            affords -= sunmmation
            affords -= (N-n-1) * M

            if affords <= 0:
                result += 1
                continue
    print(result)
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * P
            if affords <= 0:
                result += 1
                continue
            
            affords -= sum([min(A[n] + M - A[p], M) for p in range(P, n)])
            affords -= (N-n-1) * M
            
            if affords <= 0:
                result += 1
                continue
    print(result)
    return


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

Submission status: Wrong Answer

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)
    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M
            affords -= M * (P-1)
            if affords <= 0:
                result += 1
                continue
            break_flag = False
            for p in range(P, N):
                if p == n:
                    continue
                else:
                    affords -= A[n] + M - A[p]
                    if affords<=0:
                        result += 1
                        break
    print(result)
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m, v, p = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    t = a[n-p]
    b = [None]*n
    b[n-1] = 0
    ans = 0
    for i in reversed(range(n-1)):
        b[i] = b[i+1] + max(0, t - a[i+1])
    dic = {}
    cnt = {}
    for i in range(n):
        if a[i] in cnt:
            cnt[a[i]] += 1
        else:
            cnt[a[i]] = 1
        if not a[i] in dic:
            dic[a[i]] =  b[i]
    st = set()
    for i in range(n):
        if a[i] in st:
            continue
        if t <= a[i]:
            ans += cnt[a[i]]
        else:
            if a[i]+m >= t:
                if p-1 + i + dic[a[i]] >= v:
                    ans += cnt[a[i]]
        st.add(a[i])
    print(ans)

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(reverse=True)

higher = a[p-1]
for i in range(p,n):
    if(a[i] == a[i-1]):
        higher += a[i]
        continue

    if(a[p-1]- a[i] > v):
        print(i)
        exit()

    if(higher - a[i]*(i-p+1) > min(n-v,i-p+1)*m):
        print(i)
        exit()

    higher += a[i]

print(n)

Submission status: Wrong Answer

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

a.sort(reverse=True)

higher = a[p-1]
for i in range(p,n):
    if(a[i] == a[i-1]):
        higher += a[i]
        continue

    if(a[p-1]- a[i] > v):
        print(i)
        exit()

    if(higher - a[i]*(i-p+1) > min(n-v,p-1)*m):
        print(i)
        exit()

    higher += a[i]

print(n)

Submission status: Wrong Answer

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

a.sort(reverse=True)

higher = a[p-1]
for i in range(p,n):
    if(a[i] == a[p-1]):
        higher += a[i]
        continue

    if(a[p-1]- a[i] > v):
        print(i)
        exit()

    if(higher - a[i]*(i-p+1) > min(n-v,p-1)*m):
        print(i)
        exit()

    higher += a[i]

print(n)

Submission status: Wrong Answer

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


if P == 1:
    print(len([a for a in A if A[-1] - a <= M]))
else:
    B = A[: -P + 1]  # 上からP個目とそれから下
    # にぶたん: M * V の残り投票数を１つにつき最大RまでBに割り振って、Bの最大値をok以下にできるか？
    ng, ok = -1, 10 ** 9 + 1
    while abs(ok - ng) > 1:
        mr = M * V
        x = (ok + ng) // 2

        for b in B:
            mr -= min(M, max(0, x - b))
        mr -= (P - 1) * M  # 上位陣は確定なので全部降ってよい

        for b in B:
            if b > x:
                ng = x
                break
        else:
            if mr <= 0:
                ok = x
            else:
                ng = x

    print(len([a for a in A if a + M >= ok]))

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())))
B = A[:-P + 1]  # 上からP個目とそれから下
R = (V - P + 1)  # あといくつ投票する必要があるか


# にぶたん: M * R の残り投票数を１つにつき最大RまでBに割り振って、Bの最大値をok以下にできるか？
ng, ok = -1, 10 ** 9 + 1
while abs(ok - ng) > 1:
    mr = M * R
    x = (ok + ng) // 2

    for b in B:
        mr -= min(M, max(0, x - b))

    for b in B:
        if b > x:
            ng = x
            break
    else:
        if mr <= 0:
            ok = x
        else:
            ng = x

print(len([a for a in A if a + M >= ok]))

Submission status: Wrong Answer

Solution code:
# 上からx問目を選ぶことができるか二分探索
# x <= Pであれば必ず選べる
# A_x + M < A_Pであれば必ず選べない
# それ以外の場合
# A_xには必ず投票するのでA_x + Mが基準点
# A_xがP位である必要がある
# 上位P - 1位までにはM票投票して良い
# P + 1位以下に対しては、A_x + Mまでは投票して良い
# この投票して良い数がM * Vを上回ればOK

import sys
readline = sys.stdin.readline

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

# 最初の時点で上位P位の点数を求めておく
border = A[P - 1]

# 大きい順に並べる

ok = -1
ng = N

def isOk(x):
  # 上からx番目を選ぶことが出来るか
  if x <= P:
    return True
  if A[x] + M < border:
    return False
  # 基準点
  base = A[x] + M
  
  # 上位P - 1には必ず投票して良い
  vote = (P - 1) * M
  
  # P位以下には、baseを超えないように投票して良い
  for i in range(P - 1,len(A)):
    can = max(base - A[i],0)
    can = min(can, M)
    vote += can
  if vote >= M * V:
    return True
  return False

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

Submission status: Wrong Answer

Solution code:
# 上からx問目を選ぶことができるか二分探索
# x <= Pであれば必ず選べる
# A_x + M < A_Pであれば必ず選べない
# それ以外の場合
# A_xには必ず投票するのでA_x + Mが基準点
# A_xがP位である必要がある
# 上位P - 1位までにはM票投票して良い
# P + 1位以下に対しては、A_x + Mまでは投票して良い
# この投票して良い数がM * Vを上回ればOK

import sys
readline = sys.stdin.readline

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

# 最初の時点で上位P位の点数を求めておく
border = A[P - 1]

# 大きい順に並べる

ok = -1
ng = N

def isOk(x):
  # 上からx番目を選ぶことが出来るか
  if x <= P:
    return True
  if A[x] + M < border:
    return False
  # 基準点
  base = A[x] + M
  
  # 上位P - 1には必ず投票して良い
  vote = (P - 1) * M
  
  # P位以下には、baseを超えないように投票して良い
  for i in range(P,len(A)):
    can = max(base - A[i],0)
    can = min(can, M)
    vote += can
  if vote >= M * V:
    return True
  return False

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

Submission status: Wrong Answer

Solution code:
import numpy as np
# import bisect

N, M, V, P = [int(_c) for _c in input().split(" ")]
A_list = [int(_c) for _c in input().split(" ")]

A_list = sorted(A_list)

ssl = []
ss = 0
over_border_ssl = []
over_border_ss = 0
for _a in A_list:
    ss += _a
    ssl.append(ss)
    if A_list[-(P - 1)] - _a > M:
        over_border_ss += A_list[-(P - 1)] - _a - M
    over_border_ssl.append(over_border_ss)

use_sum = ssl[-P] + over_border_ssl[-P]
good = 0
for i, a in enumerate(A_list):
    if N - i <= P:
        good += 1
        continue
    if a + M < A_list[-(P)]:
        continue
    if M * V - P * M <= (N - P) * (M + a) - (use_sum - a):
        good += 1

print(good)

Submission status: Wrong Answer

Solution code:
import numpy as np
# import bisect

N, M, V, P = [int(_c) for _c in input().split(" ")]
A_list = [int(_c) for _c in input().split(" ")]

A_list = sorted(A_list)
s = np.cumsum(A_list)
use_sum = s[-P]
# _idx = bisect.bisect_left(A_list, A_list[-(P-1)])
good = 0
for i, a in enumerate(A_list):
    if N - i <= P:
        good += 1
        continue
    if a + M < A_list[-(P)]:
        continue
    if M * V - P * M < (N - P) * (M + a) - (use_sum - a):
        good += 1

print(good)

Submission status: Wrong Answer

Solution code:
import numpy as np
import bisect

N, M, V, P = [int(_c) for _c in input().split(" ")]
A_list = [int(_c) for _c in input().split(" ")]

A_list = sorted(A_list)
s = np.cumsum(A_list)
_idx = bisect.bisect_left(A_list, A_list[-(P-1)])
good = 0
for i, a in enumerate(A_list):
    if N - i <= P:
        good += 1
        continue
    if a + M < A_list[-(P)]:
        continue
    if M * V - P * M < (N - P) * (M + a) - (s[_idx - 1] - a):
        good += 1

print(good)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

n, m, v, p = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
ans = 0
rv = n - v
rp = n - p
for i in range(n):
    l = rp - i
    if (cs[rp + 1] - cs[i + 1]) + (l - rv) * m <= (a[i] + m) * l:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

n, m, v, p = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
ans = p
rv = n - v
rp = n - p
for i in range(rp):
    l = rp - i
    if l >= rv and (cs[rp + 1] - cs[i + 1]) + (l - rv) * m <= (a[i] + m) * l:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

n, m, v, p = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
ans = p
rv = n - v
rp = n - p
for i in range(rp):
    l = rp - i
    if (cs[rp + 1] - cs[i + 1]) + max(0, l - rv) * m <= (a[i] + m) * l:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

n, m, v, p = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
ans = p
rv = n - v
rp = n - p
for i in range(rp):
    l = rp - i
    if (cs[rp + 1] - cs[i + 1]) + (l - rv) * m <= (a[i] + m) * l:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
# 累積和
def cumsum(l):
    """a[i] = sum(l[:i]) なるaを返す
    """
    c = 0
    a = [None] * (len(l)+1)
    for i,num in enumerate(l):
        a[i] = c
        c += num
    a[-1] = c
    return a

s = cumsum(a)

def sub(i):
    # a[i]がいけるかどうか
    if i>=n-p:
        return True
    v1 = a[i] + m
    ss = m * (i+p)
    tmps = (s[n-p+1] - s[i+1])
    ss += v1*(n-i-p) - tmps    
    r = ss >= m*v
    return r
l = 0
r = n-1
if sub(l):
    print(n)
else:
    while l<r-1:
        mm = (r+l)//2
        if sub(mm):
            r = mm
        else:
            l = mm
    print(n-1-l)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
# 累積和
def cumsum(l):
    """a[i] = sum(l[:i]) なるaを返す
    """
    c = 0
    a = [None] * (len(l)+1)
    for i,num in enumerate(l):
        a[i] = c
        c += num
    a[-1] = c
    return a

s = cumsum(a)

def sub(i):
    # a[i]がいけるかどうか
    if i>=n-p:
        return True
    v1 = a[i] + m
    nokori = m * (v-p-(i))
    tmps = (s[n-p+1] - s[i+1])
    r = tmps + nokori <= v1*(n-p-i)
#     print(i, tmps, nokori, tmps, r)
    return r
l = 0
r = n-1
if sub(l):
    print(n)
else:
    while l<r-1:
        mm = (r+l)//2
        if sub(mm):
            r = mm
        else:
            l = mm
    print(n-1-l)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
s = sum(a[:(n-p+1)])
def sub(i):
    # a[i]がいけるかどうか
    if i>=n-p:
        return True
    v1 = a[i] + m
    nokori = m * (v-(p-1))
    return s - a[i] + nokori <= v1*(n-p)
l = 0
r = n-1
if sub(l):
    print(n)
else:
    while l<r-1:
        mm = (r+l)//2
        if sub(mm):
            r = mm
        else:
            l = mm
    print(n-1-l)

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M,V,P = LI()
    A = LI()
    A.sort()

    ans = 0
    ac = sum(A[:N-P+1])
    for i in range(N):
        if i > 0:
            ac = ac - A[i-1] + A[i]
        if i >= N-P:
            ans += 1
        else:
            if M+A[i] < A[N-P]: continue
            if V <= P:
                ans += 1
            else:
                w = ((N-P) * (M+A[i])) - (ac - A[i])
                if w >= M * (V-P):
                    ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M,V,P = LI()
    A = LI()
    A.sort()

    ans = 0
    ac = sum(A[:N-P+1])
    for i in range(N):
        if i > 0:
            ac = ac - A[i-1] + A[i]
        if i >= N-P:
            ans += 1
        else:
            if M+A[i] < A[N-P]: continue
            w = ((N-P) * (M+A[i])) - (ac - A[i])
            if w >= M * (V-P):
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N,M,V,P = LI()
    A = LI()
    A.sort()

    ans = 0
    ac = sum(A[:N-P+1])
    for i in range(N):
        if i > 0:
            ac = ac - A[i-1] + A[i]
        if i >= N-P:
            ans += 1
        else:
            w = ((N-P) * (M+A[i])) - (ac - A[i])
            if w >= M * (V-P):
                ans += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
Asorted = sorted(A)
 
start=-1
end = N-P+2
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  if Ai + M < Ap:
    start = i+1
    continue
  limit = (Ai + M)*(N-P-i) - sum(Asorted[i+1:N-P+1]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(N-start)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
Asorted = sorted(A)
 
start=0
end = N-P+1
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end)//2
  Ai = Asorted[i]
  if Ai + M < Ap:
    start = i+1
    continue
  limit = (Ai + M)*(N-P-i) - sum(Asorted[i+1:N-P+1]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(N-start)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
Asorted = sorted(A)
 
start=0
end = N-P+1
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  if Ai + M < Ap:
    start = i+1
    continue
  limit = (Ai + M)*(N-P-i) - sum(Asorted[i+1:N-P+1]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(N-start)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
total = [0]*N
total[0] = S[0]

for i in range(1, N):
    total[i] = total[i-1]+S[i]

if total[N-P]-total[0]+(V-P)*M <= (S[0]+M)*(N-P):
    ans = N
else:
    ok = N-1
    ng = 0
    while ng+1 < ok:
        mid = (ok+ng)//2
        if mid > N-P:
            ok = mid
        elif total[N-P]-total[mid]+(V-(P+mid))*M <= (S[mid]+M)*(N-P-mid) and S[mid]+M >= S[N-P]:
            ok = mid
        else:
            ng = mid
    ans = N-ok
print(ans)


# わからん

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
total = [0]*N
total[0] = S[0]

for i in range(1, N):
    total[i] = total[i-1]+S[i]

if total[N-P]-total[0]+(V-P)*M <= (S[0]+M)*(N-P):
    ans = N
else:
    ok = N-1
    ng = 0
    while ng+1 < ok:
        mid = (ok+ng)//2
        if mid > N-P:
            ok = mid
        elif total[N-P]-total[mid]+(V-(P+mid))*M <= (S[mid]+M)*(N-P-mid):
            ok = mid
        else:
            ng = mid
    ans = N-ok
print(ans)


# わからん

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
total = [0]*N
total[0] = S[0]

for i in range(1, N):
    total[i] = total[i-1]+S[i]
if total[N-P]-total[0]+(V-P)*M <= (S[0]+M)*(N-P):
    ans = N
else:
    ok = N-1
    ng = 0
    while ng+1 < ok:
        mid = (ok+ng)//2
        if mid > N-P:
            ok = mid
        elif total[N-P]-total[mid]+(V-(P+mid))*M <= (S[mid]+M)*(N-(P+mid)):
            ok = mid
        else:
            ng = mid
    ans = N-ok
print(ans)


# わからん

Submission status: Wrong Answer

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

start=-1
end = N-P
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  if Ai + M < Ap:
    start = i+1
    continue
  limit = (Ai + M)*(N-P-i-1) - sum(Asorted[i+1:N-P]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(N-start)

Submission status: Wrong Answer

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

start=0
end = N-P
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  if Ai + M < Ap:
    start = i+1
    continue
  limit = (Ai + M)*(N-P-i-1) - sum(Asorted[i+1:N-P]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(N-start)

Submission status: Wrong Answer

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

n = len(Asorted)
start=0
end = n-P
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  if Ai + M < Ap:
    start = i+1
    continue
  limit = (Ai + M)*(n-P-i-1) - sum(Asorted[i+1:n-P]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(n-start)

Submission status: Wrong Answer

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

n = len(Asorted)-P
start=0
end = n
Ap = A[-P]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  limit = (Ai + M)*(n-i-1) - sum(Asorted[i+1:n]) + (i+P)*M
  if Ai + M >= Ap and limit >= total:
    end = i+1
  else:
    start = i+1
print(n+P-start)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

n = len(Asorted)-P
start=0
end = n
Ap = A[-P]
total = V*M
while start < end -1:
  print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  limit = (Ai + M)*(n-i-1) - sum(Asorted[i+1:n]) + (i+P)*M
  if Ai + M >= Ap and limit >= total:
    end = i+1
  else:
    start = i+1
print(np.sum(np.asarray(A)>=Asorted[start]))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
if P == 1:
  Asorted = sorted(A)
else:
  Asorted = sorted(A)[:-(P-1)]

n = len(Asorted)
start=0
end = n
Ap = A[-1]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  limit = (Ai + M)*(n-i-1) - sum(Asorted[i+1:]) + (i+P)*M
  if Ai + M >= Ap and limit >= total:
    end = i+1
  else:
    start = i+1
print(np.sum(np.asarray(A)>=Asorted[start]))

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
if P == 1:
  Asorted = sorted(A)
else:
  Asorted = sorted(A)[:-(P-1)]

n = len(Asorted)
start=0
end = n
Ap = A[-1]
total = V*M
while start < end -1:
  #print(start, end)
  i = (start+end-1)//2
  Ai = Asorted[i]
  if i == n-1:
    start = n-1
    break
  limit = (Ai + M)*(n-i-1) - sum(Asorted[i+1:]) + (i+P)*M
  if limit >= total:
    end = i+1
  else:
    start = i+1
print(np.sum(np.asarray(A)>=Asorted[start]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M, V, P = mi()
A = sorted(li())

#if M >= P:
a_new = [A[i]+M for i in range(V)]
#print(a_new)
B = sorted(A[-P:] + a_new)
len_b = len(B)
#print(B)
for i, num in enumerate(a_new):
    ind = bisect.bisect_right(B, num)
    #print(ind)
    if len_b - ind + 1 <= P:
        print(N-i)
        exit()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

N, M, V, P = mi()
A = sorted(li())

#if M >= P:
a_new = [A[i]+M for i in range(V)]
print(a_new)
B = sorted(A[-P:] + a_new)
len_b = len(B)
print(B)
for i, num in enumerate(a_new):
    ind = bisect.bisect_right(B, num)
    print(ind)
    if len_b - ind + 1 <= P:
        print(N-i)
        exit()