Problem

Submissions

First Thought

• Greedy Algorithm Won’t work
• Should adopt Dynamic Programming

#include <iostream>
#include <vector>

using namespace std;

int solve()
{
    int N; cin >> N;
    int K; cin >> K;
    int P; cin >> P;

    vector<vector<int>> stacks(N);

    for(int Ni = 0; Ni < N; ++Ni){
        stacks[Ni].resize(K);
        for(int Ki = 0; Ki < K; ++Ki) {
            cin >> stacks[Ni][Ki];
        }
    }
    int total = 0;
    while(--P) {
        auto m_row = 0;
        for(int Ni = 0; Ni < N; ++Ni) {
            if(!stacks[Ni].empty() && stacks[m_row][0] < stacks[Ni][0]) m_row = Ni;
        }
        total += stacks[m_row][0];
        stacks[m_row].erase(stacks[m_row].begin());
    }
    return total;
}

int main() {
    int N; cin >> N;
    while(N--)
        cout << solve() << endl;
    return 0;
}

(To be continued…)