제출 #337830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
337830		Tosic	은행 (IZhO14_bank)	C++14	71 / 100	1083 ms	9836 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];

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);
		}
	}
	for(int i = 0; i < n; ++i){
		if(i == 0){
			for(auto j:allMasks[a[i]]){
				dp[i][j] = 1;
			}
			continue;
		}
		for(int mask = 0; mask < (1<<m); ++mask){
			for(auto x : allMasks[a[i]]){
                //cerr << x << ' ';
				if(((x & mask) == x) and dp[i-1][mask^x]){
					dp[i][mask] = 1;
					//cerr << i << ' ' << mask << '\n';
					break;
				}
			}
		}
	}
	for(int i = 0; i < (1<<m); ++i){
		ans |=dp[n-1][i];
	}
	if(ans){
		cout<<"YES\n";
	} else {
		cout << "NO\n";
	}
}

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