Problem K

K Smallest Sums

You're given k arrays, each array has k integers. There are k^k ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them.

Input

There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000. The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.

Output

For each test case, print the k smallest sums, in ascending order.

Sample Input

Output for the Sample Input

9 10 12
2 2

Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua University
Special Thanks: Yiming Li
Note: Please make sure to test your program with the gift I/O files before submitting!

[Submit] [Go Back] [Status]

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 int arr[1000][1000],k;
10 
11 struct Item
12 {
13     int s,b;
14     Item() {}
15     Item(int x,int y):s(x),b(y){}
16     bool operator<(const Item& res) const
17     {
18         return s>res.s;
19     }
20 };
21 
22 void merge(int *A,int *B,int *C,int n)
23 {
24     priority_queue<Item> q;
25     for(int i=0;i<n;i++) q.push(Item(A[i]+B[0],0));
26     for(int i=0;i<n;i++)
27     {
28         Item tmp=q.top();  q.pop();
29         C[i]=tmp.s;
30         if(tmp.b+1<n)
31         {
32             tmp.s=tmp.s-B[tmp.b]+B[tmp.b+1];
33             tmp.b++;
34             q.push(tmp);
35         }
36     }
37 }
38 
39 int main()
40 {
41     while(scanf("%d",&k)!=EOF)
42     {
43         for(int i=0;i<k;i++)
44         {
45             for(int j=0;j<k;j++)
46                 scanf("%d",&arr[i][j]);
47             sort(arr[i],arr[i]+k);
48         }
49         int A[1000],B[1000],C[1000];
50         memcpy(A,arr[0],sizeof(A));
51         for(int i=1;i<k;i++)
52         {
53             memcpy(B,arr[i],sizeof(B));
54             merge(A,B,C,k);
55             memcpy(A,C,sizeof(A));
56         }
57         for(int i=0;i<k;i++)
58         {
59             if(i) putchar(' ');
60             printf("%d",C[i]);
61         }
62         putchar(10);
63     }
64     return 0;
65 }