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())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n - 1
low = 0
mid = (high + low) // 2
# 下げるときはhigh = mid-1
# 上げるときはlow = mid
for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

# print(prob_set)
# print(ruiseki_prob)

while low < high:
    mid = (low + high) // 2
    # print(mid)
    f = True
    # まず上からp個以内であれば問答無用でOK (つまりindexがp>i)
    if mid < p:
        # print("<p")
        f = True
    else:
        # i~nには全員が票を投じると考えてよい (ここまででn-i票)
        # 次に上からp-1個に全員が票をいれてもよい(ここまでn-i + p-1)
        # それでも無理ならp ~ i-1までに残りを入れる必要がある.これがp[i] + m以下であればいいことがわかる
        if prob_set[mid] + m < prob_set[p - 1]:
            # どうあがいても無理
            # print("too short")
            f = False
        else:
            # どうにかなる
            if p - 1 + n - mid >= v:
                # print("OK for voting")
                f = True
            else:
                # mid
                amari_hyou = m * (v - (p - 1) - (n - mid))
                if ruiseki_prob[mid - 1] - ruiseki_prob[p - 2] + amari_hyou <= (prob_set[mid] + m) * (
                        (mid - 1) - (p - 2)):
                    # print("OK for super-voting")
                    f = True
                else:
                    # print("cannot EVEN super-voting")
                    f = False
    if f:
        low = mid + 1
    else:
        high = mid

print(low)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう

Submission status: Wrong Answer

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

target = A[p-1]
target_count = 0

for a in A:
    if a == target:
        target_count += 1
    elif a < target:
        break

over_target = p - 1
prev = target
ans = p

for idx in range(p, n):
    candidate = A[idx]
    under = n - idx - 1
    if candidate == prev:
        ans += 1
        continue

    if candidate + m >= target:
        if over_target + under >= v-1:
            ans += 1
            prev = candidate

        else:
            exceed = abs(v-1 - under - over_target)
            add = m * exceed // target_count + bool((m * exceed) % target_count)
            if candidate + m >= target + add:
                ans += 1
                prev = candidate
            else:
                break
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

A = list(map(int, input().split()))
A.sort(reverse=True)

print(1)
exit()

NUM = [0] * N
ACN = [0] * N
cnt = 0
mx = A[0]

# cnt and accumulation
for a in A:
    d = mx - a
    cnt += 1
    NUM[d] += 1
    ACN[d] = cnt

# P Number Problem
PROBLEM_P = 0
p = P
for i in range(0, A[0]+1):
    if NUM[i] == 0:
        continue

    p -= NUM[i]

    if p < 0:
        PROBLEM_P = i
        break

    if i == (A[0]+1) and p > 0:
        print(N)
        exit()

#print("NUM", NUM)
#print("PROBLEM_P", PROBLEM_P)

# R Number Problem
R = PROBLEM_P + M

# P-1 Problem
ans = 0
NG_POINT = (P-1) * M
NG_POINT += (N - ACN[R]) * M
MV = M * V

# p problem num
num_p = ACN[PROBLEM_P] - P

for r in range(R, -1, -1):
    need_point = M
    total = (need_point * NUM[r]) + NG_POINT

    for q in range(r-1, PROBLEM_P, -1):
        if NUM[q] == 0:
            continue
        total += NUM[q] * (q - r + M)

    total += num_p * (PROBLEM_P - r + M)

    if total >= MV:
        ans = r
        break
    else:
        NG_POINT += NUM[r] * M

print(ACN[ans])

Submission status: Wrong Answer

Solution code:
import sys
n,m,v,p=map(int,sys.stdin.readline().split())
a=sorted(list(map(int, sys.stdin.readline().split())),reverse=True)[p-1:]
l,r=0,n-p

def adopt(x):
    global a,n,m,v
    b=a[x]+m
    al=(v-(n-x))*m
    s=x*b-sum(a[:x])
    return al<=s

while l+1<r:
    k=(l+r)//2
    if adopt(k):
        l=k
    else:
        r=k

if adopt(r):
    print(p+r)
