Problem:


Score : 700 points

Problem Statement

N problems are proposed for an upcoming contest. Problem i has an initial integer score of A_i points.

M judges are about to vote for problems they like. Each judge will choose exactly V problems, independently from the other judges,
and increase the score of each chosen problem by 1.

After all M judges cast their vote, the problems will be sorted in non-increasing order of score, and the first P problems will be chosen for the problemset.
Problems with the same score can be ordered arbitrarily, this order is decided by the chief judge.

How many problems out of the given N have a chance to be chosen for the problemset?

Constraints

2 \le N \le 10^5

1 \le M \le 10^9

1 \le V \le N - 1

1 \le P \le N - 1

0 \le A_i \le 10^9

Input

Input is given from Standard Input in the following format:

N M V P
A_1 A_2 ... A_N

Output

Print the number of problems that have a chance to be chosen for the problemset.

Sample Input 1

6 1 2 2
2 1 1 3 0 2

Sample Output 1

5

If the only judge votes for problems 2 and 5, the scores will be 2 2 1 3 1 2.
The problemset will consist of problem 4 and one of problems 1, 2, or 6.

If the only judge votes for problems 3 and 4, the scores will be 2 1 2 4 0 2.
The problemset will consist of problem 4 and one of problems 1, 3, or 6.

Thus, problems 1, 2, 3, 4, and 6 have a chance to be chosen for the problemset. On the contrary, there is no way for problem 5 to be chosen.

Sample Input 2

6 1 5 2
2 1 1 3 0 2

Sample Output 2

3

Only problems 1, 4, and 6 have a chance to be chosen.

Sample Input 3

10 4 8 5
7 2 3 6 1 6 5 4 6 5

Sample Output 3

8



Sample input:
6 1 2 2
2 1 1 3 0 2


Sample output:
5

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N,M,V,P = map(int,readline().split())
A = np.array(read().split(),np.int64)

A.sort()

def test(i):
    """
    i 番の人を勝者にできる
    """
    # はじめから上位P以内の場合
    if N - i <= P:
        return True
    # 他人に入ることを許容できる票数を計算する
    me = A[i] + M
    C = np.zeros(N,np.int64)
    C[:N-i+1] = me - A[:N-i+1]
    C = np.minimum(C,M)
    C[N-P+1:] = M # この層は負け前提
    if (C < 0).any():
        return False
    C = np.maximum(C,0)
    C[i] = 0
    x = C.sum()
    return C.sum() >= M * (V-1)

left = -1 # 勝てない
right = N-1 # 勝てる
while left + 1 < right:
    x = (left + right) // 2
    if test(x):
        right = x
    else:
        left = x

answer = N - right
print(answer)

Submission status: Wrong Answer

Solution code:
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=1)
x=max(a[p-1],a[-v]+1)
ans=0
for i in a:
  if x<=i+m:ans+=1
print(ans)

Submission status: Time Limit Exceeded

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * P
            if affords <= 0:
                result += 1
                continue
            
            affords -= sum([min(A[n] + M - A[p], M) for p in range(P, n)])
            affords -= (N-n-1) * M

            if affords <= 0:
                result += 1
                continue
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)

    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M - M * P
            if affords <= 0:
                result += 1
                continue
            
            affords -= sum([min(A[n] + M - A[p], M) for p in range(P, N)]) - min(A[n] + M - A[n], M)
            if affords <= 0:
                result += 1
                continue
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)
    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M
            affords -= M * P
            if affords <= 0:
                result += 1
                continue
            break_flag = False

            tmp = sum([min(A[n] + M -A[p], M) for p in range(P, N) if p != n])
            affords -= tmp
            if affords <= 0:
                result += 1
            """
            for p in range(P, N):
                if p == n:
                    continue
                else:
                    affords -= min(A[n] + M - A[p], M)
                    if affords<=0:
                        result += 1
                        break
            """
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    P -= 1
    A = sorted(A, reverse=True)
    result = 0
    for n in range(N):
        if n < P:
            result += 1
        elif A[n] + M < A[P]:
            continue
        else:
            affords = M * V - M
            affords -= M * P
            if affords <= 0:
                result += 1
                continue
            break_flag = False
            for p in range(P, N):
                if p == n:
                    continue
                else:
                    affords -= min(A[n] + M - A[p], M)
                    if affords<=0:
                        result += 1
                        break
    print(result)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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: Time Limit Exceeded

