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()
B = [0]*N
B[0] = A[0]
for i in range(1,N):
    B[i] = B[i-1] + A[i]

#print(A)
#print(B)
mn = 0
mx = N-1
k = (mn+mx)//2
while not mx-mn == 1:
    c = A[k]
    c += M
    p = bisect.bisect_right(A,c)
    flag = False
    #print("k",k)
    #print("c",c)
    #print("p",p)
    ALL = V*M
    ALL -= (k+1)*M # left
    if N-P < p:
        ALL -= (P-1)*M # right
        if ALL <= 0:
            flag = True
        else:
            #print("ALL",ALL)
            #print(N-P-k,B[N-P]-B[k])
            res = c*(N-P-k) - (B[N-P] - B[k])
            #print("res",res)
            if ALL <= res:
                flag = True
    #print("flag",flag)
    if flag:
        mx = k
    else:
        mn = k
    k = (mn+mx)//2
print(N-mx)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=1)
#print(a)
se=set()
for i in range(p):se.add(a[i])

s=a[p-1]
for i in range(p,n):
  x=max(v-(n-((i+1)-(p-1)))-1,0)
  if a[i]+m>=0--(s+m*x)//(i-p+1):se.add(a[i])
  #print(i,x,s+m*x,s,0--(s+m*x)//(i-p+1))
  s+=a[i]

ans=0
for i in a:
  if i in se:ans+=1
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

As.sort(reverse=True)

scoreP = As[P-1]

def isOK(k):
    if k < P or As[k] == scoreP:
        return True

    scoreK = As[k] + M
    if scoreK < scoreP:
        return False

    rest = M*(V-1)
    rest -= M*(P-1)
    if rest <= 0:
        return True

    for i in range(P, N):
        if i != k:
            rest -= min(M, scoreK-As[i])
    if rest <= 0:
        return True

    return False


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

print(ok+1)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
li = list(map(int,input().split()))
print(n-2);

Submission status: Wrong Answer

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

ans = 0

for i in range(n):
    f = a[i]
    f += m
    b = a.copy()
    b.remove(a[i])
    count = 0
    for j in range(m * (v-1)):
        b[b.index(min(b))] += 1
    for j in b:
        if j > f:
            count += 1
    if count >= p:
        continue
    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

lim_A = A[p-1]
res_A = A[p:]
res_n = len(res_A)

for i in range(res_n):
    res_A[i] = lim_A - res_A[i]

ans = lim_A
cnt = 0
for i in range(res_n):
    if m >= res_A[i] and m * max(v-p-(res_n-i-1), 0) <= cnt + (m-res_A[i])*(i+1):
        ans += 1
    cnt += res_A[i]

print(ans)

Submission status: Wrong Answer

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
currentMax = As[P-1]
output = P
for i in range(len(As)):
    if i >= P:
        if (As[i]+M >= currentMax) and (V <= ((len(As)-i) + (P - 1))):
            output = output + 1
print(output)

Submission status: Wrong Answer

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

border = As[P - 1]
more_than_border_num = 0
border_num = 0
ans = 0
for a in As:
    ans += a >= border
    border_num += a == border
    more_than_border_num += a > border


s = 0
for i, a in enumerate(As):
    if a >= border:
        s += a
        continue
    
    # a < border
    a2 = a + M
    new_v = V - 1 - (N - i - 1) - more_than_border_num

    new_v = max(new_v, 0)

    m = new_v // border_num
    n = new_v - (m * border_num)
    tmp = P - more_than_border_num
    if n >= tmp:
        tmp2 = border + m + 1
    else:
        tmp2 = border + m
    ans += a + M >= tmp2
    # print("i, a, m, n, tmp2 = ", i, a, m, n, tmp2)
        

print(ans)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
imos = [0]
fl = [0 for i in range(n+1)]
for i in a:
    imos.append(imos[-1]+i)
l = 0
if v<=p:
    for i in range(p,n):
        if a[i]+m>=tmp:
            ans+=1
    print(ans)
    exit()
else:
    i = p
    while i < n:
        if a[i]+m >= tmp:
            while i+1<n-1 and a[i]==a[i+1]:
                i+=1
            t = v-p- (n-1-i)
            if (a[i]+m)*(i-p)-(imos[i]-imos[p])>=t*m:
                ans=max(ans,i+1)
        i+=1
    print(ans)
    exit()

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, M, V, P = rl()
A = rl()
A.sort(reverse=True)
INF = 10 ** 10
A = A[P-1:] + [-INF] #上位P-1問は捨てる
V -= (P-1)
N = len(A)
answer = P-1

