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:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        x = (l+r) >> 1
        ai = a[x]
        i = bisect.bisect_right(a,ai)
        A = ai+m
        j = bisect.bisect_right(a,A)
        if n-j >= p:
            l = x
            continue
        if v <= i:
            r = x
            continue
        res = m*v-m*i
        for j in range(i,v):
            res -= A-a[j]
        for j in range(v,n):
            if a[j] < A:
                res -= A-a[j]
        i = bisect.bisect_left(a,ai)
        for j in range(min(p-1,n-i-1)):
            k = n-j-1
            if a[k] < A:
                res -= a[k]-ai
            else:
                res -= m
        if res <= 0:
            r = x
        else:
            l = x
    print(n-r)
    return

#Solve
if __name__ == "__main__":
    solve()

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
for idx,val in enumerate(An):
    if theard_num == val:
        theard_idx = idx
    threadhold_list[idx] = max(0,theard_num-val)
#print(An)
#print(threadhold_list)

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 must_allocation_num < idx:
        sum_foword_nums = sum(An[must_allocation_num:idx])
        allocation_diff =  must_allocation_num - (N-idx)
        diveide_allocation_num = (idx-must_allocation_num)
        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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
# print(A)
B=A[:]
A.append(inf)
for i in range(n-1):
    B[i+1]+=B[i]
i=0
while i < n:
    count=1
    while A[i]==A[i+1]:
        i+=1; count+=1
    K=v-p-(i)
    # print(i,K,ans)
    if i>=n-p:
        ans+=count; i+=1
        continue
    if K<=0:
        if bisect.bisect_right(A,A[i]+m)>=n-p:
            ans += count
            i+=1
        else:
            i+=1
    else:
        if A[n-p]>A[i]+m:
            i+=1
        else:
            S=B[n-p]-B[i]
            if (A[i]+m)*(n-p-i)>=S+K*m:
                ans+=count
                i+=1
            else: i+=1
print(ans)

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:
    ans += 1
print(ans)

Submission status: Wrong Answer

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

sort_a = sorted(a, reverse=True)
ok = 0
ng = n - 1

while abs(ok-ng)>1:
  mid=(ok+ng)//2
  if sort_a[ng]+n<sort_a[mid]:
    sort_a.pop()
    ng -= 1
  else:
    ok = ng - 1

print(n-ng)

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)

points = a[:]

ans = 1

for i in range(1,n):

    if a[i] == a[i-1]:
        ans += 1
        continue
    if i <= (p-1):
        ans += 1
        continue

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

    sum_enemy = np.sum(points[(p-1):] - points[i])
    adding_point = m*v-m*p

    if points[i] < points[p-1]:
        break

    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:
        ans += 1
    else:
        break

print(ans)

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(a[i])

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:
    ans += 1
print(ans)

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:
        if a[i]+m>=a[n-p]+m:
            ct=a.index(a[i])+1
            break
    else:
        if a[i]+m>=a[n-p]:
            ct=a.index(a[i])+1
            break
#if v-1>=n-p+1:
#print(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 = sorted(list(map(int, input().split())), reverse = True)

ans = P
border = A[P-1]
for i in range(N):
    if A[i] == border:
        first_border = i
        break

