Elearning CodePath – CTP Online Judge

FLOWER

## Thông tin chung

| Mục      | Chi tiết     |
| -------- | ------------ |
| Tên bài  | FLOWER       |
| File vào | `FLOWER.INP` |
| File ra  | `FLOWER.OUT` |

## Đề bài

Có (n) lọ hoa được xếp trên một hàng thẳng và (k) bó hoa được đánh số từ (1) đến (k).

Cần cắm đủ (k) bó hoa vào (n) lọ hoa sao cho:

* mỗi bó hoa được cắm vào đúng một lọ hoa
* mỗi lọ hoa chứa nhiều nhất một bó hoa
* nếu bó hoa (i) và bó hoa (i+1) cùng được cắm, thì bó hoa (i) phải nằm ở một lọ đứng trước bó hoa (i+1)

Giá trị thẩm mỹ khi cắm bó hoa thứ (i) vào lọ hoa thứ (j) là (v(i,j)).

Hãy tìm tổng giá trị thẩm mỹ lớn nhất có thể đạt được.

## Dữ liệu vào

| Dòng                  | Nội dung                                                  |
| --------------------- | --------------------------------------------------------- |
| Dòng 1                | Hai số nguyên dương (n, k)  $(1 \le k \le n \le 2000) $                               |
| Dòng 2 đến dòng (k+1) | Dòng thứ (i+1) chứa (n) số nguyên, số thứ (j) là (v(i,j)) $(-10^9 \le v(i,j) \le 10^9)$ |

## Dữ liệu ra

| Nội dung                                                       |
| -------------------------------------------------------------- |
| Ghi ra một số nguyên duy nhất là tổng giá trị thẩm mỹ lớn nhất |

## Ví dụ

| FLOWER.INP                      | FLOWER.OUT |
| ------------------------------- | ---------- |
| `4 2`<br>`1 5 4 2`<br>`3 6 1 7` | `12`       |

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

Phương án tốt nhất là cắm:

* bó hoa (1) vào lọ (2), được (5)
* bó hoa (2) vào lọ (4), được (7)

Tổng giá trị thẩm mỹ là (5 + 7 = 12).

## Phân subtasks

| Subtask |                  Ràng buộc |  Điểm |
| ------- | -------------------------: | ----: |
| 1       |                 $(n \le 20)$ | (20%) |
| 2       |               $ (n \le 300)$ | (30%) |
| 3       | Không có ràng buộc gì thêm | (50%) |

✅ Đã AC: 0 / 0 submissions