Elearning CodePath – CTP Online Judge

Chia kiện hàng liên tiếp

TKM11_BSSHIP

## Đề bài

Có `N` kiện hàng xếp theo thứ tự từ `1` đến `N`. Kiện thứ `i` có khối lượng `Wi`.

Bạn cần chia dãy kiện hàng thành không quá `K` chuyến vận chuyển. Mỗi chuyến phải chở một đoạn liên tiếp các kiện hàng trong thứ tự ban đầu. Mỗi kiện hàng thuộc đúng một chuyến.

Sức chở cần thiết của một phương án là tổng khối lượng lớn nhất trong các chuyến.

Hãy tìm sức chở nhỏ nhất có thể.

## Dữ liệu vào

- Dòng đầu chứa hai số nguyên `N` và `K`.
- Dòng thứ hai chứa `N` số nguyên `W1, W2, ..., WN`.

## Dữ liệu ra

In ra một số nguyên duy nhất — sức chở nhỏ nhất cần có.

## Ràng buộc

```text
1 <= K <= N <= 200000
1 <= Wi <= 10^9
```

## Subtask

- Subtask 1 — 25 điểm: `N <= 20`, `Wi <= 100`.
- Subtask 2 — 35 điểm: `N <= 5000`, `Wi <= 10^6`.
- Subtask 3 — 40 điểm: Không có ràng buộc bổ sung.

## Ví dụ

### Input

```text
5 2
7 2 5 10 8
```

### Output

```text
18
```

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

Một cách chia tối ưu là:

```text
[7, 2, 5] và [10, 8]
```

Tổng hai chuyến lần lượt là `14` và `18`, nên sức chở cần là `18`.

Không thể có sức chở nhỏ hơn `18`.

✅ Đã AC: 0 / 0 submissions