시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 410 | 213 | 165 | 54.098% |
$N$개의 전구가 일렬로 세워져 있다. 전구는 켜져 있을 수도 있고 꺼져 있을 수도 있다. 만약 $i$번째 전구가 켜져 있다면 그 전구의 밝기는 $a_i$이다. 연우는 $N$개의 전구 중 연속한 전구를 한 개 이상 선택한 후에 그 전구들의 상태를 뒤집을 수 있다. 전구의 상태를 뒤집는다는 것은 켜져 있는 전구는 끄고, 꺼져 있는 전구는 켜는 것을 말한다.
연우는 이렇게 연속한 전구를 한 개 이상 선택해서 상태를 뒤집는 과정을 한 번 수행하려고 한다. 이때, 켜져 있는 전구의 밝기 합의 최댓값은 얼마일까?
첫째 줄에 전구의 개수 $N(1 \le N \le 200\ 000)$이 주어진다.
둘째 줄에 정수 $a_1, a_2, … , a_N$이 주어진다. $a_i(1 \le a_i \le 5\ 000)$는 $i$번째 전구의 밝기이다.
셋째 줄에 정수 $b_1, b_2,…, b_N$이 주어진다. $b_i$는 $i$번째 전구의 초기 상태를 의미한다. $b_i = 0$이라면 $i$번째 전구가 꺼져 있음을 의미하고, $b_i = 1$이라면 켜져 있음을 의미한다.
연속한 전구를 한 개 이상 선택해서 상태를 뒤집는 과정을 한 번 수행했을 때, 켜져 있는 전구의 밝기 합의 최댓값을 출력한다.
3 3 2 5 1 0 1
10
두 번째 전구를 선택해서 뒤집으면 밝기의 합이 $10$이 되게 만들 수 있다.
3 3 2 5 0 1 0
8
첫 번째 전구부터 세 번째 전구까지 모두 뒤집으면 밝기의 합이 $8$이 되게 만들 수 있다.
3 1 2 3 1 1 1
5
정확히 한 번 뒤집어야하므로 첫 번째 전구를 뒤집으면 밝기의 합이 $5$가 되게 만들 수 있다.
University > 충남대학교 > 2022 충남대학교 SW-IT Contest > Division 1 G번