else:
    print(p+l)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from bisect import bisect_left, bisect_right
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    A.sort()
    # print(A)

    # 二分探索で探す
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2
        # print("\n***二分探索 {} in ({}, {})".format(mid, left, right))

        if N-P <= mid:
            # print("A")
            right = mid
            continue

        if A[mid]+M < A[N-P]:
            # print("B")
            left = mid
            continue

        # 入れられても構わない票をカウントする
        # print("{}番目の数は{}".format(mid, A[mid]))
        # print("{}番目から{}番目に{}人が加点する(+{})".format(0, mid-1, M, mid*M))
        # print("{}番目から{}番目に{}人が加点する(+{})".format(N-P+1, N-1, M, (P-1)*M))
        tot = 0
        for i in range(mid+1, N-P):
            tot += A[mid]+M-A[i]
        # print("{}番目から{}番目に{}人が合計{}点加点する(+{})".format(mid+1, N-P, M, tot, tot))
        tot += (P-1)*M
        tot += mid*M

        # print("tot: {}, M*V: {}".format(tot, M*V))

        if tot < M*(V-1):
            left = mid
            continue
        else:
            right = mid
            continue

    # print(right)
    # A[right]が数
    print(N-bisect_left(A, A[right]))
    # Yがわかったときの答え

    return


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:
N,M,V,P=map(int,input().split())
B = sorted(list(map(int, input().split())))[::-1]
count=P
dif=0
for i in range(P,N):
    dif+=B[i-1]
    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())
B = sorted(list(map(int, input().split())))[::-1]
count=P
dif=0
for i in range(P,N):
    dif=+B[i-1]
    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())
B = sorted(list(map(int, input().split())))[::-1]
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:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def check(x, N, M, V, P, A):
    if (N - x) <= P:
        return True

    if V <= x + P:
        return (A[x] + M) >= A[N-P]

    x_score = A[x] + M
    total_v = (V - x - P) * M
    show('x =', x, 'A[x] =', A[x], 'x_score =', x_score, 'total_v =', total_v)

    if A[N-P] > x_score:
        return False

    for i in range(x+1, N-P+1):
        show('i = ', i, 'A[i] =', A[i], 'total_v =', total_v,
             '(x_score - A[i]) =', (x_score - A[i]))
        total_v -= min(M, (x_score - A[i]))

    show('total_v =', total_v)
    if total_v <= 0:
        return True
    else:
        return False


def check_(x, N, M, V, P, A):
    if (N-x) <= P:
        return True
    if(V <= x+P):
        return(A[x]+M >= A[N-P])

    x_score = A[x]+M
    total_v = (V-x-P)*M

    if(A[N-P] > x_score):
        return False

    for i in range(x+1, N-P+1):
        total_v -= min(M, (x_score - A[i]))
    if total_v <= 0:
        return True
    else:
        return False


def main():
    N, M, V, P = MI()
    A = MI()
    A = sorted(A)
    show('N =', N, 'M =', M, 'V =', V, 'P =', P)
    show(A)

    l = 0
    r = N - 1
    while r-l > 1:
        mid = (l+r) // 2
        # print('brefore l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
        if check_(mid, N, M, V, P, A):
            r = mid
        else:
            l = mid
        # print('after l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    print(N - r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def check(x, N, M, V, P, A):
    if N - x <= P:
        return True

    if V <= x + P:
        return A[x] + M >= A[N-P]

    x_score = A[x] + M
    total_v = (V - x - P) * M
    show('x =', x, 'A[x] =', A[x], 'x_score =', x_score, 'total_v =', total_v)

    if A[N-P] > x_score:
        return False

    for i in range(x+1, N-P+1):
        show('i = ', i, 'A[i] =', A[i], 'total_v =', total_v,
             '(x_score - A[i]) =', (x_score - A[i]))
        total_v -= min(M, (x_score - A[i]))

    show('total_v =', total_v)
    if total_v <= 0:
        return True
    else:
        return False


