제출 #968283

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

bank

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

#define ll long long
int const N=21;
int const mod=1e9+7;

int sal[N];
int coin[N];
int prefix_done[1<<N];
int leftover[1<<N];
int main(){
	int n,m;
	cin>>n>>m;
	for (int i = 0; i < n; ++i)
		cin>>sal[i];
	for (int i = 0; i < m; ++i)
		cin>>coin[i];
	for (int i = 0; i < (1<<m); ++i){
		prefix_done[i]=-1;
		leftover[i]=-1;
	}
	leftover[0]=0;
	prefix_done[0]=0;
	for(int mask=0;mask<(1<<m);mask++){
		for(int c=0;c<m;c++){
			if(((1<<c)&mask)==0)
				continue;
			int mk=mask-(1<<c);
			int lft=leftover[mk]+coin[c];
			int man_tar=prefix_done[mk];
			if(prefix_done[mk]==-1)
				continue;
			if(sal[man_tar]==lft){
				prefix_done[mask]=man_tar+1;
				leftover[mask]=0;
			}
			else if(sal[man_tar]>lft){
				prefix_done[mask]=man_tar;
				leftover[mask]=lft;
			}
		}
		// cout<<mask<<' '<<prefix_done[mask]<<' '<<leftover[mask]<<endl;
		if(prefix_done[mask]==n){
			// cout<<mask<<endl;
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
	return 0;
}

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