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: Accepted

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()

    # 二分探索で探す
    left = -1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2

        if N-P <= mid:
            right = mid
            continue

        if A[mid]+M < A[N-P]:
            left = mid
            continue

        # 入れられても構わない票をカウントする
        tot = 0
        for i in range(mid+1, N-P+1):
            tot += A[mid]+M-A[i]
        tot += (P-1)*M
        tot += mid*M
        tot += M

        if tot < M*V:
            left = mid
            continue
        else:
            right = mid
            continue

    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: Accepted

Solution code:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
S = [0]
for i in range(N-P+1):
    S += [S[-1]+A[i]]
a = P-1
for i in range(N-P+1):
    if A[i]+M>=A[N-P] and A[i]*(N-P-i)-(S[-1]-S[i+1])>=M*(V-N):
        a += 1
print(a)

Submission status: Accepted

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

S = [0]
for i in range(N-P+1):
    S.append(S[-1]+B[i])

ans = P-1

for i in range(N-P+1):
    if B[i]+M-B[-1]<0:
        continue
    if B[i]*(N-P-i)-(S[-1]-S[i+1])+M*(N-P)>=max(M*(V-P),0):
        ans += 1

print(ans)

Submission status: Accepted

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) and B[P-1]<=B[i]+M:
        count+=1
print(count)

Submission status: Accepted

Solution code:
# 解説を見た

def solve(N: int, M: int, V: int, P: int, A: 'list[int]') -> int:
    """
    入れてよい票 < M*V
        M*V投票するとjを超えるスコアを持つ問題数がP以上になり、不可能

    入れてよい票 >= M*V
        可能

        次の条件を満たせば可能といえる
        # 各問題への投票数は許容範囲内
        # すべてのjudgeがV投票
        # すべてのjudgeが同じ問題に2度以上投票していない
        投票してよい問題abc...zを
        許容される投票数だけ連続させた列(最大M=すべてのjudgeが投票した場合)
        aaaabbbcc...z
        仮定より長さMV以上なので,
        冒頭の区間(長さMV)に対し,judgeを0...M-1,0...M-1,...と割り当てることができる
        この割り当ては,3つの条件を満たす
    """

    from itertools import accumulate

    def is_ok(j):
        if j < P:
            return True
            # P位以内にM回加点

        X = A[j] + M  # 加点後のj位のスコアX
        if X < A[P]:
            return False
            # A[j]にM回加点、P位に加点なしでも勝てん

        return (j - P) * X - (acc[j - 1] - acc[P - 1]) >= M * (V - (P + N - j))
        # return (P - 1 + 1 + N - j) * M + sum(X - A[k] for k in range(P, j)) >= M * V
        # (P-1)位以内,j位以降にM回加点
        # P位～(j-1)位は,加点後のj位を超えない範囲で加点
        # X>=A[P]>=A[k]
        # なので,各kに対し,0点以上加点できる
        # 移項して,累積和でオーダーを落とした

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

    *A, = sorted(A, reverse=True)
    A = [0] + A  # 0-indexed -> 1-indexed
    acc = tuple(accumulate(A))
    return binary_search()


def main():
    import sys
    input = sys.stdin.readline

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve(N: int, M: int, V: int, P: int, A: 'list[int]') -> int:
    from itertools import accumulate

    def is_ok(j):
        from math import ceil

        X = A[j]
        always_add = (P - 1) + 1 + j  # この区間は、すべてのjudgeから加算を受ける

        if V <= always_add:
            return A[N - P] <= X + M

        flat_distribute_block = N - always_add  # A[j]+Mを超過しないように分配する区間
        count_per_judge = V - always_add  # 各judgeが加点する問題数

        block_sum = acc[N - P + 1] - acc[j + 1]  # [j+1,N-P](0-indexed)
        without_exceed = A[N - P] * flat_distribute_block - block_sum  # A[N-P]を超過せずに処理できる投票数
        vote_piled_up = M * count_per_judge - without_exceed

        if vote_piled_up <= 0:
            return A[N - P] <= X + M
        else:
            to_add = ceil(vote_piled_up / flat_distribute_block)
            return A[N - P] + to_add <= X + M

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

    *A, = sorted(A)
    acc = (0,) + tuple(accumulate(A))
    return N - binary_search()


