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

Solution (Python):
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



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



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
        
        if check(mid, N, M, V, P, A):
            r = mid
        else:
            l = mid
        
    print(N - r)
    return
    
    
    

    
    
    
    
    
    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
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



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



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
    
    
    

    
    
    
    
    
    
    
    
    
    
    


if __name__ == '__main__':
    main()

Solution (Python):
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



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

    
    
    
    
    
    
    
    
    
    
    

    


if __name__ == '__main__':
    main()

Solution (Python):
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



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

    
    
    
    
    
    
    
    
    
    
    

    


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
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):
  
  pps += A[i - 1]

  
  if A[i] + M < A[P - 1]:
    break
  
  fv = min(P - 1 + N - i, V)
  
  
  
  
  
  
  if (A[i] + M) * (i - P + 1) < pps + M * (V - fv):
    break
  con += 1
  
print(con)

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


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)

Solution (Python):
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)



B = A[P-1:]
V = V -P + 1
N = N - P + 1



L = B[0]
pb = B[0]
pi = 0
Z = 0
for i in range(1,N):
    
    if pb == B[i]:
        
        
        continue
    
    Z = Z + (L - pb)* (i -pi)
    pb = B[i] 
    pi = i
    
    if B[i] + M < L: 
        print(P-1+i)
        exit(0)
    if N -i >=  V:
        
        next
    
    capacity = Z + i * (B[i] + M - L ) + (N-i) * M
    
    if capacity < V * M:
        print(P -1 + i)
        exit(0)
print(P+N-1)

Solution (Python):
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)

Solution (Python):
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()

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

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







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

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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
    
    if q<=0:
        return (a[i]+m >= a[p])
    ret = (i-p)*(a[i]+m) >= acc[i-1]-acc[p-1]+m*q
    
    
    return ret

n,m,v,p = inm()
a = inl()
a.sort(reverse=True)
a[0:0] = [0] 
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:
    
    mid = (mn+mx)//2
    if foo(mid):
        mn = mid
    else:
        mx = mid
