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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>

using ll = unsigned long long;

int n, k, m;
int K[7001], M[7001];
ll C[7001];
ll INF = std::numeric_limits<ll>::max() / 2;
std::vector<int> color_list[7001];

void read(){ 
    std::cin >> n >> k >> m;
    for(int i = 0; i < n; i++) {
        std::cin >> K[i] >> M[i] >> C[i];
        color_list[K[i]].push_back(i);
    }
}

void solve() {
    std::vector<ll> old_single(m, INF);
    old_single[0] = 0;
    for(int color = 1; color <= k; color++) {
        std::vector<ll> new_single(m, INF);
        for(int r = 0; r < m; r++) {
            if(old_single[r] == INF)
                continue;
            for(int candy : color_list[color]) {
                new_single[(r + M[candy]) % m] = std::min(new_single[(r + M[candy]) % m], old_single[r] + C[candy]);
            }
        }
        old_single = new_single;
    }
    /*
    std::cerr << "old_single:\t";
    for(int r = 0; r < m; r++) {
        std::cerr << old_single[r] << " ";
    }
    std::cerr << "\n";
    */
    std::vector<ll> multiple0(m), multiple1(m);
    multiple0 = old_single;
    multiple0[0] = 0;
    for(int iters = 0; ; iters++) {
        multiple1 = std::vector<ll>(m, INF);
        /*
        for(int x = 0; x < m; x++) {
            for(int r = 0; r < m; r++) {
                multiple1[r] = std::min(multiple1[r], multiple0[x] + multiple0[(m + r - x) % m]);
            }
        }
        */
        multiple0.insert(multiple0.end(), multiple0.begin(), multiple0.end());
        multiple1 = std::vector<ll>(m, INF);
        for(int x = 0; x < m; x++) {
            for(int r = 0; r < m; r++) {
                multiple1[r] = std::min(multiple1[r], multiple0[x] + multiple0[m + r - x]);
            }
        }
        multiple0.resize(m);
        
        if(multiple0 == multiple1) {
            //std::cerr << "iters = " << iters << "\n";
            break;
        } else {
            multiple0 = multiple1;
        }
    }
    for(int r = 0; r < m; r++) {
        if(multiple0[r] == INF)
            std::cout << "-1\n";
        else
            std::cout << multiple0[r] << "\n";
    }
}

int main() {
    read();
    solve();
}