Problem B: 火炮防御(cannon)
Memory Limit:128 MB
Time Limit:1.000 S
Judge Style:Text Compare
Creator:
Submit:162
Solved:18
Description
X国为了防止Y国来袭,构筑了一条长长的火炮防线,他们将全国所有的火炮都集中起来每隔一段距离按照功能和破坏力放置一门火炮,所有火炮成一条直线排列,每门火炮有两个参数:高度H和破坏力D。只要一有敌人来袭,就会激发火炮自动防御系统,万炮齐发,把敌人消灭在防线之外。
不幸的是Y国的黑客入侵了X国的火炮自动防御系统,他们让所有火炮在同一时间依据自身炮台高度向左右水平方向各发射一枚炮弹,炮弹会沿着跟这门火炮高度相同的高度水平飞行,直到遇到另外一门高度比它高的火炮而发生爆炸,爆炸的威力就是它的破坏力。若这发炮弹左右都没碰到一门火炮,则这发炮弹就会自动失效。显而易见每门火炮发出的炮弹可能破坏0或者1或者2门其他火炮。
X国的指挥员想知道所有火炮中遭受最严重破坏的火炮的损坏程度是多少。
不幸的是Y国的黑客入侵了X国的火炮自动防御系统,他们让所有火炮在同一时间依据自身炮台高度向左右水平方向各发射一枚炮弹,炮弹会沿着跟这门火炮高度相同的高度水平飞行,直到遇到另外一门高度比它高的火炮而发生爆炸,爆炸的威力就是它的破坏力。若这发炮弹左右都没碰到一门火炮,则这发炮弹就会自动失效。显而易见每门火炮发出的炮弹可能破坏0或者1或者2门其他火炮。
X国的指挥员想知道所有火炮中遭受最严重破坏的火炮的损坏程度是多少。
Input
第一行一个整数n
接下来n行,每行两个整数,分别代表火炮的高度H和火炮的破坏力D
接下来n行,每行两个整数,分别代表火炮的高度H和火炮的破坏力D
Output
一行,遭受最严重破坏的火炮的损坏度
Sample Input Copy
4
3 2
4 2
4 5
9 50
Sample Output Copy
7
HINT
【样例解释】
四门火炮分别受到的破坏度为 0 2 0 7
【数据规模及约定】
对于40%数据满足n≤5000且H,D≤100000
对于80%数据满足n≤10000且H,D≤100000
对于100%数据满足1≤n≤1000000且H,D≤1000000000
本题可以使用
ios_base::sync_with_stdio(false) ;
cin.tie(0);
四门火炮分别受到的破坏度为 0 2 0 7
【数据规模及约定】
对于40%数据满足n≤5000且H,D≤100000
对于80%数据满足n≤10000且H,D≤100000
对于100%数据满足1≤n≤1000000且H,D≤1000000000
本题可以使用
ios_base::sync_with_stdio(false) ;
cin.tie(0);