제출 #1128669

#제출 시각아이디문제언어결과실행 시간메모리
1128669nlkn은행 (IZhO14_bank)C++20
100 / 100
87 ms8616 KiB
// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
int main() {
	int n,m; cin >> n >> m;
	int a[n],b[m],ind[1<<m],left[1<<m];
	bool works=false;
	for(int i=0; i<n; i++){
		cin>>a[i];	
	}
	for(int i=0; i<m; i++){
		cin>>b[i];	
						
	}
//	for(int i=0; i<(1<<m); i++)i
	memset(ind,2000000000,sizeof(ind));
	ind[0]=0;
	left[0]=a[0];
	for(int i=0; i<(1<<m); i++){
		if(ind[i]==2000000000)continue;
		for(int j=0; j<m; j++){
		
			int k=(1<<j);
			if(i&k)continue;
		//	cout<<i<<" "<<j<<" "<<b[j]<<" "<<left[i]<<endl;
			if(b[j]==left[i]){
				ind[i|k]=ind[i]+1;
				if(ind[i|k]==n){
					works=true;
					break;
				}
				left[i|k]=a[ind[i|k]];
			}else if(b[j]<left[i]){
				ind[i|k]=ind[i];
				left[i|k]=left[i]-b[j];
		//		cout<<(i|k)<<" "<<ind[i|k]<<" "<<left[i|k]<<endl;
			}
		}	
		
		if(works)break;
	}
	if(works)cout<<"YES";
	else cout<<"NO";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...