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: Wrong Answer

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: Wrong Answer

Solution code:
from bisect import*
from itertools import*
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
a=[-x for x in a]
acc=list(accumulate(a))
ppp=acc[p-2]
if p>=v:
	print(bisect_left(a,a[p-1]+m+0.5))
	exit()
l=bisect(a,a[p-1]+0.5)-1
r=n
while r-l>1:
	mid=(l+r)//2
	amid=a[mid]
	bl=bisect_left(a,amid+0.5)-1
	bll=bisect_left(a,amid-0.5)-1
	lim=v-(p-1)-(n-1-bll)
	if (-amid+m)*(bll-p+2)>=((ppp-acc[bll])+lim*m):
		l=mid
	else:
		r=mid
print(r)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
count=p
'''
if p+v<=n:
    for i in range(n-p):
        idx=bisect.bisect_right(a,a[i]+m)
        print(i,a[i],idx,n-p)
        if idx>=n-p:
            count+=1
    print(count)
    sys.exit()
'''
s=[0]*n
s[0]=a[0]
for i in range(1,n):
    s[i]=s[i-1]+a[i]

def search(res,i):
    mn=-1
    mx=n-1
    buf=0
    while mx-mn>1:
        buf=(mx+mn)//2
        #print(res,s[buf]-s[i]-(buf-i)*a[i],i)
        if res>=s[buf]-s[i]-(buf-i)*a[i]:
            mn=buf
        else:
            mx=buf
    return mn


for i in range(n-p):
    k=0
    idx=bisect.bisect_right(a,a[i]+m)-1
    if idx>v:
        buf=(a[i]+m)*(idx-v+1)-s[idx]+s[v-1]
        k=search(buf,i)-i
        #print(buf,k)
    idx1=bisect.bisect_left(a,a[i],0,v)
    #print(a[i]+m,max([idx-v+1,0]),idx1,k,max([idx-v+1,0])+idx1+k)
    if max([idx-v+1,0])+idx1+k>=n-p:
        count+=1
print(count)

Submission status: Wrong Answer

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: Wrong Answer

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)
    cum = defaultdict(int)
    c = 0
    for i in A[:P]:
        c +=1
        if cum[maxA-i]:
            cum[maxA-i] +=1
        else:
            cum[maxA-i] =c
    c = 0
    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
        if (V-P)*M-(N-P)*(M-need)+cum[maxA-A[now]-(M-need)]>c:
            flag = False
        if flag:
            r = now
        else:
            l = now
#        print(A[now],c,(V-P)*M-(N-P)*(M-need),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: Wrong Answer

Solution code:
import sys
import bisect
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
count=p
'''
if p+v<=n:
    for i in range(n-p):
        idx=bisect.bisect_right(a,a[i]+m)
        print(i,a[i],idx,n-p)
        if idx>=n-p:
            count+=1
    print(count)
    sys.exit()
'''
s=[0]*n
s[0]=a[0]
for i in range(1,n):
    s[i]=s[i-1]+a[i]

def search(res,i):
    mn=-1
    mx=n-1
    buf=0
    while mx-mn>1:
        buf=(mx+mn)//2
        #print(res,s[buf]-s[i]-(buf-i)*a[i],i)
        if res>=s[buf]-s[i]-(buf-i)*a[i]:
            mn=buf
        else:
            mx=buf
    return mn


for i in range(n-p):
    k=0
    idx=bisect.bisect_right(a,a[i]+m)-1
    if idx>v:
        buf=(a[i]+m)*(idx-v+1)-s[idx]+s[v-1]
        k=search(buf,i)-i
        print(buf,k)
    idx1=bisect.bisect_left(a,a[i],0,v)
    #print(a[i]+m,max([idx-v+1,0]),idx1,k,max([idx-v+1,0])+idx1+k)
    if max([idx-v+1,0])+idx1+k>=n-p:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import bisect


# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


n, m, v, p = map(int, input().split())
n += 1
v += 1
a = [-10**20] + list(map(int, input().split()))
a = sorted(a)

