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

struct zelek {
    int masa;
    long long cena;
};

std::vector<zelek> kolory[7001];

long long tablica[7001][7001];

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

    for (int i = 0; i < n; ++i) {
        std::cin >> K >> M >> C;
        kolory[K].push_back({ M,C });
    }

    for (int i = 0; i < kolory[1].size(); i++)
        if (tablica[1][kolory[1][i].masa % m] == 0 || tablica[1][kolory[1][i].masa % m] > kolory[1][i].cena)
            tablica[1][kolory[1][i].masa % m] = kolory[1][i].cena;

    for (int i = 2; i <= k; i++)
        for (int j = 0; j < kolory[i].size(); j++) 
            for (int l = 0; l < m; l++)
                if (tablica[i - 1][l] != 0 && (tablica[i][(kolory[i][j].masa + l) % m] > kolory[i][j].cena + tablica[i - 1][l] || tablica[i][(kolory[i][j].masa + l) % m] == 0))
                    tablica[i][(kolory[i][j].masa + l) % m] = kolory[i][j].cena + tablica[i-1][l];
    
    bool fafa;
    std::vector<int> v;
    std::set<std::pair<long long, int>> s;
    std::pair<long long, int> num;
    for (int i = 0; i < m; i++)
        if (tablica[k][i])
            v.push_back(i);

    for (int i = 0; i < v.size(); i++)
        for (int j = i; j < v.size(); j++)
            s.insert({ tablica[k][v[i]] + tablica[k][v[j]], (v[i] + v[j]) % m });
    
    for (auto itr = s.begin(); itr != s.end(); ++itr) {
        fafa = false;
        num = *itr;
        if (tablica[k][num.second] == 0) {
            v.push_back(num.second);
            fafa = true;
        }
        else if (num.first < tablica[k][num.second]) {
            for (int i = 0; i < v.size(); i++)
                s.erase({ tablica[k][num.second] + tablica[k][v[i]], (num.second + v[i]) % m });
            fafa = true;
        }
        if (fafa) {
            tablica[k][num.second] = num.first;
            for (int i = 0; i < v.size(); i++) {
                s.insert({ tablica[k][num.second] + tablica[k][v[i]], (num.second + v[i]) % m });
            }
        }
    }

    std::cout << 0;
    for (int i = 1; i < m; i++)
        if (tablica[k][i])
            std::cout << '\n' << tablica[k][i];
        else
            std::cout << '\n' << -1;
}