結果
問題 |
No.2866 yuusaan's Knapsack
|
ユーザー |
![]() |
提出日時 | 2024-08-31 00:22:57 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,490 bytes |
コンパイル時間 | 4,220 ms |
コンパイル使用メモリ | 255,088 KB |
最終ジャッジ日時 | 2025-02-24 03:27:27 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 25 WA * 1 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using lint = long long; using mint = atcoder::modint998244353; lint INF = 2000000000; int main() { int n, W; cin >> n >> W; vector<lint> v(n), w(n); for (int i = 0; i < n; i++) { cin >> v[i] >> w[i]; } vector<vector<pair<lint, mint>>> dp(n + 1, vector<pair<lint, mint>>(20010, {-INF, 0})); dp[0][10000] = {0, 1}; for (int i = 1; i <= n; i++) { for (int j = 0; j < 20010; j++) { if (dp[i - 1][j].first > dp[i][j].first) { dp[i][j] = dp[i - 1][j]; } else if (dp[i - 1][j].first == dp[i][j].first) { dp[i][j].second += dp[i - 1][j].second; } if (0 <= j - w[i - 1] && j - w[i - 1] < 20010) { if (dp[i - 1][j - w[i - 1]].first + v[i - 1] > dp[i][j].first) { dp[i][j] = {dp[i - 1][j - w[i - 1]].first + v[i - 1], dp[i - 1][j - w[i - 1]].second}; } else if (dp[i - 1][j - w[i - 1]].first + v[i - 1] == dp[i][j].first) { dp[i][j].second += dp[i - 1][j - w[i - 1]].second; } } } } lint val = -INF; for (int j = 0; j <= W + 10000; j++) { val = max(val, dp[n][j].first); } mint ans = 0; for (int j = 0; j <= W + 10000; j++) { if (dp[n][j].first == val) { ans += dp[n][j].second; } } cout << val << " " << ans.val() << endl; }