Tổng đoạn con lớn nhất có giới hạn độ dài (Maximum Subarray Sum II)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $n$ số nguyên và hai giới hạn độ dài $a,b$.

Hãy tìm tổng lớn nhất của một đoạn con liên tiếp có độ dài nằm trong khoảng

Nếu đoạn là $[l,r]$ thì độ dài của nó bằng $r-l+1$.

Input

• Dòng đầu chứa ba số nguyên $n,a,b$.
• Dòng thứ hai chứa $n$ số nguyên $x_1,x_2,\ldots,x_n$.

Output

In tổng lớn nhất của một đoạn con có độ dài từ $a$ đến $b$, tính cả hai giới hạn.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le2\cdot10^5$

• $1\le a\le b\le n$

• $-10^9\le x_i\le10^9$

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: $a=b$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

8 1 2
-1 3 -2 5 3 -5 2 2

Output

8

Giải thích

Trong ví dụ, độ dài hợp lệ là $1$ hoặc $2$.

Dãy là

Đoạn gồm hai phần tử tại vị trí $4$ và $5$ có tổng

Không có đoạn độ dài $1$ hoặc $2$ nào có tổng lớn hơn $8$, nên đáp án là $8$.