제출 #1301995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1301995		metalius	은행 (IZhO14_bank)	C++20	100 / 100	441 ms	24600 KiB

bank

#include <bits/stdc++.h>


using namespace std;


using ll = long long;


int a[21];
int notes[21];
bool dp[21][1<<20];

int sum[1<<20];

vector<int> sumst[20003];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,m; cin >> n >> m;
	for(int i = 1; i <= n;i++) {
		cin >> a[i];
	}
	for(int i = 0; i < m; i++) {
		cin >> notes[i];
	}
	
	sum[0] = 0;
	for(int i = 1; i < (1 << m); i++) {
		for(int j = 0; j < m; j++) {
			if((i >> j) & 1) {
				sum[i] += notes[j];
			}
		}
		sumst[sum[i]].push_back(i);
	}
	/*
for(auto &vc : sumst) {
		if(!vc.empty()) {
			cout << sum[vc[0]] << " ";
			for(auto el : vc) {
				cout << el << " ";
			}
			cout << "\n";
		}
	}
	*/
	dp[0][0] = true;
	int cursum = 0;
	for(int i = 1; i <= n; i++) {
		cursum += a[i];
		for(int s = 1; s < (1 << m); s++) {
			if(sum[s] != cursum) continue;
			for(auto el : sumst[a[i]]) {
				if((el & s) == el) {
					dp[i][s] = dp[i][s] || dp[i-1][s - el];
				}
			}
		}
	}
	bool ans = false;
	for(auto el : sumst[cursum]) {
		ans = ans ||  dp[n][el];
	}
	cout << (ans ? "YES":"NO");
	return 0;
}

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