結果
問題 | No.2429 Happiest Tabehodai Ways |
ユーザー |
|
提出日時 | 2023-08-18 23:09:34 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 783 bytes |
コンパイル時間 | 4,244 ms |
コンパイル使用メモリ | 257,252 KB |
最終ジャッジ日時 | 2025-02-16 10:39:47 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using mint = atcoder::modint998244353; using namespace std; int main() { int N, K; cin >> N >> K; vector<int> C(N), D(N); for (int i = 0; i < N; i++){ cin >> C[i]; } for (int i = 0; i < N; i++){ cin >> D[i]; } vector<pair<int, mint>> dp(K + 1); dp[0].second = 1; for (int i = 0; i < K; i++){ for (int j = 0; j < N; j++){ if (i + C[j] <= K){ int l = dp[i + C[j]].first, r = dp[i].first + D[j]; if (l < r){ dp[i + C[j]] = make_pair(r, dp[i].second); } else if (l == r){ dp[i + C[j]].second += dp[i].second; } } } } map<int, mint> m; int M = 0; for (int i = 0; i <= K; i++){ auto [k, v] = dp[i]; m[k] += v; M = max(M, k); } cout << M << '\n'; cout << m[M].val() << '\n'; }