开始: 2026-10-15 00:00:00

【集训10】模拟赛1015

结束: 2026-10-15 23:00:00
当前  2026-11-04 11:35:11  类型: IOI  状态: 已经结束 

P4. 倒栅栏fence
描述

开学季大扫除,学校要把操场边一排旧栅栏清理掉。共有 N 块栅栏,按从左到右编号 1 \sim N,第 i 块立在数轴的整数位置 x_i 上(保证 x_1 < x_2 < \dots < x_N),高度为 h_i。

工人决定玩一个游戏:**每块栅栏最多推倒一次**——

- 向左推倒:占据区间 [x_i - h_i,\ x_i];

- 向右推倒:占据区间 [x_i,\ x_i + h_i];

- 也可以不推倒,只占着自己的点 x_i。

规则:任何两块栅栏**占据的区间不能重叠**(端点相触也算重叠;推倒的栅栏如果倒向某块立着的栅栏,也会压到它,同样不允许)。

求最多能推倒多少块栅栏。


输入

第一行一个整数 N;

接下来 N 行,每行两个整数 x_i, h_i(x_i 严格递增)。

输出

一行一个整数:最多能推倒的栅栏数。


样例

输入

3
1 2
2 3
5 1

输出

2z

输入

2
1 10
2 1

输出

2

输入

1
5 3

输出

1
提示

样例1说明:(第 1 块向左倒,占 [-1,1];第 2 块向左会压到第 1 块、向右([2,5])会压到第 3 块,只能立着;第 3 块向左倒,占 [4,5]。共 2 块。)

| t1 | 20 | N \le 8,x_i \le 30,h_i \le 6 | 

| t2 | 20 | N \le 50,x_i \le 1000,h_i \le 100 | 

| t3 | 20 | N \le 2000,x_i \le 10^6 | 

| t4 | 20 | N \le 10^5,x_i, h_i \le 10^9 | 

| t5 | 20 | N \le 10^5


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交