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(' '))
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 (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
    break
print(idx)

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)
    sc = sc - M * (P-1)
    return sc <= 0

l, r = -1, N
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:
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
  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:
n,m,v,p=map(int,input().split())
A=[int(i) for i in input().split()]
A=sorted(A)
#print(A)

import sys
import math
from itertools import accumulate
from collections import defaultdict

B = defaultdict(int)
for a in A:
    B[a] += 1
Bk=list(B.keys())
Bv=list(B.values())
nn=len(Bk)
C=list(accumulate(Bv))
#print(Bv)
#print(Bk)

left = 0
right = nn
mid = (left+right)//2
    
def func(i):
    b = Bk[i]
    #if C[-1]-C[i] < p:
        #print("ok")
    x = b + m
    v2 = max(0,v - C[i])
    L=[]
    count = 0
    ans_count = []
    for j in range(i+1,nn)[::-1]:
        if count < v2:
            temp=Bk[j] + math.ceil(m/Bv[j])
        else:
            temp=Bk[j]
        L.append(temp)
        if temp > x :
            ans_count.append(Bv[j])
        else:
            ans_count.append(0)
        #if m % Bv[j] == 0:
        #    L.append(Bk[j] + v2//Bv[j])
        #else:
        #    L.append(Bk[j]+ v2//Bv[j] + 1)
        count += Bv[j]
    y=sum(ans_count)
    #print("a",ans_count[::-1])
    #print(b,v-C[i],x,y,L[::-1],ans_count[::-1])
    #print([int(ii) + m for ii in Bk[:i+1]],L[::-1])
    return p >= y

def ans_func(i):
    if i == 0:
        print(C[-1])
    else:
        print(C[-1]-C[i-1])
    sys.exit()
he=0
#print(left,mid,right)
while True:
    if func(mid):
        right = mid
    else:
        left = mid
    mid = (left+right)//2
    #print(left,mid,right)
    if right - left == 1:
        if func(left):
            ans_func(left)
        else:
            ans_func(right)

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
    for i in range(p, n):
        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: 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**18] + list(map(int, input().split()))
a = sorted(a)

ans = 0
ok = 0
ng = 0
for i in range(n):
    if i+1 >= v:
        tmp = a[i] + m
        ind = bisect.bisect_right(a, tmp)
        if n - ind < p:
            ans += 1
    else:
        ng = 0
        ok = i + 1

def solve(i):
        if i+1 >= v:
            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

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

Submission status: Wrong Answer

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_step = 0
while True:
    if pre_step == 1 and  step == 1:
        break
    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 - 1)
        exit()

Submission status: Wrong Answer

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

def main():
    N, M, V, P = (int(x) for x in input().split())
    A = [int(x) for x in input().split()]
    
    A.sort(reverse=True)
    ans = P

    for i in range(P,N):
        tail = (N-i)
        
        if tail >= V:
            if A[i]+M >= A[P-1]:
                ans += 1
        else:
            over = V - tail
            if over <= (P-1):
                if A[i]+M >= A[P-1]:
                    ans += 1
            else:
                miwariate_point = (over-(P-1))*M
                btw = A[P-1:i]
                base = miwariate_point//len(btw)
                amari = miwariate_point%len(btw)
                if btw[0] >= (btw[-amari]+1):
                    rival = btw[0] + base
                else:
                    rival = btw[-amari] + base + 1
                    
                if A[i]+M >= rival:
                    ans += 1
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

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

A_Counter = collections.Counter(A)
A_Counter = sorted(A_Counter.items(), reverse=True)

tot = 0
Tot = []
for i in range(len(A_Counter)):
    tot += A_Counter[i][1]
    Tot.append(tot)

for i in range(len(Tot)):
    if Tot[i] >= p:
        A_p = A_Counter[i][0]
        A_p_ind = i
        A_p_count = A_Counter[i][1]
        break

Judge_count = [True for i in range(A_p_ind+1)] + [False for i in range(len(Tot)-A_p_ind-1)]
Judge_val = [True for i in range(A_p_ind+1)] + [False for i in range(len(Tot)-A_p_ind-1)]


# num
After_p_count = []
before_p = 0
after_p = 0
for i in range(len(Tot)):
    if i < A_p_ind:
        before_p += A_Counter[i][1]
        After_p_count.append(0)
    else:
        after_p += A_Counter[i][1]
        After_p_count.append(after_p)

