內容
給定 $N$ 個 $\text{Pair}$，每個 $\text{Pair}$ 包含兩個整數 $a, b$，挑選一個 $\text{Pair}$ 時，你可以選擇取 $a$、取 $b$ 或都不取，請你計算看看，分別隨機挑選 $1\sim N$ 個 $\text{Pair}$，有可能的取數相加最大值。
輸入說明
輸入的第一行包含一個正整數 $N$（$1\le N\le 2\times 10^5$），代表有 $N$ 個 $\text{Pair}$。
接下來有 $N$ 行，每行包含兩個整數 $a, b$（$|a|, |b|\le 10^9$），代表其中一個 $\text{Pair}$。
輸出說明
對於每筆測資，請輸出 $N$ 行，每行有一個整數 $x$，第 $k$ 行的 $x$ 代表隨機挑選 $k$ 個 $\text{Pair}$ 的取數相加最大值。
範例輸入
#1
2 3 5 1 -2
範例輸出
#1
5 6
範例輸入
#2
4 4 14 15 0 10 15 -2 -5
範例輸出
#2
15 30 44 44
測資資訊：
記憶體限制：
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
公開 測資點#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$ 個 $\text{Pair}$，選 $(3, 5)$ 取 $5$，有最大總和 $5$。
選擇 $2$ 個 $\text{Pair}$，選 $(3, 5)$ 取 $5$、$(1, -2)$ 取 $1$，有最大總和 $6$。
本題共有 $3$ 個子題，每個子題有多筆測資。
第一子題： $N=1$，全部解出可得 $10$ 分。
第二子題： $N\le 2\times 10^4$，全部解出可得 $40$ 分。
第三子題： $N\le 2\times 10^5$，全部解出可得 $50$ 分。
標籤:
出處:
112學年度新北新莊高中校內資訊學科能力競賽
[管理者：
liaoweichen1
...
(M_SQRT)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||