結果

問題 No.2364 Knapsack Problem
ユーザー untiunti
提出日時 2023-07-04 03:37:00
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 26 ms / 3,000 ms
コード長 3,853 bytes
コンパイル時間 2,556 ms
コンパイル使用メモリ 219,604 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-09-25 01:05:20
合計ジャッジ時間 3,850 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 3 ms
4,380 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 13 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 7 ms
4,376 KB
testcase_11 AC 2 ms
4,376 KB
testcase_12 AC 24 ms
4,376 KB
testcase_13 AC 26 ms
4,376 KB
testcase_14 AC 24 ms
4,376 KB
testcase_15 AC 25 ms
4,380 KB
testcase_16 AC 23 ms
4,376 KB
testcase_17 AC 22 ms
4,376 KB
testcase_18 AC 25 ms
4,376 KB
testcase_19 AC 25 ms
4,380 KB
testcase_20 AC 25 ms
4,376 KB
testcase_21 AC 23 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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[j].fi;
    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;
  
}
0