解法
貨幣の枚数を考える. 組(金貨,銀貨,銅貨) が辞書順で最大になるのがベスト. 銅貨の残り枚数を状態にもって DP すれば O(NX).
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
pll operator + (pll a, pll b){
return make_pair(a.first + b.first, a.second + b.second);
}
int main() {
ll n,x;
cin >> n >> x;
vll a(n), b(n), c(n);
rep(i,n){
cin >> a[i] >> b[i] >> c[i];
}
// r: remainder bronze
dp[x] = {0,(ll)1e9};
rep(i,n) {
rep(br,x+1){
if(br - b[i] >= 0) chmax(dp[br - b[i]], dp[br] + make_pair(c[i], -a[i]));
}
}
tuple<ll,ll,ll> ans(-1,-1,-1);
rep(br,x+1){ // get bronze
auto [g,s] = dp[br]; // get gold, get silver
chmax(ans, make_tuple(g, s, br));
}
auto [p,q,r] = ans;
cout << p << " " << q << " " << r << endl;
return 0;
}