def solve(i):
        tmp = a[i] + m
        if i+1 >= v:
            ind = bisect.bisect_right(a, tmp)
            if n - ind < p:
                return True
        if i+1 >= n-p:
            return True
  
        length = v - p - i
        bit = BIT(n)
        #print(i, tmp, length)
        if length <= 0:
            if a[n-p] <= tmp: 
                return True
            else:
                return False
        # 初期化
        for j in range(i+1,n-p+1):
            bit.add(j, j+1, a[j])

        times = 0
        for j in range(i+1, n-p+1)[::-1]:
            tmp_times = tmp - bit.get_val(j)
            if tmp_times < 0:
                return False
            if j+1-length <= i:
                if times >= m: 
                    return True
                else:
                    return False
            bit.add(j+1-length, j+1, tmp_times)
            times += tmp_times
        if times >= m: 
                return True
        else:
                return False

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
#print(a)
d = dd(int)
for x in a: d[x] += 1
#print(d)
ks = sorted(d.keys())
#print(ks)
def check(x):
  b = a + [x + M]
  isit = 0
  for i in range(V):
    if isit == 0:
      b[i] = -float("inf")
      isit = 1
    b[i] += M
  b.sort()
  c = 0
  t = 0
  for i in range(N, -1, -1):
    if b[i] != t:
      if c >= P: break
      if b[i] <= x + M: return True
      t = b[i]
    c += 1
  return False
ok = N
ng = -1
m = (ok + ng) // 2
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(a[m]):
    ok = m
  else: ng = m
res = N
if check(ng): ng -= 1
for k in ks:
  if k <= ng: res -= d[k]

print(res)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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

ap = a[p-1]
ans = 0
gap = 0
for i,ai in enumerate(a):
    if i < p:
      ans += 1
      continue
      
    elif i < (n - v + p):
        if (ai + m) >= ap:
            ans += 1
            gap += ap - ai
            continue
      
    else:
        amari = max(0, m * (v - n + i - p + 1) - gap)
        if  (ai + m) >= ap + math.ceil((amari / (i - p))):
            ans += 1
            gap += ap - ai
            continue
        else:
            gap += ap - ai

print(ans)

Submission status: Wrong Answer

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
    wall = -1
    while a[i]>=a[index]+m:
        if a[i]>=a[index]+m+1:
            wall = i
        i+=1
    if i>index:
        return True
    intg = 0
    while i<index:
        intg += a[index] + m - a[i]
        i+=1
    intg += (len(a)-1-index)*m + min(v,p - wall)*m
    #print("intg = ",intg ,m*(v-1) )
    return intg >= m*(v-1)

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: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
B=[A[0]]
for i in range(n-1):
  B.append(B[i]+A[i+1])
#print(B)
ok = -1
ng = n
while ng-ok > 1:
  mid = (ok+ng) // 2 # 平均(小数切り捨て)
  #print(mid)
  if mid<p:
    ok=mid
    #print(0)
  elif n-(mid+1)+p>=v:
    if A[p-1]<=A[mid]+m:
      ok=mid
      #print(1)
    else:
      ng=mid
      #print(2)
  else:
    if A[mid]+m>=A[p-1]:
      a=m*(v-n-p+mid+1)
      b=A[mid]+m
      if (mid+1-p)*b-(B[mid-1]-B[p-2])>=a:
        ok=mid
        #print(3)
      else:
        ng=mid
        #print(4)
    else:
      ng=mid
      #print(5)
