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
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> v[7005];
const long long inf = 1e14 + 105;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int a, k, m;
    cin>>a>>k>>m;
    for(int x = 1; x <= a; x++)
    {
        int c, d, e;
        cin>>c>>d>>e;
        v[c].push_back(make_pair(d, e));
    }
    vector<long long> dp(m, inf);
    dp[0] = 0;
    for(int x = 1; x <= k; x++)
    {
        vector<vector<long long>> new_dps;
        for(auto p : v[x])
        {
            auto dp2 = vector<long long>(m);
            for(int i = 0; i < m; i++)
                dp2[(i + p.first) % m] = dp[i] + p.second;
            new_dps.push_back(dp2);
        }
        vector<long long> act(m, inf);
        for(int j = 0; j < new_dps.size(); j++)
            for(int i = 0; i < m; i++)
                act[i] = min(act[i], new_dps[j][i]);
        dp = act;
    }
    vector<long long> res(m, inf);
    res[0] = 0;
    for(int i = 1; i < m; i++)
    {
        long long val = dp[i];
        vector<int> odw(m, 0);
        for(int j = 0; j < m; j++)
        {
            int act = j;
            while(odw[act] < 2)
            {
                odw[act]++;
                int new_act = (act + i) % m;
                res[new_act] = min(res[new_act], res[act] + val);
                act = new_act;
            }
        }

    }
    for(auto x : res)
    {
        if(x == inf)
            cout<<"-1\n";
        else
            cout<<x<<'\n';
    }
    return 0;
}