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:
N,M,V,P=map(int, input().split())
*A,=map(int, input().split())

A.sort()

#A[x]の問題が採用される可能性があるか？
def check(x):
    r = A[-P] #無投票でギリギリ採用される問題のスコア
    if A[x] + M < r:
        return False
    votes = M*V
    votes -= M # A[x]に投票
    votes -= M*(P-1) #上位の問題に投票
    votes -= M*x #下位の問題に投票
    #微妙な問題にギリギリ投票
    for i in range(x+1, N-P+1):
        votes -= A[x]+M - A[i]
    return votes <= 0

l,r=-1,N-1
while r-l>1:
    m=(l+r)//2
    if check(m):
        r=m
    else:
        l=m
print(N-r)

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
        s = m*p
        for j in range(n-p+1):
            if i == j:
                continue
            s += min(m,A-a[j])
        if s >= m*v:
            r = i
        else:
            l = i
    print(n-r)
    return

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

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
        s = m
        for j in range(n-p+1):
            if i == j:
                continue
            s += min(m,A-a[j])
        s += m*(p-1)
        if s >= m*v:
            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)

def isOk(i):
    if i < P:
        return True

    b = A[i] + M
    if b < A[P - 1]:
        return False

    cnt = (P - 1) * M + (N - i) * M

    for a in A[P - 1: i]:
        cnt += max(0, b - a)
    return cnt >= M * V

ok = 0
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(map(int, input().split()))[::-1]
ans, s = P, A[P-1]
for i in range(P, N):
    if A[i]+M>=A[P-1]:
        ans += ((V+i+1-N-P)*M<=(i-P+1)*(A[i]+M)-s)
        s += A[i]
print(ans)

Submission status: Accepted

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

ans = P
s = A[P-1]
for i in range(P, N):
    if A[i]+M>=A[P-1]:
        a = V-(N-i+P-1)
        ans += (a*M<=(i-P+1)*(A[i]+M)-s)
        s += 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()

def f(x):
  if x>=n-p:
    return 1
  elif a[x]+m<a[n-p]:
    return 0
  else:
    ct=(p-1)*m+m+x*m
    for i in range(x+1,n-p+1):
      ct+=a[x]+m-a[i]
    if ct>=m*v:
      return 1
    else:
      return 0

L=-1;R=n
while R-L>1:
  x=(L+R)//2
  if f(x)==1:
    R=x
  else:
    L=x
print(n-L-1)

Submission status: Accepted

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, V, P = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype = np.int64)

A.sort()
r = N
l = 0
border = N - P
AP = A[border]
B = AP - A
np.cumsum(B, axis = 0, out = B)

def solve(ind):
	if A[ind] + M < AP:
		return 0
	if ind >= V - P:
		return 1

	score_border = A[ind] + M
	tmp = 0
	tmp += (ind + P) * M
	tmp += B[border] - B[ind]
	tmp += (score_border - A[border]) * (border - ind)
	if tmp >= M * V:
		return 1
	else:
		return 0

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

if solve(l):
	print(N - l)
else:
	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)

ans = p-1

d = 0

for i in range(p-1,n):
    if A[p-1] > A[i] + m:break
    may = (p-1 + n-i-1)*m
    may +=(A[i]+m)*(i - p+1) - d
    ans += (may + m>= m*v)
    d += A[i]

print(ans)

Submission status: Accepted

Solution code:
def solve(mid):
    if mid <= p:
        return True
    max_ = a[mid - 1] + m
    b = [max_ - a[i] for i in range(p - 1, mid - 1)]
    new_v = v - p - n + mid
    # print(mid)
    # print(b, m, new_v)
    if min(b) < 0:
        return False
    if new_v <= 0:
        return True

    cnt = 0
    for num in b:
        cnt += min(num, m)
    return cnt >= m * new_v
       


n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a = sorted(a, reverse=True)
# print(a)
ok = 1
ng = n + 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, m, v, p = map(int, readline().split())
a = np.array(read().split(), np.int64)
a.sort()


def check(i):
    if n - i <= p:
        return True
    x = a[i] + m
    y = np.zeros(n, np.int64)
    y = x - a
    y = np.minimum(y, m)
    y[n - p + 1:] = m
    if (y < 0).any():
        return False
    y[i] = 0
    next = y.sum()
    return next >= m * (v - 1)


