Submission #1313329

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313329		aiclo	은행 (IZhO14_bank)	C++20	100 / 100	354 ms	12600 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int sum[1 << 20];
int a[20], b[20];
int n, m;

void wczytaj(){
	cin >> n >> m;
	
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < m; i++) cin >> b[i];

}

void precompute(){
	for(int mask = 0; mask < (1 << m); mask++)
		for(int i = 0; i < m; i++)
			if(mask & (1 << i)) sum[mask] += b[i];
}

int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	wczytaj();	
	precompute();
	
	vector<bool> DP(1<<m);
	DP[0] = 1;
	
	unordered_map<int, vector<int>> sums;
	for(int mask = 0; mask < (1 << m); mask++) sums[sum[mask]].push_back(mask);
	
	for(int i = 0; i < n; i++){
		vector<bool> tmp(1<<m);
		for(int mask = 0; mask < (1 << m); mask++){
			if(!DP[mask]) continue;
			for(int submask: sums[a[i]]){
				if((submask & mask) == 0) tmp[mask | submask] = 1;
			}
		}
		DP = tmp;
	}
	
	for(int mask = 0; mask < (1 << m); mask++)
		if(DP[mask]){
			cout<<"YES";
			return 0;
		}
	cout<<"NO";
}

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