Submission #1067481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067481		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	89 ms	10732 KiB

bank

#include<bits/stdc++.h>
#define F first
#define S second
#define SZ(x) int((x).size())
const char nl = '\n';
using namespace std;

int sum[(1 << 20)];
vector<int> v[1010];
int a[20], b[20];
int n, m;
bool dp[1010][(1 << 20)];


bool muba(int N, int M, vector<int> A, vector<int> B) {
	// input
	n = N, m = M;
	for (int i = 0; i < n; i ++) {
		a[i] = A[i];
	}
	for (int i = 0; i < m; i ++) {
		b[i] = B[i];
	}
	// end of input
	for (int mask = 0; mask < (1 << m); mask ++) {
		for (int i = 0; i < m; i ++) {
			if (mask & (1 << i)) sum[mask] += b[i];
		}
	}
	for (int i = 0; i < n; i ++) {
		for (int mask = 0; mask < (1 << m); mask ++) {
			if (sum[mask] == a[i]) {
				v[a[i]].push_back(mask);
			}
		}
	}
	for (auto el : v[a[0]]) {
		dp[0][el] = true;
	}
	for (int mask = 0; mask < (1 << m); mask ++) {
		if (dp[0][mask]) {
			for (int i = 0; i < m; i ++) {
				if (mask != (mask | (1 << i))) {
					// cout << mask << " " << (mask | (1 << i)) << nl;
				}
				dp[0][mask | (1 << i)] = true;
			}
		}
	}
	int tot = 0;
	for (int i = 0; i < n; i ++) {
		for (int mask = 0; mask < (1 << m); mask ++) {
			if (i > 0) {
				if (!dp[i-1][mask]) continue;
			} else {
				if (!dp[i][mask]) continue;
			}
			if (sum[mask] - tot == a[i]) {
				dp[i][mask] = true;
				for (int j = 0; j < m; j ++) {
					dp[i][mask | (1 << j)] = true;
				}
			}
		}
		tot += a[i];
	}
	if (dp[n-1][(1 << m)-1]) {
		return true;
	} else {
		return false;
	}

}


int people_num;
int note_num;
vector<int> people(20);
vector<int> banknotes(20);
vector<int> leftover(1 << 20, -1);
vector<int> people_covered(1 << 20, -1);


bool usaco(int N, int M, vector<int> A, vector<int> B) {
	people_num = N, note_num = M;
	for (int i = 0; i < N; i ++) {
		people[i] = A[i];
	}
	for (int i = 0; i < M; i ++) {
		banknotes[i] = B[i];
	}
	for (int i = 0; i < (1 << 20); i ++) {
		leftover[i] = -1;
		people_covered[i] = -1;
	}
	leftover[0] = 0;
	people_covered[0] = 0;
	for (int s = 0; s < (1 << note_num); s++) {
		for (int last = 0; last < note_num; last++) {
			if ((s & (1 << last)) == 0) { continue; }
			int prev = s & ~(1 << last);
			if (people_covered[prev] == -1) { continue; }

			int new_amt = leftover[prev] + banknotes[last];
			int curr_target = people[people_covered[prev]];
			if (new_amt < curr_target) {
				people_covered[s] = people_covered[prev];
				leftover[s] = new_amt;
			}
			else if (new_amt == curr_target) {
				people_covered[s] = people_covered[prev] + 1;
				leftover[s] = 0;
			}
		}
		if (people_covered[s] == people_num) {
			return true;
		}
	}
	return false;
}


signed main() {
	int nn, mm;
	cin >> nn >> mm;
	vector<int> aa(nn), bb(mm);
	for (int i = 0; i < nn; i ++) {
		cin >> aa[i];
	}
	for (int i = 0; i < mm; i ++) {
		cin >> bb[i];
	}
	if (usaco(nn, mm, aa, bb)) {
		cout << "YES";
	} else {
		cout << "NO";
	}
}

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