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
from collections import defaultdict
readline = sys.stdin.buffer.readline
#sys.setrecursionlimit(10**8)


def geta(fn=lambda s: s.decode()):
    return map(fn, readline().split())


def gete(fn=lambda s: s.decode()):
    return fn(readline().rstrip())


def main():

    N, M, V, P = geta(int)
    A = [-10**15] + list(geta(int))
    A.sort()

    target = A[N - P + 1]

    def c(x):
        """
        return True iff Problem x has chance to be chosen 
        """
        if x >= N - P + 1:
            return True

        v_left = M * max(V - x - P + 1, 0)

        Ax = A[x] + M
        if Ax < A[N - P + 1]:
            return False

        ok = False
        for i in range(x + 1, N - P + 1 + 1):
            ad = min(M, Ax - A[i])
            v_left -= ad
            if v_left <= 0:
                ok = True
                break

        return ok

    left, right = 0, N
    while left + 1 < right:
        middle = (left + right) // 2
        if c(middle):
            right = middle
        else:
            left = middle

    print(N - right + 1)


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(reverse=True)

higher = a[p-1]
for i in range(p,n):
    if(a[i] == a[i-1]):
        higher += a[i]
        continue

    if(a[p-1]- a[i] > m):
        print(i)
        exit()

    if(higher - a[i]*(i-p+1) > min(n-v,i-p+1)*m):
        print(i)
        exit()

    higher += a[i]

print(n)

Submission status: Accepted

Solution code:
# 上からx問目を選ぶことができるか二分探索
# x <= Pであれば必ず選べる
# A_x + M < A_Pであれば必ず選べない
# それ以外の場合
# A_xには必ず投票するのでA_x + Mが基準点
# A_xがP位である必要がある
# 上位P - 1位までにはM票投票して良い
# P + 1位以下に対しては、A_x + Mまでは投票して良い
# この投票して良い数がM * Vを上回ればOK

import sys
readline = sys.stdin.readline

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

# 最初の時点で上位P位の点数を求めておく
border = A[P - 1]

# 大きい順に並べる

ok = -1
ng = N

def isOk(x):
  # 上からx番目を選ぶことが出来るか
  if (x + 1) <= P:
    return True
  if A[x] + M < border:
    return False
  # 基準点
  base = A[x] + M
  
  # 上位P - 1には必ず投票して良い
  vote = (P - 1) * M
  # P位以下には、baseを超えないように投票して良い
  for i in range(P - 1,len(A)):
    limit = max(base - A[i], 0)
    can = min(limit, M)
    vote += can
  if vote >= M * V:
    return True
  return False

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

Submission status: Accepted

Solution code:
# 上からx問目を選ぶことができるか二分探索
# x <= Pであれば必ず選べる
# A_x + M < A_Pであれば必ず選べない
# それ以外の場合
# A_xには必ず投票するのでA_x + Mが基準点
# A_xがP位である必要がある
# 上位P - 1位までにはM票投票して良い
# P + 1位以下に対しては、A_x + Mまでは投票して良い
# この投票して良い数がM * Vを上回ればOK

import sys
readline = sys.stdin.readline

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

# 最初の時点で上位P位の点数を求めておく
border = A[P - 1]

# 大きい順に並べる

ok = -1
ng = N

def isOk(x):
  # 上からx番目を選ぶことが出来るか
#  print("x",x,"A[x]",A[x])
  if (x + 1) <= P:
    return True
  if A[x] + M < border:
    return False
  # 基準点
  base = A[x] + M
#  print("base",base,"点を取って合格したい")
  
  # 上位P - 1には必ず投票して良い
  vote = (P - 1) * M
#  print("まず",vote,"票を投票")
  # P位以下には、baseを超えないように投票して良い
  for i in range(P - 1,len(A)):
    limit = max(base - A[i], 0)
    can = min(limit, M)
#    print(A[i],"にはcan",can,"票投票できる")
    vote += can
#  print("vote",vote)
  if vote >= M * V:
    return True
  return False

while abs(ok - ng) > 1:
  mid = abs(ok + ng)//2
  if isOk(mid):
#    print(mid,"is ok")
    ok = mid
  else:
