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 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(1, len(After_p_count)):
    if p > n -v:
        Judge_count[i] = False
    elif After_p_count[i-1] <= 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)

# print(Tot)

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 itertools
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
ans = p
a.sort(reverse=True)
def check(left, right,rem_vote,target):
    sum_vote = 0
    for i in range(left, right):
        sum_vote += (target) - a[-(i + 1)]
    if sum_vote > rem_vote:
        return False
    else:
        return 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 check(p-1,i,m * v - used_vote, a[i] + m):
        break
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
li = list(map(int,input().split()))
a = list(map(int,input().split()))
n = li[0]
m = li[1]
v = li[2]
p = li[3]
b = sorted(a)
ans = 0
i=0
a.sort()
while i<m:
    j = 0
    while j<v-p:
        a[j] += 1
        j += 1
    if p > 1:
        j = n-p+1
        while j<n:
            a[j] += 1
            j += 1
    i += 1
    a.sort()
k=0
while k < n:
    if b[k]+m>=a[n-p]:
        ans+=1
    k += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import bisect as bi

N,M,V,P=map(int,input().split())
A=list(map(int,input().split())) # 0-index
A.sort(reverse=True) # 降順ソート
C=dict(Counter(A)) # スコアと人数の対応

d={} # 当初スコアAiに対応する順位d[i]
for i in range(N):
    if A[i] not in d:
        d[A[i]]=i+1
# 問番号iに対応する当初順位r[i]はr[i]=d[A[i]]となる
r=[d[A[i]] for i in range(N)]
# 当初スコアから成るlist
s=sorted(list(set(A)),reverse=True)
# 当初スコアに対応する順位からなるlist
rs=[d[si] for si in s]
# 当初スコア*人数
ps=[si*C[si] for si in s]
# 累積和
sps=[0]
for psi in ps:
    sps.append(sps[-1]+psi)
'''
print(f'A:{A}')
print(f'd:{d}')
print(f'r:{r}')
print(f's:{s}')
print(f'rs:{rs}')
'''
# 当初スコアを降順に並べたときに(1から数えて)P番目に来る問題の順位をq位とする。
q=r[P-1]
# print(f'q:{q}')

ans=0
# 注目するスコアsiに対応する順位r[si]を考える。
for si in s:
# d[si]<=qであれば，明らかに，対応する問題は問題セットに採用され得る。
    if d[si]<=q:
        ans+=C[si]
# そうでない場合，当初順位が「q位以下で，d[si]位より上」であるような問題d[si]-q問に自身を加えた(d[si]-q+1)問の中で，その問題のスコアを最大にすることができればよい。
# 各ジャッジは，(1)当初順位がq位より上のq-1問及び(2)当初順位がd[si]位以下の(N-d[si]+1)問には常に投票するとしてよい。
# 各ジャッジの投票後，当初スコアがsiだった問題のスコアはsi+Mになる。
# 当初順位がq位以下でd[si]位より上の問題d[si]-q問の当初スコアの合計は，sum([sj*C[sj] for sj in s if q<=d[sj]<d[si]])
# これに(V-(N-d[si]+1))*Mを加えたものが(si+M)*(d[si]-q+1)以下であればよい。
    else:
        sumscore=sum([sj*C[sj] for sj in s if q<=d[sj]<d[si]])
        addition=max((V-(q-1)-(N+1-d[si])),0)*M
        if sumscore + addition <= (si+M)*(d[si]-q):
            ans+=C[si]

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=-1
c=a[n-p]
d=a.index(c)
#if d-(n-v)<0:
 #   sta=0
#else:
 #   sta=d-(n-v)
for i in range(0,n-p):#a.index(a[d-(n-v)])
   # if a[i]+m>=a[n-p]:
    #    ct=a.index(a[i])+1
     #   break
    if a[i]+m>=a[n-p]:
        ct=a.index(a[i])+1
        break
        #elif a[i]+m<a[n-p]:
         #   ct=-1
    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
    if 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
    
#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:
from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
Q = [A[P-1]]
for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        
        Q.append(A[i-1])
        Q_sum=sum(Q)
        len_Q=len(Q)
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

Submission status: Wrong Answer

Solution code:
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)//(i-(P-1)) <= (A[i]+M):
            ans += 1
    S += A[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)[::-1]
#print(A)
for i in range(N):
    A[i] += M
#print(A)
cnt = 0
std = A[P-1]
ans = 0
check = -1
for i in range(N):
  if A[i] > std:
    ans += 1
  elif A[i] == std:
    ans += 1
    cnt += 1
  else:
    check = i
    break
if check == -1:
  print(ans)
  exit()
