제출 #867830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
867830		pete555	은행 (IZhO14_bank)	C++17	100 / 100	100 ms	8848 KiB

bank

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

int main()
{
	int N, M;
	cin >> N >> M;
	int sala[N], bank[M];
	for(int& i: sala) cin >> i;
	for(int& i: bank) cin >> i;
	vector<int> covered(1<<M, -1); //maximum people covered from this subset
	vector<int> leftover(1<<M, -1); //leftover money from this subset
	covered[0] = 0; leftover[0] = 0;
	for(int mask=1; mask<(1<<M); mask++){
		for(int i=0; i<M; i++){
			if(!(mask&(1<<i))) continue;
			int prev = mask^(1<<i);
			if(leftover[prev] == -1) continue;
			int target = covered[prev];
			if(leftover[prev] + bank[i] < sala[target]){
				leftover[mask] = leftover[prev] + bank[i];
				covered[mask] = covered[prev];
			}
			else if(leftover[prev] + bank[i] == sala[target]){
				leftover[mask] = 0;
				covered[mask] = covered[prev] + 1;
			}
		}
		if(covered[mask] == N){
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
}

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