#    print(mid,"is ng")
    ng = mid
    
print(ok + 1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

n, m, v, p = map(int, input().split())
a = sorted(map(int, input().split()))
cs = [0] + list(accumulate(a))
ans = p
rv = n - v
rp = n - p
for i in range(rp):
    if a[i] + m < a[rp]:
        continue
    l = rp - i
    if (cs[rp + 1] - cs[i + 1]) + (l - rv) * m <= (a[i] + m) * l:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
# 累積和
def cumsum(l):
    """a[i] = sum(l[:i]) なるaを返す
    """
    c = 0
    a = [None] * (len(l)+1)
    for i,num in enumerate(l):
        a[i] = c
        c += num
    a[-1] = c
    return a

s = cumsum(a)

def sub(i):
    # a[i]がいけるかどうか
    if i>=n-p:
        return True
    if a[i] + m < a[-p]:
        return False
    v1 = a[i] + m
    ss = m * (i+p)
    tmps = (s[n-p+1] - s[i+1])
    ss += v1*(n-i-p) - tmps    
    r = ss >= m*v
    return r
l = 0
r = n-1
if sub(l):
    print(n)
else:
    while l<r-1:
        mm = (r+l)//2
        if sub(mm):
            r = mm
        else:
            l = mm
    print(n-1-l)

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mi = 0
ma = n - 1


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


while mi != ma:
    mm = (mi + ma) // 2
    if ok(mm):
        ma = mm
    else:
        mi = mm + 1
print(n - mi)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

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

    ans = 0
    ac = list(itertools.accumulate(A))
    for i in range(N):
        if i >= N-P:
            ans += 1
            continue
        if M+A[i] < A[N-P]: continue
        if V <= P:
            ans += 1
            continue

        w = ((N-P-i) * (M+A[i])) - (ac[N-P] - ac[i])
        if w >= M * (V-P-i):
            ans += 1
    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(reverse=True)
ans=P
T=A[P-1]
for i in range(P,N):
 if A[P-1]-A[i]<=M and T-(i-P+1)*A[i]<=M*(N-V):
  ans+=1
 T+=A[i]
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)
ans=p
x = a[p - 1]
if v<=p:
    for i in range(p,n):
        if a[i]+m>=x:
            ans+=1
        else:
            break

else:
    # 当落ラインを変えずにどれくらい点を割り振れるか記録
    b=[0]*n
    for i in range(p,n):
        b[i]+=b[i-1]
        b[i]+=x-a[i]

    for i in range(p,n):
        r=v-n+i-p+1
        if r<=0:
            if a[i]+m>=x:
                ans+=1
            else:
                break
        else:
            # 新しい当落ライン=x1
            if r*m<=b[i-1]:
                x1=x
            else:
                x1=-(-(r*m-b[i-1])//(i-p+1))+x

            if a[i]+m>=x1:
                ans+=1
            else:
                break

print(ans)

Submission status: Accepted

Solution code:
N, M, V, P = map(int, input().split())
S = list(map(int, input().split()))
S.sort()
total = [0]*N
total[0] = S[0]

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

if total[N-P]-total[0]+(V-P)*M <= (S[0]+M)*(N-P) and S[0]+M >= S[N-P]:
    ans = N
else:
    ok = N-1
    ng = 0
    while ng+1 < ok:
        mid = (ok+ng)//2
        if mid > N-P:
            ok = mid
        elif total[N-P]-total[mid]+(V-(P+mid))*M <= (S[mid]+M)*(N-P-mid) and S[mid]+M >= S[N-P]:
            ok = mid
        else:
            ng = mid
    ans = N-ok
print(ans)

Submission status: Accepted

Solution code:
import bisect
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)
if (v<=p):
    limit = a[n-p]
    if (a[n-p] <= m):
        print(n)
    else:
        x = bisect.bisect_left(a,a[n-p]-m)
        print(n-x)
