// // main.cpp // zel // // Created by Michal Kowalski on 14/03/2024. // #include <iostream> #include <vector> #include <queue> using namespace std; void generate_sets(int depth, vector<int> v); void find_solution(); void calc_price(vector<int> &t); void print_solution(); long long calculate_last_sum(); int N,K,M; vector<vector<int> > T(7005); vector<vector<int> > COL(7005); vector<vector<int> > COMB; int TABM[7005]; long long last_sum = (long long)7005*INT32_MAX; int main() { for (int i=0;i<7005;++i) TABM[i]=INT32_MAX; scanf("%d %d %d",&N,&K,&M); for (int i=0;i<N;++i) { int k,w,p; scanf("%d %d %d",&k,&w,&p); T[i] = {k,w,p}; COL[k].push_back(i); } generate_sets(0, {}); if (COMB.empty()) { TABM[0]=0; print_solution(); return 0; } find_solution(); print_solution(); return 0; } void generate_sets(int depth, vector<int> v) { if (depth == K) { COMB.push_back(v); } else { for(auto c: COL[depth+1]) { vector<int> t = v; t.push_back(c); generate_sets(depth+1, t); } } } void find_solution() { queue<vector<int>> Q; Q.push({}); int step = 1; bool finish = false; while(!finish) { vector<int> t = Q.front(); Q.pop(); calc_price(t); for (auto com: COMB) { vector<int> nt = t; // add for (auto x: com) nt.push_back(x); Q.push(nt); } ++step; /// check if output array changed if not finish if (step % 5000 == 0) { long long currentSum = calculate_last_sum(); if (currentSum == last_sum) { finish = true; } else { last_sum = currentSum; } } } } void calc_price(vector<int> &t) { int price = 0; int weight = 0; for(auto index: t) { price += T[index][2]; weight += T[index][1]; } int mindex = weight%M; TABM[mindex] = min(TABM[mindex], price); } void print_solution() { for(int i=0;i<M;++i) { printf("%d\n",TABM[i] == INT32_MAX ? -1 : TABM[i]); } } long long calculate_last_sum() { long long current = 0; for(int i=0;i<M;++i) { current = current + (long long) TABM[i]; } return current; }
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 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | // // main.cpp // zel // // Created by Michal Kowalski on 14/03/2024. // #include <iostream> #include <vector> #include <queue> using namespace std; void generate_sets(int depth, vector<int> v); void find_solution(); void calc_price(vector<int> &t); void print_solution(); long long calculate_last_sum(); int N,K,M; vector<vector<int> > T(7005); vector<vector<int> > COL(7005); vector<vector<int> > COMB; int TABM[7005]; long long last_sum = (long long)7005*INT32_MAX; int main() { for (int i=0;i<7005;++i) TABM[i]=INT32_MAX; scanf("%d %d %d",&N,&K,&M); for (int i=0;i<N;++i) { int k,w,p; scanf("%d %d %d",&k,&w,&p); T[i] = {k,w,p}; COL[k].push_back(i); } generate_sets(0, {}); if (COMB.empty()) { TABM[0]=0; print_solution(); return 0; } find_solution(); print_solution(); return 0; } void generate_sets(int depth, vector<int> v) { if (depth == K) { COMB.push_back(v); } else { for(auto c: COL[depth+1]) { vector<int> t = v; t.push_back(c); generate_sets(depth+1, t); } } } void find_solution() { queue<vector<int>> Q; Q.push({}); int step = 1; bool finish = false; while(!finish) { vector<int> t = Q.front(); Q.pop(); calc_price(t); for (auto com: COMB) { vector<int> nt = t; // add for (auto x: com) nt.push_back(x); Q.push(nt); } ++step; /// check if output array changed if not finish if (step % 5000 == 0) { long long currentSum = calculate_last_sum(); if (currentSum == last_sum) { finish = true; } else { last_sum = currentSum; } } } } void calc_price(vector<int> &t) { int price = 0; int weight = 0; for(auto index: t) { price += T[index][2]; weight += T[index][1]; } int mindex = weight%M; TABM[mindex] = min(TABM[mindex], price); } void print_solution() { for(int i=0;i<M;++i) { printf("%d\n",TABM[i] == INT32_MAX ? -1 : TABM[i]); } } long long calculate_last_sum() { long long current = 0; for(int i=0;i<M;++i) { current = current + (long long) TABM[i]; } return current; } |