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: Time Limit Exceeded

Solution code:
import collections
x = [int(i) for i in input().split()]
a = sorted([int(i) for i in input().split()],reverse=True)
n, m, v, p = x[0], x[1], x[2], x[3]
a_ = collections.Counter(a)
ans = 0
i = 0
while ans < p:
    ans += a_[a[i]]
    i = ans
l = a[:ans]
r = a[ans:]
l_r = l[-1]
l_r_cnt = a_[l_r]
if v <= ans - l_r_cnt + 1:
    for i in r:
        if l_r <= m + i:
            ans += 1
else:
    res = v - (ans - l_r_cnt + 1)
    cnt = l[-l_r_cnt:]
    for i in range(len(r)):
        can = m + r[i]
        if l_r <= can:
            if res <= len(r) - (i + 1):
                ans += 1
            else:
                res2 = res - (len(r) - (i + 1))
                if (sum(cnt) + res2 * m) / len(cnt) <= r[i] + m:
                    ans += 1
        cnt.append(r[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy
N,M,V,P=map(int,input().split())
S=list(map(int,input().split()))
score=sorted(S)
for j in range(P-1):
    score.remove(max(score))
t=0
def sorting(a):
  for i in range(M):
      
    for j in range(V-P):
      a[j]+=1
    a=sorted(a)
  return(a)

for i in range(N-P+1):
  score1=copy.deepcopy(score)
  del score1[i]
  if(score[i]+M>=max(sorting(score1))):
      t+=1
print(t+P-1)

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
n_rank = 0
b_rank = 0

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

Submission status: Time Limit Exceeded

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

l.sort()


right = n
left = -1
while right-left>1:
    mid = (right-left)//2
    l1 = copy.deepcopy(l)
    if mid >= m:
        l1[mid] += m
    else:
        index = bisect.bisect_left(l1, l1[mid]+m+1,mid)
  
        k = mid+n+1-index
        v1 = v-k
        if v1 > 0:
            l2 = l1[mid+1:index]
           
            for i in range(m):
                l2.sort()
                for i in range(v1):
                    l2[i] +=1
            l2.sort()
            for i in range(mid+1,index):
                l1[i] = l2[i-mid-1]
        l1[mid] += m

    if l1[mid] >= l1[-p]:
        
        right = mid
     
    else:
        left = mid
       


print(n-left)

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
memo = {}
sum_memo = {}
su = 0
b = 0
n_rank = 0
b_rank = 0

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

Submission status: Time Limit Exceeded

Solution code:
n, m, v, p = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)
limit = a[p - 1]
snum = a.index(limit)
alr = snum + a.count(limit)
restv = v - snum
cnt = 0
for i in range(n):
    if a[i] >= limit:
        cnt += 1
        continue
    if a[i] + m >= limit:
        garbage = n - a.index(a[i])
        restp = a[snum:a.index(a[i])]
        if (sum(restp) + (restv - garbage) * m) / len(restp) <= a[i] + m:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a.sort(reverse=True)
a = np.array(a)

def isok(i):

    if i <= (p-1):
        return True

    points = a.copy()

    points[i] += m
    points[:(p-1)] += m

    adding_point = m*v-m*p

    if points[i] < points[p-1]:
        return False

    j = n-1
    # okflag = True
    while adding_point > 0:

        if j <= p-2:
            return False

        if i == j:
            j -= 1
            continue
        adding_point -= min(m, points[i]- points[j])

        j -= 1

    return True

if isok(n-1):
    print(n)
    exit()

ok = p-1
ng = n-1

while ng - ok > 1:
    mid = (ok+ng)//2

    if isok(mid):
        ok = mid
    else:
        ng = mid
print(ok+1)

Submission status: Time Limit Exceeded

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


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

    A.sort()
    # print(*A, sep=" ")

    if N == 2:
        if A[1] <= A[0]+M:
            print(2)
        else:
            print(1)
        return

    # あるスコアYの問題は最初のP問に入れますか？
    # 二分探索で探す
    left = -1
    right = N-1
    while right - left > 1:
        mid = (right + left)//2
        # print("二分({}, {}) => {}, {}".format(left, right, mid, A[mid]))

        # mid番目以外の問題
        B = [a for i, a in enumerate(A) if i != mid]
        # 上位P-1個は除く
        B.sort()
        C = B[:-(P-1)]
        if len(C) == 0:
            while True:
                1+1

        # print(C)
        # M人がCの各問題からV-P個を選んで加点する。
        # このとき、最大のスコアとしてありうる値の最小値を探す。
        inner_left = C[-1]-1
        inner_right = 3*(10**9)
        # inner_right = 1
        while inner_right - inner_left > 1:
            inner_mid = (inner_right + inner_left)//2
            # print("\t({}, {}) => {}".format(inner_left, inner_right, inner_mid))
            # print(C)

            count = sum([c < inner_mid for c in C])
            if count < V-P:
                # print("A")
                inner_flag = False
            elif inner_mid < min(C):
                inner_flag = False
                # print("C")
            else:
                # print("B")
                # print("inner_mid: ", inner_mid)
                # print(C)
                tot = 0
                for c in C:
                    if inner_mid <= c:
                        break
                    tot += min(inner_mid-c, M)  # V-P回まで加点できる
                # print("tot: ", tot)
                if M*(V-P) <= tot:
                    inner_flag = True
                else:
                    inner_flag = False

            if inner_flag:
                inner_right = inner_mid
            else:
                inner_left = inner_mid
        # print("最大値の最小値inner_right: ", inner_right)
        # print(A[mid], M, A[mid]+M)
        if inner_right <= A[mid]+M:
            right = mid
        else:
            left = mid
    # print("答え: ", right, A[right])

    Y = A[right]

    # Yがわかったときの答え
    print(sum([a >= Y for a in A]))

    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: Time Limit Exceeded

Solution code:
import copy
N,M,V,P=map(int,input().split())
S=list(map(int,input().split()))
score=sorted(S)
t=0
def sorting(a):
  for i in range(M):
    for j in range(V-P):
      a[j]+=1
    a=sorted(a)

  return(a)

for i in range(N):
  score1=copy.deepcopy(score)
  del score1[i]
  for j in range(P-1):
    score1.remove(max(score1))
  if(score[i]+M>=max(sorting(score1))):
      t+=1
print(t)

Submission status: Time Limit Exceeded

Solution code:
n, m, v, p = map(int, input().split())
a = sorted([int(i) for i in input().split()], reverse=True)
limit = a[p - 1]
snum = a.index(limit)
alr = snum + a.count(limit)
restv = v - snum
cnt = 0
for i in range(n):
    if a[i] >= limit:
        cnt += 1
        continue
    if a[i] + m >= limit:
        garbage = n - a.index(a[i])
        restp = a[snum:a.index(a[i])]
        for j in range(m):
            restp.sort()
            for k in range(restv - garbage):
                restp[k] += 1
        if max(restp) <= a[i] + m:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, M, V, P = map(int, input().split())
A_list = list(map(int, input().split()))

A_list.sort(reverse = True)
# print(A_list)
ans = P
border = A_list[P - 1]

if P < N:
    before_A = border
    for i in range(P, N):
        if before_A == A_list[i]:
            ans += 1
#             print(1, i, A_list[i])
        elif border <= (A_list[i] + M):
            over_V = V - (P + N - (i + 1))
            if over_V > 0:
                sum_over = sum(A_list[P - 1:i]) + over_V * M
                round_up_sum_over = -(-sum_over // (i + 1 - P))
                if A_list[i] + M >= round_up_sum_over:
                    ans += 1
#                     print(2, i, A_list[i], round_up_sum_over, over_V, sum_over)
                else:
#                     print("NG", i, A_list[i], round_up_sum_over, over_V)
                    break
            else:
                ans += 1
#                 print(3, i, A_list[i])
            before_A = A_list[i]
        else:
            break
print(ans)

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
memo = {}
sum_memo = {}
su = 0

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

Submission status: Time Limit Exceeded

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

t = P
border = M*V - M*P + M
for i in range(N-P):
    c = 0
    reach = A_list[t] + M
    if reach < A_list[P-1]:
        break
    for j in range(P-1,N):
        c += min(reach - A_list[j],M)
        if c >= border:
            break
    if c < border:
        break
    t += 1
print(t)

Submission status: Time Limit Exceeded

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

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

while True:
    mv = M * V
    for i in range(len(b)):
        t = min(p - b[i], M)
        mv -= t
    if mv > 0:
        p += (mv + len(b) - 1) // len(b)
    else:
        break

print(len([i for i in A if i + M >= p]))

Submission status: Time Limit Exceeded

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

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

while True:
    mv = M * V
    for i in range(len(b)):
        t = min(p - b[i], M)
        mv -= t
    if mv > 0:
        p += 1
    else:
        break

print(len([i for i in A if i + M >= p]))

Submission status: Time Limit Exceeded

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
currentMax = As[P-1]
output = P
for i in range(len(As)):
    things = []
    if i >= P:
        if (As[i]+M >= currentMax):
            if (V <= ((len(As)-i) + (P - 1))):
                output = output + 1
            else:
                thisMax = As[i] + M
                for j in range(i-P+1):
                    things.append(As[j+P-1])
                remaining = M*(V-(N-len(things)))
                total = 0
                for z in things:
                    total = total + thisMax - z
                if total >= remaining:
                    output = output + 1
print(output)

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)))
cnt = 0
memo = {}
sum_memo = {}
for i in A:
    if i in memo.keys():
        rank = memo[i]
    else: 
        rank = S.index(i)
        memo[i] = rank
    
    if P > rank:
        cnt += 1
    else:
        xx = P-1 + N - rank
        if xx < V:
            if rank in sum_memo.keys():
                sum_val = sum_memo[rank]
            else:
                sum_val = sum(S[P-1:rank])
                sum_memo[rank] = sum_val
            x = max(math.ceil((sum_val+(V-xx)*M)/(rank-P+1)), S[P-1])
        else:
            x = S[P-1]
                    
        y = i + M
        if x <= y:
            cnt += 1
