結果
問題 | No.2364 Knapsack Problem |
ユーザー | dokaraya |
提出日時 | 2023-06-30 21:28:52 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,513 bytes |
コンパイル時間 | 2,237 ms |
コンパイル使用メモリ | 207,412 KB |
実行使用メモリ | 13,756 KB |
最終ジャッジ日時 | 2024-07-07 09:01:12 |
合計ジャッジ時間 | 6,397 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
13,756 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 1 ms
6,944 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 10 ms
6,944 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | TLE | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
ソースコード
#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); VI t(n+m); iota(ALL(t), 0); int ans = 0; do{ int val = 0; int wgt = 0; REP(i,n+m){ if(t[i] < n){ if(wgt + a[t[i]] <= w){ wgt += a[t[i]]; val += b[t[i]]; } }else{ if(wgt - c[t[i] - n] >= 0){ wgt -= c[t[i] - n]; val -= d[t[i] - n]; } } chmax(ans, val); } }while(next_permutation(ALL(t))); cout << ans << endl; }