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: Runtime Error

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
#show_flg=True

ans=0

n,m,v,p=LI()
a=sorted(LI())

def check(x):
    y=min(bisect.bisect(a,a[x]+m),n-1)
    #show('y',y)
    vv=max(v-(n-y+1),0)
    if vv==0 and n-bisect.bisect(a,a[x]+m+1)<p:
        return True
    show('y,a[y],vv=',y,a[y],vv)
    if IsDistributable(m,vv,[a[x]+m - i for i in a[x+1:y][::-1]+a[:x][::-1]]):
        return True
    else:
        return False
    return y

def IsDistributable(M,V,B):
    show('M,V,B=',M,V,B)
    p=M*V
    r=0
    pre=0
    W=len(B)
    for i in range(W):
        if i!=0 and pre==B[i]:
            continue
        
        avl=(B[i]-pre)*(n-i)-r
        p-=avl+r
        r=avl%V
        if V<n-i:
            return False
        pre=B[i]
        if p<=0:return True


# initial value
ok=n-1
ng=-1

while abs(ok-ng)>1:
    mid=(ok+ng)//2
    if check(mid):
        ok=mid
    else:
        ng=mid
ans=ok
show('ans')
print(n-ans)
x=3
show('x,check=',x,check(x))
show('n,m,v,p=',n,m,v,p)
show(a)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
t = 0
i = 0
while t == 0:
  i += 1
  if A[N-P-i] * M >= A[N-P]:
    if V <= N-i :
      true
    else:
      if A[N-P] * (i-1) - sum(A[N-P-i+1:N-P]  >= M * (V-N+i-1):
        true
      else:
        t = 1
  else:
      t = 1
print(P + i - 1)

Submission status: Runtime Error

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

li = []

  # print(lis)
cnt = 1
now = 0
ans = 0

border = lis[p-1]
li.append(0)
ind = 0
for i in range(n-1):
    if lis[i]!=lis[i+1]:
        now += cnt
        cnt = 1
    else:
        cnt += 1
    if now <= p:
        ind += 1
    li.append(now)

  #print(li)
sa = 0
keykey = 1
key = 0

for i in range(n):
    if i >= p-1:
        sa += lis[i]
        if keykey:
            key = i
        keykey = 0

    if li[i]+1 <= p:
        ans += 1
  #        print(i,1)

    else:
        if lis[i] + m >= border:
            num = (p-1)+(n-li[i]-1)+1
            if num >= v:
                ans += 1
  #                print(i,2)
            else:
                nu = v-num
                if (sa -lis[i])-lis[i]*(i-key) <= (key-nu-1)*m:
                    ans += 1
  #                    print(i,3)
  #                    print(sa,lis[i],i,key,key-nu,m)
                else:
  #                    print(i,4)
  #                    print(sa, lis[i], i, key, key - nu, m)
  #        else:
  #            print(i,5)
    if i != n-1:
        if sa != 0 and lis[i] == lis[i+1]:
            sa -= lis[i]
print(ans)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int,input().split())
A = list(map(int,input().split()))
A = sorted(A)[::-1]
#print(A)
for i in range(N):
    A[i] += M
#print(A)
cnt = 0
std = A[P-1]
ans = 0
for i in range(N):
  if A[i] > std:
    ans += 1
  elif A[i] == std:
    ans += 1
    cnt += 1
  else:
    check = i
    break
#print("ans1",ans)
#print(check)
S = M * (N - V)
#print("S",S)
Sum = 0
for i in range(check,N):
  if A[i] != A[check]:
    std = A[i-1]
  elif i != check and A[i] == A[check]:
    ans += 1
    cnt += 1
    continue
  Sum = Sum + (std - A[i]) * cnt
  #print("Sum",Sum)
  if S >= Sum:
    ans += 1
    cnt += 1
  else:
    break
print(ans)

Submission status: Runtime Error

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]
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break
    
z = sum(A[P-1:y])
for i in range(y,N):
  a = A[i]
  d = a+M
  if x<=d:
    b = N-i+P-1
    c = M*(V-b)
    e = z+c
    f = d*(i-P+1)
    if f>=e:
      ans+=1
      
  z+=a
        
