TopCoder

FHVirus
$\Huge 8e7 二分圖判斷範例程式碼有錯,道歉!$

User's AC Ratio

95.6% (87/91)

Submission's AC Ratio

47.3% (130/275)

Tags

Description

在一個沿海的國家中,所有的村莊都是沿著海岸線分佈的(因此它們連成一條直線)。一條筆直的道路連接起所有沿海的村莊。所有的村莊都可以用一個非負整數表示——代表與道路開端的距離(以公里計)。

大部分的居民從事漁業活動。捕魚季節結束以後,在旅遊季節還沒有開始之前,這些居民所捕的魚可以被運送至不同的城鎮。只要某個城鎮的魚貨儲存量至少有X噸,那麼該城鎮可以提供X位旅客服務。而目標就是盡可能將所有旅客平均的分佈在每個城鎮。換句話說,我們要找出最大的整數Y,使得經過村莊與村莊間的魚貨運送,每一個村莊都至少儲存了Y噸以上的魚。

城鎮與城鎮之間可以運輸整數噸數的魚貨。但是每次在運送時,每載送一公里,就會有山上的搶匪搶走一噸的魚。具體來說,若某個村莊欲運送 F噸的魚到距離D公里遠的另一個村莊,那麼實際到達目的地的魚貨量為 F-D 噸。若F小於D,那麼整批的魚貨將會消失不見。

當然,你可以任意的在某些村莊將這些魚貨重新包裝、組合,然後再運送出去。舉個例子來說,你可以在城鎮C,將從城鎮A和城鎮B運來的魚的各一半,整理一下,然後整批運送到城鎮D,這樣只算是一次運送。

Input Format

輸入檔可能包含多筆測試資料。

每筆測試資料的第一列包含一個正整數N (1<=N<=100,000),代表城鎮的數量。

接下來的N列,每一列都有兩個整數 P、F(0<=P,F<=1012),分別代表城鎮的位置以及該城鎮漁民捕到的魚貨量(噸)。城鎮順序已經依照位置的值由小到大排好了。並且所有城鎮的位置都不一樣。

Output Format

對於每筆測試資料請輸出一列包含一個整數:Y的最大值。

Sample Input 1

3
1 0
2 21
4 0

3
5 70
15 100
1200 20

4
20 300
40 400
340 700
360 600

Sample Output 1

6
20
415

Hints

Problem Source

原TIOJ1406 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。
(Adapted From IOI2007 Practice Session - FISH)

Subtasks

No. Testdata Range Score
1 0 33
2 1 33
3 2 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3