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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
a = a[p-1:]
l = list(accumulate(a))
ans = p-1

for i in range(n-p+1):
    s = (n-p-(i+1))*m + p*m
    s += (a[i] + m) * i
    s -= (l[i] - a[i])
    if s >= m*v:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
a = a[p-1:]
l = list(accumulate(a))
ans = p

for i in range(n-p):
    s = (n-p-(i+1))*m + p*m
    s += (a[i] + m) * i
    s -= (l[i] - a[i])
    if s >= m*v:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
a = a[p:]
l = list(accumulate(a))
ans = p

for i in range(n-p):
    s = (n-p-(i+1))*m + p*m
    s += (a[i] + m) * i
    s -= (l[i] - a[i])
    if s >= m*v:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np

stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m, v, p = na()
a = na()
a.sort(reverse=True)
a = np.array(a)
left = p - 1
right = n - 1
def check(i):
    c = a[i] + m
    s = (p-1) * m + np.sum(np.minimum(c - a[p-1:], m)) - m
    if i+1 <= p:
        return True
    elif a[i] + m < a[p-1]:
        return False
    elif s > m * (v-1):
        return True
    else:
        return False
while left + 1 < right:
    x = (left + right) // 2
    if check(x):
        left = x
    else:
        right = x
print(left + 1)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort()
c = Counter(a)
x = a[n-p]
tmp = c[x]
ans = 0
lst = []
for i in a:
    if x <= i:
        ans += 1
        lst.append(i)
num = n - ans
lst2 = []
for i in range(num):
    if i+1 >= v:
        if a[i] + m >= x:
            ans += 1
    else:
        if max(num - i,tmp) > n-v:
            continue
        if a[i] + m >= x:
            ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort()
c = Counter(a)
x = a[n-p]
tmp = c[x]
ans = 0
lst = []
for i in a:
    if x <= i:
        ans += 1
        lst.append(i)
cnt = ans
lst2 = []
for i in range(n):
    if a[i] < x:
        if i+1 > v:
            if a[i] + m >= x:
                ans += 1
        else:
            if n - v < tmp:
                continue
            if v - (i+1) > p:
                continue
            if a[i] + m >= x:
                ans += 1
            lst2.append(a[i])
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort()
x = a[n-p]
ans = 0
val = deque()
inval = deque()
for i in a:
    if x <= i:
        ans += 1
        val.append(i)
    else:
        inval.append(i)
c = list(Counter(a).items())
for i,j in c:
    if i == x:
        tmp = j
        break
if n - v >= tmp:
    cnt = 0
    while inval:
        s = inval.pop()
        while val:
            t = val.popleft()
            if s + m >= t:
                cnt += 1
                break
    ans += min(tmp,cnt)
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort()
x = a[n-p]
ans = 0
val = deque()
inval = deque()
for i in a:
    if x <= i:
        ans += 1
        val.append(i)
    else:
        inval.append(i)

if ans - (n - v) < p:
    cnt = 0
    while inval:
        s = inval.pop()
        while val:
            t = val.pop()
            if s + m >= t:
                cnt += 1
                break
    ans += min((n-v),cnt)
print(ans)

Submission status: Wrong Answer

Solution code:
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

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

S = cumulative_sum(A)

def check(i):
    s = max(0,S.get(i+1,N-P+1))
    res = max(M*(V-P-i),0)
    return ((A[i]+M)*max(0,N-P-i))>=s+res

ans = sum(check(i) for i in range(N))
print(ans)

Submission status: Wrong Answer

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

S = [0]*(N+1)
for i,a in enumerate(A):
    S[i+1] = S[i] + A[i]

def check(i):
    s = max(0,S[N-P+1] - S[i+1])
    res = max(M*(V-P-i),0)
    return ((A[i]+M)*max(0,N-P-i))>=s+res

ans = sum(check(i) for i in range(N))
print(ans)

Submission status: Wrong Answer

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

S = [0]*(N+1)
for i,a in enumerate(A):
    S[i+1] = S[i] + A[i]