#print("ans1",ans)
#print(check)
S = M * (N - V)
#print("S",S)
Sum = 0
for i in range(check,N):
  if A[i] != A[check]:
    std = A[i-1]
  elif i != check and A[i] == A[check]:
    ans += 1
    cnt += 1
    continue
  Sum = Sum + (std - A[i]) * cnt
  #print("Sum",Sum)
  if S >= Sum:
    ans += 1
    cnt += 1
  else:
    break
print(ans)

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)
# 関係のある問題
A_q = A[0:N-P+1]
# 実質投票数
V_q = V - P + 1
ruikei = [A_q[-1]-a for a in A_q]
ruikei_sum = sum(ruikei)
for i,a in enumerate(A_q):
    if a + M >= A_q[-1]:
        plus = A_q[-1] - a
        yoyuu = ruikei_sum - ruikei[i] - (plus*(V_q-1+ruikei.count(0)))
        if yoyuu >= 0:
            break
    else:
        pass
print(N-i)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A)
ans=N
thr=A[-P]
i=0
while i<N:
  A[i]+=M
  V-=1
  a=A[:]
  j=i+1
  nokori=M*V
  if A[i]<thr:
    i+=1
    continue
  while j<N:
    if a[j]<A[i]:
      nokori-=(A[i]-a[j])
      a[j]=A[i]
    elif a[j]>A[i]:
      nokori-=M
      a[j]+=M
    if nokori<=0:
      break
    j+=1
  if j!=N and nokori<0:
    a[j]-=(-nokori)
    nokori=0
  if nokori==0:
    a=sorted(a)
    if a[-P]<=A[i]:
      ans=N-i
      
      break
    else:
      pass
  else:
    j-=1
    while j>=0:
      if a[j]<A[j]+M:
        x=A[j]+M-a[j]
        nokori-=x
        if nokori<=0:
          break
      else:
        pass
      j-=1
    a=sorted(a)
    if a[-P]<=A[i]:
      ans=N-i-2
      break
  i+=1
  
print(ans)

Submission status: Wrong Answer

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

for _ in range(m):
    a.sort()
    for i in range(v):
        a[i] += 1
a.sort()
j = 0
for k in range(1, n):
    if a[k-1] != a[k]:
        j += 1
    if j == p + 1:
        print(k)
        exit()
    if k == n - 1:
        print(n - 1)
        exit()

Submission status: Wrong Answer

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

N,M,V,P = map(int,input().split())
A = sorted([int(i) for i in input().split()])
print(A)
MINMAXA = A[N-P]

answer = 0
while A:
    tmp = A.pop()
    if tmp >= MINMAXA:
        if tmp > MINMAXA and V > 1:
            V -= 1
        answer += 1
    else:
        A.append(tmp)
        break

if V == 1:
    for i in range(len(A))[::-1]:
        if A[i] + M >= MINMAXA:
            answer += 1
        else:
            break
    print(answer)

else:
    if len(A) < V:
        print(answer)
    else:
        for _ in range(len(A) - V + 2):
            tmp = A.pop()
            if tmp + M >= MINMAXA:
                answer += 1
            else:
                break
        print(answer)

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)/(i-(P-1)) <= (A[i]+M):
            ans += 1
    S += A[i]
print(ans)

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)
                rlist = rlist[::-1]
                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)
                rlist = rlist[::-1]
                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:
import itertools

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

NO = [i for i in range(1, N + 1)]
A = list(map(int, input().split()))

d = dict(zip(NO, A))

init = [0 for _ in range(N)]
flag = dict(zip(NO, init))

combs = list(itertools.combinations(range(1, N + 1), V))
cmbs_pu = list(itertools.combinations(combs, M))
# print(cmbs_pu)


class MyClass:
    def __init__(self, d):
        self.d_duplicate = d

    def voting_judges(self):
        for combs2 in cmbs_pu:
            self.d_duplicate = d
            for comb in combs:
                for i in comb:
                    self.d_duplicate[i] += 1
            s_check = sorted(self.d_duplicate.items(), key=lambda x: x[1], reverse=True)
            s = iter(s_check)
            cnt = 0
            # print(self.d_duplicate)
            for j in s:
                if cnt == P:
                    for k, v in self.d_duplicate.items():
                        if v == j[1]:
                            if not flag[k]:
                                flag[k] = 1
                    break
                if not flag[j[0]]:
                    flag[j[0]] = 1
                cnt += 1
            self.d_duplicate = dict(zip(NO, A))

        print(list(flag.values()).count(1))


my_instance = MyClass(d)
my_instance.voting_judges()

Submission status: Wrong Answer

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

    sA = sorted(AN)
    rA = list(reversed(sA))
    border = rA[P - 1]

    # i = 0
    # while True:
    #     if border <= sA[i] + M:
    #         break
    #     i += 1

    if P < V:
        l = N - P
        r = P
        amari = V - l

        print(amari + r)
    else:
        print(len([a for a in AN if border <= a + M]))