low = -1
high = n - 1
while low + 1 < high:
    mid = (low + high) // 2
    if check(mid):
        high = mid
    else:
        low = mid
print(n - high)

Submission status: Accepted

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

def judge(x):
    if N-P<=x<=N-1:
        return True
    if A[x]+M<A[N-P]:
        return False
    
    cnt = 0
    
    for i in range(N-P+1):
        if i==x:
            continue
        
        cnt += min(M, A[x]+M-A[i])
    
    return cnt>=M*(V-P)

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

print(N-binary_search())

Submission status: Accepted

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

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

def binary_search():
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(m):
            r = m-1
        else:
            l = m+1
    
    return l

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

print(N-binary_search())

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):
        if x <= P-1:
            return True
        elif A[x-1] + M < A[P-1]:
            return False

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

    def binary_search_meguru():
        ng = N+1
        ok = -1
        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:
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

def ok(x):
    if x == -1:
        return False
    if x >= n-p:
        return True
    cnt = 0
    for i in range(x+1, n-p):
        cnt += max((A[x]+m)-A[i], 0)
    cnt += m*x
    cnt += m*(p-1)
    if max(m*(v-1) - cnt, 0)+A[n-p] <= A[x]+m:
        return True
    else:
        return False

l = -1
r = n-1
while l+1 < r:
    c = (l+r)//2
    if ok(c):
        r = c
    else:
        l = c
print(n-r)

Submission status: Accepted

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

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

ans = p

b = a[p:]
b_cumsum = [a[p - 1]]
for i in b:
    b_cumsum.append(b_cumsum[-1] + i)

for i in range(len(b)):
    vote_cnt = max(0, (v - p - (len(b) - (i + 1)))) # 上位p-1問と自分と自分より小さい問題にmずつ加算して余った回数
    if b_cumsum[i] + m * vote_cnt <= (b[i] + m) * (i + 1) and a[p - 1] <= b[i] + m: # 余った回数は好きな問題に分けて平均を取ると考える、そもそもp問目に追い付けないとアウト
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

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

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

ans = p

b = a[p:]
b_cumsum = [a[p - 1]]
for i in b:
    b_cumsum.append(b_cumsum[-1] + i)

for i in range(len(b)):
    vote_cnt = max(0, (v - p - (len(b) - (i + 1))))
    if b_cumsum[i] + m * vote_cnt <= (b[i] + m) * (i + 1) and a[p - 1] <= b[i] + m:
        ans += 1
    else:
        break

print(ans)

Submission status: Accepted

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

A.sort()
Ax = A[-P]  #上位Pの中の最下位

def f(i):
    mine = A[i] + M #自分に全力で投票
    if mine < Ax: return False #逆転不能
    votes = M*V
    votes -= M #自分への票
    votes -= min(P-1, V) * M #上位陣のx以外に全力で投票
    votes -= sum([min(mine - A[j], M) for j in range(N-P+1) if i!=j]) #逆転されない程度に下位陣に投票
    if votes > 0 : return False #再逆転される
    return True

under = -1
r = N-P
while r-under>1:
    m = (r+under)//2
    if f(m): r=m
    else: under=m

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)

def isOk(i):
    x = A[i] + M
    B = [x - a for a in A[max(0, P - 1): i]]

    if not B:
        return True
    cnt = sum(B) + (P - 1) * M + (N - i) * M
    return min(B) >= 0 and cnt >= M * V

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

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    B = A[N - P]
    low, high = -1, N
    while high - low > 1:
        mid = (low + high) // 2
        if mid >= N - P: high = mid
        elif A[mid] + M < B: low = mid
        else:
            border = A[mid] + M
            room = 0
            for i in range(N - P + 1):
                if i != mid: room += min(M, max(0, border - A[i]))
            if room >= max(0, V - P) * M: high = mid
            else: low = mid
            #print(mid, room)
    print(N - high)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def check_pickedup(N: int, M: int, V: int, P: int, A: list, accum_score: list, i: int) -> bool:
    th_score = A[P-1]
    if A[i] >= th_score:
        return True
    sum_surplus = (accum_score[i-1] - (accum_score[P-2] if P-2 >=0 else 0)) - ((i-1)-(P-2))*A[i]
    #print('i: ', i)
    #print('th_score: ', th_score)
    #print('sum_surplus: ', sum_surplus)
    #print('th_score - A[i]: ', th_score - A[i])
    if th_score - A[i] <= M and sum_surplus <= M*(N-V):
        return True
    return False

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    
    A.sort(reverse=True)
    
    accum_score = [A[0]] * N
    for i in range(1, N):
        accum_score[i] = accum_score[i-1] + A[i]
    
    # Reduce N-V scores each judge
    ans = 0
    was_checked = {}
    for i, a in enumerate(A):
        # Check a will be picked up
        if a in was_checked:
            ans += 1
            continue
        if check_pickedup(N, M, V, P, A, accum_score, i):
            ans += 1
            was_checked[a] = True
        else:
            break
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys
import random
import itertools
import math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt


