Elearning CodePath – CTP Online Judge

ENERGY

### Thông tin chung

### Đề bài

Phi hành gia Ti đang thực hiện nhiệm vụ khám phá vũ trụ thì phi thuyền gặp sự cố cạn kiệt năng lượng. May mắn thay, Ti thu thập được một dãy gồm $N$ tinh thể năng lượng xếp thành một hàng dọc, được đánh số thứ tự từ $1$ đến $N$.

Ti cần sử dụng toàn bộ số tinh thể này để nạp đầy cho $K$ lõi động cơ của phi thuyền.

Quy trình nạp năng lượng phải tuân thủ những điều kiện sau:

Mỗi lõi động cơ phải được nạp bằng một dãy các tinh thể liên tiếp nhau.

Toàn bộ $N$ tinh thể đều phải được phân bổ hết vào $K$ lõi động cơ.

Để tránh quá tải, mỗi lõi động cơ không được chứa nhiều hơn $M$ tinh thể.

Mỗi tinh thể mang một mức điện tích nhất định, có thể là điện tích âm hoặc dương.

Công suất hoạt động của một lõi động cơ được tính bằng giá trị tuyệt đối của tổng điện tích các tinh thể bên trong lõi đó.

Tổng công suất cung cấp cho phi thuyền bằng tổng công suất của tất cả $K$ lõi động cơ.

Yêu cầu: Bạn có trong tay danh sách mức điện tích của các tinh thể, hãy giúp phi hành gia Ti tính toán cách chia tinh thể sao cho tổng công suất cung cấp cho phi thuyền là lớn nhất để có thể khởi hành về Trái Đất an toàn.

### Dữ liệu vào

Dữ liệu vào từ file ENERGY.INP:

| Dòng | Nội dung                                   |
| :--- | :----------------------------------------- |
| 1    | Chứa ba số nguyên $N, K, M$                |
| 2    | Chứa $N$ số nguyên $A_1, A_2, \ldots, A_N$ |

Điều kiện:

$$1 \le N \le 3000$$

$$1 \le K, M \le N$$

$$0 \le |A_i| \le 10^7,\ 1 \le i \le N$$

Dữ liệu bảo đảm tồn tại ít nhất một cách chia hợp lệ.

### Dữ liệu ra

Ghi ra file ENERGY.OUT một số nguyên duy nhất là tổng công suất lớn nhất có thể đạt được.

### Ví dụ

| ENERGY.INP | ENERGY.OUT | Giải thích | | | | |
| :---------------------------- | :--------- | :------------------------------------------------------------------------------------------------ | --------------- | -------------------------------------------- | --- | -------------------------------- |
| `5 2 4` `-7 -7 17 3 -20` | `26` | Cách chia tinh thể để tạo ra công suất lớn nhất: Lõi 1: `(-7, -7, 17, 3)`, có công suất là ` | -7 - 7 + 17 + 3 | = 6`. Lõi 2: `(-20)`, có công suất là ` | -20 | = 20`. Tổng: `6 + 20 = 26`. |
| `3 2 2` `-6 -15 13` | `34` | Chia làm 2 lõi: `(-6, -15)` và `(13)`. Công suất là ` | -6 - 15 | + | 13 | = 34`. |

### Subtask

| Subtask | Ràng buộc                                 | Điểm  |
| :------ | :---------------------------------------- | :---- |
| 1       | $K = 2$                                   | $10%$ |
| 2       | $N \le 20$                                | $10%$ |
| 3       | $N \le 1000,\ M \le 50,\ K \le 200$       | $20%$ |
| 4       | $N \le 3000,\ K \le 500$ hoặc $M \le 500$ | $30%$ |
| 5       | Không có ràng buộc gì thêm                | $30%$ |

✅ Đã AC: 0 / 0 submissions