Problem : 332 - 交換數列

Problem Statistics

Solved Member: 17　　Submission: 85　　User Tried: 20

Statement:

給定 n 個有序的數列，我們稱一個數列的大小為這個數列的總和。每次我們可以選定兩個長度不同的數列做一種操作：

1. 假設長的數列長度(數字個數)為 a, 短的數列長度為 b
2. 操作一次之後，會將這兩數列的前 b 個數字互相交換
3. 例如將 {4,5,7,1} 與 {3,6} 兩數列做一次操作之後會變成 {3,6,7,1} 和 {4,5}

於是你想知道，經過多次的操作之後，能得到總和最大的數列究竟有多大呢？

Input:Output:

第一行有一個整數 n，代表數列的個數。

接下來有 n 行，每行一開始有一個整數 w，代表這個數列的長度。接下來 w 個整數 $x_1,x_2,...,x_w$ 為這個數列的描述。

$1 \le n \le 500000$
$-10^6 \le x_i \le 10^6$
數列總長度$\le 10^6$

60% 的測試資料滿足：$n \le 1500$

輸出一個數字，代表經過操作以後，能得到總和最大的數列。

Sample Input:Sample Output:

A:
4
4 4 5 7 1
2 3 6
1 4
1 1

B:
1
2 -2 -3

C:
2
2 3 -5
1 1

A:
18

B:
-5

C:
3

Source:

103附中資奧選拔賽

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0-1	1000ms	262144kb
0-2	1000ms	262144kb
0-3	1000ms	262144kb
1-1	1000ms	262144kb	10
1-2	1000ms	262144kb
2-1	1000ms	262144kb	10
2-2	1000ms	262144kb
3-1	1000ms	262144kb	10
3-2	1000ms	262144kb
3-3	1000ms	262144kb
4	1000ms	262144kb	10
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7-1	1000ms	262144kb	10
7-2	1000ms	262144kb
8-1	1000ms	262144kb	10
8-2	1000ms	262144kb
9-1	1000ms	262144kb	10
9-2	1000ms	262144kb
10-1	1000ms	262144kb	10
10-2	1000ms	262144kb
10-3	1000ms	262144kb