結果
問題 |
No.2866 yuusaan's Knapsack
|
ユーザー |
|
提出日時 | 2024-09-01 07:36:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,162 bytes |
コンパイル時間 | 3,893 ms |
コンパイル使用メモリ | 257,436 KB |
最終ジャッジ日時 | 2025-02-24 03:39:25 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using mint = atcoder::modint998244353; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, W; cin >> n >> W; W += 10000; vector<pair<int,int>> a(n); for(auto &&[v, w] : a){ cin >> v >> w; swap(v, w); } sort(a.begin(), a.end()); const int r = max(10000, W); vector<mint> dp1(r + 1); vector<int> dp2(r + 1, -(1 << 30)); dp1[10000] = 1; dp2[10000] = 0; for(auto &&[w, v] : a){ if(w >= 0){ for(int j = r - w; j >= 0; j--){ const int v2 = dp2[j] + v; const int to = j + w; if(dp2[to] == v2){ dp1[to] += dp1[j]; }else if(dp2[to] < v2){ dp2[to] = v2; dp1[to] = dp1[j]; } } }else{ for(int j = -w; j <= r; j++){ const int v2 = dp2[j] + v; const int to = j + w; if(dp2[to] == v2){ dp1[to] += dp1[j]; }else if(dp2[to] < v2){ dp2[to] = v2; dp1[to] = dp1[j]; } } } } int mx = -(1 << 30); for(int i = 0; i <= W; i++){ if(dp2[i] > mx) mx = dp2[i]; } mint ans; for(int i = 0; i <= W; i++) if(dp2[i] == mx) ans += dp1[i]; cout << mx << ' ' << ans.val() << '\n'; }