Solution code:
def main():

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

    ans = P
    for i in range(P, N):
        v = P * M + (N-1-i-1+1) * M
        for j in range(P-1, i):
            v += min(A[i] + M - A[j], M)
        if v >= M * V:
            ans += 1
    return ans

if __name__ == '__main__':
    print(main())

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        cnt+= ((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)>=v*m
              
    print(cnt)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys 
    input= sys.stdin.readline
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort(reverse=True)
    cnt=p
    #from bisect import bisect_left
    #print(a[5]+m)
    for i in range(p,n):
        if (a[i]+m )<a[p-1]:
            break
        # 3 2 2 1 1 0
        if ((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)>=v*m:
            cnt+=1  
    print(cnt)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys 
input= sys.stdin.readline
n,m,v,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
cnt=p
from bisect import bisect_left
#print(a[5]+m)
for i in range(p,n):
    if (a[i]+m )<a[p-1]:
        break
    # 3 2 2 1 1 0
    if ((a[i]+m)*(i-p+1)-sum(a[p-1:i])+(n-(i-p+1))*m)>=v*m:
        cnt+=1  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

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

A.sort()
r = N
l = 0
border = N - P
AP = A[border]

def solve(ind):
	if A[ind] + M < AP:
		return 0
	if ind >= V - P:
		return 1

	score_border = A[ind] + M
	tmp = 0
	for i in range(N):
		if i <= ind:
			tmp += M
		elif ind < i <= border:
			tmp += min(M, score_border - A[i])
		else:
			tmp += M
	if tmp >= M * V:
		return 1
	else:
		return 0

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

if solve(l):
	print(N - l)
else:
	print(N - r)

Submission status: Time Limit Exceeded

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

A.sort()
ans=P
for i in range(N-P):
    Ax = A[-P]  #上位Pの中の最下位
    mine = A[i] + M #自分に全力で投票
    if mine < Ax: continue #逆転不能
    votes = M*V
    votes -= M #自分への票
    votes -= min(P-1, V) * M #上位陣のx以外に全力で投票
    votes -= sum([min(mine - A[j], M) for j in range(N-P+1) if i!=j]) #逆転されない程度に下位陣に投票
    if votes > 0 : continue #再逆転される
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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


def is_possible(idx):
    if idx < P:
        return True
    if A[P - 1] <= A[idx]:
        return True
    if A[idx] + M < A[P - 1]:
        return False
    t = P * M
    for i in range(P - 1, idx):
        t += A[idx] + M - A[i]
    for i in range(idx + 1, N):
        t += M
    if t < M * V:
        return False
    return True


left, right = 0, N
while left + 1 < right:
    middle = (left + right) // 2
    if is_possible(middle):
        assert all(is_possible(i) for i in range(middle))
        left = middle
    else:
        assert all(not is_possible(i) for i in range(middle + 1, right))
        right = middle
print(right)

Submission status: Time Limit Exceeded

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-1
if v <= p:
    for i in range(p, n):
        if a[i]+m >= tmp:
            ans += 1
    print(ans)
    exit()
while l<r:
    mid = (l+r)//2
    if mid<=p:
        l = mid
        continue
    if a[mid]+m<tmp:
        r = mid-1
    else:
        thresh = a[mid]+m 
        amari = (v-p)*m
        for i in range(p-1,n):
            if i==mid:
                continue
            amari-=min(m,thresh-a[i])
        if amari<=0:
            l = mid
        else:
            r=mid-1
print(r+1)

Submission status: Time Limit Exceeded

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+m >= a[n-p]]))
else:
  s = p-1
  for i in range(n-p+1):
    if a[i]+m >= a[n-p] and (a[i]+m)*(n-p-i) - sum(a[(i+1):(n-p+1)]) >= (v-p-i)*m:
      s += 1
  print(s)

Submission status: Time Limit Exceeded

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

    ret = 0
    for i in range(n):
        if A[i]+m < A[n-p]:
            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:
            ret = n-i
            break

    return str(ret)


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