def main():
    import sys
    input = sys.stdin.readline

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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 = LI()
    A.sort()

    if(check(0, N, M, V, P, A)):
        print(N)
        return

    r = N - 1
    l = 0
    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: Accepted

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 = LI()
    A.sort()

    if(check(0, N, M, V, P, A)):
        print(N)
        return

    # 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)
    r = N - 1
    l = 0
    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)
    return
    # 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: Accepted

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 = LI()
    A.sort()

    if(check(0, N, M, V, P, A)):
        print(N)
        return

    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
    # 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: Accepted

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 main():
    N, M, V, P = MI()
    A = MI()
    A = sorted(A, reverse=True)
    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, count) >= (minp - A[i]) * count - td and minp <= A[i] + M:
            result += 1
            tpcount += 1
            tptd += minp - A[i]
            pre = A[i]
        else:
            break
    print(result + P)
    # N, M, V, P = 10**5, 10*19, 10**4, 10**4
    # A = [i for i in range(N)]
    # MAP = {}
    # A = sorted(A, reverse=True)
    # AH = A[:P]
    # AH_min = AH[-1]
    # AT = []
    # cur = 0
    # sent_c = 0
    # for i in range(P, N):
    #     if AH_min == A[i]:
    #         sent_c += 1
    #     # else:
    #     if A[i] not in MAP:
    #         MAP[A[i]] = cur
    #     cur += 1
    #     AT.append(A[i])
    # print(AH, AT)
    # # print('M=', M, 'V=', V)
    # ans = len(AH)
    # AT_len = len(AT)
    # # print(AT, MAP)
    # # show(len(AT), V - len(AH) + 1)

    # _V = V - len(AH) + 1
    # # print('_V', _V, V, AH_min)
    # for i in range(AT_len):
    #     if AH_min == AT[i]:
    #         ans += 1
    #     elif AH_min <= (AT[i] + M):
    #         remaining = AT_len - (MAP[AT[i]] + 1)
    #         print('AT[i]', AT[i], 'ans=', ans, 'i=', i, 'remain=', remaining +
    #               1, 'V=', _V, 'AH_MIN=', AH_min, 'MAP=', MAP[AT[i]])
    #         if remaining + 1 >= _V:
    #             ans += 1

    # print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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+=max(min(M+A[N-i]-point,M),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: Accepted

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

pps = 0
con = P

for i in range(P,N):
  #P以降でi番目に大きい数を加算
  pps += A[i - 1]

  #xの上限が順位に入らない
  if A[i] + M < A[P - 1]:
    break
  #点数をいくら振り分けてもいいスコアの数
  fv = min(P - 1 + N - i, V)
  #左辺第二項は、P以降とi以前の、点数の振り分け可能数に上限がある数
  #左辺は振り分けた後にA[i]がP入りを果たせる区間の総和の上限を示す
  #右辺第一項は、振り分け可能数に上限がある数の総和
  #右辺第二項は、振り分けないといけない数の残り
  #右辺は、点数を振り分けた後の値の区間の総和を示すため、
  #右辺が左辺を上回った場合、ループは終了となる
  if (A[i] + M) * (i - P + 1) < pps + M * (V - fv):
    break
  con += 1
  
print(con)

Submission status: Accepted

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+1
    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: Accepted

Solution code:
import math
import sys

m=10**9 + 7 
sys.setrecursionlimit(1000010)
(N, M,V,P) = list(map(int,input().split()))
A  = sorted(list(map(int,input().split())),reverse=True)
#print(N,M,V,P)
#print(A)

B = A[P-1:]
V = V -P + 1
N = N - P + 1
# print(N ,M,V,1)
#print(B)

