#1387. CHECKIN - Check In

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

NGUỒN: Bài tập thầy Hiếu ôn Hải Phòng T11/2020

Anna (annabelle) là cô gái rất thích sống ảo. Hàng ngày, mỗi khi rảnh rỗi, cô thường tới các cửa hàng quần áo, giày dép, trang sức xem hàng, chụp ảnh selfie rồi đăng lên facebook.

Cô vừa tới khu chợ thời trang có 𝑛 cửa hàng. Qua khảo sát nhanh, cửa hàng thứ 𝑖 sẽ đóng cửa vào thời điểm 𝑡_𝑖 . Đồng thời, Anna tính toán được rằng, thời gian di chuyển, thử đồ, checkin tại cửa hàng thứ 𝑖 𝑥_𝑖 . Là một người rất yêu thích sống ảo, Anna muốn thăm nhiều cửa hàng nhất có thể.

Yêu cầu: biết rằng Anna bắt đầu di chuyển từ thời điểm 0 . Hãy lập trình giúp Anna xác định phương án tối ưu để thăm được nhiều cửa hàng nhất.

Dữ liệu vào:

  • Dòng thứ nhất chứa số nguyên dương 𝑛\ (≤ 2\times 10^5) ;
  • 𝑛 dòng tiếp theo, dòng thứ 𝑖 chứa hai số nguyên dương 𝑥_𝑖, 𝑡_𝑖\ (x_i, t_i ≤ 10^9) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là số lượng cửa hàng nhiều nhất Anna có thể ghé thăm.

Ví dụ:

Dữ liệu vào:
3
1 2
4 4
2 3
Dữ liệu ra:
2
Dữ liệu vào:
5
5 8
5 6
3 4
5 13
6 10
Dữ liệu ra:
3