print(cnt)

Submission status: 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)))
cnt = 0
for i in A:
    rank = S.index(i)
    
    if P > rank:
        cnt += 1
    else:
        xx = P-1 + N - rank
        if xx < V:
            x = max(math.ceil((sum(S[P-1:rank])+(V-xx)*M)/(rank-P+1)), S[P-1])
        else:
            x = S[P-1]
                    
        y = i + M
        if x <= y:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
currentMax = As[P-1]
output = P
for i in range(len(As)):
    things = []
    if i >= P:
        if (As[i]+M >= currentMax):
            if (V <= ((len(As)-i) + (P - 1))):
                output = output + 1
            else:
                thisMax = As[i] + M
                for j in range(i-P+1):
                    things.append(As[j+P-1])
                remaining = M*(V-(N-len(things)))
                while remaining != 0:
                    increment = min(things)
                    index = things.index(min(things))
                    temp = things[index]
                    things.pop(index)
                    things.append(temp+1)
                    if max(things) > thisMax:
                        remaining = 1
                    remaining = remaining - 1
                add = True
                for l in things:
                    if l > thisMax:
                        add = False
                if add:
                    output = output + 1
            
print(output)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right as bi_r
from heapq import heapify, heappop, heappush

n, m, v, p, *a = map(int, sys.stdin.read().split())

