結果
問題 | No.2364 Knapsack Problem |
ユーザー |
![]() |
提出日時 | 2023-06-30 22:31:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 667 ms / 3,000 ms |
コード長 | 842 bytes |
コンパイル時間 | 1,647 ms |
コンパイル使用メモリ | 170,188 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-07 10:22:46 |
合計ジャッジ時間 | 7,523 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll =long long; #define all(v) v.begin(),v.end() #define rep(i,a,b) for(int i=a;i<b;i++) #define rrep(i,a,b) for(int i=a;i>=b;i--) ll INF=1e18; int main() { ll N,M,W;cin>>N>>M>>W; vector<ll> A(N),B(N),C(M),D(M); for(ll i=0;i<N;i++) cin>>A[i]; for(ll i=0;i<N;i++) cin>>B[i]; for(ll i=0;i<M;i++) cin>>C[i]; for(ll i=0;i<M;i++) cin>>D[i]; vector<ll> a(N),b(M); for(ll i=0;i<N;i++) a[i]=i; for(ll i=0;i<M;i++) b[i]=i; ll ans=0; do { do{ ll w=0; ll v=0; ll bi=0; for(ll i=0;i<N;i++) { while(bi<M&&w+A[a[i]]>W) { w-=C[b[bi]]; v-=D[b[bi]]; bi++; } if(w<0||w+A[a[i]]>W) break; w+=A[a[i]]; v+=B[a[i]]; ans=max(ans,v); } }while(next_permutation(all(b))); }while(next_permutation(all(a))); cout<<ans<<endl; }