| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 166 | 89 | 73 | 56.154% |
중력 발전소란 중력의 힘을 이용하여 에너지를 생산하는 발전소이다. 중력 발전소는 수직으로 배열된 $N+1$개의 공간으로 구성된다. 각 공간에는 0ドル$번부터 $N$번까지 차례대로 번호가 매겨져 있다. 이때 가장 위에 위치한 공간이 0ドル$번, 가장 아래에 위치한 공간이 $N$번이다.
중력 발전소를 가동시키면, 0ドル$번 공간에 공을 놓은 후 중력의 힘으로 공을 $N$번 공간까지 떨어뜨린다. 인접한 두 공간 사이에는 떨어지는 공을 감지할 수 있는 고리형 발전기가 있다. 구체적으로, 1ドル \leq i \leq N$에 대해 공이 $i - 1$번 공간에서 $i$번 공간으로 떨어질 경우 두 공간 사이의 고리형 발전기가 이를 감지하여 $A_i$만큼의 에너지를 생산한다.
과학자들은 중력 발전소의 생산성을 높이기 위해 반중력 장치를 개발하였다. 중력 발전소에는 총 $\displaystyle \frac{N(N + 1)}{2}$개의 반중력 장치가 존재하며, 각 장치는 0ドル \leq i < j \leq N$을 만족하는 정수 쌍 $(i, j)$에 대응된다. $(i, j)$에 대응되는 반중력 장치를 공이 $j$번 공간에 있을 때 사용하면 중력을 거슬러 공을 $i$번 공간으로 이동시킬 수 있다. 고리형 발전기는 공을 감지할 때마다 독립적으로 에너지를 생산하기 때문에 반중력 장치를 사용하여 각 고리형 발전기가 여러 번 에너지를 생산하도록 설계할 수 있다.
다만 반중력 장치는 중력 발전소를 불안정하게 만들 수 있기 때문에 사용에 몇 가지 제약이 존재한다.
발전은 반드시 공을 0ドル$번 공간에 둔 상태에서 시작하고, 공이 $N$번 공간에 존재하는 상태에서 종료되어야 한다. 이때 공이 $N$번 공간에 있는 상태에서도 반중력 장치를 사용할 수 있다.
반중력 장치를 적절히 사용해 생산할 수 있는 총 에너지의 최댓값을 구하여라.
첫째 줄에 세 정수 $N,ドル $M,ドル $K$가 공백으로 구분되어 주어진다. (1ドル \leq N \leq 100,000円$; 0ドル \displaystyle \leq M \leq \min \left( \frac{N(N + 1)}{2}, {10}^9 \right)$; 0ドル \leq K \leq {10}^9$)
둘째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. (1ドル \leq A_i \leq {10}^9$; $\sum A_i \leq {10}^9$)
생산할 수 있는 총 에너지의 최댓값을 출력한다.
7 1 5 9 7 4 3 3 8 8
49
4 3 100 1 2 3 4
10
5 5 4 7 3 7 3 7
52
첫 번째 예제의 경우 다음과 같은 방식으로 발전을 진행한다.
이때 총 42ドル - 35 + 42 = 49$만큼의 에너지를 생산하며, 이보다 더 많이 생산할 수 없다.
두 번째 예제의 경우 반중력 장치를 사용하지 않는 것이 이득이며, 단순히 공을 떨어뜨리면 1ドル + 2 + 3 + 4 = 10$만큼의 에너지를 생산할 수 있다.