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
// [3B] Zelki, Kamil Debowski
#include <bits/stdc++.h>
using namespace std;

long long INF = 4e18L + 5;

void mini(long long& a, long long b) {
	a = min(a, b);
}

int main() {
	int n, k, m;
	cin >> n >> k >> m; // input size; color count; modulo
	vector<vector<pair<int,int>>> ofColor(k+1);
	for (int i = 0; i < n; i++) {
		int color, weight, price;
		cin >> color >> weight >> price;
		ofColor[color].emplace_back(weight % m, price);
	}
	vector<long long> dp(m, INF);
	dp[0] = 0;
	// dp[weight] = min total cost
	for (int color = 1; color <= k; color++) {
		vector<long long> new_dp(m, INF);
		for (pair<int,int> p : ofColor[color]) {
			int weight = p.first;
			int price = p.second;
			for (int w = 0; w < m; w++) {
				int sum = w + weight;
				if (sum >= m) sum -= m;
				mini(new_dp[sum], dp[w] + price);
			}
		}
		dp = new_dp;
	}
	dp[0] = 0;
	vector<bool> visited(m);
	set<pair<long long, int>> s;
	for (int i = 0; i < m; i++) {
		if (dp[i] < INF) {
			s.insert({dp[i], i});
		}
	}
	while (!s.empty()) {
		int a = s.begin()->second;
		s.erase(s.begin());
		visited[a] = true;
		for (int b = 0; b < m; b++) {
			if (visited[b]) {
				long long total = dp[a] + dp[b];
				int sum = a + b;
				if (sum >= m) sum -= m;
				if (total < dp[sum]) {
					s.erase({dp[sum], sum});
					dp[sum] = total;
					s.insert({dp[sum], sum});
				}
			}
		}
	}
	for (int i = 0; i < m; i++) {
		if (dp[i] == INF) {
			dp[i] = -1;
		}
		cout << dp[i] << "\n";
	}
}