전구 상태 뒤집기

면접 대비

시간 제한1초메모리 제한512 MB

요약

각 전구의 밝기와 켜짐 상태가 주어질 때, 연속된 구간을 한 번 뒤집어 켜진 전구의 밝기 합을 최대로 만드는 문제입니다.

난이도: 보통10점 중 4점
유형: 배열, 동적 계획법
정답자: 아직 제출이 없습니다

문제

$N$ 개의 전구가 일렬로 놓여 있다. 각 전구는 켜져 있을 수도 있고 꺼져 있을 수도 있다. $i$ 번째 전구가 켜져 있다면 그 전구의 밝기는 $a_i$ 이다. 연우는 $N$ 개의 전구 중 연속한 전구를 한 개 이상 골라 그 전구들의 상태를 뒤집을 수 있다. 상태를 뒤집는다는 것은 켜진 전구는 끄고, 꺼진 전구는 켜는 것이다.

연우는 이렇게 연속한 전구를 골라 상태를 뒤집는 과정을 한 번 수행하려고 한다. 이때 켜져 있는 전구의 밝기 합의 최댓값은 얼마인가?

입력

첫째 줄에 전구의 개수 $N$ ( $1 \le N \le 200\ 000$ )이 주어진다.

둘째 줄에 정수 $a_1, a_2, \ldots, a_N$ ( $1 \le a_i \le 5\ 000$ )이 주어진다. $a_i$ 는 $i$ 번째 전구의 밝기이다.

셋째 줄에 정수 $b_1, b_2, \ldots, b_N$ 이 주어진다. $b_i$ 는 $i$ 번째 전구의 초기 상태를 뜻한다. $b_i = 0$ 이면 $i$ 번째 전구가 꺼져 있고, $b_i = 1$ 이면 켜져 있다.

출력

연속한 전구를 한 개 이상 골라 상태를 뒤집는 과정을 한 번 수행했을 때, 켜져 있는 전구의 밝기 합의 최댓값을 출력한다.

예제3

예제 1
입력
```
3
3 2 5
1 0 1
```
예상 출력
```
10
```
예제 2
입력
```
3
3 2 5
0 1 0
```
예상 출력
```
8
```
예제 3
입력
```
3
1 2 3
1 1 1
```
예상 출력
```
5
```