SequenceTime Limit:6000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
SubmitStatusPracticePOJ 2442
Description
Given m sequences, each contains n non-negative integer. Now we may select one number from each sequence to form a sequence with m integers. It’s clear that we may get n ^ m this kind of sequences. Then we can calculate the sum of numbers in each sequence, and get n ^ m values. What we need is the smallest n sums. Could you help us?
Input
The first line is an integer T, which shows the number of test cases, and then T test cases follow. The first line of each case contains two integers m, n (0 < m <= 100, 0 < n <= 2000). The following m lines indicate the m sequence respectively. No integer in the sequence is greater than 10000. Output For each test case, print a line with the smallest n sums in increasing order, which is separated by a space. Sample Input 1 2 3 1 2 3 2 2 3 Sample Output 3 3 4

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 ``` ```#include #include #include #include #include #include #include   using namespace std;   int main(){ int n, m; int cnt , i, j, k; int str1[2010], str2[2010]; priority_queue str; cin >> cnt; while(cnt--){ cin >> m >> n; memset(str1, 0, sizeof(str1)); memset(str2, 0, sizeof(str2)); for(i = 0; i < n; i ++) scanf("%d", &str1[i]); sort(str1, str1 + n); for(i = 1; i < m; i++){ for(j = 0; j < n; j++) scanf("%d", &str2[j]); sort(str2, str2 + n); for(j = 0; j < n; j ++) str.push(str2[0] + str1[j]); for(j = 1; j < n; j ++){ for(k = 0; k < n; k ++){ if(str2[j] + str1[k] > str.top()) break; str.pop(); // str.push(str2[j] + str1[k]); } } for(j = 0; j < n; j ++){ str1[n - j -1] = str.top(); //str1 str.pop();// } } for(i = 0; i < n; i ++) { if(i != 0) cout<<" "; cout<