길이 \(N\)의 정수 수열 \(a_1, \dots, a_N\) 과 두 정수 \(L, R\) 이 주어진다. 길이가 \(L\) 이상 \(R\) 이하인 연속 부분 수열 중에서 원소들의 합이 최대인 것을 찾아, 그 합을 출력하여라.

수열에 음수가 포함될 수 있으며, 빈 부분 수열은 허용하지 않는다(길이는 최소 \(L\ge1\)). 길이 제약이 있는 최대 구간합 문제로, 누적합 위에서 슬라이딩 윈도우 최솟값(분할 정복적 구간 결합)을 이용해 \(O(N)\)~\(O(N\log N)\) 에 해결할 수 있다. \(O(N^2)\) 으로는 제한을 통과할 수 없다.

\(1 \le L \le R \le N \le 200{,}000\)

\(-10^9 \le a_i \le 10^9\)

첫째 줄에 \(N\), \(L\), \(R\) 이 주어진다.

둘째 줄에 \(N\)개의 정수 \(a_1, \dots, a_N\) 이 주어진다.

조건을 만족하는 부분 수열의 최대 합을 출력한다.

riseoj 작성

출처 Original