Skip to content

14294: 【原4294】憨憨开灯

题目

题目描述

author: Unknown 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4294

问题描述

铁憨憨很喜欢开着一个名叫“骑行世界校园”的APP在宣怀大道上骑车。这一天,金憨憨想做恶作剧,就把宣怀大道上的路灯全都关了。关灯后宣怀大道上漆黑一片。因为在黑暗中骑车太危险,所以铁憨憨想把宣怀大道的路上的灯重新开起来。

如果把宣怀大道看成从左向右的一条线,那么每一个路灯可以看做直线上的一点。同时,宣怀大道的路上的灯很奇怪。对于任意一个路灯,它要么只能向左照亮一定距离,要么只能向右照亮一定距离。

一般的,我们可以把宣怀大道看成 $x$ 轴。对于第 $i$ 个路灯,它在坐标轴上的位置为 $a_i$,照明能力为 $l_i$。那么铁憨憨有三种选择:

  1. 不开灯,那么这一个路灯不会照亮任何地方。
  2. 向左开灯,那么坐标轴上的区间 $[a_i-l_i,a_i]$ 将被照亮。
  3. 向右开灯,那么坐标轴上的区间 $[a_i,a_i+l_i]$ 将被照亮。

铁憨憨希望能找到一个最佳的开灯方案,使得宣怀大道上被照亮的地方尽量大,也就是被照亮的区间的并尽量大。但是铁憨憨还没骑满80km,所以没空考虑这个问题,就把这个问题交给了你。

输入格式

数据第一行包含一个整数 $n$,表示路灯数量。

接下来的 $n$ 行每行包含两个整数 $a_i$ 和 $l_i$,表示第 $i$ 个路灯的位置以及它的照明能力。

输出格式

输出一行一个整数,表示最长能够被照亮的区间长度。

样例输入

4
1 2
3 3
4 3
6 2

样例输出

9

样例解释

从左到右四个路灯的照亮方向应该是:左右左右。

数据规模

对于 10% 的数据,$n=1$。

对于 20% 的数据,$n\le10$。

对于 40% 的数据,$n\le30$。

对于 60% 的数据,$n\le50$。

对于 80% 的数据,$n\le100$。

对于 100% 的数据,$n\le 300,a_i\le 10^8,l_i\le 10^8,ai\ge0,li>0$,保证 $a_i$ 互不相同。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!