Elearning CodePath – CTP Online Judge

CHỌN QUÀ GIÁNG SINH

GEN045

### Thông tin chung

| Mục | Nội dung |
| --- | --- |
| **Tên Bài Toán** | **Chọn quà giáng sinh** |
| **Input** | **3** số nguyên **n**, **a**, **b** và **n** số nguyên $a_i$ |
| **Output** | Một số nguyên là giá trị dãy quà tối đa chọn được |
| **File Input** | `SLIDINGWINDOW_1.INP` |
| **File Ouput** | `SLIDINGWINDOW_1.OUT` |

### Bài toán

Sau khi thi xong GOI, M dẫn bạn gái BD đi chơi giáng sinh bù, và thực hiện lời hứa mua cho bạn gái một số món quà. Thật không may, bạn gái BD lại dẫn M vào trong cửa hàng của Dior. Trong cửa hàng có bày bán $n$ món đồ, món đồ thứ $i$ sẽ tăng thiện cảm của BD với M lên $a_i$ (Còn vì sao M lại biết thông số của từng món hàng thì phải đi hỏi HCV GOI mới biết được).

Quá sốc với giá cả “trên giời” của các món đồ tại cửa hàng này, M quyết định chỉ cho bạn gái mình chọn một dãy quà liên tiếp có độ dài không quá $B$. Nhưng với tính cách sĩ diện của mình, M muốn số lượng món đồ mà bạn gái chọn phải không ít hơn $A$.

Hãy giúp M tính xem tổng độ thiện cảm tối đa có thể tăng khi bạn gái chọn quà là bao nhiêu ?

### Định dạng đầu vào

- Dòng đầu là **3** số $n$, $A$, $B$
  - **1** $\le$ $n$ $\le$ **2000000**
  - **1** $\le$ $A$ $\le$ $B$ $\le$ $n$
- Dòng tiếp theo gồm **n** số nguyên $a_i$ (**-1000000000** $\le$ $a_i$ $\le$ **1000000000**)

### Định dạng đầu ra

- In ra trên một dòng duy nhất là độ thích lớn nhất của bạn gái Tèo khi cô ấy chọn một dãy quà liên tiếp không ngắn hơn $A$ và không dài hơn $B$.

### Ví dụ (Sample Test)

| Input (`SLIDINGWINDOW_1.INP`) | Output (`SLIDINGWINDOW_1.OUT`) |
| --- | --- |
| `8 1 2` <br/>`-1 3 -2 5 3 -5 2 2` | `8` |

✅ Đã AC: 8 / 15 submissions