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:
def main():
    n,m,v,p = map(int,input().split())
    scores = list(map(int,input().split()))

    scores.sort(reverse = True)

    #print(scores)

    ans = set()
    for i in range(p):
        ans.add(i)
    for i in range(p,n):
        if scores[i]+m >= scores[p-1]:
            if n-i-1 >= v-1:
                ans.add(i)

    for i in range(n-v+1,n):
        scores[i] += m

    arr = []
    for i in range(n):
        arr.append((scores[i],i))

    arr.sort(reverse = True)

    for i in range(p):
        ans.add(arr[i][1])

    print(len(ans))


main()

Submission status: Wrong Answer

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

import copy
A = sorted(A, reverse=False)
# print(A)
num = N
for i in range(N - P):
    target = A[i] + M
    resource = (V - 1) * M
    # print('A[i]', A[i], 'target', target, 'resource', resource)
    for j in range(N):
        if i == j:
            continue
        if j < i:
            diff = M
        else:
            diff = max(target - A[j], 0)
        if diff == 0:
            break
        else:
            resource -= diff
    #     print('j', j, 'A[j]', A[j], 'resource', resource, 'diff', diff)
    # print(target, resource)
    if resource < 0 or j == N - 1:
        # print('break', resource, j)
        break
    else:
        num -= 1

ans = num
for i in range(N - num, -1, -1):
    if A[num-1] == A[i]:
        ans += 1

print(ans)

Submission status: Wrong Answer

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


def solve(N: int, M: int, V: int, P: int, A: "List[int]"):
    A.sort(reverse = True)

    used_vote = (P-1)*M
    res = M*V-used_vote

    # res を振り分けていく
    a = A[P-1:]
    r = a[0]
    l = 0
    while r - l > 1:
        mid = (r+l)//2
        goal = mid+M
        if a[0] > goal:
            l = mid
            continue

        need= 0 
        for aa in a:
            need+=min(M,goal-aa)
        
        if need >=res: ##成功
            r = mid
        else:
            l = mid

    # l が最小の値
    for i in range(N):
        if A[i] > l:
            continue
        else:
            print(i)
            break
    return


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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