main()

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
    print(idx)
    exit(0)
print(N)

Submission status: Wrong Answer

Solution code:
def main():
    n, m, v, p = list(map(int, input().split()))
    a = sorted(list(map(int, input().split())))
    # print(a)

    def value(i):
        if i+p >= n:
            return True
        if a[n-p] > a[i]+m:
            return False
        b = list(reversed([a[i]+m-j for j in a[:i] + a[i+1:n]]))[p-2:]
        # print(b)
        # if b[0] < 0:
        #    return False
        rest = v-n+len(b)
        if rest <= 0:
            return False
        # print(rest)

        c = [min(m, i) for i in b]
        d = [i for i in c][:-rest]
        e = [m-i for i in c][-rest:]
        #print(d, e)
        if sum(d) < sum(e):
            return False
        else:
            return True

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                b = med
            else:
                a = med+1
        if a == b:
            return a
        else:
            if value(a):
                return a
            else:
                return b

    # print(value(1))

    print(n-b_search(0, n-1, value))


main()

Submission status: Wrong Answer

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

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

cnt = 0
sum_memo = {}
su = 0
b = 0
b_rank = 0

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

Submission status: Wrong Answer

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

A.sort(reverse = True)
print("A:", A)

cnt = P - 2
for i in range(1, N):
  if i + cnt == N:
    break
  if A[P - 2] == A[P - 2 + i]:
    cnt = P - 2 + i
print("cnt:", cnt + 1)

B = A[cnt + 1:]
print("A:", A)

l = 0
r = len(B)

if V - (P - 1) <= 0:
  for i in range(len(B)):
    if B[i] + M >= A[P - 1]:
      cnt += 1
  print(cnt)
  exit()
else:
  while l + 1 < r:
    m = (l + r) // 2
    b = B[m] + V - (P - 1)
    
    n = (V - (P - 1)) * M
    for i in range(len(B)):
      if i != m:
        n -= min(M - B[i], (V - (P - 1)))
    if n < 0:
      r = m
    else:
      l = m
print(cnt + r - 1)

Submission status: Wrong Answer

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

li = []

  # print(lis)
cnt = 1
now = 0
ans = 0

border = lis[p-1]
li.append(0)
ind = 0
ssa = 0
for i in range(n-1):
    if lis[i]!=lis[i+1]:
        now += cnt
        cnt = 1
    else:
        cnt += 1
    if now <= p:
        ind += 1
    li.append(now)

  #print(li)
sa = 0
keykey = 1
key = 0

for i in range(n):
    if i >= p-1:
        sa += lis[i]
        if keykey:
            key = i
        keykey = 0

    if li[i]+1 <= p:
        ans += 1
  #        print(i,1)

    else:
        if lis[i] + m >= border:
            num = (p-1)+(n-li[i]-1)+1
            if num >= v:
                ans += 1
  #                print(i,2)
            else:
                nu = v-num
                if (sa -lis[i])-lis[i]*(i-key) <= (key-nu-1)*m:
                    ans += 1
  #                    print(i,3)
  #                    print(sa,lis[i],i,key,key-nu,m)
                else:
                    print(ans)
                    exit()
  #                    print(i,4)
  #                    print(sa, lis[i], i, key, key - nu, m)
        else:
  #            print(i,5)
            print(ans)
            exit()
    if i != n-1:
        if sa != 0 and lis[i] == lis[i+1]:
            sa -= lis[i]
            ssa += lis[i]
        if lis[i] != lis[i+1]:
            sa += ssa
            ssa = 0
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)

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

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

Submission status: Wrong Answer

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


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

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

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

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


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

def solve(i):
        if i >= n - p:
            return True

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

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

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

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
A=list(map(int,input().split()))
A=sorted(A,reverse=True)
B=[A[0]]
for i in range(n-1):
  B.append(B[i]+A[i+1])
#print(B)
ok = -1
ng = n
if p>=1:
  while ng-ok > 1:
    mid = (ok+ng) // 2 # 平均(小数切り捨て)
    #print(mid)
    if mid<p:
      ok=mid
      #print(0)
    elif n-(mid+1)+p>=v:
      if A[p-1]<=A[mid]+m:
        ok=mid
        #print(1)
      else:
        ng=mid
        #print(2)
    else:
      if A[mid]+m>=A[p-1]:
        a=m*(v-n-p+mid+1)
        b=A[mid]+m
        if p-2==-1:
          q=0
        else:
          q=p-2
        if (mid+1-p)*b-(B[mid-1]-B[q])>=a:
          ok=mid
          #print(3)
        else:
          ng=mid
          #print(4)
      else:
        ng=mid
        #print(5)
  print(ok+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):
    #print(al[i])
    if al[-p]!=al[i]:
        if v-i-1 < p: # p番目に大き物には足されない
            if al[i]+m < al[-p]: 
                impo+=1   
            else:
                break
        else:
            comp=0
            for j in al[i+1:-p]:
                comp+=j
            if float(al[i]+m)<= float((comp+m*(v-p-i))/len(al[i+1:-p])):
                impo+=1
            else:    
                break
    else:
        break
