Elearning CodePath – CTP Online Judge

Bánh sinh nhật

ANNICAKE

🟢 Hard #Greedy #Sliding Window #Queue #Data Structure

### 📌 Thông tin chung

### Bài toán

Tỉ phú Bình muốn ăn càng nhiều bánh sinh nhật càng tốt trong $T$ giây. Các bánh sinh nhật nằm trên một đường thẳng. Ban đầu Bình đứng ở vị trí tọa độ $0$. 
* Bánh thứ $i$ nằm tại tọa độ $x_i$ và cần $t_i$ thời gian để ăn hết.
* Thời gian di chuyển từ tọa độ $a$ đến tọa độ $b$ là $|a - b|$.
* Nếu nhiều bánh ở cùng một vị trí, Bình có thể ăn lần lượt các bánh đó mà không tốn thêm thời gian di chuyển giữa chúng.

Yêu cầu: Tìm số lượng bánh sinh nhật lớn nhất mà Bình có thể ăn trong khoảng thời gian $T$ giây.

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

Dữ liệu vào từ file ANNICAKE.INP:
* Dòng đầu tiên gồm hai số nguyên dương $n$ và $T$ ($n \le 10^5, T \le 10^9$).
* $n$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $x_i$ và $t_i$ ($x_i, t_i \le 10^9$) là tọa độ và thời gian ăn của bánh thứ $i$.
* Các bánh được cho theo thứ tự tọa độ không giảm ($x_i \le x_{i+1}$).

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

Ghi ra file ANNICAKE.OUT một số nguyên duy nhất là số lượng bánh lớn nhất có thể ăn được.

### ✨ Ví dụ

| ANNICAKE.INP | ANNICAKE.OUT |
| :--- | :--- |
| 3 10 <br> 1 4 <br> 2 5 <br> 3 3 | 2 |

**Giải thích ví dụ:**
- Nếu Bình đi đến tọa độ $x=2$: tốn $2$ giây di chuyển. Bình ăn bánh 1 (tốn 4s) và bánh 2 (tốn 5s). Tổng thời gian: $2 + 4 + 5 = 11 > 10$ (Không thỏa mãn).
- Nếu Bình đi đến tọa độ $x=3$: tốn $3$ giây di chuyển. Bình ăn bánh 1 (tốn 4s) và bánh 3 (tốn 3s). Tổng thời gian: $3 + 4 + 3 = 10 \le 10$ (Thỏa mãn). Số bánh ăn được là 2.

### 🏷 Subtasks

| Subtask | Ràng buộc | Tỷ lệ điểm |
| :--- | :--- | :--- |
| 1 | $n \le 1000$ | 40% |
| 2 | $n \le 10^5, T \le 10^9$ | 60% |

✅ Đã AC: 2 / 6 submissions