Submission #388356

#	Time	Username	Problem	Language	Result	Execution time	Memory
388356		ronnith	Bank (IZhO14_bank)	C++14	100 / 100	177 ms	1396 KiB

bank

#include <bits/stdc++.h>

using namespace std;

const int N = 20;
const int M = 20;
const int MX_A = 1000;
const int MX_B = 1000;

int n, m, a[N], b[M];
bool dp[1<<M];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for(int i = 0;i < n;i ++) {
		cin >> a[i];
		if(i != 0) {
			a[i] += a[i - 1];
		}
	}
	for(int i = 0;i < m;i ++) {
		cin >> b[i];
	}
	dp[0] = true;
	for(int mask = 0;mask < (1<<m);mask ++) {
		int sm = 0;
		for(int i = 0;i < m;i ++) {
			if((1<<i)&mask) {
				sm += b[i];
			}
		}
		if(sm > a[n - 1]) continue;
		int ptr = 0;
		while(a[ptr] < sm) ptr ++;
		for(int i = 0;i < m;i ++) {
			if((1<<i)&mask && b[i] <= sm - (ptr == 0 ? 0 : a[ptr - 1])) {
				if(dp[mask^(1<<i)]) {
					dp[mask] = true;
		//			if(mask == 12) {
		//				cerr << i << '\n';
		//			}
					break;
				}
			}
		}
		if(sm == a[n - 1] && dp[mask]) {
		//	cerr << sm << '\n';
		//	for(int i = m - 1;i >= 0;i --) {
		//		cout << ((mask>>i)&1);
		//	}
		//	cout << '\n';
			cout << "YES\n";
			return 0;
		}
	}
	cout << "NO\n";
	return 0;
}

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