아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

전구 상태 뒤집기

면접 대비

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

요약
전구의 연속한 한 구간을 정확히 한 번 뒤집은 뒤, 켜져 있는 전구 밝기 합의 최댓값을 구한다.
난이도

보통10점 중 5점

유형
동적 계획법, 배열, 누적 합, 그리디
정답자
아직 제출이 없습니다

문제

NN개의 전구가 일렬로 세워져 있다. 전구는 켜져 있을 수도 있고 꺼져 있을 수도 있다. 만약 ii번째 전구가 켜져 있다면 그 전구의 밝기는 a_ia\_i이다. 연우는 NN개의 전구 중 연속한 전구를 한 개 이상 선택한 후에 그 전구들의 상태를 뒤집을 수 있다. 전구의 상태를 뒤집는다는 것은 켜져 있는 전구는 끄고, 꺼져 있는 전구는 켜는 것을 말한다.

연우는 이렇게 연속한 전구를 한 개 이상 선택해서 상태를 뒤집는 과정을 한 번 수행하려고 한다. 이때, 켜져 있는 전구의 밝기 합의 최댓값은 얼마일까?

입력

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

둘째 줄에 정수 a_1,a_2,…,a_Na\_1, a\_2, … , a\_N이 주어진다. a_i(1≤a_i≤5 000)a\_i(1 \le a\_i \le 5\ 000)는 ii번째 전구의 밝기이다.

셋째 줄에 정수 b_1,b_2,…,b_Nb\_1, b\_2,…, b\_N이 주어진다. b_ib\_i는 ii번째 전구의 초기 상태를 의미한다. b_i=0b\_i = 0이라면 ii번째 전구가 꺼져 있음을 의미하고, b_i=1b\_i = 1이라면 켜져 있음을 의미한다.

출력

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

예제3

  1. 예제 1

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

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

    입력
    3
    1 2 3
    1 1 1
    
    예상 출력
    5