結果

問題 No.2429 Happiest Tabehodai Ways
ユーザー noya2noya2
提出日時 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0