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
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

ng = -1
ok = N - P
#print(a)
def check(x):
  vs = M * V
  p = N
  for i in range(N):
    if a[i] > a[x] + M:
      p = i - 1
      break
  #print(x, vs, p)
  if p < N - P: return False
  #print(x, vs)
  for i in range(N - P + 1, N):
    vs -= M
  #print(x, vs)
  for i in range(N - P + 1):
    vs -= min(max(a[x] + M - a[i], 0), M)

  #print(x, vs)
  return vs <= 0

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

Submission status: Accepted

Solution code:
class cumulative_sum:
    def __init__(self,A):
        N = len(A)
        self.S = [0]*(N+1)
        for i in range(N):
            self.S[i+1] = self.S[i] + A[i]
    def get(self,i,j=None):
        if j==None:j=len(self.S)-1
        if j<=i:return 0
        return self.S[j]-self.S[i]

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

S = cumulative_sum(A)

def check(i):
    s = max(0,S.get(i+1,N-P+1))
    res = max(M*(V-P-i),0)
    if A[i]+M<A[N-P]: return False
    return ((A[i]+M)*max(0,N-P-i))>=s+res

ans = sum(check(i) for i in range(N))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
p-=1
A=sorted(list(map(int,input().split())),reverse=True)[p:]
s=0
for u,a in enumerate(A):
 if a>=A[0]-m and u*a+m*n-m*v>=s:s+=a;p+=1
 else:break
print(p)

Submission status: Accepted

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)


def isOK(i):  # i番目が採用されるかどうかを確かめる
    # 上位P-1問には上限いっぱいM票ずつ投票可能
    need = M * (P-1)
    # 今見ているi問目には上限いっぱいM票入れるのが妥当
    need += M
    # 今見ているi問目よりもスコアの小さいN-i-1問は上限いっぱいM票入れる
    # N=10, i=7の場合は後ろは残り2問
    need += M * (N-i-1)
    ai = A[i]+M  # 基準値
    s = 0
    for j in range(P-1, i):
        d = ai - A[j]
        if d < 0:
            return False
        s += d
    
    if need + s >= M*V:
        return True
    else:
        return False


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid

print(left + 1)

Submission status: Accepted

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

capacity = M * (N-V)


def isOK(i):
    ai = A[i]  # 基準となる値
    s = 0
    # 0~P-2番目のP-1問とi番目とi番目以降には全員が投票しても構わない
    # P-1番目からi-1番目までについて考える必要がある
    for j in range(P-1, i):
        d = A[j] - ai
        # A[j]とaiの差がM以上あるということは、A[0]からA[j-1]までも差がM以上あり追いつけない
        if d > M:  # この時点で先頭のA[j]問を含む先頭の問題たちはaiが追いつけないスコアをもっている
            return False
        s += d
    if s > capacity:
        return False
    else:
        return True


left = -1
right = N
while right - left > 1:
    mid = (right+left)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid
print(left + 1)

Submission status: Accepted

Solution code:
# A[i]が採用されるとき、A[i-1]も採用されるという単調性があるので二分探索で解く
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

capacity = M * (N-V)


def isOK(i):
    ai = A[i]  # 基準となる値
    s = 0
    # 0~P-2番目のP-1問とi番目とi番目以降には全員が投票しても構わない
    # P-1番目からi-1番目までについて考える必要がある
    for j in range(P-1, i):
        d = A[j] - ai
        # A[j]とaiの差がM以上あるということは、A[0]からA[j-1]までも差がM以上あり追いつけない
        if d > M:  # この時点で先頭のA[j]問を含む先頭の問題たちはaiが追いつけないスコアをもっている
            return False
        s += d
    if s > capacity:
        return False
    else:
        return True


left = -1
right = N
while right - left > 1:
    mid = right + (left-right)//2
    if isOK(mid):  # 中央値が満たすなら下界をあげる
        left = mid
    else:  # 中央値が満たさないなら上界を下げる
        right = mid
print(left + 1)

Submission status: Accepted

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

A.sort()

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

def check(m) :
  if m >= N - P :
    return True
  if A[m] + M < A[N - P] :
    return False

  rest = M * (V - P)
  x = A[m] + M
  for i in range(N - P + 1) :
    if i == m :
      continue
    rest -= min(x - A[i], M)
  return rest <= 0

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

print(N - ng - 1)

Submission status: Accepted

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

def isOk(n):
    if n < P:
        return True
    b = A[n] + M

    cnt = (P - 1) * M + (N - n) * M
    for a in A[P - 1: n]:
        cnt += max(0, b - a)

    if b >= A[P - 1] and cnt >= V * M:
        return True
    return False

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

print(ng)

Submission status: Accepted

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = -(-(sum(D) - W) // W) + 1

    return max(max(D), cnt) <= M

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

print(ng)

Submission status: Accepted

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

ok, ng = p-1, n
while ng-ok > 1:
	mi = (ng+ok)//2
	possible = True
	x = a[mi]
	i = mi-1
	cnt = 0
	while i >= p-1:
		if a[i]-x > m:
			possible = False
			break
		cnt += a[i]-x
		i -= 1
	if cnt > m * (n - v):
		possible = False

	if possible:
		ok = mi
	else:
		ng = mi

print(ok+1)

Submission status: Accepted

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

A.sort()

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

def check(m) :
  if m >= N - P :
    return True
  if A[m] + M < A[N - P] :
    return False

  rest = M * (V - P)
  x = A[m] + M
  for i in range(N - P + 1) :
    if i == m :
      continue
    rest -= min(x - A[i], M)
  return rest <= 0

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

print(N - ng - 1)

Submission status: Accepted

Solution code:
n = input()    
m = n.split()
p = [int(i) for i in m]
n = input()    
m = n.split()
P = [int(i) for i in m]
nP = sorted(P,reverse=True)
A = p[3] -1
a = nP[p[3]-1]
sum = nP[p[3]-1]
V = a
for i, value in enumerate(nP):
    if i < p[3]:
        pass
    else:
        if V == value:
            sum = sum + value
            A = i
        else:
            if value + p[1] >= a:
                if ((i - p[3]+1)-(p[0] - p[2])) *p[1] <= (value +p[1])*(i - p[3]+1)-sum:
                    A = i
                    sum = sum + value
                    V = value
                else:
                    break
            else:
                break

print(A + 1)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

A.sort()
l = -1
r = N
while r - l > 1:
    m = (l+r)//2
    if m+1+P > N:
        r = m
        continue
    if V <= m+P:
        if A[m]+M >= A[-P]:
            r = m
        else:
            l = m
        continue
    if A[m]+M < A[-P]:
        l = m
        continue
    limit = A[m] + M
    can = 0
    for i in range(m+1, N-P+1):
        can += limit-A[i]
    if can >= (V-P-m)*M:
        r = m
    else:
        l = m

print(N-r)

Submission status: Accepted

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

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


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

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

# A_P -> A_X (A_P - M = A_X)
A_P = A[P-1]
A_X = A[P]
i_X = P
for i in range(P, len(A)):
    if (A_P - A[i]) > M:
        A_X = A[i-1]
        i_X = i-1
        break
    elif i == (len(A)-1):
        A_X = A[i]
        i_X = i
    else:
        continue

NG_POINT = (P-1) * M


def isPossible(i):
    if (i+1) < P:
        return True
    elif i > i_X:
        return False

    MV = M * V
    ax = A[i]
    score = ax + M

    total = M + NG_POINT
    total += (N - i - 1) * M

    for j in range(i-1, P-2, -1):
        total += score - A[j]

    #print("i", i, "total", total, "NG_POINT", NG_POINT)

    if total >= MV:
        return True

    return False


left = 0
right = i_X

if not isPossible(left):
    print(1)
    exit()

if isPossible(i_X):
    print(i_X + 1)
    exit()

#print("A", A, "i_X", i_X)

for _ in range(i_X):
    #print("left", left, isPossible(left), "right", right, isPossible(right))
    if (left + 1) == right:
        break

    mid = (left + right) // 2

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

print(left + 1)

Submission status: Accepted

Solution code:
from itertools import *
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
acc=list(accumulate(a))+[0]
ok,ng=p-1,n
while ng-ok>1:
	mid=(ok+ng)//2
	if a[mid]+m>=a[p-1] and (a[mid]+m)*(mid-p+1)-(acc[mid-1]-acc[p-2])>=m*(v-(p-1)-(n-mid)):
		ok=mid
	else:
		ng=mid
print(ok+1)

Submission status: Accepted

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

    def is_possible(i):
        # Aは降順 -> sorted_A、
        # i+1番目以降の問題のスコアをi番目の問題のスコア以下になるように投票すれば
        # i番目の問題に採用される可能性が生まれるという考え方

        # 投票前の上位P問は採用される可能性がある
        if i < P:
            return True

        # 残り投票数
        num_votes = V * M

        # i番目の問題を採用させようとする場合は、M人のジャッジ全員がi番目の問題に投票すればよい
        score_i = sorted_A[i] + M
        num_votes -= M

        # M人のジャッジ全員がi番目の問題に投票しても、上位P問にスコアが上がらない場合は採用される可能性がない
        if sorted_A[P - 1] > score_i:
            return False

        # 上の操作からi+1番目以降のの問題のスコアを、i番目の問題のスコアを超えることがないため、
        # M人のジャッジ全員がi+1番目以降の問題に投票してもよい
        num_votes -= (N - i - 1) * M

        # i番目の問題が上位P問に入ればよいので、P-1位の問題にもM人のジャッジ全員が投票してもよい
        num_votes -= (P - 1) * M

        # P番目からi番目
        # print('margin: {}, num_votes: {}'.format(sum(score_i - j for j in sorted_A[P-1 : i]), num_votes))
        return sum(score_i - j for j in sorted_A[P-1 : i]) >= num_votes

    # 1番目は必ず採用される
    # N番目は採用されるか
    if is_possible(N-1):
        print(N)

    # 1番目:採用、N番目:採用されない
    # -> [1:N-1]のどこに採用の境界があるかを二分探索する
    else:
        low = 0
        hight = N - 1

        while hight - low > 1:
            middle = (hight + low) // 2
            # print('PRE - low:{}, middle:{}, hight:{}'.format(low, middle, hight))
            if is_possible(middle):
                low = middle
            else:
                hight = middle
            # print('AFT - low:{}, middle:{}, hight:{}'.format(low, middle, hight))

        print(low + 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
           
right = P-1
left = N

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M

        
    if b<0:
        if A[P-1]<=target:
            right = i
        else:
            left = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)

Submission status: Accepted

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

import sys
import numpy as np


def check(N, M, V, P, As, i):
    # As = 3 2 2 1 1 0
    border = As[P - 1]
    a = As[i]
    # iはTop Pに入っている
    if a >= border:
        return True
    # iに全票入れてもTop Pに入れない
    if a + M < border:
        return False

    # iがTop Pに入るのを保てる最大の票数を計算
    num = M  # i番目に全票
    num += (P - 1) * M  # Top 1からP-1までには全票いれてよい
    num += (N - i - 1) * M # iよりあとのものにも全票いれてよい
    for j in range(P - 1, i): # Top Pからi-1まで、同票までOK
        num += (a + M - As[j])
    
    return num >= M * V


def solve(N, M, V, P, As):

    As = As[:]
    As.sort(reverse=True)

    # for j in range(N):
    #     print("j, check = ", j, check(N, M, V, P, As, j))

    # 二分探索がなりたたない場合を除外
    if check(N, M, V, P, As, N-1):
        return N

    ok = 0
    ng = N - 1
    while ng - ok > 1:
        mid = (ok + ng) // 2
        if check(N, M, V, P, As, mid):
            ok = mid
        else:
            ng = mid

    return ok + 1


def main():
    N, M, V, P = map(int, input().split())
    As = list(map(int, input().split()))
    print(solve(N, M, V, P, As))

main()

Submission status: Accepted

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

a.sort(reverse=True)


def can_be_used(x):
    # x: 0-index
    if x < p:
        return True

    if a[x] + m < a[p-1]:
        return False

    vote_max = (p - 1 + n - x) * m
    for i in range(p-1, x):
        vote_max += a[x] + m - a[i]

    if vote_max < m * v:
        return False

    return True


l = 0
r = n

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

    if can_be_used(mid):
        l = mid
    else:
        r = mid

ans = l + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + 1 + u_cnt >= v:
        return True
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    # print(cnt)
    if cnt >= m*v:
        return True
    else:
        return False
# print(f(a[2],2))
ok = n-1
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-ok)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + 1 + u_cnt >= v:
        return True
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    # print(cnt)
    if cnt >= m*v:
        return True
    else:
        return False
# print(f(a[2],2))
ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-ok)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,v,p = inpl()
a = inpl()
c = Counter(a)
a.sort()
b_num = a[n-p]
d_cnt = 0
b_cnt = 0
u_cnt = 0
for i in a:
    if i < b_num: d_cnt += 1
    elif i == b_num: b_cnt += 1
    else: u_cnt += 1

def f(x,i):
    if x >= b_num:
        return True
    if x + m < b_num:
        return False
    if i + 1 + u_cnt >= v:
        return True
    cnt = 0
    for item in a:
        if item > b_num or item <= x:
            cnt += m
        else:
            cnt += x + m - item
    # print(cnt)
    if cnt >= m*v:
        return True
    else:
        return False
# print(f(a[2],2))
ok = n
ng = -1
while abs(ok-ng) > 1:
    mid = (ok+ng)//2
    if f(a[mid],mid):
        ok = mid
    else:
        ng = mid
print(n-ng-1)

Submission status: Accepted

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


def isPossible(i):
    # Get highest rank with the same score
    i = A.index(A[i])

    # If already high rank, can vote top V to keep relative ordering
    if i < P:
        return True

    numVotes = V
    # Otherwise have every judge vote for i-th first
    # Each judge has V - 1 votes remaining
    score = A[i] + M
    numVotes -= 1
    # This is the best possible rank (more voting can only decrease rank)
    # If it isn't good enough, return early
    if A[P - 1] > score:
        return False
    # Soak up votes by voting for everything after i-th
    # Since adding M to everything, they will still be smaller
    numVotes -= N - i - 1
    # Soak up more votes by voting for everything in the top P - 1
    # Our element just needs to be within top P even if it's last
    numVotes -= P - 1
    if numVotes > 0:
        # If there are any votes remaining, it will be for indices P-1 thru i-1
        # We currently have:
        # A[i] + M >= A[P-1] >= A[P-2] >= ... >= A[i - 1] > A[i]
        # We want to distribute the remaining votes so that none of these become
        # greater than A[i] + M
        remainingVotes = numVotes * M
        gap = sum(score - x for x in A[P - 1 : i])
        return gap >= remainingVotes
    return True