def LI(): return list(map(int, input().split()))


def LF(): return list(map(float, input().split()))


def LI_(): return list(map(lambda x: int(x)-1, input().split()))


def II(): return int(input())


def IF(): return float(input())


def LS(): return list(map(list, input().split()))


def S(): return list(input().rstrip())


def IR(n): return [II() for _ in range(n)]


def LIR(n): return [LI() for _ in range(n)]


def FR(n): return [IF() for _ in range(n)]


def LFR(n): return [LI() for _ in range(n)]


def LIR_(n): return [LI_() for _ in range(n)]


def SR(n): return [S() for _ in range(n)]


def LSR(n): return [LS() for _ in range(n)]


mod = 1000000007
inf = 1e10

#solve


def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (p - 1) * m + (n - x) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p - 1, x):
            tmp += t - a[i]
        return tmp >= m * v
        
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys

def f(x):
    if a[x]+m<a[p-1]: return 0
    elif v<=p+n-1-x: return 1
    able=(p+n-1-x)*m
    able+=sum([a[x]+m-a[k] for k in range(p-1,x)])
    if able>=m*v: return 1
    else: return 0

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

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>0:
    if r-l==1 and f(l)==1 and f(r)==0: break
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(l+1)

Submission status: Accepted

Solution code:
# tokenakatta ...
def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    l = 0
    r = N - P + 1
    while l != r:
        k = (l + r)//2
        m = P * M + k * M
        t = A[k] + M
        if t < A[N - P]:
            l = k + 1
            continue
        for i in range(k+1, N-P+1):
            m += t - A[i]
        if m < M * V:
            l = k + 1
        else:
            r = k
    return N - r
print(main())

Submission status: Accepted

Solution code:
def judge(a, acc, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p + n - i)*m + (a[i-1] + m)*(i - p) - (acc[i-2] - acc[p-2])
    return check >= m*v

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

a.sort(reverse=True)
acc = [0] * (n+1)
for i in range(n):
    acc[i] = a[0] if i == 0 else a[i] + acc[i-1]
ng = n + 1
ok = 0

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

Submission status: Accepted

Solution code:
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p + n - i)*m
    for j in range(p, i):
        check += a[i-1] + m - a[j-1]
    return check >= m*v

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

a.sort(reverse=True)
ng = n + 1
ok = 0

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

Submission status: Accepted

Solution code:
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p + n - i)*m
    for j in range(p, i):
        check += a[i-1] + m - a[j-1]
    return check >= m*v

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

a.sort(reverse=True)
ng = n + 1
ok = -1

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

Submission status: Accepted

Solution code:
def binsearch(l, r, fn):
    while r - l > 1:
        m = (l + r) // 2
        if fn(m):
            l = m
        else:
            r = m
    return l

def main():
    N, M, V, P = list(map(int, input().split()))
    A = sorted(list(map(int, input().split())), reverse=True)
    def ss(k):
        t = A[k] + M
        if A[P - 1] > t:
            return False
        r = M * (V - (N - k) - (P - 1))
        for i in range(P - 1, k):
            r -= min(M, max(0, t - A[i]))
            if r <= 0:
                return True
        return False
    return binsearch(P - 1, N, ss) + 1


print(main())

Submission status: Accepted

Solution code:
import sys
class IoTool:  # a tool for input redirection 
    DEBUG = 0
    def _reader_dbg():
        with open('./input.txt', 'r') as f:
            lines = f.readlines()
        for l in lines: yield l.strip() 
    def _reader_oj():  
        return iter(sys.stdin.read().split('\n'))
    reader = _reader_dbg() if DEBUG else _reader_oj()
    def read(): return next(IoTool.reader)

