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
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAX_N = 7000;

long long dp[MAX_N][MAX_N];

int main() {

    int n, k, m; cin >> n >> k >> m;

    vector<vector<pair<int, int>>>gummies(k);

    for(int i = 0; i < n; i++) {
        int color, mass, price; cin >> color >> mass >> price;
        gummies[color - 1].emplace_back(mass, price);
    }

    for(int i = 0; i < k; i++)
        for(int j = 0; j < m; j++)
            dp[i][j] = 1ll << 62;

    dp[0][0] = 0;

    priority_queue<pair<long long, int>>q;

    q.push(make_pair(0, 0));

    while(!q.empty()) {
        auto p = q.top();
        q.pop();

        int a = p.second / MAX_N;
        int b = p.second % MAX_N;

        if(dp[a][b] != -p.first)
            continue;

   //     cout << "a = " << a << ", b = " << b << "\n";

        int new_a = (a + 1) % k;

        for(auto [mass, price] : gummies[a]) {
            int new_b = (b + mass) % m;
            if(dp[new_a][new_b] > dp[a][b] + price) {
                dp[new_a][new_b] = dp[a][b] + price;

                int id = new_a * MAX_N + new_b;
                q.push(make_pair(-dp[new_a][new_b], id));
            }
        }
    }

    for(int i = 0; i < m; i++) {
        cout << (dp[0][i] == (1ll << 62) ? -1 : dp[0][i]) << "\n";
    }
}