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
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, m, v, p = LI()
    a = LI()
    a.sort(reverse=True)
    ok = p - 1
    ng = n
    def f(x):
        tmp = (n + p - 1 - x) * m
        t = a[x] + m
        if t < a[p - 1]:
            return False
        for i in range(p, x):
            tmp += max(0, t - a[i])
        return tmp >= m * v
    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if f(mid):
            ok = mid
        else:
            ng = mid
    print(ok + 1)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    if v<=p+n-1-x: return 1
    elif a[x]+m<a[p-1]: return 0
    able=(p+n-1-x)*m
    able+=sum([a[x]+m-a[k] for k in range(p-1,x)])
    if able>=m*v: return 1
    else: return 0

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

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>0:
    if r-l==1 and f(l)==1 and f(r)==0: break
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(l+1)

Submission status: Wrong Answer

Solution code:
import sys

def f(x):
    if v<=p+n-2-x: return 1
    elif a[x]+m<a[p-1]: return 0
    able=(p+n-1-x)*m
    able+=sum([a[x]+m-a[k] for k in range(p-1,x)])
    if able>=m*v: return 1
    else: return 0

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

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>0:
    if r-l==1 and f(l)==1 and f(r)==0: break
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(l+1)

Submission status: Wrong Answer

Solution code:
import sys

def f(i):
    if v<=p+n-2-i: return 1
    elif a[i]+m<a[p-1]: return 0
    able=(p+n-2-i)*m
    able+=sum([a[i]+m-a[k] for k in range(p-1,i)])
    if able>=m*v: return 1
    else: return 0

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

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>1:
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(r)

Submission status: Wrong Answer

Solution code:
import sys

def f(i):
    if v<=p+n-2-i: return 1
    elif a[i]+m<a[p-1]: return 0
    able=(p+n-2-i)*m
    able+=sum([a[i]+m-a[k] for k in range(p-1,i)])
    if able>=m*v: return 1
    else: return 0

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

print(a)
print([f(i) for i in range(n)])
l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>1:
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(r)

Submission status: Wrong Answer

Solution code:
import sys

def f(i):
    if v<=p+n-2-i: return 1
    elif a[i]+m<a[p-1]: return 0
    able=(p+n-1-i)*m
    able+=sum([a[i]+m-a[k] for k in range(p-1,i)])
    if able>=m*v: return 1
    else: return 0

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

l,r=0,n-1
if f(r)==1: print(n);sys.exit()
while r-l>1:
    tmp=(l+r)//2
    if f(tmp)==1: l=tmp
    else: r=tmp
print(r)

Submission status: Wrong Answer

Solution code:
import sys

def f(i):
    if v<=p+n-1-i: return 1
    elif a[i]+m<a[p-1]: return 0
    able=(p+n-1-i)*m
    able+=sum([a[i]+m-a[k] for k in range(p-1,i)])
    if able>=m*v: return 1
    else: return 0

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

l,r=0,n-1
if f(r)==0:
    while r-l>1:
        tmp=(l+r)//2
        if f(tmp)==1: l=tmp
        else: r=tmp

print(r)

Submission status: Wrong Answer

Solution code:
params_01 = input()
problems = input()

_, judges, votes, chosen = [int(i) for i in params_01.split(' ')]
problems = [int(i) for i in problems.split(' ')]

num_possible = 0
max_problem = max(problems)
for problem in problems:
  if problem >= (max_problem + judges):
    num_possible += 1
    
print(num_possible)

Submission status: Wrong Answer

Solution code:
# tokenakatta ...
def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    l = 0
    r = N - P + 1
    while l != r:
        k = (l + r)//2
        m = P * M + k * M
        t = A[k] + M
        for i in range(k+1, N-P+1):
            m += t - A[i]
        if m < M * V:
            l = k + 1
        else:
            r = k
    return N - r
print(main())

Submission status: Wrong Answer

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
ans = P
if V <= P:
    for i in A[P:]:
        if i + M >= A[P - 1]:
            ans += 1
else:
    cum_sum = list(itertools.accumulate(A)) + [0]
    for i in range(P, N):
        enemy = i - (P - 1)
        num = (V - (N - enemy))
        if num <= 0:
            if A[i] + M >= A[P-1]:
                ans += 1
        else:
            val = math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + max(0, M * num)) / enemy)
            if A[i] + M >= val:
                ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
ans = P
if V <= P:
    for i in A[P:]:
        if i + M >= A[P-1]:
            ans += 1