input = IoTool.read

def main():
    n, m, v, p = map(int, input().split())
    val = list(map(int, input().split()))
    val.sort(reverse=True)
    ans, presum, v = p, val[p-1], v-p+1
    for i in range(p, n):
        if val[i] + m < val[p-1] or (val[i] + m)*(i-p+1) - presum < m*(v-1-(n-i-1)):
            break
        presum += val[i]
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def is_possible(idx):
    if idx < P:
        return True
    if A[P - 1] <= A[idx]:
        return True
    if A[idx] + M < A[P - 1]:
        return False
    t = P * M
    for i in range(P - 1, idx):
        t += A[idx] + M - A[i]
    for i in range(idx + 1, N):
        t += M
    if t < M * V:
        return False
    return True


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

Submission status: Accepted

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

def func():
    S = 0
    c = 0
    for i in range(P-1, N):
        if A[i] + M >= A[P-1] and (V - (P-1) - (N-i-1) - 1) * M <= S + (A[i] + M - A[P-1]) * c:
            pass
        else:
            return i
        S += A[P-1] - A[i]
        c += 1
    return N
print(func())

Submission status: Accepted

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

def check(x):
    if x<p:
        return True
    if al[p-1]>al[x]+m:
        return False

    s = 0
    for i in range(n):
        if i<p-1:
            s += m
        elif p-1<=i<x:
            s += al[x]+m-al[i]
        else:
            s += m
    return s>=m*v

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

Submission status: Accepted

Solution code:
import bisect
n,m,v,p=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
ok=n#idx
ng=-1
def solve(x):
    if bisect.bisect_right(l,l[x])>=n-p+1:
        return 1
    lx=l[x]+m
    lxi=bisect.bisect_right(l,lx)-1
    if lxi<=n-p-1:
        return 0
    #n-p-1<lxi
    f=0
    for i in range(n):
        if i<=x or i>n-p:
            f+=m
            continue         
        else:
            f+=min(lx-l[i],m)
    if f>=v*m:
        return 2
    else:
        return 0
#for i in range(n):
    #print(solve(i))
while ok-ng>1:
    x=(ok+ng)//2
    if solve(x):
        ok=x
    else:
        ng=x
    #print(x)
print(n-ok)

Submission status: Accepted

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

A.sort(reverse=True)
p = A[P-1]

#X番目の問題に可能性があるかどうか(0-indexed)
def f(X):
    x = A[X]
    if x + M < p: return False
    votes = M*V
    votes -= M * (P-1)
    for i in range(P-1,N):
        votes -= min(M, x + M - A[i])
    return votes <= 0

ok = 0
over = N
while over - ok > 1:
    mid = (over + ok) // 2
    if f(mid): ok = mid
    else: over = 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
"""
indexはN-1までなので、ngはN-1の気がするのだが......
[ok,ng)か？
*****  okは条件を満たす（選ばれうる）し、ngは条件を満たさない（選ばれない）ので、ng=N-1とすると、そこを最初からきりすててしまうから！  *****
最終的なokとngの境界で選ばれるか選ばれないか分かれ、境界の先は単調に選ばれうる
"""
ng = N 
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    curr_max = A[mid] + M

    if curr_max < A[P-1]:
        ng = mid
        continue

    cnt = 0
    # midと上位P-1位に＋Mした分
    cnt += M + (P-1) * M
    for i in range(P-1, N):
        if i == mid: continue

        cnt += min(M, max(0, curr_max - A[i]))

    if cnt >= 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
    curr_max = A[mid] + M

    if curr_max < A[P-1]:
        ng = mid
        continue

    cnt = 0
    # midと上位P-1位に＋Mした分
    cnt += M + (P-1) * M
    for i in range(P-1, N):
        if i == mid: continue

        cnt += min(M, max(0, curr_max - A[i]))

    if cnt >= M*V:
        ok = mid
    else:
        ng = mid

