Elearning CodePath – CTP Online Judge

Đoạn bắt buộc và điểm thưởng hai phía

COMMONSEG

🟢 Easy

## Đề bài

Cho dãy số nguyên `A` gồm `N` phần tử và số nguyên `H`.

Bạn phải chọn đúng một đoạn con liên tiếp có độ dài `H`, gọi là đoạn bắt buộc. Ngoài đoạn bắt buộc, bạn được phép chọn thêm:

- tối đa một đoạn con liên tiếp nằm hoàn toàn bên trái;
- tối đa một đoạn con liên tiếp nằm hoàn toàn bên phải.

Giá trị của phương án là:

```text
tổng đoạn bắt buộc - tổng đoạn thưởng bên trái - tổng đoạn thưởng bên phải
```

Nếu không chọn đoạn thưởng ở một phía thì tổng thưởng phía đó bằng `0`.

Hãy tìm giá trị nhỏ nhất có thể.

## Input

Dòng 1: hai số `N H`.

Dòng 2: `N` số nguyên `A_i`.

## Output

In ra giá trị nhỏ nhất.

## Ràng buộc gợi ý

- `1 ≤ H ≤ N ≤ 10^6`
- `|A_i| ≤ 10^9`

## Ví dụ

### Input

```text
6 2
3 -5 4 2 -1 6
```

### Output

```text
-13
```

## Giải thích ví dụ

Chọn đoạn bắt buộc gồm hai phần tử đầu:

```text
3, -5
```

Tổng đoạn bắt buộc là `-2`.

Ở bên phải, đoạn thưởng tốt nhất là:

```text
4, 2, -1, 6
```

Tổng thưởng là `11`. Không có đoạn bên trái.

Giá trị phương án là:

```text
-2 - 11 = -13
```

Đây là giá trị nhỏ nhất.

✅ Đã AC: 2 / 6 submissions