TopCoder

Thumb
1.6449
Rolling in the DeeP?

User's AC Ratio

90.0% (9/10)

Submission's AC Ratio

59.4% (19/32)

Description

小智的學校在天空之城,父母親每天開直升機送他上下學,上學途中小智可以一邊抓寶。請寫個程式幫助小智的父母親規劃一條路徑以便在從家裡到學校的路上,小智可以抓到最多的寶貝。

學校與小智家之間所有的位置均等劃分成N x N 的格子(如下所示),每個格子以座標(x, y)表示,其中x 代表水平距離,y 代表高度,若小智家的座標設為原點(0, 0),學校的座標則為(N-1, N-1)。 直升機飛行的路線被設定成每次只能向右或向上推進一格,也就是說,若直升機在(x, y)上,下一步只能飛達(x+1, y)或(x, y+1),當然,直升機也不可以飛超過0≦x<N 及0≦y<N 的範圍。

小智上學的路途上一共有N 隻寶貝,每隻寶貝可以被補獲的範圍是某特定高度而水平座標在某連續區間的格子。明確的說,對於寶貝P(i), 0≦i<N,要捕抓到P(i),小智必須經過下列座標之一:$\{(x, y)| S(i)\leq x\leq T(i), y=i\}$,其中$0≦S(i), T(i) <N$。

上圖是一個N=5 的例子,藍色區塊顯示可以捕抓到寶貝的座標位置,例如寶貝0 (P(0))的捕獲區域為 S(0)≦x≦T(0) (而S(0)=1, T(0)=2),且y = 0。每一個寶貝可捕獲區域都一定在一個水平連續區間。紅線所顯示的路徑是一條合乎規定的飛行路徑,因為每一步都只有向右或向上,沿這一條路徑共可以捕抓到四隻寶貝,即P(0), P(1), P(2), P(4),也是所有可能路徑中可以捕抓到寶貝數最多的。

Input Format

輸入的第一行是座標範圍N,接下來的N 行,每一行有兩個以空白隔開的整數S(i)與T(i),依序是i = 0, 1,…, N-1,其中0≦S(i)≦T(i)<N。

Output Format

輸出一整數為小智最多可以抓到的寶貝數量。

Sample Input

輸入範例一 (符合子題一、三)
5
2 2
1 1
0 0
2 2
4 4
輸入範例二 (符合子題二、四、五)
5
1 3
0 1
3 4
0 0
2 3

Sample Output

輸出範例一
3

輸出範例二
4

Hints

本題共有五個子題,每一子題可有多筆測試資料:
第一子題的測試資料 N≦10,且對所有i,S(i)=T(i),全部解出可獲17 分;
第二子題的測試資料 N≦5,000,全部解出可獲13 分;
第三子題的測試資料 N≦100,000,且對所有i,S(i)=T(i),全部解出可獲13 分;
第四子題的測試資料 N≦300,000,全部解出可獲25 分;
第五子題的測試資料 N≦800,000,全部解出可獲32 分。

Problem Source

105學年度高級中學資訊學科能力競賽決賽 程式設計試題第四題

Subtasks

For Testdata: 0 ~ 8, Score: 17
For Testdata: 0 ~ 16, Score: 13
For Testdata: 17 ~ 23, Score: 13
For Testdata: 0 ~ 35, Score: 25
For Testdata: 0 ~ 51, Score: 32
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 65536
1 1000 524288 65536
2 1000 524288 65536
3 1000 524288 65536
4 1000 524288 65536
5 1000 524288 65536
6 1000 524288 65536
7 1000 524288 65536
8 1000 524288 65536
9 1000 524288 65536
10 1000 524288 65536
11 1000 524288 65536
12 1000 524288 65536
13 1000 524288 65536
14 1000 524288 65536
15 1000 524288 65536
16 1000 524288 65536
17 1000 524288 65536
18 1000 524288 65536
19 1000 524288 65536
20 1000 524288 65536
21 1000 524288 65536
22 1000 524288 65536
23 1000 524288 65536
24 1000 524288 65536
25 1000 524288 65536
26 1000 524288 65536
27 1000 524288 65536
28 1000 524288 65536
29 1000 524288 65536
30 1000 524288 65536
31 1000 524288 65536
32 1000 524288 65536
33 1000 524288 65536
34 1000 524288 65536
35 1000 524288 65536
36 1000 524288 65536
37 1000 524288 65536
38 1000 524288 65536
39 1000 524288 65536
40 1000 524288 65536
41 1000 524288 65536
42 1000 524288 65536
43 1000 524288 65536
44 1000 524288 65536
45 1000 524288 65536
46 1000 524288 65536
47 1000 524288 65536
48 1000 524288 65536
49 1000 524288 65536
50 1000 524288 65536
51 1000 524288 65536