Submission #1096160

#TimeUsernameProblemLanguageResultExecution timeMemory
1096160muntasir__은행 (IZhO14_bank)C++14
0 / 100
10 ms16732 KiB
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #include <bits/stdc++.h>
#include<iostream>
#include<cstring>
using namespace std;
#define ll long long
const ll mod = 1e9 + 7;

ll n, m, a[20], b[20], dp1[(1 << 20)], dp2[(1 << 20)];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.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];
	memset(dp1, -1, sizeof(dp1));
	memset(dp2, -1, sizeof(dp2));
	dp1[0] = dp2[0] = 0;
	for (int mask = 0; mask < (1 << m); mask++) {
		for (int i = 0; i < m; i++) {
			if (mask & (1 << i)) {
				int prev = mask & ~(1 << i);
				int nwamnt = dp2[prev] + b[i];
				int cur_target = a[dp1[prev]];
				if (cur_target > nwamnt) {
					dp1[mask] = dp1[mask];
					dp2[mask] = nwamnt;
				}
				if (cur_target == nwamnt) {
					dp1[mask] = dp1[mask] + 1;
					dp2[mask] = 0;
				}
			}
		}
		if (dp1[mask] == n) {
			cout << "YES\n";
			return 0;
		}
	}
	cout << "NO\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...