제출 #873788

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
873788		Irate	은행 (IZhO14_bank)	C++14	0 / 100	1097 ms	18844 KiB

bank

#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<int>a, b;
vector<vector<int>>lookup;
vector<int>sums, pref;
int dp[21][(1 << 20)];

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	a.resize(n);
	b.resize(m);
	sums.resize((1 << m));
	lookup.resize(2e4 + 3);
	pref.resize(m);
	for(int i = 0;i < n;++i){
		cin >> a[i];
	}
	for(int i = 0;i < m;++i){
		cin >> b[i];
	}
	pref[0] = b[0];
	for(int i = 1;i < m;++i){
		pref[i] = pref[i - 1] + b[i];
	}
	for(int i = 0;i < (1 << m);++i){
		int sum = 0;
		for(int j = 0;j < m;++j){
			if((i & (1 << j))){
				sum += b[j];
			}
		}
		lookup[sum].push_back(i);
		sums[i] = sum;
	}
	for(int j = 0;j < (1 << m);++j){
		dp[n][j] = 1;
	}
	for(int i = n - 1;i >= 0;--i){
		for(int mask = 0;mask < (1 << m);++mask){
			int chosen = (1 << m) ^ mask;
			if(i >= 1 && sums[chosen] != pref[i - 1])continue;
			for(int &submask : lookup[a[i]]){
				if((mask & submask) == submask){
					dp[i][mask] |= dp[i + 1][mask ^ submask];
				}
			}
		}
	}
	if(dp[0][(1 << m) - 1]){
		cout << "YES";
	}
	else{
		cout << "NO";
	}
}	

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