Submission #1000076

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000076		vjudge3	Bank (IZhO14_bank)	C++17	100 / 100	547 ms	1680 KiB

bank

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> b;
bitset<1<<20> vis[21];
vector<vector<int>> need[21]; 
int n, m;

int conv (vector<int>& vec) {
	int base = 1, res = 0;
	for (int i = 0; i < m; i++) {
		res += base * vec[i];
		base *= b[i].second+1;
	}
	return res;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	vector<int> a (n+1);
	vector<int> cnt (1001);
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 0; i < m; i++) {
		int x;
		cin >> x;
		cnt[x]++;
	}
	for (int i = 1; i <= 1000; i++) if (cnt[i]) b.push_back({i, cnt[i]});
	m = b.size();
	for (int i = 1; i <= n; i++) {
		vector<int> cur (m);
		while (true) {
			cur[0]++;
			for (int j = 0; j < m; j++) if (cur[j] > b[j].second) {
				if (j == m-1) goto nxt;
				cur[j] = 0;
				cur[j+1]++;
			}
			int sum = 0;
			for (int j = 0; j < m; j++) sum += cur[j] * b[j].first;
			if (sum == a[i]) need[i].push_back(cur);
		}
		nxt: {}
	}
	queue<pair<int, vector<int>>> bfs;
	vector<int> init (m);
	bfs.push({0, init});
	while (!bfs.empty()) {
		auto [i, used] = bfs.front();
		if (i == n) {
			cout << "YES\n";
			exit(0);
		}
		bfs.pop();
		i++;
		for (auto& v : need[i]) {
			bool ok = true;
			for (int k = 0; k < m; k++) if (used[k] + v[k] > b[k].second) {
				ok = false;
				break;
			}
			if (ok) {
				for (int k = 0; k < m; k++) used[k] += v[k];
				int h = conv(used);
				if (!vis[i][h]) {
					vis[i][h] = true;
					bfs.push({i, used});
				}
				for (int k = 0; k < m; k++) used[k] -= v[k];
			}
		}
	}
	cout << "NO\n";
	return 0;
}

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