結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー | Today03 |
提出日時 | 2024-08-30 22:15:40 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 50 ms / 2,000 ms |
コード長 | 1,830 bytes |
コンパイル時間 | 2,874 ms |
コンパイル使用メモリ | 260,732 KB |
実行使用メモリ | 36,836 KB |
最終ジャッジ日時 | 2024-08-31 01:28:20 |
合計ジャッジ時間 | 4,442 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 4 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 39 ms
28,636 KB |
testcase_07 | AC | 32 ms
23,040 KB |
testcase_08 | AC | 43 ms
30,720 KB |
testcase_09 | AC | 40 ms
29,568 KB |
testcase_10 | AC | 35 ms
25,088 KB |
testcase_11 | AC | 34 ms
25,568 KB |
testcase_12 | AC | 39 ms
28,472 KB |
testcase_13 | AC | 37 ms
27,620 KB |
testcase_14 | AC | 33 ms
25,296 KB |
testcase_15 | AC | 36 ms
26,112 KB |
testcase_16 | AC | 32 ms
22,780 KB |
testcase_17 | AC | 47 ms
33,324 KB |
testcase_18 | AC | 31 ms
23,876 KB |
testcase_19 | AC | 42 ms
30,460 KB |
testcase_20 | AC | 38 ms
28,652 KB |
testcase_21 | AC | 37 ms
28,672 KB |
testcase_22 | AC | 34 ms
25,216 KB |
testcase_23 | AC | 50 ms
36,836 KB |
testcase_24 | AC | 27 ms
20,712 KB |
testcase_25 | AC | 39 ms
29,784 KB |
testcase_26 | AC | 33 ms
27,376 KB |
testcase_27 | AC | 3 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 1e9 + 10; const ll INFL = 4e18; template <typename T> struct NegativeVector : vector<T> { int offset; NegativeVector(int lo, int hi, T init) { assert(lo <= hi); this->assign(hi - lo + 1, init); offset = -lo; } T& operator[](int i) { assert(i + offset >= 0); return vector<T>::operator[](i + offset); } T operator[](int i) const { assert(i + offset >= 0); return vector<T>::operator[](i + offset); } }; #include <atcoder/modint> using mint = atcoder::modint998244353; int main() { int N, M; cin >> N >> M; vector<ll> V(N), W(N); for (int i = 0; i < N; i++) cin >> V[i] >> W[i]; const int mx = 10000; const int hi = max(0, M + mx); vector<NegativeVector<ll>> dp(N + 1, NegativeVector<ll>(-mx, hi, -INFL)); dp[0][0] = 0; for (int i = 0; i < N; i++) { for (int j = -mx; j <= hi; j++) { if (dp[i][j] == -INFL) continue; dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]); if (j + W[i] >= -mx && j + W[i] <= hi) dp[i + 1][j + W[i]] = max(dp[i + 1][j + W[i]], dp[i][j] + V[i]); } } ll vmx = -INFL; for (int i = -mx; i <= M; i++) vmx = max(vmx, dp[N][i]); vector<NegativeVector<mint>> dp2(N + 1, NegativeVector<mint>(-mx, hi, 0)); for (int i = -mx; i <= M; i++) { if (dp[N][i] == vmx) dp2[N][i] = 1; } for (int i = N - 1; i >= 0; i--) { for (int j = -mx; j <= hi; j++) { if (dp[i][j] == dp[i + 1][j]) dp2[i][j] += dp2[i + 1][j]; if (j + W[i] >= -mx && j + W[i] <= hi && dp[i + 1][j + W[i]] == dp[i][j] + V[i]) dp2[i][j] += dp2[i + 1][j + W[i]]; } } cout << vmx << ' ' << dp2[0][0].val() << endl; }