def main():
    N, M, V, P = MI()
    A = MI()
    A = sorted(A)
    show('N =', N, 'M =', M, 'V =', V, 'P =', P)
    show(A)

    isOK = N-1
    isNG = 0
    while(isOK-isNG > 1):
        middle = (isOK+isNG)//2
        if(check(middle, N, M, V, P, A)):
            isOK = middle
        else:
            isNG = middle
    print(N-isOK)
    return
    # l = 0
    # r = N - 1
    # while r-l > 1:
    #     mid = (l+r) // 2
    #     # print('brefore l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    #     if check(mid, N, M, V, P, A):
    #         r = mid
    #     else:
    #         l = mid
    #     # print('after l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    # print(N - r)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


show_flg = False
# show_flg = True


def check(x, N, M, V, P, A):
    if N - x <= P:
        return True

    if V <= x + P:
        return A[x] + M >= A[N-P]

    x_score = A[x] + M
    total_v = (V - x - P) * M
    show('x =', x, 'A[x] =', A[x], 'x_score =', x_score, 'total_v =', total_v)

    if A[N-P] > x_score:
        return False

    for i in range(x+1, N-P+1):
        show('i = ', i, 'A[i] =', A[i], 'total_v =', total_v,
             '(x_score - A[i]) =', (x_score - A[i]))
        total_v -= min(M, (x_score - A[i]))

    show('total_v =', total_v)
    if total_v <= 0:
        return True
    else:
        return False


