#887154 (C++17) No.2364 Knapsack Problem

提出ソース
結果

問題	No.2364 Knapsack Problem
ユーザー	wahr69
提出日時	2023-07-04 11:19:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	4 ms / 3,000 ms
コード長	15,966 bytes
コンパイル時間	3,306 ms
コンパイル使用メモリ	278,500 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-18 07:27:33
合計ジャッジ時間	4,381 ms
ジャッジサーバーID （参考情報）	judge1 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	3 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	3 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,940 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	4 ms 6,944 KB
testcase_16	AC	3 ms 6,940 KB
testcase_17	AC	3 ms 6,940 KB
testcase_18	AC	3 ms 6,944 KB
testcase_19	AC	3 ms 6,944 KB
testcase_20	AC	3 ms 6,940 KB
testcase_21	AC	3 ms 6,944 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#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を指定したときは小数点は表示しない
	// 表示桁数＋１桁目を四捨五入する
	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<ll> w(1 << N, vector<ll>(1 << M, 0));
	for (int a = 0; a < (1 << N); ++a) {
		for (int b = 0; b < (1 << M); ++b) {
			ll weight = 0;
			for (int i = 0; i < N; ++i) {
				if (a & (1 << i)) {
					weight += A[i];
				}
			}
			for (int j = 0; j < M; ++j) {
				if (b & (1 << j)) {
					weight -= C[j];
				}
			}
			w[a][b] = weight;
		}
	}

	vector2<ll> dp(1 << N, vector<ll>(1 << M, -V_LL_MAX));
	dp[0][0] = 0;
	for (int a = 0; a < (1 << N); ++a) {
		for (int b = 0; b < (1 << M); ++b) {
			if (w[a][b] < 0 || w[a][b] > W || dp[a][b] == -V_LL_MAX) {
				continue;
			}
			for (int j = 0; j < M; ++j) {
				if (!(b & (1 << j)) && w[a][b] - C[j] >= 0) {
					dp[a][b | (1 << j)] = max(dp[a][b | (1 << j)], dp[a][b] - D[j]);
				}
			}
		}
		for (int b = 0; b < (1 << M); ++b) {
			if (w[a][b] < 0 || w[a][b] > W || dp[a][b] == -V_LL_MAX) {
				continue;
			}
			for (int i = 0; i < N; ++i) {
				if (!(a & (1 << i)) && w[a][b] + A[i] <= W) {
					dp[a | (1 << i)][b] = max(dp[a | (1 << i)][b], dp[a][b] + B[i]);
				}
			}
		}
	}
	ll ans = 0;
	for (int a = 0; a < (1 << N); ++a) {
		for (int b = 0; b < (1 << M); ++b) {
			ans = max(ans, dp[a][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();
}
yukicoder

結果

テストケース

ソースコード