print(ans)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

lim=a[p]
for i in range(p,n):
 if a[i]<lim:
  inx=i
  break

cnt=0
y=inx-1
for x in range(inx,n):
# print(x)
 if a[y]-a[x]>m or inx-count[y]<=v-(n-inx):
  cnt+=1
 y-=1

print(n-cnt)

Submission status: Runtime Error

Solution code:
import sys
import copy
import bisect
import numpy as np

def solve(a,n,N,M,V,P):
    if N-n+1 >= V:
        b = copy.deepcopy(a)
        b[n-1] += M
        tmp = b[n-1]
        b = sorted(b[0:n], reverse=True)
        k = bisect.bisect_left(b,tmp)
        if k<=P-1:
            return True
        else:
            return False
    else:
        V2 = V-N+n-1
        b = copy.deepcopy(a[0:n])
        b[n-1] += M
        tmp = b[n-1]
        b.sort()
        k = bisect.bisect_left(b,tmp)
        k = len(b)-k
        if k+N-1-n < V:
            if P<=k:
                return False
            elif P>=n:
                return True
            else:
                V2 = V-N+n-1
                num = P-k-N+n-1
                aaa = min([V2-1, num])
                if (np.sum(a[n-num:n])+M*aaa+num-1)//num <= tmp:
                    return True
                else:
                    return False
        else:
            b = copy.deepcopy(a)
            b[n-1] += M
            tmp = b[n-1]
            b = sorted(b[0:n])
            k = bisect.bisect_right(b,tmp)
            k = len(b)-k
            if k<=P:
                return True
            else:
                return False

def main():
    N,M,V,P = map(int,input().split())
    a = list(map(int,input().split()))
    a.sort(reverse=True)
    lo = 0
    hi = 2*N
    while lo + 1 < hi:
        cnt = (lo + hi) // 2
        if solve(a,cnt,N,M,V,P):
            lo = cnt
        else:
            hi = cnt

    return hi

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, V-P)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M,V,P=map(int,input().split())
S=list(map(int,input().split()))
score=sorted(S)
t=0
def sorting(a):
  for i in range(M):
    for j in range(V-P):
      a[j]+=1
    a=sorted(a)

  return(a)

for i in range(N):
  score1=copy.deepcopy(score)
  del score1[i]
  for j in range(P-1):
    score1.remove(max(score1))
  if(score[i]+M>=max(sorting(score1))):
      t+=1
print(t)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

lim=a[p]
for i in range(p,n):
 if a[i]<lim:
  inx=i
  break

cnt=0
y=inx-1
for x in range(inx,n):
# print(x)
 if a[y]-a[x]>m or inx-count[y]<v-(n-x):
  cnt+=1
 y-=1

print(n-cnt)

Submission status: Runtime Error

Solution code:
import itertools
import copy

N, M, V, P = [int(x) for x in input().split(' ')]
A = [int(x) for x in input().split(' ')]

patterns = list(itertools.combinations(range(N), V))
combinations = list(itertools.combinations_with_replacement(patterns, M))

apparentlist = []
for combination in combinations:
    A_cal = copy.copy(A)
    for pattern in combination:
        for row in pattern:
            A_cal[row] += 1
    A_sort = sorted(A_cal, reverse=True)
    for i in range(N):
        if A_cal[i] >= A_sort[P-1]:
            apparentlist.append(i)
    apparentlist = list(set(apparentlist))

print(len(apparentlist))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    A.sort()
    # print(A)

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return
    # print(*A, sep=" ")

    # あるスコアYの問題は最初のP問に入れますか？

    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        # inner_right = 3*(10**9)
        inner_right = 10
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, V-P)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

ans = set()
i = 0
while(A[i] >= A[P-1]):
  ans.add(i)
  i += 1
#print(ans)

csum = [0 for _ in range(N)]
csum[P-1] = A[P-1]
for i in range(P,N):
  csum[i] = csum[i-1]+A[i]

for i in range(P,N):
  if A[i]+M >= (csum[i-1]+((V-P)*M-(N-1-i)*M)+1)//(i-(P-1)):
    ans.add(i)
