結果
問題 | 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;}