[POJ] 2442 Sequence.cpp

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
struct custom_type {
    int val;
    int pos;

    bool operator < (const custom_type &B) const {
        return val > B.val; // min heap
    }
};
int main()
{
    int T ,M, N, L1[2001], L2[2001];
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &M, &N);
        for (int i = 0; i < N; ++i) scanf("%d", &L1[i]);
        sort(L1, L1 + N);

        for (int k = 1; k < M; ++k) {
            for (int i = 0; i < N; ++i) scanf("%d", &L2[i]);
            sort(L2, L2 + N);
            
            priority_queue<custom_type> PQ;
            for (int i = 0; i < N; ++i) 
                PQ.push({L1[i] + L2[0], 0});
            
            for (int i = 0; i < N; ++i) {
                custom_type tmp = PQ.top();
                PQ.pop();
                L1[i] = tmp.val;
                if (tmp.pos+1 < N)
                    PQ.push({tmp.val - L2[tmp.pos] + L2[tmp.pos+1], tmp.pos + 1});
            }
        }
        for (int i = 0; i < N - 1; ++i)
            printf("%d ", L1[i]);
        printf("%d\n", L1[N-1]);
    }
}