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
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
int main() {
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int n, k, m, x;
	std::cin >> n >> k >> m;
	std::vector<std::vector<std::pair<int, long long>>> w(k);
	{
		std::pair<int, long long> h;
		for (int i = 0; i < n; i++) {
			std::cin >> x >> h.first >> h.second; x--;
			w[x].push_back(h);
		}
	}
	std::vector<std::vector<long long>> h;
	h.resize(k + 1, std::vector<long long>(m));
	h[0][0] = 1;
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < w[i].size(); j++) {
			for (int ii = 0; ii < m; ii++) {
				if (h[i][ii] != 0) {
					if (h[i + 1][(ii + w[i][j].first) % m] != 0)
						h[i + 1][(ii + w[i][j].first) % m] = std::min(h[i][ii] + w[i][j].second, h[i + 1][(ii + w[i][j].first) % m]);
					else h[i + 1][(ii + w[i][j].first) % m] = h[i][ii] + w[i][j].second;

				}
			}
		}
	}
	h[0][0] = 0;
	std::vector<std::pair<long long, int>> res;
	std::set<std::pair<long long, int>> s;
	std::set<std::pair<long long, int>>::iterator itr;
	s.insert({ 0, 0 });
	h[h.size() - 1][0] = 0;
	for (int i = 1; i < m; i++) {
		h[h.size() - 1][i]--;
		if (h[h.size() - 1][i] != -1) {
			res.push_back({ h[h.size() - 1][i], i });
		}
		else h[h.size() - 1][i] = INT64_MAX;
	}
	std::sort(res.begin(), res.end());
	for (int j = 0; j < m; j++) {
		s.insert({ h[h.size() - 1][j], j });
	}
	for (int i = 0; i < res.size(); i++) {
		for (itr = s.begin(); itr != s.end(); itr++) {
			if ((*itr).first == INT64_MAX) {
				break;
			}
			if (h[h.size() - 1][((*itr).second + res[i].second) % m] > (*itr).first + res[i].first) {
				s.erase(s.find({ h[h.size() - 1][((*itr).second + res[i].second) % m], ((*itr).second + res[i].second) % m }));
				s.insert({ (*itr).first + res[i].first,((*itr).second + res[i].second) % m });
				h[h.size() - 1][((*itr).second + res[i].second) % m] = (*itr).first + res[i].first;
			}
		}

	}
	for (int i = 0; i < m; i++) {
		if (h[h.size() - 1][i] == INT64_MAX)
			std::cout << "-1\n";
		else {
			std::cout << h[h.size() - 1][i] << "\n";
		}
	}
	return 0;

}