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:


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

A.sort(reverse=True)

can_chosen = 0
can_not_chosen = N-1

while abs(can_chosen - can_not_chosen) > 1:
    mid = (can_chosen + can_not_chosen) // 2
    # 元から上位P位にあれば選ばれうる
    if mid < P:
        can_chosen = mid
    else:
        # 現在選ばれるか考えている値の最高の得点はM人全員が選んだパターン
        curr_max = A[mid] + M
        # P足しても初期のP位のものを上回れないので選ばれない
        if A[P - 1] > curr_max:
            can_not_chosen = mid
        else:
            cnt = 0
            # 下から現在選ばれているか考えてる値までに＋Mする
            cnt += (N - mid) * M
            # 上位P-1位に+Mする
            cnt += (P - 1) * M
            # 現在見てる値より一つ順位が上からP位までに、curr_maxを超えないように割り振る
            for i in range(P-1, mid):
                cnt += max(0, curr_max - A[i])

            # 割り振って余りがなければ、その値は選ばれうるので、より小さい値を見に行く
            if cnt >= M*V:
                can_chosen = mid
            else:
                can_not_chosen = mid


# can_chosenより上の物は選ばれうるので最後まで詰めていくと、can_chosenには選ばれる物の中で一番小さい値のインデックスが入っているから、、+1して個数に変える
print(can_chosen + 1)

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
print(A)
cnt = 0
for i in range(N-1,-1,-1):
    if (P-1) + i >= V - 1:
        # 採用されるか
        if A[i] + M >= A[-P]:
            cnt += 1
    else:
        Q = A[i+1:-P+1]
        tmp_V = V - 1 - (P-1) - i
        tmp_M = M

        if len(Q) <= tmp_V:
            break

        """
        tmp_V個選んで+1する行動をtmp_M回する
        差を最小にしたときの最大値は？
        """

print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
a = a[::-1]
tmp = a[p-1]
ans = p
l = 0
r = n
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r-1:
    mid = (l+r)//2
    if mid<=p:
        l = mid
        continue
    if a[mid]+m<tmp:
        r = mid
    else:
        thesh = a[mid]+m 
        amari = v-p
        for i in range(p-1,n):
            if i==mid:
                continue
            amari-=thesh-a[i]
        if amari<=0:
            l = mid
        else:
            r=mid
print(l-1)

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N,M,V,P = LI()
A = LI()

A.sort(reverse=True)
cumA = [A[0]]
for i in range(1,N):
    cumA.append(cumA[-1]+A[i])

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

print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())))
if p >= v:
  print(sum([1 for b in a if b >= a[n-p]-m]))
else:
  s = p
  for i in range(n-p+1):
    if a[i] >= a[n-p]-m:
      if sum([max(a[i]+m-a[j],0) for j in range(i+1,n-p+1)]) >= (v-p-i+1)*m:
        s += 1
  print(s)

Submission status: Wrong Answer

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

if v <= p:
  for i in range(n-p):
    if a[i] + m >= a[n-p]:
      break;
  print(n-i)
else:
  for i in range(n-p+1):
    if v-p-i <= 0:
      if a[i] + m >= a[n-p]:
        break;
    else:
      if (a[i]+m)*(n-p-i) >= sum(a[i+1:n-p+1])+m*(v-p-i):
        break;
  print(n-i)

Submission status: Wrong Answer

Solution code:
#2分探索は点数でなく順位
n,m,v,p = map(int, input().split( ))
a = list(map(int, input().split( )))###
a.sort(reverse = True)
mx = n
mn = p-1

while mx-mn>1:
    md = (mx+mn)//2
    sc = (p-1)*m+(n-md-1)*m
    for i in range(md):
        sc += max(a[md]+m-a[i],0)
    if sc>=v*m:
        mn = md
    else:
        mx = md
print(mn+1)

Submission status: Wrong Answer

Solution code:
#2分探索は点数でなく順位
n,m,v,p = map(int, input().split( ))
a = list(map(int, input().split( )))+[-1]
a.sort(reverse = True)
mx = n
mn = p-1

while mx-mn>1:
    md = (mx+mn)//2
    sc = (p-1)*m+(n-md-1)*m
    for i in range(md):
        sc += max(a[md]+m-a[i],0)
    if sc>=v*m:
        mn = md
    else:
        mx = md
