結果

問題 No.2429 Happiest Tabehodai Ways
コンテスト
ユーザー noya2
提出日時 2023-08-12 00:27:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 1,080 bytes
コンパイル時間 1,950 ms
コンパイル使用メモリ 199,052 KB
最終ジャッジ日時 2025-02-16 02:32:04
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

int main(){
    int n, k; cin >> n >> k;
    vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    vector<pair<int,mint>> dp(k+1,{-1,0});
    dp[0] = {0,1};
    for (int s = 0; s < k; s++){
        for (int i = 0; i < n; i++){
            int ns = s + a[i];
            if (ns > k) continue;
            int val = dp[s].first + b[i];
            if (dp[ns].first > val) continue;
            if (dp[ns].first == val){
                dp[ns].second += dp[s].second;
            }
            else {
                dp[ns] = {val,dp[s].second};
            }
        }
    }
    int ma = 0;
    mint cnt = 0;
    for (int s = 0; s <= k; s++){
        if (dp[s].first < ma) continue;
        if (dp[s].first == ma){
            cnt += dp[s].second;
        }
        else {
            ma = dp[s].first;
            cnt = dp[s].second;
        }
    }
    cout << ma << endl;
    cout << cnt.val() << endl;
}
0