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:
import sys

read = sys.stdin.read
N, M, V, P, *A = map(int, read().split())

A += [10 ** 10]
A.sort(reverse=True)
left = P
right = N + 1
# i番目の問題が採用される可能性があるか否や
e = tuple(enumerate(A))
while right - left > 1:
    mid = (right + left) // 2
    score = A[mid] + M
    if score < A[P]:
        right = mid
        continue
    s = M * (V - P)
    for idx, i in e[P:]:
        if mid == idx:
            continue
        if i + M <= score:
            s -= M
        else:
            s -= score - i

    if s <= 0:
        left = mid
    else:
        right = mid

print(left)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, m, v, p = LI()
A = LI()
A.sort()
def bi(x):
    if A[x] + m < A[-p]:
        return 0
    if x + p >= v:
        return 1
    ret = (x + p) * m
    l = x + 1
    r = n - p + 1
    for i in range(l, r):
        ret += A[x] + m - A[i]
        if ret >= v * m:
            return 1
    return 0


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


print(n - ok)

Submission status: Accepted

Solution code:
import bisect

N, M, V, P = map(int, input().split())
A = list(map(int, input().split())) + [-M-1]
A.sort()

Ap = A[-P] # 初期状態でP番目に大きい点数
I = N + 2 - P
right = N + 1 - P
left = 0

while left + 1 < right:
  mid = (left + right) // 2
  b = A[mid] + M
  if b < Ap:
    left = mid
  else:
    v = V - (bisect.bisect_right(A, A[mid])-1) - (P-1)
    if v <= 0:
      right = mid
    else:
      mv = M*v
      for i in range(mid+1, I):
        if A[i] == A[mid]:
          continue
        mv -= b - A[i]
        if mv <= 0:
          break
      if mv <= 0:
        right = mid
      else:
        left = mid

print(N + 1 - right)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import deque
import bisect

def main():
    N,M,V,P = map(int,input().split())
    a = sorted(list(map(int,input().split())),reverse=True)
    r = a[P-1]
    l = a[P-1]-M-1
    
    while r-l > 1:
        mid = (r+l)//2
        count = 0
        for x,num in enumerate(a):
            if x < P-1:
                count += M
            else:
                if num > mid:
                    count += max(mid+M-num,0)
                else:
                    count += M
        if count >= M*V:
            r = mid
        else:
            l = mid

    a.reverse()     
    print(N-bisect.bisect_left(a,r))
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

n,m,v,p=map(int,input().split())
arr=list(map(int,input().split()))
arr=sorted(arr)
acum=[0]
for i in range(n):
  acum.append(acum[-1]+arr[i])
ans=0
for i in range(n):
  flag=False
  cnt=bisect.bisect_right(arr,arr[i])
  cnt2=bisect.bisect_right(arr,arr[i]+m)
  tv=v-cnt-min((p-1),n-cnt)
  rem=-1
  if cnt2<=n-p:
    ans+=0
  else:
    if tv<=0:
      ans+=1
      flag=True
    else:
      rem=acum[min(cnt2,n-(p-1))]-acum[cnt]
      if (arr[i]+m)*(min(cnt2,n-(p-1))-cnt)-rem>=m*tv:
        ans+=1
        flag=True
      else:
        ans+=0
print(ans)

Submission status: Accepted

Solution code:
N, M, V, P = map(int, input().split())
A = [int(c) for c in input().split()]
A.sort(reverse=True)
m = A[P-1]
l = -1
r = N
while l+1<r:
  s = (l+r)//2
  c = A[s]
  if m>c+M:
    r = s
    continue
  if s<P:
    l = s
    continue
  x = 0
  for i in range(N):
    if i<P-1:
      x += M
      continue
    if i>=s:
      x += M
      continue
    x += min(M,A[s]+M-A[i])
  if x>=M*V:
    l = s
  else:
    r = s
print(l+1)

Submission status: Accepted

Solution code:
from collections import Counter
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
l = 0
r = n
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r-1:
    mid = (l+r)//2
    if mid<=p:
        l = mid
        continue
    if a[mid]+m<tmp:
        r = mid
    else:
        thresh = a[mid]+m 
        amari = (v-p)*m
        for i in range(p-1,n):
            if i==mid:
                continue
            amari-=min(m,thresh-a[i])
        if amari<=0:
            l = mid
        else:
            r=mid
print(l+1)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

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

A.sort(reverse=True)
cumA = [A[0]]
for i in range(1,N):
    cumA.append(cumA[-1]+A[i])

ans = P
if V < P:
    for i in range(P,N):
        if A[P-1] <= A[i]+M:
            ans += 1