else:
    limit = a[n-p]
    #print(1,limit)
    wa = [0]*n
    wa[0] = a[0]
    for i in range(1,n):
        wa[i] = wa[i-1] + a[i]
    #print(limit,wa)
    ans = 0
    for i in range(n-p-1,-1,-1):
        sa = limit - a[i]
        if (sa==0):
            ans += 1
            continue
        elif (sa > m):
            continue
        if (i>=v):
            ans += 1
            
        else:
            nokori = (v-i-1-(p-1))*m
            #x = bisect.bisect_left(a,a[i]+m)
            #print(i,nokori)
            if (nokori <= (a[i]+m)*(n-p-i) - (wa[n-p]-wa[i])):
                ans += 1
                #print(i)
              
    print(ans + p)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n,m,v,p = map(int,readline().split())
a = [int(i) for i in readline().split()]
a.sort(reverse=True)
ans = p
v -= (p-1)
g = a[p-1]
L = 1
use = m-g

for i in range(p,n):
  mar = g-a[i]
  V = v-(n-1-i)
  if mar > m:
    break
  if V <= 1:
    if mar <= m:
      ans += 1
      L += 1
      use += m-a[i]
    else:
      break
  else:
    if use+a[i]*L >= (V-1)*m:
      ans += 1
      L += 1
      use += m-a[i]
    else:
      break

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)
ans=p
border=a[p-1]
d=0
for i in range(p,n):
    # 考察対象はi+1位の問題
    if border>a[i]+m:#全員から票を集めてもp位になれない
        break
    # i+1位の問題をp位にできるパターンを分析
    # i+1位からn位の問題にm票投票
    vote=m*(n-i)
    # 1位からp-1位の問題にm票投票
    vote+=m*(p-1)
    # p位～i位の問題にi+1位と同じ票数になるように投票。このとき一問あたりの得票数はmを超えない
    vote+=d+(a[i]+m-border)*(i-p+1)
    # d:p位からi位問題の得票数をp位と同じにするのに必要な票数。一個当たりの票数はmを超えない。
    if vote>=v*m:
        ans+=1
    d+=border-a[i]
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product

def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)

rui=[0]
for i in range(p,n):
   rui.append(rui[i-p]+(a[p-1]-a[i]))
# print(a)
# print(rui)
ans=p
tmp=0

for i in range(p,n):
    if a[p-1]<=a[i]+m:
        if n-i-1+p>=v:
            ans+=1
        else:
            mae=rui[i-p]+(a[i]+m-a[p-1])*(i-p+1)
            ushiro=(n-i-1)*m
            # print(mae,ushiro)
            if mae+p*m+ushiro>=m*v:
                ans+=1

print(ans)

Submission status: Accepted

Solution code:
# B - Voting Judges
# https://atcoder.jp/contests/agc041/tasks/agc041_b
# https://atcoder.jp/contests/agc041/submissions/12183756

# にぶたん　二分探索
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)

ok = p - 1
ng = n

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i != mid:
      used += min(m, max(0, A[mid] + m - A[i]))
      if used >= m * v:
        break

  if used >= m * v:
    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(reverse=True)

ok = p - 1
ng = n

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i != mid:
      used += min(m, max(0, A[mid] + m - A[i]))

  if used >= m * v:
    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(reverse=True)

ok = p - 1
ng = n

while abs(ok - ng) > 1:
  mid = (ok + ng) // 2
  if A[mid] + m < A[p - 1]:
    ng = mid
    continue

  used = m * p
  for i in range(p - 1, n):
    if i == mid:
      continue

    used += min(m, max(0, A[mid] + m - A[i]))

  if used >= m * v:
    ok = mid
  else:
    ng = mid

print(ok + 1)

Submission status: Accepted

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

ls.sort()
total=m*v
for i in range(min(v-1,p-1)):
    ls[-i-1]+=m
    total-=m

ac = [0]*n
for i in range(n-1):
    ac[i+1] = ac[i]+(ls[i+1]-ls[i])*(i+1)

l=-1
r=n
while l+1<r:
    i=(l+r)//2
    idx=bisect.bisect_right(ls,ls[i]+m)
    if n-idx>=p:
        l=i
        continue
    totalnow=total-m*(i+1)
    if totalnow <= 0:
        r=i
        continue
    ok=ac[-p]-ac[i]-(ls[-p]-ls[i])*(i+1)+(ls[i]+m-ls[-p])*(n-p-i)
    if ok< totalnow:
        l=i
        continue
    r=i

