// #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> // #include <x86intrin.h> using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif template<class T> T &ctmin(T &x){ return x; } template<class T, class Head, class ...Tail> T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min<T>(x, h), t...); } template<class T> T &ctmax(T &x){ return x; } template<class T, class Head, class ...Tail> T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max<T>(x, h), t...); } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int nt, nc, nw; cin >> nt >> nc >> nw; vector<vector<int>> value(nc, vector<int>(nw, numeric_limits<int>::max())); for(auto i = 0; i < nt; ++ i){ int c, w, v; cin >> c >> w >> v, -- c, w %= nw; ctmin(value[c][w], v); } vector<vector<int>> active_w(nc); for(auto c = 0; c < nc; ++ c){ for(auto w = 0; w < nw; ++ w){ if(value[c][w] != numeric_limits<int>::max()){ active_w[c].push_back(w); } } if(active_w[c].empty()){ cout << "0\n"; for(auto w = 1; w < nw; ++ w){ cout << "-1\n"; } return 0; } } const long long inf = numeric_limits<long long>::max() / 4; vector<long long> dp(nw, inf); for(auto w: active_w[0]){ ctmin(dp[w], value[0][w]); } auto reduce = [&](int wpref, int w)->int{ return wpref + w >= nw ? wpref + w - nw : wpref + w; }; for(auto c = 1; c < nc; ++ c){ static vector<long long> dp_next(nw); ranges::fill(dp_next, inf); for(auto wpref = 0; wpref < nw; ++ wpref){ if(dp[wpref] == inf){ continue; } for(auto w: active_w[c]){ ctmin(dp_next[reduce(wpref, w)], dp[wpref] + value[c][w]); } } swap(dp, dp_next); } vector<long long> res(nw, inf); res[0] = 0; for(auto w = 1; w < nw; ++ w){ for(auto wpref = 0; wpref < nw; ++ wpref){ ctmin(res[reduce(wpref, w)], res[wpref] + dp[w]); } for(auto wpref = 0; wpref < nw; ++ wpref){ ctmin(res[reduce(wpref, w)], res[wpref] + dp[w]); } } for(auto x: res){ if(x == inf){ x = -1; } cout << x << "\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 | // #pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> // #include <x86intrin.h> using namespace std; #if __cplusplus >= 202002L using namespace numbers; #endif template<class T> T &ctmin(T &x){ return x; } template<class T, class Head, class ...Tail> T &ctmin(T &x, const Head &h, const Tail &... t){ return ctmin(x = min<T>(x, h), t...); } template<class T> T &ctmax(T &x){ return x; } template<class T, class Head, class ...Tail> T &ctmax(T &x, const Head &h, const Tail &... t){ return ctmax(x = max<T>(x, h), t...); } int main(){ cin.tie(0)->sync_with_stdio(0); cin.exceptions(ios::badbit | ios::failbit); int nt, nc, nw; cin >> nt >> nc >> nw; vector<vector<int>> value(nc, vector<int>(nw, numeric_limits<int>::max())); for(auto i = 0; i < nt; ++ i){ int c, w, v; cin >> c >> w >> v, -- c, w %= nw; ctmin(value[c][w], v); } vector<vector<int>> active_w(nc); for(auto c = 0; c < nc; ++ c){ for(auto w = 0; w < nw; ++ w){ if(value[c][w] != numeric_limits<int>::max()){ active_w[c].push_back(w); } } if(active_w[c].empty()){ cout << "0\n"; for(auto w = 1; w < nw; ++ w){ cout << "-1\n"; } return 0; } } const long long inf = numeric_limits<long long>::max() / 4; vector<long long> dp(nw, inf); for(auto w: active_w[0]){ ctmin(dp[w], value[0][w]); } auto reduce = [&](int wpref, int w)->int{ return wpref + w >= nw ? wpref + w - nw : wpref + w; }; for(auto c = 1; c < nc; ++ c){ static vector<long long> dp_next(nw); ranges::fill(dp_next, inf); for(auto wpref = 0; wpref < nw; ++ wpref){ if(dp[wpref] == inf){ continue; } for(auto w: active_w[c]){ ctmin(dp_next[reduce(wpref, w)], dp[wpref] + value[c][w]); } } swap(dp, dp_next); } vector<long long> res(nw, inf); res[0] = 0; for(auto w = 1; w < nw; ++ w){ for(auto wpref = 0; wpref < nw; ++ wpref){ ctmin(res[reduce(wpref, w)], res[wpref] + dp[w]); } for(auto wpref = 0; wpref < nw; ++ wpref){ ctmin(res[reduce(wpref, w)], res[wpref] + dp[w]); } } for(auto x: res){ if(x == inf){ x = -1; } cout << x << "\n"; } return 0; } /* */ |