for i in range(len(After_p_count)):
    if After_p_count[i] <= n -v:
        Judge_count[i] = True

# val
P_minus_val = []
for i in range(len(Tot)):
    p_minus = A_p - A_Counter[i][0]
    P_minus_val.append(p_minus)

for i in range(len(Tot)):
    if P_minus_val[i] <= m:
        Judge_val[i] = True


Final_judge = [False for i in range(len(Tot))]
for i in range(len(Tot)):
    if (Judge_count[i]==True) and (Judge_val[i] == True):
        Final_judge[i] = True

ans = 0
for i in range(len(Final_judge)):
    if Final_judge[i] == True:
        ans += A_Counter[i][1]

print(ans)

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:
            break
      
    else:
        amari = max(0, m * (v - n + i - p + 1) - gap)
        if  (ai + m) >= ap + math.floor((amari / (i - p))):
            ans += 1
            gap += ap - ai
            continue
        else:
            break  

print(ans)

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**8] + list(map(int, input().split()))
a = sorted(a)

ans = 0
ok = 0
ng = 0
for i in range(n):
    if i+1 >= v:
        tmp = a[i] + m
        ind = bisect.bisect_right(a, tmp)
        if n - ind < p:
            ans += 1
    else:
        ng = 0
        ok = i + 1

def solve(i):
        if i+1 >= v:
            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

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

Submission status: Wrong Answer

Solution code:
from math import ceil,floor

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]

            
ans =P
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
        Q = A[P-1:i]
        n_Q =len(Q)
        sum_Q=sum(Q)
        sum_Q2 =sum_Q + b*M
        max_Q2 =ceil(sum_Q2/n_Q)
            
            
        if max_Q2<=target:
            ans+=1
        else:
            break
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()]
a.sort(reverse=True)
res = p
i = p
while i < n:
    if a[i] + m >= a[p-1]:
        res += 1
        if (a[i] + m + n - p - v) < a[p-1]:
            res -= 1
    i+=1
print(res)

Submission status: Wrong Answer

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

    scores.sort(reverse = True)
    ans = set()
    for i in range(p):
        ans.add(i)
        
    for i in range(p,n):
        if scores[i]+m >= scores[p-1]:
            if n-i-1 >= v-1:
                ans.add(i)

    #print(scores)
    for i in range(n-1,n-v-1,-1):
        scores[i] += m

    arr = []
    for i in range(n):
        arr.append((scores[i],i))

    arr.sort(reverse = True)

    for i in range(p):
        ans.add(arr[i][1])

    last = arr[p-1][0]
    for i in range(p,n):
        if arr[i][0] == last:
            ans.add(arr[i][1])

    #print(scores,arr)
    #print(ans)
    print(len(ans))


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=0
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
    else: 
        if 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==0:
    ct=1
print(n-ct+1)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)

import math
def handan(a,n,m,v,p,now):
    if v<=n-now+p-1:
        if a[p-1]<=a[now]+m:
            return True
        else:
            return False
    else:
        vv=v-(n-now+p-1) #>=1
        b =a[p-1:now]
        l=len(b)
        s=sum(b)
        k_th=math.ceil((-l*a[now]+s)/(l-vv))
        if k_th<=m:
            return True
        else:
            return False
          
left=0
right=n-1
ma=-1
while left<=right:
    now = (right+left)//2    
    if handan(a,n,m,v,p,now):
        left = now+1
        if ma<=now:
            ma=now
    else:
        right = now-1
print(ma+1)

Submission status: Wrong Answer

Solution code:
n,m,v,p =map(int, input().split())
al=[int(i) for i in input().split()]
al.sort()

impo=0
for i in range(n):
    if v-i-1 < p: # p番目に大き物には足されない
        if al[i]+m < al[-p]:
            impo+=1
        else:
            break
    else:
        impo+=1
print(n-impo)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
imos = [0]
fl = [0 for i in range(n+1)]
for i in a:
    imos.append(imos[-1]+i)
l = 0
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
else:
    ans = 0
    c = Counter(a)
    s = set()
    for i in range(n):
        if a[i] in s:
            continue
        if i < p:
            ans += c[a[i]]
            s.add(a[i])
            continue
        if a[i]+m >= tmp:
            t = v-p - (n-1-i)
            if (a[i]+m)*(i-p)-(imos[i]-imos[p]) >= t*m:
                ans += c[a[i]]
                s.add(a[i])
    print(ans)
    exit()

