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:
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):
    #ddprint("foo {} call ".format(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
    #ddprint("r {}".format(r))
    if r>p:
        return False
    #q = v-n+i-r
    #if q<=0:
    #    return (a[i]+m >= a[p])
    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))
        #ddprint("ret {} i {} s {} ai {} m {} acm {} acp {} v-n+i-s {}".format(ret,i,s,a[i],m,acc[i-1],acc[s-1],v-n+i-s))
        if ret:
            ok = True
            break
    #ret = ( (i-p)*(a[i]+m) >= max(a[p], acc[i-1]-acc[p-1]+m*q) )
    #ddprint("foo {} returns {}".format(i,ok))
    return ok

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

Submission status: Accepted

Solution code:
# この提出を含めて
# この時間までに提出している私のすべてのBの提出は嘘解法でした

# ランダムに作成した下記のテストケースで解答が不一致でした

# 6 2 5 3
# 6 4 3 2 1 1

# https://atcoder.jp/contests/agc041/submissions/9179921
# 4

# 自分
# 6

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:
            # 上位P-1に毎回加算して、
            # rest-(P-1)人に対し、最大値を上げないようにして、均等に割り振る
            rng = N - ika - (P - 1)  # 加算先候補数
            times = V - (P - 1) - ika  # M人のjudgeがtimes回加算する

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
            #print(a[i], target, br, dif, a, acm)
            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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np

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

Submission status: Accepted

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np
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()

Submission status: Accepted

Solution code:
import sys

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


# mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np




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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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
    #print(intg,m*(v-1))
    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))
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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:
            # 上位P-1に毎回加算して、
            # rest-(P-1)人に対し、最大値を上げないようにして、均等に割り振る
            rng = N - ika - (P - 1) # 加算先候補数
            times = V - (P - 1) - ika # M人のjudgeがtimes回加算する

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

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:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()


def check(x):
    if x > n - p:
        return True

    for i in range(x + 1, n - p + 1):
        if a[x] + m < a[i]:
            return False

    if v - x - p > 0:
        cnt = 0
        for i in range(x + 1, n - p + 1):
            cnt += min((a[x] + m) - a[i], m)

        if (cnt // (v - x - p)) >= m:
            return True
        else:
            return False
    else:
        return True


lb = -1  # False
ub = n - 1  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

# print(a)
# print(lb, ub)
ans = n - ub
print(ans)

Submission status: Accepted

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

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-1:]
        if b[0] < 0:
            return False
        rest = v-n+len(b)
        if rest <= 0:
            return True

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    print(n-b_search(0, n-1, value))


main()

Submission status: Accepted

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

def ok(x):
    if x + M < A[P-1]:
        return False
    sc = M * V
    for a in A[:P-1]:
        sc = sc - M
    for a in A[P-1:]:
        sc = sc - min(M, x + M - a)
    return sc <= 0

l, r = -1, N
while r - l > 1:
    m = l + (r - l) // 2
    if not ok(A[m]):
        r = m
    else:
        l = m
print(r)

Submission status: Accepted

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

a = sorted(a)

sm = sum(a[:n-p+1])

for k in range(n-p+1):
    sm -= a[k]
    if a[k]+m < a[n-p]:
        continue
    elif (n-p-k)*(a[k]+m) - sm +(p+k)*m < v*m:
        continue
    else:
        print(n-k)
        exit()

Submission status: Accepted

Solution code:
def main():
    n, m, v, p = list(map(int, input().split()))
    a = sorted(list(map(int, input().split())))
    # print(a)

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-1:]
        #print(b)
        if b[0] < 0:
            return False
        rest = v-n+len(b)
        if rest <= 0:
            return True
        #print(rest)

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        #print(d, e)
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    #print(value(1))

    print(n-b_search(0, n-1, value))


main()

Submission status: Accepted

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

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

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

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 = map(int,input().split())
    A = [int(x) for x in input().split()]
    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()

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-1):
        return True

    points = a.copy()

    points[i] += m

    adding_point = m*v-m*p

    if points[i] < points[p-1]:
        return False

    j = n-1
    while adding_point > 0:

        if j <= p-2:
            return False

        if i == j:
            j -= 1
            continue
        adding_point -= min(m, points[i]- points[j])

        j -= 1

    return True

if isok(n-1):
    print(n)
    exit()