# 残りの問題からトップに立てるかどうか二分探索
high = N-1 #不可能
low = 0 #可能
while high > low + 1:
    mid = (high+low)//2
    num = V - (N-1-mid)
    B = np.array(A[:mid])
    #Bの中からM人のジャッジがnum問選ぶ
    count = ((A[mid] + M) - B).sum()
    if count <=  M * num:
        high = mid #不可能
    else:
        low = mid

answer += (low + 1)
print(answer)

Submission status: Wrong Answer

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


def check(x):
    if x > n - p:
        return True

    b = [0] * n
    b[x] = m
    for i in range(p - 1):
        b[n - 1 - i] = m
    cnt = m * (v - p)
    idx = n - p
    while cnt > 0 and idx >= 0:
        if b[idx] == m:
            idx -= 1
        elif a[idx] + b[idx] < a[x] + m:
            cnt -= min((a[x] + m) - (a[idx] + b[idx]), m)
            b[idx] = m
            idx -= 1
        else:
            idx -= 1

    if cnt > 0:
        return False
    else:
        return True


lb = 0  # False
ub = n - 1  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid
# lbがFalseの最大、ubがTrueの最小
# print(lb, ub)
ans = n - ub
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s=[None]*N
t=0
for i in range(N):
    t+=A[i]
    s[i]=t
S=M*(N-V)
l=P
r=N
while l<r:
    m=(r - l) // 2 + l
    if A[P-1]-M>A[m]:
        r=m
        continue
    if s[m-1]-s[P-2]-(m-P+1)*A[m]>S:
        r=m
        continue
    l=m+1
print(l)

Submission status: Wrong Answer

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
print(As)
currentMax = As[P-1]
print(currentMax)
output = P
for i in range(len(As)):
    if i >= P:
        if (As[i]+M >= currentMax) and (V <= ((len(As)-i) + (P - 1))):
            output = output + 1
print(output)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

ans = 0
tmp = -1
for x in range(N):
    if A[x] == tmp:
        ans = x+1
        continue
    tmp = A[x]

    if x < P:
        ans = x+1
        continue
    else:
        Smid = S[x]-S[P-1]
        C = V - (N-x + P-1)
        # print(x, Smid, C, Smid + C*M, (x-P+1), A[x] + M)
        if C < 0:
            if A[P-1] <= A[x] + M:
                ans = x+1
                continue
            else:
                break
        else:
            if -(-(Smid + C*M)//(x-P+1)) <= A[x] + M:
                ans = x+1
                continue
            else:
                break


print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

ans = 0
tmp = -1
for x in range(N):
    if A[x] == tmp:
        ans = x+1
        continue
    tmp = A[x]

    if x < P:
        ans = x+1
        continue
    else:
        Smid = S[x]-S[P-1]
        C = V - (N-x + P-1)
        print(x, Smid, C, Smid + C*M, (x-P+1), A[x] + M)
        if C < 0:
            if A[P-1] <= A[x] + M:
                ans = x+1
                continue
            else:
                break
        else:
            if -(-(Smid + C*M)//(x-P+1)) <= A[x] + M:
                ans = x+1
                continue
            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()
a = a[::-1]
tmp = a[p-1]
ans = p
imos = [0]
fl = [0 for i in range(n+1)]
for i in a:
    imos.append(imos[-1]+i)
l = 0
if v<=p:
    for i in range(p,n):
        if a[i]+m>=tmp:
            ans+=1
    print(ans)
    exit()
else:
    for i in range(p, n):
        if a[i]+m >= tmp:
            cnt = 1
            while i+1<n-1 and a[i]==a[i+1]:
                i+=1
            t = v-p- (n-1-i)
            if (a[i]+m)*(i-p)-(imos[i]-imos[p])>=t*m:
                ans=max(ans,i+1)
    print(ans)
    exit()

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

K = A[-P]
R = bisect.bisect_left(A, K)
RL = bisect.bisect_right(A, K)
L = bisect.bisect_left(A, K - M)
ans = N - R

for i in range(L, R):
    # print("i:", i, P+i, V > P+i)
    if V > P+i:
        v = V - (P+i)
        D = N-P - (A[i]+1) + 1
        # print(v*M, N-P-R + 1)
        if (-((-v*M) // D)) + K <= A[i]+M:
            ans += 1

    else:
        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 = sorted(a)

sm = sum(a[:n-p+1])

for k in range(n-p):
    sm -= a[k]
    if (n-p-k)*(a[k]+m) - sm <= (v-k-p)*m:
        continue
    else:
        print(n-k)
        exit()

print(p)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def solve(n, m, v, p, aaa):
    aaa.sort(reverse=True)
    count = Counter(aaa)
    scores = sorted(count.keys(), reverse=True)

    htm_cnt = 1  # higher than me excluding top p-1
    htm_sum = aaa[p - 1]
    rival = aaa[p - 1]
    ans = 0

    tmp_cnt = 0
    for pi, s in enumerate(scores):
        c = count[s]
        if tmp_cnt + c >= p:
            ans = tmp_cnt + c
            rival = s
            htm_cnt = tmp_cnt + c - (p - 1)
            htm_sum = s * htm_cnt
            break
        tmp_cnt += c
    else:
        raise RuntimeError

    # print(ans)
    # print(rival)
    # print(htm_cnt, htm_sum)

    for s in scores[pi + 1:]:
        c = count[s]
        upper = s + m

        v4mtm = v - (n - htm_cnt)  # remaining vote for higher than s excluding top p-1
        if v4mtm <= 0:
            if upper >= rival:
                ans += c
            else:
                break
        else:
            space = upper * htm_cnt - htm_sum
            if space >= m * v4mtm:
                ans += c

        htm_cnt += c
        htm_sum += s * c

    return ans


n, m, v, p = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, m, v, p, aaa))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from bisect import bisect_left, bisect_right
N, M, V, P = read_ints()
A = read_ints()
A.sort()
edge_idx = N - P
edge = A[-P]
# ここに処理を書けば終わりだ
# M人がちょうどV配ることによる副作用の扱いがわからん...
# print(A)
left_point = V * M
for i in range(edge_idx - 1, -1, -1):
    sa = edge - A[i]
    if sa > M or sa > left_point:
        break
    # 代入処理
    left_point -= sa
    A[i] = edge

if left_point > 0:
    left_point %= N

lower_bound_idx = bisect_left(A, edge)
n_candi = edge_idx - lower_bound_idx
print(P + n_candi - left_point)
# print(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)
nums = set()
ans = 0
border = float('inf')
index = float('inf')
for i in range(n):
    nums.add(a[i])
    if len(nums) == p:
        border = a[i]
    if len(nums) > p:
        index = i
        break
    ans += 1
if index != float('inf'):
    for i in range(index, n):
        if n - i >= v and border - a[i] >= m:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, M, V, P = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))