Submission status: Wrong Answer

Solution code:
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


from bisect import bisect_left, bisect_right
N, M, V, P = read_ints()
A = read_ints()
A.sort()
edge_idx = N - P
edge = A[-P]
# ここに処理を書けば終わりだ
# M人がちょうどV配ることによる副作用の扱いがわからん...
Mls = [M] * N
# print(A)
left_point = V * M
for i in range(edge_idx - 1, -1, -1):
    sa = edge - A[i]
    if sa > left_point:
        break
    # 代入処理
    sa = min(sa, M)
    left_point -= sa
    Mls[i] -= sa
    A[i] = edge

mina = 0
if left_point > 0:
    for i, m in enumerate(Mls):
        if m == 0:
            mina += 1
            continue
        else:
            left_point -= m * (N - i)
            if left_point < 0:
                break
            elif left_point == 0:
                mina += 1
                break
            else:
                mina += 1


# print(Mls)
# print(A)

lower_bound_idx = bisect_left(A, edge)
n_candi = edge_idx - lower_bound_idx
print(P + n_candi - mina)
# print(A)

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 = 0
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 = (ind-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)*m:
                    ans += 1
  #                    print(i,3)
  #                else:
  #                    print(i,4)
  #        else:
  #            print(i,5)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_right, bisect_left
input = sys.stdin.readline
n, m, v, p = [int(x) for x in input().strip().split()]
araw = sorted([int(x) for x in input().strip().split()])
a = list(reversed(araw))

def f(x, n, m, v, p, a, araw):
    c = p - (n - bisect_right(araw, a[x-1]+m)) - 1
    if c < 0:
        return False
    vote = m * (v - 1)
    a[x-1] += m
    thr = a[x-1]
    for i, aa in enumerate(a, start=1):
        if vote <= 0:
            break
        if i == x:
            continue
        if aa > thr:
            a[i-1] += m
            vote -= m
        elif aa == thr:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
        elif thr - aa < m:
            if c:
                a[i-1] += m
                vote -= m
                c -= 1
            else:
                v_ = min(vote, thr - aa, m)
                a[i-1] += v_
                vote -= v_
        else:
            a[i-1] += m
            vote -= m
    return vote <= 0

x = 0
l = 1
r = n
while l < r:
    x = (l + r) // 2
    if f(x, n, m, v, p, a[:], araw):
        l = x + 1
    else:
        r = x
print(l-1)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
a=[int(i) for i in input().split()]
a.sort(reverse=True)

import math
def handan(a,n,m,v,p,now):
    if v<=n-now+p-1:
        if a[p-1]<=a[now]+m:
            return True
        else:
            return False
    else:
        vv=v-(n-now+p-1) #>=1
        b =a[p-1:now]
        l=len(b)
        s=sum(b)
        k_th=math.ceil((-l*a[now]+s)/(l-vv))
        if k_th<=m:
            return True
        else:
            return False
          
left=0
right=n-1
ma=-1
while left<=right:
    now = (right+left)//2
    print(left,now,right)
    
    if handan(a,n,m,v,p,now):
        left = now+1
        if ma<=now:
            ma=now
    else:
        right = now-1
print(ma+1)

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]
  for i in range(V):
    b[i] += M
  b.sort()
  for i in range(V):
    if b[i] == x + M:
      return False
  return True
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
print(N - ok)

Submission status: Wrong Answer

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

A.sort(reverse=True)


left = P
right = N-1
mid = (P+N-1)//2
MIN = A[P-1]
while True:
    mid = (right+left)//2
    if right-left <= 1:
        high = M+A[right]
        zan = P+N-right-2
        if zan >= V-1:
            if high >= MIN:
                ans = right
            else:
                ans = left
        else:
            yak = V-1-zan
            rlist = []
            for j in range(right-P):
                rlist.append(high-A[P-1+j])
            if rlist[0] < 0:
                ans = left
            else:
                plus = [0]*yak
                heapq.heapify(plus)
                for r in rlist:
                    p = heapq.heappop(plus)
                    heapq.heappush(plus,p+r)
                p = heapq.heappop(plus)
                if p >= M:
                    ans = right
                else:
                    ans = left
        break
    else:
        high = M+A[mid]
        zan = P+N-mid-2
        if zan >= V-1:
            if high >= MIN:
                left = mid
            else:
                right = mid
        else:
            yak = V-1-zan
            rlist = []
            for j in range(mid-P):
                rlist.append(high-A[P-1+j])
            if rlist[0] < 0:
                right = mid
            else:
                plus = [0]*yak
                heapq.heapify(plus)
                for r in rlist:
                    p = heapq.heappop(plus)
                    heapq.heappush(plus,p+r)
                p = heapq.heappop(plus)
                if p >= M:
                    left = mid
                else:
                    right = mid
                    

