結果
問題 | No.2364 Knapsack Problem |
ユーザー | wahr69 |
提出日時 | 2023-07-04 10:19:55 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 15,955 bytes |
コンパイル時間 | 3,828 ms |
コンパイル使用メモリ | 286,180 KB |
実行使用メモリ | 8,064 KB |
最終ジャッジ日時 | 2024-07-18 06:37:49 |
合計ジャッジ時間 | 4,579 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | WA | - |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 6 ms
6,944 KB |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | AC | 2 ms
6,940 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | AC | 2 ms
6,944 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
ソースコード
//#define NDEBUG #pragma GCC optimize("O3","unroll-loops","omit-frame-pointer","inline") //Optimization flags //#pragma GCC option("arch=native","tune=native","no-zero-upper") //Enable AVX #pragma GCC target("avx") //Enable AVX #ifndef _MSC_VER #include <x86intrin.h> //AVX/SSE Extensions #endif #ifdef _MSC_VER #pragma warning(1:4456) #endif #define _CRT_SECURE_NO_WARNINGS #define _USE_MATH_DEFINES #define ALL(a) (a).begin(),(a).end() #define MEM2LOC(type,name) type name=(this->name); #define MEM2LOC_V(type,name) type name=((this->name).data()); #define LOC2MEM(name) (this->name)=(name); #include<iostream> #include<array> #include<vector> #include<list> #include<stack> #include<queue> #include<set> #include<map> #include<unordered_set> #include<unordered_map> #include<algorithm> #include<numeric> #include<iomanip> #include<math.h> #include<fstream> #include<string> #include<sstream> #include<cmath> #include<memory> #include<cassert> #include<functional> #include<chrono> #include<bitset> using namespace std; using namespace chrono; namespace ValLib { constexpr double DIST_INF=1e100; constexpr int DX4[]={0,-1,0,1}; constexpr int DY4[]={-1,0,1,0}; constexpr int DX8[]={0,-1,-1,-1,0,1,1,1}; constexpr int DY8[]={-1,-1,0,1,1,1,0,-1}; constexpr int DX5[]={DX4[0],DX4[1],DX4[2],DX4[3],0}; constexpr int DY5[]={DY4[0],DY4[1],DY4[2],DY4[3],0}; constexpr int DX9[]={DX8[0],DX8[1],DX8[2],DX8[3],DX8[4],DX8[5],DX8[6],DX8[7],0}; constexpr int DY9[]={DY8[0],DY8[1],DY8[2],DY8[3],DY8[4],DY8[5],DY8[6],DY8[7],0}; typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; constexpr ll V_MOD = 998244353ll; constexpr int V_INT_MAX = 2147483647; constexpr ll V_LL_MAX = 9223372036854775807ll; constexpr ull V_ULL_MAX = 18446744073709551615ull; template<class T,size_t A>using array1=array<T,A>; template<class T,size_t A,size_t B>using array2=array<array<T,B>,A>; template<class T,size_t A,size_t B,size_t C>using array3=array<array<array<T,C>,B>,A>; template<class T,size_t A,size_t B,size_t C,size_t D>using array4=array<array<array<array<T,D>,C>,B>,A>; template<class T,size_t A,size_t B,size_t C,size_t D,size_t E>using array5=array<array<array<array<array<T,E>,D>,C>,B>,A>; template<class T>using vector1=vector<T>; template<class T>using vector2=vector<vector<T>>; template<class T>using vector3=vector<vector<vector<T>>>; template<class T>using vector4=vector<vector<vector<vector<T>>>>; template<class T>using vector5=vector<vector<vector<vector<vector<T>>>>>; template<typename T>class tuple3{public:T a,b,c;tuple3()=default;tuple3(const T&a,const T&b,const T&c):a(a),b(b),c(c){}}; template<typename Key,typename Value>using umap=std::unordered_map<Key,Value>; template<typename T>using uset=std::unordered_set<T>; template<typename T>using sptr=typename std::shared_ptr<T>; template<class _Iter>using iter_cat_type=typename std::iterator_traits<_Iter>::iterator_category; template<class _Ty,class=void>constexpr bool _is_iterator=false; template<class _Ty>constexpr bool _is_iterator<_Ty,std::void_t<iter_cat_type<_Ty>>> = true; template<typename T>void fill(vector<T>&a,const T&v){std::fill(ALL(a),v);} template<typename T>void fill(vector<vector<T>>&a,const T&v){for(vector<T>&t:a)std::fill(ALL(t),v);} template<typename T>void resize(vector<T>&a,int sz1){a.resize(sz1);} template<typename T>void resize(vector<T>&a,int sz1,const T&v){a.resize(sz1,v);} template<typename T>void resize(vector<vector<T>>&a,int sz1,int sz2){a.resize(sz1);for(vector<T>&t:a)t.resize(sz2);} template<typename T>void resize(vector<vector<T>>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector<T>&t:a)t.resize(sz2,v);} template<typename T>void assign(vector<T>&a,int sz1,const T&v){a.assign(sz1,v);} template<typename T>void assign(vector<vector<T>>&a,int sz1,int sz2,const T&v){a.resize(sz1);for(vector<T>&t:a)t.assign(sz2,v);} template<typename T,size_t SZ>void fill(array<T,SZ>&a,const T&v){std::fill(ALL(a),v);} template<typename T,size_t SZ1,size_t SZ2>void fill(array2<T,SZ1,SZ2>&a,const T&v){for(array<T,SZ2>&t:a)std::fill(ALL(t),v);} template<typename T,typename U>ostream&operator<<(ostream&os,const pair<T,U>&pr){os<<"{"<<pr.first<<","<<pr.second<<"}";return os;} template<typename T>ostream&operator<<(ostream&os,vector<T>&a){for(int i=0;i<a.size();i++){if(i!=0){os<<" ";}os<<a[i];}return os;} template<typename T,size_t SZ>ostream&operator<<(ostream&os,const array<T,SZ>&a){os<<"[";for(int i=0;i<SZ;i++){if(i!=0){os<<",";}os<<a[i];}os<<"]";return os;} template<typename T,typename U>ostream&operator<<(ostream&os,const map<T,U>&m){os<<"{";auto b=m.begin();auto e=m.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<p->first<<":"<<p->second;}os<<"}";return os;} template<typename T>ostream&operator<<(ostream&os,const set<T>&s){os<<"{";auto b=s.begin();auto e=s.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<*p;}os<<"}";return os;} template<typename T,typename U>ostream&operator<<(ostream&os,const unordered_map<T,U>&m){os<<"{";auto b=m.begin();auto e=m.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<p->first<<":"<<p->second;}os<<"}";return os;} template<typename T>ostream&operator<<(ostream&os,const unordered_set<T>&s){os<<"{";auto b=s.begin();auto e=s.end();for(auto p=b;p!=e;++p){if(p!=b){os<<",";}os<<*p;}os<<"}";return os;} constexpr ll mod_add(ll a,ll b,ll mod){return((a%mod)+(b%mod))%mod;} constexpr ll mod_sub(ll a,ll b,ll mod){return((a%mod)+mod-(b%mod))%mod;} // a>bだとmod-(b-a)が返る constexpr ll mod_mul(ll a,ll b,ll mod){return((a%mod)*(b%mod))%mod;} constexpr ull mod_add(ull a,ull b,ull mod){return((a%mod)+(b%mod))%mod;} constexpr ull mod_sub(ull a,ull b,ull mod){return((a%mod)+mod-(b%mod))%mod;} // a>bだとmod-(b-a)が返る constexpr ull mod_mul(ull a,ull b,ull mod){return((a%mod)*(b%mod))%mod;} constexpr int intPow(int x,int n){assert(x>=0);assert(n>=0);if(x==0){if(n==0){return 1;}else{return 0;}}int r=1,z=x;while(n>0){if(n&1){r*=z;}z*=z;n>>=1;}return r;} constexpr ll intPow(ll x,ll n){assert(x>=0ll);assert(n>=0ll);if(x==0ll){if(n==0ll){return 1ll;}else{return 0ll;}}ll r=1ll,z=x;while(n>0ll){if(n&1ll){r*=z;}z*=z;n>>=1ll;}return r;} constexpr ll intPow(ll x,ll n,ll mod){assert(x>=0ll);assert(n>=0ll);if(x==0ll){if(n==0ll){return 1ll;}else{return 0ll;}}ll r=1ll,z=x;while(n>0ll){if(n&1ll){if(mod>0ll){r=mod_mul(r,z,mod);}else{r*=z;}}if(mod>0ll){z=mod_mul(z,z,mod);}else{z*=z;}n>>=1ll;}return r;} constexpr ull intPow(ull x,ull n){if(x==0ull){if(n==0ull){return 1ull;}else{return 0ull;}}ull r=1ull,z=x;while(n>0ull){if(n&1ull){r*=z;}z*=z;n>>=1ull;}return r;} constexpr ull intPow(ull x,ull n,ull mod){if(x==0ull){if(n==0ull){return 1ull;}else{return 0ull;}}ull r=1ull,z=x;while(n>0ull){if(n&1ull){if(mod>0ull){r=mod_mul(r,z,mod);}else{r*=z;}}if(mod>0ull){z=mod_mul(z,z,mod);}else{z*=z;}n>>=1ull;}return r;} constexpr ll mod_inv(ll a,ll mod){return intPow(a%mod,mod-2ll,mod);} constexpr ll mod_div(ll a,ll b,ll mod){return mod_mul(a,mod_inv(b,mod),mod);} constexpr ull mod_inv(ull a,ull mod){return intPow(a%mod,mod-2ull,mod);} constexpr ull mod_div(ull a,ull b,ull mod){return mod_mul(a,mod_inv(b,mod),mod);} typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef pair<long double, long double> pdd; ll ceilDiv(ll a,ll b){return a/b+(a%b!=0?1:0);} ll isOverflowAdd(ll a,ll b){return a > V_LL_MAX - b;} ll isOverflowMul(ll a,ll b){return a > V_LL_MAX / b;} void debugErrSub(); template<class Head,class...Tail>void debugErrSub(Head&&head,Tail&&...tail){cerr<<" "<<head;debugErrSub(std::forward<Tail>(tail)...);} template<class Head,class...Tail>void debugErr(Head&&head,Tail&&...tail){cerr<<head;debugErrSub(std::forward<Tail>(tail)...);} template<typename Key, typename Value> bool containsKey(const umap<Key, Value>& m, const Key& key) { return m.find(key) != m.end(); } template<typename Key, typename Value> bool containsValue(const umap<Key, Value>& m, const Value& val) { for (auto it = m.begin(); it != m.end(); ++it) if (it->second == val) return true; return false; } template<typename T> const typename uset<T>::const_iterator find(const uset<T>& s, const T& key) { return s.find(key); } template<typename T> bool contains(const uset<T>& s, const T& key) { return s.find(key) != s.end(); } #ifndef __GNUC__ int __builtin_popcount(unsigned int n){return(int)bitset<32>(n).count();} int __builtin_popcountll(unsigned long long n){return(int)bitset<64>(n).count();} #endif // 条件を満たす最小の要素のindexを返す // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 // 使い方の例: int result = binarySearch<int>(A, 0, N - 1, [&](int x) { return x >= K; }); template<typename T> int binarySearch(const vector<T>& vec, int beginIndex, int endIndex, const function<bool(const T&)>& confilm) { int lb = beginIndex; // lower bound int ub = endIndex; // upper bound while (abs(ub - lb) > 1) { int mid = (ub + lb) / 2; if (confilm(vec[mid])) { ub = mid; } else { lb = mid; } } return ub; } // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 ll binarySearch(ll lb, ll ub, const function<bool(ll)>& check) { while (abs(ub - lb) > 1ll) { ll mid = (lb + ub) / 2ll; if (check(mid)) { ub = mid; } else { lb = mid; } } return ub; } // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 ull binarySearch(ull lb, ull ub, const function<bool(ull)>& check) { assert(ub > lb); while (ub - lb > 1ull) { ull mid = (lb + ub) / 2ull; if (check(mid)) { ub = mid; } else { lb = mid; } } return ub; } // lb: lower bound. 条件式を満たさない // ub: upper bound. 条件式を満たす // check: 条件式 long double binarySearch(long double lb, long double ub, const function<bool(long double)>& check) { while (fabs(ub - lb) > (long double)1e-15) { long double mid = (lb + ub) / 2.0L; if (check(mid)) { ub = mid; } else { lb = mid; } } return ub; } // 最大公約数(ユーグリッドの互除法) static constexpr ull gcd(ull x, ull y) { assert(x > 0ull); assert(y > 0ull); ull r = 0ull; while ((r = x % y) != 0ull) { x = y; y = r; } return y; } // 最小公倍数 static constexpr ull lcm(ull x, ull y) { assert(x > 0ull); assert(y > 0ull); return x / gcd(x, y) * y; } // 文字列の先頭の0を削除する string cutZeroLeft(const string& str) { for (int i = 0; i < (int)str.length(); ++i) { if (str[i] != '0') { return str.substr(i); } } return ""; } // 0以上の整数を0埋めで表記する string fillZero(ull number, int digit) { int zeroNum = max(0, (int)(digit - to_string(number).length())); return move(move(string(zeroNum, '0')) + move(to_string(number))); } // double型の値を任意の少数桁数で表示する // 指定の桁数まで0で埋める。指数表記にはならない // precision=0を指定したときは小数点は表示しない // 表示桁数+1桁目を四捨五入する string sprintDoublePlane(double value, int precision) { assert(precision >= 0); stringstream ss; ss << fixed << setprecision(precision) << value; return move(ss.str()); } template<typename A>void in(A&a){cin>>a;cin.ignore();} template<typename A,typename B>void in(A&a,B&b){cin>>a>>b;cin.ignore();} template<typename A,typename B,typename C>void in(A&a,B&b,C&c){cin>>a>>b>>c;cin.ignore();} template<typename A,typename B,typename C,typename D>void in(A&a,B&b,C&c,D&d){cin>>a>>b>>c>>d;cin.ignore();} template<typename A,typename B,typename C,typename D,typename E>void in(A&a,B&b,C&c,D&d,E&e){cin>>a>>b>>c>>d>>e;cin.ignore();} template<typename A,typename B,typename C,typename D,typename E,typename F>void in(A&a,B&b,C&c,D&d,E&e,F&f){cin>>a>>b>>c>>d>>e>>f;cin.ignore();} template<typename A,typename B,typename C,typename D,typename E,typename F,typename G>void in(A&a,B&b,C&c,D&d,E&e,F&f,G&g){cin>>a>>b>>c>>d>>e>>f>>g;cin.ignore();} template<typename A>void inr(vector<A>&a,int size){resize(a,size);for(int i=0;i<size;++i){cin>>a[i];cin.ignore();}} template<typename A,typename B>void inr(vector<A>&a,vector<B>&b,int size){resize(a,size);resize(b,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i];cin.ignore();}} template<typename A,typename B,typename C>void inr(vector<A>&a,vector<B>&b,vector<C>&c,int size){resize(a,size);resize(b,size);resize(c,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i]>>c[i];cin.ignore();}} template<typename A,typename B,typename C,typename D>void inr(vector<A>&a,vector<B>&b,vector<C>&c,vector<D>&d,int size){resize(a,size);resize(b,size);resize(c,size);resize(d,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i]>>c[i]>>d[i];cin.ignore();}} template<typename A,typename B,typename C,typename D,typename E>void inr(vector<A>&a,vector<B>&b,vector<C>&c,vector<D>&d,vector<E>&e,int size){resize(a,size);resize(b,size);resize(c,size);resize(d,size);resize(e,size);for(int i=0;i<size;++i){cin>>a[i]>>b[i]>>c[i]>>d[i]>>e[i];cin.ignore();}} template<typename A>void inrl(vector<A>&a,int size){resize(a,size);for(int i=0;i<size;++i){cin>>a[i];}cin.ignore();} template<typename A>void inr(vector2<A>&a,int h,int wa){resize(a,h,wa);for(int i=0;i<h;++i){for(int j=0;j<wa;++j){cin>>a[i][j];}cin.ignore();}} template<typename A,typename B>void inr(vector2<A>&a,vector2<B>&b,int h,int wa,int wb){resize(a,h,wa);resize(b,h,wb);for(int i=0;i<h;++i){for(int j=0;j<wa;++j){cin>>a[i][j];}for(int j=0;j<wb;++j){cin>>b[i][j];}cin.ignore();}} template<typename A,typename B,typename C>void inr(vector2<A>&a,vector2<B>&b,vector2<C>&c,int h,int wa,int wb,int wc){resize(a,h,wa);resize(b,h,wb);resize(c,h,wc);for(int i=0;i<h;++i){for(int j=0;j<wa;++j){cin>>a[i][j];}for(int j=0;j<wb;++j){cin>>b[i][j];}for(int j=0;j<wc;++j){cin>>c[i][j];}cin.ignore();}} template<typename A,typename B>void inpr(vector<pair<A,B>>&a,int h){resize(a,h);for(int i=0;i<h;++i){cin>>a[i].first>>a[i].second;cin.ignore();}} template<typename T>void out(const T&val){cout<<val<<"\n";} } using namespace ValLib; ull xor128(){static ull x=123456789,y=362436069,z=521288629,w=88675123;ull t=(x^(x<<11));x=y;y=z;z=w;return w=(w^(w>>19))^(t^(t>>8));} void solve() { ll N, M, W; in(N, M, W); vector<ll> A, B, C, D; inrl(A, (int)N); inrl(B, (int)N); inrl(C, (int)M); inrl(D, (int)M); vector2<pair<int, pll>> magicList(1 << M); for (int b = 0; b < (1 << M); ++b) { for (int b2 = 0; b2 < (1 << M); ++b2) { if (b + b2 != (b | b2)) { continue; } ll c = 0, d = 0; for (int i = 0; i < M; ++i) { if ((1 << i) & b2) { c += C[i]; d += D[i]; } } magicList[b].push_back(make_pair(b + b2, pll(c, d))); } } vector3<ll> dp(N + 1, vector2<ll>(W + 1, vector<ll>(1 << M, 0))); for (int i = 0; i < N; ++i) { for (int w = 0; w <= W; ++w) { for (int b = 0; b < (1 << M); ++b) { for (const pair<int, pll>& magic : magicList[b]) { int b2 = magic.first; ll c = magic.second.first; ll d = magic.second.second; if (w - c >= 0 && w - c <= W) { dp[i][w - c][b] = max(dp[i][w - c][b], dp[i][w][b] - d); } } } for (int b = 0; b < (1 << M); ++b) { if (w + A[i] >= 0 && w + A[i] <= W) { dp[i + 1][w + A[i]][b] = max(dp[i + 1][w + A[i]][b], dp[i][w][b] + B[i]); } dp[i + 1][w][b] = max(dp[i + 1][w][b], dp[i][w][b]); } } } ll ans = 0; for (int w = 0; w <= W; ++w) { for (int b = 0; b < (1 << M); ++b) { ans = max(ans, dp[N][w][b]); } } out(ans); } int main() { std::ios::sync_with_stdio(false); //#define INPUT_FROM_FILE //#define OUTPUT_TO_FILE #ifdef INPUT_FROM_FILE ifstream ifs("input01.txt"); cin.rdbuf(ifs.rdbuf()); #endif #ifdef OUTPUT_TO_FILE ofstream ofs("output01.txt"); cout.rdbuf(ofs.rdbuf()); #endif solve(); }