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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include<bits/stdc++.h>
#include <unistd.h>

using namespace std;
#ifdef DEBUG
#define _log 1
#else
#define _log 0
#endif

#ifdef STAT
#define _stat 1
#else
#define _stat 0
#endif

int n, m, k;
const long MAXC = LONG_MAX/3;
struct Jelly{
    long m, c; //mass, color
};
struct Jump{
    long cost;
    int size;
};
long total_jumps = 0;
long rejected_jumps = 0;

vector<vector<Jelly>> jellies;
vector<long> results;

vector<Jump> jumps;
priority_queue<pair<long, int>, vector<pair<long, int>>, greater<pair<long, int>>> jumps_queue;

void print_results(string del = " "){
    for(int i = 0; i < m; ++i){
        cout<<(results[i] == MAXC ? -1 : results[i])<<del;
    }
    cout<<"\n";
}

void add_jumps(int poz){
    // add all possible jumps from this position
    for(auto j : jumps){
        if(results[(poz + j.size) % m] > results[poz] + j.cost){
            jumps_queue.push({results[poz] + j.cost, (poz + j.size) % m}); // new cost, new position
        }
    }
}

void jump(){
    while(!jumps_queue.empty()){
        auto j = jumps_queue.top();
        jumps_queue.pop();
        if(j.first < results[j.second]){
            total_jumps++;
            results[j.second] = j.first;
            add_jumps(j.second);
            if constexpr (_log)print_results();
        }else{
            rejected_jumps++;
        }
    }
}

int main(){
	ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    cin>>n>>k>>m;
    //n - number of jellies
    //k - number of colors

    jellies.assign(k + 1, vector<Jelly>());
    results.assign(m, MAXC);

    for(int i = 0, k; i < n; ++i){
        Jelly j;
        cin>>k>>j.m>>j.c;
        jellies[k].push_back(j);
    }

    vector<vector<long>> dp(k + 1, vector<long>(m, MAXC));
    dp[0][0] = 0;
    for(int i = 1; i <= k; ++i){
        for(int j = 0; j < m; ++j){
            for(auto jell : jellies[i]){
                dp[i][j] = min(dp[i][j], min(dp[i-1][(j - jell.m + m) % m] + jell.c, MAXC));
                // cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<" | "<<i-1<<" "<<(j - jell.m + m) % m<<" | "<<dp[i-1][(j - jell.m + m) % m]<<" + "<<jell.c<<" | jell.m: "<<jell.m<<"\n";
            }
        }
    }

    results[0] = 0; // we always can buy 0 jellies
    for(int i = 1; i < m; ++i){
        results[i] = dp[k][i];
        if(dp[k][i] != MAXC){
            jumps.push_back({dp[k][i], i}); // add new jump
        }
    }

    for(int i = 0; i < m; ++i){
        add_jumps(i);
    }
    
    if constexpr (_log) print_results();
    jump();
    if constexpr (_stat) cout<<"Total jumps: "<<total_jumps<<" | Rejected jumps: "<<rejected_jumps<<"\n";
    print_results("\n");

	return 0;
}