for i in range(P, N):
    if A[i] == border:
        ans += 1
    elif V-(N-i)-1 < 0 and A[i] + M >= border:
        ans += 1
    elif A[V-(N-i)-1] > border and A[i] + M >= border:
        ans += 1
    elif A[V-(N-i)-1] == border:
        score_sum = M * (V-(N-i)-1 - first_border + 1)
        for j in range(first_border, i):
            score_sum += A[j]
        if A[i] + M >= -(-score_sum//((i-1) - (first_border-1))):
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        x = (l+r) >> 1
        ai = a[x]
        i = bisect.bisect_right(a,ai)
        A = ai+m
        j = bisect.bisect_right(a,A)
        if n-j >= p:
            l = x
            continue
        if v <= i:
            r = x
            continue
        res = m*v-m*i
        for j in range(i,v):
            res -= A-a[j]
        for j in range(v,n):
            if a[j] < A:
                res -= A-a[j]
        i = bisect.bisect_left(a,ai)
        for j in range(min(p-1,v-i-1)):
            k = n-j-1
            if a[k] < A:
                res -= a[k]-ai
            else:
                res -= m
        if res <= 0:
            r = x
        else:
            l = x
    print(n-r)
    return

#Solve
if __name__ == "__main__":
    solve()

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(B)
for i,b in enumerate(Bk[:-1]):
    #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(b,v-C[i],x,y,L[::-1],ans_count[::-1])
    if p >= y:
        if i == 0:
            print(C[-1])
        else:
            print(C[-1]-C[i-1])
        sys.exit()

Submission status: Wrong Answer

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


def binary_search(S,k,m,v,p):
  test=S[k]+m
  cnt=m*(p-1)
  for i in range(p-1,n):
    if i==k:
      continue
    elif test-S[i]>=m:
      cnt+=m
    else:
      cnt+=test-S[i]
  if cnt>=m*(v-1):
    return True
  else:
    return False

l=p-1
r=n
while r-l>1:
  mid=(r+l)//2
  if binary_search(S,mid,m,v,p):
    l=mid
  else:
    r=mid
print(l+1)

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)
for i in range(d-(n-v),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:
        if a[i]+m>=a[n-p]+m:
            ct=a.index(a[i])+1
            break
    else:
        if a[i]+m>=a[n-p]:
            ct=a.index(a[i])+1
            break
#if v-1>=n-p+1:
#print(a.index(a[n-p]))
#else:
print(n-ct+1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, M, V, P = rl() #Vは選べる問題
A = rl()
A.sort(reverse=True)
INF = 10 ** 10
A = A[P-1:] + [-INF] #上位P-1問は捨てる
V -= (P-1)
N = len(A)
answer = P-1

# 残りの問題からトップに立てるかどうか二分探索
high = N-1 #不可能
low = 0 #可能
while high > low + 1:
    mid = (high+low)//2
    num = max(0, V - (N-1-mid)) #INFは捨てる   
    B = np.array(A[:mid])
    #Bの中からM人のジャッジがnum問選ぶ
    count = ((A[mid] + M) - B).sum()
    if count <  M * num:
        high = mid #不可能
    # 他に不可能な場合がある
    else:
        low = mid

answer += (low + 1)
print(answer)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a,reverse=True)
    border=a[p-1]
    notac=0
#    temp=p-1
#    for i in range(p,n):
  #      if a[i]==border:
  #          temp=i
  #      else:
  #          break
#    temp+=1
#    print(a)
 #   print(border)
    if v<p:
        for i in range(p,n):
            if border-a[i]>m:
                notac=i
                break
    else:
        total=p
        for i in range(p,n):
            total+=a[i]
            if m*(n-v)<total-(i-p+1)*a[i]:
                notac=i
                break
            if border-a[i]>m:
                notac=i
                break
 #   print(ans)
    print(notac)











if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m, v, p = map(int, input().split())
a = np.array(list(map(int, input().split())))
a = -np.sort(-a)
rest = a[p-1:]
sa = np.cumsum(rest)
nr = len(sa)
ans = p

for i, (sl, ai) in enumerate(zip(sa, rest)):
    if i == 0:
        continue
    nsmalls = nr-i
    nlarges = i
    rm = v-nsmalls-(p-1)
    slarges = sl+rm*m-ai
    mean_larges = slarges/nlarges
    if mean_larges <= (ai+m):
        ans += 1
    else:
        break
print(ans)

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, n):
            if a[i] > bin_v:
                if cost + a[i] - bin_v <= mi:
                    cost += a[i] - bin_v
                else:
                    if n - i + 1 >= p:
                        inc_v = bin_v
                        b = False
                        break
                    else:
                        break
        if b:
            cor_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 = sorted([int(i) for i in input().split()], reverse=True)


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

Submission status: Wrong Answer

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