print(mn+1)

Submission status: Wrong Answer

Solution code:
#2分探索は点数でなく順位
n,m,v,p = map(int, input().split( ))
a = list(map(int, input().split( )))+[-1]
a.sort(reverse = True)#いつまでも間違えたので解説に合わせたが
mx = n
mn = 0

while mx-mn>1:
    md = (mx+mn)//2
    sc = (p-1)*m+(n-md)*m##なぜか0にしてifで帳尻合わせると間違える
    for i in range(md):
        sc += max(a[md]+m-a[i],0)
    if sc>=v*m:
        mn = md
    else:
        mx = md
print(mn+1)

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	ans = float("inf")
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M and A[mid] + M >= A[N - P]:
			ans = min(ans, mid)
			right = mid - 1
		elif mid >= N - P - 1:
			ans = min(ans, mid)
			right = mid - 1			
		else:
			left = mid + 1

	return N - ans

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	ans = float("inf")
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M and A[mid] + M >= A[N - P - 1]:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return N - ans

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	ans = float("inf")
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M and A[mid] + M >= A[N - P]:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return N - ans

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	ans = float("inf")
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M:
			ans = min(ans, mid)
			right = mid - 1
		else:
			left = mid + 1

	return N - ans

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M:
			right = mid - 1
		else:
			left = mid + 1

	mid = (left + right) // 2
	return N - mid - 1

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P) * M:
			right = mid - 1
		else:
			left = mid + 1


	return N - mid

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

con = 10 ** 9 + 7
#入力受け取り
def getlist():
	return list(map(int, input().split()))

def Binary_Search(A, N, M, V, P):
	#初期化
	#B:累積和
	B = [0]
	for i in range(N):
		B.append(B[i] + A[i])
	left = 0
	right = N - 1
	#二分探索
	while left <= right:
		mid = (left + right) // 2
		if (A[mid] + M) * (N - P - mid) >= B[N - P + 1] - B[mid + 1] + (V - mid - P + 1) * M:
			right = mid - 1
		else:
			left = mid + 1


	return N - mid

#処理内容
def main():
	N, M, V, P = getlist()
	A = sorted(getlist())
	ans = Binary_Search(A, N, M, V, P)

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(i):

    B=[A[m] for m in range(N-(P-1)) if m!=i]

    C=A[i]+M
    a=V-P

    if C<A[-P]:
        return(0)
    else:
        if a>0:
            Votenum=a*M
            for b in B:
                Votenum-=min(C-b,M)
                if Votenum<=0:
                    return(1)

            return(0)
        else:
            return(1)




if main(0):
    print(N)
    exit()
st=0
end=N-P+1

while 1:
    a=(st+end)//2
    if main(a):
        end=a
    else:
        st=a

    if end-st<=1:
        break