L = B[0]
pb = B[0]
pi = 0
Z = 0
for i in range(1,N):
    # print("# ",i,B[i])
    if pb == B[i]:
        # the same value
        # print("The same")
        continue
    # We had change 
    Z = Z + (L - pb)* (i -pi)
    pb = B[i] # New Value
    pi = i
    # print("Z",Z)
    if B[i] + M < L: # Cannto be candidate any more
        print(P-1+i)
        exit(0)
    if N -i >=  V:
        # It can be canditate
        next
    # Have to check in detail
    capacity = Z + i * (B[i] + M - L ) + (N-i) * M
    # print(V * M ,capacity, Z, i * (B[i] + M - L ), (N-i) * M)
    if capacity < V * M:
        print(P -1 + i)
        exit(0)
print(P+N-1)

Submission status: Accepted

Solution code:
import sys

n, m, v, p, *a = map(int, sys.stdin.read().split())
a.sort(reverse=True)

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

def main():
    lo = -1
    hi = n
    while lo + 1 < hi:
        i = (lo + hi) // 2
        if possible(i):
            lo = i
        else:
            hi = i
        
    return lo + 1

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

Submission status: Accepted

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-1:
            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: Accepted

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]+M*remain <= thre*(i-P+1):
                ans+=1
print(ans)

Submission status: Accepted

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
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break

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: Accepted

Solution code:
import sys
from bisect import bisect_right, bisect_left
input = sys.stdin.readline
n, m, v, p = [int(x) for x in input().strip().split()]
araw = sorted([int(x) for x in input().strip().split()])
a = list(reversed(araw))

def f(x, n, m, v, p, a, araw):
    c = p - (n - bisect_right(araw, a[x-1]+m)) - 1
    if c < 0:
        return False
    vote = m * (v - 1)
    thr = a[x-1] + m
    for i, aa in enumerate(a, start=1):
        if vote <= 0:
            break
        if i == x:
            continue
        if aa > thr:
            vote -= m
        elif aa == thr:
            if c:
                vote -= m
                c -= 1
        elif thr - aa < m:
            if c:
                vote -= m
                c -= 1
            else:
                v_ = min(vote, thr - aa, m)
                vote -= v_
        else:
            vote -= m
    return vote <= 0

x = 0
l = 1
r = n + 1
while l < r:
    x = (l + r) // 2
    if f(x, n, m, v, p, a[:], araw):
        l = x + 1
    else:
        r = x
print(l-1)

Submission status: Accepted

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

A.sort(reverse = True)

l = P-1
r = N

while r-l > 1:
    m = (r + l) // 2
    last = M + A[m]
    s = 0
    for i in range(P-1, N):
        if i == m:
            continue
        s += min(max(last - A[i],0), M)
    if s >= M * (V - P) and last >= A[P-1]:
        l = m
    else:
        r = m
        
print(l+1)

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
ans = p
c = [0]
cnt = 0
for i in range(n):
  # 累積和
  cnt += a[i]
  c.append(cnt)
  
from bisect import bisect_right
for i in range(p,n):
  h = a[i]+m
  free = v - (p-1) - (n-i)
  if free >= 0 and h >= a[p-1]:
    d = h * (i-p+1) - (c[i]-c[p-1]) # 余裕
    if d >= free*m:
      ans += 1
  else:
    if h >= a[p-1]:
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(i):
    if i<=p:
        return True
    if a[i]+m < a[p]:
        return False
    q = v-n+i-p
    #ddprint("foo {} call q {}".format(i,q))
    if q<=0:
        return (a[i]+m >= a[p])
    ret = (i-p)*(a[i]+m) >= acc[i-1]-acc[p-1]+m*q
    #ddprint("i {} p {} ai {} m {} ap {} acm {} acp {} q {}".format(i,p,a[i],m,a[p],acc[i-1],acc[p-1],q))
    #ddprint("foo {} returns {}".format(i,ret))
    return ret

n,m,v,p = inm()
a = inl()
a.sort(reverse=True)
a[0:0] = [0] # a1..an
acc = [0]*(n+1)
for i in range(1,n+1):
    acc[i] = acc[i-1]+a[i]