#print(ans)

print(len(ans)-1)

Submission status: Runtime Error

Solution code:
import collections
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
a=sorted(A,reverse=True)
key_num=a[p-1]
k=a.count(key_num)
key_idx=a.index(key_num)+k
c=a[key_idx:]
d=collections.Counter(c)
D=list(d.items)
l=len(set(c))
cnt=0
for i in range(l):
  idx=i+1
  if key_num<=int(D[i][0])+m:
    if v<key_idx+idx:
      cnt+=D[i][1]
print(cnt+key_idx)

Submission status: Runtime Error

Solution code:
from collections import Counter

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

lim=a[p]
for i in range(p,n):
 if a[i]<lim:
  inx=i
  break

cnt=0
y=inx-1
for x in range(inx,n):
 if a[y]-a[x]>m or inx-count[y]<v-a[x]:
  cnt+=1
 y-=1

print(n-cnt)

Submission status: Runtime Error

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

# スコアの降順にソート
a.sort()
a.reverse()

# しきい値になるスコア
t = a[p - 1]
i = p - 1
# 採用可能性あるのが確定した問題のindex
pp = i
while a[i + 1] == t:
    pp += 1
    i += 1

# print(pp)
if (n - (pp + 1)) >= v:
    # v(1人のジャッジが投票できる数)が不確定な問題数以下のとき
    # スコアを不確定な問題にすべて寄せれるので、+mしたときにtを超えたものが採用可能性あり
    result = 0
    for i in range(pp + 1, n):
        if a[i] + m >= t:
            result += 1
    print(result + pp + 1)
else:
    # vが不確定な問題数より大きい場合
    # オーバーした問題数
    over = v - (n - (pp + 1))
    # オーバーした問題数がp以上の場合
    # つまりこのときしきい値が変わる
    # print(over)
    kakutei = n - v
    # print(kakutei)
    t = min(a[kakutei - 1], t + m)
    result = 0
    safe = 0
    for i in range(pp + 1, n):
        if safe < n - v and a[i] + m >= t:
            result += 1
            safe += 1
    print(result + pp + 1)

Submission status: Runtime Error

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

li = []

  # print(lis)
cnt = 1
now = 0
ans = 0

border = lis[p-1]
li.append(0)
ind = 0
for i in range(n-1):
    if lis[i]!=lis[i+1]:
        now += cnt
        cnt = 1
    else:
        cnt += 1
    if now <= p:
        ind += 1
    li.append(now)

print(li)
sa = 0
keykey = 1
key = 0

for i in range(n):
    if i >= p-1:
        sa += lis[i]
        if keykey:
            key = i
        keykey = 0

    if li[i]+1 <= p:
        ans += 1
   #       print(i,1)

    else:
        if lis[i] + m >= border:
            num = (p-1)+(n-li[i]-1)+1
            if num >= v:
                ans += 1
   #               print(i,2)
            else:
                nu = v-num
                if (sa -lis[i])-lis[i]*(i-key) <= (key-nu-1)*m:
                    ans += 1
   #                   print(i,3)
   #                   print(sa,lis[i],i,key,key-nu,m)
                else:
   #                   print(i,4)
  #        else:
  #            print(i,5)
print(ans)

Submission status: Runtime Error

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

def check(num):
    global n, a, m, v, p
    if num >= n - 1 - p:
        return True
    idx = bisect.bisect_left(a, a[num]+m)
    sum_ = sum(a[:idx]) - a[num]
    idx -= 1
    if idx == 0:
        return False
    if a[num] + m >= math.ceil((m * min(v - (p - 1), (n - idx)) + sum_) / idx):
        return True
    else:
        return False

start = n//2
step = math.ceil(n/4)
pre_start = 0
pre_step = 0
while True:
    if step == 1:
        if check(pre_start) != check(start):
            break
    prestart = start
    if check(start):
        start -= step
    else:
        start += step
    pre_step = step
    step = math.ceil(step/2)

for i in range(20):
    i -= 10
    if start + i < 0 or start + i + 1 >= n:
        continue
    if not check(start + i) and check(start + i+1):
        print(n - (start + i) - 1)
        exit()