ok = p-1
ng = n-1

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

    if isok(mid):
        ok = mid
    else:
        ng = mid
print(ok+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()

OK=N-P
NG=-1

while OK-NG>1:
    
    mid=(OK+NG)//2
    #print(OK,NG,mid)

    if (P-1)+mid+1>=V:
        if A[-P]<=A[mid]+M:
            OK=mid
        else:
            NG=mid

    else:
        V2=V-(P-1)-mid
        A2=A[mid:N-P+1]

        #print(V2,A2)

        BASE=A2[0]+M
        k=0

        if BASE<A2[-1]:
            NG=mid
            continue
            
        for a in A2[1:]:
            k+=(BASE-a)

        #print(k)

        if k<M*(V2-1):
            NG=mid
        else:
            OK=mid


print(N-NG-1)

Submission status: Accepted

Solution code:
def examA():
    N, A, B = LI()
    ans = inf
    if abs(A-B)%2==0:
        ans = abs(A-B)//2
    cur = min((A+B-1)//2,(2*N-A-B+1)//2)
    ans = min(ans,cur)
    print(ans)
    return

def examB():
    N, M, V, P = LI()
    A = LI(); A.sort()
    maxA = A[N-P]
    sumA = maxA*(N-P)-sum(A[:N-P])
#    print(maxA,sumA)
    l = -1; r = N-P
    while(r-l>1):
        flag = True
        now = (l+r)//2
        c = sumA - (maxA-A[now])
        need = maxA - A[now]
        if need>M:
            flag = False
        q = 0
        for i in range(N):
            if A[i]>=maxA-M+(M-need):
                break
            if i==now:
                break
            q +=maxA-M+(M-need)-A[i]
        if (V-P)*M-(N-P)*(M-need)+q>c:
            flag = False
        if flag:
            r = now
        else:
            l = now
#        print(A[now],c,(V-P)*M-(N-P)*(M-need)+q,q,need)
    ans = N-r
    print(ans)
    return

def examC():
    N = I()
    ans = [["."]*N for _ in range(N)]
    if N%3!=0 and N%2!=0:
        print("-1")
        return
    if N%3==0:
        for i in range(N//3):
            ans[i*3][i*3] = "a"
            ans[i*3][i*3+1] = "a"
        for i in range(N//3):
            ans[i*3+1][i*3+2] = "a"
            ans[i*3+2][i*3+2] = "a"
    else:
        for i in range(N//2):
            for j in range((N+2) // 4):
                ans[i * 2][j * 4] = "a"
                ans[i * 2][j * 4 + 1] = "a"
                ans[i * 2 + 1][j * 4] = "b"
                ans[i * 2 + 1][j * 4 + 1] = "b"
                if j*4+2==N:
                    break
                ans[i * 2][j * 4+2] = "c"
                ans[i * 2][j * 4+3] = "c"
                ans[i * 2 + 1][j * 4 + 2] = "d"
                ans[i * 2 + 1][j * 4 + 3] = "d"
            ans[i*2][i*2] = "e"
            ans[i*2+1][i*2] = "e"
            ans[i*2][i*2+1] = "f"
            ans[i*2+1][i*2+1] = "f"
    for v in ans:
        print("".join(map(str,v)))
    return

def examD():
    return

def examE():
    return

def examF():
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examB()


"""
                for j in range(N // 4):
                    ans[i * 2][j * 4+2] = "a"
                    ans[i * 2][j * 4 +3] = "a"
                    ans[i * 2 +1][j * 4+2] = "b"
                    ans[i * 2 +1][j * 4 +3] = "b"
                for j in range(N // 4):
                    ans[i*2-2][j*4+2] = "c"
                    ans[i*2-1][j*4+2] = "c"
                    ans[i*2-2][j*4 +3] = "d"
                    ans[i*2-1][j*4 +3] = "d"

"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
i8 = np.int64

f = open('/dev/stdin', 'rb')
pin = np.fromstring(f.read(), i8, sep=' ')
N, M, V, P = pin[: 4]
a = pin[4:4 + N]

x = np.arange(N - P)
N -= P - 1
V -= P - 1
a = np.sort(a)[::-1][P - 1:]
top = a[0]
cumsum = np.cumsum(a)[: -1]
a = a[1:]

filter = np.logical_and(a + M >= top, (a + M) * (x + 1) - cumsum - (x + 1 - (N - V))*M >= 0)
print(np.count_nonzero(filter) + P)

Submission status: Accepted

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

A.sort()
sumtab = [0] * (N + 1)
tmp_tab = 0
for i, Ai in enumerate(A):
    tmp_tab += Ai
    sumtab[i + 1] = tmp_tab

l = 0
r = N
while True:
    i = l + (r - l) // 2
    # print("#", l, r, i)
    #
    B = list(A)
    # everyone vote: i
    score_i = A[i] + M
    B[i] += M
    M_tmp = M * (V - 1)
    #
    rslt = False
    # print("#", i, B)
    for j in list(range(N))[::-1]:
        # print("##", j, M_tmp, B)
        if j == i:
            continue # me
        elif j > N - P:
            # make stronger problems stronger as possible
            tmp = min(M, M_tmp)
            #
            M_tmp -= tmp
            B[j] += tmp
        else:
            # make weaker problems weaker as possible
            if A[j] > score_i:
                break
            if A[j] + M <= score_i:
                tmp = min(M, M_tmp)
            else:
                tmp = min(score_i - A[j], M_tmp)
            #
            M_tmp -= tmp
            B[j] += tmp
        #
        if M_tmp <= 0: break
    #
    # print("##", 'e', M_tmp, B)
    if i >= N - P:
        r = i
    elif M_tmp <= 0 and score_i >= B[N - P]:
        r = i
    else:
        l = i + 1
    #
    if l >= r: break
        
print(N - l)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M, V, P = map(int, input().split())
A_list = list(map(int, input().split()))

A_list.sort(reverse = True)
# print(A_list)
ans = P
border = A_list[P - 1]
sum_over_A = border

if P < N:
    before_A = border
    for i in range(P, N):
        if before_A == A_list[i]:
            ans += 1
#             print(1, i, A_list[i])
        elif border <= (A_list[i] + M):
            over_V = V - (P + N - (i + 1))
            if over_V > 0:
                sum_over = sum_over_A + over_V * M
                round_up_sum_over = -(-sum_over // (i + 1 - P))
                if A_list[i] + M >= round_up_sum_over:
                    ans += 1
#                     print(2, i, A_list[i], round_up_sum_over, over_V, sum_over)
                else:
#                     print("NG", i, A_list[i], round_up_sum_over, over_V)
                    break
            else:
                ans += 1
#                 print(3, i, A_list[i])
            before_A = A_list[i]
        else:
            break
        sum_over_A += A_list[i]
print(ans)

Submission status: Accepted

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

A.sort()
Cumsum=list(itertools.accumulate(A))
Kijun=A[n-p]
Ans=n
for i in range(n):
   L=0
   if A[i]+m>=Kijun:
       b1=min(bisect.bisect_left(A, A[i]+m),n-p)
       b2=min(bisect.bisect_right(A, A[i]+m),n-p) 
       L=m*(i+1)+(A[i]+m)*(b1-i)-(Cumsum[b1]-Cumsum[i])+m*(n-b2-1)
       if L>=m*v:
            break

print(n-i)

Submission status: Accepted

Solution code:
from sys import exit

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))


def main():
    n,m,v,p = mi()
    atmp = li()
    
    atmp = list(sorted(atmp))
    a = []
    ad = []

    for i in range(n):
        a.append([atmp[i],i])
        ad.append([atmp[i],i])


    # for i in range(v):
    #     a[i][0]+=m

    a = list(sorted(a, key=lambda x : x[0]))#, reverse=True))
    #print(a)


    l = 0
    r = n-1
    mid = (r-l)//2+l

    while r-l >= 2:
        mid = (r-l)//2+l
        #print(mid,l,r)

        if mid >= n-p:
            r = mid
            continue

        tmpmax = a[mid][0]+m
        tmp = m*(v-1)

        if tmpmax < a[n-p][0]:
            l = mid
            continue

        #print(tmpmax)

        flag = False
        for itmp in range(n):
            i =n-1-itmp
            if i == mid:
                continue
            if itmp <= p-2:
                tmp-=m
            else:
                if a[i][0] > tmpmax:
                    l = mid
                    flag = True
                    break
                tmp-=(min(tmpmax-a[i][0],m))
                #print(i,(min(tmpmax-a[i][0],m)))
        if flag:
            continue
        else:
            #print("tmp",tmp)
            if tmp >0:
                l = mid
            else:
                r = mid
    
    if r == 1:
        mid = 0
        tmpmax = a[mid][0]+m
        tmp = m*(v-1)

        if tmpmax < a[n-p][0]:
            l = mid

        #print(tmpmax)

        flag = False
        for itmp in range(n):
            i =n-1-itmp
            if i == mid:
                continue
            if itmp <= p-2:
                tmp-=m
            else:
                if a[i][0] > tmpmax:
                    l = mid
                    flag = True
                    break
                tmp-=(min(tmpmax-a[i][0],m))
                #print(i,(min(tmpmax-a[i][0],m)))
        else:
            #print("tmp",tmp)
            if tmp >0:
                l = mid
            else:
                r = mid




    print(n-r)



    
main()

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A, reverse=True)
target = A[p - 1]
s = 0
for i in range(p - 1, n):
    s += A[i]
ans = p

B = [0] * n
B[p - 1] = A[p - 1]

count = 0
for i in range(p - 1, n - 1):
    if A[i] == A[i-1]:
        count += 1
        B[i + 1] = B[i]
    else:
        B[i + 1] = B[i] + A[i + 1] + count * A[i]
        count = 0

if v <= p:
    for i in range(p, n):
        if target - A[i] <= m:
            ans += 1
    print(ans)
    exit()
else:
    ans -= 1
    lim = m * (n - v)
    for i in range(p - 1, n):
        if i == 0:
            ans += 1
        else:
            temp = B[i - 1] - (i - p + 1) * A[i]
            if A[i] == A[i - 1] or (temp <= lim and target - A[i] <= m):
                ans += 1
            else:
                print(ans)
                exit()
    print(ans)
    exit()

Submission status: Accepted

Solution code:
# coding: utf-8
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
A_wa=[A[0]]

for i in range(1,N):
    A_wa.append(A_wa[i-1]+A[i])
A_wa.append(0)
def bin_isOK(index):
    if A[index]+M < A[N-P]:
        return False
    # print("index:{}".format(index))
    # print("f1:{}".format((A[index]+M)*(N-P-index+1) - (A_wa[N-P] - A_wa[index-1])))
    # print("f2:{}".format(V*M-M*(P-1+index)))
    if (A[index]+M)*(N-P-index+1) - (A_wa[N-P] - A_wa[index-1]) >= V*M-M*(P-1+index):
        return True
    else:
        return False


def binary_search():
    ng = -1
    ok = N-P

    while abs(ok - ng) >1:
        # print("!")
        mid = (ok + ng)//2

        if bin_isOK(mid):
            ok = mid
        else:
            ng = mid
    
    return ok

# print(A)
# print(A_wa)
# print(A[N-P])

print(N-binary_search())

Submission status: Accepted

Solution code:
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
#print(a)
def adopt(x):
    global a,n,m,v,p
    b=a[x]+m
    if b<a[0]:
        return False
    al=v*m
    al-=(n-x)*m
    if al<=0:
        return True
    s=x*b-sum(a[:x])
    #print(al)
    #print(s)
    if al>s:
        return False
    else:
        return True

while l+1<r:
    #print()
    #print(str(l)+" "+str(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 bisect
N,M,V,P= map(int,input().split())
A = list(map(int,input().split()))

A.sort()
B = [0]*N
B[0] = A[0]

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

#print(A)
#print(B)
mn = 0 # NG
mx = N-1 # OK
while True:
    k = (mn+mx)//2
    #print(mn,mx,k)
    c = A[k]
    c += M
    p = bisect.bisect_right(A,c)
    flag = False
    #print("k",k)
    #print("c",c)
    #print("p",p)
    ALL = V*M
    ALL -= (k+1)*M # left
    ALL -= (P-1)*M # right
    if N-P < p:
        if ALL <= 0:
            flag = True
        #print("ALL",ALL)
        #print(N-P-k,B[N-P]-B[k])
        res = c*(N-P-k) - (B[N-P] - B[k])
        #print("res",res)
        if ALL <= res:
            flag = True
    #print("flag",flag)
    if mx - mn == 1:
        if flag:
            mx = k
        else:
            mn = k
        break
    if flag:
        mx = k
    else:
        mn = k
#print(mn,mx)
print(N-mx)