6 人解决，11 人已尝试。
29 份提交通过，共有 130 份提交。
7.5 EMB 奖励。
单点时限: 3.0 sec
内存限制: 256 MB
The oppressively hot summer days have raised the cows’ clamoring to its highest level. Farmer John has finally decided to build an artificial lake. For his engineering studies, he is modeling the lake as a two-dimensional landscape consisting of a contiguous sequence of N soon-to-be-submerged levels (1 <= N <= 100,000) conveniently numbered 1..N from left to right.
Each level i is described by two integers, its width W_i (1 <= W_i <= 1,000) and height (like a relative elevation) H_i (1 <= H_i <= 1,000,000). The heights of FJ’s levels are unique. An infinitely tall barrier encloses the lake’s model on the left and right. One example lake profile is shown below.
* * : * * : * * 8 * *** * 7 * *** * 6 * *** * 5 * ********** 4 <- height * ********** 3 *************** 2 *************** 1 Level | 1 |2| 3 |
In FJ’s model, he starts filling his lake at sunrise by flowing
water into the bottom of the lowest elevation at a rate of 1 square
unit of water per minute. The water falls directly downward until
it hits something, and then it flows and spreads as room-temperature
water always does. As in all good models, assume that falling and
flowing happen instantly. Determine the time at which each elevation’s
becomes submerged by a single unit of water.
WATER WATER OVERFLOWS | | * | * * | * * * * V * * V * * * * * * .... * *~~~~~~~~~~~~* * ** * *~~~~** : * *~~~~**~~~~~~* * ** * *~~~~** : * *~~~~**~~~~~~* * ** * *~~~~**~~~~~~* *~~~~**~~~~~~* * ********* *~~~~********* *~~~~********* *~~~~********* *~~~~********* *~~~~********* ************** ************** ************** ************** ************** **************
After 4 mins After 26 mins After 50 mins
Lvl 1 submerged Lvl 3 submerged Lvl 2 submerged
Warning: The answer will not always fit in 32 bits.
Line 1: A single integer: N
Lines 2..N+1: Line i+1 describes level i with two space-separated integers: W_i and H_i
3 4 2 2 7 6 4 INPUT DETAILS: Three levels just as in the example above. Water will fill the first level because it is the lowest.
4 50 26 OUTPUT DETAILS: As in the illustrations above.
6 人解决，11 人已尝试。
29 份提交通过，共有 130 份提交。
7.5 EMB 奖励。