시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 121 21 21 22.581%

문제

호반우들 사이에서는 저번달 새로 출시한 리듬게임인 호스가 유행이다. 호스는 연속된 노트를 처리할 수록 보너스 점수를 받게 되는데 그 과정은 이러하다.

  1. 노트에는 점수가 정수로 매겨져있다. 하지만 호스는 다른 리듬게임과 다르게 점수가 음수일 수도 있다.
  2. 호반우가 연속으로 처리한 노트의 개수를 콤보라고 하자. 노트 하나를 칠 때마다 (누적 콤보)×(현재 노트) 값이 총 점수에 추가된다.
  3. 연속으로 3개의 노트를 놓치면 지금까지 얻은 점수가 0점이 되고 더 이상 점수를 얻을 수 없다.
  4. 호반우는 모든 노트를 주어진 순서대로 처리해야 한다.

호반우는 모든 노트를 처리해서 풀 콤보를 받았지만 최대 점수를 받을 수 없었다. 호반우를 위해 호반우가 얻을 수 있는 최대 점수를 계산해주는 프로그램을 만들어주자!

입력

첫째 줄에 노트 개수 N (1 ≤ N ≤ 1,000) 이 주어집니다.

둘째 줄에 공백으로 구분된 N개의 정수 a1, a2, ..., an (-10,000 ≤ ai ≤ 10,000)가 주어지는데, i번째 정수는 i번째 노트의 점수를 나타냅니다.

출력

호반우가 얻을 수 있는 최대 점수를 출력합니다.

예제 입력 1

4
3 4 -7 1

예제 출력 1

12

호반우가 모든 노트를 처리하면 3×1 + 4×2 + (-7)×3 + 1×4 = -6 점을 얻을 수 있습니다. 3번 노트를 제외한 모든 노트를 처리하면 3×1 + 4×2 + 1×1 = 12 점을 얻을 수 있습니다.

3번 노트를 놓쳤기에 4번 노트를 칠 때는 콤보가 1로 초기화 됩니다.

출처

University > 경북대학교 > 2020 Goricon I번