else:
    cum_sum = list(itertools.accumulate(A)) + [0]
    for i in range(P, N):
        enemy = i - (P - 1)
        val = math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + max(0, M * (V - (N - enemy)))) / enemy)
        if A[i] + M >= val:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
ans = P
if V <= P:
    for i in A[P:]:
        if i + M >= A[P-1]:
            ans += 1
else:
    cum_sum = list(itertools.accumulate(A))
    for i in range(P, N):
        enemy = i - (P - 1)
        val = math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + max(0, M * (V - (N - enemy)))) / enemy)
        if A[i] + M >= val:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

cum_sum = list(itertools.accumulate(A))
ans = P
for i in range(P, N):
    enemy = i - (P - 1)
    val = math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + max(0, M * (V - (N - enemy)))) / enemy)
    if A[i] + M >= math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + M * (V - (N - enemy))) / enemy):
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

if P == 1:
    ans = 1
    for i in A[1:]:
        if i + M >= A[0]:
            ans += 1
    print(ans)
elif N - V + 1 > P:
    ans = 0
    for i in A:
        if i + M >= A[P - 1]:
            ans += 1
    print(ans)
else:
    cum_sum = list(itertools.accumulate(A))
    ans = P
    for i in range(P, N):
        enemy = i - (P - 1)
        val = math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + max(0, M * (V - (N - enemy)))) / enemy)
        if A[i] + M >= math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + M * (V - (N - enemy))) / enemy):
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

N, M, V, P = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)

if P == 1:
    ans = 1
    for i in A[1:]:
        if i + M >= A[0]:
            ans += 1
    print(ans)
elif N - V + 1 > P:
    ans = 0
    for i in A:
        if i + M >= A[P - 1]:
            ans += 1
    print(ans)
else:
    cum_sum = list(itertools.accumulate(A))
    ans = P
    for i in range(P, N):
        enemy = i - (P - 1)
        if A[i] + M >= math.ceil((cum_sum[i - 1] - cum_sum[P - 2] + M * (V - (N - enemy))) / enemy):
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N, M, V ,P = map(int,input().split())
score = list(map(int,input().split()))
score.sort(reverse=True)
score_candidate = score[P:]

count = P
if V > (N-P):
    score_num = score[N-V-1]
    for num in score_candidate:
        if score_num <= num + M:
            count += 1
else:
    score_num = score[P-1] 
    for num in score_candidate:
        if score_num <= num + M:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p - 1 + n - i)*m + m
    for j in range(p, i):
        check += a[i-1] + m - a[j-1]
    return check >= m*v

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

a.sort(reverse=True)
ng = n
ok = 1

while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if judge(a, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p - 1 + n - i)*m
    for j in range(p, i):
        check += a[i-1] + m - a[j-1] if a[i-1] + m - a[j-1] < m else m
    return check >= m*(v - 1)

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

a.sort(reverse=True)
ng = n
ok = 0

while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if judge(a, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p - 1 + n - i)*m
    for j in range(p, i):
        check = check + a[i-1] + m - a[j-1]
    return check >= m*(v-1)

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

a.sort(reverse=True)
ng = n
ok = 0