A.sort(reverse=True)
RA = A[::-1]


def can_choose(k):
    # A[k]が選ばれるか
    ak = A[k] + M
    greaters = N - bisect.bisect_right(RA, ak)
    if greaters >= P:
        return False
    # 自分より上位 P - 1 人には全部配る
    rem = (V - P) * M

    cnt = 0
    for i, a in reversed(list(enumerate(A))):
        if i == k:
            continue
        cnt += 1
        if cnt >= N - P:
            break
        if rem <= 0:
            break
        rem -= min(M, ak - a)
    return rem <= 0


# print(A)
# for i in range(N):
#     a = can_choose(i)
#     print(A[i], a)


ok = -1
ng = N
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if can_choose(mid):
        ok = mid
    else:
        ng = mid
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)

ans = P
border = A[P-1]
n_border = 1
for i in range(P, N):
    if A[i] == border:
        n_border += 1
    else:
        break

for i in range(P, N):
    if A[i] == border:
        ans += 1
    elif V-(N-i)-1 < 0 and A[i] + M >= border:
        ans += 1
    elif A[V-(N-i)-1] > border and A[i] + M >= border:
        ans += 1
    elif A[V-(N-i)-1] == border and A[i] + M >= border + -(-M//n_border):
        ans += 1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split(' '))
An = list(map(int,input().split(' ')))
An.sort(reverse=True)
threadhold_list = [0] * N
theard_num = An[P-1]
for idx,val in enumerate(An):
    threadhold_list[idx] = max(0,theard_num-val)
#print(An)
#print(threadhold_list)

min_num = 10**10
min_goal_num = 10**10
must_allocation_num = P - 1
for idx,val in enumerate(An):
    if idx + 1 <= P:
        min_num = min(min_num,val)
        min_goal_num = min(min_goal_num,val)
        continue
    if val == min_num:
        continue
    if threadhold_list[idx] <= M and must_allocation_num <= (N-idx):
        min_num = min(min_num,val)
        continue
    break
print(idx)

Submission status: Wrong Answer

Solution code:
import bisect
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
kijun=a[p-1]
s=[0]*n
for i in range(n):
  s[i]+=s[i-1]+a[n-i-1]
if p>=v:
  print(n-bisect.bisect_left(a[::-1],kijun-m))
else:
  for i in range(n)[::-1]:
    rem=m*max(0,v-(n-i+p-1))
    if rem+(s[n-p]-s[n-1-i]) <= (a[i]+m)*(i-p+1):
      print(i+1)
      break
    else:
      pass

