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
#include <cstdio>
#include <map>

using namespace std;

int c[7010][7010];
int poj[7010][7010];
int res[7010][7010];

int main()
{
    int n, kol, mas;

    scanf("%d %d %d", &n, &kol, &mas);

    map<int, int> kolo_map;
    int map_cnt = 0;

    for(int i = 0; i < n; i++)
    {
        int ki, mi, ci;
        scanf("%d %d %d", &ki, &mi, &ci);

        if(!kolo_map.contains(ki))
        {
            kolo_map[ki] = map_cnt;
            map_cnt++;
        }

        ki = kolo_map[ki];
        mi = mi % mas;

        if(c[ki][mi] == 0 || c[ki][mi] > ci) c[ki][mi] = ci;
    }

    for(int i = 0; i < mas; i++) poj[0][i] = c[0][i];

    for(int i = 0; i < kol - 1; i++)
    {
        for(int j = 0; j < mas; j++)
        {
            if(!poj[i][j]) continue;

            for(int k = 0; k < mas; k++)
            {
                if(!c[i + 1][k]) continue;

                int nowa_m = j + k;
                if(nowa_m > mas) nowa_m -= mas;

                if(poj[i + 1][nowa_m] == 0 || poj[i][j] + c[i + 1][k] < poj[i + 1][nowa_m]) poj[i + 1][nowa_m] = poj[i][j] + c[i + 1][k];
            }
        }
    }

    for(int i = 0; i < mas; i++) res[0][i] = poj[kol - 1][i];

    for(int i = 0; i < mas - 1; i++)
    {
        for(int j = 0; j < mas; j++)
        {
            if(!res[i][j]) continue;

            if(res[i + 1][j] == 0 || res[i][j] < res[i + 1][j]) res[i + 1][j] = res[i][j];

            for(int k = 0; k < mas; k++)
            {
                if(!res[0][k]) continue;

                int nowa_m = j + k;
                if(nowa_m > mas) nowa_m -= mas;

                if(res[i + 1][nowa_m] == 0 || res[i][j] + res[0][k] < res[i + 1][nowa_m]) res[i + 1][nowa_m] = res[i][j] + res[0][k];
            } 
        }
    }
    printf("0\n");
    for(int i = 1; i < mas; i++)
    {
        if(res[mas - 1][i]) printf("%d\n", res[mas - 1][i]);
        else printf("-1\n");
    }

    return 0;
}