def main():
    N, M, V, P = MI()
    A = MI()
    A = sorted(A)
    show('N =', N, 'M =', M, 'V =', V, 'P =', P)
    show(A)

    l = 0
    r = N - 1
    while r-l > 1:
        mid = (l+r) // 2
        # print('brefore l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
        if check(mid, N, M, V, P, A):
            r = mid
        else:
            l = mid
        # print('after l =', l, 'mid =', mid, 'r =', r, 'A[mid] =', A[mid])
    print(N - r)


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()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    C = sorted_dic_A[P:]
    ans = set()

    num_vote = M * V
    for i, v in C:
        if P_min_val > v + M:
            break
        margin = num_vote
        margin -= M * (P-1)
        margin_list = [v+M-w for (j,w) in C if j!=i]
        mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
        margin -= M
        margin -= sum(mod_margin_list)
        if margin > 0:
            break
        ans.add(i)

    for i, _ in B:
        ans.add(i)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    N,M,V,P=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    
    def solve(mid):
        point=A[mid]+M
        z=0
        c=0
        i=1
        while c<P-1:
            if N-i!=mid:
                z+=min(M+A[N-i]-point,M)
                c+=1
            i+=1
        for i in range(N):
            if i!=mid:
                z+=min(M,max(point-A[i],0))
        if point>=A[N-P] and z>=M*(V-1):
            return True
        else:
            return False
        
    print(N-nibutan(N-1,-1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)
    # chkprint(sorted_dic_A)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    # chkprint(B)
    C = sorted_dic_A[P:]
    # chkprint(C)

    ans = set()

    num_vote = M * V
    # chkprint(num_vote)
    for i, v in C:
        if P_min_val > v + M:
            break
        margin = num_vote
        margin -= M * (P-1)
        margin_list = [v+M-w for (j,w) in C if j!=i]
        mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
        # chkprint(margin_list)
        # chkprint(mod_margin_list)
        margin -= M
        margin -= sum(mod_margin_list)
        # chkprint(margin)
        if margin > 0:
            break
        ans.add(i)

    for i, _ in B:
        ans.add(i)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    N,M,V,P=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    
    def solve(mid):
        point=A[mid]+M
        z=0
        c=0
        i=1
        while c<P-1:
            if N-i!=mid:
                z+=M+min(A[N-i]-point,0)
                c+=1
            i+=1
        for i in range(N):
            if i!=mid:
                z+=min(M,max(point-A[i],0))
        if point>=A[N-P-1] and z>=M*(V-1):
            return True
        else:
            return False
        
    print(N-nibutan(N-1,-1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)
    # chkprint(sorted_dic_A)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    # chkprint(B)
    C = sorted_dic_A[P:]
    # chkprint(C)

    ans = set()

    num_vote = M * V
    # chkprint(num_vote)
    for i, v in C:
        if P_min_val > v + M:
            break
        margin = num_vote
        margin -= M * (P-1)
        margin_list = [v+M-w for (j,w) in C if j!=i]
        mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
        # chkprint(margin_list)
        # chkprint(mod_margin_list)
        margin -= M
        margin -= sum(mod_margin_list)
        chkprint(margin)
        if margin <= 0:
            ans.add(i)

    for i, _ in B:
        ans.add(i)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    N,M,V,P=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    
    def solve(mid):
        point=A[mid]+M
        z=0
        c=0
        i=1
        while c<P-1:
            if N-i!=mid:
                z+=M+min(A[N-i]-point,0)
                c+=1
            i+=1
        for i in range(N):
            if i!=mid:
                z+=min(M,max(point-A[i],0))
        if point>=A[N-P] and z>=M*(V-1):
            return True
        else:
            return False
        
    print(N-nibutan(N-1,-1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    N,M,V,P=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    
    def solve(mid):
        point=A[mid]+M
        z=0
        c=0
        i=1
        while c<P-1:
            if N-i!=mid:
                z+=M+min(point-A[N-i],0)
                c+=1
            i+=1
        for i in range(N):
            if i!=mid:
                z+=min(M,max(point-A[i],0))
        if point>=A[N-P] and z>=M*(V-1):
            return True
        else:
            return False
        
    print(N-nibutan(N-1,-1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    N,M,V,P=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    
    def solve(mid):
        point=A[mid]+M
        z=0
        c=0
        i=1
        while c<P-1:
            if N-i!=mid:
                z+=M-(A[N-i]-point)
                c+=1
            i+=1
        for i in range(N):
            if i!=mid:
                z+=min(M,max(point-A[i],0))
        if point>=A[N-P] and z>=M*(V-1):
            return True
        else:
            return False
        
    print(N-nibutan(N-1,-1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import *
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    def nibutan(ok,ng):
        while abs(ok-ng) > 1:
            mid = (ok + ng) // 2
            if solve(mid):
                ok = mid
            else:
                ng = mid
        return ok
    
    
    N,M,V,P=map(int,input().split())
    A=sorted(list(map(int,input().split())))
    
    def solve(mid):
        point=A[mid]+M
        z=(P-1)*M
        for i in range(N):
            if i!=mid:
                z+=min(M,max(point-A[i],0))
        if point>=A[N-P] and z>=M*(V-1):
            return True
        else:
            return False
        
    print(N-nibutan(N-1,-1))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

#　せっかくなのであとでmarginを前計算してm*v以上をbisect
def isOK(x):
  border = a[x-1]
  if border + m < a[p-1]:
    return False
  elif x <= p:
    return True
  else:
    margin = m * n
    for i in range(p-1,x-1):
      margin -= a[i] - border
    if margin >= m * v:
      return True
    else:
      return False

def binary_search():
    ok = p-1
    ng = n
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans = binary_search()  
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)

#　せっかくなのであとでpossibleを前計算してm*v以上をbisectでもやる
def isOK(x):
  x -= 1
  if a[x] + m < a[p-1]:
    return False
  elif x+1 <= p:
    return True
  else:
    pos = m * n
    for i in range(p-1,x):
      pos -= a[i] - a[x]
    if pos >= m * v:
      return True
    else:
      return False

def binary_search():
    ok = p-1
    ng = n
    while abs(ok-ng) > 1:
        mid = (ok+ng)//2
        if isOK(mid):
            ok = mid
        else:
            ng = mid
    return ok

ans = binary_search()  
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)
limit = a[p - 1]
snum = a.index(limit)
restv = v - snum
idx = n // 2
left, right = 0, n - 1
memo = [None] * n
for i in range(n):
  mid = (left + right) // 2
  this = a.index(a[mid])
  garbage = n - this
  restp = a[snum:this]
  if restp == [] or (sum(restp) + (restv - garbage) * m) / len(restp) <= a[mid] + m:
    memo[mid] = True
    left = mid + 1
    mid = (left + right) // 2
    if memo[mid] is False:
      print(mid)
      break
  else:
    memo[mid] = False
    right = mid - 1
    mid = (left + right) // 2
    if memo[mid] is True:
      print(mid + 1)
      break

Submission status: Wrong Answer

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

    def is_ok(mid):
        if mid <= P:
            return False  # 採用可能
        if A[mid] + M < A[P-1]:
            return True  # 採用不可能
        votable = M + (P-1) * M + (N - (mid + 1))*M
        for i in range(P-1, mid):
            votable += min(M, max(0, A[mid] + M - A[i]))
        if M*V <= votable:
            return False
        else:
            return True

    def binary_search_meguru():
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right
    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

sum_=[0]*N
sum_[0]=A[0]
for i in range(1,N):
    sum_[i]=(sum_[i-1]+A[i])
# sum_=[0]
# cnt=0
# for i in range(N):
#   # 累積和
#   cnt += A[i]
#   sum_.append(cnt)

for i in range(P,N):
    thre=A[i]+M
    if thre < A[P-1]:
        continue

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    else:
        if P!=1:
            if sum_[i-1]-sum_[P-2]+M*remain <= thre*(i-P+1):
                ans+=1
        else:
            if sum_[i-1]-sum_[P-1]+M*remain <= thre*(i-P+1):
                ans+=1
print(ans)

Submission status: Wrong Answer

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

    def is_ok(mid):
        if mid <= P:
            return False  # 採用可能
        if A[mid] + M < A[P-1]:
            return True  # 採用不可能
        votable = M + (P-1) * M + (N - mid - 1)*M
        for i in range(P-1, mid):
            votable += max(0, A[mid] + M - A[i])
        if M*V <= votable:
            return False
        else:
            return True

    def binary_search_meguru():
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right
    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A = np.array(sorted(A,reverse=True))
ans = P
x = A[P-1]
y = N-1
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break

if y==N-1:
  print(N-1)
  exit()
z = sum(A[P-1:y])
for i in range(y,N):
  a = A[i]
  d = a+M
  if x<=d:
    b = N-i+P-1
    c = M*(V-b)
    e = z+c
    f = d*(i-P+1)
    if f>=e:
      ans+=1
      
  z+=a
print(ans)

Submission status: Wrong Answer

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

# sum_=[0]*N
# sum_[0]=A[0]
# for i in range(1,N):
#     sum_[i]=(sum_[i-1]+A[i])
sum_=[0]
cnt=0
for i in range(N):
  # 累積和
  cnt += A[i]
  sum_.append(cnt)

for i in range(P,N):
    thre=A[i]+M
    if thre < A[P-1]:
        continue

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    # elif sum(A[P-1:i])+M*remain <= thre*(i-1-(P-1)+1):
    elif sum_[i-1]-sum_[P-2]+M*remain <= thre*(i-P+1):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
l=sorted(list(map(int,input().split())))
l=l[::-1]
#初めから上位p位に入っているものは自動的に採用
#print(l)
if p+v<=n:
  ans=p
  for i in range(p,n):
    if i<n-v:
      if l[i]+m>=l[p-1]:
        ans+=1
      else:
        break
    elif i>=n-v:
      if i-n-v+1>p:
        break
      if l[i]+m>=l[max(0,p-1-(i-n+v))]:
        ans+=1        
  print(ans)
else:
  ans=p
  for i in range(p,n):
    if i-n-v+1>p:
        break
    #print(l[i]+m,l[max(0,-v-1-(i-p))])
    if l[i]+m>=l[max(0,-v-1-(i-p))]:
      ans+=1
  print(ans)

Submission status: Wrong Answer

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

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

for i in range(P,N):
    thre=A[i]+M
    if thre < A[P-1]:
        continue

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    # elif sum(A[P-1:i])+M*remain <= thre*(i-1-(P-1)+1):
    elif sum_[i-1]-sum_[P-2]+M*remain <= thre*(i-P+1):
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A = np.array(sorted(A,reverse=True))
ans = P
x = A[P-1]
y = N-1
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break

if y==N-1:
  print(N)
z = sum(A[P-1:y])
for i in range(y,N):
  a = A[i]
  d = a+M
  if x<=d:
    b = N-i+P-1
    c = M*(V-b)
    e = z+c
    f = d*(i-P+1)
    if f>=e:
      ans+=1
      
  z+=a
print(ans)