시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB72464375.439%

문제

방구석 독거 코더가 된 병우를 안타까워한 친구들이 병우에게 여자친구를 소개해 주었고, 둘은 놀이공원에 놀러 가게 되었다.

놀이공원 벤치에서 꽁냥꽁냥을 하던 병우는 맞은편에 풍선 다트 게임이 있는 것을 보았다. 높은 점수를 얻어 곰 인형을 주고 싶었던 병우는 풍선 다트 게임을 하러 당당하게 걸어갔다. 하지만 놀이공원에 있는 풍선 다트 게임은 평소에 보던 풍선 다트 게임과 전혀 다른 규칙을 가진 것을 알게 되었다.

  1. 풍선 다트 게임의 풍선은 1차원 배열처럼 1자로 쭉 나열되어있다.
  2. 다트는 풍선의 개수만큼 주어진다. 병우는 다트의 신이라 던지는 모든 다트가 풍선을 정확하게 적중시켜 터트린다.
  3. 풍선 다트 게임의 점수는 (각 segment에 포함된 풍선의 점수의 합 $\times$ 각 segment의 크기)의 합으로 계산된다. segment란 연속한 부분 배열을 의미한다. 보다 자세한 설명을 하자면 segment란 구간 $[l, r]$에서 $l-1$번째 풍선과 $r + 1$번째 풍선이 존재하지 않거나 터져있으며, 구간 $[l, r]$에 풍선이 모두 존재할 때 전체 풍선 배열 $a$의 부분 풍선 배열 $a_l, a_{l + 1}, \cdots, a_{r-1}, a_r$이다. 점수계산 방식을 자세한 수식으로 나타내면 아래와 같다. $$ \sum\limits_{i=1}^{k} {(seg_{i} × size(seg_{i}))} $$
    • $ seg_i $는 $ i $번째 segment에 포함된 풍선의 점수의 합이다.
    • $ size(seg_i) $는 $ i $번째 segment가 나타내는 구간의 크기이다.
    • $ k $는 segment의 총 개수이다.
  4. 점수는 0점으로 시작하며, 다트를 던져 풍선을 터트릴 때마다 점수가 다시 계산된다. 계산된 점수 중 최대 점수가 최종 점수가 된다. 첫 다트를 던지기 전에는 점수가 계산되지 않아 0점인 점을 명심하자.

아, 꿈! 사실 여자친구와 데이트를 간 건 병우의 꿈이었다. 달콤했던 꿈을 잊지 못한 병우는 혹시나 다음에 생길 여자친구와 풍선 다트 게임을 할 것을 대비하기 위해 최종 점수를 계산해보려 한다.

설치된 풍선의 점수와 병우가 터트린 풍선의 번호가 순서대로 주어질 때 최종 점수를 계산해보자.

입력

첫 번째 줄에 풍선의 개수인 정수 $ N \left(3 ≤ N ≤ 100\,000\right) $이 주어진다.

두 번째 줄에는 각 풍선의 점수를 나타내는 $ N $개의 정수 $ B_1, B_2, \cdots, B_n \left(-100\,000 ≤ B_i ≤ 100\,000\right) $이 주어진다.

세 번째 줄에는 터트리는 풍선의 순서를 나타내는 서로 다른 $ N $개의 정수 $ P_1, P_2, \cdots, P_n \left(1 ≤ P_i ≤ N\right) $이 주어진다.

출력

최종 점수를 출력한다.

예제 입력 1

5
13 7 8 -20 21
2 4 1 3 5

예제 출력 1

42

다트를 던지기 전에는 점수가 계산되지 않아 0점이다.

첫 번째 다트를 던져서 2번 풍선을 터트렸으므로 segment가 $(13),(8,−20,21)$ 2개로 나뉘게 된다. 따라서 점수는 $ 13×1+(8+−20+21)×3=40 $점이 된다.

두 번째 다트를 던져서 4번 풍선을 터트렸으므로 segment가 $(13),(8),(21)$ 3개로 나뉘게 된다. 따라서 점수는 $ 13×1+8×1+21×1=42 $점이 된다.

이후 1, 3, 5번 풍선을 순서대로 터트리는 각각의 경우에 대해서 $42$점을 넘지 못한다.

따라서 최종 점수는 $42$점으로 마무리된다.

예제 입력 2

3
-40 -9 -19
3 1 2

예제 출력 2

0

예제 입력 3

11
6 28 15 17 23 39 -22 -30 -17 -24 28
10 11 5 2 4 6 3 7 9 1 8

예제 출력 3

559

출처

University > 부산대학교 > 2022 부산대학교 CodeRace E번