print(n-r)

Submission status: Accepted

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

ls.sort()
total=m*v
for i in range(min(v-1,p-1)):
    ls[-i-1]+=m
    total-=m

ac = [0]*n
for i in range(n-1):
    ac[i+1] = ac[i]+(ls[i+1]-ls[i])*(i+1)

ans=p
for i in range(n-p):
    idx=bisect.bisect_right(ls,ls[i]+m)
    if n-idx>=p:
        continue
    totalnow=total-m*(i+1)
    if totalnow <= 0:
        ans += 1
        continue
    ok=ac[-p]-ac[i]-(ls[-p]-ls[i])*(i+1)+(ls[i]+m-ls[-p])*(n-p-i)
    if ok< totalnow:
        continue
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a)
eps = 0.1
def func(k):
    # print("tsrget:"+str(k))
    used = 0
    tmp = a[:k]+a[k+1:]
    val = a[k]+M
    x1 = N-1-bisect.bisect(tmp, val+eps)
    x2 = bisect.bisect(tmp, val-eps)
    x3 = N-(x1+x2+1)
    # print(tmp,val,x1,x2,x3)
    if x1 >= P:
        return False
    v = V - (x1+1)
    p = P - (x1+1)
    used += x1+1
    if v <= 0:
        return True
    # x2+x3問からあとp問はa[k]+Mを超えてもよい
    # x3が十分ある
    if x3 >= p > 0:
        x3 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x3
        v -= x3
        used += x3
    if x2 >= p > 0:
        x2 -= p
        v -= p
        used += p
        p = 0
    if p>0:
        p -= x2
        v -= x2
        used += x2
    if v <= 0:
        return True
    # x2問からあとp問はa[k]+Mを超えてもよい
    tmp2 = tmp[:N-used]
    rest = sum([min(M,val-val2) for val2 in tmp2])
    # print(tmp2,N,x1,x3,p,v, rest)
    if rest >= M*v:
        return True
    return False

ok = N-1  # exist
ng = -1  # not exist
while abs(ok - ng) > 1:
    cnt = (ok + ng) // 2
    t = func(cnt)
    # print(t)
    if t:
        ok = cnt
    else:
        ng = cnt
print(N-ok)

Submission status: Accepted

Solution code:
import bisect
def main():

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

    prefix = [0]
    for i in range(N):
        prefix.append(prefix[-1] + A[i])

    ans = P
    for i in range(N-P):
        if A[i] + M >= A[N-P]:
            v = i * M + P * M
            v += (A[i] + M) * (N-P-i)
            v -= prefix[N-P+1] - prefix[i+1]
            if v >= M * V:
                ans += 1

    return ans

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

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
a = [int(x) for x in input().split()]

a.sort(reverse=True)

l, r = 0, n
while r-l>1:
  key = (r+l)//2
  if key < p:
    l = key
    continue
  if a[key]+m < a[p-1]:
    r = key
    continue
  
  count = 0
  for i in range(n):
    if i < p-1 or i >= key:
      count += m
    else:
      count += a[key]+m-a[i]
  if count >= m*v:
    l = key
  else:
    r = key

print(r)

Submission status: Accepted

Solution code:
def check(n):

    if n <= P-1:
        return True

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-i for i in A[P-1:n]])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

##開区間
right = N
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Accepted

Solution code:
def check(n):

    if n <= P-1:
        return True

    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

##開区間
right = N
left = 0

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Accepted

Solution code:
def check(n):

    if n <= P-1:
        return True


    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N
left = -1


##
"""
if check(right):
    print(N)
    exit()
"""
while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Accepted

Solution code:
def check(n):
    """
    if n <= P-1:
        return True
    """
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = P-1

if check(right):
    print(N)
    exit()

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Accepted

Solution code:
def check(n):

    if n <= P-1:
        return True
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

if check(right):
    print(N)
    exit()

while abs(right-left) > 1:

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Accepted

Solution code:
def check(n):

    if n <= P-1:
        return True
    
    if A[n]+M < A[P-1]:
        return False
    
    votes = (P+N-1-n)*M + sum([A[n]+M-A[i] for i in range(P-1,n)])

    if votes < M*V:
        return False
    else:
        return True

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

