GOODG - Good Inflation

The competition is drawing to a close, and The Team could really use another balloon to help them come out on top...good thing they're no chumps, and thought of this in advance! Before the contest started, they instructed an accomplice to go to the local balloon shop, buy an extra balloon, and deliver it to them at the conclusion of the event. It is true that their balloons then won't match up with the scoreboard's record of which problems they've solved - but, in the end, it's the balloons that count! In fact, The Team knows that, the larger their extra balloon, the more their opponents (and the judges) will be intimidated. They're not the best ACM-ICPC team in the world for nothing!

However, this balloon shop is rather strange. The accomplice is given an empty balloon (a balloon with size 0), and told that he can tie it closed and keep it after exactly $N$ ($1 \leq N \leq 10^6$) minutes. In the meantime, during each minute, an inflation offer is available. If offer $i$ is taken, then, at the start of the $i$th minute, the balloon's size will be increased by $a_i$ ($0 \leq a_i \leq 10^6$). However, since the balloon cannot be closed until the end, its air will leak out at a constant rate, which depends on the gas that was used - in particular, its size will immediately start to decrease at a rate of $d_i$ ($0 \leq d_i \leq 10^6$) per minute, until either another offer is taken, or the balloon deflates completely (its size can never become negative, of course).

The Team will not be happy if they don't receive the largest balloon possible. Unfortunately, their accomplice happens to Can you figure out the maximal size that the balloon can have at the start of minute $N+1$, before it's too late?


First line: 1 integer, $N$

Next $N$ lines: 2 integers, $a_i$ and $d_i$, for $i=1..N$


1 integer, the maximal size which the balloon can have at the start of minute $N+1$.


2 3
10 2
0 1
5 4
1 10
Explanation of Sample:

The best option is to take only the offers at minutes 2 and 3. At the start of minute 2, the balloon will be inflated to size 10, and will deflate to size 8 by the start of minute 3. At that point, the balloon's size will not change, but its deflation rate will change to 1. As a result, by the start of minute 6, its size will be 5.

Note that, if the offer at minute 1 is additionally taken, the balloon will simply be inflated to size 2 before deflating back to size 0 by the start of minute 2 - therefore, this will not change the outcome.

Also note that, if the offer at minute 4 is additionally taken, the balloon will inflate to size 12 at the start of minute 4, but its deflation rate of 4 will result in a size of 4 at the start of minute 6, which is not optimal.


hide comments
Sigma Kappa: 2017-07-20 05:37:10

The convex hull trick here needs to be fully dynamic. STL set<> is your friend, along with custom comparators.

Last edit: 2017-07-22 13:19:06
tomcilo: 2017-04-03 22:43:29

What a great way to solve your 15th problem :D

Rishav Goyal: 2015-08-22 16:17:49

jacob can you tell me the error in implementation? i am sure i have correct algo.

ppppppxx: 2015-08-22 16:14:36

Last edit: 2015-08-22 16:14:49
Alex Abbas: 2014-09-27 15:12:27

@Jacob Plachta could you please see my 12471836 submission, I'm pretty sure it shouldn't give wrong answers...

RE: You get 1/5 cases wrong, and it doesn't look like it's the data's fault.

Last edit: 2014-10-01 07:44:23
Dionysis Zindros: 2013-08-03 21:01:25

@Jacob Plachta Could we perhaps have some non-trivial larger test-cases to work with? It would help with debugging. See submission id: 9775390

Giorgos Christoglou: 2013-05-26 09:15:29

@Jacob Plachta could you see please my last submission is anything wrong with my solution logic or just a bug that I should fix? the id: 9346240

RE: It looks like you have the right algorithm, though the implementation is more complicated than it could be. However, some of your submissions (including that one) apparently produce no output on the last case (and another large answer is also a bit off).

Thank you for your response , i will try to simplify my code and check for bugs..

Last edit: 2013-05-30 09:57:36

Added by:SourSpinach
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem