結果
問題 | No.2364 Knapsack Problem |
ユーザー | unti |
提出日時 | 2023-07-04 03:34:44 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,853 bytes |
コンパイル時間 | 2,815 ms |
コンパイル使用メモリ | 223,012 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-18 01:15:55 |
合計ジャッジ時間 | 4,694 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | RE | - |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | WA | - |
testcase_10 | RE | - |
testcase_11 | WA | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll,ll>; using Graph= vector<vector<ll>>; struct edge{ll to ; ll cost ;} ; using graph =vector<vector<edge>> ; #define rep(i,n) for (ll i=0; i < (n); ++i) #define rep2(i,n,m) for(ll i=n;i<=m;i++) #define rep3(i,n,m) for(ll i=n;i>=m;i--) #define pb push_back #define eb emplace_back #define ppb pop_back #define mpa make_pair #define fi first #define se second const ll INF=1e18 ; inline void chmax(ll& a,ll b){a=max(a,b);} inline void chmin(ll& a,ll b){a=min(a,b);} struct UnionFind { vector<int> d; UnionFind(int n=0): d(n,-1) {} int find(int x) { if (d[x] < 0) return x; return d[x] = find(d[x]); } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (d[x] > d[y]) swap(x,y); d[x] += d[y]; d[y] = x; return true; } bool same(int x, int y) { return find(x) == find(y);} int size(int x) { return -d[find(x)];} }; // ダイクストラ ひーぷ /* dijkstra(G,s,dis) 入力:グラフ G, 開始点 s, 距離を格納する dis 計算量:O(|E|log|V|) 副作用:dis が書き換えられる */ // グラフ スタート 距離 ひとつ前 void dijkstra(const graph & g, ll s ,vector<ll> & d,vector<ll> &prev ){ ll N = g.size() ; //頂点数 d.resize(N,INF) ; prev.resize(N,INF) ; priority_queue<P,vector<P>,greater<P>> pq ; d[s]=0 ; pq.emplace(d[s],s) ; while(!pq.empty()){ P p=pq.top() ; pq.pop() ; ll v= p.se; if(d[v]<p.fi) continue ; for(auto & e :g[v]){ if(d[e.to]>d[v]+e.cost){ d[e.to]=d[v]+e.cost ; prev[e.to]=v ; //頂点vを使ってe.toに辿り着いた pq.emplace(d[e.to],e.to) ; } } } } /* get_path(prev, t) 入力:dijkstra で得た prev, ゴール t 出力: t への最短路のパス */ vector<ll> get_path(const vector<ll> &prev, ll t) { vector<ll> path; for (ll cur = t; cur != -1; cur = prev[cur]) { path.push_back(cur); } reverse(path.begin(), path.end()); // 逆順なのでひっくり返す return path; } map<ll,ll> factor(ll n){ //素因数とオーダーをマップで管理 map <ll,ll> ord ; for(ll i=2;i*i<=n;i++){ if(n%i==0){ int res=0; while(n%i==0){ n/=i; res++; } ord[i]=res; } } if(n!=1) ord[n]++; return ord ; } vector< int > z_algorithm(const string &s) { vector< int > prefix(s.size()); for(int i = 1, j = 0; i < s.size(); i++) { if(i + prefix[i - j] < j + prefix[j]) { prefix[i] = prefix[i - j]; } else { int k = max(0, j + prefix[j] - i); while(i + k < s.size() && s[k] == s[i + k]) ++k; prefix[i] = k; j = i; } } prefix[0] = (int) s.size(); return prefix; } ll dp[(1<<14)]; ll ep[(1<<14)]; int main(){ ll n,m,w; cin>>n>>m>>w; vector<P> A(n+m); rep(i,n) cin>>A[i].fi; rep(i,n) cin>>A[i].se; rep(i,m) cin>>A[n+i].fi; rep(i,m) cin>>A[n+i].se; rep(i,m){ A[n+i].fi=-A[n+i].fi; A[n+i].se=-A[n+i].se; } rep(i,(1<<14)){ dp[i]=-INF; ep[i]=-INF; } dp[0]=0ll; ll sum[(1<<14)]; rep(i,(1<<(n+m))){ ll p=0ll; bitset<14> s(i); rep(j,n+m) if(s[j]) p+=A[i].se; sum[i]=p; } rep(ww,14){ rep(i,(1<<(n+m))){ ep[i]=dp[i]; } rep(i,(1<<(n+m))){ ll j=sum[i]; bitset<14> s(i); rep(add,n+m){ if(s[add]) continue; if(!(0<=j+A[add].fi&&j+A[add].fi<=w)) continue; chmax(ep[i^(1<<add)],dp[i]+A[add].se); } } rep(i,(1<<(n+m))){ dp[i]=ep[i]; ep[i]=-INF; } } ll ans=-INF; rep(i,(1<<(n+m))){ chmax(ans,dp[i]); } cout<<ans<<endl; }