def check(x):
    if x > n - p:
        return True

    cnt = 0
    for i in range(x + 1, n - p + 1):
        if (a[x] + m) - a[i] > 0:
            cnt += min((a[x] + m) - a[i], m)

    if v - x - p > 0:
        if (cnt // (v - x - p)) >= m:
            return True
        else:
            return False
    else:
        for i in range(x + 1, n - p + 1):
            if a[x] + m < a[i]:
                return False
        return True


lb = 0  # False
ub = n - 1  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

# print(a)
# print(lb, ub)
ans = n - ub
print(ans)

Submission status: Wrong Answer

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

cnt = 0
A.sort()
S = [0]*(N+1)
for i in range(N):
    S[i+1] = S[i]+A[i]
    
if V <= P:
    for i in range(N-P):
        if A[i]+M < A[N-P]:
            cnt += 1
        else:
            break
else:
    for i in range(N-P):
        if i+P >= V:
            if A[i]+M < A[N-P]:
                cnt += 1
            else:
                break
        else:
            num = M*V-M*(i+P)#さばかないといけない数
            t = (N-P-i)*(A[i]+M)-(S[N-P+1]-S[i+1])#空いてる数
            t -= t%(V-P-i)
            if num > t:
                cnt += 1
            else:
                break
                
print(N-cnt)

Submission status: Wrong Answer

Solution code:
N, M, V, P = map(int, input().split())
A = [int(a) for a in 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)
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: Wrong Answer

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

A.sort()

K = A[-P]
R = bisect.bisect_left(A, K)
RL = bisect.bisect_right(A, K)
L = bisect.bisect_left(A, K - M)
ans = N - R
table = [0]*N
for i in range(L, R):
    table[i] = K - A[i]
table2 = [0]*N
for i in range(L, R):
    table2[i] = table2[i-1] + table[i]

X = table2[R-1]

for i in range(L, R):
    # print("i:", i, P+i, V > P+i)
    if V > P+i:
        v = V - (P+i)
        D = N-P - i
        print(A[i], v*M, -(v*M - (X - table2[i])))
        if (-((-(v*M - (X - table2[i]))) // D)) + K <= A[i]+M:
            ans += 1

    else:
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    """区間加算、一点取得クエリをそれぞれO(logN)で答える
    add: 区間[l, r)にvalを加える
    get_val: i番目の値を求める
    i, l, rは0-indexed
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def _add(self, i, val):
        while i > 0:
            self.bit[i] += val
            i -= i & -i

    def get_val(self, i):
        """i番目の値を求める"""
        i = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[l, r)にvalを加える"""
        self._add(r, val)
        self._add(l, -val)

import bisect

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

ans = 0
ok = 0
ng = 0
for i in range(n):
    if i+1 >= v:
        tmp = a[i] + m
        ind = bisect.bisect_right(a, tmp)
        if n - ind < p:
            ans += 1
    else:
        ng = -1
        ok = i

def solve(i):
        tmp = a[i] + m
        length = v - p - i
        bit = BIT(n)
        #print(i, tmp, length)
        if length <= 0:
            if a[n-p] <= tmp: 
                return True # print(i, "ok")
            else:
                return False
        # 初期化
        for j in range(i+1,n-p+1):
            bit.add(j, j+1, a[j])
        times = 0
        for j in range(i+1,n-p+1)[::-1]:
            tmp_times = tmp - bit.get_val(j)
            if tmp_times < 0:
                return False
            bit.add(j+1-length, j+1, tmp_times)
            times += tmp_times
            if j+1-length == i + 1:
                if times >= m: 
                    return True
        return False

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

Submission status: Wrong Answer

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

A.sort(reverse=True)


left = P
right = N-1
mid = (P+N-1)//2
MIN = A[P-1]
while True:
    mid = (right+left)//2
    if right-left <= 1:
        high = M+A[right]
        zan = P+N-right-2
        if zan >= V-1:
            if high >= MIN:
                ans = right
            else:
                ans = left
        else:
            yak = V-1-zan
            rlist = []
            for j in range(right-P+1):
                rlist.append(high-A[P-1+j])
            if rlist[0] < 0:
                ans = left
            else:
                plus = [0]*yak
                heapq.heapify(plus)
                for r in rlist:
                    p = heapq.heappop(plus)
                    heapq.heappush(plus,p+r)
                p = heapq.heappop(plus)
                if p >= M:
                    ans = right
                else:
                    ans = left
        break
    else:
        high = M+A[mid]
        zan = P+N-mid-2
        if zan >= V-1:
            if high >= MIN:
                left = mid
            else:
                right = mid
        else:
            yak = V-1-zan
            rlist = []
            for j in range(mid-P+1):
                rlist.append(high-A[P-1+j])
            if rlist[0] < 0:
                right = mid
            else:
                plus = [0]*yak
                heapq.heapify(plus)
                for r in rlist:
                    p = heapq.heappop(plus)
                    heapq.heappush(plus,p+r)
                p = heapq.heappop(plus)
                if p >= M:
                    left = mid
                else:
                    right = mid
                    

print(ans+1)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
nums = set()
ans = 0
border = float('inf')
index = float('inf')
for i in range(n):
    nums.add(a[i])
    if len(nums) == p:
        border = a[i]
    if len(nums) > p:
        index = i
        break
    ans += 1
if index != float('inf'):
    for i in range(index, n):
        if n - i >= v and border - a[i] <= m:
            ans += 1
print(ans)

Submission status: Wrong Answer

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 = 0
    
    ans = P
    
    for i in range(P,N):
        tail = (N-i)
        
        if tail >= V:
            target = A[P]
        else:
            over = V - tail
            if P - over >=0:
                target = A[P-over]
            else:
                continue
        if A[i]+M >= target:
            ans += 1
            
    print(ans)
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

A.sort()
B = [0]*N
B[0] = A[0]
for i in range(1,N):
    B[i] = B[i-1] + A[i]

#print(A)
#print(B)
mn = 0
mx = N-1
k = (mn+mx)//2
while not mx-mn == 1:
    c = A[k]
    c += M
    p = bisect.bisect_right(A,c)
    flag = False
    #print("k",k)
    #print("c",c)
    #print("p",p)
    ALL = V*M
    ALL -= (k+1)*M # left
    if N-P <= p:
        ALL -= (P-1)*M # right
        if ALL <= 0:
            flag = True
        else:
            #print("ALL",ALL)
            #print(N-P-k,B[N-P]-B[k])
            res = c*(N-P-k) - (B[N-P] - B[k])
            #print("res",res)
            if ALL <= res:
                flag = True
    #print("flag",flag)
    if flag:
        mx = k
    else:
        mn = k
    k = (mn+mx)//2
print(N-mx)

Submission status: Wrong Answer

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

li = []

cnt = 1
now = 0
ans = 0

border = lis[p-1]
li.append(0)
for i in range(n-1):
    if lis[i]!=lis[i+1]:
        now += cnt
        cnt = 1
    else:
        cnt += 1
    li.append(now)



for i in range(n):
    if li[i] > p:
        ans += 1
    else:
        if lis[i] + m >= border:
            num = (p-1)+(n-li[i]-1)+1
            if num >= v:
                ans += 1
        else:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,M,V,P = map(int,input().split())
cntA = Counter(list(map(int,input().split())))
keyA = sorted(cntA.keys(),reverse=True)

selected_num = 0
dif_val = 0
dif_num = 0
for key in keyA:
  if selected_num < P:
    selected_num += cntA[key]
    if selected_num>=P:
      last_val = key
      last_val_num = cntA[key]
  else:
    dif_val += (dif_num+last_val_num)*(last_val-key)
    dif_num += last_val_num
    if dif_val <= (N-V)*M:
      selected_num += cntA[key]
    last_val = key
    last_val_num = cntA[key]
    #print(last_val, last_val_num, key, M, selected_num)
print(selected_num)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import numpy as np
input = sys.stdin.readline
N, M, V, P = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
c = collections.Counter(A)
kakutei = A[-P]
kakutei_idx = A.index(kakutei)
ans = N - kakutei_idx
V -= (ans - c[kakutei])
V = max(1, V)
A = A[:kakutei_idx]
n = len(A)
if V > n:
    print(ans)
    sys.exit()
A = sorted(A, reverse=True)
if V == 1:
    for i in A:
        if i + M >= kakutei:
            ans += 1
else:
    temp = A[V - 1]
    temp_idx = A.index(temp)
    A_left = A[:temp_idx]
    for j in A_left:
        if j + M >= kakutei:
            ans += 1
    A_right = A[temp_idx:]
    c = collections.Counter(A_right)
    maxA = max(A_right)
    maxA_ = c[maxA]
    if maxA_ > 1 and maxA + M >= kakutei:
        ans += maxA_
print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        x = (l+r) >> 1
        ai = a[x]
        i = bisect.bisect_right(a,ai)
        A = ai+m
        j = bisect.bisect_right(a,A)
        if n-j >= p:
            l = x
            continue
        if v <= i:
            r = x
            continue
        res = 0
        i = bisect.bisect_left(a,ai)
        for j in range(i,v):
            res += a[j]-ai
        for j in range(v,n):
            if a[j] < A:
                res -= A-a[j]
        for j in range(min(p-1,v-i-1)):
            k = n-j-1
            if a[k] < A:
                res -= a[k]-ai
            else:
                res -= m
        if res <= 0:
            r = x
        else:
            l = x
    print(n-r)
    return

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

Submission status: Wrong Answer

Solution code:
n, m, v, p = [int(_) for _ in input().split()]
l = [int(_) for _ in input().split()]

l = sorted(l, reverse=True)

# print(l)

s = [0]


for i in range(1, n+1):
    s.append(s[-1] + l[-i])
s = sorted(s, reverse=True)

# print(s)

for i in range(p, n):
    x = (l[i] + m) * (i - p + 1) - (s[p - 1] - s[i])
    # print('i',i)
    # print('(l[i] + m)', (l[i] + m))
    # print('(i - p + 1)', (i - p + 1))
    # print('(s[p - 1] - s[i])', (s[p - 1] - s[i]))
    # print('x',x)
    y = 0
    if v >= (n - i) + (p - 1):
        y = v - (n - i) - (p - 1)

    # print('y * m', y * m)

    if x < y * m:
        ans = i
        break

    if i == n-1:
        ans = n

print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
n,m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
if v >= p:
    l, r = -1, n - p - 1
    while r - l > 1:
        flg = 0
        med = (l + r) // 2
        t = max(v - p, 0) * m
        for i in range(n - p + 1):
            if a[med] + m < a[i]:
                flg = 1
                break
        for i in range(n - p + 1):
            if i == med:
                continue
            t -= min(m, a[med] + m - a[i])
        if t > 0:
            flg = 1
        if flg:
            l = med
        else:
            r = med
    print(n - r)
else:
    print(n - bisect_left(a,a[n - p] - m))

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,v,p = LI()
    a = LI()
    a.sort()
    l = -1
    r = n-1
    while r-l > 1:
        x = (l+r) >> 1
        ai = a[x]
        i = bisect.bisect_right(a,ai)
        A = ai+m
        j = bisect.bisect_right(a,A)
        if n-j >= p:
            l = x
            continue
        if v <= i:
            r = x
            continue
        res = 0
        i = bisect.bisect_left(a,ai)
        for j in range(i,v):
            res += a[j]-ai
        for j in range(v,n):
            if a[j] < A:
                res -= A-a[j]
        for j in range(min(p-1,v-i)):
            k = n-j-1
            if a[k] < A:
                res -= a[k]-ai
            else:
                res -= m
        if res <= 0:
            r = x
        else:
            l = x
    print(n-r)
    return

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

Submission status: Wrong Answer

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

a=[-1*i for i in a]#最大値をとるため＊－１
heapq.heapify(a)
maxa=heapq.heappop(a)*-1
a=[-1*i for i in a]#最大値をとるため＊－１
heapq.heapify(a)

h=maxa-m
count=0
for i in range(n):
    ma=heapq.heappop(a)
    if ma>=h:
        break
    count+=1
    heapq.heappush(a,maxa)
print(n-count)

Submission status: Wrong Answer

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

import bisect
asort = sorted(a)
aset = list(set(a))
obj = min(asort[:n-p-1:-1])
n_under = bisect.bisect_left(asort, obj)
n_equal = bisect.bisect_right(asort, obj) - n_under
n_over = n-(n_equal+n_under)

ans = n_equal + n_over
for i in range(len(aset)):
    if aset[i] < obj:
        tmp_n_low = bisect.bisect_left(asort,aset[i])
        if (aset[i]+m >= obj) & ((v-1 - n_over - (n_equal-1) - tmp_n_low) <= 0):
            ans += asort.count(aset[i])
print(ans)

Submission status: Wrong Answer

Solution code:
#import sys
MOD = 10 ** 9 + 7
#input = sys.stdin.readline
import math

import itertools

#import bisect

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default


#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]
def main():
    n,m,v,p=map(int,input().split())
    a=list(map(int,input().split()))
    a=sorted(a,reverse=True)
    border=a[p-1]
    notac=0
#    temp=p-1
#    for i in range(p,n):
  #      if a[i]==border:
  #          temp=i
  #      else:
  #          break
#    temp+=1
#    print(a)
 #   print(border)
    if v<p:
        for i in range(p,n):
            if border-a[i]>m:
                notac=i
                break
    else:
        for i in range(p,n):
            total=sum(a[p-1:i])
            if m*(n-v)<total-(i-p+1)*a[i]:
                notac=i
                break
 #   print(ans)
    print(notac)











if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,M,V,P = map(int,input().split())
cntA = Counter(list(map(int,input().split())))
keyA = sorted(cntA.keys(),reverse=True)

selected_num = 0
dif_val = 0
dif_num = 0
for key in keyA:
  if selected_num < P:
    selected_num += cntA[key]
    if selected_num>=P:
      last_val = key
      last_val_num = cntA[key]
  else:
    if V>N-last_val_num:
      if key + M >= last_val+(M-1)//last_val_num + 1:
        selected_num += cntA[key]
    else:
      dif_val += (dif_num+last_val_num)*(last_val-key)
      dif_num += last_val_num
      if dif_val <= (N-V)*M:
        selected_num += cntA[key]
      last_val = key
      last_val_num = cntA[key]
    #print(last_val, last_val_num, key, M, selected_num)
print(selected_num)

Submission status: Wrong Answer

Solution code:
N,M,V,P=map(int,input().split())
A=list(map(int,input().split()))
B=sorted(A, reverse=True)
count=P
for i in range(P,N):
    dif=sum(B[P-1:i])
    if V<=(P-1)+(N-i) and B[P-1]<=B[i]+M:
        count+=1
    elif M*(V-((P-1)+(N-i)))+dif<=(B[i]+M)*(i-P+1):
        count+=1
    else:
      break
print(count)

Submission status: Wrong Answer

Solution code:

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

a = list(map(int,input().split()))
num = m * v
c= 0
ans = 0

while num > 0:
    a.sort()
    a[0] += 1
    num -= 1

a.sort(reverse = True)

while ans < p:
    c = a.count(a[0])
    ans = ans + c
    a.remove(a[0])

print(ans+1)

Submission status: Wrong Answer

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

a = sorted(a)[::-1]

minp = a[p-1]
result = 0
td = 0
count = 0
tpcount = 1
tptd = 0
pre = minp
for i in range(p, n):
    if pre != a[i]:
        td += tptd
        count += tpcount
        tptd = 0
        tpcount = 0
    dis = (minp + m) * count - td - min(n-v, count) * m
    diss = 0
    if count != 0:
        diss = dis // count
        if dis % count != 0:
            diss += 1
    if m * min(n-v, count) >= (minp - a[i]) * count - td and diss <= a[i] + m:
        result+=1
        tpcount+=1
        tptd+= minp - a[i]
        pre = a[i]
    else:
        break
print(result+p)

Submission status: Wrong Answer

Solution code:
n, m, v, p = [int(_) for _ in input().split()]
l = [int(_) for _ in input().split()]

l = sorted(l, reverse=True)

print(l)

s = [0]


for i in range(1, n+1):
    s.append(s[-1] + l[-i])
s = sorted(s, reverse=True)

print(s)

for i in range(p, n):
    x = (l[i] + m) * (i - p + 1) - (s[p - 1] - s[i])
    print('i',i)
    print('(l[i] + m)', (l[i] + m))
    print('(i - p + 1)', (i - p + 1))
    print('(s[p - 1] - s[i])', (s[p - 1] - s[i]))
    print('x',x)
    y = 0
    if v >= (n - i) + (p - 1):
        y = v - (n - i) - (p - 1)

    print('y * m', y * m)

    if x < y * m:
        ans = i
        break

    if i == n-1:
        ans = n

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, m, v, p = map(int, input().split())
a = list(map(int, input().split()))
a.sort(reverse=True)
def judge(i):
    thres = a[i] + m
    rem = m * v - (n - i) * m
    rank = 0
    memo = 0
    for j in range(i):
        if a[j] > thres:
            rank += 1
            rem = max(rem-m, 0)
        else:
            if rank < p-1:
                rank += 1
                rem = max(rem-m, 0)
            else:
                rem = max(rem-(thres-a[j]), 0)
        if rank > p -1:
            break
    # print(i, a[i], thres, rem)
    if rank <= p - 1 and rem == 0:
        return True
    else:
        return False
l = 0
r = n-1

while True:
    if r - l == 1:
        print(l+1)
        break
    i = (r + l) // 2
    if judge(i):
        l = i
    else:
        r = i

Submission status: Wrong Answer

Solution code:
# B
import numpy as np
N, M, V, P = map(int, input().split())
A = np.array(input().split(), dtype=int)

A = np.sort(A)[::-1]

# X(1-origin)が再録される可能性があるか
def f(X):
    # M人が, Pに票を入れず、Xに全振りして可能性がないなら終了
    if (A[P-1] > A[X-1] + M):
        # print("C1")
        return False

    # M人がV2回投票を行う
    V2 = V - (P-1) - 1 - (N-X)
    if V2 < 0: V2 = 0
    # A[P:X]の範囲にM人がV2回投票を行ったとき、Ax = A[X-1] + Mを超えたら終了(同点はOK)
    # 自明に小さいAに票を入れる
    Ax = A[X-1] + M
    RANGE = Ax - A[P:X-1]
    # 先にAxから引いておくので、負数になったら終了
    
    # RANGEの各要素はPまで吸収できる→Mとmaxをとって、合計値がM*V以下ならOK
    # print(RANGE)
    RANGE = np.minimum(RANGE, M)
    # print(RANGE)
    # print(np.sum(RANGE), M*V2)
    return np.sum(RANGE) >= M*V2

# 二分探索
lo, up = P, N

while(lo!=up):
    ta = (lo + up + 1) // 2
    # print(lo, up, ta)

    if f(ta):
        lo = ta
    else:
        up = ta - 1

print(lo)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,M,V,P = map(int,input().split())
cntA = Counter(list(map(int,input().split())))
keyA = sorted(cntA.keys(),reverse=True)

selected_num = 0
dif_val = 0
dif_num = 0
for key in keyA:
  if selected_num < P:
    selected_num += cntA[key]
    if selected_num>=P:
      last_val = key
      last_val_num = cntA[key]
  else:
    if V>N-last_val_num:
      if key + M >= last_val+(M-1)//last_val_num + 1:
        selected_num += cntA[key]
    else:
      dif_val += (last_val-key)*last_val_num + dif_num*(last_val-key)
      dif_num += last_val_num
      if dif_val <= (N-V)*M:
        selected_num += cntA[key]
      last_val = key
      last_val_num = cntA[key]
    #print(last_val, last_val_num, key, M, selected_num)
print(selected_num)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N, M, V, P = rl() #Vは選べる問題
A = rl()
A.sort(reverse=True)
INF = 10 ** 10
A = A[P-1:] + [-INF] #上位P-1問は捨てる
V -= (P-1)
N = len(A)
answer = P-1

# 残りの問題からトップに立てるかどうか二分探索
high = N-1 #不可能
low = 0 #可能
while high > low + 1:
    mid = (high+low)//2
    num = V - (N-1-mid) #INFは捨てる
    
    B = np.array(A[:mid])
    #Bの中からM人のジャッジがnum問選ぶ
    count = ((A[mid] + M) - B).sum()
    if count <  M * num:
        high = mid #不可能
    else:
        low = mid

answer += (low + 1)
print(answer)

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]
tmp = a[p-1]
ans = p
imos = [0]
fl = [0 for i in range(n+1)]
for i in a:
    imos.append(imos[-1]+i)
l = 0
if v<=p:
    for i in range(p,n):
        if a[i]+m>=tmp:
            ans+=1
    print(ans)
    exit()
else:
    i = n-1
    while i >= p:
        if a[i]+m >= tmp:
            t = v-p- (n-1-i)
            if (a[i]+m)*(i-p)-(imos[i]-imos[p])>=t*m:
                print(i+1)
                exit()
        i-=1
    print(p)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import numpy as np
input = sys.stdin.readline
N, M, V, P = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A = sorted(A)
kakutei = A[-P]
kakutei_idx = A.index(kakutei)
ans = N - kakutei_idx
V -= (ans - 1)
V = max(1, V)
A = A[:kakutei_idx]
A = sorted(A, reverse=True)
if V == 1:
    for i in A:
        if i + M >= kakutei:
            ans += 1
else:
    temp = A[V - 1]
    temp_idx = A.index(temp)
    A_left = A[:temp_idx]
    for j in A_left:
        if j + M >= kakutei:
            ans += 1
    A_right = A[temp_idx:]
    c = collections.Counter(A_right)
    maxA = max(A_right)
    maxA_ = c[maxA]
    if maxA_ > 1 and maxA + M >= kakutei:
        ans += maxA_
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, v, p = map(int, input().split())
a = list(map(int, input().split(" ")))
a.sort()
a.reverse()
ans = 0
#print(a)
if n - v < p:
    for i in range(n):
        if (i >= p-1-n+v) and (i <= p-1):
            a[i] = a[i]
        else:
            a[i] += m
    b = a.copy()
    b.sort()
    b.reverse()
    for i in range(p,n):
        if a[i] < b[p-1]:
            ans = n - i
            break

else:
    for i in range(p,n):
        if a[p-1] - a[i] > m:
            ans = n - i
            break



print(n - ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter
N,M,V,P = map(int,input().split())
cntA = Counter(list(map(int,input().split())))
keyA = sorted(cntA.keys(),reverse=True)

selected_num = 0
dif_val = 0
dif_num = 0
for key in keyA:
  if selected_num < P:
    selected_num += cntA[key]
    if selected_num>=P:
      last_val = key
      last_val_num = cntA[key]
  else:
    if V>N-last_val_num:
      if key + M >= last_val+(M-1)//last_val_num + 1:
        selected_num += cntA[key]
    else:
      dif_val += (last_val-key)*last_val_num + dif_num
      dif_num += last_val_num
      if dif_val <= (N-V)*M:
        selected_num += cntA[key]
      last_val = key
      last_val_num = cntA[key]
    #print(last_val, last_val_num, key, M, selected_num)
print(selected_num)

Submission status: Wrong Answer

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

A.sort()

K = A[-P]
R = bisect.bisect_left(A, K)
RL = bisect.bisect_right(A, K)
L = bisect.bisect_left(A, K - M)
ans = N - R
table = [0]*N
for i in range(L, R):
    table[i] = K - A[i]
table2 = [0]*N
for i in range(L, R):
    table2[i] = table2[i-1] + table[i]

X = table2[R-1]

for i in range(L, R):
    # print("i:", i, P+i, V > P+i)
    if V > P+i:
        v = V - (P+i)
        D = N-P - (A[i]+1) + 1
        # print(v*M, N-P-R + 1)
        if (-((-(v*M - (X - table2[i]))) // D)) + K <= A[i]+M:
            ans += 1

    else:
        ans += 1

print(ans)