結果
問題 | No.2364 Knapsack Problem |
ユーザー | dokaraya |
提出日時 | 2023-06-30 21:34:27 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,400 bytes |
コンパイル時間 | 1,840 ms |
コンパイル使用メモリ | 206,428 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-07-07 09:09:04 |
合計ジャッジ時間 | 2,508 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 0 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 1 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,944 KB |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | WA | - |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 3 ms
6,940 KB |
testcase_13 | AC | 3 ms
6,944 KB |
testcase_14 | WA | - |
testcase_15 | AC | 3 ms
6,944 KB |
testcase_16 | AC | 3 ms
6,944 KB |
testcase_17 | AC | 3 ms
6,944 KB |
testcase_18 | AC | 2 ms
6,944 KB |
testcase_19 | AC | 3 ms
6,944 KB |
testcase_20 | AC | 2 ms
6,944 KB |
testcase_21 | AC | 3 ms
6,940 KB |
ソースコード
#line 1 "template/template.hpp" #include<bits/stdc++.h> using ll = long long; #define REP(i, n) for(ll i = 0; (i) < ll(n); ++ (i)) #define FOR(i, m, n) for(ll i = (m); (i) <= ll(n); ++ (i)) #define REPR(i, n) for(ll i = ll(n) - 1; (i) >= 0; -- (i)) #define FORR(i, m, n) for(ll i = ll(n); (i) >= ll(m); -- (i)) #define ALL(x) x.begin(),x.end() #define INF (int)1e9 #define LLINF (long long)1e18 #define MOD (int)(1e9+7) #define MOD9 (int)998244353 #define PI 3.141592653589 #define PB push_back #define F first #define S second #define YESNO(T) if(T){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;} #define yesno(T) if(T){cout<<"yes"<<endl;}else{cout<<"no"<<endl;} #define YesNo(T) if(T){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;} #define Yes(T) {cout<<"Yes"<<endl; if(T) return 0;} #define No(T) {cout <<"No"<<endl; if(T) return 0;} #define YES(T) {cout<<"YES"<<endl; if(T) return 0;} #define NO(T) {cout <<"NO"<<endl; if(T) return 0;} #define Graph vector<vector<int> > #define CostGraph vector<vector<pair<int,ll> > > #define PII pair<int,int> #define PLL pair<ll,ll> #define VI vector<int> #define VL vector<ll> #define VVI vector<vector<int> > #define VVL vector<vector<ll> > #define VPII vector<pair<int,int> > #define VPLL vector<pair<ll,ll> > #define DDD fixed<<setprecision(10) #define PAD setfill('0')<<right<<setw(8) template <class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false; } template <class T> inline bool chmax(T &a, T b) { if(a < b){a = b; return true;} return false; } struct input{ int n; input() {} input(int n_) : n(n_){}; template <class T> operator T(){ T ret; std::cin >> ret; return ret; } template <class T> operator std::vector<T>() { std::vector<T> ret(n); REP(i,n) std::cin >> ret[i]; return ret; } }; template <class T> inline void printVec(std::vector<T> v){ REP(i,v.size()){ if(i) std::cout << " "; std::cout << v[i]; } std::cout << std::endl; } using namespace std; #line 2 "data-structure/unionfind.hpp" struct UnionFind { vector<int> parent; vector<int> rank; UnionFind(int n) { init(n); } void init(int n) { parent.resize(n); rank.resize(n); for(int i = 0; i < n; ++i){ parent[i] = i; rank[i] = 0; } } int getRoot(int x) { if(parent[x] == x) return x; return parent[x] = getRoot(parent[x]); } bool isSame(int x, int y) { return getRoot(x) == getRoot(y); } bool merge(int x, int y) { x = getRoot(x); y = getRoot(y); if(x == y) return false; if(rank[x] < rank[y]) swap(x, y); if(rank[x] == rank[y]) ++rank[x]; parent[y] = x; return true; } vector<vector<int>> getGroups(){ int n = rank.size(); vector<vector<int>> rest(n), res; for(int i = 0; i < n; ++i) rest[getRoot(i)].push_back(i); for(int i = 0; i < n; ++i) if(rest[i].size()) res.push_back(rest[i]); return res; } }; #line 3 "main.cpp" int main(){ int n, m, w; cin >> n >> m >> w; VI a = input(n); VI b = input(n); VI c = input(m); VI d = input(m); int ans = 0; REP(i,(1 << (n+m))){ int sw = 0, sv = 0; REP(j,(n+m)){ if((i & (1 << j)) == 0) continue; if(j < n){ sw += a[j]; sv += b[j]; }else{ sw -= c[j-n]; sv -= d[j-n]; } } if(sw >= 0 && sw <= w) chmax(ans, sv); } cout << ans << endl; }