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

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

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import math

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

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

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
currentMax = As[P-1]
output = P
for i in range(len(As)):
    things = []
    if i >= P:
        if (As[i]+M > currentMax):
            if (V <= ((len(As)-i) + (P - 1))):
                output = output + 1
            else:
                thisMax = As[i] + M
                for j in range(i-P+1):
                    things.append(As[j+P-1])
                remaining = M*(V-(N-len(things)))
                total = 0
                for z in things:
                    total = total + thisMax - z
                if total >= remaining:
                    output = output + 1
print(output)

Submission status: Wrong Answer

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
currentMax = As[P-1]
output = P
print(As)
for i in range(len(As)):
    things = []
    if i >= P:
        if (As[i]+M > currentMax):
            if (V <= ((len(As)-i) + (P - 1))):
                output = output + 1
            else:
                thisMax = As[i] + M
                for j in range(i-P+1):
                    things.append(As[j+P-1])
                remaining = M*(V-(N-len(things)))
                total = 0
                for z in things:
                    total = total + thisMax - z
                if total >= remaining:
                    output = output + 1
print(output)

Submission status: Wrong Answer

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

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))
    # print(a)


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

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

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

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

        if tmpmax < a[n-p][0]:
            l = mid
            continue

        # print(tmpmax)

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



    print(n-r)



    
main()

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
    rival = N-x-P

    if(x_score < A[N-P]+total_v//rival):
        return False

    if(total_v%rival==0):
        return True

    if(x_score >= A[x+total_v%rival] + (total_v//rival) + 1):
        return True
    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:
from bisect import*
from itertools import accumulate
n,m,v,p,*a=map(int,open(0).read().split())
a.sort(reverse=True)
a=[-x for x in a]
acc=list(accumulate(a))
ppp=acc[p-2]
if p>=v:
	print(bisect_left(a,a[p-1]+m+0.5))
	exit()
l=bisect(a,a[p-1]+0.5)-1
r=n
while r-l>1:
	mid=(l+r)//2
	amid=a[mid]
	bl=bisect_left(a,amid+0.5)-1
	bll=bisect_left(a,amid-0.5)-1
	lim=v-(p-1)-(n-1-bll)
	print(p,v,amid,bll,lim,ppp-acc[bll])
	if (-amid+m)*(bll-p+2)>=((ppp-acc[bll])+lim*m):
		l=mid
	else:
		r=mid
print(l+1)

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()

# convert
n = N - (P - 1)
m = M
v = max(1, V - (P - 1))
p = 1
a = A[:n]

cum_a = [0]
for ai in reversed(a):
    cum_a.append(cum_a[-1] + ai)
cum_a.reverse()


i = 0
for i in range(n):
    if (a[i] + m) * (n - 1 - i) - cum_a[i + 1] >= m * (v - 1 - i):
        break


ans = N - i

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,reverse=True)
key_num=a[p-1]
k=a.count(key_num)
key_idx=a.index(key_num)+k
c=a[key_idx:]
C=list(set(c))
cnt=0
for i in c:
  idx=len(C)-C.index(i)
  if key_num<=i+m:
    if v<key_idx+idx:
      cnt+=1 
print(cnt+key_idx)

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:
    c = bisect.bisect_left(b,a[i])
    c = n-i+1-c
    can = a[i]+m
    must = m*(v-n+i-1-p+c)
    for j in range(p-c,i):    
      must -= min(can-a[j] ,m)
    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())
a=list(map(int,input().split()))
a=sorted(a)
#print(a)
ct=-1
c=a[n-p]
d=a.index(c)
if d-(n-v)<0:
    sta=0
else:
    sta=d-(n-v)
for i in range(sta,n-p):#a.index(a[d-(n-v)])
   # if a[i]+m>=a[n-p]:
    #    ct=a.index(a[i])+1
     #   break
    if v>n-p and v+1!=n:
        if a[i]+m>=a[n-p]+m or a[i]+m>=a[v+1]:
            ct=a.index(a[i])+1
            break
        elif a[i]+m<a[n-p]+m and a[i]+m<a[v+1]:
            ct=-1
    elif v>n-p and v+1==n:
        if a[i]+m>=a[n-p]+m:
            ct=a.index(a[i])+1
            break
        elif a[i]+m<a[n-p]+m:
            ct=-1
    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==-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 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()
for i in range(n-1):
    if not check(i) and check(i+1):
        print(n - i - 1)
        exit()
print(n)

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



    print(count)

Submission status: 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)

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 >= 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 heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


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


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