print(n-impo)

Submission status: Wrong Answer

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return [int(x) for x in sys.stdin.readline().split()]

def check(x,N,M,V,P,A):
    if (N-x)<=P:
        return True
    if(V<=x+P):
        return(A[x]+M>=A[N-P])

    x_score = A[x]+M
    total_v = (V-x-P)*M

    for i in range(x+1,N-P):
        total_v -= min(M,(x_score - A[i]))
    if total_v <= 0:
        return True
    else:
        return False

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

    if(check(0,N,M,V,P,A)):
        print(N)
        return

    isOK = N-1
    isNG = 0
    while(isOK-isNG>1):
        middle = (isOK+isNG)//2
        if(check(middle,N,M,V,P,A)):
            isOK = middle
        else:
            isNG = middle
    print(N-isOK)
    return


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
import numpy as np
A = list(map(int,input().split()))
A = np.array(sorted(A,reverse=True))
ans = P
x = A[P-1]
y = N-1
for i in range(P,N):
  a = A[i]
  if x==a:
    ans+=1
  else:
    y=i
    break
    
if y==N-1:
  print(N)
z = sum(A[P-1:y])
for i in range(y,N):
  a = A[i]
  d = a+M
  if x<=d:
    b = N-i+P-1
    c = M*(V-b)
    e = z+c
    f = d*(i-P+1)
    if f>=e:
      ans+=1
      
  z+=a
        
print(ans)

Submission status: Wrong Answer

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



s=[0]*n
s[0]=a[0]
for i in range(1,n):
    s[i]=s[i-1]+a[i]

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


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

Submission status: Wrong Answer

Solution code:
import sys
bbn=1000000007
	
#+++++

class mmm:
	def __init__(self):
		self.n, self.m, self.v ,self.p = map(int, input().split())
		self.al=list(map(int, input().split()))
		self.al.sort(reverse=True)
		r=0
		m=self.al[0]
		self.diffl=[0]*self.n
		for i,v in enumerate(self.al):
			r+=m-v
			self.diffl[i]=r
		self.border=self.al[self.p-1]
			
		pa(self.diffl)
		pa(self.al)
	
	def is_ok(self,ni):
		if ni <= self.p-1:
			return True
		vv=self.al[ni]
		if vv + self.m < self.border:
			return False
		
		nv=self.v-((self.p-1)+(self.n-ni-1))
		if nv < 0:
			return True
		
		ss=nv*self.m
		di=self.diffl[ni]-self.diffl[self.p-1]

		div=self.al[0]-self.border
		din=di-(div*(ni))
		pa((ni,di,din))
		if din > ss:
			return True
		return False
	
	
	def solve(self):
		ok=0
		if self.is_ok(self.n-1):
			return self.n
		ng=self.n-1
		
		while ng-ok>=2:
			mm=(ng+ok)//2
			if self.is_ok(mm):
				ok=mm
			else:
				ng=mm
			#print(ok,ng,mm)
		return ok+1

		
def main():
	a=mmm()
	ret=a.solve()
	print(ret)
	
	
	
	
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)

if __name__ == "__main__":
	if sys.platform =='ios':
		sys.stdin=open('inputFile.txt')
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import numpy as np
input = sys.stdin.readline
N, M, V, P = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
c = collections.Counter(A)
kakutei = A[-P]
kakutei_idx = A.index(kakutei)
kakutei_kosu = c[kakutei]
ans = N - kakutei_idx
V -= (P - 1)
V = max(1, V)
A = A[:kakutei_idx]
c_1 = collections.Counter(A)
c_1_keys = sorted(c_1.keys(), reverse=True)
onechan = np.array([kakutei] * kakutei_kosu)
for i in c_1_keys:
    V_i = V - c_1[i]
    flag = 0
    if V_i <= 0:
        if i + M >= kakutei:
            ans += c_1[i]
            flag = 1
    else:
        i_idx = A.index(i)
        V_i -= i_idx
        if V_i <= 0:
            if i + M >= kakutei:
                ans += c_1[i]
                flag = 1
        else:
            onechan_ = onechan[:]
            S = (i + M) - onechan_
            s = 0
            for j in S:
                if j > 0:
                    s += j
            if s >= (M * V_i):
                ans += c_1[i]
                flag = 1
    if not flag:
        print(ans)
        sys.exit()
    if flag:
        onechan = np.concatenate([onechan, np.array([i] * c_1[i])])
print(ans)

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
if idx == N -1:
    print(N)
else:
    print(idx)