print(st,end)
if main(st):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-P)

    if s<A[-P]:
        return(0)
    else:
        if a>0:

            tempSUM+=a*M
            if tempSUM<=s*(N-P):
                return(1)
            else:
                return(0)

        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-P)

    if s<A[-P]:
        return(0)
    else:
        if a>0:
            tempSUM+=a*M
            if s>tempSUM//(N-P) or s==tempSUM//(N-P) and tempSUM%(N-P) == 0:
                return(1)
        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))

    if s<A[-P]:
        return(0)
    else:
        if a>0:
            tempSUM+=a*M
            if tempSUM%(N-1-(P-1)) and s>tempSUM//(N-1-(P-1)) or s>=tempSUM//(N-1-(P-1)):
                return(1)
        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))

    if s<A[-P]:
        return(0)
    else:
        if a>0:
            tempSUM+=a*M
            if tempSUM%(N-1-(P-1)) and s>tempSUM//(N-1-(P-1)) or s==tempSUM//(N-1-(P-1)):
                return(1)
        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))

    if s<A[-P]:
        return(0)
    else:
        if a>0:
            tempSUM+=a*M
            return(s>tempSUM//(N-1-(P-1)))
        else:
            return(1)    


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))


    if a>0:
        tempSUM+=a*M
        return(s>tempSUM//(N-1-(P-1)))
    else:
        if s<A[-P]:
            return(0)
        else:
            return(1)


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))
    if a>0:
        tempSUM+=a*M
    if s<A[-P]:
        return(0)
    return(s>tempSUM//(N-1-(P-1)))


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-(P-1)])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))
    tempSUM+=a*M
    return(s>tempSUM//(N-1-(P-1)))


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math
N,M,V,P=map(int,input().split())
A=sorted(list(map(int,input().split())))
_SUM=sum(A[:N-M])



def main(s):
    tempSUM=_SUM-s
    s+=M
    a=(V-1-(P-1))
    tempSUM+=a*M
    return(s>tempSUM//(N-1-(P-1)))


if main(A[0]):
    print(N)
    exit()
st=0
end=N-1

while 1:
    a=(st+end)//2
    if main(A[a]):
        end=a
    else:
        st=a

    if end-st<=1:
        break

if main(A[st]):
    print(N-st)
else:
    print(N-end)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
import numpy as np
A=np.array(sorted(map(int,input().split())))
ng,ok=-1,N-P+1
while ng+1<ok:
    t=(ng+ok)//2
    if A[t]+M<A[-P] or np.sum(np.minimum(M,A[t]+M-A[t+1:-P+1]))<M*(V-P-t):
        ng=t
    else:
        ok=t
print(N-ok)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
import numpy as np
A=np.array(sorted(map(int,input().split())))
ng,ok=-1,N-P+1
while ng+1<ok:
    t=(ng+ok)//2
    if A[t]<A[-P] or np.sum(np.minimum(M,A[t]+M-A[t+1:-P+1]))<M*(V-P-t):
        ng=t
    else:
        ok=t
print(N-ok)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
import numpy as np
A=np.array(sorted(map(int,input().split())))
ng,ok=-1,N-P+1
while ng+1<ok:
    t=(ng+ok)//2
    if np.sum(np.minimum(M,A[t]+M-A[t+1:-P+1]))<M*(V-P-t):
        ng=t
    else:
        ok=t
print(N-ok)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
import numpy as np
A=np.array(sorted(map(int,input().split())))
A[-P+1:]+=M
a=np.cumsum(A)
ng,ok=-1,N-P+1
while ng+1<ok:
    t=(ng+ok)//2
    if (A[t]+M)*(N-P-t)-a[-P]+a[t]<M*(V-P-t):
        ng=t
    else:
        ok=t
print(N-ok)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort(reverse=True)
ans = 0
trash = 0
print(lis)
for i in range(n):
    if i+1 <= p:
        ans += 1
    else:
        if lis[i] + m >= lis[p-1]:
            if (lis[i]+m)*(i-(p-1))-trash >= m * (v-(p-1)-(n-i)):
  #                 print(lis[i]+m,i-(p-1)-trash,m*(v-(p-1)-(n-i)))
                ans += 1
    if i+1 >= p:
        trash += lis[i]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = -1
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    if indR<N-P+1:
        low = mid
        continue
    tot = M*V
    i = indL
    while i<N-P+1:
        if tot-(mid-A[i])<0:break
        tot -= mid-A[i]
        i += 1
    if i<N-P+1:
        high = mid
        break
    if 0<=tot<=M*(P-1+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = -1
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    if indR<N-P+1:
        low = mid
        continue
    dif = 0
    for i in range(indL,N-P+1):
        dif += mid-A[i]
    if 0<=M*V-dif<=M*(P-1+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = -1
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    if indR<N-P+1:
        low = mid
        continue
    dif = 0
    for i in range(indL,indR):
        dif += mid-A[i]
    tot = 0
    for i in range(N-P+1,indR):
        tot += M-mid+A[i]
    if 0<=M*V-dif<=tot+M*(N-indR+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = -1
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    dif = 0
    for i in range(indL,indR):
        dif += mid-A[i]
    tot = 0
    for i in range(N-P+1,indR):
        tot += M-mid+A[i]
    if indR>=N-P+1 and 0<=M*V-dif<=tot+M*(N-indR+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = A[bisect_left(A,A[N-P])-1]
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    if indL>N-P:
        high = mid
        continue
    dif = 0
    for i in range(indL,indR):
        dif += mid-A[i]
    tot = 0
    for i in range(N-P+1,indR):
        tot += M-mid+A[i]
    if indR>=N-P+1 and 0<=M*V-dif<=tot+M*(N-indR+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = A[bisect_left(A,A[N-P])-1]
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    dif = 0
    for i in range(indL,indR):
        dif += mid-A[i]
    tot = 0
    for i in range(N-P+1,indR):
        tot += M-mid+A[i]
    if indR>=N-P+1 and 0<=M*V-dif<=tot+M*(N-indR+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
N,M,V,P = map(int,input().split())
A = sorted(list(map(int,input().split())))
low = A[bisect_left(A,A[N-P])-1]
high = A[-1]+M
while high-low>1:
    mid = (low+high)//2
    indL = bisect_left(A,mid-M)
    indR = bisect_right(A,mid)
    dif = 0
    for i in range(indL,indR):
        dif += mid-A[i]
    tot = 0
    for i in range(N-P+1,indR):
        tot += M-mid+A[i]
    if 0<=M*V-dif<=tot+M*(N-indR+indL):
        high = mid
    else:
        low = mid
ind = bisect_left(A,high-M)
print(N-ind)

Submission status: Wrong Answer

Solution code:
n,m,v,p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
b = [0]*(n+1)
for i in range(n):
  b[i+1] = b[i] + a[i]

def judge(x):
  if x >= n-p: return True
  if a[x] + m < a[n-p]: return False
  safe = m*(n-2) + a[x]*(n-p-x-1) - b[n-p] + b[x+1]
  return safe >= m*(v-1)
ok = n-p
ng = -1
while ok-ng > 1:
  mid = (ok+ng)//2
  if judge(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.sort()
b = [0]*(n+1)
for i in range(n):
  b[i+1] = b[i] + a[i]

def judge(x):
  if x >= n-p: return True
  if a[x] + m < a[n-p]: return False
  safe = (n-2)*m + a[x]*(n-p) - b[n-p]
  return safe >= m*(v-1)
ok = n-p
ng = -1
while ok-ng > 1:
  mid = (ok+ng)//2
  if judge(mid):
    ok = mid
  else:
    ng = mid
print(n-ok)

Submission status: Wrong Answer

Solution code:
n, m, v, p = [int(item) for item in input().split()]
A = [int(item) for item in input().split()]
A.sort()
for i in range(len(A)):
    af = A[i+1:-p+1]
    sum = 0
    for item in af:
        sum = sum+A[i]+m-item
    if sum >= (len(af)-n+v)*m:
        print(n-i)
        break

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)

def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n,m,v,p = LI()
    a = sorted(LI())
    pi = n-p
    pv = a[pi]

    def f(i):
        t = a[i] + m
        if pv > t:
            return True
        mv = m*v-m
        for j in range(n):
            if j == i:
                continue
            aj = a[j]
            if j > pi:
                mv -= m
            elif aj <= t:
                mv -= min(m, t - aj)
            else:
                mv -= m
        return mv >= 0

    r = bs(f,0,n-1)

    return n - r


print(main())

Submission status: Wrong Answer

Solution code:
N,M,V,P = map(int, input().split())
A = list(map(int,input().split()))
A.sort(reverse=True)
count = 0
for i in range (N):
  if i <= P:
    count += 1
  elif A[i] + M < A[P-1]:
    continue
  else:
    sum = M*(P-1) + M*(N-(i+1)) 
    for j in range (P,i-1):
      sum += A[P-1]+M -A[j]
    if sum >= M*V:
      count +=1
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter

A = input()

N = len(A)
C = Counter(A)

print(1 + N * (N - 1) // 2 - sum(v * (v - 1) // 2 for v in C.values()))

Submission status: Wrong Answer

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

A.sort()
A = A[::-1]
#print("A:", A)

left = 0
right = N - 1

while left + 1 < right:
  mid = (left + right) // 2
  Amid = A[mid]
  rest = M * V - M * P
  start = P if mid <= P - 1 else P - 1
  
  flag = 0
  for i in range(start, N):
    if mid == i:
      continue
    else:
      if A[i] > Amid + M:
        flag = 1
        break
      else:
        rest -= min(M, Amid + M - A[i])
        
  if rest > 0 or flag:
    right = mid
  else:
    left = mid
#print(left)

answer = 0
Aleft = A[left]
for i in range(N):
  if A[i] >= Aleft:
    answer += 1
    
print(answer)

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 += min(a[mid]-a[i]+m,m)
            if key:
                break
            if cnt >= m*v:
                ok = mid
            else:
                ng = mid
    print(ok+1)

if __name__ == "__main__":
    main()