print(ok + 1)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect

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

    low, high = -1, N
    while high - low > 1:
        mid = (low + high) //2
        point = A[mid] + M
        if point < border: low = mid
        elif mid >= N - P: high = mid
        else:
            space = (mid + P) * M
            for i in range(mid + 1, N - P + 1 ): space += point - A[i]
            if space >= M * V: high = mid
            else: low = mid
    print(N - low - 1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
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 r-l > 1:
        i = (l+r) >> 1
        ai = a[i]
        aim = ai+m
        ri = bisect.bisect_right(a,aim)
        if n-ri >= p:
            l = i
            continue
        cnt = 0
        for j in range(n-p+1):
            if i == j:
                continue
            cnt += min(m,aim-a[j])
        if cnt >= m*(v-p):
            r = i
        else:
            l = i
    print(n-r)
    return

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
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 r-l > 1:
        i = (l+r) >> 1
        ai = a[i]
        aim = ai+m
        ri = bisect.bisect_right(a,aim)
        if n-ri >= p:
            l = i
            continue
        cnt = 0
        for j in range(n-p+1):
            if i == j:
                continue
            cnt += min(m,max(0,aim-a[j]))
        if cnt >= m*(v-p):
            r = i
        else:
            l = i
    print(n-r)
    return

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

Submission status: Accepted

Solution code:
"""
AtCoder Grand Contest 041  B - Voting Judges


N個の問題があり、M人がそれぞれV問に１点足していく。同じ人が同じ問題に点は入れられない。
全員が点を入れた後、得点の大きいものからP個選ばれる。
選ばれうる可能性のある問題の個数を考える。

例えば1,2,3,4,5,6,7,8,9,10として、３人が４問に加点するのを考える。その後４問が選ばれるとする
５がえらばれうるか考えてみる。
５に３点入れて、残りは５未満に足しておけば８に並ぶので選ばれうる。
上位一位にいくより上位４位にはいる方が縛りが緩そう。１～４のどこにいてもいいので。

なので、とりあえず４位になることを目標とする。
４位になるには上位３位の10,9,8には負けててもいいが、少なくとも７に並ぶ必要がある。
また、投票者が３人なので、多くても＋３しかされない。

とりあえず５にとって最善の＋３した場合を考える。
このときに７に＋２とか６に＋３とかされて８を上回られると選ばれない。
なので、５的には、自分に最大に点を割り振って、残りは順位に影響ないところで使いつぶすのが嬉しい。

１～４について、＋３しても順位に影響ないから、これらには割り振る。
８～１０についても、５的には４位に入ることができたら問題ないので、これらについても＋３して問題ない。
ついで、６，７であるが、これが９になると５は勝てないので、こいつらには＋した結果でも８にとどまってほしい。

こんな感じで、P位になるためにある数字に最大に割り振って、残りを使いつぶす。
で、全体でM*V点持っていて、使いつぶしたときにこれを使い切っていなければ、今回でいうところの６とか７に振るしかなくなる。
そのときは選ばれる可能性がない。
みたいな？

"""
import bisect


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:
    mid = (l + r) // 2

    curr_max = A[mid] + M
    if curr_max < A[P-1]:
        r = mid
        continue

    cnt = 0
    # P位になれればよいので、P位以降に対して見る
    for i in range(P-1, N):
        if i == mid:
            continue
        # A[mid]以下の値は＋MしてOK、それ以外はcurr_maxと同じ値までは＋してよい
        cnt += min(M, max(0, curr_max - A[i]))

    # 上位P-1とA[mid]に振った分をのぞいて、都合いい感じに振ったものが、余りを上回れば、選ばれうる
    if cnt >= M * (V - P):
        l = mid
    else:
        r = mid

# lがギリギリ選ばれるもののインデックス（下限）なので、+1して要素数というか個数にする
print(l + 1)

Submission status: Accepted

Solution code:
N, M, V, P = (int(i) for i in input().split())
A = [int(i) for i in input().split()]
A.sort()
As = [0]*(N+1)
for i in range(N):
    As[i+1] = A[i] + As[i]

ans = 0
b = A[N-P]
for i in range(N):
    if b-A[i] > M:
        continue
    if P+i>=V:
        ans += 1
    else:
        r = As[N-P+1]-As[i+1]-A[i]*(N-P-i)
        if r <= (N-V)*M:
            ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

A = np.array(A + [10 ** 10], np.int64)
A.sort()
A = A[::-1]
left = P
right = N + 1
# i番目の問題が採用される可能性があるか否や
while right - left > 1:
    mid = (right + left) // 2
    score = A[mid] + M
    if score < A[P]:
        right = mid
        continue

    s = np.minimum(score - A[P:], M)
    if np.sum(s) >= M * (V - (P - 1)):
        left = mid
    else:
        right = mid

print(left)