Submission #1353926

#TimeUsernameProblemLanguageResultExecution timeMemory
1353926temporary1은행 (IZhO14_bank)C++17
0 / 100
136 ms263024 KiB
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }

const int MOD = 1e9+7; // 998244353;

int a[25];
int b[25];

bitset<1005> dp[2][(1<<20)+5];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i <= m; ++i) {
		cin >> b[i];
	}
	dp[0][0][0] = true;
	for (int i = 1; i <= n; ++i) {
		int z = i&1;
		for (int j = 1; j < (1<<m); ++j) {
			int x = __builtin_ctz(j);
			dp[!z][j] = dp[!z][j^(1<<x)]|(dp[!z][j^(1<<x)]<<b[x+1]);
			// for (int ii = 0; ii < 20; ++ii) {
			// 	cout << dp[!z][j][ii];
			// } cout << '\n';
		}
		for (int j = 0; j < (1<<m); ++j) {
			dp[z][j].reset();
			if (dp[!z][j][a[i]])dp[z][j][0] = true;
		}
	}
	bool ans = false;
	for (int j = 0; j < (1<<m); ++j) {
		ans |= dp[n&1][j][0];
	}
	cout << (ans ? "YES" : "NO") << '\n';
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...