# show_flg = False
show_flg = True


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

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

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

def possible(a, i):
    global N, M, V, P
    b = a.copy()
    b.reverse()
    d = b.index(a[i])
    if d > N - V:
        return d < P
    for j in range(len(b)):
        if b[j] == a[i]:
            b[j] += M
    b.sort()
    b.reverse()
    return b.index(a[i] + M) < P
    
l, r = 0, N - 1
while l < r:
    mid = (l + r) // 2
    f = possible(A, mid)
    if f:
        r = mid - 1
    else:
        l = mid + 1;

print(N - l)

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
  #print(x, b)
  for i in range(N - 1, -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
print(N - ok)

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

# print(After_p_count)
# print(A_Counter)
# print(Judge_count)
# print(Judge_val)
# print(Final_judge)

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

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 = (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)*m:
                    ans += 1
  #                    print(i,3)
  #                    print(sa,lis[i],i-key,key-nu,m)
  #                else:
  #                    print(i,4)
  #        else:
  #            print(i,5)
print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdout
printn = lambda x: stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def foo(i):
    q = v-n+i-p
    #ddprint("foo {} call q {}".format(i,q))
    if q<=0:
        return (a[i]+m >= a[p])
    ret = ( (i-p)*(a[i]+m) >= max(a[p], acc[i-1]-acc[p-1]+m*q) )
    #ddprint("i {} p {} ai {} m {} ap {} acm {} acp {} q {}".format(i,p,a[i],m,a[p],acc[i-1],acc[p-1],q))
    #ddprint("foo {} returns {}".format(i,ret))
    return ret

n,m,v,p = inm()
a = inl()
a.sort(reverse=True)
a[0:0] = [0] # a1..an
acc = [0]*(n+1)
for i in range(1,n+1):
    acc[i] = acc[i-1]+a[i]
ddprint(a)
ddprint(acc)
mn = p
mx = n+1
while mx-mn>=2:
    #ddprint("loop mn {} mx {}".format(mn,mx))
    mid = (mn+mx)//2
    if foo(mid):
        mn = mid
    else:
        mx = mid
print(mn)

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

n, m, v, p, *A = map(int, read().split())
ans = n

dicts = {}
for a in A:
    if a not in dicts.keys():
        dicts[a] = 0
    dicts[a] += 1
    

A = sorted(A)
thresh = A[-p]
thresh_ = A[v] + 1
tmp = v
past = A[::-1][0]

for a in A[::-1]:
    if past != a:
      tmp -= dicts[a]
    past = a
    if a >= thresh:
        continue
    if a + m > thresh_:
        continue
    if a+ m  == thresh_:
        continue
    ans -= 1

print(ans)

Submission status: Wrong Answer

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

A_list = list(map(int, input().split()))
A_list.sort()

largests = []
prev = None
for i in range(N - 1, -1, -1):
	a = A_list[i]
	if a != prev:
		largests.append(i)
	prev = a
largests.reverse()

#R = N - P
#a = A_list[R]
#while R < N - 1 and a == A_list[R + 1]:
#	R += 1

#print(largests)

def check(x):
	y = largests[x]
	if y >= N - P:
		return True
	
	a = A_list[y] + M
	
	if a < A_list[N - P]:
		return False
	
	v = V - (P - 1)
	m = 0
#	print(x, y, v, m)
	for i in range(N - P):
#		print(i, A_list[i], ">", i, v, m)
		if i == y:
			next
		if v < 0 or v == 0 and m == 0:
			return True
		a2 = A_list[i]
		if a2 + M < a:
			v -= 1
		else:
			if a2 + m <= a:
				m = m + M - a
				v -= 1
			else:
				m -= a - a2
#	print(v, m)
	
	return v < 0 or v == 0 and m == 0

s = 0
l = len(largests) - 1

while s < l:
	mid = (s + l) // 2
#	print(s, mid, l)
#	print(s, mid, l, check(mid))
	if check(mid):
		l = mid
	else:
		s = mid + 1

#print("s", s)
#for i in range(len(largests)):
#	print(i, A_list[largests[i]], check(i))

if s == 0:
	print(N)
else:
	print(N - largests[s - 1] - 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)
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:
    print(n-a.index(a[n-p]))
else:
    print(n-ct+1)

Submission status: Wrong Answer

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

tests = [int(i) for i in input().split()]

t = sorted(tests, reverse=True)

m = t[P - 1]

k = map(lambda x: x + M, t)
print(len(list(filter(lambda x: x > m, k))))

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]が挿入できる点を探す
  if x != 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().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:
#!/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)