Elearning CodePath – CTP Online Judge

Ma-nơ-canh

MANOCANH

🟢 Hard #Greedy #Dynamic Programming

### 📌 Thông tin chung

---
### 📝 Bài toán

Cửa hàng có $M$ chiếc áo ($M$ hàng) và $N$ con ma-nơ-canh ($N$ cột).
Giá trị thẩm mĩ khi mặc áo thứ $i$ vào ma-nơ-canh thứ $j$ là $V_{i,j}$.

Quy tắc:
* Mỗi chiếc áo phải được mặc vào đúng một ma-nơ-canh.
* Mỗi con ma-nơ-canh chỉ được mặc tối đa một chiếc áo.

Yêu cầu: Hãy xác định phương án mặc hết $M$ áo vào $N$ ma-nơ-canh để tổng giá trị thẩm mĩ là cao nhất.

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

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

* Dòng đầu tiên: Ghi 2 số $M$ (số áo) và $N$ (số ma-nơ-canh), cách nhau bởi dấu cách ($1 \le M, N \le 10^3$).
* $M$ dòng tiếp theo: Mỗi dòng ghi $N$ số nguyên là các giá trị thẩm mĩ $V_{i,j}$ ($1 \le V_{i,j} \le 10^4$).

Lưu ý: Do phải mặc hết $M$ áo, điều kiện cần là $M \le N$.

---
### 📤 Định dạng Đầu ra

Ghi vào file `MANOCANH.OUT` gồm:

1.  Dòng thứ nhất: Ghi tổng giá trị thẩm mĩ cao nhất của phương án mặc áo.
2.  Dòng thứ hai: Là dãy $M$ số hiệu con ma-nơ-canh được chọn cho mỗi chiếc áo (Áo 1, Áo 2, ..., Áo $M$). Các số hiệu được ghi cách nhau bởi dấu cách.

---
### ✨ Ví dụ

| Input (`MANOCANH.INP`) | Output (`MANOCANH.OUT`) | Giải thích |
| :--- | :--- | :--- |
| `1 8` `16 37 12 39 41 31 45 16` | `45` `7` | $M=1, N=8$. Áo 1 chọn giá trị lớn nhất: $V_{1,7}=45$. |
| `3 5` `7 45 5 6 2` `5 1 12 10 3` `1 5 4 4 35` | `92` `2 3 5` | Áo 1 chọn ma-nơ-canh 2 ($45$). Áo 2 chọn ma-nơ-canh 3 ($12$) (vì ma-nơ-canh 2 đã được chọn). Áo 3 chọn ma-nơ-canh 5 ($35$). Tổng: $45 + 12 + 35 = 92$. |

---
### 🏷 Ràng buộc

| Tỷ lệ điểm | Ràng buộc |
| :--- | :--- |
| $40\%$ | $1 \le M, N \le 50$; $1 \le V_{i,j} \le 10^2$ |
| $30\%$ | $50 < M, N \le 10^2$; $10^2 < V_{i,j} \le 10^3$ |
| $30\%$ | $10^2 < M, N \le 10^3$; $10^3 < V_{i,j} \le 10^4$ |

---

✅ Đã AC: 0 / 13 submissions