Submission status: Wrong Answer

Solution code:
import bisect
import sys
import math
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

K = A[-P]
R = bisect.bisect_left(A, K)
RL = bisect.bisect_right(A, K)
L = bisect.bisect_left(A, K - M)
ans = N - R
D = RL-1 - R + 1

for i in range(L, R):
    # print("i:", i, P+i, V > P+i)
    if V > P+i:
        v = V - (P+i)
        # print(v*M, N-P-R + 1)
        if (-((-v*M) // D)) + K <= A[i]+M:
            ans += 1

    else:
        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)
reva = [a[0] - x for x in a]
ub = a[0]
lb = a[-1]

from bisect import *

def ok(val):
    i = bisect_left(reva,a[0]-val)
    val = a[i]
    if v-(min(n-i,v)) < p and a[p-1] <= a[i] + m:
        return True
    l = v - (p-1) - (n - i)
    if sum(list(map(lambda x:min(a[i]+m-x,m),a[p-1:i]))) >= l*m:
        return True
    return False

while ub > lb:
    mid = (ub+lb)//2
    if ok(mid):
        ub=mid
    else:
        lb=mid+1

print(len(list(filter(lambda x:x >= lb,a))))

Submission status: Wrong Answer

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

a = sorted(a)[::-1]

minp = a[p-1]
result = 0
td = 0
count = 0
tpcount = 1
tptd = 0
pre = minp
for i in range(p, n):
    if pre != a[i]:
        td += tptd
        count += tpcount
        tptd = 0
        tpcount = 0
    if m * min(n-v, i-p+1) >= (minp - a[i]) * count - td:
        result+=1
        tpcount+=1
        tptd+= minp - a[i]
        pre = a[i]
    else:
        break
print(result+p)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def solve(n, m, v, p, aaa):
    aaa.sort(reverse=True)
    count = Counter(aaa)
    scores = sorted(count.keys(), reverse=True)

    htm_cnt = 1  # higher than me excluding top p-1
    htm_sum = aaa[p - 1]
    rival = aaa[p - 1]
    ans = 0

    tmp_cnt = 0
    pi = 0
    for pi, s in enumerate(scores):
        c = count[s]
        if tmp_cnt + c >= p:
            ans = tmp_cnt + c
            rival = s
            htm_cnt = tmp_cnt + c - (p - 1)
            htm_sum = s * htm_cnt
            break
        tmp_cnt += c

    # print(ans)
    # print(rival)
    # print(htm_cnt, htm_sum)

    for s in scores[pi + 1:]:
        c = count[s]
        upper = s + m

        v4mtm = v - (n - htm_cnt)  # remaining vote for higher than s excluding top p-1
        if v4mtm <= 0:
            if upper >= rival:
                ans += c
            else:
                break
        else:
            space = upper * htm_cnt - htm_sum
            if space >= m * v4mtm:
                ans += c

        htm_cnt += c
        htm_sum += s * c

    return ans


n, m, v, p = map(int, input().split())
aaa = list(map(int, input().split()))
print(solve(n, m, v, p, aaa))

Submission status: Wrong Answer

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



############
for i in range(V-1):
  A[-1-i] +=M

thhold = A[-P]-M
index = bisect.bisect_left(A,thhold)

print(N-index)

Submission status: Wrong Answer

Solution code:
def check(i, N, M, V, P, A):
    K = N - V
    tot = sum(A[(P-1):i]) - A[i]*(i-(P-1))
    if K*M >= tot and (A[P-1]-A[i])<=N:
        return True
    else:
        return False

N, M, V, P = map(int,input().split())
A = [int(i) for i in input().split()]
A.sort(reverse=True)

start = P
end = N-1
if check(end, N, M, V, P, A):
    print(N)
elif not check(start, N, M, V, P, A):
    print(P)
else:
    while True:
        if (end - start) == 1:
            break
        new = (start + end)//2
        flag = check(new, N, M, V, P, A)
        if flag:
            start = new
        else:
            end = new
    print(start+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s=A[P-1]
c=0
if P>=V:
  for i in range(P,N):
    if s-A[i]<=M:
      c+=1
    else:
      break
else:
  for i in range(P,N):
    sa=s*(i-P)-sum(A[P:i])
    if P-1+N-i+1+sa//M<V:
      break
    if s-A[i]<M:
      c+=1
    else:
      break
print(c+P)

Submission status: Wrong Answer

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M, V, P = inpl()
A = inpl()
A.sort(reverse=True)
s = 0
S = []
for i in range(N):
    s += A[i]
    S.append(s)
OK = P-1
NG = N
while NG - OK > 1:
    x = (NG+OK)//2
    if A[P-1] > A[x] + M:
        NG = x
    elif P + (N-1-x) >= V:
        OK = x
    else:
        remain = M * (V-P-(N-1-x))
        space = (x-P+1)*(A[x]+M) - (S[x-1] - S[P-2])
        if remain <= space:
            OK = x
        else:
            NG = x
print(OK+1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

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

B = [0] * N
B[0] = A[0]
for i in range(1, N):
    B[i] = B[i - 1] + A[i]

if V <= P:
    tmp = bisect_left(A[:-P], A[-P] - M)
    print (N - tmp)
    exit()

v = V - (P - 1) #P-1個は関係ないところですでに使用済み

#大丈夫かどうかの確認
def check(x):
    if A[x] + M < A[-P]:
        return False
    if v - 1 <= x:
        return True
    
    zan = M * (v - (x + 1))
    if x > 0:
        used = B[-P] - B[x - 1]
    else:
        used = B[-P]

    if (A[x] + M) * ((N - P) - x) - used >= zan:
        return True
    return False     

#二分探索の初期値
l = 0
r = N - P
while r - l > 1:
    # print (l, r)
    # s = str(input())
    mid = (l + r) // 2
    if check(mid):
        r = mid
    else:
        l = mid

if check(l):
    print (N - l)
    exit()
if check(r):
    print (N - r)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
imos = [0]
fl = [0 for i in range(n+1)]
for i in a:
    imos.append(imos[-1]+i)
if v<=p:
    for i in range(p,n):
        if a[i]+m>=tmp:
            ans+=1
    print(ans)
    exit()
else:
    for i in range(p, n):
        if a[i]+m >= tmp:
            t = v-p- (n-1-i)
            if fl[i-1]==1 and a[i]==a[i-1]:
                ans+=1
                fl[i]=1
                continue
            if (a[i]+m)*(i-p)-(imos[i]-imos[p])>=t*m:
                ans+=1
                fl[i]=1
    print(ans)
    exit()

Submission status: Wrong Answer

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


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

left = 0
right = N - P + 1
while left < right:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid + 1
print(N - left)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=p
S=[A[p-1]]
for i in range(p,n):
    S.append(S[-1]+A[i])
for i in range(p,n):
    if v<=p+n-i-1:
        if A[i]-A[p-1]<=m:
            ans+=1
    else:
        if A[i]-A[p-1]<=m and S[i-p]-A[i]*(i-p+1)<=(n-v)*m:
            ans+=1
        else:
            break
print(ans)

Submission status: Wrong Answer

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

As.sort(reverse=True)

scoreP = As[P-1]

def isOK(k):
    if k < P:
        return True

    scoreK = As[k] + M
    if scoreK < scoreP:
        return False

    rest = M*(V-1)
    rest -= M*(P-1)
    if rest <= 0:
        return True

    for i in range(P, N):
        if i != k:
            rest -= min(M, scoreK-As[i])
    if rest <= 0:
        return True

    return False


ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(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()
a = a[::-1]
tmp = a[p-1]
ans = p
imos = [0]
fl = [0 for i in range(n+1)]
for i in a:
    imos.append(imos[-1]+i)
if v<=p:
    for i in range(p,n):
        if a[i]+m>=tmp:
            ans+=1
    print(ans)
    exit()
else:
    for i in range(p, n):
        if a[i]+m >= tmp:
            t = v-p- (n-1-i)
            if fl[i-1]==1 and a[i]==a[i-1]:
                ans+=1
                continue
            if (a[i]+m)*(i-p)-(imos[i]-imos[p])>=t*m:
                ans+=1
                fl[i]=1
    print(ans)
    exit()

Submission status: Wrong Answer

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

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

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

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
n,m,v,p=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=n,0
while l-r>1:
    t=(l+r)//2
    s=a[t]+m
    w=a[:]
    k=m*(v-1)
    for i in range(n):
        if i!=t:
            if i<t:
                c=min(k,m)
                k-=c
                w[i]+=c
            else:
                if w[i]>=s:
                    break
                else:
                    c=min(k,s-w[i])
                    k-=c
                    w[i]+=c
            if k==0:
                break
    if k>0:
        for j in range(n-1,-1,-1):
            if j!=t:
                g=min(k,m-w[j]+a[j])
                w[j]+=g
                k-=g
            if k==0:
                break
    w.pop(t)
    w=sorted(w)
    if n-br(w,s)<=p:
        l=t
    else:
        r=t
print(n-l)

Submission status: Wrong Answer

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