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
//Solution by Mikołaj Kołek

#include "bits/stdc++.h"

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int n, k, m;
	cin >> n >> k >> m;
	vector<vector<pair<int, int>>> colors(k);
	for(int i = 0; i < n; i++) {
		int color, mass, cost;
		cin >> color >> mass >> cost;
		colors[color - 1].push_back({ mass, cost });
	}
	
	for(int i = 0; i < k; i++) {
		if(colors[i].empty()) {
			cout << "0\n";
			
			for(int i = 0; i < m - 1; i++)
				cout << "-1\n";
			
			return 0;
		}
	}
	
	vector<long long> minCosts(m, 1e18);
	minCosts[0] = 0;
	for(const auto &jellies : colors) {
		vector<long long> newMinCosts(m, 1e18);
		
		for(const auto &[mass, cost] : jellies)
			for(int i = 0; i < m; i++)
				if(minCosts[i] < 1e18)
					newMinCosts[(i + mass) % m] = min(newMinCosts[(i + mass) % m], minCosts[i] + cost);
		
		minCosts = newMinCosts;
	}
	
	vector<long long> res(m, 1e18);
	res[0] = 0;
	for(int pos = 0; pos < m; pos++) {
		if(minCosts[pos] >= 1e18)
			continue;
		
		vector<int> vis(m, 0);
		for(int i = 0; i < m; i++) {
			if(vis[i] >= 2)
				continue;
			
			for(int j = i + pos; vis[j] < 2; j = (j + pos) % m) {
				res[j] = min(res[j], res[(j - pos + m) % m] + minCosts[pos]);
				vis[j]++;
			}
		}
	}
	
	for(int i = 0; i < m; i++)
		cout << (res[i] >= 1e18 ? -1 : res[i]) << "\n";
	
	return 0;
}