#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'; } } }
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'; } } } |