def check(i):
    s = S[N-P+1] - S[i+1]
    res = max(M*(V-P-i),0)
    return ((A[i]+M)*max(0,N-P-i))>=s+res

def binary_search(l,r,func):
    if func(l):return l-1
    if not func(r):return r
    while l+1<r:
        i = (l+r)//2
        if func(i):
            r = i
        else:
            l = i
    return l

print(N-(binary_search(0,N-1,check)+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)

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

ans = P
j = P
for i in range(P, N):
    # front leg
    # if (i + 1 < N) and (A[i] == A[i + 1]):
    #     continue
    
    # rear leg
    while A[j] > A[i] + M:
        j += 1

    if A[i] + M < A[P - 1]:
        break
    elif (
        M * (P - 1)
        + (A[i] + M) * (i + 1 - j)
        - (cum_A[i + 1] - cum_A[j])
        + M * (N - i - 1)
        >= M * V
    ):
        ans = i + 1
    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)

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

ans = P
j = P
for i in range(P, N):
    # front leg
    if (i + 1 < N) and (A[i] == A[i + 1]):
        continue
    
    # rear leg
    while A[j] > A[i] + M:
        j += 1

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

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
A=sorted(list(map(int,input().split())))[-p::-1]
s=m*v-m*n
for u,a in enumerate(A):
 if a<A[0]-m or s>u*a:break
 s+=a
print(u+p-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)

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

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

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

    if A[i] + M < A[P - 1]:
        break
    elif (
        M * (P - 1)
        + (A[i] + M) * (i + 1 - j)
        - (cum_A[i + 1] - cum_A[j])
        + M * (N - i - 1)
        >= M * V
    ):
        ans = i + 1
    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)

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

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

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

    if A[i] + M < A[P - 1]:
        break
    elif (
        M * (P - 1)
        + (A[i] + M) * (i + 1 - j)
        - (cum_A[i + 1] - cum_A[j])
        + M * (N - i - 1)
        >= M * V
    ):
        ans = i + 1
    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)

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
A=sorted(list(map(int,input().split())))[-p::-1]
s=0;p-=1
for u,a in enumerate(A):
 if a>=A[0]-m and u*a+m*n-m*v>=s:s+=a;p+=1
print(p)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
A=sorted(list(map(int,input().split())))[p::-1]
s=0;p-=1
for u,a in enumerate(A):
 if a>=A[0]-m and u*a+m*n-m*v>=s:s+=a;p+=1
print(p)

Submission status: Wrong Answer

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)


def isOK(i):  # i番目が採用されるかどうかを確かめる
    # 上位P-1問には上限いっぱいM票ずつ投票可能
    need = M * (P-1)
    # 今見ているi問目には上限いっぱいM票入れるのが妥当
    need += M
    # 今見ているi問目よりもスコアの小さいN-i-1問は上限いっぱいM票入れる
    # N=10, i=7の場合は後ろは残り2問
    # need += M * (N-i-1)
    ai = A[i]  # 基準値
    s = 0
    for j in range(P-1, i):
        d = A[j] - ai
        if d > M:  # aiに上限いっぱい投票しても届かない世界があるならi番目は採用されない
            return False
        s += d
    return True


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid
print(left + 1)

Submission status: Wrong Answer

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

print(A)
print(M*V)
def isOK(i):  # i番目が採用されるかどうかを確かめる
    # 上位P-1問には上限いっぱいM票ずつ投票可能
    need = M * (P-1)
    # 今見ているi問目には上限いっぱいM票入れるのが妥当
    need += M
    # 今見ているi問目よりもスコアの小さいN-i-1問は上限いっぱいM票入れる
    # N=10, i=7の場合は後ろは残り2問
    need += M * (N-i-1)
    ai = A[i]  # 基準値
    s = 0
    for j in range(P-1, i):
        d = A[j] - ai
        if d > M:  # aiに上限いっぱい投票しても届かない世界があるならi番目は採用されない
            return False
        s += d
    print(i, need, s)
    if need + s >= M*V:
        return True
    else:
        return False


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid
print(left + 1)

