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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <iostream>
#include <vector>
#include <set>

using namespace std;

typedef int Kolor;
typedef int Masa;
typedef int Cena;
typedef long long int SumarycznaCena;
typedef unsigned int IndeksNaKolorze;

const int MAX_N = 7000;
const int MAX_K = 7000;
const long long int MILIARD = 1000000000L;
const long long int inf = MILIARD * MILIARD;

int N, K, M;

struct Zelka {
    Kolor kolor;
    Masa masa;
    Cena cena;
};

struct Uklad {
    vector<IndeksNaKolorze> kolor_to_indeks;
    Masa masa;
    SumarycznaCena cena;
};

struct Zaznaczenie {
    Kolor kolor;
    IndeksNaKolorze indeks;
};

vector<Zaznaczenie> zaznaczenia;

vector<vector<Zelka>> kolor_to_zelki;
vector<Uklad> uklady;

void przygotuj_zaznaczenia() {
    for (Kolor kolor = 0; kolor < K; kolor++) {
        const vector<Zelka>& zelki = kolor_to_zelki[kolor];
        if (zelki.size() <= 1)
            continue;
        for (IndeksNaKolorze i = 0; i < zelki.size(); ++i)
            zaznaczenia.push_back({kolor, i});
    }
}

IndeksNaKolorze wybierz_najtansza_zelke(const vector<Zelka>& zelki) {
    IndeksNaKolorze best_index = 0;
    Cena best_cena = zelki[0].cena;
    for (IndeksNaKolorze i = 1; i < zelki.size(); ++i) {
        if (best_cena > zelki[i].cena) {
            best_index = i;
            best_cena = zelki[i].cena;
        }
    }
    return best_index;
}

Uklad znajdz_najtanszy_uklad() {
    Masa masa_ukladu = 0;
    SumarycznaCena cena_ukladu = 0;
    vector<IndeksNaKolorze> kolor_to_indeks;

    for (Kolor kolor = 0; kolor < K; kolor++) {
        const vector<Zelka>& zelki = kolor_to_zelki[kolor];
        IndeksNaKolorze indeks = wybierz_najtansza_zelke(zelki);
        const Zelka& zelka = zelki[indeks];

        kolor_to_indeks.push_back(indeks);
        masa_ukladu = (masa_ukladu + zelka.masa) % M;
        cena_ukladu += zelka.cena;
    }

    return { kolor_to_indeks, masa_ukladu, cena_ukladu };
}

pair<Masa, SumarycznaCena> masa_i_cena_po_zmianie(const Uklad& u, Zaznaczenie z) {
    IndeksNaKolorze obecny_indeks_na_kolorze = u.kolor_to_indeks[z.kolor];
    const Zelka& obecna_zelka = kolor_to_zelki[z.kolor][obecny_indeks_na_kolorze];
    const Zelka& przyszla_zelka = kolor_to_zelki[z.kolor][z.indeks];

    Masa masa = (M + u.masa - obecna_zelka.masa + przyszla_zelka.masa) % M;
    SumarycznaCena cena = u.cena - obecna_zelka.cena + przyszla_zelka.cena;
    return pair<Masa, SumarycznaCena>(masa, cena);
}

void znajdz_najlepsze_uklady() {
    for (Masa r = 0; r < M; ++r) {
        uklady.push_back({{}, r, inf});
    }
    Uklad najtanszy_uklad = znajdz_najtanszy_uklad();
    uklady[najtanszy_uklad.masa] = najtanszy_uklad;
    set<Masa> poprawione = { najtanszy_uklad.masa };

    while (!poprawione.empty()) {
        Masa t = *poprawione.begin();
        poprawione.erase(poprawione.begin());

        const Uklad& u = uklady[t];
        for (Zaznaczenie z: zaznaczenia) {
            pair<Masa, SumarycznaCena> masa_i_cena = masa_i_cena_po_zmianie(u, z);
            Masa nowa_masa = masa_i_cena.first;
            SumarycznaCena nowa_cena = masa_i_cena.second;
            if (nowa_cena < uklady[nowa_masa].cena) {
                uklady[nowa_masa] = { u.kolor_to_indeks, nowa_masa, nowa_cena };
                uklady[nowa_masa].kolor_to_indeks[z.kolor] = z.indeks;
                poprawione.insert(nowa_masa);
            }
        }
    }
}

vector<SumarycznaCena> znajdz_rozwiazanie() {
    vector<SumarycznaCena> sol(M, inf);
    sol[0] = 0;
    for (const Uklad& u: uklady) {
        for (Masa masa_startowa = 0; masa_startowa < M; ++masa_startowa) {
            Masa t = masa_startowa;
            Masa next_t = (t + u.masa) % M;
            while (sol[next_t] > sol[t] + u.cena) {
                sol[next_t] = sol[t] + u.cena;
                t = next_t;
                next_t = (t + u.masa) % M;
            }
        }
    }
    return sol;
}

int main() {
    cin >> N >> K >> M;
    kolor_to_zelki = vector<vector<Zelka>>(K);
    for (int i = 0; i < N; ++i) {
        int ki, mi, ci;
        cin >> ki >> mi >> ci;
        ki--;
        kolor_to_zelki[ki].push_back({ki, mi % M, ci});
    }

    // obsluzmy przypadek gdy nie ma zelki w jakims kolorze
    for (const vector<Zelka>& zelki: kolor_to_zelki) {
        if (zelki.empty()) {
            cout << "0" << endl;
            for (Masa r = 1; r < M; ++r)
                cout << "-1" << endl;
            return 0;
        }
    }

    przygotuj_zaznaczenia();
    znajdz_najlepsze_uklady();
    const auto& sol = znajdz_rozwiazanie();

    for (Masa r = 0; r < M; ++r) {
        if (sol[r] >= inf) {
            cout << "-1" << endl;
        } else {
            cout << sol[r] << endl;
        }
    }

    return 0;
}