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:
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 >= n - p:
            return True

        tmp = a[i] + m
        if i+1 >= v:
            ind = bisect.bisect_right(a, tmp)
            if n - ind < 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(0, n):
            bit.add(j, j+1, a[j])

        times = 0
        for j in range(n)[::-1]:
            tmp_times = tmp - bit.get_val(j)
            if j+1-length <= i:
                break
            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 bisect

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

def ok(i):
  if i < p:
    return True
  else:
    can = a[i]+m
    c = bisect.bisect_right(b,a[i])
    must = m*(v-(p-1+c))
    for j in range(p-1,n-c):    
      must -= can-a[j] 
    if must > 0:
      return False
    else:
      return True
    
L = -1
U = n
while U-L > 1:
  mid = (L+U)//2
  if ok(mid):
    L = mid
  else:
    U = mid

print(U)

Submission status: Wrong Answer

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

Solution code:
import sys
import bisect
import collections


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
        d = collections.defaultdict(int)
        for i in range(pp + 1, n):
            if a[i] > bin_v:
                d[a[i]]
                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 <= 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:
from sys import stdin
import numpy as np


# noinspection PyShadowingBuiltinsInspection

def main():
    n, m, v, p = [int(x) for x in input().split()]
    all_vote = m * v
    scores = np.array([int(x) for x in input().split()])
    scores.sort()
    minimum_score = scores[n - p]
    # print(scores)
    # print("min: ", minimum_score)
    ans = 0
    red = scores[n-1] - np.array(scores)
    for i in range(n - 1):
        ind = n - 2 - i
        if red[ind] > m:
            red[ind] = m
        red[ind] += red[ind + 1]
    # print(red)
    for i in range(n):
        geta_score = scores[i] + m
        if geta_score < minimum_score:
            continue
        if scores[i] >= minimum_score:
            ans += 1
            continue
        # 自分以下とp-１位までの投票数を抜いた分
        unvoted_n = all_vote - (p + i) * m
        # 自分とp-1位の間の問題数
        unvoted_q = n - p - i
        small_vote = unvoted_n // unvoted_q
        red = unvoted_n % unvoted_q
        # print(i, unvoted_n, unvoted_q, small_vote, red)
        if max(scores[i + red] + small_vote + 1, scores[n - p - 1] + small_vote) <= geta_score:
            ans += 1
        # if unvoted_n > 0 and  != 0:
        #     minimum_score += 1
        # if geta_score >= scores[n - 1]:
        #     buf += red[i + 1] - red[n - (p - 1)]
        # else:
        #     buf += red[i + 1] + (geta_score - 1 - scores[n - 1]) * (n - i - 2)
        # print("ind:", i, "buf:", buf, (v - 1) * m)
        # if buf >= all_vote:
        #     ans += 1
    print(ans)
    return


if __name__ == "__main__":
    main()

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(0,n-p+1):#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:
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

    for i in range(x+1,N-P):
        total_v -= (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: 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)
    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
        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: Wrong Answer

Solution code:
import bisect

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

a.sort()

border = a[-p]

res = bisect.bisect_left(a, border - m)
res2 = bisect.bisect_right(a, border - m)
if res2 + p < v:
    zan = v - (res + p - 1)
    if p != 1:
        a2 = a[res : 1 - p]
    else:
        a2 = a[res:]
    t = 0
    for sa2 in a2:
        t += border - sa2
    if t > zan * m:
        print(n - res)
    else:
        ten = zan * m - t
        j = 0
        l = len(a2)
        while j < l:
            ten -= (a2[j] + m - border) * (l - j)
            if ten <= 0:
                print(n - res - j)
                break
            j += 1
        if j == l:
            print(n - bisect.bisect_left(a, border) + 1)
else:
    print(n - res)

Submission status: Wrong Answer

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

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

l, r = -1, N
# for i in range(N):
#     print(i, ok(A[i]))
while r - l > 1:
    m = l + (r - l) // 2
    if ok(A[m]):
        r = m
    else:
        l = m
print(N-r)

Submission status: Wrong Answer

Solution code:
import sys
from math import factorial
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n, m, v, p = MAP()
a = LIST()
a = sorted(a, reverse=True)
def hantei(i):
    if i < p-1: return True
    if a[p-1] > a[i] + m: return False
    if i <= n-v+p-1: return True
    if (i-p+1)*(a[i]+m)-sum(a[p-1:i]) >= m*(v-p-n+i+1): return True
    return False