print(ans+1)

Submission status: Wrong Answer

Solution code:
def main():
    tmp0 = input()
    tmp1 = input()
    [n, m, v, p] = [int(i) for i in tmp0.split()]
    a = [int(i) for i in tmp1.split()]
    a.sort(reverse=True)
    ans = p
    for i in range(p,n):
        tgt = a[i]
        enemy = a[p-2]
        tgt += m
        if tgt >= enemy:
            ans += 1
        else:
            break
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from sys import exit

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


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

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


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

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


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

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

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

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


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



    print(n-r)



    
main()

Submission status: Wrong Answer

Solution code:
from math import ceil,floor

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]

ans = 0

if P==1:
    for i in range(N):
        if A[0]<=A[i]+M:
            ans +=1
            
else:
    ans =P
    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
            Q = A[P-1:i]
            n_Q =len(Q)
            sum_Q=sum(Q)
            sum_Q2 =sum_Q + b*M
            max_Q2 =ceil(sum_Q2/n_Q)
            
            
            if max_Q2<=target:
                ans+=1
            else:
                break
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
from collections import defaultdict
N, M, V, P = map(int, input().split())
A = sorted([int(x) for x in input().split()])

def debug(*args):
    if 1:
        print(*args)

def solve(N, M, V, P, A):
    Y = A[N-P]
    L = N - bisect_left(A, Y)
    R = N - bisect_right(A, Y)

    count = defaultdict(int)
    for i in range(N):
        count[A[i]] += 1

    answer = 0
    for a in count:
        d = 0
        if a >= Y:
            d = 1
        elif a + M < Y:
            d = 0
        elif a + M >= Y+1:
            d = 1
        elif a + M == Y:
            #print(N-count[Y], "<", V)
            if N - count[Y] - 1 >= V:
                d = 1
        #print(a, d)
        answer += count[a] * d
    return answer

print(solve(N, M, V, P, A))

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)
  
from bisect import bisect_right
for i in range(p,n):
  h = a[i]+m
  x = bisect_right(a, h) #満票獲得時のa[i]が挿入できる点を探す
  free = v - (x + (n-i)) #各人が自由に使える票数
  s = c[i+1] - c[x] # ライバルゾーンにいる奴の総和
  d = h * (i-x) - s # 余裕
  if d >= free*m and d >= 0 and free >= 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import copy
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-1):
      a[j]+=1
    a=sorted(a)
  for i in range(P-1):
    a.remove(max(a))
  return(a)

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

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
seta = list(set(A))
count = 0
tmp = -P+(V)
if tmp > 0:
    tmp = -1
for i in range(N):
    if A[i]+M >= A[-1]:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
ans=p
k=-1
l=0
for i in range(p,n):
  if a[p-1]==a[i]:
    ans+=1
    l+=1
  else:
    k=i-1
    break
l=k+1-(v-(n-1-k))
if k==-1 or k==n-1:
  print(ans)
else:
  if v-(n-1-k)>=p:
    print(ans)
  else:
    for i in range(k+1,n):
      if a[i]>=a[p-1]-m:
        if l>0:
          ans+=1
          l-=1
    print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)
limit = a[p - 1]
snum = a.index(limit)
alr = snum + a.count(limit)
restv = v - snum - 1
# print(a)
# print(limit, snum, alr, restv)
cnt = 0
for i in range(n):
    if a[i] >= limit:
        cnt += 1
        continue
    if a[i] + m >= limit:
        restp = i - snum
        rests = (restv - n + i + 1) * m
        if n - i - 1 >= restv:
            cnt += 1
        else:
            restl = a[i] + m - limit
            # print(i, restp, rests, restl, rests / restp)
            if rests / restp <= restl:
                cnt += 1
print(cnt)