結果

問題 No.2364 Knapsack Problem
ユーザー unti
提出日時 2023-07-04 03:23:01
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,806 bytes
コンパイル時間 2,410 ms
コンパイル使用メモリ 214,452 KB
最終ジャッジ日時 2025-02-15 05:46:02
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

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)][505];
ll ep[(1<<14)][505];
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))rep(j,505){
    dp[i][j]=-INF; ep[i][j]=-INF;
  }
  dp[0][0]=0ll;
  rep(ww,14){
    rep(i,(1<<(n+m)))rep(j,505){
      ep[i][j]=dp[i][j];
    }
    rep(i,(1<<(n+m)))rep(j,505){
      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)][j+A[add].fi],dp[i][j]+A[add].se);
      }
    }
    rep(i,(1<<(n+m)))rep(j,505){
      dp[i][j]=ep[i][j];
      ep[i][j]=-INF;
    }
  }
  ll ans=-INF;
  rep(i,(1<<(n+m)))rep(j,505){
    chmax(ans,dp[i][j]);
  }
  cout<<ans<<endl;
  
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0