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:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
# mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,v,p = inpm()
    a = inpl()
    a.sort(reverse=True)
    ok = -1
    ng = n
    while ng-ok >1:
        mid = (ok+ng)//2
        if mid+1 <= p:
            ok = mid
        elif a[p-1] > a[mid]+m:
            ng = mid
        else:
            key = 0
            cnt = (p)*m + (n-mid-1)*m
            for i in range(mid-1,p-1,-1):
                if a[i] > a[mid]+m:
                    ng = mid
                    key = 1
                    break
                cnt += a[mid]-a[i]+m
            if key:
                break
            if cnt >= m*v:
                ok = mid
            else:
                ng = mid
    print(ok+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
# mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,v,p = inpm()
    a = inpl()
    a.sort(reverse=True)
    ok = 0
    ng = n
    while ng-ok >1:
        mid = (ok+ng)//2
        if mid <= p:
            ok = mid
        elif a[p-1] > a[mid]+m:
            ng = mid
        else:
            key = 0
            cnt = (p)*m + (n-mid-1)*m
            for i in range(mid-1,p-1,-1):
                if a[i] > a[mid]+m:
                    ng = mid
                    key = 1
                    break
                cnt += a[mid]-a[i]+m
            if key:
                break
            if cnt >= m*v:
                ok = mid
            else:
                ng = mid
    print(ok+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
# mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,m,v,p = inpm()
    a = inpl()
    a.sort(reverse=True)
    ok = 0
    ng = n
    pre = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        for j in range(n):
            pre[i][j] = a[i]-a[j]+m
    for i in range(n):
        pre[i] = tuple(pre[i])
    pre = tuple(pre)
    while ng-ok >1:
        mid = (ok+ng)//2
        if mid <= p:
            ok = mid
        elif a[p-1] > a[mid]+m:
            ng = mid
        else:
            cnt = (p)*m + (n-mid-1)*m
            for i in range(p,mid):
                cnt += pre[mid][i]
            if cnt >= m*v:
                ok = mid
            else:
                ng = mid
    print(ok+1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
from bisect import bisect_left
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    # 降順
    A.sort(reverse=True)
    acc = list(accumulate(A))

    left = P-1
    right = len(A)
    L = M*(V-N)-acc[P-2]
    K = A[P-1]-M
    while right - left > 1:
        mid = (right + left)//2
        cap = (mid-P+1)*A[mid] - acc[mid-1]
        if A[mid] < K or cap < L:
            right = mid
        else:
            left = mid
    print(right)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    # 降順
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)
    L = M*(V-N)-acc[P-1]
    while right - left > 1:
        mid = (right + left)//2
        cap = (mid-P+1)*A[mid] - acc[mid]
        if cap >= L:
            left = mid
        else:
            right = mid
    print(right)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    # 降順
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2

        if A[mid]+M < A[P-1]:
            right = mid
            continue

        cap = M*N + (mid-P+1)*(A[mid]) + acc[P-1]-acc[mid]
        if cap >= M*V:
            left = mid
        else:
            right = mid
    print(right)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    # 降順
    A.sort(reverse=True)
    acc = [0]+list(accumulate(A))

    left = P-1
    right = len(A)-1
    while right - left > 1:
        mid = (right + left)//2

        # if A[mid]+M < A[P-1]:
        #     right = mid
        #     continue

        cap = M*N + (mid-P+1)*(A[mid]) + acc[P-1]-acc[mid]
        if cap >= M*V:
            left = mid
        else:
            right = mid
    print(right)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

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,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
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 LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m,v,p=LI()
a=LI()
b=sorted(a)[::-1]

def check(k):
    tot=m*v
    if k<=p-1:
        return True
    if b[p-1]>b[k]+m:
        return False
    tot-=m*p
    mx=b[k]+m
    for i in range(p,n):
        if i==k:
            continue
        tot-=min(max(0,min(mx-b[i],m)),m)

    if tot<=0:
        return True
    else:
        return False
        
l,r=0,n

while r-l>1:
    mid=(l+r)//2
    if check(mid):
        l=mid
    else:
        r=mid

ok=b[l]
ans=sum([1 if i>=ok else 0 for i in b])
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

Ap = A[P-1]
iOK = 2
iNG = N
while iOK+1 < iNG:
    x = (iOK+iNG)//2
    if x <= P:
        iOK = x
    elif Ap - A[x] > M:
        iNG = x
    elif P-1+N-x >= V:
        iOK = x
    elif (A[x]+M)*(x-P+1)-np.sum(A[P-1:x]) >= M*(V-P+1-N+x):
        iOK = x
    else:
        iNG = x

ans = iOK + 1
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    ans = 0

    # 降順
    A.sort(reverse=True)

    acc = [0]+list(accumulate(A))

    for i in range(N):
        # ソート後の冒頭P問は大きいので可
        if i < P:
            ans += 1
            continue
        if A[i]+M < A[P-1]:
            continue

        # 対象iがP問目として選ばれるために
        # 許容可能な投票数と、実際の投票数を比較する。
        cap = M*(P+N-i-1)
        cap += (i-P+1)*(A[i]+M)
        cap -= acc[i-1] - acc[P-2]
        if cap >= M*V:
            ans += 1
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):

    ans = 0

    # 降順
    A.sort(reverse=True)

    acc = [0]+list(accumulate(A))

    for i in range(N):
        # ソート後の冒頭P問は大きいので可
        if i < P:
            ans += 1
            continue

        # 対象iがP問目として選ばれるために
        # 許容可能な投票数と、実際の投票数を比較する。
        cap = M*(P+N-i-1)
        cap += (i-P+1)*(A[i]+M)
        cap -= acc[i-1] - acc[P-2]
        if cap >= M*V:
            ans += 1
    print(ans)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    V = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, M, V, P, A)


