붉은 구간 정확히 고르기
다이아몬드 I의견: 0
길이 \(N\)의 정수 수열 \(a_1, \dots, a_N\)이 있다. 각 위치는 빨강 또는 파랑으로 칠해져 있다.
이 수열에서 서로 겹치지 않는 비어 있지 않은 연속 구간을 정확히 \(K\)개 고른다. 구간의 값은 그 구간에 속한 원소들의 합이다.
어떤 구간이 빨강 구간이라는 것은 그 구간의 가장 왼쪽 원소의 위치가 빨강인 경우를 말한다. 고른 \(K\)개의 구간 중 빨강 구간이 정확히 \(L\)개여야 한다.
이 조건을 만족하도록 고를 때, 고른 구간들의 값의 총합의 최댓값을 구하라. 조건을 만족하도록 고르는 것이 불가능하면 IMPOSSIBLE을 출력한다.
\(1 \le N \le 12{,}000\)
\(0 \le L \le K \le N\)
\(-10^9 \le a_i \le 10^9\)
첫 줄에 세 정수 \(N\), \(K\), \(L\)이 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\)이 주어진다.
셋째 줄에 길이 \(N\)의 문자열이 주어지며, \(i\)번째 문자가 1이면 위치 \(i\)가 빨강, 0이면 파랑이다.
조건을 만족하는 최대 총합을 한 줄에 출력한다. 불가능하면 IMPOSSIBLE을 출력한다.
6 2 1
3 -1 4 2 -5 6
101001
11위치 색은 R B R B B R, 수열은 [3,-1,4,2,-5,6]. 구간 2개를 고르되 그 중 시작 위치가 빨강인 구간(빨강 구간)이 정확히 1개여야 한다. 예를 들어 빨강 구간 [3,4]=4+2=6(시작 위치 3=R)와 파랑 구간으로 시작 위치가 파랑인 구간을 함께 골라 최대 총합 11을 얻을 수 있다. 정답은 11.
3 2 1
5 5 5
000
IMPOSSIBLE모든 위치가 파랑이라 빨강 구간을 1개도 만들 수 없다. 빨강 구간 1개가 필요하므로 불가능.
riseoj 작성
출처 Original
평가 및 의견
붉은 구간 정확히 고르기
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
붉은 구간 정확히 고르기