#include <bits/stdc++.h> #define ft first #define sc second #define pb push_back #define FOR(i,n) for(int i=0; i<n; i++) #define FORX(i,a,b) for(int i=(a); i<=(b); i++) #define watch(x) cerr << (#x) << " == " << (x) << endl typedef long long ll; typedef long double ld; using namespace std; ll m; ll pack[7007], new_pack[7007]; ll dp[7007], new_dp[7007]; bool vis[7007]; vector<pair<ll,ll>> candy[7007]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,k; cin>>n>>k>>m; FOR(i,n){ int col, mass, cost; cin>>col>>mass>>cost; candy[col].pb({mass%m,cost}); } FORX(i,1,k){ if (candy[i].empty()) { cout<<0<<"\n"; FORX(j,1,m-1){ cout<<-1<<"\n"; } return 0; } } fill(pack, pack+m+5, INT_MAX); fill(new_pack, new_pack+m+5, INT_MAX); pack[0] = 0; FORX(i,1,k) { FOR(j,m){ if (pack[j] == INT_MAX) continue; for (auto &p : candy[i]) { new_pack[(j+p.ft)%m] = min(new_pack[(j+p.ft)%m], pack[j]+p.sc); } } FOR(j,m){ pack[j] = new_pack[j]; new_pack[j] = INT_MAX; } } pack[0] = 0; fill(dp, dp+m+5, INT_MAX); fill(new_dp, new_dp+m+5, INT_MAX); dp[0] = 0; FOR(i,m){ pair<int,int> low = {INT_MAX, INT_MAX}; FOR(j,m){ if (!vis[j]) { low = min(low, {dp[j], j}); } } int pos = low.sc; int cost = low.ft; vis[pos] = 1; if (cost == INT_MAX) {break;} FORX(j,1,m-1) { if (pack[j] == INT_MAX) {continue;} dp[(pos+j)%m] = min(dp[(pos+j)%m], cost+pack[j]); } } FOR(i,m){ cout<<(dp[i] == INT_MAX ? -1 : dp[i])<<"\n"; } return 0; }
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 87 88 89 | #include <bits/stdc++.h> #define ft first #define sc second #define pb push_back #define FOR(i,n) for(int i=0; i<n; i++) #define FORX(i,a,b) for(int i=(a); i<=(b); i++) #define watch(x) cerr << (#x) << " == " << (x) << endl typedef long long ll; typedef long double ld; using namespace std; ll m; ll pack[7007], new_pack[7007]; ll dp[7007], new_dp[7007]; bool vis[7007]; vector<pair<ll,ll>> candy[7007]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n,k; cin>>n>>k>>m; FOR(i,n){ int col, mass, cost; cin>>col>>mass>>cost; candy[col].pb({mass%m,cost}); } FORX(i,1,k){ if (candy[i].empty()) { cout<<0<<"\n"; FORX(j,1,m-1){ cout<<-1<<"\n"; } return 0; } } fill(pack, pack+m+5, INT_MAX); fill(new_pack, new_pack+m+5, INT_MAX); pack[0] = 0; FORX(i,1,k) { FOR(j,m){ if (pack[j] == INT_MAX) continue; for (auto &p : candy[i]) { new_pack[(j+p.ft)%m] = min(new_pack[(j+p.ft)%m], pack[j]+p.sc); } } FOR(j,m){ pack[j] = new_pack[j]; new_pack[j] = INT_MAX; } } pack[0] = 0; fill(dp, dp+m+5, INT_MAX); fill(new_dp, new_dp+m+5, INT_MAX); dp[0] = 0; FOR(i,m){ pair<int,int> low = {INT_MAX, INT_MAX}; FOR(j,m){ if (!vis[j]) { low = min(low, {dp[j], j}); } } int pos = low.sc; int cost = low.ft; vis[pos] = 1; if (cost == INT_MAX) {break;} FORX(j,1,m-1) { if (pack[j] == INT_MAX) {continue;} dp[(pos+j)%m] = min(dp[(pos+j)%m], cost+pack[j]); } } FOR(i,m){ cout<<(dp[i] == INT_MAX ? -1 : dp[i])<<"\n"; } return 0; } |