# ## debug
# l = []
# for i in range(n):
#     l.append(check(i))
# print(l)
# print(n)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int, input().split())
pre = list(map(int, input().split()))
li = sorted(pre)
total = M * V
for i in range(N):
	if li[i] + M >= li[-P]:
		tmp = i + P - 1
		nokori = total - (M * tmp)
		if li[i] + M >= nokori // tmp + li[-P]:
			ans = N - i
			break
print(ans)

Submission status: Runtime Error

Solution code:
import collections

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

cnt = collections.OrderedDict()
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = collections.OrderedDict()
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num < arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    for k in keys:
        i = int(k)
        if i <= num or add_num < i:
            continue
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt.keys())

if select(arr[0]):
    print(N)
    exit(0)

l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
       l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

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

def check(num):
    global n, a, m, v, p
    if num >= n - 1 - p:
        return True
    idx = bisect.bisect_left(a, a[num]+m)
    sum_ = sum(a[:idx]) - a[num]
    idx -= 1
    if idx == 0:
        return False
    if a[num] + m >= math.ceil((m * min(v - (p - 1), (n - idx)) + sum_) / idx):
        return True
    else:
        return False

start = n//2
step = math.ceil(n/4)
pre_start = -1
pre_step = 0
while True:
    if step == 1:
        if check(pre_start) != check(start):
            break
    prestart = start
    if check(start):
        start -= step
    else:
        start += step
    pre_step = step
    step = math.ceil(step/2)

for i in range(20):
    i -= 10
    if start + i < 0 or start + i + 1 >= n:
        continue
    if not check(start + i) and check(start + i+1):
        print(n - (start + i) - 1)
        exit()

# ## debug
# l = []
# for i in range(n):
#     l.append(check(i))
# print(l)
# print(n)

Submission status: Runtime Error

Solution code:
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] + 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 M_tmp <= 0 and score_i >= B[N - P]:
        r = i
    else:
        l = i + 1
    #
    if l >= r: break
        
print(N - l)

Submission status: Runtime Error

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

def check(num):
    global n, a, m, v, p
    if num >= n - 1 - p:
        return True
    idx = bisect.bisect_left(a, a[num]+m)
    sum_ = sum(a[:idx]) - a[num]
    idx -= 1
    if idx == 0:
        return False
    if a[num] + m >= math.ceil((m * min(v - (p - 1), (n - idx)) + sum_) / idx):
        return True
    else:
        return False

start = n//2
step = math.ceil(n/4)
pre_start = -1
pre_step = 0
while True:
    if check(pre_start) != check(start) and step == 1:
        break
    prestart = start
    if check(start):
        start -= step
    else:
        start += step
    pre_step = step
    step = math.ceil(step/2)

for i in range(20):
    i -= 10
    if start + i < 0 or start + i + 1 >= n:
        continue
    if not check(start + i) and check(start + i+1):
        print(n - (start + i) - 1)
        exit()

# ## debug
# l = []
# for i in range(n):
#     l.append(check(i))
# print(l)
# print(n)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
X = A.index(A[P-1])
C = A[X:]
V = V-X
P = P-X
D = list(set(C))
D = [i for i in D if i >= D[len(D)-1]-M]
Y = 0
for i in D:
    F = 1
    E = 1
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y+C.count(i)
print(X+Y)

Submission status: Runtime Error

Solution code:
import collections

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

cnt = collections.OrderedDict()
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = collections.OrderedDict()
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num < arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    s = keys.index(str(num))
    e = keys.index(str(add_num))
    for k in range(s+1, e):
        i = int(keys[k])
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt.keys())

if select(arr[0]):
    print(N)
    exit(0)

l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
       l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

Solution code:
import collections

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

cnt = collections.OrderedDict()
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = collections.OrderedDict()
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num < arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    s = keys.index(num+1)
    e = keys.index(add_num)
    for k in range(s, e):
        i = int(keys[k])
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt.keys())

if select(arr[0]):
    print(N)
    exit(0)

l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
       l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