print(mn)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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の問題が採用されるかどうかを真偽値で返す"""
        
        if x + m < a[p - 1]:
            return False
        
        mv = m * v
        mv -= m * len(a[:p-1])  
        for score in a[p-1:]:
            mv -= min(m, x + m - score)  
        
        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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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):
    
    mn = 0
    mx = i
    while mx-mn>=2:
        mid = (mx+mn)//2
        if a[i]+m < a[mid]:
            mn = mid
        else:
            mx = mid
    r = mx
    
    if r>p:
        return False
    
    
    
    ok = False
    for s in range(r,p+1):
        ret = ( (i-s)*(a[i]+m) >= acc[i-1]-acc[s-1]+m*(v-n+i-s))
        
        if ret:
            ok = True
            break
    
    
    return ok

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

Solution (Python):














def main():
    from bisect import bisect_left, bisect_right
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

    N, M, V, P = map(int, input().split())
    *A, = sorted(map(int, input().split()))
    acc = (0,) + tuple(accumulate(A))

    def is_ok(mid):
        x = A[mid]
        ika = bisect_right(A, x)
        rest = max(0, V - ika)
        if rest >= P:
            
            
            rng = N - ika - (P - 1)  
            times = V - (P - 1) - ika  

            range_sum = acc[mid + 1 + rng] - acc[mid + 1]
            to_sub = A[mid + rng] * rng - range_sum
            to_dist = M * times - to_sub

            if to_dist <= 0:
                return A[N - P] <= x + M
            else:
                to_add = (to_dist + rng - 1) // rng
                return max(A[N - P], A[mid + rng] + to_add) <= x + M

        else:
            return A[N - P] <= 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

    idx = binary_search()
    print(N - bisect_left(A, A[idx]))


if __name__ == '__main__':
    main()

Solution (Python):
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=P
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)

Solution (Python):
import sys
import bisect
import itertools


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n, m, v, p = list(map(int, readline().split()))
    a = list(map(int, readline().split()))
    a.sort()
    acm = list(itertools.accumulate(a))
    target = bisect.bisect_right(a, a[-p]) - 1
    for i in range(n - 1):
        bl = bisect.bisect_left(a, a[i])
        br = bisect.bisect_right(a, a[i])
        if br < n:
            dif = acm[target] - acm[br-1] - a[i] * (target - br + 1)
            
            if dif <= min((n - v), (target - br) + 1) * m and a[target] - a[i] <= m:
                print(n - i)
                exit()
    print(n - bisect.bisect_left(a, a[target]))


if __name__ == '__main__':
    solve()

Solution (Python):
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
    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():
    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()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines







def main():
	n,m,v,p=map(int,input().split())
	A=list(map(int,input().split()))
	A.sort(reverse=True)
	teki=A[p-1]
	
	cnt=1
	d=0
	
	for i in range(p,n):
		if A[i]+m<teki:break
		d+=cnt*(A[i-1]-A[i])
		if d>m*(n-v):break
		cnt+=1
	print(p+cnt+-1)
	
	
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines






import bisect



def main():
	n,m,v,p=map(int,input().split())
	A=list(map(int,input().split()))
	A.sort(reverse=True)
	teki=A[p-1]
	
	ans=0
	cnt=1
	d=0
	
	for i in range(p,n):
		if A[i]+m<teki:break
		d+=cnt*(A[i-1]-A[i])
		if d>m*(n-v):break
		cnt+=1
		ans+=1
	print(p+ans)
	
if __name__ == "__main__":
	main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines










def main():
	n,m,v,p=map(int,input().split())
	A=list(map(int,input().split()))
	A.sort(reverse=True)
	teki=A[p-1]
	
	ans=0
	cnt=1
	d=0
	
	for i in range(p,n):
		if A[i]+m<teki:break
		d+=cnt*(A[i-1]-A[i])
		if d>m*(n-v):break
		cnt+=1
		ans+=1
	print(p+ans)
	
if __name__ == "__main__":
	main()

Solution (Python):
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def binary_search(left, right):
    if right - left <= 1:
        return left
    middle = (left + right) // 2
    if check(middle):
        return binary_search(middle, right)
    else:
        return binary_search(left, middle)

def check(target):
    used_vote = (p + n - target - 1) * m
    sum_vote = 0
    for i in range(target-1, p-2, -1):
        if a[target] + m < a[i]:
            return False
        sum_vote += (a[target] + m) - a[i]
    if sum_vote >= (m * v - used_vote): 
        return True
    else:
        return False
print(binary_search(0,n) + 1)

Solution (Python):
n,m,v,p = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
p-=1

a.sort(reverse=True)

ans=0
s = sum(a)

def safe(index):
    if a[p]>a[index]+m:
        return False
    i=0
    while a[i]>=a[index]+m:
        i+=1
    if i>index:
        return True
    intg = 0
    i = max(i,p)
    while i<index:
        intg += a[index] + m - a[i]
        i+=1
    intg += (len(a)-1-index)*m
    
    return intg >= m*(v-1) - p*m

left = 0
right = len(a)-1
ans = int((right - left)/2)
if safe(right):
    ans = right
else:
    j = safe(ans)
    while not(j and not safe(ans+1)):
        if j:
            left = ans
        else:
            right = ans
        ans = left + int((right - left)/2)
        j = safe(ans)
print(ans+1)
"""
for i in range(len(a)):
    print(a[i],safe(i))
"""

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

Solution (Python):
def main():
    from bisect import bisect_left, bisect_right
    from itertools import accumulate
    import sys

    input = sys.stdin.readline

    N, M, V, P = map(int, input().split())
    *A, = sorted(map(int, input().split()))
    acc = (0,) + tuple(accumulate(A))

    def is_ok(mid):
        x = A[mid]
        ika = bisect_right(A, x)
        rest = max(0, V - ika)
        if rest >= P:
            
            
            rng = N - ika - (P - 1) 
            times = V - (P - 1) - ika 

            range_sum = acc[mid + 1 + rng] - acc[mid + 1]
            to_sub = A[mid + rng] * rng - range_sum
            to_dist = M * times - to_sub

            if to_dist <= 0:
                return A[N - P] <= x + M
            else:
                to_add = (to_dist + rng - 1) // rng
                return max(A[N - P], A[mid + rng] + to_add) <= x + M

        else:
            return A[N - P] <= 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

    idx = binary_search()
    print(N - bisect_left(A, A[idx]))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import heapq

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()

    h, l = N, -1
    b = A[N - P]
    while h - l  > 1:
        m = (h + l) // 2
        NG = A[m] + M
        if NG < b: l = m
        elif m >= N - P: h = m
        else:
            room = (m + P) * M
            for i in range(m + 1, N - P + 1): room += NG - A[i]
            if room < M * V: l = m
            else: h = m

    print(N - l - 1)
    return 0

if __name__ == "__main__":
    solve()