right = n-1
left = 0


while right-left > 1:
    mid = (right+left)//2
    if hantei(mid):
        left = mid
    else:
        right = mid

print(right)

Submission status: Wrong Answer

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 = list(set(C))
D = [i for i in D if i >= D[len(D)-1]-M]
Y = []
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 :
        break
B = A.index(i)+C.count(i)
print(B)

Submission status: Wrong Answer

Solution code:
input_sample = iter("""
6 1 2 2
2 1 1 3 0 2
""".split("\n")[1:-1])


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-2:]
        # print(b)

        rest = v-n+len(b)
        # 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: 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(0,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(' '))
An = list(map(int,input().split(' ')))
An.sort(reverse=True)
threadhold_list = [0] * N
theard_num = An[P-1]
theard_idx = 0
sum_An = [0] * N
sum_An[0] = An[0]
for idx,val in enumerate(An):
    if theard_num == val:
        theard_idx = idx
    threadhold_list[idx] = max(0,theard_num-val)
for idx in range(1,N):
    sum_An[idx] = sum_An[idx-1] + An[idx]

#print(An)
#print(threadhold_list)
#print(sum_An)

min_num = 10**10
min_goal_num = 10**10
must_allocation_num = V- (P - 1)
for idx,val in enumerate(An):
    if idx + 1 <= P:
        min_num = min(min_num,val)
        min_goal_num = min(min_goal_num,val)
        continue
    if val == min_num:
        continue
    if threadhold_list[idx] <= M and must_allocation_num <= (N-idx):
        min_num = min(min_num,val)
        continue
    if M < threadhold_list[idx]:
        break 
    if (N-idx) < must_allocation_num:
        sum_foword_nums = sum_An[idx-1] - sum_An[(P - 1-1)]
        allocation_diff =  must_allocation_num - (N-idx)
        diveide_allocation_num = (idx-(P - 1))
        plus_sum = (allocation_diff*M)
        last_num = (sum_foword_nums + plus_sum)/diveide_allocation_num
        candidate_num = An[idx] + M
        if last_num <= candidate_num:
            min_num = min(min_num,val)
            continue

        '''
        sum_foword_nums = sum_An[idx-1]
        allocation_diff = V - (N-idx)
        plus_sum = (allocation_diff*M)
        last_num = (sum_foword_nums + plus_sum)/diveide_allocation_num
        candidate_num = An[idx] + M
        if last_num <= candidate_num:
            min_num = min(min_num,val)
            continue
        '''
    break
if idx == N -1:
    print(N)
else:
    print(idx)

Submission status: Wrong Answer

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque


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

A.sort(reverse=True)


if N <= P:
    print(N)
    exit(0)


baselinen = P - 1
baseline = A[P - 1]

maxn = N - 1
for i, a in enumerate(A):
    if a + M < baseline:
        maxn = i - 1
        break


rem = (V - (P - 1) - (N - maxn - 1))

if rem <= 1:
    print(maxn + 1)
    exit(0)

defin = maxn - rem + 1


space = 0
load = 0
for n in range(baselinen + 1, maxn + 1):
    if load > space + (n - baselinen) * (A[n] + M - baseline):
        break

    space += baseline - A[n]

    if n >= defin:
        load += M

print(n)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().strip().split())
a=map(int,input().strip().split())
a=sorted(a,reverse=True)
minnum = a[p-1]
if v>p:
  b=a[:]
  for i in range(n-v+1,n):
    b[i]+=m
  for i in range(p,n-v+1):
    b[i]+=m//2 if m//2!=0 else 1
  b=sorted(b,reverse=True)
  minnum=b[p-1]
c=p
for i in range(p,n):
  if a[i]+m >= minnum:
    c+=1
print(c)

Submission status: Wrong Answer

Solution code:
import itertools
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
ans = p
a.sort(reverse=True)
def check(li,rem_vote,target):
    sum_vote = 0
    for i in range(len(li)):
        sum_vote += (target) - a[-(i + 1)]
    if sum_vote >= rem_vote:
        return True
    else:
        return False
for i in range(p,n):
    remain_people = n - i - 1
    used_vote = remain_people * m + (p - 1) * m
    if used_vote >= m * v:
        ans += 1
        continue
    if a[p-1] + v - (p - 1 + n - i) > a[i] + m:
        break
    ans += 1
