Problem : 34 - 海報

Problem Statistics

Solved Member: 45　　Submission: 141　　User Tried: 48

Statement:

在拜特堡東區的大樓皆依照著一個原則建造：每兩棟大樓相鄰，並且中間沒有任何間隔。由東往西看，這些大樓很整齊的排成一列。

拜特堡的的市長－－拜特瑟決定把這些大樓的外牆貼上海報來賺取廣告收入，以減少人民的稅金壓力(天啊，真好心)。每張海報都是長方形的，它不可以超過大樓的邊緣，並且你可以假設它最大可以到無限大。

請問你最少要幾張海報才能夠把所有大樓貼滿。

Task:

請你寫一個程式：

1.讀入所有大樓的形狀
2.計算最少需要幾張海報
3.並且輸出上面的答案

Input:Output:

第1行有1個整數n(1 <= n <= 250000)，代表高樓的數量。
接下來n行各有兩個整數Di,Wi(1 <= Di,Wi <= 1000000000)，以空格分隔，分別代表大樓的寬度和高度。

輸出只有1行，請你輸出最少所需要的海報數量。

Sample Input:Sample Output:

5
1 2
1 3
2 2
2 5
1 4

HINT:

範例輸入的圖形：

並且最佳解答為：

Source:

POI 15 Stage 1

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-ocen	1000ms	32768kb
1-1	1000ms	32768kb	10
1-2	1000ms	32768kb
1-3	1000ms	32768kb
2-ocen	1000ms	32768kb
2-1	1000ms	32768kb	10
2-2	1000ms	32768kb
2-3	1000ms	32768kb
3-ocen	1000ms	32768kb
3-1	1000ms	32768kb	10
3-2	1000ms	32768kb
3-3	1000ms	32768kb
4-ocen	5000ms	32768kb
4-1	1000ms	32768kb	10
4-2	1000ms	32768kb
5-1	1500ms	32768kb	10
5-2	1500ms	32768kb
6-1	1500ms	32768kb	10
6-2	1500ms	32768kb
7-1	1500ms	32768kb	10
7-2	1500ms	32768kb
8-1	1500ms	32768kb	10
8-2	1500ms	32768kb
9-1	1500ms	32768kb	10
9-2	1500ms	32768kb
10-1	1500ms	32768kb	10
10-2	1500ms	32768kb