e370.
翻牌
內容
這天，蝸牛老師想要來考驗他的學生，他在桌上放了 N 張卡牌，卡牌的正反面都各寫了一個正整數，他提出了這樣的問題：
「如果我們可以自由選擇卡牌要正面還是反面朝上的話，那所有朝上顯現出來的數字的總和最大可以是多少呢？」
聰明的學生們當然很快就解決掉這個問題了，於是蝸牛老師決定加高難度：
「那如果，我們計算分數的方式改成，把朝上的數字一一加進袋子裡，如果要加進去的數字在袋子裡已經出現過了就不加進去，那最後袋子裡的數字總和最大會是多少呢？」
學生們馬上就被難倒了，你可以幫助他們嗎？
輸入說明
首行輸入一個整數 N (1 ≤ N ≤ 106 ) 代表有 N 張卡牌。
接下來 N 行，第 i 行會有兩個正整數 ai, bi (1 ≤ ai, bi ≤ 109)，分別代表第 i 張卡牌的正面數字和反面數字。
輸出說明
輸出最大的總和。
範例輸入
#1
輸入範例一 3 1 2 2 3 3 4 輸入範例二 3 1 2 2 3 3 1 輸入範例三 3 1 1 2 2 3 3 輸入範例四 3 1 2 3 4 5 6 輸入範例五 3 1 2 1 2 1 2
範例輸出
#1
輸出範例一 9 輸出範例二 6 輸出範例三 6 輸出範例四 12 輸出範例五 3
測資資訊：
記憶體限制：
512
MB
不公開 測資點#0 (4%): 1.5s , <1K
不公開 測資點#1 (4%): 1.5s , <1K
不公開 測資點#2 (4%): 1.5s , <1K
不公開 測資點#3 (4%): 1.5s , <1K
不公開 測資點#4 (4%): 1.5s , <1K
不公開 測資點#5 (5%): 1.5s , <1K
不公開 測資點#6 (5%): 1.5s , <50M
不公開 測資點#7 (5%): 1.5s , <1M
不公開 測資點#8 (5%): 1.5s , <1M
不公開 測資點#9 (5%): 1.5s , <1M
不公開 測資點#10 (5%): 1.5s , <1M
不公開 測資點#11 (5%): 1.5s , <1M
不公開 測資點#12 (5%): 1.5s , <1M
不公開 測資點#13 (5%): 1.5s , <1M
不公開 測資點#14 (5%): 1.5s , <50M
不公開 測資點#15 (5%): 1.5s , <50M
不公開 測資點#16 (5%): 1.5s , <50M
不公開 測資點#17 (5%): 1.5s , <50M
不公開 測資點#18 (5%): 1.5s , <50M
不公開 測資點#19 (5%): 1.5s , <50M
不公開 測資點#20 (5%): 1.5s , <50M
不公開 測資點#0 (4%): 1.5s , <1K
不公開 測資點#1 (4%): 1.5s , <1K
不公開 測資點#2 (4%): 1.5s , <1K
不公開 測資點#3 (4%): 1.5s , <1K
不公開 測資點#4 (4%): 1.5s , <1K
不公開 測資點#5 (5%): 1.5s , <1K
不公開 測資點#6 (5%): 1.5s , <50M
不公開 測資點#7 (5%): 1.5s , <1M
不公開 測資點#8 (5%): 1.5s , <1M
不公開 測資點#9 (5%): 1.5s , <1M
不公開 測資點#10 (5%): 1.5s , <1M
不公開 測資點#11 (5%): 1.5s , <1M
不公開 測資點#12 (5%): 1.5s , <1M
不公開 測資點#13 (5%): 1.5s , <1M
不公開 測資點#14 (5%): 1.5s , <50M
不公開 測資點#15 (5%): 1.5s , <50M
不公開 測資點#16 (5%): 1.5s , <50M
不公開 測資點#17 (5%): 1.5s , <50M
不公開 測資點#18 (5%): 1.5s , <50M
不公開 測資點#19 (5%): 1.5s , <50M
不公開 測資點#20 (5%): 1.5s , <50M
提示 ：
因測資超過ZJ上限500MB，所以只挑選部分測資。
日後仍有可能變動測資，若題敘或測資有問題歡迎寄信。
本題共有六組測試題組，條件限制如下所示。每一組可有一或多筆測試資料。
|
子任務 |
額外輸入限制 |
|
e370_00-e370_05 |
N ≤18，1 ≤ ai, bi ≤ 106 。 |
|
e370_06 |
N 張牌的數字都不同(總共有 2N 個相異數字) |
|
e370_07-e370_10 |
N ≤1000，1 ≤ ai, bi ≤ 103 。 |
|
e370_11-e370_13 |
N ≤1000，1 ≤ ai, bi ≤ 109 。 |
|
e370_14-e370_18 |
N ≤106，1 ≤ ai, bi ≤ 106 。 |
|
e370_19-e370_20 |
無特別限制。 |
標籤:
出處:
108學年度板橋高中校內資訊學科能力競賽Day3_pE310573sao
[管理者：
310573sao
(Jiburiru)
]