else:
    for i in range(P,N):
        if A[i]+M < A[P-1]:
            continue
        cum = cumA[i-1]-cumA[P-2] if P >= 2 else cumA[i-1]
        cap = (i-P+1)*(M+A[i]) - cum + M*(N-i-1)
        if cap >= M*(V-P):
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())))
if p >= v:
  print(sum([1 for b in a if b+m >= a[n-p]]))
else:
  s = p-1
  t = sum(a[:(n-p+1)])
  for i in range(n-p+1):
    t -= a[i]
    if a[i]+m >= a[n-p] and (a[i]+m)*(n-p-i) - t >= (v-p-i)*m:
      s += 1
  print(s)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	ans = float("inf")
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M and A[mid] + M >= A[N - P]:
			ans = min(ans, mid)
			right = mid - 1
		elif mid >= N - P:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return N - ans

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

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

def is_ok(i):
    if i<0: return False
    cur,rival = A[i]+M, A[N-P]
    if cur < rival: return False
    rem_p = V - P - i
    if rem_p <= 0: return True
    j = 0
    for k in range(i+1,N-P+1):
        z = min(M, cur-A[k])
        j += z
        if j >= rem_p * M: return True
    return False

ok = N-P
ng = -1
while ok-ng > 1:
    m = (ok+ng)//2
    if is_ok(m):
        ok = m
    else:
        ng = m

print(N-ok)

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
B=[0]
for i in range(n):
  B.append(B[-1]+A[i])
#print(B)
ok = -1
ng = n
if p>=1:
  while ng-ok > 1:
    mid = (ok+ng) // 2 # 平均(小数切り捨て)
    #print(mid)
    if mid<p:
      ok=mid
      #print(0)
    elif n-(mid+1)+p>=v:
      if A[p-1]<=A[mid]+m:
        ok=mid
        #print(1)
      else:
        ng=mid
        #print(2)
    else:
      if A[mid]+m>=A[p-1]:
        a=m*(v-n-p+mid+1)
        b=A[mid]+m
        q=p-1
        if (mid+1-p)*b-(B[mid]-B[q])>=a:
          ok=mid
          #print(3)
        else:
          ng=mid
          #print(4)
      else:
        ng=mid
        #print(5)
  print(ok+1)

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(i):

    B=[A[m] for m in range(N-(P-1)) if m!=i]

    C=A[i]+M
    a=V-P

    if C<A[-P]:
        return(0)
    else:
        if a>0:
            Votenum=a*M
            for b in B:
                Votenum-=min(C-b,M)
                if Votenum<=0:
                    return(1)

            return(0)
        else:
            return(1)




if main(0):
    print(N)
    exit()
st=0
end=N-P+1

while 1:
    a=(st+end)//2
    if main(a):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(st):
    print(N-st)
else:
    print(N-end)

Submission status: Accepted

Solution code:
N,M,V,P=map(int,input().split())
import numpy as np
A=np.array(sorted(map(int,input().split())))
ng,ok=-1,N-P+1
while ng+1<ok:
    t=(ng+ok)//2
    if A[t]+M<A[-P] or np.sum(np.minimum(M,A[t]+M-A[t+1:N-P+1]))<M*(V-P-t):
        ng=t
    else:
        ok=t
print(N-ok)

Submission status: Accepted