if not isPossible(0):
    print(0)
elif isPossible(N - 1):
    print(N)
else:
    # If i-th is possible, so is 0th to (i-1)th
    # So binary search for the last index possible
    lo = 0
    hi = N - 1
    assert isPossible(lo)
    assert not isPossible(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if isPossible(mid):
            lo = mid
        else:
            hi = mid
    assert isPossible(lo)
    assert not isPossible(lo + 1)
    # If index i is possible, there are i+1 possible problems
    print(lo + 1)

Submission status: Accepted

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

while l != r:
    k = ceil((l + r) / 2)
    b = a[k] + m
    if b < a[0] or (v - (n - k)) * m > (k * b - sum(a[:k])):
        r = k - 1
    else:
        l = k
print(p+l)

Submission status: Accepted

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

As.sort(reverse=True)

scoreP = As[P-1]

def isOK(k):
    if k < P or As[k] == scoreP:
        return True

    scoreK = As[k] + M
    if scoreK < scoreP:
        return False

    rest = M*(V-1)
    rest -= M*(P-1)
    if rest <= 0:
        return True

    for i in range(P-1, N):
        if i != k:
            rest -= min(M, scoreK-As[i])
    if rest <= 0:
        return True

    return False


ng, ok = N, -1
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok+1)

Submission status: Accepted

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

