結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;}