풀이 방법

N대의 컴퓨터 최고 성능 = 10^5 10^9 = 10^14이다.
완전탐색으로 한다면 무조건 시간초과
그렇다면 이분 탐색을 이용하면 된다.
원래는 힙을 이용해서 풀었는데, 힙에 요소를 삽이하면 재정렬 시간이 O(log₂n) 이다.
원소의 개수는 최대 N개여서 O(Nlog₂n)인데, 이걸 또 N번 돌기 때문에 완전 탐색과 다를게 없다.

풀이 코드

import sys

n, b = map(int, sys.stdin.readline().split())

a = list(map(int, sys.stdin.readline().split()))

a = sorted(a)

start = 1
end = 10 ** 9

while start < end:
    total = b
    mid = (start + end) // 2 + 1
    res = end

    for i in range(len(a)):
        if mid <= a[i]:
            break
        total -= (mid - a[i]) ** 2
        if total < 0:
            break
    if total > 0:
        start = mid
    elif total == 0:
        break
    else:
        end = mid - 1

print((start + end) // 2)