def main():
    a.sort()
    # return a

    for i in range(n):
        l = bi_r(a, a[i]) - 1
        r = max(0, v - l - 1)
        if r >= p:
            cand = a[l+1:n-p+1]
            ma = cand[-1]
            heapify(cand)
            remain = m * (r - (p - 1))
            while True:
                x = heappop(cand)
                if x == ma:
                    heappush(cand, x)
                    break
                d = ma - x
                if remain < d:
                    remain = 0
                    break
                remain -= d
                heappush(cand, ma)

            if not remain:
                if a[i] + m >= ma:
                    return n - i
            le = len(cand)
            ma += (remain + le - 1) // le
            if a[i] + m >= ma:
                return n - i
        else:
            if a[i] + m >= a[n-p]:
                return n - i

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

Submission status: Time Limit Exceeded

Solution code:
import math
N, M, V, P = map(int, input().split())
A_ = list(map(int, input().split()))
A = sorted(A_)
temp = 0
for i in range(N):
  points = V - P - i
  if points < 0:
    points = 0
  requires = 0
  for j in range(i+1, N-P):
    requires += A[N-P] - A[j]
  kabe = N - P - i
  if kabe == 0:
    temp = i
    break
  else:
    wall = points * M - requires
    if wall < 0:
      wall = 0
    wall_2 = math.ceil(wall / kabe)
    wall_3 = A[N-P] + wall_2
    i_points = A[i] + M
    if i_points >= wall_3:
      temp = i
      break
