n368. 2. Pair - 高中生程式解題系統

內容

　　給定 $N$ 個 $Pair$ ，每個 $Pair$ 包含兩個整數 $a, b$ ，挑選一個 $Pair$ 時，你可以選擇取 $a$ 、取 $b$ 或都不取，請你計算看看，分別隨機挑選 $1 \sim N$ 個 $Pair$ ，有可能的取數相加最大值。

輸入說明

　　輸入的第一行包含一個正整數 $N$ （ $1 \leq N \leq 2 \times 10^{5}$ ），代表有 $N$ 個 $Pair$ 。
　　接下來有 $N$ 行，每行包含兩個整數 $a, b$ （ $| a |, | b | \leq 10^{9}$ ），代表其中一個 $Pair$ 。

輸出說明

　　對於每筆測資，請輸出 $N$ 行，每行有一個整數 $x$ ，第 $k$ 行的 $x$ 代表隨機挑選 $k$ 個 $Pair$ 的取數相加最大值。

範例輸入 #1

2
3 5
1 -2

範例輸出 #1

5
6

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1M
公開測資點#3 (5%): 1.0s , <1M
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <1M
公開測資點#7 (5%): 1.0s , <1M
公開測資點#8 (5%): 1.0s , <1M
公開測資點#9 (5%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

　　對於「範例輸入 #1」：
選擇 $1$ 個 $Pair$ ，選 $(3, 5)$ 取 $5$ ，有最大總和 $5$ 。
選擇 $2$ 個 $Pair$ ，選 $(3, 5)$ 取 $5$ 、 $(1, - 2)$ 取 $1$ ，有最大總和 $6$ 。

本題共有 $3$ 個子題，每個子題有多筆測資。
第一子題：　 $N = 1$ ，全部解出可得 $10$ 分。
第二子題：　 $N \leq 2 \times 10^{4}$ ，全部解出可得 $40$ 分。
第三子題：　 $N \leq 2 \times 10^{5}$ ，全部解出可得 $50$ 分。

標籤:

排序

出處:

112學年度新北新莊高中校內資訊學科能力競賽 [管理者： liaoweichen1024@gmail.com

liaoweichen1 ... (M_SQRT) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」