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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
constexpr ll INF = 1e18;

struct gummy {
    int color, mass, cost;
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k, m;
    cin >> n >> k >> m;
    vector<gummy> gummies(n);
    for (auto& g : gummies)
        cin >> g.color >> g.mass >> g.cost;

    vector<vector<gummy>> gfc(k + 1);  // (gummies for color) gfc[i] - vector of all gummies that have color = i
    for (const auto& g : gummies)
        gfc[g.color].push_back(g);

    vector<vector<ll>> dp(k, vector<ll>(m, INF));
    dp[0][0] = 0;
    queue<tuple<ll,int,int>> q;  // {-cost, color, reminder}
    q.push({0, 0, 0});
    while (q.size()) {
        auto [total_cost, i, j] = q.front(); q.pop(); total_cost *= -1;
        if (dp[i][j] < total_cost)
            continue;
        int next_i = (i + 1) % k;
        for (const auto& g : gfc[i+1]) {
            int next_j = (j + g.mass) % m;
            if (dp[next_i][next_j] > total_cost + g.cost) {
                dp[next_i][next_j] = total_cost + g.cost;
                q.push({-(total_cost + g.cost), next_i, next_j});
            }
        }
    }
    for (int j = 0; j < m; j++)
        cout << (dp[0][j] == INF ? -1 : dp[0][j]) << '\n';
    return 0;
}