시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB5931107918.765%

문제

인천대학교의 마스코트, 횃불이는 매우 귀엽습니다. 따라서 용준이는 횃불이 키우기라는 게임을 하기로 했습니다. 횃불이 키우기는 $N$일 동안 횃불이에게 먹이를 줘서 횃불이를 최대한 성장시키는 게임입니다.

횃불이는 정수로 표현되는 크기를 갖고, 초기 횃불이의 크기는 $s$입니다. 횃불이의 크기가 $0$이하의 정수가 될 때 횃불이는 죽고 게임이 종료됩니다. $i$일차에 먹이를 섭취하면 영양분 $A_i$만큼 크기가 증가합니다.

$i$일차의 용준이는 둘 중 하나의 행동을 선택할 수 있습니다.

  1. $i$일차에 주어진 먹이를 횃불이에게 먹입니다. 이후에 횃불이의 크기는 $A_i$만큼 증가합니다.
  2. 먹이 섭취를 포기하고 횃불이를 강화시킵니다. 이후에 횃불이의 크기는 $2$배로 증가합니다.

단, 횃불이는 최대 $k$번 강화할 수 있습니다.

$N$일이 지났을 때, 횃불이가 가장 커질 때 크기를 출력하는 프로그램을 작성해주세요. 만약 횃불이의 크기가 $10^{11}$을 넘게 될 경우, 횃불이는 메가 횃불이로 분류되고 횃불이의 크기를 나타내는 정수 대신 MEGA를 출력해야 합니다. 만약 어떤 경우에도 횃불이가 $N$일차에 생존하지 못하면 $-1$을 출력합니다.

입력

첫 번째 줄에 횃불이를 키우는 날 $N$과 횃불이를 강화할 수 있는 횟수 $k$, 그리고 횃불이의 최초 크기($0$일차)를 나타내는 정수 $s$가 공백으로 구분되어 주어집니다.($1 \leq\ N \leq\ 200\,000$, $0 \leq\ k \leq\ N$, $1 \leq\ s \leq\ 100$)

두 번째 줄에 $N$개의 정수 $A_1, A_2, ..., A_N$이 공백으로 구분되어 주어집니다. $A_i$는 $i$일차에 횃불이가 섭취하는 먹이의 영양분을 나타내는 값입니다. $(-500 \leq\ A_i \leq\ 500)$

출력

$N$일차에 횃불이의 크기를 가장 크게 했을 경우 얼마나 커질 수 있는지 출력해 주세요. 메가 횃불이로 진화할 수 있다면 MEGA를, 그렇지 않다면 횃불이의 크기를 나타내는 정수를 출력해주세요. 만약 횃불이가 $N$일차에 살아남을 수 없다면 $-1$을 출력해 주세요.

예제 입력 1

8 2 3
1 3 5 7 9 5 2 -3

예제 출력 1

132

예제 입력 2

30 30 100
500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500

예제 출력 2

MEGA

예제 입력 3

8 1 6
74 -303 -274 -113 -119 -251 354 -34

예제 출력 3

-1

노트

Python유저는 PyPy 제출을 권장합니다.

출처

University > 인천대학교 > INU 코드페스티벌 2024 J번