Submission status: Wrong Answer

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

capacity = M*V


def isOK(i):
    ai = A[i]  # 基準となる値
    s = 0
    # 0~P-2番目のP-1問とi番目とi番目以降には全員が投票しても構わない
    # P-1番目からi-1番目までについて考える必要がある
    for j in range(P-1, i):
        d = A[j] - ai
        # A[j]とaiの差がM以上あるということは、A[0]からA[j-1]までも差がM以上あり追いつけない
        if d > M:  # この時点で先頭のA[j]問を含む先頭の問題たちはaiが追いつけないスコアをもっている
            return False
        s += d  # 基準値並ぶことは許されているので、基準値との差分を投票しても良い
    if s + M*(P-1) + M*(N-(i-1)) >= capacity:
        return True
    else:
        return False


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid
print(left + 1)  # left問目が満たす。0-indexで3が満たすなら答えの値は4

Submission status: Wrong Answer

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

capacity = M * (N-V)


def isOK(i):
    ai = A[i]  # 基準となる値
    s = 0
    # 0~P-2番目のP-1問とi番目とi番目以降には全員が投票しても構わない
    # P-1番目からi-1番目までについて考える必要がある
    for j in range(P-i, i):
        d = A[j] - ai
        # A[j]とaiの差がM以上あるということは、A[0]からA[j-1]までも差がM以上あり追いつけない
        if d > M:  # この時点で先頭のA[j]問を含む先頭の問題たちはaiが追いつけないスコアをもっている
            return False
        s += d
    if s > capacity:
        return False
    else:
        return True


left = -1
right = N
while right - left > 1:
    mid = right + (left-right)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid
print(left + 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)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    D = [d for d in D if d > 0]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        E = D[left: left + W]
        T = E[0]

        cnt += T
        minus = min(E[-1], diff // len(E))
        cnt -= minus
        diff -= minus * len(E)
        for d in E:
            diff += T - d

    return cnt <= M

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

print(ng)

Submission status: Wrong Answer

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    D = [d for d in D if d > 0]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        E = D[left: left + W]
        T = D[left]

        cnt += T
        cnt -= diff // len(E)
        diff %= len(E)
        for d in E:
            diff += T - d

    return cnt <= M

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

print(ng)

Submission status: Wrong Answer

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:][:: -1]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        T = D[-1]
        cnt += T
        cnt -= diff // W
        diff %= W
        for d in D[left: left + W]:
            diff += T - d

    return cnt <= M

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

print(ng)

Submission status: Wrong Answer

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        T = D[left]
        cnt += T
        for d in D[left: left + W]:
            diff += T - d

    return cnt - diff // W <= M

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

print(ng)

Submission status: Wrong Answer

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        T = D[left]
        cnt += T - diff // W
        diff %= W
        for d in D[left: left + W]:
            diff += T - d

    return cnt <= M

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

print(ng)

Submission status: Wrong Answer

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        T = D[left]
        cnt += T - diff // W
        diff %= W
        for d in D[left: left + W]:
            diff += T - d

    return max(max(D), cnt) <= M

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

print(ng)

Submission status: Wrong Answer

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = 0
    diff = 0

    for left in range(0, len(D), W):
        T = D[left]
        cnt += T - diff // W
        diff //= W
        for d in D[left: left + W]:
            diff += T - d

    return max(max(D), cnt) <= M

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

print(ng)

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 = -1
ng = N

# V個増やす = N - V個減らす
V = N - V
def isOk(n):
    b = A[n]
    cnt = [max(0, a - b) for a in A]
    cnt = cnt[P - 1:]
    return max(max(cnt), sum(cnt)) <= M * V

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

print(max(P, ng))

Submission status: Wrong Answer

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

ok = max(A)
ng = -1

def isOk(n):
    cnt = [max(0, a - n) for a in A]
    return sum(sorted(cnt, reverse=True)[P - 1:]) <= (N - V) * M

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

ans = sum([a >= ok for a in A])
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 = -1
ng = N

