結果
問題 | No.2866 yuusaan's Knapsack |
ユーザー |
![]() |
提出日時 | 2024-08-30 23:11:44 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 1,450 bytes |
コンパイル時間 | 3,758 ms |
コンパイル使用メモリ | 285,140 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-26 14:37:38 |
合計ジャッジ時間 | 4,206 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h>using namespace std;#include <atcoder/modint>using namespace atcoder;using ll = long long;using P = pair<ll,ll>;#define fix(x) fixed << setprecision(x)#define asc(x) x, vector<x>, greater<x>#define rep(i, n) for(ll i = 0; i < n; ++i)#define all(x) (x).begin(),(x).end()template<class T>bool chmin(T&a, const T&b){if(a>b){a=b;return 1;}return 0;}template<class T>bool chmax(T&a, const T&b){if(a<b){a=b;return 1;}return 0;}constexpr ll INFLL = (1LL << 62), MOD = 998244353;constexpr int INF = (1 << 30);using mint = modint998244353;int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int n,x;cin >> n >> x;vector<int> v(n), w(n);ll tot = 0;rep(i,n){cin >> v[i] >> w[i];if(w[i]<0){w[i] *= -1;v[i] *= -1;x += w[i];tot += v[i];}}vector<ll> dp(x+1,-INFLL);vector<mint> cnt(x+1,0);dp[0] = 0;cnt[0] = 1;rep(i,n){auto upd = dp;auto ucnt = cnt;rep(j,x+1-w[i]){if(dp[j]==-INFLL) continue;if(chmax(upd[j+w[i]], dp[j]+v[i])) ucnt[j+w[i]] = 0;if(upd[j+w[i]]==dp[j]+v[i]) ucnt[j+w[i]] += cnt[j];}dp = upd, cnt = ucnt;}ll p = 0;rep(i,x+1) chmax(p, dp[i]);mint ans = 0;rep(i,x+1) if(p==dp[i]) ans += cnt[i];cout << p-tot << " " << ans.val() << '\n';return 0;}