Solution code:
n,m,v,p = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort(reverse=True)
ans = 0
trash = 0
for i in range(n):
    if i+1 <= p:
        ans += 1
    else:
        if lis[i] + m >= lis[p-1]:
            if (lis[i]+m)*(i-(p-1))-trash >= m * (v-(p-1)-(n-i)):
  #                 print(lis[i]+m,i-(p-1)-trash,m*(v-(p-1)-(n-i)))
                ans += 1
    if i+1 >= p:
        trash += lis[i]
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = -1
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    if indR<N-P+1:
        low = mid
        continue
    tot = M*V
    i = indL
    while i<N-P+1:
        if tot-(mid-A[i])<0:break
        tot -= mid-A[i]
        i += 1
    if i<N-P+1 or 0<=tot<=M*(P-1+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Accepted

Solution code:
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = [0]*(n+1)
for i in range(n):
  b[i+1] = b[i] + a[i]

def judge(x):
  if x >= n-p: return True
  if a[x] + m < a[n-p]: return False
  safe = m*(n-1) + a[x]*(n-p-x) - b[n-p+1] + b[x+1]
  return safe >= m*(v-1)

ok = n-p
ng = -1
while ok-ng > 1:
  mid = (ok+ng)//2
  if judge(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,m,v,p = LI()
    a = sorted(LI())
    pi = n-p
    pv = a[pi]

    def f(i):
        t = a[i] + m
        if pv > t:
            return True
        mv = m*v-m
        for j in range(n):
            if j == i:
                continue
            aj = a[j]
            if j > pi:
                mv -= m
            elif aj <= t:
                mv -= min(m, t - aj)
            else:
                mv -= m
        return mv > 0

    r = bs(f,0,n-1)

    return n - r


print(main())

Submission status: Accepted

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
# https://atcoder.jp/contests/abc145/tasks/abc145_e
# E - All-you-can-eat
"""

"""


def good(i):
    tv = A[i] + M
    max_used = (i + 1 + (P - 1)) * M
    free = M * V - max_used

    for j in range(i + 1, N - P + 1):
        if A[j] > tv:
            return 0
        free -= tv - A[j]

    return free <= 0


N = gi()
M = gi()
V = gi()
P = gi()
A = [0] * N
for i in range(N):
    A[i] = gi()
A.sort()

#print(A)

l = 0
h = N - 1

while l < h:
    mid = (l + h) // 2
    if good(mid):
        h = mid
    else:
        l = mid + 1

print(N - l)

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
ap=a[p-1]
iok=p-1
ing=n
while ing-iok>1:
  x=(ing+iok)//2
  if x<=p-1:
    iok=x
  else:
    if a[x]+m<ap:
      ing=x
    else:
      if (p-1+n-x)*m+(x-(p-1))*(a[x]+m)-sum(a[p-1:x])>=m*v:
        iok=x
      else:
        ing=x
print(iok+1)

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

    if v-1 <= p-2:
        if a[mid]+m >= a[p-1]:
            ok = mid
        else:
            ng = mid
    else:
        if a[mid]+m < a[p-1]:
            ng = mid
        else:
            r = v-p
            cnt = 0
            for i in range(p-1,n):
                if i == mid:
                    continue
                cnt += min(m,a[mid]+m-a[i])
            if cnt >= r*m:
                ok = mid
            else:
                ng = mid
print(ok+1)

Submission status: Accepted

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

A.sort()
A = A[::-1]
#print("A:", A)

left = 0
right = N

while left + 1 < right:
  mid = (left + right) // 2
  Amid = A[mid]
  rest = M * V - M * P
  start = P if mid + 1 <= P else P - 1
  
  flag = 0
  for i in range(start, N):
    if mid == i:
      continue
    else:
      if A[i] > Amid + M:
        flag = 1
        break
      else:
        rest -= min(M, Amid + M - A[i])
        
  if rest > 0 or flag:
    right = mid
  else:
    left = mid
#print(left)

answer = 0
Aleft = A[left]
for i in range(N):
  if A[i] >= Aleft:
    answer += 1
    
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
# mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,v,p = inpm()
    a = inpl()
    a.sort(reverse=True)
    ok = 0
    ng = n
    while ng-ok >1:
        mid = (ok+ng)//2
        if mid+1 <= p:
            ok = mid
        elif a[p-1] > a[mid]+m:
            ng = mid
        else:
            key = 0
            cnt = (p)*m + (n-mid-1)*m
            for i in range(mid-1,p-2,-1):
                if a[i] > a[mid]+m:
                    ng = mid
                    key = 1
                    break
                cnt += min(a[mid]-a[i]+m,m)
            if key:
                break
            if cnt >= m*v:
                ok = mid
            else:
                ng = mid
    print(ok+1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

N, M, V, P, *A = map(int, open(0).read().split())

A.sort(reverse=True)

S = list(accumulate(A)) + [0]

def is_ok(md):
    return (A[md] + M < A[P - 1]) or (A[md] + M) * (md - P + 1) - (S[md - 1] - S[P - 2]) < M * (V - (P - 1) - (N - md))

ng, ok = P - 1, N
while ok - ng > 1:
    md = (ok + ng) // 2
    if is_ok(md):
        ok = md
    else:
        ng = md

print(ok)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


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

    # 降順
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)
    L = M*(V-N)-acc[P-1]
    K = A[P-1]-M
    while right - left > 1:
        mid = (right + left)//2
        cap = (mid-P+1)*A[mid] - acc[mid]
        if A[mid] < K or cap < L:
            right = mid
        else:
            left = mid
    print(right)

    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:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


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

    ans = 0

    # 降順
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)
    while right - left > 1:
        mid = (right + left)//2
        if A[mid]+M < A[P-1]:
            right = mid
            continue

        cap = M*N+(mid-P+1)*(A[mid]) - acc[mid] + acc[P-1]
        if cap >= M*V:
            left = mid
        else:
            right = mid
    print(left+1)

    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:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
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 LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m,v,p=LI()
a=LI()
b=sorted(a)[::-1]

def check(k):
    tot=m*v
    if k<=p-1:
        return True
    if b[p-1]>b[k]+m:
        return False
    tot-=m*p
    mx=b[k]+m
    for i in range(p-1,n):
        if i==k:
            continue
        tot-=min(max(0,mx-b[i]),m)

    if tot<=0:
        return True
    else:
        return False
        
l,r=0,n

while r-l>1:
    mid=(l+r)//2
    if check(mid):
        l=mid
    else:
        r=mid

ok=b[l]
ans=sum([1 if i>=ok else 0 for i in b])
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N,M,V,P = map(int,input().split())
A = np.sort(list(map(int,input().split())))[::-1]

Ap = A[P-1]
iOK = P-1
iNG = N
while iOK+1 < iNG:
    x = (iOK+iNG)//2
    if x <= P-1:
        iOK = x
    elif Ap - A[x] > M:
        iNG = x
    elif (P-1)+(N-x) >= V:
        iOK = x
    elif (A[x]+M)*(x-P+1)-np.sum(A[P-1:x]) >= M*(V-P+1-N+x):
        iOK = x
    else:
        iNG = x

ans = iOK + 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


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

    ans = 0

    # 降順
    A.sort(reverse=True)

    acc = [0]+list(accumulate(A))

    for i in range(N):
        # ソート後の冒頭P問は大きいので可
        if i < P:
            ans += 1
            continue
        # M人が投票してもP番目のスコアに届かないなら無駄。
        if A[i]+M < A[P-1]:
            continue

        # 対象iがP問目として選ばれるために
        # 許容可能な投票数と、実際の投票数を比較する。
        cap = 0
        # 始めのP-1問にはM人が投票してよい
        cap += M*(P-1)
        # 後ろのN-i問(i, i+1, ..., N-1)にはM人が投票して良い
        cap += M*(N-i)
        # P問目からi-1問目までは、A[i]+Mを超えない範囲で投票して良い
        # \sum_{j = P-1}^{i-1} A[i]+M-A[j]
        # = (i-P+1)*(A[i]+M) - \sum_{j=P-1}^{i-1}A[j]
        cap += (i-P+1)*(A[i]+M)
        # accは始めに0を加えているので、インデックスが異なるので注意
        # 数列(0-index)のi-1番目までの和はacc[i](0-index)
        cap -= acc[i] - acc[P-1]
        if cap >= M*V:
            ans += 1
    print(ans)

    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:
# -*- coding: utf-8 -*-

import sys
from bisect import bisect_right

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bisearch_min(mn, mx, func):
    """ 条件を満たす最小値を見つける二分探索 """

    ok = mx
    ng = mn
    while ng+1 < ok:
        mid = (ok+ng) // 2
        if func(mid):
            # 下を探しに行く
            ok = mid
        else:
            # 上を探しに行く
            ng = mid
    return ok

def check(m):
    # 元々P番目以内なのでOK確定
    if m >= N - P:
        return True
    # 自分に全投票した最善の状態
    target = A[m] + M
    # 残りの票数合計
    total = M * (V-1)
    # 絶対勝てないやつがP個以上あればNG確定
    r = bisect_right(A, target)
    if r <= N - P:
        return False
    # 元々自分より下に全投票(そうしても勝てるから)
    total -= M * m
    # P番目ギリギリに入れればいいので、関係ない上位層にも全投票
    total -= M * (P-1)
    # ボーダー上のものに、自分との差分ギリギリ(同率)まで投票
    for i in range(m+1, N-P+1):
        total -= target - A[i]
    # 票数が使い切れていればOK
    return total <= 0

N, M, V, P = MAP()
A = LIST()

A.sort()
res = bisearch_min(-1, N-1, check)
ans = N - res
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,v,p,*a=map(int,open(0).read().split())
a=sorted(a)[::-1]
ok=p-1
ng=n
while ng-ok>1:
  mid=(ok+ng)//2
  c=a[mid]+m
  s=f=0
  for t in a[p-1:mid]:
    if t>c:break
    s+=c-t
  else:f|=(p-1+n-mid)*m+s>=v*m
  if f:ok=mid
  else:ng=mid
print(ok+1)

Submission status: Accepted

Solution code:
def nibutan(L):
  ok = len(L)
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if nasu(mid, L):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n, L):
  p = L[n] + M
  if p < L[K]:
    return False
  m = (V - 1 - (n + P - 1)) * M
  if m <= 0:
    return True
  for i in range(n + 1, K + 1):
    m -= p - L[i]
    if m <= 0:
      return True
  return False

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

A.sort()
K = N - P
T = A[K]
print(N - nibutan(A))

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    left, right = -1, n

    while left+1 < right:
        i = (left+right)//2

        if A[i]+m < A[n-p]:
            left = i
            continue

        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            right = i
        else:
            left = i

    return str(n-right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np

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

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

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

Submission status: Accepted

Solution code:
import sys
import math
import numpy as np

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

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

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