結果
問題 |
No.2866 yuusaan's Knapsack
|
ユーザー |
![]() |
提出日時 | 2024-08-30 21:44:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 2,000 ms |
コード長 | 1,112 bytes |
コンパイル時間 | 4,424 ms |
コンパイル使用メモリ | 257,224 KB |
最終ジャッジ日時 | 2025-02-24 02:59:14 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <stdio.h> #include <bits/stdc++.h> #include <atcoder/all> using namespace atcoder; using mint = modint998244353; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf32 1000000001 #define Inf64 1000000000000000001 using P = pair<int,mint>; P op(P a,P b){ if(a.first>b.first)return a; if(a.first<b.first)return b; return P(a.first,a.second+b.second); } P e(){ return make_pair(-Inf32,1); } int main(){ int N,W; cin>>N>>W; vector<P> dp(20001,e()); int c = 10000; dp[c] = make_pair(0,1); vector<pair<int,int>> items(N); rep(i,N){ int x,y; cin>>x>>y; items[i] = make_pair(y,x); } sort(items.begin(),items.end()); rep(i,N){ int v,w; v = items[i].second,w = items[i].first; vector<P> ndp(20001,e()); rep(j,20001){ P val = dp[j]; if(val.first==-Inf32)continue; ndp[j] = op(ndp[j],val); int nj = j + w; if(nj<0 || nj>=ndp.size())continue; val.first += v; ndp[nj] = op(ndp[nj],val); } swap(dp,ndp); } W += c; P ans = e(); rep(i,W+1){ ans = op(ans,dp[i]); } cout<<ans.first<<' '<<ans.second.val()<<endl; return 0; }