A8173 | Tram
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
Linear Kingdom has exactly one tram line. It has $n$ stops, numbered from $1$ to $n$ in the order of tram's movement. At the $i$ -th stop $a_{i}$ passengers exit the tram, while $b_{i}$ passengers enter it. The tram is empty before it arrives at the first stop. Also, when the tram arrives at the last stop, all passengers exit so that it becomes empty.
Your task is to calculate the tram's minimum capacity such that the number of people inside the tram at any time never exceeds this capacity. Note that at each stop all exiting passengers exit before any entering passenger enters the tram.
Your task is to calculate the tram's minimum capacity such that the number of people inside the tram at any time never exceeds this capacity. Note that at each stop all exiting passengers exit before any entering passenger enters the tram.
输入格式
The first line contains a single number $n$ ( $2<=n<=1000$ ) — the number of the tram's stops.
Then $n$ lines follow, each contains two integers $a_{i}$ and $b_{i}$ ( $0<=a_{i},b_{i}<=1000$ ) — the number of passengers that exits the tram at the $i$ -th stop, and the number of passengers that enter the tram at the $i$ -th stop. The stops are given from the first to the last stop in the order of tram's movement.
- The number of people who exit at a given stop does not exceed the total number of people in the tram immediately before it arrives at the stop. More formally, . This particularly means that $a_{1}=0$ .
- At the last stop, all the passengers exit the tram and it becomes empty. More formally, .
- No passenger will enter the train at the last stop. That is, $b_{n}=0$ .
Then $n$ lines follow, each contains two integers $a_{i}$ and $b_{i}$ ( $0<=a_{i},b_{i}<=1000$ ) — the number of passengers that exits the tram at the $i$ -th stop, and the number of passengers that enter the tram at the $i$ -th stop. The stops are given from the first to the last stop in the order of tram's movement.
- The number of people who exit at a given stop does not exceed the total number of people in the tram immediately before it arrives at the stop. More formally, . This particularly means that $a_{1}=0$ .
- At the last stop, all the passengers exit the tram and it becomes empty. More formally, .
- No passenger will enter the train at the last stop. That is, $b_{n}=0$ .
输出格式
Print a single integer denoting the minimum possible capacity of the tram (0 is allowed).
输入输出样例
输入 #1
4 0 3 2 5 4 2 4 0
输出 #1
6
For the first example, a capacity of 6 is sufficient:
- At the first stop, the number of passengers inside the tram before arriving is 0. Then, 3 passengers enter the tram, and the number of passengers inside the tram becomes 3.
- At the second stop, 2 passengers exit the tram (1 passenger remains inside). Then, 5 passengers enter the tram. There are 6 passengers inside the tram now.
- At the third stop, 4 passengers exit the tram (2 passengers remain inside). Then, 2 passengers enter the tram. There are 4 passengers inside the tram now.
- Finally, all the remaining passengers inside the tram exit the tram at the last stop. There are no passenger inside the tram now, which is in line with the constraints.
Since the number of passengers inside the tram never exceeds 6, a capacity of 6 is sufficient. Furthermore it is not possible for the tram to have a capacity less than 6. Hence, 6 is the correct answer.
- At the first stop, the number of passengers inside the tram before arriving is 0. Then, 3 passengers enter the tram, and the number of passengers inside the tram becomes 3.
- At the second stop, 2 passengers exit the tram (1 passenger remains inside). Then, 5 passengers enter the tram. There are 6 passengers inside the tram now.
- At the third stop, 4 passengers exit the tram (2 passengers remain inside). Then, 2 passengers enter the tram. There are 4 passengers inside the tram now.
- Finally, all the remaining passengers inside the tram exit the tram at the last stop. There are no passenger inside the tram now, which is in line with the constraints.
Since the number of passengers inside the tram never exceeds 6, a capacity of 6 is sufficient. Furthermore it is not possible for the tram to have a capacity less than 6. Hence, 6 is the correct answer.
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted