yukicoder / traP 作問ハッカソンコンテスト 001 / No.2429 Happiest Tabehodai Ways 別解

元の解説と同様に、以下のようにDPテーブルを定義します。
$\operatorname{DP}_h[i]=(満腹度がi以下のときの幸福度の最大値)$
$\operatorname{DP}_w[i]=(満腹度がi以下で幸福度が最大になるような料理の食べ方の個数)$
答えは、 $\operatorname{DP}_h[K]$ と $\operatorname{DP}_w[K]$ となります。
そして、以下のような漸化式を立てることができます。
$\operatorname{DP}_h[i]=\max(\{\operatorname{DP}_h[i-C[j]]+D[j]\ |\ 1\leq j\leq N,\ i\geq C[j]\}\cup\{0\})$
$\operatorname{DP}_w[i]=\max\{\sum_{\{j\ |\ 1\leq j\leq N,\ i\geq C[j],\ \operatorname{DP}_h[i]=\operatorname{DP}_h[i-C[j]]+D[j]\}}\operatorname{DP}_w[i-C[j]],1\}$
実装では、 $\operatorname{DP}_h[i]$ が更新されるときに $\operatorname{DP}_w[i]$ を $\operatorname{DP}_w[i-C[j]]$ に更新し、暫定の $\operatorname{DP}_h[i]$ と $\operatorname{DP}_h[i-C[j]]+D[j]$ が等しければ $\operatorname{DP}_w[i]$ に $\operatorname{DP}_w[i-C[j]]$ を足せばよいです。
時間計算量のオーダーは $\Theta(NK)$ となります。
以下はC++での実装例です。

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/modint>
using namespace atcoder;
using mint=modint998244353;

int main(void) {
    int n,k;
    cin >> n >> k;
    vector<int> c(n);
    vector<int> d(n);
    for(int i=0;i<n;++i){
        cin >> c[i];
    }
    for(int i=0;i<n;++i){
        cin >> d[i];
    }
    vector<int> dp1(k+1);
    vector<mint> dp2(k+1);
    dp2[0]=1;
    for(int i=1;i<=k;++i){
        dp2[i]=1;
        for(int j=0;j<n;++j){
            if(i>=c[j]){
                if(dp1[i]<dp1[i-c[j]]+d[j]){
                    dp1[i]=dp1[i-c[j]]+d[j];
                    dp2[i]=dp2[i-c[j]];
                } else if(dp1[i]==dp1[i-c[j]]+d[j]){
                    dp1[i]=dp1[i-c[j]]+d[j];
                    dp2[i]+=dp2[i-c[j]];
                }
            }
        }
    }
    cout << dp1[k] << endl;
    cout << dp2[k].val() << endl;
    return 0;
}