print(ans)

Submission status: Wrong Answer

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

l.sort()
print(l)

right = n
left = -1
while right-left>1:
    mid = (right-left)//2
    l1 = copy.deepcopy(l)
    if mid >= m:
        l1[mid] += m
    else:
        index = bisect.bisect_left(l1, l1[mid]+m+1,mid)
        print(index,l1[mid]+m+1)
        k = mid+n+1-index
        v1 = v-k
        if v1 > 0:
            l2 = l1[mid+1:index]
            print(l2)
            for i in range(m):
                l2.sort()
                for i in range(v1):
                    l2[i] +=1
            l2.sort()
            for i in range(mid+1,index):
                l1[i] = l2[i-mid-1]
        l1[mid] += m
        print(l1)
    if l1[mid] >= l1[-p]:
        
        right = mid
        print(right,left)
    else:
        left = mid
        print(right,left)


print(n-left)

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 -1)*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:
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)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        else:
            Q.append(A[i-1])
            Q_sum=sum(Q)
            len_Q=len(Q)
            if target*len_Q-Q_sum>=b*M:
                ans+=1
            else:
                break
print(ans)

Submission status: Wrong Answer

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)

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

if inx==-1:
 print(n)
 exit()

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

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

left=0
right=n-p

while  right -left >1:
    mid =(left+right)//2
    if a[mid]+m < a[n-p]:
        left=mid+1
    else:
        j=v-(mid+1+p-1)
        if j <= 0:
            right=mid
        else:
            sum=0
            for k in range(mid+1,n-p+1,1):
                if m+a[mid]-a[k] < 0:
                    left = mid+1
                    break
                sum+=a[mid]+m-a[k]
                if sum >= j*m:
                    right=mid
                    break
                if k==n-p:
                    left=mid+1

if left==right:
    print(n-left)
elif right-left==1:
    p1 = 0
    mid = left
    if a[mid] + m < a[n - p]:
        p1 = 0
    else:
        j = v - (mid + 1+p-1)
        if j <= 0:
            p1 = 1
        else:
            sum = 0
            for k in range(mid + 1, n+p+1, 1):
                if m + a[mid] - a[k] < 0:
                    p1 = 0
                    break
                sum += a[mid] + m - a[k]
                print("s", sum, j * m, a[k])
                if sum >= j * m:
                    p1 = 1
                    break
                if k == n-p:
                    p1 = 0

    if p1==1:
        print(n-left)
    else:
        print(n-left-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]
"""

"""
10 4 10 5
7 2 3 6 1 6 5 4 6 5
ans 6
[1, 2, 3, 4, 5, 5, 6, 6, 6, 7]
"""

"""
10 4 9 5
7 2 3 6 1 6 5 4 6 5
ans 6?
[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:
    if v == n:
        print(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())
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: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
al=sorted(list(map(int,input().split())))
if p>1:
    ta=al[:-p+1]
else:
    ta=al[:]
tn=len(ta)
tv=v-(p-1)
ans=p-1
mt=max(ta)
if tv<=0:
    for i in ta:
        if i>=mt:
            ans+=1
    print(ans)
elif tv==1:
    for i in ta:
        if i+m>=mt:
            ans+=1
    print(ans)
else:
    td=tn-tv
    mc=ta.count(mt)
    if mc-td>0:
        for i in ta:
            if i>=mt:
                ans+=1
    else:
        for i in ta:
            if i+m>=mt+m//2:
                ans+=1
    print(ans)

Submission status: Wrong Answer

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
    j = p
    for i in range(p, n):
        if n - i - 1 < y:
            z = y - n + i + 1
            if k * (m + sort_list[i]) >= sum_socre + z * m and kijyun_score - sort_list[i] <= m:
                j += 1
        else:
            if kijyun_score - sort_list[i] > m:
                count = i
                print(count)
                break
            j += 1
        k += 1
        sum_socre += sort_list[i]
        if i == n - 1:
            print(j)

Submission status: Wrong Answer

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 // (N-tmp) + li[-P]:
			ans = N - i
			break
print(ans)

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 N <= 10:
  for i in range(N):
    if check(a[i]) == False:
      ng = max(ng, a[i])
if check(ng): ng -= 1
if check(ng): ng -= 1
if check(ng): ng -= 1
for k in ks:
  if k <= ng: res -= d[k]

print(res)

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 + 1)*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)
#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(0,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)