ddprint(a)
ddprint(acc)
mn = p
mx = n+1
while mx-mn>=2:
    #ddprint("loop mn {} mx {}".format(mn,mx))
    mid = (mn+mx)//2
    if foo(mid):
        mn = mid
    else:
        mx = mid
print(mn)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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

def check(x):
    if (N-x)<=P:
        return True
    x_score = A[x] + M
    if (V-x-P) <= 0:
        return(A[N-P]<=x_score)

    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 False
    return True

def main():
    if(check(0)):
        print(N)
        return

    isOK = N-1
    isNG = 0
    while(isOK-isNG>1):
        mid = (isOK+isNG)//2
        if(check(mid)):
            isOK = mid
        else:
            isNG = mid
    print(N-isOK)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

left = 0
right = n - p -1

while right - left >=0:
    mid = (left + right) // 2
    if a[mid] + m < a[n - p]:
        left = mid + 1
    else:
        j = v - (mid + 1 + p - 1)
        if j <= 0:
            right = mid-1
        else:
            sum = 0
            for k in range(mid + 1, n - p + 1, 1):
                if m + a[mid] - a[k] < 0:
                    left = mid + 1
                    break
                sum += a[mid] + m - a[k]
                if sum >= j * m:
                    right = mid-1
                    break
                if k == n - p:
                    left = mid + 1

print(n-left)

Submission status: Accepted

Solution code:
def main():
    n, m, v, p = [int(i) for i in input().split()]
    a = sorted([int(i) for i in input().split()], reverse=True)

    def check(x):
        """スコアxの問題が採用されるかどうかを真偽値で返す"""
        # m人全員が投票してもp番目に届かない場合は採用されない
        if x + m < a[p - 1]:
            return False
        # 総投票数
        mv = m * v
        mv -= m * len(a[:p-1])  # p-1番目までの上位全員にm人が投票
        for score in a[p-1:]:
            mv -= min(m, x + m - score)  # p番目以降の全員がx+mになるまで投票
        # mvが0以下でない場合、p番目以降にxより高い最終スコアがあるため採用されない
        return mv <= 0

    left, right = 0, n
    while left < right:
        mid = (left + right) // 2
        if check(a[mid]):
            left = mid + 1
        else:
            right = mid
    print(right)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m, v, p = MAP()
a = LIST()
a = sorted(a, reverse=True)

def hantei(i):
    if i < p: return True
    if a[p-1] > a[i] + m: return False
    if ((i-p+1)*(a[i]+m)-sum(a[p-1:i]))+m*(p-1+n-i) < m*v: return False
    return True

if hantei(n-1):
    print(n)
    sys.exit()
    
right = n-1
left = 0

while right-left > 1:
    mid = (right+left)//2
    if hantei(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m, v, p = MAP()
a = LIST()
a = sorted(a, reverse=True)

def hantei(i):
    if i < p: return True
    if a[p-1] > a[i] + m: return False
    if ((i-p+1)*(a[i]+m)-sum(a[p-1:i]))+m*(p-1+n-i) < m*v: return False
    return True

def check(x):
    if (n-x)<=p:
        return True
 
    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

if hantei(n-1):
    print(n)
    sys.exit()
right = n-1
left = 0

while right-left > 1:
    mid = (right+left)//2
    if hantei(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
a=sorted(list(map(int,input().split())), reverse=True)
ps=0;ans=p
for i in range(p,n):
  ps+=a[i-1]
  if a[i]+m<a[p-1]: break
  hv = min(p-1+n-i, v)
  if (a[i]+m)*(i-p+1)<ps+m*(v-hv): break
  ans+=1
print(ans)

Submission status: Accepted

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
def solve(x):
    if a[x] + m < a[p-1]:
        return False
    now = 0
    for i in range(n):
        if i >= x:
            now += m
        elif i < p-1:
            now += m
        else:
            now += a[x] + m - a[i]
    if now >= m*v:
        return True
    else:
        return False

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

print(ok+1)