Submission status: Time Limit Exceeded

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

    ret = 0
    for i in range(n):
        if A[i]+m < A[n-p]:
            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:
                break

        if m*v <= pts:
            ret += 1

    return str(ret)


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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from bisect import bisect_left, bisect_right


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

    ret = 0
    for i in range(n):
        pts = 0
        for j in range(n):
            if j <= i or n-p < j:
                pts += m
            else:
                pts += A[i]+m-A[j]

        if m*v <= pts:
            ret += 1

    return str(ret)


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

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

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    D = deque([d for d in D if d > 0])
    cnt = 0

    while D:
        cnt += 1
        E = []
        for _ in range(min(W, len(D))):
            E.append(D.pop())
        for e in E:
            e -= 1
            if e > 0:
                D.append(e)

    return cnt <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)

Submission status: Time Limit Exceeded

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

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
           
right = P-1
left = N

while left - right !=1:
    
    i = (left+right)//2
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<0:
        if A[P-1]<=target:
            right = i
    else:
        if target<A[P-1]:
            left = i
        else:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
            if target*len_Q-Q_sum>=b*M:
                right = i
            else:
                left =i


print(right+1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush


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


def isPossible(i):
    i = A.index(A[i])
    if i < P:
        return True
    numVotes = V
    score = A[i] + M
    numVotes -= 1
    if A[P - 1] > score:
        return False
    numVotes -= P - 1
    numVotes -= N - i - 1
    if numVotes:
        heap = A[P - 1 : i][::-1]
        for j in range(M):
            temp = []
            for k in range(numVotes):
                temp.append(heappop(heap))
            for x in temp:
                heappush(heap, x + 1)
        return max(heap) <= score
    return True


if not isPossible(0):
    print(0)
elif isPossible(N - 1):
    print(N)
else:
    lo = 0
    hi = N - 1
    assert isPossible(lo)
    assert not isPossible(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if isPossible(mid):
            lo = mid
        else:
            hi = mid
    assert isPossible(lo)
    assert not isPossible(lo + 1)
    print(lo + 1)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heapify, heappop, heappush


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


def isPossible(i):
    a = list(A)
    i = a.index(a[i])
    if i < P:
        return True
    numVotes = V
    a[i] += M
    score = a[i]
    numVotes -= 1
    if a[P - 1] > score:
        return False
    for j in range(N):
        if numVotes:
            if j < P - 1 or j > i:
                a[j] += M
                numVotes -= 1
        else:
            break
    if numVotes:
        heap = a[P - 1 : i]
        heapify(heap)
        for j in range(M):
            temp = []
            for k in range(numVotes):
                temp.append(heappop(heap))
            for x in temp:
                heappush(heap, x + 1)
        return max(heap) <= score
    return True


if not isPossible(0):
    print(0)
elif isPossible(N - 1):
    print(N)
else:
    lo = 0
    hi = N - 1
    assert isPossible(lo)
    assert not isPossible(hi)
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if isPossible(mid):
            lo = mid
        else:
            hi = mid
    assert isPossible(lo)
    assert not isPossible(lo + 1)
    print(lo + 1)

Submission status: Time Limit Exceeded

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

l.sort()
count = 0
for i in range(n-p):
    c = l[i] + m
    sum = m*v-m
    rank = 0
    for j in range(n):
        if c-l[j] < 0:
            break
        elif c-l[j] in range(m):
            sum -= c-l[j]
            rank += 1
        else:
            sum -= m
            rank += 1
    if n-p <= rank-1 < n:
        a = rank-1-n+p
        if a*m < sum:
            count += 1
    else:
        count += 1

print(n-count)

Submission status: Time Limit Exceeded

Solution code:
n, m, v, p = map(int, input().split())
# n:問題数 m:人数 v:投じる標数 p:選ばれるもの
prob_set = list(map(int, input().split()))
prob_set.sort(reverse=True)
ruiseki_prob = [0 for i in range(n)]
ruiseki_prob[0] = prob_set[0]
high = n - 1
low = 0
mid = (high + low) // 2
# 下げるときはhigh = mid-1
# 上げるときはlow = mid
for i in range(1, n):
    ruiseki_prob[i] = ruiseki_prob[i - 1] + prob_set[i]

# print(prob_set)
# print(ruiseki_prob)

while low <= high:
    mid = (low + high) // 2
    # print(mid)
    f = True
    # まず上からp個以内であれば問答無用でOK (つまりindexがp>i)
    if mid < p:
        # print("<p")
        f = True
    else:
        # i~nには全員が票を投じると考えてよい (ここまででn-i票)
        # 次に上からp-1個に全員が票をいれてもよい(ここまでn-i + p-1)
        # それでも無理ならp ~ i-1までに残りを入れる必要がある.これがp[i] + m以下であればいいことがわかる
        if prob_set[mid] + m < prob_set[p - 1]:
            # どうあがいても無理
            # print("too short")
            f = False
        else:
            # どうにかなる
            if p - 1 + n - mid >= v:
                # print("OK for voting")
                f = True
            else:
                # mid
                amari_hyou = m * (v - (p - 1) - (n - mid))
                if ruiseki_prob[mid - 1] - ruiseki_prob[p - 2] + amari_hyou <= (prob_set[mid] + m) * (
                        (mid - 1) - (p - 2)):
                    # print("OK for super-voting")
                    f = True
                else:
                    # print("cannot EVEN super-voting")
                    f = False
    if f:
        low = mid + 1
    else:
        high = mid


print(low)

# 昇順に並んでいるとき,a_i が選ばれる → i > jなるa_jも選ばれる
# 二分探索することで間に合いそう
# あるiについて評価するとき,以下の観点に注意する

Submission status: Time Limit Exceeded

Solution code:
from inspect import currentframe

def chkprint(*args):
    names = {id(v):k for k,v in currentframe().f_back.f_locals.items()}
    print(', '.join(names.get(id(arg),'???')+' = '+repr(arg) for arg in args))

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    dic_A = {k:v for (k, v) in enumerate(A)}
    sorted_dic_A = sorted(dic_A.items(), key=lambda x: x[1], reverse=True)
    # chkprint(sorted_dic_A)

    B = sorted_dic_A[:P]
    P_min_val = min(B, key=lambda  x: x[1])[1]
    # chkprint(B)
    C = sorted_dic_A[P:]
    # chkprint(C)

    ans = set()

    num_vote = M * V
    # chkprint(num_vote)
    for i, v in C:
        if P_min_val > v + M:
            break
        margin = num_vote
        margin -= M * (P-1)
        margin_list = [v+M-w for (j,w) in C if j!=i]
        mod_margin_list = list(map(lambda x: x if x < M else M, margin_list))
        # chkprint(margin_list)
        # chkprint(mod_margin_list)
        margin -= M
        margin -= sum(mod_margin_list)
        # chkprint(margin)
        if margin <= 0:
            ans.add(i)

    for i, _ in B:
        ans.add(i)

    print(len(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

#A = [[int(i),x]for x,i in enumerate(input().split())]

target = P

con = 0

for i in range(N):
  x = A[i]
  x = x + M
  
  #xより小さい値の個数
  y = bisect.bisect_left(A,x)
  #xの個数
  c = A.count(x)

  #振り分け範囲より、xの上限を下回る数が多い場合
  ##…xがAのなかでP番目に入れればカウントする
  if y > V - 1:
    bigger = N - y - c
    if target > bigger:
      con += 1
  #そうでなければ
  ##xの上限数を下回るYの数y個分振り分けた後
  ##xの上限数を同等または上回る値の個数zが、
  ##入っているべき順位より小さければカウントする
  else:
    z = N - y
    if V - y - 1 < z and target - 1 > z:
      con += 1

print(con)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, V, P = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort(reverse=True)
    not_ans = 0
    for i in range(P, N):
        if A[i] + M < A[P-1]:
            not_ans += 1
            continue
        votable = M + (P-1) * M + (N - i - 1)*M
        for j in range(P-1, i):
            votable += max(0, A[i] + M - A[j])
        if votable < M*V:
            not_ans += 1

    print(N - not_ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

#A = [[int(i),x]for x,i in enumerate(input().split())]


target = P

con = 0

for i in range(N):
  x = A[i]
  x = x + M
  Y = [k for k in A if k < x]
  c = A.count(x)
  y = len(Y)
  #振り分け範囲より、xの上限を下回る数が多い場合
  ##…xがAのなかでP番目に入れればカウントする
  if y > V - 1:
    bigger = N - y - c
    if target > bigger:
      con += 1
  #そうでなければ
  ##xの上限数を下回るYの数y個分振り分けた後
  ##xの上限数を同等または上回る値の個数zが、
  ##入っているべき順位より小さければカウントする
  else:
    z = N - y
    if V - y - 1 < z and target - 1 > z:
      con += 1


print(con)

Submission status: Time Limit Exceeded

Solution code:
N, M, V, P = map(int, input().strip().split())
A = sorted(list(map(int, input().strip().split())),reverse=True)
ans=0

for i in range(N):
    thre=A[i]+M
    if thre < A[P-1]:
        continue

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    elif sum(A[P-1:i])+M*remain <= thre*(i-1-(P-1)+1):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

#A = [[int(i),x]for x,i in enumerate(input().split())]

#順位を得るため重複をなくし降順

target = P

con = 0

for i in range(N):
  x = A[i]
  x = x + M
  Y = [k for k in A if k < x]
  y = len(Y)

  #振り分け範囲より、xの上限を下回る数が多い場合
  ##…xがAのなかでP番目に入れればカウントする
  if y > V - 1:
    bigger = len([b for b in (A) if b > x])
    if target > bigger:
      con += 1
  #そうでなければ
  ##xの上限数を下回るYの数y個分振り分けた後
  ##xの上限数を同等または上回る値の個数zが、
  ##入っているべき順位より小さければカウントする
  else:
    Z = [j for j in A if j >= x]
    z = len(Z)

    if V - y - 1 < z and target - 1 > z:
      con += 1


print(con)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, V, P = map(int, input().strip().split())
A = sorted(list(map(int, input().strip().split())),reverse=True)
ans=0

for i in range(N):
    thre=A[i]+M
    if thre < A[P-1]:
        continue

    remain=V-(P-1)-(N-i)
    if remain <=0:
        ans+=1
    elif sum(A[P-1:i])+M*remain <= thre*(i-1-(P-1)+1):
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        if first==1:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
        else:
            Q_sum+=A[i-1]
            len_Q+=1
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        if first==1:
            Q_sum=sum(A[P-1:i])
            len_Q =i-(P-1)
        else:
            Q_sum+=A[i-1]
            len_Q+=1
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

for i in range(P,N):
    b = (V-((P-1)+(N-i)))
    target = A[i]+M
        
    if b<=0:
        if A[P-1]<=target:
            ans+=1
    else:
        if target<A[P-1]:
            break
        if first==1:
            Q = A[P-1:i]
            Q_sum=sum(Q)
            len_Q =len(Q)
        else:
            Q_sum+=A[i-1]
            len_Q+=1
        if target*len_Q-Q_sum>=b*M:
            ans+=1
        else:
            break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque


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

A.sort(reverse=True)


if N <= P:
    print(N)
    exit(0)


baselinen = P - 1
baseline = A[P - 1]

maxn = N - 1
for i, a in enumerate(A):
    if a + M < baseline:
        maxn = i - 1
        break


rem = (V - (P - 1) - (N - maxn - 1))

if rem <= 1:
    print(maxn + 1)
    exit(0)

defin = maxn - rem + 1


space = 0
load = 0
while True:
    pass
for n in range(baselinen + 1, maxn + 1):
    if load > space + (n - baselinen) * (A[n] + M - baseline):
        break

    space += baseline - A[n]

    if n >= defin:
        load += M

print(n)

Submission status: Time Limit Exceeded

Solution code:
import copy
import itertools
import heapq

def main():
    N, M, V, P = map(int, input().split())
    A = list(map(int, input().split()))
    ans = set()

    X = [i for i in range(N)]
    Y = [perm for perm in itertools.permutations(X, V)]
    Z = [Y for _ in range(M)]
    #print([perm for perm in itertools.product(*Z)])

    for i in [perm for perm in itertools.product(*Z)]:
        # print(i)
        A_copy = copy.copy(A)
        for j in i:
            for k in j:
                A_copy[k] += 1

        # print(A_copy)
        # psbl = sorted(A_copy, reverse=True)[:P]
        psbl_min = min(heapq.nlargest(P, A_copy))
        psbl_index_list = [i for i, a in enumerate(A_copy) if a >= psbl_min]
        # print(psbl_index_list)
        for l in psbl_index_list:
            ans.add(l)
        # print(ans)

    print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
import sys
input = sys.stdin.readline

N,M,V,P = map(int, input().split())
a = list(map(int, input().split()))
A = sorted(a)[::-1]
            
ans =P
first =1

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

Submission status: Time Limit Exceeded

Solution code:
from math import ceil,floor
import sys
input = sys.stdin.readline

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