시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 104 | 25 | 24 | 58.537% |
명실상부한 대국 The United States of Jooddae는 오늘도 세계의 평화를 위해 힘쓴다. 이를 위해서 USJ의 수장 오주원은 오늘도 평화 유지에 기여하기로 결심했다.
여러분도 잘 알다시피, 평화로운 민주주의를 유지하기 위한 가장 중요한 조건은 다름 아닌 석유이다. 당신은 윤라크의 연속된 구역을 점령하여 기름을 얻어낼 준비를 하고 있다.
USJ의 적국 윤라크는 $1$번부터 $N$번까지 번호가 붙어 있는 원형 구역 모양으로 구획되어 있는 나라이다. 이 구역 중 몇몇 구역에는 위협 단체가 존재한다.
하지만 석유를 추출하기 위해 적국을 침공하기엔 다른 나라의 눈치가 보이므로, 당신은 적국을 침공하면서 적어도 $K$개의 위협 단체가 존재하는 구역을 점령하겠다고 선포했다.
$i$번째 구역을 점령하면, 석유를 추출해서 $A_i$만큼의 이익을 얻을 수 있다. 단, 점령에 들어가는 비용이 채산성보다 더 크면 이익은 음수가 될 수도 있다.
주원이가 최대한의 이익을 얻으려면, 땅을 어떻게 점령해야 할까?
첫 번째 줄에는 구역의 개수인 $N$과 점령한 구역에 있어야 하는 위협 단체의 최소 개수 $K$가 주어진다.
두 번째 줄에는 정수 $A_1, A_2, \dots, A_N$이 차례로 공백을 사이에 두고 주어진다.
세 번째 줄에는 $B_1, B_2, \dots, B_N$이 차례로 공백을 사이에 두고 주어진다. $B_i$가 $0$이면 $i$번째 구역에 위협 단체가 존재하지 않는 것이고, $1$이면 존재하는 것이다.
주원이가 얻을 수 있는 최대 이익을 출력하라.
5 2 5 -2 -1 -5 1 1 0 1 1 0
3
1 1 -1000000000 1
-1000000000