문제
10억 이하의 자연수로 구성된, 길이 N짜리 배열이 있다.
성윤이는 이 배열에 구멍을 총 N번 뚫을 것이다. ( 한 번 구멍을 뚫은 곳에 또 뚫을 수는 없다. )
성윤이가 구멍을 한 번 뚫을 때마다, 여러분은 구멍 사이사이의 연속 구간의 숫자의 합 중 최댓값을 출력해야 한다.
연속 구간이 하나도 없다면, 0 을 출력한다.
예를 들어, N = 5 이고, 배열이 [ 7, 10, 5, 7, 8 ] 이라고 하자.
성윤이가 구멍을 뚫는 순서는 { 3, 1, 4, 2, 5 } 라고 주어졌다고 하자.
3 번째 칸에 구멍을 뚫으면 배열은 [ 7, 10, ■, 7, 8 ] 이다. 연속 구간은 2개고, 첫 번째 연속 구간은 합은 7 + 10 = 17, 두 번째 연속 구간의 합은 7 + 8 = 15 이다. 최댓값은 17 이다.
1 번째 칸에 구멍을 뚫으면 배열은 [ ■, 10, ■, 7, 8 ] 이다. 연속 구간은 2개고, 각 연속 구간의 합은 10, 15 이다. 최댓값은 15 이다.
4 번째 칸에 구멍을 뚫으면 배열은 [ ■, 10, ■, ■, 8 ] 이다. 연속 구간은 2개고, 각 연속 구간의 합은 10, 8 이다. 최댓값은 10 이다.
2 번째 칸에 구멍을 뚫으면 배열은 [ ■, ■, ■, ■, 8 ] 이다. 이제 연속 구간은 1개 뿐이고, 최댓값은 8 이다.
5 번째 칸에 구멍을 뚫으면 배열은 [ ■, ■, ■, ■, ■ ] 이다. 연속 구간은 없고, 최댓값은 0 이다.
따라서 이 경우,
17
15
10
8
0
을 출력하면 된다.
입력
첫 줄에 배열의 길이 N 이 입력된다. ( 1 ≤ N ≤ 100,000 )
두 번째 줄에는 각 배열의 칸에 적힌 N 개의 숫자가 입력된다. ( 각각 10억 이하의 자연수 )
세 번째 줄에는 성윤이가 배열에 구멍을 뚫는 순서인 N 개의 숫자가 입력된다. ( 1 ~ N 범위의 서로 다른 자연수 )
출력
N 개의 줄에 걸쳐, 성윤이가 구멍을 뚫을 때마다, 구멍이 뚫리지 않은 연속 구간의 합의 최댓값을 출력한다. ( 마지막은 항상 0 일 것이다. )
숫자의 범위가 크기 때문에, long long 자료형을 쓰는 것을 권장한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 10점 | 연속 구간의 개수가 2개 이상이 되는 경우가 하나도 없다. ( 항상 왼쪽 끝 또는 오른쪽 끝이 뚫린다. ) |
| #2 | 40점 | 1 ≤ N ≤ 1000 |
| #3 | 50점 | 제약 조건 없음 |
예제 #1
5
7 10 5 7 8
3 1 4 2 5
17
15
10
8
0
예제 #2
10
8 2 5 12 9 3 1 8 7 10
6 9 1 4 3 10 7 8 2 5
36
36
28
10
10
9
9
9
9
0
로그인해야 코드를 작성할 수 있어요.