Tàu Điện Ngầm

Buổi 12 — Greedy Algorithm Buổi 15 — Prefix Sum & Difference Array Buổi 16 — Contest Chặng 2 prefix-sum
Points
40
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Tuyến tàu điện ngầm có $N$ ga. Tại ga $i$, có $a_i$ hành khách lên tàu và $b_i$ hành khách xuống tàu (hành khách xuống trước khi hành khách lên). Ban đầu tàu trống. Hãy tìm số hành khách tối đa trên tàu tại bất kỳ thời điểm nào (sau khi xử lý xong mỗi ga).

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$ $(1 \le N \le 10^5)$.
  • $N$ dòng tiếp theo, mỗi dòng chứa $a_i$ và $b_i$ $(0 \le a_i, b_i \le 10^9)$.
  • Đảm bảo số người trên tàu luôn không âm.
Dữ liệu ra
  • In ra số hành khách tối đa trên tàu.
Ví dụ
Input Output
4
10 0
5 3
2 8
0 6
12
Giới hạn
  • $1 \le N \le 10^5$
  • $0 \le a_i, b_i \le 10^9$
Draft saved