Solution code:
from collections import Counter
N, M, V, P = map(int,input().split())
A = [int(i) for i in input().split()]
A = sorted(A)[::-1]
cnt = 0
l, r = [], []
for i in range(N-1):
  cnt += 1
  if A[i] == A[i+1]:
    P += 1
  if cnt == P:
    l = A[:i+1]
    r = A[i+1:]
    break
ans = 0
for i in range(len(r[:V])):
  r[i] += 1
  for a in l:
    if r[i] >= a:
      ans += 1
      break
for i in range(len(l)-1, len(l)-(V-len(r))-1, -1):
  l[i] += 1
L = l+r
c = Counter(L)
ans1 = 0
for i in c.values():
  ans1 += i
  if ans1 >= P:
    print(ans1)
    break

Submission status: Runtime Error

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]
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break
    
for i in range(y,N):
  d = A[i]+M
  if x<=d:
    b = N-i+P-1
    c = M*(V-b)
    for j in range(i-1,P-2,-1):
      e = d-A[j]
      c-=(max(0,e))
      if c <=0:
        ans+=1
        break
      elif e<=0:
        break
        
print(ans)

Submission status: Runtime Error

Solution code:
import collections

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

cnt = collections.OrderedDict()
for i in arr:
    stri = str(i)
    if stri in cnt:
        cnt[stri] += 1
    else:
        cnt[stri] = 1
csum = collections.OrderedDict()
_sum = 0
for k, v in cnt.items():
    _sum += v
    csum[k] = _sum

def select(num):
    q = V * M
    add_num = num + M
    if add_num < arr[-P]:
        return False
    q -= (P-1) * M
    if q <= 0:
        return True
    tmp = csum[str(num)]
    q -= tmp * M
    if q <= 0:
        return True
    for i in range(num+1, add_num):
        tmp = add_num - i
        q -= tmp * cnt[str(i)]
        if q<= 0:
            return True
    return False

keys = list(cnt.keys())

if select(arr[0]):
    print(N)
    exit(0)

l = 0
r = len(keys)
while r - l > 1:
    mid = l + r // 2
    if select(mid):
       r = mid
    else:
       l = mid

print(N - csum[str(l)])

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
sort_list = sorted(a, reverse=True)
kijyun_score = sort_list[p-1]
if p >= v:
    count = 0
    for i in range(p, n):
        if kijyun_score - sort_list[i] > m:
            count = i
            break
    print(count)
else:
    y = v - p
    count = 0
    sum_socre = kijyun_score
    k = 1
    b_no = kijyun_score
    for i in range(p, n):
        if b_no == sort_list[i]:
            continue
        else:
            b_no = sort_list[i]:
        if kijyun_score - sort_list[i] > m:
                count = i
                break
        if n - i - 1 < y:
            z = y - n + i + 1
            if k * (m + sort_list[i]) < sum_socre + z * m:
                count = i
                break
        k += 1
        sum_socre += sort_list[i]



    print(count)

Submission status: Runtime Error

Solution code:
n, m, v, p = map(int, input().split())
a = sorted([ i for i in map(int, input().split())])
set_a = list(set(a))

len_dup = len(set_a)

num = 0
for i in range(len_dup-1, 0, -1):
    num += a.count(set_a[i])
    if num >= p:
        break

diff1 = set_a[i] - set_a[i-1]
diff2 = p - (num - a.count(set_a[i]))

if diff1 > m or i == 0:
    print(num)
elif diff2 > 1:
    if diff2 + n - a.count(set_a[i]) > v:
        print(num + a.count(set_a[i-1]))
    else:
        print(num)
else:
    if n - a.count(set_a[i]) > v:
        print(num + a.count(set_a[i-1]))
    else:
        print(num)

Submission status: Runtime Error

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
B = sorted(A,reverse=True)
X = B.index(B[P-1])
C = B[X:]
V = V-X
P = P-X
D = set(C)
D = [i for i in D if i >= D[len(D)-1]-M]
Y = 0
for i in D:
    C2 = C.index(i)
    F = M*(V-(len(C)-C2)
    E = C[:C2]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y+C.count(i)
print(X+Y)