Submission #337832

#	Time	Username	Problem	Language	Result	Execution time	Memory
337832		Tosic	Bank (IZhO14_bank)	C++14	100 / 100	124 ms	16056 KiB

bank

#include <bits/stdc++.h>
#define maxA 1010
#define maxn 21
using namespace std;

int n, m, a[maxn],b[maxn], ans;
vector<vector<int> > allMasks;
int dp[maxn][1<<20];
bool was[maxn][1<<20];

bool getDp(int idx, int mask){
	if(idx < 0){
		return 1;
	}
	if(was[idx][mask]){
		return dp[idx][mask];
	}
	was[idx][mask] = 1;
	for(auto x : allMasks[a[idx]]){
                //cerr << x << ' ';
				if(((x & mask) == x) and getDp(idx-1, mask^x)){
					dp[idx][mask] = 1;
					//cerr << idx << ' ' << mask << '\n';
					return 1;
				}
    }
    return 0;
}

int main(){
	ios_base::sync_with_stdio(0);
	cout.tie(0);
	cin.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];
	}
	allMasks.resize(maxA, vector<int>());
	for(int i = 0; i < (1<<m); ++i){
		int tmp = 0;
		for(int j = 0; j < m; ++j){
			tmp += ((i>>j) & 1)*b[j];
		}
		if(tmp < maxA){
			allMasks[tmp].push_back(i);
		}
	}
	ans = getDp(n-1, (1<<m)-1);
	if(ans){
		cout<<"YES\n";
	} else {
		cout << "NO\n";
	}
}

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