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
80
81
82
83
84
85
86
87
88
89
90
#include <cstdio>
#include <cstdlib>
#include <cstdint>

#include <limits>
#include <vector>
#include <set>
#include <unordered_map>

struct jelly {
    uint64_t mass;
    uint64_t cost;
};

const uint64_t HUGE_NUMBER = std::numeric_limits<uint64_t>::max() / 2;

std::vector<uint64_t> fuse_jellies(const std::unordered_map<int, std::vector<jelly> >& jellies_by_color, int m) {
    std::vector<uint64_t> ret(m, HUGE_NUMBER);
    ret[0] = 0;

    std::vector<uint64_t> tmp(m);

    for (const auto& [color, jellies] : jellies_by_color) {
        for (int i = 0; i < m; i++) {
            uint64_t cheapest = HUGE_NUMBER;
            for (const auto& jelly : jellies) {
                cheapest = std::min(cheapest, ret[(i + m - jelly.mass) % m] + jelly.cost);
            }
            tmp[i] = cheapest;
        }
        std::swap(ret, tmp);
    }

    return ret;
}

int main() {
    int n, k, m;
    scanf("%d %d %d", &n, &k, &m);

    std::unordered_map<int, std::vector<jelly> > jellies_by_color;

    for (int i = 0; i < n; i++) {
        int kolor, mass, cost;
        scanf("%d %d %d", &kolor, &mass, &cost);
        jelly j;
        j.mass = mass;
        j.cost = cost;
        jellies_by_color[kolor - 1].push_back(j);
    }

    if (jellies_by_color.size() < k) {
        // Jellies of some colors are missing. We can only complete a set
        // for 0 jellies because of that. Handle this case here.
        puts("0");
        for (int i = 1; i < m; i++) {
            puts("-1");
        }
        return 0;
    }

    std::vector<uint64_t> fused = fuse_jellies(jellies_by_color, m);
    fused[0] = 0;

    std::set<std::pair<int, uint64_t> > que;
    for (int i = 1; i < m; i++) {
        que.insert(std::pair<int, uint64_t>(i, fused[i]));
    }

    while (!que.empty()) {
        auto it = que.begin();
        const auto [i, val] = *it;
        que.erase(it);
        for (int j = 1; j < m; j++) {
            uint64_t candidate = val + fused[j];
            int newi = (i + j) % m;
            if (fused[newi] > candidate) {
                que.erase(std::pair<int, uint64_t>(newi, fused[newi]));
                que.insert(std::pair<int, uint64_t>(newi, candidate));
                fused[newi] = candidate;
            }
        }
    };

    for (int i = 0; i < m; i++) {
        printf("%lld\n", (fused[i] == HUGE_NUMBER) ? -1LL : (long long int)fused[i]);
    }

    return 0;
}