제출 #1313328

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1313328		aiclo	은행 (IZhO14_bank)	C++20	71 / 100	1096 ms	4776 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;
	
	for(int i = 0; i < n; i++){
		vector<bool> tmp(1<<m);
		for(int mask = 0; mask < (1 << m); mask++){
			if(!DP[mask]) continue;
			
			int alter = ((1 << m) - 1) ^ mask;
			for(int submask = alter; submask; submask = (submask - 1) & alter)
				if(sum[submask] == a[i]) tmp[mask | submask] = true;
		}
		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: 0 / 29