#PU859. USACO 2018 December Contest, Silver — Problem 2. Convention II

    ID: 1259 传统题 文件IO:convention2 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高 上传者: 标签>USACO赛事:dec18来源:usaco.orgscoring:equal_test_cases堆

USACO 2018 December Contest, Silver — Problem 2. Convention II

USACO 2018 December Contest, Silver — Problem 2. Convention II

题目描述

Despite long delays in airport pickups, Farmer John's convention for cows interested in eating grass has been going well so far. It has attracted cows from all over the world. The main event of the conference, however, is looking like it might cause Farmer John some further scheduling woes. A very small pasture on his farm features a rare form of grass that is supposed to be the tastiest in the world, according to discerning cows. As a result, all of the NN cows at the conference (1≤N≤1051 \leq N \leq 10^5) want to sample this grass. This will likely cause long lines to form, since the pasture is so small it can only accommodate one cow at a time. Farmer John knows the time aia_i that each cow ii plans to arrive at the special pasture, as well as the amount of time tit_i she plans to spend sampling the special grass, once it becomes her turn. Once cow ii starts eating the grass, she spends her full time of tit_i before leaving, during which other arriving cows need to wait. If multiple cows are waiting when the pasture becomes available again, the cow with the highest seniority is the next to be allowed to sample the grass. For this purpose, a cow who arrives right as another cow is finishing is considered "waiting". Similarly, if a number of cows all arrive at exactly the same time while no cow is currently eating, then the one with highest seniority is the next to eat. Please help FJ compute the maximum amount of time any cow might possibly have to wait in line (between time aia_i and the time the cow begins eating).

输入格式

The first line of input contains NN. Each of the next NN lines specify the details of the NN cows in order of seniority (the most senior cow being first). Each line contains aia_i and tit_i for one cow. The tit_i's are positive integers each at most 10410^4, and the aia_i's are positive integers at most 10910^9.

输出格式

Please print the longest potential waiting time over all the cows.

数据范围

(见题面原文)

样例

样例 1

5
25 3
105 30
20 50
10 17
100 10
10
In this example, we have 5 cows (numbered 1..5 according to their order in the