lst1.sort(reverse=True)

def func(u):
    score = lst1[u] + m
    cost1 = max(0,v-(n-u))*m
    all_score = (p-1)*m
    for i in range(p-1,u):
        if score-lst1[i] < 0:
            all_score = -1
            break
        all_score += score-lst1[i]
    if all_score >= cost1:
        return True
    else:
        return False  


def binary_search(n): #2分探索
    ok = p-1
    ng = len(lst1)
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if func(mid):
            ok = mid
        else:
            ng = mid

    return ok

print(binary_search(n)+1)

Submission status: Accepted

Solution code:
import math
n,m,v,p=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
def is_ok(N,m,v,p):
    counter=0
    howadd=0
    not_avoid=0
    judge=lists[N]+m
    for k in range(n-1,-1,-1):
        if k!=N:
            if judge<lists[k]:
                counter+=m
                howadd+=1
                not_avoid+=1
            elif judge==lists[k] and howadd<p-1:
                counter+=m
                howadd+=1
            elif judge==lists[k] and howadd==p-1:
                pass
            elif judge>lists[k] and howadd<p-1:
                howadd+=1
                counter+=m
            elif judge>lists[k] and howadd==p-1:
                counter+=min(judge-lists[k],m)    
    if not_avoid>=p:
            return False
    elif not_avoid<p:
        if counter<(m)*(v-1):
            return False
        elif counter>=(m)*(v-1):
            return True
start=0
end=n-1
for _ in range(17):
    c=(start+end)/2
    if is_ok(math.floor(c),m,v,p):
        end=c
    elif not (is_ok(math.floor(c),m,v,p)):
        start=c       
print(n-math.floor(end))

Submission status: Accepted

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

A.sort(reverse=True)

S = [0]*N
t = 0
for i in range(N):
    t += A[i]
    S[i] = t

s = M*(N-V)
l = P
r = N
if P == 1:
    a = 0
else:
    a = S[P-2]
while l < r:
    m = (r-l)//2 + l
    if A[P-1]-M > A[m]:
        r = m
        continue
    if S[m-1]-a-(m-P+1)*A[m] > s:
        r = m
        continue
    l = m+1
    
print(l)

Submission status: Accepted

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

def check(i):
  if i <= P-1:
    return True
  vote = (V-1)*M
  vote -= (N-1-i)*M
  vote -= (P-1)*M
  if vote <= 0:
    return A[i]+M >= A[P-1]
  else:
    for j in range(i-1,P-1,-1):
      if A[j] > A[i]+M:
        return False
      vote -= min(A[i]+M-A[j],M)
      if vote <= 0:
        break
    if vote <= 0:
      return A[i]+M >= A[P-1]
    else:
      return A[i]+M >= A[P-1]+vote

ok = -1
ng = N
while(ok+1 < ng):
  md = (ok+ng)//2
  if check(md):
    ok = md
  else:
    ng = md
print(ok+1)

Submission status: Accepted

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