print(N - temp)

Submission status: Time Limit Exceeded

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

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

    for i in range(P,N):
        tail = (N-i)
        
        if tail >= V:
            if A[i]+M >= A[P-1]:
                ans += 1
        else:
            over = V - tail
            if over <= (P-1):
                if A[i]+M >= A[P-1]:
                    ans += 1
            else:
                miwariate_point = (over -(P-1))*M
                base_point = miwariate_point//len(A[P-1:i])
                amari_point = miwariate_point%len(A[P-1:i])
                btw = list(map(lambda x: x+base_point, A[P-1:i]))
                for x in (1,amari_point+1):
                    btw[-x] += 1
                
                if A[i]+M >= max(btw):
                    ans +=1

    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
ui1 = input()
ui2 = input()
ui1s = ui1.split(" ")
ui2s = ui2.split(" ")
As = []
N = int(ui1s[0])
M = int(ui1s[1])
V = int(ui1s[2])
P = int(ui1s[3])
for i in range(len(ui2s)):
    As.append(int(ui2s[i]))
As.sort(reverse = True)
currentMax = As[P-1]
output = P
for i in range(len(As)):
    things = []
    if i >= P:
        if (As[i]+M >= currentMax):
            if (V <= ((len(As)-i) + (P - 1))):
                output = output + 1
            else:
                thisMax = As[i] + M
                for j in range(i-P+1):
                    things.append(As[j+P-1])
                remaining = M*(V-(N-len(things)))
                while remaining != 0:
                    increment = min(things)
                    index = things.index(min(things))
                    temp = things[index]
                    things.pop(index)
                    things.append(temp+1)
                    remaining = remaining - 1
                add = True
                for l in things:
                    if l > thisMax:
                        add = False
                if add:
                    output = output + 1
            
print(output)

Submission status: Time Limit Exceeded

Solution code:
N, M, V, P = map(int, input().split())
A = list(map(int,input().split()))
B = sorted(A,reverse=True)
X = B.index(B[P-1])
C = B[X:]
V = V-X
P = P-X
D = set(C)
D = [i for i in D if i >= max(D)-M]
Y = 0
for i in D:
    F = M*(V-(len(C)-C.index(i)))
    E = C[:C.index(i)]
    G = (i+M)*len(E)-sum(E)
    if F <= G :
        Y = Y+C.count(i)
print(X+Y)

Submission status: Time Limit Exceeded