A.sort(reverse=True)

right = N-1
left = 0

if check(right):
    print(N)
    exit()

while abs(right-left) > 1 and check(left) and not check(right):

    mid = (right+left)//2

    if check(mid):
        left = mid
    else:
        right = mid

print(left+1)

Submission status: Accepted

Solution code:
n,m,v,p=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
a.sort(reverse=True)

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    if a[x]+m<a[p-1]:
        return False
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=a[x]+m-a[i]
    if tmp>=m*v:
        return True
    return False

left=0
right=n
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Submission status: Accepted

Solution code:
n,m,v,p=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
a.sort(reverse=True)

def f(x):
    if x>n-1:
        return False
    if x<p:
        return True
    if a[x]+m<a[p-1]:
        return False
    tmp=m*(p+n-x-1)
    for i in range(p-1,x):
        tmp+=min(m,a[x]+m-a[i])
    if tmp>=m*v:
        return True
    return False
left=-1
right=n
while right-left>1:
    mid=(left+right)//2
    if f(mid):
        left=mid
    else:
        right=mid
print(left+1)

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np
import bisect
N,M,V,P = (int(x) for x in input().split())
A = list(map(int, input().split()))
dtype = [('points','int64'),('number','int64')]
c = np.array([x for x in Counter(A).items()],dtype=dtype)
c.sort(order='points')
value = [c[-i][1] for i in range(1,len(c)+1)]
cs = np.cumsum(value)
bs = bisect.bisect_left(cs,P)
thr = c[-bs-1][0]
limit = np.cumsum([(thr-c[i][0])*c[i][1] for i in range(len(c)-bs-1)])
broke = False
if bs == len(cs) - 1:
    print(N)
else:
    for i in range(len(cs)-bs-1):
        point = c[-bs-2-i][0]
        points_needed = thr - point
        if points_needed > M:
            print(cs[bs+i])
            broke = True
            break
        else:
            questions_raised = V - (N - cs[bs+i])
            if questions_raised >= P:
                points_overflowed = M * (questions_raised-(P-1))
                points_limit = limit[-1] - limit[-1-i] + (point+M-thr) * (cs[bs+i]-P+1)
                if points_overflowed > points_limit:
                    print(cs[bs+i])
                    broke = True
                    break
    if broke == False:
        print(N)

Submission status: Accepted

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

a.sort()

l = -1
r = n-1
while r-l>1:
    i = (l+r)//2
    flag = 1
    if a[i]+m<a[n-p]:
        flag = 0
    elif i+p-1>=v:
        flag = 1
    else:
        rest = (v-i-p)*m
        for j in range(i+1,n-p+1):
            rest -= min(m,a[i]+m-a[j])
        if rest<=0:
            flag = 1
        else:
            flag = 0
    if flag:
        r = i
    else:
        l = i

print(n-r)

Submission status: Accepted

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

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

mv = m*max(0, v-p+1)
b = a[p-1:]

l, r = b[0], b[0]+m
while l < r:
    md = (l+r)//2
    c = 0
    for i in b:
        c += min(m, md-i)
    if mv <= c:
        r = md
    else:
        l = md + 1

result = p
for i in b[1:]:
    if i+m >= r:
        result += 1
    else:
        break
print(result)

Submission status: Accepted

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

ans = p
for i in range(p, n):
    res = m * ((p - 1) + (n - i)) + \
          (a[i] + m) * (i - p + 1) - (sa[i] - sa[p-1])

    if res >= m * v and a[p-1] <= a[i] + m:
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N, M, V, P = map(int, rl().split())
    A = list(map(int, rl().split()))
    
    A.sort()
    
    def check(t):
        if A[t] + M < A[-P]:
            return False
        at = A[t]
        cnt = (P - 1) * M
        for idx in range(N - P + 1):
            cnt += min(M, M - A[idx] + at)
        return M * V <= cnt
    
    ok, ng = N - 1, -1
    while 1 < ok - ng:
        mid = (ok + ng) // 2
        if check(mid):
            ok = mid
        else:
            ng = mid
    print(N - ok)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import copy

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

