Informatica Online Judge

  계단 게임 [1001 / 03E9]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 49   Total Tried : 272


The Champion of this Problem (C++) : gs18081 - 0ms / 813byte
My Best Submission (C++) : N/A

[JKJeong 2014]

Background

경곽이는 계단을 오르는 게임을 좋아한다.

경곽이는 다리가 짧아서 한 번에 한 칸 또는 두 칸 만 오를 수 있다.

그리고 경곽이는 한 번 이동하는데 1초가 걸린다.

계단의 각 단에는 밟으면 올라가는 점수가 있다. 재미있는 것은 각 계단은 일반 계단 또는 특수 계단이 있다.

일반 계단은 점수가 변화가 없지만, 특수계단은 점수가 시간이 지날수록 1초에 1점씩 올라가거나, 내려간다는 점이다.

예를 들어 어떤 특수 계단의 점수가 3점이고, 이 계단이 점수가 올라가는 특수계단이라면 이 계단의 점수는 3초후에 6점이 된다. 만약 이 계단이 점수가 내려가는 계단이라면 3초 후 0점이 되어 있을 것이다.

물론 계단의 점수는 음수로 내려갈 수도 있으며, 오르거나 내리는 한계는 없다.
그리고 경곽이는 첫 번째 계단에서 출발하고, 마지막 계단에서 끝나야 한다. (즉 처음과 끝 계단은 반드시 밟는다.)

계단의 수가 주어지고, 각 계단의 기본 점수와 그 계단의 점수가 오르는지 내리는지가 주어져 있을 때, 경곽이가 계단을 오르면서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 계단의 수 N이 입력된다.
다음 줄에 각 계단의 점수 N개가 공백으로 구분되어 입력된다.
다음 줄에 각 계단이 점수가 올라가는 계단이면 1, 변동 없는 계단이면 0, 내려가는 계단이면 -1로 주어진다.

[입력값의 정의역]
3 <= N <= 5,000
-5,000 <= 각 계단의 초기 점수 <= 5,000
각 계단의 특성값 = { -1, 0, 1 }

[Sub-Task Info]
#1 : N <= 10
#2 : N <= 100
#3 : N <= 1,000
#4 : N <= 5,000

Output

얻을 수 있는 최대 점수를 출력한다.

IO Example

입력
5
1 2 3 4 5
0 0 0 0 0

출력
15

* 설명 : 모든 계단을 다 밟고 지나가면 최대 점수를 얻을 수 있다.

입력2
5
1 2 3 2 -5
1 0 -1 -1 1

출력2
2

* 설명 : 처음 3개를 연속으로 밟고 마지막 계단을 밟는다. 그럼 모두 4초간 이동한 것이되고,
처음 계단을 밟을 때, 1점(0초)
다음 계단을 밟을 때, 2점(1초) 일반 계단이므로 점수 변화 없음. 여기까지 합계 3점
그 다음 계단을 밟을 때, 1점(2초) 원래 3점인데 점수가 내려가는 계단이며, 2초가 지났으므로 1점, 합계 4점
그리고 마지막 계단을 밟으면, -2점(3초) 원래 -5점인데 점수가 오르는 계단이고 3초가 지났으므로 -2점, 합계 2점

이 방법이 가장 많은 점수를 획득하는 방법이고 그 이상으로 얻을 수 있는 방법은 없다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]