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
#include <iostream>
#include <numeric>
#include <vector>

int main() {
    int n, k, m;
    std::cin >> n >> k >> m;

    std::vector<std::vector<std::pair<int, int64_t>>> in(k);
    for (int i = 0; i < n; ++i) {
        int k_i, m_i;
        int64_t c_i;
        std::cin >> k_i >> m_i >> c_i;

        in[k_i - 1].emplace_back(m_i, c_i);
    }

    std::vector<int64_t> dyn1(m, 1LL << 60);
    dyn1[0] = 0;
    for (auto &color: in) {
        auto prev = std::move(dyn1);
        dyn1 = std::vector<int64_t>(m, 1LL << 60);
        for (auto [m_i, c_i]: color) {
            for (int i = 0; i < m; ++i) {
                if (dyn1[(i + m_i) % m] > c_i + prev[i]) {
                    dyn1[(i + m_i) % m] = c_i + prev[i];
                }
            }
        }
    }

    std::vector<int64_t> dyn2(m, 1LL << 60);
    dyn2[0] = 0;
    for (int i = 1; i < m; ++i) {
        bool improved;
        do {
            improved = false;
            for (int j = 0; j < m; ++j) {
                if (dyn2[(i + j) % m] > dyn1[i] + dyn2[j]) {
                    dyn2[(i + j) % m] = dyn1[i] + dyn2[j];
                    improved = true;
                }
            }
        } while (improved);
    }

    for (auto v: dyn2) {
        std::cout << ((v < (1LL << 60)) ? v : -1) << "\n";
    }
}