Solution code:
import math
n,m,v,p=map(int,input().split())
lists=list(map(int,input().split()))
lists=sorted(lists)
def is_ok(N,m,v,p):
    counter=0
    howadd=0
    not_avoid=0
    judge=lists[N]+m
    for k in range(n-1,-1,-1):
        if k!=N:
            if judge<lists[k]:
                counter+=m
                howadd+=1
                not_avoid+=1
            elif judge==lists[k] and howadd<p-1:
                counter+=m
                howadd+=1
            elif judge==lists[k] and howadd==p-1:
                pass
            elif judge>lists[k] and howadd<p-1:
                howadd+=1
                counter+=m
            elif judge>lists[k] and howadd==p-1:
                counter+=min(judge-lists[k],m)    
    if not_avoid>=p:
            return False
    elif not_avoid<p:
        if counter<(m)*(v-1):
            return False
        elif counter>=(m)*(v-1):
            return True
start=0
end=n-1
for _ in range(30):
    c=(start+end)/2
    if is_ok(math.floor(c),m,v,p):
        end=c
    elif not (is_ok(math.floor(c),m,v,p)):
        start=c       
print(n-math.floor(end))

Submission status: Time Limit Exceeded

Solution code:
input = raw_input


def answer():
    n, m, v, p = map(int, input().split(" "))
    nums = sorted(map(int, input().split(" ")), reverse=True)

    num_last = nums[p-1]

    nokori_sum = sum(nums[p-1:n])

    out = p
    count = 0
    if v > p:
        for i in range(p, n):
            x = nums[i]
            if x + m < num_last:
                break

            #nokori_yoyuu = ( (x + m) * (n-p+1- 1) ) - (nokori_sum-x)
            nokori_yoyuu = 0
            for j in range(p-1, n):
                if j == i:
                    continue
                x2 = nums[j]
                cur_yoyuu = max(0, min(x+m-x2, m))
                nokori_yoyuu += cur_yoyuu
            cost = (v-p) * m
            if cost > nokori_yoyuu:
                break

            count += 1

        out += count

    else:
        for x in nums[p:]:
            if x + m < num_last:
                break
            count += 1
        out += count

    print(out)

answer()

Submission status: Time Limit Exceeded

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

aList = list(map(int, input().split()))
aList.sort(reverse=True)

pointer = p
subListSum = 0
preNum = 0
while pointer <= n:
  subListSum += aList[pointer - 1]
  if preNum == aList[pointer - 1]:
    pointer += 1
    continue
  if max(aList[p-1:pointer]) - aList[pointer - 1] > m:
    break
  if subListSum - aList[pointer - 1] * (pointer - (p - 1)) > (n - v) * m: # = なら OK
    break
  preNum = aList[pointer - 1]
  pointer += 1

print(pointer - 1)

Submission status: Time Limit Exceeded

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

t = P
for i in range(N-P):
    c = 0
    reach = A_list[t] + M
    if reach < A_list[P-1]:
        break
    for j in range(P-1,N):
        c += min(reach - A_list[j],M)
        if c >= (M*V - M*P + M):
            break
    if c < (M*V - M*P + M):
        break
    t += 1
print(t)

Submission status: Time Limit Exceeded

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

aList = list(map(int, input().split()))
aList.sort(reverse=True)

pointer = p
while pointer <= n:
  subListSum = sum(aList[p-1:pointer])
  if max(aList[p-1:pointer]) - aList[pointer - 1] > m:
    break
  if subListSum - aList[pointer - 1] * (pointer - (p - 1)) > (n - v) * m: # = なら OK
    break
  pointer += 1

