結果
問題 |
No.2167 Fibonacci Knapsack
|
ユーザー |
![]() |
提出日時 | 2022-12-19 08:36:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,653 ms / 2,000 ms |
コード長 | 1,198 bytes |
コンパイル時間 | 2,228 ms |
コンパイル使用メモリ | 205,908 KB |
最終ジャッジ日時 | 2025-02-09 16:40:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#pragma optimize("Ofast") #pragma target("avx2") #include<bits/stdc++.h> using namespace std; using lint = long long; #define rep(i,a,b) for(int i=(a);i<(b);++i) #define endl '\n' int main(){ cin.tie(0)->sync_with_stdio(0); int t; cin>>t; while(t--){ lint n,w; cin>>n>>w; vector<lint>a(n),b(n+1); rep(i,0,n)cin>>a[i]; rep(i,0,n)b[i+1]=b[i]+a[i]; vector<lint>f(n); f[0]=1; if(n>=2)f[1]=2; rep(i,2,n)f[i]=f[i-1]+f[i-2]; map<lint,lint>dp; lint ans=0; dp[w]=0; for(lint i=n-1;i>=0;i--){ map<lint,lint>dp1; for(auto [e,c]:dp){ if(i!=0&&e-a[i]-a[i-1]>=0){ dp1[e-a[i]]=max(dp1[e-a[i]],c+f[i]); ans=max(ans,c+f[i]); }else{ bool ok=0; if(e-a[i]>=0){ ok=1; ans=max(ans,c+f[i]); dp1[e-a[i]]=max(dp1[e-a[i]],c+f[i]); } dp1[e]=max(dp1[e],c); } } swap(dp,dp1); } cout<<ans<<endl; } }