print(ok+1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

################ DANGER ################
test = ""
#test = \
"""
6 1 2 2
2 1 1 3 0 2
ans 5
[0, 1, 1, 2, 2, 3]
"""

"""
6 1 5 2
2 1 1 3 0 2
ans 3
[0, 1, 1, 2, 2, 3]
"""

"""
10 4 8 5
7 2 3 6 1 6 5 4 6 5
ans 8
[1, 2, 3, 4, 5, 5, 6, 6, 6, 7]
"""
########################################
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
########################################  
    
n, m, v, p = map(int, input2().split())
aa = sorted(map(int, input2().split()))

#print(n, "m=", m, "v=", v, "p=", p)
#print(aa)

fmin = aa[n - p]
fmindex = aa.index(fmin)
fkouho = aa[fmindex:]
nkouho = aa[:fmindex]

#print(nkouho, fkouho)

if len(nkouho) + 1 > v:
    nkouho2 = nkouho[:len(nkouho) - v] + \
    [i + m for i in nkouho[len(nkouho) - v:]]
    print(len([i for i in nkouho2 if i > fmin - 1]) + len(fkouho))
    
else:
    print(len([i for i in aa if i + m > aa[-1] - 1]))

Submission status: Wrong Answer

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

now = 1
get = 0
while now < p:
	if a[now] != a[get]:
		get = now
	now += 1

limit = n
while now < n:
	vv = max(v - get - (n-now), 0)
	total = sum(a[get:now])
	total += m*vv
	if (total//(now-get)) > a[now]+m:
		limit = now
		break
	elif (total//(now-get)) == a[now]+m:
		if (total - (total//(now-get))*(now-get)) >= p-get:
			limit = now
			break
	now += 1
print(limit)

Submission status: Wrong Answer

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] + 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: Wrong Answer

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

S = tuple(reversed(sorted(A))) #O(N)

cnt = 0
memo = {}
sum_memo = {}
su = 0

for n, i in enumerate(S): # Loop O(N)
#     if i in memo.keys():
#         rank = memo[i]
#     else: 
#         rank = S.index(i)
#         memo[i] = rank
    rank=1
    if n >= P - 1:
        su += S[n]
        sum_memo[n] = su
    
    if P > rank:
        cnt += 1
    else:
        xx = P-1 + N - rank
        if xx < V:
            if rank in sum_memo.keys():
                sum_val = sum_memo[rank]
            else:
                sum_val = sum(S[P-1:rank])
                sum_memo[rank] = sum_val
            x = max(math.ceil((sum_val+(V-xx)*M)/(rank-P+1)), S[P-1])
        else:
            x = S[P-1]
                    
        y = i + M
        if x <= y:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

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)
for i in range(p,n):
  h = a[i]+m
  free = v - (p-1) - (n-i)
  d = h * (i-p+1) - (c[i]-c[p-1]) # 余裕
  if d >= free*m:
    ans += 1
print(ans)

Submission status: Wrong Answer

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
from fractions import gcd
#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 input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    N, M, V, P = MI()
    A = MI()
    # N, M, V, P = 10**5, 10*19, 10**4, 10**4
    # A = [i for i in range(N)]
    MAP = {}
    A = sorted(A, reverse=True)
    AH = A[:P]
    AH_min = AH[-1]
    AT = []
    cur = 0
    for i in range(P, N):
        if AH_min == A[i]:
            AH.append(A[i])
        else:
            if A[i] not in MAP:
                MAP[A[i]] = cur
            cur += 1
            AT.append(A[i])
    # print(AH, AT)
    # print('M=', M, 'V=', V)
    ans = len(AH)
    AT_len = len(AT)
    # print(AT, MAP)

    if len(AT) <= V - len(AH) + 1:
        # print(len(AT), V - len(AH) + 1)
        print(ans)
    else:
        _V = V - len(AH) + 1
        # print(_V, V, AH_min)
        for i in range(AT_len):
            if AH_min <= (AT[i] + M):
                remaining = AT_len - (MAP[AT[i]] + 1)
                # print(i, remaining, _V, AH_min, 'MAP', MAP[AT[i]])
                if remaining + 1 >= _V:
                    ans += 1

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
X = A.index(A[P-1])
C = A[X:]
V = V-X
P = P-X
D = list(set(C))

Y = 0
for i in D:
    F = 1
    E = C[:2]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y+C.count(i)
print(X+Y)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a.sort(reverse=True)
a = np.array(a)

def isok(i):


    if i <= (p-1):
        return True

    points = a.copy()

    points[i] += m
    points[:(p-1)] += m

    adding_point = m*v-m*p


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

    j = n-1
    okflag = True
    while adding_point > 0:
        if i == j:
            j -= 1
        else:
            if points[i] < points[j]:
                okflag = False
                break
            adding_point -= min(m, points[i]- points[j])

        if j == p-2:
            okflag = False
            break

        if adding_point <= 0:
            break

        j -= 1

    if okflag == True:
        return True
    else:
        return False


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: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
X = A.index(A[P-1])
C = A[X:]
V = V-X
P = P-X
D = list(set(C))

Y = 0
for i in D:
    F = 1
    E = C[:2]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y
print(X+Y)

Submission status: Wrong Answer

Solution code:
from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
Q = [A[P-1]]
for i in range(P,N):
    b = (V-((P-1)+(N-i)))

        
    if b<=0:
        if A[P-1]<=A[i]+M:
            ans+=1
    else:
        target = A[i]+M
        if target<A[P-1]:
            break
        Q.append(A[i-1])
        sum_Q2 =sum(Q) + b*M
        max_Q2 =ceil(sum_Q2/len(Q)) 
       
        if max_Q2<=target:
            ans+=1
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
import collections

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

if P + V <= N:
  bottom = A[P-1]
  for i in range(P, N):
    if bottom - A[i] > M:
      print(i)
      exit()

for i in range(M):
  for j in range(V):
    A[N-j-1] += 1
    A.sort(reverse=True)

C = collections.Counter(A)
sorted_list = sorted(C.items(), key=lambda x: x[0], reverse=True)

i = 0
count = 0
for a, c in sorted_list:
  if i == P:
    print(count)
    exit()
  count += c
  i += 1

Submission status: Wrong Answer

Solution code:
import bisect


# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)


n, m, v, p = map(int, input().split())
n += 1
v += 1
a = [-10**20] + list(map(int, input().split()))
a = sorted(a)

def solve(i):
        if i+1 >= v:
            tmp = a[i] + m
            ind = bisect.bisect_right(a, tmp)
            if n - ind <= p:
                return True

        tmp = a[i] + m
        length = v - p - i
        bit = BIT(n)
        #print(i, tmp, length)
        if length <= 0:
            if a[n-p] <= tmp: 
                return True
            else:
                return False
        # 初期化
        for j in range(i+1,n-p+1):
            bit.add(j, j+1, a[j])

        times = 0
        for j in range(i+1, n-p+1)[::-1]:
            tmp_times = tmp - bit.get_val(j)
            if tmp_times < 0:
                return False
            if j+1-length <= i:
                if times >= m: 
                    return True
                else:
                    return False
            bit.add(j+1-length, j+1, tmp_times)
            times += tmp_times
        if times >= m: 
                return True
        else:
                return False

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

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a=sorted(a)
#print(a)
ct=-1
c=a[n-p]
d=a.index(c)
if d-(n-v)<0:
    sta=0
else:
    sta=d-(n-v)
for i in range(sta,n-p):#a.index(a[d-(n-v)])
   # if a[i]+m>=a[n-p]:
    #    ct=a.index(a[i])+1
     #   break
    if v>n-p and v+1!=n:
        if a[i]+m>=a[n-p]+m or a[i]+m>=a[v+1]:
            ct=a.index(a[i])+1
            break
       # elif a[i]+m<a[n-p]+m and a[i]+m<a[v+1]:
        #    ct=-1
    elif v>n-p and v+1==n:
        if a[i]+m>=a[n-p]+m:
            ct=a.index(a[i])+1
            break
        #elif a[i]+m<a[n-p]+m:
         #   ct=-1
    elif a[i]+m>=a[n-p]:
        ct=a.index(a[i])+1
        break
        #elif a[i]+m<a[n-p]:
         #   ct=-1
#if v-1>=n-p+1:
#print(a.index(a[n-p]))
#else:
if ct==-1:
    print(n-a.index(a[n-p]))
#elif ct==1:
 #   print(n-a.index(a[n-p]))
else:
    print(n-ct+1)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
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 = M*(V-(len(C)-C.index(i)))
    E = C[:C.index(i)]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y+C.count(i)
print(X+Y)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
import bisect
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
count=p
'''
if p+v<=n:
    for i in range(n-p):
        idx=bisect.bisect_right(a,a[i]+m)
        print(i,a[i],idx,n-p)
        if idx>=n-p:
            count+=1
    print(count)
    sys.exit()
'''
s=[0]*n
s[0]=a[0]
for i in range(1,n):
    s[i]=s[i-1]+a[i]

def search(res,i):
    mn=-1
    mx=n-1
    buf=0
    while mx-mn>1:
        buf=(mx+mn)//2
        #print(res,s[buf]-s[i]-(buf-i)*a[i],i)
        if res>=s[buf]-s[i]-(buf-i)*a[i]:
            mn=buf
        else:
            mx=buf
    return mn


for i in range(n-p):
    k=0
    idx=bisect.bisect_right(a,a[i]+m)-1
    if idx>v:
        buf=(a[i]+m)*(idx-v+1)-s[idx]+s[v-1]
        k=search(buf,i)-i
        #print(buf,s,k,a[i]+m,s[i],idx-v+1,s[idx]-s[v-1],i)
    idx1=bisect.bisect_left(a,a[i],0,v)
    #print(a[i]+m,max([idx-v+1,0]),idx1,k,max([idx-v+1,0])+idx1+k)
    if max([idx-v+1,0])+idx1+k>=p:
        count+=1
print(count)

Submission status: Wrong Answer

Solution code:
import sys
import bisect


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()
    mi = (n - v) * m
    cor_v = 10 ** 20
    inc_v = -1
    while cor_v - inc_v > 1:
        bin_v = (cor_v + inc_v) // 2
        cost = 0
        #条件を満たすcostを全検索
        pp = bisect.bisect_right(a, bin_v)
        b = True
        for i in range(pp + 1, n):
            if a[i] > bin_v:
                if cost + a[i] - bin_v <= mi:
                    cost += a[i] - bin_v
                else:
                    if n - i + 1 >= p:
                        b = False
                    break
        if b:
            if v - pp - 1 < p:
                cor_v = bin_v
            else:
                inc_v = bin_v
        else:
            inc_v = bin_v

    cnt = 0
    for v in a:
        if v >= cor_v:
            cnt += 1
    print(cnt)


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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 = C[:min(N,10)]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y+C.count(i)
print(X+Y)