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
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,k,m;
    cin>>n>>k>>m;
    vector <pair <ll, pair <ll,ll> > > v(n);
    for(ll i=0;i<n;i++) {
        cin>>v[i].first>>v[i].second.first>>v[i].second.second;
    }
    sort(v.begin(),v.end());
    vector <vector <ll> > dp(k+2,vector <ll> (m+2,1e15));
    ll x=0;
    while(v[x].first==1) {
        dp[1][(v[x].second.first)%m]=min(dp[1][(v[x].second.first)%m], v[x].second.second);
        x++;
    }
    /*for(ll i=0;i<m;i++) {
        cout<<dp[1][i]<<" ";
    }
    cout<<"\n";*/
    for(ll i=x;i<n; ) {
        ll q=v[i].first;
        while(i<n && v[i].first==q) {
            for(ll j=0;j<m;j++) {
                ll dest=(j+v[i].second.first)%m;
                dp[q][dest]=min(dp[q][dest], dp[q-1][j]+v[i].second.second);
            }
            i++;
        }
    }
    /*for(ll i=1;i<k;i++) {
        for(ll j=0;j<m;j++) {
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }*/
    vector <pair <ll,ll> > pom;
    pom.reserve(m);
    for(ll i=1;i<m;i++) {
        //cout<<dp[k][i]<<" ";
        if(dp[k][i]!=1e15) {
            pom.push_back({dp[k][i],i});
        }
    }
    sort(pom.begin(),pom.end());
    vector <ll> wynik(m, 1e15);
    wynik[0]=0;
    for(ll i=0;i<pom.size();i++) {
        vector <ll> vis(m,0);
        //cout<<pom[i].first<<" "<<pom[i].second<<"\n";
        for(ll j=0;j<m;j++) {
            if(wynik[j]!=1e15&&vis[j]==0) {
                ll start=j;
                ll x=start;
                vis[start]=1;
                bool pocz=1;
                while(x!=start||pocz==1) {
                    if(wynik[x]+pom[i].first<wynik[(x+pom[i].second)%m]) {
                        wynik[(x+pom[i].second)%m]=wynik[x]+pom[i].first;
                        x=(x+pom[i].second)%m;
                        pocz=0;
                        vis[x]=1;
                    }
                    else break;
                }
            }
        }
    }
    for(ll i=0;i<m;i++) {
        if(wynik[i]==1e15) {
            wynik[i]=-1;
        }
        cout<<wynik[i]<<"\n";
    }
    return 0;
}