# V個増やす = N - V個減らす
V = N - V
def isOk(n):
    b = A[n]
    cnt = [max(0, a - b) for a in A]
    cnt = cnt[P:]
    return sum(cnt) <= M * V

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

print(max(P, ng))

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 = -1
ng = N

# V個増やす = N - V個減らす
V = N - V
def isOk(n):
    b = A[n]
    cnt = [max(0, a - b) for a in A]
    cnt = cnt[P - 1:]
    return sum(cnt) <= M * V

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

print(max(P, ng))

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 = 0
ng = N

# V個増やす = N - V個減らす
V = N - V
def isOk(n):
    b = A[n]
    cnt = [max(0, a - b) for a in A]
    cnt = cnt[P - 1:]
    return sum(cnt) <= M * V

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

print(max(P, ng))

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

# V個増やす = N - V個減らす
V = N - V
def isOk(n):
    b = A[n]
    cnt = [max(0, a - b) for a in A]
    cnt = cnt[P - 1:]
    return sum(cnt) <= M * V

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

print(ng)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort()
c = list(Counter(a).items())
if len(c) == 1:
    print(n)
    quit()
tmp = a[n-p]
ans = 0
for i,j in c:
    if i >= tmp:
        ans += j
if ans - (n - v) < p:
    cnt = 0
    for i in range(n):
        if a[i] < tmp:
            if a[i] + m >= tmp:
                cnt += 1
    ans += min(n-v, cnt)
print(ans)

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()
l = -1
r = N
while r - l > 1:
    m = (l+r)//2
    if m+1+P > N:
        r = m
        continue
    if V <= m+P:
        if A[m]+M >= A[-P]:
            r = m
        else:
            l = m
        continue
    limit = A[m] + M
    can = 0
    for i in range(m+1, N-P+1):
        can += max(0, limit-A[i])
    if can >= (V-P-m)*M:
        r = m
    else:
        l = m

print(N-r)

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()
l = 0
r = N+1
while r - l > 1:
    m = (l+r)//2
    if m+1+P > N:
        r = m
        continue
    if V <= m+P:
        if A[m]+M >= A[-P]:
            r = m
        else:
            l = m
        continue
    limit = A[m] + M
    can = 0
    for i in range(m+1, N-P+1):
        can += max(0, limit-A[i])
    if can >= (V-P-m)*M:
        r = m
    else:
        l = m

print(N-r)

Submission status: Wrong Answer

Solution code:
from itertools import *
n, m, v, p, *a = map(int, open(0).read().split())
a.sort(reverse=True)
acc = list(accumulate(a)) + [0]
ok, ng = p - 1, n
while ng - ok > 1:
	mid = (ok + ng) // 2
	if a[mid] + m > a[p - 1] and (a[mid] + m) * (mid - p + 1) - (acc[mid - 1] - acc[p - 2]) >= m * (
			v - (p - 1) - (n - mid)):
		ok = mid
	else:
		ng = mid
print(ok + 1)

Submission status: Wrong Answer

Solution code:
from itertools import*
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
acc=list(accumulate(a))+[0]
ok,ng=p-1,n
while ng-ok>1:
	mid=(ok+ng)//2
	if 0<=(a[mid]+m)*(mid-p+1)-(acc[mid-1]-acc[p-2])>=m*(v-(p-1)-(n-mid)):
		ok=mid
	else:
		ng=mid
print(ok+1)

Submission status: Wrong Answer

Solution code:
from itertools import*
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
acc=list(accumulate(a))+[0]
ok,ng=p-1,n
while ng-ok>1:
	mid=(ok+ng)//2
	if (a[mid]+m)*(mid-p+1)-(acc[mid-1]-acc[p-2])>=m*(v-(p-1)-(n-mid)):
		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)

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

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

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

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

Submission status: Wrong Answer

Solution code:
from itertools import*
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
acc=list(accumulate(a))
ok,ng=p,n
while ng-ok>1:
	mid=(ok+ng)//2
	if (a[mid]+m)*(v-p+1-n+mid)<=acc[mid-1]-acc[p-1]:
		ok=mid
	else:
		ng=mid
print(ok)

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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