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
#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

ll dp1[7100][7100];
vector<int> tab[7100];
ll dp2[7100][2];

vector<pair<int,pair<int,ll>>> V;

int main()
{   
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,k,m;
    cin>>n>>k>>m;
    for(int i = 0 ;i < n ;i ++)
    {
        int kolor,waga,cena;
        cin>>kolor>>waga>>cena;
        V.push_back({kolor,{waga,cena}});
    }
    sort(V.begin(),V.end());
    tab[0].push_back(0);
    for(auto I : V)
    {
        int kolor=I.first,waga=I.second.first,cena=I.second.second;
        for(auto J : tab[kolor-1])
        {
            if(dp1[(J+waga)%m][kolor]==0){
                tab[kolor].push_back((J+waga)%m);
                dp1[(J+waga)%m][kolor]=dp1[J][kolor-1]+cena;
            }
            else
            {
                dp1[(J+waga)%m][kolor]=min(dp1[(J+waga)%m][kolor],dp1[J][kolor-1]+cena);
            }
        }
    }
    for(int i = 1; i< m ;i ++)
    {
        dp2[i][0]=-1;
        dp2[i][1]=-1;
    }
    vector<int> indstartowe,indnowe,indnowe2;
    for(int i = 1 ; i <m ;i ++){
        if(dp1[i][k]>0)
        {
            dp2[i][0]=dp1[i][k];
            dp2[i][1]=dp1[i][k];
            indnowe.push_back(i);
            indstartowe.push_back(i);
        }
    }
    while(!indnowe.empty())
    {
        for(auto I : indnowe)
        {
            for(auto J : indstartowe){
                if(dp2[(I+J)%m][1]==-1||dp2[(I+J)%m][1]>dp2[I][0]+dp2[J][0])
                {
                    dp2[(I+J)%m][1]=dp2[I][0]+dp2[J][0];
                    indnowe2.push_back((I+J)%m);
                }
            }
        }
        indnowe.clear();
        for(auto I : indnowe2)
        {
            if(dp2[I][1]!=dp2[I][0])
            {
                dp2[I][0]=dp2[I][1];
                indnowe.push_back(I);
            }
        }
        indnowe2.clear();
    }
    for(int i = 0 ;i < m ;i ++)
        cout<<dp2[i][0]<<'\n';

}