def check(i):
  if i <= P-1:
    return True
  vote = (V-1)*M
  vote -= (N-1-i)*M
  vote -= (P-1)*M
  if vote <= 0:
    return A[i]+M >= A[P-1]
  else:
    for j in range(i-1,P-1,-1):
      if A[j] > A[i]+M:
        return False
      v = min(A[i]+M-A[j],M,vote)
      vote -= v
      if vote <= 0:
        break
    if vote <= 0:
      return A[i]+M >= A[P-1]
    else:
      return A[i]+M >= A[P-1]+vote

ok = -1
ng = N
while(ok+1 < ng):
  md = (ok+ng)//2
  if check(md):
    ok = md
  else:
    ng = md
print(ok+1)

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n
low = 0
mid = (high + low) // 2
f = True


for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

while low < high:
    mid = (low + high) // 2
    if mid <= p-1:
        f = True
    elif prob_set[mid] + m < prob_set[p - 1]:
        f = False
    else:
        hyou = m * (p - 1) + m * (n - mid)
        for i in range(p-1,mid):
            hyou += prob_set[mid] + m - prob_set[i]
        # まず0 ~ p-2まで(1,2,,,p-1まで) :p-1
        # 次にmid,mid+1,,,n-1まで       :n-mid
        # 上限はp-1,p,,,mid-1は(mid)+mずつ
        # 和はmid-1 - p-2
        if hyou < m*v:
            f = False
        else:
            f = True
    if f:
        low = mid + 1
    else:
        high = mid

print(high)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう
# あるiについて評価するとき,以下の観点に注意する

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
total = 0
target = A[p-1]
before_p = p - 1

ans = p-1
for idx in range(p-1, n):
    candidate = A[idx]

    if candidate + m < target:
        break

    later_idx = n - idx - 1
    if before_p + later_idx >= v - 1:
        ans += 1

    else:
        possible = (before_p + later_idx)*m
        possible += (candidate+m)*(idx-p+1) - total

        if possible >= m*(v-1):
            ans += 1
        else:
            break
    total += candidate

print(ans)

Submission status: Accepted

Solution code:
N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True) + [-10 ** 10]
L, R, sA, lP = 0, N, [A[P - 1]], A[P - 1]
for i in range(P, N):
    sA.append(sA[-1] + A[i])

while R - L > 1:
    mid = L + (R - L) // 2
    if mid < P:
        L = mid
    elif A[mid] + M < lP:
        R = mid
    else:
        mi = mid - P + 1
        if M * (N - mi) + (A[mid] + M) * mi - sA[mi - 1] >= M * V:
            L = mid
        else:
            R = mid
print(L + 1)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort(reverse=True)
s=[None]*N
t=0
for i in range(N):
    t+=A[i]
    s[i]=t
S=M*(N-V)
l=P
r=N
if P==1:
    a=0
else:
    a=s[P-2]
while l<r:
    m=(r - l) // 2 + l
    if A[P-1]-M>A[m]:
        r=m
        continue
    if s[m-1]-a-(m-P+1)*A[m]>S:
        r=m
        continue
    l=m+1
print(l)

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])): r=k
    else: l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)

Submission status: Accepted

Solution code:
n,m,v,p=map(int,input().split())
a=sorted(list(map(int, input().split())),reverse=True)[p-1:]
l,r=0,n-p
while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])):
        r=k
    else:
        l=k
b=a[r]+m
print(p+l if(b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r]))) else p+r)

Submission status: Accepted

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

while l+1<r:
    k=(l+r)//2
    b=a[k]+m
    if b<a[0] or (v-(n-k))*m>(k*b-sum(a[:k])):
        r=k
    else:
        l=k

b=a[r]+m
if b<a[0] or (v-(n-r))*m>(r*b-sum(a[:r])):
    print(p+l)
else:
    print(p+r)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m,v,p=map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)
a=a[p-1:]
le=len(a)
l,r=0,le-1

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

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

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