Elearning CodePath – CTP Online Judge

Bánh Sinh Nhật

BANH_SINH_NHAT

🟢 Medium #General #Tree #Set / Map

### 📌 Thông tin chung

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

Cho $N$ chiếc bánh ngọt được đặt tại các tọa độ $x_i$ trên một trục số. Chiếc bánh thứ $i$ mất $t_i$ giây để ăn hết.
Vị trí ban đầu của Khánh là gốc tọa độ $O$ (tọa độ $0$).

* **Thời gian di chuyển** giữa hai chiếc bánh ở vị trí $x_i$ và $x_j$ là $|x_j - x_i|$ giây.
* **Tổng thời gian** để Khánh ăn một tập hợp các bánh $I = \{i_1, i_2, \dots, i_k\}$ được tính bằng:
    $$
    T_{\text{tổng}} = T_{\text{di chuyển}} + T_{\text{ăn}}
    $$
* Khánh chỉ có thể ăn các bánh trong thời gian tối đa $T$ giây.

Yêu cầu: Tính số lượng bánh **nhiều nhất** mà Khánh có thể ăn trong thời gian $\le T$.

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

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

* Dòng đầu tiên: Hai số nguyên $N$ và $T$.
* $N$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $x_i$ và $t_i$.

Giới hạn:
* $1 \le N \le 10^5$, $1 \le T \le 10^9$.
* $1 \le x_i, t_i \le 10^9$.
* Dữ liệu đảm bảo: $x_i$ được liệt kê theo thứ tự không giảm ($x_i \le x_{i+1}$).

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

Ghi ra file `CAKES.OUT` một dòng duy nhất, số nguyên là số lượng bánh nhiều nhất mà Khánh có thể ăn.

---
### ✨ Ví dụ

| Input (`CAKES.INP`) | Output (`CAKES.OUT`) |
| :--- | :--- |
| `3 10` <br> `1 4` <br> `2 6` <br> `3 3` | `2` |

### 🏷 Phân Subtask

Thuật toán $O(N \log N)$ là cần thiết.

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

---

✅ Đã AC: 0 / 0 submissions