Elearning CodePath – CTP Online Judge

Lịch Vắt Sữa

SMILK

🟢 Easy #Greedy #Scheduling

### 📌 Thông tin chung

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

Nông dân John (FJ) có $N$ con bò cần được vắt sữa.
* Mỗi con bò cần **1 đơn vị thời gian** để vắt sữa.
* Bò $i$ có thể cho $g_i$ gallon sữa.
* Bò $i$ chỉ cho sữa nếu nó được vắt sữa **trước thời điểm $d_i$** (thời điểm kết thúc vắt sữa).
* Thời điểm bắt đầu vắt sữa là $t=0$.

Yêu cầu: Lên lịch vắt sữa một cách hợp lý để tính **lượng sữa tối đa** mà FJ có thể thu được.

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

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

* Dòng 1: Ghi số nguyên dương $N$.
* $N$ dòng tiếp theo: Dòng thứ $i$ ghi hai số nguyên $g_i$ và $d_i$, lần lượt là lượng sữa (gallon) và thời hạn vắt sữa của con bò thứ $i$.

Giới hạn:
* $1 \le N \le 10^4$.
* $1 \le g_i \le 1000$.
* $1 \le d_i \le 10^4$.

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

Ghi ra file `SMILK.OUT` một số nguyên duy nhất là số lượng sữa tối đa mà FJ có thể thu được.

---
### ✨ Ví dụ

| Input (`SMILK.INP`) | Output (`SMILK.OUT`) | Giải thích: |
| :--- | :--- | :--- |
| `4` `10 3` `7 5` `8 1` `2 1` | `25` | Vắt sữa các con bò theo lịch (chỉ số): **3 - 1 - 2** (Con 4 không tham gia vắt sữa) |

Giải thích chi tiết ví dụ:
* Bò 1: $g=10, d=3$.
* Bò 2: $g=7, d=5$.
* Bò 3: $g=8, d=1$.
* Bò 4: $g=2, d=1$.

Lịch vắt sữa: **3 - 1 - 2**.
* Bò 3 (vắt từ $t=0$ đến $t=1$): $C_3=1$. $1 \le D_3=1$. (Được $8$).
* Bò 1 (vắt từ $t=1$ đến $t=2$): $C_1=2$. $2 \le D_1=3$. (Được $10$).
* Bò 2 (vắt từ $t=2$ đến $t=3$): $C_2=3$. $3 \le D_2=5$. (Được $7$).
* Bò 4 (bị loại): $D_4=1$. Nếu vắt, $C_4 \ge 1$. Nếu $C_4=1$, thì Bò 3 phải loại. Nếu vắt sau Bò 3, $C_4=2 > 1$.
* **Tổng sữa**: $8 + 10 + 7 = 25$.

---
### 🏷 Phân Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N \le 1000$ | $40\%$ |
| 2 | $N \le 10^4$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions