Submission #342043

#	Time	Username	Problem	Language	Result	Execution time	Memory
342043		Kevin_Zhang_TW	Bank (IZhO14_bank)	C++17	100 / 100	270 ms	94444 KiB

bank

#include<bits/stdc++.h>
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &val, T nv) {
	return val < nv ? (val = nv, true) : false;
}
template<class T>
bool chmin(T &val, T nv) {
	return nv < val ? (val = nv, true) : false;
}
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
void kout(){ cerr << endl; }
template<class T1, class ...T2> void kout(T1 a, T2 ...e) { cerr << a << ' ', kout(e...); }
#else
#define DE(...) 0
#define debug(...) 0
#endif
// What I should check
// 1. overflow
// 2. corner cases
// Enjoy the problem instead of hurrying to AC
// Good luck !
const int MAX_N = 20, MAX_M = 1001;
int n, m, a[MAX_N], b[MAX_N], sum[1<<MAX_N];
int dp[MAX_N][1<<MAX_N];
vector<int> sumask[MAX_N * MAX_M];
bool dfs(int cur, int mask) {
	if (cur == n) return true;
	if (dp[cur][mask] != -1) return dp[cur][mask];
	dp[cur][mask] = 0;
	for (int u : sumask[ a[cur] ])
		if ((mask & u) == u && (dp[cur][mask] |= dfs(cur+1, mask ^ u)))
			return true;
	return false;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 0;i < n;++i)
		cin >> a[i];
	for (int i = 0;i < m;++i)
		cin >> b[i];

	for (int s = 1;s < 1<<m;++s) {
		sum[s] = b[__lg(s)];

		if (s != (s & -s)) sum[s] += sum[s ^ (1<<__lg(s))];

		assert(sum[s] < MAX_N * MAX_M);

		sumask[ sum[s] ].pb(s);
	}

	memset(dp, -1, sizeof(dp));

	puts(dfs(0, (1<<m)-1) ? "YES" : "NO");
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29