al = sorted(al)
import bisect
if v > p:
   down_power = n - v
   rest_list = al[:n-p+1]
   ub = n-p+1
   lb = 0
   while True:
      if ub == lb:
         print(n - ub)
         import sys
         sys.exit()
      target = (ub + lb) // 2
      pp = rest_list[target] 
      point = 0
      for a in rest_list:
         if a > pp:
            point += a - pp
      if point * (m - target + 1) > down_power:
         lb = target + 1
      else:
         ub = target 
else:
   k = al[-p]
   ans = 0
   for a in al:
      if a + m >= k:
         ans += 1
   print(ans)

Submission status: Wrong Answer

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


import bisect

n, m, v, p = map(int, input().split())
a = 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 = -1
        ok = i

def solve(i):
        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

tmp_ok = ok
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if solve(mid):
        ok = mid
    else:
        ng = mid
if ng == -1:
    print(ans)
else:
    print(ans + (tmp_ok - ok + 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]

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)-s[idx]+s[v]+s[i]
        k=bisect.bisect_right(s,buf)
    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:
temp = list(map(int,input().split()))
n = temp[0]
m = temp[1]
v = temp[2]
p = temp[3]
count = 0

a = list(map(int,input().split()))
new = sorted(a)
b = new[n-p]
i = 0
while i < n-p:
  new[i] = new[i] + m
  i = i + 1

j = 0
if v < n-2:  
  while j < n-p:  
    if new[j] >= b:
      count = count+1
    j = j + 1
else:
  while j < n-p:  
    if new[j] >= new[n-1]:
      count = count+1
    j = j + 1
    
print(count+p)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

a = sorted(a)

sm = sum(a[:n-p+1])
mxcnt = a[:n-p+1].count(a[n-p])
mx = a[n-p]

if v <= p:
    k = bisect_left(a,mx - m)
    print(n-k)
    exit()

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

print(p)

a[v-p]

Submission status: Wrong Answer

Solution code:
import bisect
n,m,v,p = map(int,input().split())
a = list(map(int,input().split()))
a = sorted(a)
wa = [a[0]]
for i in range(1,n):
    wa.append( wa[i-1] + a[i] )
border = a[n-p]
j = bisect.bisect_right(a,border)
for i in range(n-p):
    if a[i] + m >= border:
        if n-j+i+1 >= v:
            print(n-i)
            break
        else:
            if (j-i-1)*(a[i]+m)-(wa[j-1]-wa[i]) >= (v-(n-j+i+1))*m:
                print(n-i)
                break

Submission status: Wrong Answer

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


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

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

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

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


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

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

Submission status: Wrong Answer

Solution code:
if __name__ == "__main__":
  N, M, V, P = map(int, input().split())
  Al = list(map(int, input().split()))
  A = sorted(Al, reverse=True)
  
  cnt = 0
  
  B = A[P:]
  B.reverse()
  for i in range(M):
    for j in range(V-P+1):
      B[j] += 1
    B.sort()
      
  edge = B[-1]
  Ap = A[P:]
  
  for Ai in A:
    if( Ai + M >= edge ):
      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())))

B = A[:N-P+1]

low = 0
high = N-P+1

while high-low>1:
    mid = (low+high)//2
    tmp = 0
    flag = False
    for i in range(N-P+1):
        if i==mid:
            continue
        if B[mid]+M-B[i]<0:
            flag = True
        tmp += min(B[mid]+M-B[i],M)
    if tmp >= max(M*(V-P),0) and not flag:
        high = mid
    else:
        low = mid

print(N-high)

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)

    for i in range(n-v+1,n):
        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(len(ans))


main()

Submission status: Wrong Answer

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

cnt = 0
A.sort()
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i]+A[i]
    
if V <= P:
    for i in range(N-P):
        if A[i]+M < A[N-P]:
            cnt += 1
        else:
            break
else:
    for i in range(N-P):
        if i+P >= V:
            if A[i]+M < A[N-P]:
                cnt += 1
            else:
                break
        else:
            num = M*V-M*(i+P)#さばかないといけない数
            j = N-P
            while A[j] >= A[i]+M:
                j -= 1
            
            t = (j-i)*(A[i]+M)-(S[j+1]-S[i+1])#空いてる数
            t -= t%(V-P-i)
            if num > t:
                cnt += 1
            else:
                break
                
