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 <bits/stdc++.h>
using namespace std;
int n, k, m;
pair <int, pair< int, int> > tab[7001];
int kolory[7001];
long long wyniki[7001], inf = 9223372036854775807;
long long ceny[7001][7001];
void wypisz();
int main() {
	ios_base::sync_with_stdio(0); cin.tie();cout.tie();
	int i, j, wielokrotnosc, wiersze = 1;
	cin >> n >> k >> m;
    for(i = 0; i < n; i++) {
        cin >> tab[i].first >> tab[i].second.first >> tab[i].second.second;
        kolory[tab[i].first] = 1;
    }
    for(i = 1; i <= k;i++) if (kolory[i] == 0) {
        cout << 0 << endl;
        for(j = 1; j < m; j++) cout << -1 <<endl;
        return 0;
    }
    sort(tab,tab + n);
    for(i = n; i > 0; i--) {tab[i].first = tab[i-1].first;
        tab[i].second.first = tab[i-1].second.first;
        tab[i].second.second = tab[i-1].second.second;}
    //tab[i].first - kolor
    //tab[i].second.first - masa
    //tab[i].second.second - cena

    for(i = 1; i < m; i++) wyniki[i] = inf;
    for(i = 0; i < m*m; i++)
        for(j= 0; j < m*m; j++) ceny[i][j] = inf;
    ceny[0][0] = 0;
    for(wielokrotnosc = 1; wielokrotnosc <= k*k; wielokrotnosc++){
    	wiersze = 1;
        for(i = 1; i <= k; i++) {//wiersze
            while(tab[wiersze].first == i){
                for(j = 0; j < m * m ; j++){
                    if(ceny[i-1][j]!= inf ) {
                        ceny[i][j+ tab[wiersze].second.first]=min(ceny[i][j+ tab[wiersze].second.first], ceny[i-1][j] + tab[wiersze].second.second);
                    }
                    //cout <<ceny[i][j] <<" ";
                }
                //cout << endl;
                wiersze++;
            }

        //wypisz();
        }
        for(j = 1; j < m*m;j++) ceny[0][j] = ceny[k][j];
        for(j = 1; j < m * m  ; j++) wyniki[j%m] = min(wyniki[j%m],ceny[k][j]);
    }

    wypisz();

	return 0;
}

void wypisz(){
    for(int i = 0; i < m;i++) cout << wyniki[i] <<  endl;
}