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

struct p{
    short int col;
    short int mass;
    int cost;
};

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    int n, k, m;
    std::cin>>n>>k>>m;
    p t[n];
    std::vector<std::pair<int,int> > by_col[k+1];//masz cost
    for (size_t i=0; i<n; ++i){
        std::cin>>t[i].col>>t[i].mass>>t[i].cost;
        by_col[t[i].col].emplace_back(t[i].mass,t[i].cost);
    }
    long long plecak[2][m];
    for (size_t j=0; j<m; ++j){
        plecak[0][j]=std::numeric_limits<long long>::max();
        plecak[1][j]=std::numeric_limits<long long>::max();
    }
    for (int i=1; i<=k; ++i){
        for (size_t j=0; j<m; ++j)plecak[i%2][j]=std::numeric_limits<long long>::max();
        if (i==1){
            plecak[(i+1)%2][0]=0;
        }
        for (size_t j=0; j<m; ++j){
            long long v=plecak[(i+1)%2][j];
            if (v==std::numeric_limits<long long>::max())continue;
            for (auto a:by_col[i])plecak[i%2][(j+a.first)%m]=std::min(plecak[i%2][(j+a.first)%m],v+a.second);
        }
        //for (size_t j=0; j<m; ++j)std::cout<<plecak[i%2][j]<<' ';
        //std::cout<<'\n';
    }
    std::vector<std::pair<long long,long long> > block;//masa, koszt
    for (int j=0; j<m; ++j){
        if (plecak[k%2][j]!=std::numeric_limits<long long>::max())block.emplace_back(j,plecak[k%2][j]);
    }
    //for (auto a:block)std::cout<<a.first<<' '<<a.second<<'\n';
    //return 0;
    long long res[m];
    res[0]=0;
    for (size_t i=1; i<m; ++i)res[i]=std::numeric_limits<long long>::max();
    for (auto a:block){
        for (size_t i=1; i<m; ++i){
            res[(a.first*i)%m]=std::min(res[(a.first*i)%m],{a.second*i});
        }
    }//multiple
    long long res2[m];
    res2[0]=0;
    for (size_t i=1; i<m; ++i)res2[i]=std::numeric_limits<long long>::max();
    std::vector<std::pair<long long, int> > tmp;
    for (size_t i=1; i<m; ++i){
        if (res[i]!=std::numeric_limits<long long>::max())tmp.emplace_back(res[i],i);
    }
    std::sort(tmp.begin(), tmp.end());
    for (auto a:tmp){
        for (size_t i=0; i<m; ++i){
            if (res2[i]!=std::numeric_limits<long long>::max()){
                res2[(i+a.second)%m]=std::min(res2[(i+a.second)%m],res2[i]+a.first);
            }
        }
    }

    /*for (size_t x=0; x<=5; ++x){
    for (size_t i=0; i<m; ++i){
        for (size_t j=1; j<m; ++j){
            if (res[j]!=std::numeric_limits<long long>::max() and res2[i]!=std::numeric_limits<long long>::max())
                res2[(i+j)%m]=std::min(res2[(i+j)%m],res2[i]+res[j]);
        }
    }
    }*/
    for (size_t i=0; i<m; ++i){
        if (res2[i]==std::numeric_limits<long long>::max()){
            std::cout<<-1<<'\n';
        }else{
            std::cout<<res2[i]<<'\n';
        }
    }
}