if __name__ == '__main__':
    main()

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,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
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 LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m,v,p=LI()
a=LI()
b=sorted(a)[::-1]

def check(k):
    tot=m*v
    if k<=p-1:
        return True
    if b[p-1]>b[k]+m:
        return False
    tot-=m*p
    mx=b[k]+m
    #show((k,b[k],tot),p,v,mx,b[p:n])
    for i in range(p,n):
        if i==k:
            continue
        tot-=min(max(0,mx-b[i]),m)
    #show(tot)

    if tot<=0:
        return True
    else:
        return False
        
l,r=0,n

while r-l>1:
    mid=(l+r)//2
    if check(mid):
        l=mid
    else:
        r=mid
    #show(l,mid,r)
ok=b[l]
ans=sum([1 if i>=ok else 0 for i in b])
print(ans)

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,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
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 LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m,v,p=LI()
a=LI()
b=sorted(a)[::-1]

def check(k):
    tot=m*v
    if k<=p-1:
        return True
    if b[p-1]>b[k]+m:
        return False
    tot-=m*p
    mx=b[k]+m
    #show((k,b[k],tot),p,v,mx,b[p:n])
    for i in range(p,n):
        if i==k:
            continue
        tot-=min(max(0,mx-b[i]),m)
    #show(tot)

    if tot<=0:
        return True
    else:
        return False
        
l,r=0,n

while r-l>1:
    mid=(l+r)//2
    if check(mid):
        l=mid
    else:
        r=mid
    #show(l,mid,r)
