Submission #765457

#	Time	Username	Problem	Language	Result	Execution time	Memory
765457		AutomatiC__	Bank (IZhO14_bank)	C++17	100 / 100	112 ms	8548 KiB

bank

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cstdlib>
#include <bitset>
#include <deque>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 20;
pair<int, int> f[1 << maxn];
int a[maxn], b[maxn];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	sort(a, a + n, greater<int>());
	sort(b, b + m, greater<int>());
	f[0] = make_pair(0, 0);
	for (int s = 1; s < (1 << m); s++) {
		f[s] = make_pair(0, 0);
		for (int i = 0; i < m; i++) {
			if (~s & (1 << i)) continue;
			pair<int, int> pre = f[s ^ (1 << i)];
			if (pre.second + b[i] == a[pre.first]) {
				pre.first++;
				pre.second = 0;
			} else if (pre.second + b[i] < a[pre.first]) {
				pre.second += b[i];
			}
			f[s] = max(f[s], pre);
		}
	}
	for (int s = 0; s < (1 << m); s++) {
		if (f[s].first >= n) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
	return 0;
}

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