#include <bits/stdc++.h>
#define ndl '\n'
#define ll long long
#define INF 1000000007
#define st first
#define nd second
#define debug(x) cout << #x << ": " << x << ndl
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin(), (x).end()
using namespace std;
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
ll n,k,m; cin>>n>>k>>m;
vector<vector<pair<ll,ll>>> cuksy(k+1, vector<pair<ll,ll>>());
for(ll i=0;i<n;i++) {
ll a,b,c; cin>>a>>b>>c;
cuksy[a].push_back({b, c});
}
for(ll i=1;i<=k;i++) {
if(cuksy[i].size() == 0) {
cout<<0<<'\n';
for(ll j=1;j<m;j++)
cout<<-1<<'\n';
return 0;
}
}
vector<ll> mini_cena(m, -1), to_ale_ironicznie(m, -1);
for(auto [b, c]: cuksy[1])
if(to_ale_ironicznie[b%m] == -1 || to_ale_ironicznie[b%m] > c)
to_ale_ironicznie[b%m] = c;
for(ll ii = 2; ii<=k; ii++) {
for(ll j = 0; j<m; j++) {
mini_cena[j] = to_ale_ironicznie[j];
to_ale_ironicznie[j] = -1LL;
}
for(auto [b, c]: cuksy[ii]) {
for(ll j=0;j<m;j++) {
if(mini_cena[j] == -1) continue;
if(to_ale_ironicznie[(j + b)%m] == -1 || to_ale_ironicznie[(j + b)%m] > c + mini_cena[j]) {
to_ale_ironicznie[(j + b)%m] = c + mini_cena[j];
}
}
}
}
vector<pair<ll, ll>> mozliwosci;
for(ll i=1; i<m; i++) {
if(to_ale_ironicznie[i] != -1)
mozliwosci.push_back({i, to_ale_ironicznie[i]});
}
// for(auto [a,b]:mozliwosci)
// cout<<a<<" "<<b<<"\n";
vector<ll> dp(m, -1);
dp[0] = 0;
bool zm = 1;
while(zm){
zm = 0;
for(ll i=0;i<m;i++)
if(dp[i] != -1)
for(auto [b, c]: mozliwosci)
if(dp[(b+i)%m] == -1 || dp[(b+i)%m] > c + dp[i]) {
zm = 1;
dp[(b+i)%m] = c + dp[i];
}
}
for(auto x:dp) cout<<x<<"\n";
}
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 | #include <bits/stdc++.h> #define ndl '\n' #define ll long long #define INF 1000000007 #define st first #define nd second #define debug(x) cout << #x << ": " << x << ndl #define pb push_back #define pob pop_back #define pf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define all(x) (x).begin(), (x).end() using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); ll n,k,m; cin>>n>>k>>m; vector<vector<pair<ll,ll>>> cuksy(k+1, vector<pair<ll,ll>>()); for(ll i=0;i<n;i++) { ll a,b,c; cin>>a>>b>>c; cuksy[a].push_back({b, c}); } for(ll i=1;i<=k;i++) { if(cuksy[i].size() == 0) { cout<<0<<'\n'; for(ll j=1;j<m;j++) cout<<-1<<'\n'; return 0; } } vector<ll> mini_cena(m, -1), to_ale_ironicznie(m, -1); for(auto [b, c]: cuksy[1]) if(to_ale_ironicznie[b%m] == -1 || to_ale_ironicznie[b%m] > c) to_ale_ironicznie[b%m] = c; for(ll ii = 2; ii<=k; ii++) { for(ll j = 0; j<m; j++) { mini_cena[j] = to_ale_ironicznie[j]; to_ale_ironicznie[j] = -1LL; } for(auto [b, c]: cuksy[ii]) { for(ll j=0;j<m;j++) { if(mini_cena[j] == -1) continue; if(to_ale_ironicznie[(j + b)%m] == -1 || to_ale_ironicznie[(j + b)%m] > c + mini_cena[j]) { to_ale_ironicznie[(j + b)%m] = c + mini_cena[j]; } } } } vector<pair<ll, ll>> mozliwosci; for(ll i=1; i<m; i++) { if(to_ale_ironicznie[i] != -1) mozliwosci.push_back({i, to_ale_ironicznie[i]}); } // for(auto [a,b]:mozliwosci) // cout<<a<<" "<<b<<"\n"; vector<ll> dp(m, -1); dp[0] = 0; bool zm = 1; while(zm){ zm = 0; for(ll i=0;i<m;i++) if(dp[i] != -1) for(auto [b, c]: mozliwosci) if(dp[(b+i)%m] == -1 || dp[(b+i)%m] > c + dp[i]) { zm = 1; dp[(b+i)%m] = c + dp[i]; } } for(auto x:dp) cout<<x<<"\n"; } |
English