제출 #1128669

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1128669		nlkn	은행 (IZhO14_bank)	C++20	100 / 100	87 ms	8616 KiB

bank

// 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";
}

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