print(pointer - 1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right as br
n,m,v,p=map(int,input().split())
a=sorted(list(map(int,input().split())))
l,r=n,-1
while l-r>1:
    t=(l+r)//2
    s=a[t]+m
    w=a[:]
    k=m*(v-1)
    for i in range(n):
        if i!=t:
            if i<t:
                c=min(k,m)
                k-=c
                w[i]+=c
            else:
                if w[i]>=s:
                    break
                else:
                    c=min(k,s-w[i])
                    k-=c
                    w[i]+=c
        if k==0:
            break
    if k>0:
        for j in range(n-1,-1,-1):
            if j!=t:
                g=min(k,m-w[j]+a[j])
                w[j]+=g
                k-=g
            if k==0:
                break
    w.pop(t)
    w=sorted(w)
    if n-br(w,s)<=p:
        l=t
    else:
        r=t
print(n-l)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

ok = N-1
ng = -1
mid = (ok+ng)//2
while ok - ng > 1:
    if mid >= N - P:
        ok = mid
        continue
    K = A[mid] + M
    if K < A[N - P]:
        ng = mid
        mid = (ok+ng)//2
        continue
    p = M * (V-P)
    flg = 0
    for i in range(mid):
        p -= M
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
        continue
    for i in range(mid+1, N - (P-1)):
        p -= K - A[i]
        if p <= 0:
            flg = 1
            break
    if flg:
        ok = mid
        mid = (ok+ng)//2
    else:
        ng = mid
        mid = (ok+ng)//2

print(N - ok)

Submission status: Accepted

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

def solve(ind):
    if a[ind]+m < a[-p]:
        return False
    thr = a[ind] + m
    votes=[]
    for i in range(n):
        if i<=ind or i>n-p:
            votes.append(m)
        else:
            votes.append(thr-a[i])
    sm = sum(votes)
    return sm >= m*v

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

print(n-ok)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, V, P = mapint()
As = list(mapint())
As.sort(reverse=True)

threshold = As[P-1]
l, r = P-1, N
while l+1<r:
    half = (l+r)//2
    a = As[half]+M
    if a<threshold:
        r = half
    else:
        rest_sum = 0
        for i in range(P-1, N):
            if As[i]>=a:
                continue
            if i==half:
                continue
            rest_sum += min(M, a-As[i])
        if M*V > rest_sum+P*M:
            r = half
        else:
            l = half
print(l+1)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

"""
# 問題:N問、ジャッジ:M人
# M人のジャッジがそれぞれV問を選び、問題のスコアを１ずつあげる
# M人の投票の後、大きい方からP問が選ばれる
# 問題セットに選ばれる可能性があるのは何問あるか

M人全員が投票すれば選ばれやすくなる
選ばれるとは？
可能性がないものを数えた方が早いのでは
P番目以内にあれば無条件で通過
現在のP番目 <= A[i] + M
V <= Pなら
上からP - 1番目までのどれか + A[i]を加算させることでA[i]を強くできる　
V > Pなら？
上からP - 1番目までとA[i]を強化するとして、残りのV - P個は小さいものから順に選ぶ
A[i]を抜かせないようにしたい
A[i]より大きい数字も一緒に足される場合にはP以内に入れない
"""
N, M, V, P = getNM()
A = getList()
A.sort(reverse = True)

def judge(x):
    if x < P:
        return True
    if A[P - 1] > A[x] + M:
        return False
    # P - 1番目まで + 自身以降の数字についてはM個足す
    left = (V - (P - 1) - (N - x)) * M
    # P個目からx-1まで A[x] + Mを超えない分足す
    for i in range(P - 1, x):
        left -= A[x] + M - A[i]

    return left <= 0

ok = -1
ng = N

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

Submission status: Accepted

Solution code:
n, m, v, p = map(int, input().split())
arr = list(map(int, input().split()))
arr.sort(reverse=True)
thr = arr[p - 1]

ok, ng = 0, n

while abs(ok - ng) > 1:
    mid = (ok + ng) // 2
    # midに全力投票した時のスコア
    x = arr[mid] + m
    # 残りの投票数
    rest = m * (v - 1)

    # 全力投票で届かない場合は探索を続行
    if x < thr:
        ng = mid
        continue

    # 全力投票で届く場合、残りの票を上手く処理できるか
    for i, a in enumerate(arr):
        # idxがp未満の場合は最大まで積める
        if i < p and arr[i] > thr:
            rest -= m
        elif i == mid:
            continue
        # idxがpより後ろの場合はmかx-aまで積める
        else:
            rest -= min(m, x - a)

    # 消化しきれていれば勝ち、そうでなければ負け
    if rest <= 0:
        ok = mid
    else:
        ng = mid

print(ok + 1)