while (ng - ok) > 1:
    mid = (ok + ng) // 2 if (ok + ng) % 2 == 0 else (ok + ng) // 2 + 1
    if judge(a, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

Solution code:
def judge(a, i, m, n, v, p):
    if i <= p: return True
    if a[i-1] + m < a[p-1]: return False
    check = (p - 1 + n - i)*m
    for j in range(p, i):
        check = check + a[i-1] + m - a[j-1]
    return check >= m*(v-1)

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

a.sort(reverse=True)
ng = n
ok = 0

while (ng - ok) > 1:
    mid = (ok + ng) // 2
    if judge(a, mid, m, n, v, p):
        ok = mid
    else:
        ng = mid
print(ok)

Submission status: Wrong Answer

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

# process
A.sort(reverse=True)
# print(A)

# idxの値と同じ値のインデックスの最大値
def getMaxIdx(al, idx):
    for i in range(idx+1, N):
        if al[i] != al[idx]:
            return i-1
    return N-1

# 採用されない下限のインデックス
def getLowerIdx(al, idx, num):
    for i in reversed(range(idx,N)):
        if al[i]+M >= num:
            return i+1
    return idx

# 2分探索
def binary_search(m, si, ei, x, y):
    mid = (x+y-1)//2
    score = A[mid]+M
    v = 0
    for i in reversed(range(si, ei)):
        if score > A[i]:
            v += score - A[i]

    # print("bs:{} {} {} {}".format(x, y, mid, v))
    if v < m:
        if mid == y-1:
            return mid-1
        # print("next:{} {}".format(x, mid+1))
        return binary_search(m, si, ei, x, mid+1)
    elif v >= m:
        if mid == y-1:
            return getMaxIdx(A, mid)
        # print("next:{} {}".format(mid+1, y))
        return binary_search(m, si, ei, mid+1, y)

adopt = getMaxIdx(A, P-1)
unadopt = getLowerIdx(A, adopt+1, A[P-1])
votable = (P+N-unadopt-1)*M # 1～P-1,unadopt～Nへ投票可能な数
if adopt+1 == unadopt:
    ans = adopt+1
elif votable >= M*V:
    ans = unadopt
else:
    ans = binary_search(M*V-votable, adopt+1, unadopt, adopt+1, unadopt)+1

# print("{} {} {}".format(M*V-votable, adopt+1, unadopt))

# output
print(ans)

Submission status: Wrong Answer

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

# process
A.sort(reverse=True)
# print(A)

# idxの値と同じ値のインデックスの最大値
def getMaxIdx(al, idx):
    for i in range(idx+1, N):
        if al[i] != al[idx]:
            return i-1
    return N-1

# 採用されない下限のインデックス
def getLowerIdx(al, idx, num):
    for i in reversed(range(idx,N)):
        if al[i]+M >= num:
            return i+1
    return idx

# 2分探索
def binary_search(m, si, ei, x, y):
    mid = (x+y-1)//2
    score = A[mid]+M
    v = 0
    for i in reversed(range(si, ei)):
        if score > A[i]:
            v += score - A[i]

    # print("bs:{} {} {} {}".format(x, y, mid, v))
    if v < m:
        if mid == y-1:
            return mid-1
        # print("next:{} {}".format(x, mid+1))
        return binary_search(m, si, ei, x, mid+1)
    elif v >= m:
        if mid == y-1:
            return getMaxIdx(A, mid)
        # print("next:{} {}".format(mid+1, y))
        return binary_search(m, si, ei, mid+1, y)

adopt = getMaxIdx(A, P)
unadopt = getLowerIdx(A, adopt+1, A[P])
votable = (P+N-unadopt-1)*M # 1～P-1,unadopt～Nへ投票可能な数
if adopt+2 == unadopt:
    ans = adopt+1
elif votable >= M*V:
    ans = unadopt
else:
    ans = binary_search(M*V-votable, adopt+1, unadopt, adopt+1, unadopt)+1

# print("{} {} {}".format(M*V-votable, adopt+1, unadopt))

# output
print(ans)

Submission status: Wrong Answer

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

n,m,v,p = mi()
alis = li()
alis.sort()
aalis = [0]*n
tmp = 0
for i in range(1,n):
    if alis[i-1] == alis[i]:
        tmp += 1
        aalis[i] = tmp
    else:
        tmp = 0
aalis = aalis[::-1]
alis= alis[::-1]
ans = p
alll = [0]*n
for i in range(p):
    alll[i] = 1
for i in range(p,n):
    if alis[i] == alis[i-1]:
        alll[i] = alll[i-1]
        if alll[i] == 1:
            ans += 1
        continue
    back = n-i
    nokori = v - back
    if nokori < p:
        if alis[p-1] <= alis[i] + m:
            alll[i] = 1
            ans += 1
    else:
        if alis[p-1] == alis[i]:
            alll[i] = 1
            ans += 1
        elif aalis[nokori-1] != 0:
            ima = aalis[nokori -1] -1
            if alis[i] + m >= alis[ima]:
                ans += 1
                alll[i] = 1
print(ans)

Submission status: Wrong Answer

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

n,m,v,p = mi()
alis = li()
alis.sort()
alis= alis[::-1]
ans = p
for i in range(p,n):
    back = n-i
    nokori = v - back
    if nokori < p:
        if alis[p-1] <= alis[i] + m:
            ans += 1
    else:
        if alis[p-1] == alis[nokori]:
            if alis[p-1] <= alis[i] + m:
                ans += 1
        elif alis[p-1] == alis[i]:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N,M,V,P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
#print(A)
thres = A[P-1]

# binary search
l, r = 0, N-1
for x in range(50):
  if l>r:
    break
  now = l + ceil((r - l)/2)
  #print(l,r,now)
    
  if A[now] > thres:
    l=now
    continue
  if A[now] + M < thres:
    r=now
    continue
    
  #voteしてよい数
  work = (P-1) * M + M + (N-now-1) * M
  for i in range(P-1,now):
    work += A[now] + M - A[i]
  if work >= M*V:
    l=now
  else:
    r=now

ans = now
#tiebreakの場合すべてOKなので、値が同じものをカウントする（たぶん不要）
for i in range(now,N):
  if A[i] == A[now-1]:
    ans += 1
  else:
    break
print(ans)
#print(l,r,now,ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N,M,V,P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
#print(A)
thres = A[P-1]

# binary search
l, r = 0, N-1
for x in range(1000):
  if l>r:
    break
  now = l + ceil((r - l)/2)
  #print(l,r,now)
    
  if A[now] > thres:
    l=now
    continue
  if A[now] + M < thres:
    r=now
    continue
    
  #voteしてよい数
  work = (P-1) * M + M + (N-now-1) * M
  for i in range(P-1,now):
    work += A[now] + M - A[i]
  if work >= M*V:
    l=now
  else:
    r=now

ans = now
#tiebreakの場合すべてOKなので、値が同じものをカウントする（たぶん不要）
for i in range(now,N):
  if A[i] == A[now-1]:
    ans += 1
  else:
    break
print(ans)
#print(l,r,now,ans)

Submission status: Wrong Answer

Solution code:
from math import ceil
N,M,V,P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
print(A)
thres = A[P-1]

# binary search
l, r = 0, N-1
for x in range(20):
  if l>r:
    break
  now = l + ceil((r - l)/2)
  print(l,r,now)
    
  if A[now] > thres:
    l=now
    continue
  if A[now] + M < thres:
    r=now
    continue
    
  #voteしてよい数
  work = (P-1) * M + M + (N-now-1) * M
  for i in range(P-1,now):
    work += A[now] + M - A[i]
  if work >= M*V:
    l=now
  else:
    r=now

ans = now
#tiebreakの場合すべてOKなので、値が同じものをカウントする（たぶん不要）
for i in range(now,N):
  if A[i] == A[now-1]:
    ans += 1
  else:
    break
print(ans)
#print(l,r,now,ans)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

n, m, v, p = (int(val) for val in input().split())
a = [int(val) for val in input().split()]
a.sort()
a.reverse()
c = 0
remain = 0
remain_i = 0
for i, val in enumerate(a):
    if i < p:
        c += 1
        continue
    if m < a[p - 1] - val:
        break

    if i >= p:
        remain_i = a[p - 1] - val
    diff = i - p + 1
    effv = v - (p - 1) - (n - i)
    b = effv * m - remain_i
    if b <= 0:
        border = a[p - 1]
    else:
        border = a[p - 1] + int(b / diff)
        if b % diff != 0:
            border += 1
    if border > m + val:
        break
    else:
        c += 1

    remain += remain_i
print(c)

Submission status: Wrong Answer

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

def check(x):
    if x<p:
        return True

    s = 0
    for i in range(n):
        if i<p-1:
            s += m
        elif p-1<=i<x:
            s += al[x]+m-al[i]
        else:
            s += m
    return s>=m*v

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

Submission status: Wrong Answer

Solution code:
import bisect
n,m,v,p=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
ok=n#idx
ng=-1
def solve(x):
    if bisect.bisect_right(l,l[x])>=n-p+1:
        return 1
    lx=l[x]+m
    lxi=bisect.bisect_right(l,lx)-1
    if lxi<=n-p-1:
        return 0
    #n-p-1<lxi
    f=0
    for i in range(n):
        if i<=x or i>n-p:
            f+=m
            continue         
        else:
            f+=min(lx-l[i],m)
    if f>v*m:
        return 2
    else:
        return 0
#for i in range(n):
    #print(solve(i))
while ok-ng>1:
    x=(ok+ng)//2
    if solve(x):
        ok=x
    else:
        ng=x
    #print(x)
print(n-ok)

Submission status: Wrong Answer

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

A.sort(reverse=True)
p = A[P-1]

#X番目の問題に可能性があるかどうか(0-indexed)
def f(X):
    x = A[X]
    if x + M < p: return False
    votes = M*V
    votes -= M
    votes -= M * (P-1)
    for i in range(P-1,N):
        if i == X: continue
        votes -= max(0, x + M - 1 - A[i])
    return votes <= 0

ok = 0
over = N
while over - ok > 1:
    mid = (over + ok) // 2
    if f(mid): ok = mid
    else: over = mid
print(ok+1)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
l=list(map(int,input().split()))
l.sort()
ok=n-1#idx
ng=0
def solve(x):
    if n-x<=p:
        return True
    lx=l[x]+m
    f=0
    g=0
    for i in range(n):
        if i==x:
            continue
        if lx>=l[i]:
            g+=min(lx-l[i],m)
        else:
            f+=1
    if f>p:
        return False
    if f*m+g<=(v-1)*m:
        return True
    else:
        return False
            
while ok-ng>1:
    x=(ok+ng)//2
    if solve(x):
        ok=x
    else:
        ng=x
print(ok)

Submission status: Wrong Answer

Solution code:

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

A = list(map(int, input().split()))


A.sort(reverse=True)
ok = P-1
ng = N - 1
while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    curr_max = A[mid] + M

    if curr_max < A[P-1]:
        ng = mid
        continue

    cnt = 0
    # midと上位P-1位に＋Mした分
    cnt += M + (P-1) * M
    for i in range(P-1, N):
        if i == mid: continue

        cnt += min(M, max(0, curr_max - A[i]))

    if cnt >= M*V:
        ok = mid
    else:
        ng = mid

print(ok + 1)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    border = A[N - P]

    low, high = 0, N
    while high - low > 1:
        mid = (low + high) //2
        point = A[mid] + M
        if point < border: low = mid
        elif mid >= N - P: high = mid
        else:
            space = (mid + P) * M
            for i in range(mid + 1, N - P + 1 ): space += point - A[i]
            if space >= M * V: high = mid
            else: low = mid
    print(N - low - 1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    border = A[N - P]

    low, high = 0, N
    while high - low > 1:
        mid = (low + high) //2
        point = A[mid] + M
        if point < border: low = mid
        elif mid >= N - P: high = mid
        else:
            if mid >= V - 1: high = mid
            else:
                space = 0
                for i in range(mid + 1, N - P + 1): space += max(0, point - A[i])    
                if space >= (M - mid - 1) * V: high = mid
                else: low = mid
    print(N - low )
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    border = A[N - P]

    low, high = 0, N
    while high - low > 1:
        mid = (low + high) //2
        point = A[mid] + M
        if point < border: low = mid
        elif mid >= N - P: high = mid
        else:
            space = (mid + P) * M
            for i in range(mid + 1, N - P + 1): space -= point - A[i]
            if space >= M * V: high = mid
            else: low = mid
    print(N - low - 1)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
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:
        i = (l+r) >> 1
        ai = a[i]
        aim = ai+m
        ri = bisect.bisect_right(a,aim)
        if n-ri >= p:
            l = i
            continue
        cnt = 0
        for j in range(n-p):
            if i == j:
                continue
            cnt += min(m,aim-a[j])
        if cnt >= m*(v-p):
            r = i
        else:
            l = i
    print(n-r)
    return

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

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect

def solve():
    input = sys.stdin.readline
    N, M, V, P = map(int, input().split())
    A = [int(a) for a in input().split()]
    A.sort()
    A.append(10 ** 10)
    B = []
    start = A[0]
    count = 1
    total = [0]
    tc = 0
    for i in range(N):
        if A[i+1] == start: count += 1
        else:
            B.append(start)
            total.append(tc + count)
            tc += count
            start = A[i + 1]
            count = 1

    #print(B)
    #print(total)

    border = A[N - P]
    low, high = 0, len(B)
    while high - low > 1:
        mid = (low + high) //2
        #print(mid, total[mid + 1])
        if total[mid + 1] > N - P: high = mid
        elif total[mid + 1] >= V:
            if B[mid] + M >= border: high = mid
            else: low = mid
        else:
            midPoint = B[mid] + M
            if midPoint < border: low = mid
            else:
                larger = bisect(B, midPoint)
                if N - total[larger] + V - total[mid + 1] <= P: high = mid
                else: low = mid
    #print(low)
    print(N - total[low + 1])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
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:
        i = (l+r) >> 1
        ai = a[i]
        aim = ai+m
        ri = bisect.bisect_right(a,aim)
        if ri <= n-p:
            l = i
            continue
        li = bisect.bisect_right(a,ai)
        s = li+n-ri-1
        if s >= v-1:
            r = i
            continue
        res = v-1-s
        resp = p-n+ri-1
        if res <= resp:
            r = i
            continue
        res -= resp
        ak = [aim-a[k] for k in range(li,ri-res)]
        if sum(ak) >= m*res:
            r = i
        else:
            l = i
    print(n-r)
    return

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