結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
![]() |
提出日時 | 2023-08-18 23:48:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 605 ms / 2,000 ms |
コード長 | 1,449 bytes |
コンパイル時間 | 963 ms |
コンパイル使用メモリ | 87,088 KB |
実行使用メモリ | 15,232 KB |
最終ジャッジ日時 | 2024-06-12 08:02:56 |
合計ジャッジ時間 | 4,687 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <map>#include <set>#include <queue>using namespace std;using ll = long long;using P = pair<int, int>;constexpr ll MOD = 998244353;int main(){int n, k; cin >> n >> k;vector<int> c(n), d(n);for(auto &it: c) cin >> it;for(auto &it: d) cin >> it;vector<vector<int>> dp(k+10, vector<int>(k+10, -(1 << 30)));vector<vector<ll>> cnt(k+10, vector<ll>(k+10, 0));dp[0][0] = 0;cnt[0][0] = 1;for(int i = 0; i <= k; i++){for(int j = 0; j <= k; j++){if(cnt[i][j] == 0) continue;for(int l = 0; l < n; l++){if(k < j+c[l]) continue;if(dp[i+1][j+c[l]] < dp[i][j]+d[l]){dp[i+1][j+c[l]] = dp[i][j]+d[l];cnt[i+1][j+c[l]] = cnt[i][j];}else if(dp[i+1][j+c[l]] == dp[i][j]+d[l]){cnt[i+1][j+c[l]] = (cnt[i+1][j+c[l]]+cnt[i][j])%MOD;}}}}int maxc = 0;for(int i = 0; i <= k; i++){for(int j = 0; j <= k; j++){maxc = max(dp[i][j], maxc);}}ll ans = 0;for(int i = 0; i <= k; i++){for(int j = 0; j <= k; j++){if(dp[i][j] == maxc){ans = (ans+cnt[i][j])%MOD;}}}cout << maxc << endl;cout << ans << endl;return 0;}