print(N-cnt)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int,input().split())
a = list(map(int,input().split()))
import bisect
asort = sorted(a)
aset = list(set(a))
obj = min(asort[:n-p-1:-1])
n_under = bisect.bisect_left(asort, obj)
n_equal = bisect.bisect_right(asort, obj) - n_under
n_over = n - n_equal - n_under

ans = n_equal + n_over
tmp_ad = 0
for i in range(len(aset)):
    if aset[i] < obj:
        tmp_c = asort.count(aset[i])
        if (aset[i]+m >= obj) & ((v - n_over - n_equal - tmp_ad) <= 0):
            ans += tmp_c
        tmp_ad += tmp_c
    else:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        x = (l+r) >> 1
        ai = a[x]
        i = bisect.bisect_right(a,ai)
        A = ai+m
        j = bisect.bisect_right(a,A)
        if n-j >= p:
            l = x
            continue
        if v <= i:
            r = x
            continue
        res = 0
        i = bisect.bisect_left(a,ai)
        for j in range(i,v):
            res += a[j]-ai
        for j in range(min(p-1,v-i-1)):
            k = n-j-1
            if a[k] < A:
                res -= a[k]-ai
            else:
                res -= m
        if res <= 0:
            r = x
        else:
            l = x
    print(n-r)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import bisect
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]

n, m, v, p = ril()
ls = sorted(ril(), reverse=True)

if p + v - n <= 0:
    thresh = ls[p - 1]
else:
    i = n - bisect.bisect(ls[::-1], ls[p - 1])
    s = (v - i) * m
    r = s % (n - i)
    thresh = ls[p - 1] + s // (n - i)
    if ls[-r] == ls[p - 1]:
        thresh += 1

index = n - bisect.bisect_left(ls[::-1], thresh)
print(n - bisect.bisect_left(ls[index:][::-1], thresh - m))

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a,reverse=True)
    border=a[p-1]
    notac=0
#    temp=p-1
#    for i in range(p,n):
  #      if a[i]==border:
  #          temp=i
  #      else:
  #          break
#    temp+=1
#    print(a)
 #   print(border)
    if v<p:
        for i in range(p,n):
            if border-a[i]>m:
                notac=i
                break
    else:
        total=p
        for i in range(p,n):
            total+=a[i]
            if m*(n-v)<total-(i-p+1)*a[i]:
                notac=i
                break
 #   print(ans)
    print(notac)











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.sort(reverse=True)
nums = set()
ans = 0
border = float('inf')
index = float('inf')
for i in range(n):
    nums.add(a[i])
    if len(nums) == p:
        border = a[i]
    if len(nums) > p:
        index = i
        break
    ans += 1
if index != float('inf'):
    for i in range(index, n):
        if n - i >= v and border - a[i] <= m:
            ans += 1
        if n - i < v and border - a[i] <= m and v - n + i <= p - 1:
            ans += 1
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)
"""
b = dd(int)
for i in range(len(ks) - 1):
  k = ks[i]
  l = ks[i + 1]
  b[k] = (l - k) * d[k]
"""
"""
def check(x):
  if x + M >= ks[-P]:
    return True
  t = V * M - M
  for k in ks:
    if 
    t -= ks[k] * M
    if t <= 0: break
"""
t = float("inf")
c = 0
for i in range(N - 1, -1, -1):
  if a[i] != t:
    if c == P: break
    t = a[i]
    c += 1
#print(t)
res = 0
tt = 0
for i in range(V - 1, N):
  if a[i] + M >= t:
    tt = a[i]
    break
#print(tt)
for k in ks:
  if k >= min(tt, t):
    res += d[k]
print(res)

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)
tmp = a[p-1]
cnt = p
for i,ai in enumerate(a[p:]):
  if tmp - ai > m or i + a.count(ai) - 1 > n - v:
    break
  cnt += 1
print(cnt)