TopCoder

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

100.0% (4/4)

Tags

Description

給定 N 群數字,每群都恰有 M 個正整數。若從每群數字中各選擇一個數字(假設第 i 群所選出數字為 ti),將所選出的 N 個數字加總即可得總和 S=t1+t2++tN。請寫程式計算 S 的最大值(最大總和),並判斷各群所選出的數字是否可以整除 S

範例測資一說明:挑選的數字依序是 5,6,1,總和 S=12。而此三數中可整除 S 的是 616 在第二群,1 在第三群所以先輸出 6 再輸出 1。注意,1 雖然也出現在第一群,但它不是第一群中挑出的數字,所以順序是先 61

範例測資二說明:挑選的數字依序是 6,9,7,9,總和 S=31。而此四數中沒有可整除 S 的,所以第二行輸出 -1

Input Format

第一行有兩個正整數 NM,1N20,1M20
接下來的 N 行,每一行各有 M 個正整數 xi ,代表一群整數,數字與數字間有一個空格,且 1iM,以及 1xi256

Output Format

第一行輸出最大總和 S
第二行按照被選擇數字所屬群的順序,輸出可以整除 S 的被選擇數字,數字與數字間以一個空格隔開;若 N 個被選擇數字都不能整除 S,就輸出 -1

Sample Input 1

3 2
1 5
6 4
1 1

Sample Output 1

12
6 1

Sample Input 2

4 3
6 3 2
2 7 9
4 7 1
9 5 3

Sample Output 2

31
-1

Hints

Problem Source

2016 年 APCS 考古題第 2 題「最大和」

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 2~7 1N20,M=1 20
3 8~13 1N20,M=2 30
4 0~20 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 4
1 1000 524288 65536 1 4
2 1000 524288 65536 2 4
3 1000 524288 65536 2 4
4 1000 524288 65536 2 4
5 1000 524288 65536 2 4
6 1000 524288 65536 2 4
7 1000 524288 65536 2 4
8 1000 524288 65536 3 4
9 1000 524288 65536 3 4
10 1000 524288 65536 3 4
11 1000 524288 65536 3 4
12 1000 524288 65536 3 4
13 1000 524288 65536 3 4
14 1000 524288 65536 4
15 1000 524288 65536 4
16 1000 524288 65536 4
17 1000 524288 65536 4
18 1000 524288 65536 4
19 1000 524288 65536 4
20 1000 524288 65536 4