def condition(num):
    test=copy.copy(A)
    x=test[num]+M
    test[num]+=M
    test.sort(reverse=True)
    k=test.index(x)
    index=k+1
    if index>P:
        return False

    test=test[P:]
    yoyuu=0
    for i in range(0,len(test)):
        if x-test[i]>M:
            yoyuu+=M
        else:
            yoyuu+=x-test[i]

    return yoyuu>=M*(V-P)

A.sort()
start=0
end=N-1
while end-start>1:
    t=(end+start)//2
    if condition(t):
        end=t
    else:
        start=t

if condition(start):
    print(N-start)
else:
    print(N-end)

Submission status: Accepted

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

#二分探索するからAをsortする
A = sorted(A,reverse=True)

left=0
right=N-1

while left<=right:
    mid = (left+right)//2

    if mid<P:#そもそも入っている
        left = mid + 1
    elif A[mid] + M < A[P-1]:
        right = mid -1
    else:
        voted = P * M
        for _ in range(mid+1,N):
            voted += M

        for v in A[P-1:mid]:
            voted += A[mid]+M-v

        if voted >= M*V:
            left= mid+1
        else:
            right = mid-1

print(left)

Submission status: Accepted

Solution code:
def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    s=sum(a[p-1:p])
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        
        cnt+= ((a[i]+m)*(i-p+1)-s+(n-(i-p+1))*m)>=v*m
        try: s+=a[i]
        except: continue      
    print(cnt)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def f(A, M, V, P, m):
    N = len(A)
    a = A[m]
    i = bisect.bisect_right(A, a + M)
    C = N - i

    if C >= P:
        return False

    C = P - 1
    i = N - C

    U = 0
    for j in range(i):
        if j == m:
            continue
        U += min(a + M - A[j], M)

    return U >= (V - 1 - C) * M


def main():
    N, M, V, P = read_values()
    A = read_list()
    A.sort()
    
    l = 0
    r = N
    while l < r:
        m = (r + l) // 2
        if f(A, M, V, P, m):
            r = m
        else:
            l = m + 1

    print(N - r)


if __name__ == "__main__":
    main()

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(x):
        # x問目が選ばれるか判定
        if x <= P-1:
            return True
        elif A[x-1] + M < A[P-1]:
            return False
        voted = (P-1)*M + (N-x)*M + M
        for i in range(P, x):
            voted += min(max((A[x-1] + M - A[i-1]), 0), M)
        if M*V <= voted:
            return True
        else:
            return False

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

    print(binary_search_meguru())


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while l+1 < r:
        i = (l+r) >> 1
        A = a[i]+m
        ri = bisect.bisect_right(a,A)
        j = n-ri
        if j >= p:
            l = i
            continue
        li = bisect.bisect_right(a,a[i])
        res = v-j-li
        if res <= 0:
            r = i
            continue
        res -= (p-j-1)
        s = 0
        for j in range(li,ri-(p-j-1)):
            s += A-a[j]
        if s >= res*m:
            r = i
        else:
            l = i
    print(n-r)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

A.sort(reverse=True)

# idxでP-1番目まで（上からP個）は必ず選ばれうる
ok = P-1
# 最後が選ばれるかまだ分からない
ng = N

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2

    # idxでmid番目の問題が選ばれるか考える
    # M人全員が投票しても上位P位の最も小さいもの（P番目。idxでいうとP-1のやつ）を超えないなら無理
    if A[mid] + M < A[P-1]:
        ng = mid
        continue

    used = 0
    # 上からP-1個とmidには＋Mしてよい
    used += M*P

    # それ以外には、mid番目＋Mを超えないように＋してよい
    for i in range(P-1, N):
        # mid番目は既に足しているので飛ばす
        if i == mid:
            continue
        
        # mid番目＋Mを超えないように＋する。
        used += min(M, max(0, A[mid] + M - A[i]))

    # midにとって最も都合のいい割り振りで、投票数を使い切れるなら、上位P位に入れる可能性がある
    if used >= M*V:
        ok = mid
    else:
        ng = mid

# idxがokの問題までは選ばれうるので、ok+1個が選ばれうる
print(ok+1)