ok=b[l]
print(l+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,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
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 LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n,m,v,p=LI()
a=LI()
b=sorted(a)[::-1]

def check(k):
    tot=m*v
    if k<=p-1:
        return True
    if b[p-1]>b[k]+m:
        return False
    tot-=m*p
    mx=b[k]+m
        
    for i in range(p,n):
        if i==k:
            continue
        tot-=max(0,mx-b[i])
    

    if tot<=0:
        return True
    else:
        return False
        
l,r=0,n

while r-l>1:
    mid=(l+r)//2
    if check(mid):
        l=mid
    else:
        r=mid

ok=b[l]
print(l+1)

Submission status: Wrong Answer

Solution code:
def nibutan(L):
  ok = len(L)
  ng = -1
  while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    if nasu(mid, L):
      ok = mid
    else:
      ng = mid
  return ok

def nasu(n, L):
  p = L[n] + M
  if p < L[K]:
    return False
  m = (V - 1 - (n + P - 1)) * M
  if m <= 0:
    return True
  for i in range(n + 1, K):
    m -= p - L[i]
    if m <= 0:
      return True
  return False

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

A.sort()
K = N - P
T = A[K]
print(N - nibutan(A))

Submission status: Wrong Answer

Solution code:
def check(a, n, m, v, i, j):
    # 採用可能性が確定している問題に入れて良い票数
    b_sum = (i + 1) * m
    # jよりスコアの低い問題に入れて良い票数
    b_sum += (n - (j + 1)) * m
    # それ以外の問題はAx + M - Aiが入れて良い票数
    for k in range(i + 1, j):
        b_sum += a[j] + m - a[k]
    # print(b_sum, n, m, v, i, j)
    return b_sum >= m * v

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

    # スコアの降順にソート
    a.sort()
    a.reverse()

    # 採用可能性あるのが確定した問題のindex
    i = p - 1
    
    # 採用可能性のある問題数
    questions = i + 1
    left = i + 1
    right = n - 1
    # print(left, right)
    mid = (left + right) // 2
    while left <= right:
        if check(a, n, m, v, i, mid):
            questions += mid - left + 1
            left = mid + 1
            mid = (left + right) // 2
        else:
            right = mid - 1
            # print(left, right)
            mid = (left + right) // 2
    
    print(questions)

main()

Submission status: Wrong Answer

Solution code:
def check(a, n, m, v, i, j):
    # 採用可能性が確定している問題に入れて良い票数
    b_sum = (i + 1) * m
    # jよりスコアの低い問題に入れて良い票数
    b_sum += (n - (j + 1)) * m
    # それ以外の問題はAx + M - Aiが入れて良い票数
    for k in range(i + 1, j):
        b_sum += a[j] + m - a[k]
    # print(b_sum, n, m, v, i, j)
    return b_sum >= m * v

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

    # スコアの降順にソート
    a.sort()
    a.reverse()

    # 採用可能性あるのが確定した問題のindex
    i = p - 1
    
    # while a[i + 1] == t:
    #     i += 1

    # 採用可能性のある問題数
    questions = i + 1
    for j in range(i + 1, n):
        if check(a, n, m, v, i, j):
            questions += 1
        else:
            print(questions)
            exit(0)
    print(questions)

main()

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
x = a[p-1]
a = a[p-1:]
l = list(accumulate(a))
ans = p

for i in range(n-p):
    if a[i] + m < x:
        continue
    s = (n-(p+i+1))*m + p*m
    s += (a[i+1] + m) * (i+1)
    s -= l[i]
    if s >= m*v:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
x = a[p-1]
a = a[p:]
l = list(accumulate(a))
ans = p

for i in range(n-p):
    if a[i] + m < x:
        continue
    s = (n-(p+i+1))*m + p*m
    s += (a[i] + m) * i
    s -= (l[i] - a[i])
    if s >= m*v:
        ans += 1
print(ans)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m,v,p = LI()
a = LI()
a.sort(reverse=True)
a = a[p-1:]
l = list(accumulate(a))
ans = p-1

for i in range(n-p+1):
    s = (n-p-(i+1))*m + (p-1)*m
    s += (a[i] + m) * i
    s -= (l[i] - a[i])
    if s >= m*v:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8


def solve(*args: str) -> str:
    n, m, v, p = map(int, args[0].split())
    A = list(map(int, args[1].split()))
    A.sort()

    left, right = 0, n-1

    while left+1 < right:
        i = left+(right-left)//2

        if A[i]+m < A[n-p]:
            left = i
            continue

        pts = m*min(n, i+p)
        for j in range(i+1, n-(p-1)):
            pts += max(0, A[i]+m-A[j])

        if m*v <= pts:
            right = i
        else:
            left = i

    return str(n-right)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np

stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m, v, p = na()
a = na()
a.sort(reverse=True)
a = np.array(a)
print(a)
left = 0
right = n
def check(i):
    c = a[i] + m
    s = (p-1) * m + np.sum(np.minimum(c - a[p-1:], m))
    if i+1 <= p:
        return True
    elif a[i] + m < a[p-1]:
        return False
    elif s >= m * v:
        return True
    else:
        return False
while left + 1 < right:
    x = (left + right) // 2
    if check(x):
        left = x
    else:
        right = x
print(left + 1)

Submission status: Wrong Answer

Solution code:
import sys
import math
import numpy as np

stdin = sys.stdin
mod = 10**9 + 7

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
sa = lambda h: [list(map(int, stdin.readline().split())) for i in range(h)]

n, m, v, p = na()
a = na()
a.sort(reverse=True)
a = np.array(a)
left = p - 1
right = n - 1
def check(i):
    c = a[i] + m
    s = (p-1) * m + np.sum(np.minimum(c - a[p-1:], m))
    if i+1 <= p:
        return True
    elif a[i] + m < a[p-1]:
        return False
    elif s >= m * v:
        return True
    else:
        return False
while left + 1 < right:
    x = (left + right) // 2
    if check(x):
        left = x
    else:
        right = x
print(left + 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

ng = -1
ok = N - P
#print(a)
def check(x):
  vs = M * V
  p = N
  for i in range(N):
    if a[i] > a[x] + M:
      p = i - 1
      break
  #print(x, vs, p)
  if p < N - P: return False
  #print(x, vs)
  for i in range(N - min(V, P) + 1, N):
    vs -= M
  #print(x, vs)
  for i in range(N - min(V, P)):
    vs -= min(max(a[x] + M - a[i], 0), M)

  #print(x, vs)
  return vs <= 0

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

ng = -1
ok = N - P
#print(a)
def check(x):
  vs = M * V
  p = N
  for i in range(N):
    if a[i] > a[x] + M:
      p = i - 1
      break
  #print(x, vs, p)
  if p < N - P: return False
  #print(x, vs)
  for i in range(N - P + 1, N):
    vs -= M
  #print(x, vs)
  for i in range(N - P):
    vs -= min(max(a[x] + M - a[i], 0), M)

  #print(x, vs)
  return vs <= 0

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, V, P = map(int, input().split())
a = list(map(int, input().split()))
a.sort()

ng = -1
ok = N - P
#print(a)
def check(x):
  vs = M * V
  p = N
  for i in range(N):
    if a[i] > a[x] + M:
      p = i
      break
  #print(x, vs, p)
  if p < N - P: return False
  #print(x, vs)
  for i in range(N - P + 1, N):
    vs -= M
  #print(x, vs)
  for i in range(N - P):
    vs -= min(max(a[x] + M - a[i], 0), M)

  #print(x, vs)
  return vs <= 0

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