POJ/2442.cc

   1 #include <cstdio>
   2 #include <cassert>
   3 #include <queue>
   4 #include <algorithm>
   5
   6 const int maxn=2000;
   7
   8 std::priority_queue<int> heap;
   9
  10 int pool[2][maxn];
  11 int *a=pool[0],*b=pool[1];
  12
  13 int main() {
  14         int tcase,n,m;
  15         register int i,j;
  16         std::scanf("%d",&tcase);
  17         while (tcase--) {
  18                 std::scanf("%d%d",&m,&n);
  19                 for (--m,i=0; i<n; ++i) std::scanf("%d",&a[i]);
  20                 std::sort(a,a+n);
  21                 while (m--) {
  22                         for (i=0; i<n; ++i) scanf("%d",&b[i]);
  23                         std::sort(b,b+n);
  24                         for (i=0; i<n; ++i) heap.push(a[i]+b[0]);
  25                         for (i=1; i<n; ++i) {
  26                                 for (j=0; j<n; ++j) {
  27                                         if (b[i]+a[j] > heap.top()) break;
  28                                         heap.pop();
  29                                         heap.push(b[i]+a[j]);
  30                                 }
  31                         }
  32                         i=0;
  33                         while (!heap.empty()) a[i++]=heap.top(),heap.pop();
  34                         std::sort(a,a+n);
  35                 }
  36                 for (i=0; i<n; ++i) printf("%d ",a[i]);
  37                 putchar('\n');
  38         }
  39         return 0;
  40 }