Submission #991244

#TimeUsernameProblemLanguageResultExecution timeMemory
991244hippo123Bank (IZhO14_bank)C++17
0 / 100
4 ms1116 KiB
#include <bits/stdc++.h>
using namespace std;

#define pr pair<int, int>
#define ll long long
#define pb push_back
#define f first
#define s second


int main(){
	int n, m; cin>>n>>m;
	multiset<int> a;
	vector<int> b(m);
	//int amax=0;
	for (int i=0; i<n; i++) {
		int temp; cin>>temp; 
	}
	for (int i=0; i<m; i++) cin>>b[i];
	
	
	vector<pair<multiset<int>, int>> dp(1<<m, {a, 0});
	
	for (int x=1; x<(1<<m); x++){
		
		pair<multiset<int>, int> mast=dp[x];
		multiset<int> nd=mast.f;
		
		for (int i=0; i<m; i++){
			if(x&(1<<i)){
				pair<multiset<int>, int> prev=dp[x^(1<<i)];				
				multiset<int> elem=prev.f;  int last=prev.s;
				
				last+=b[i];
				if(elem.find(last)!=elem.end()){
					elem.erase(last); last=0;
				}
				
				if(nd.size()>elem.size()){
					dp[x]={elem, last};
				}
				else if(nd.size()==elem.size()){
					if(mast.s<last){
						dp[x]={elem, last};
					}
				}
				else{;}
			}
			
		}
		
		//for (auto e: dp[x].f) cout<<e<<" ";
		//cout<<endl;
		//cout<<dp[x].s<<endl;
	}
	
	multiset<int> sf=dp[(1<<m)-1].f;
	if(sf.size()==0) 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...