icpc.me 17392

https://www.acmicpc.net/problem/17392

숭고한 공식 풀이는 여기서 보실 수 있습니다.

그리디 문제입니다. 첫번째로 알아야 하는 사실은 기분이 음수가 아닌 날에 만남을 가질 필요가 없다는 점입니다.

따라서 하나의 약속이 $H_i+1$ 일 동안을 책임질 수 있습니다.

이제 문제는 $m-SUM(H_i+1)$ 을 n-1일동안 분배하는 문제로 바뀌게 됩니다.

$m-SUM(H_i+1)<0$ 이라면 당연히 0을 출력하면 됩니다.

우울함은 기분의 제곱이므로 큰 수가 많을수록 불리합니다. 즉, 바구니에 공을 담을 때, 공이 쏠리는 바구니가 있다면 큰 수가 많아지므로 불리합니다.

이제, 이 문제는 바구니에 공을 최대한 균등하게 담는 문제로 변했습니다.

바구니에 공을 최대한 균등하게 담는다면 $ m/(n+1)+1 $ 개를 담는 바구니가 일부 생기고 나머지는 $ m/(n+1) $ 개를 담습니다.

제곱의 합은 공식을 이용하여 구할 수 있습니다.

n,m=map(int,input().split())
l=map(int,input().split())
for x in l:
    m=m-x-1
if m<=0:
    print(0)
else:
    k=m//(n+1)
    print((k+1)*(k+1)*(m%(n+1))+(n+1)*(k*(k+1)*(2*k+1))//6)