Submission #590796

#TimeUsernameProblemLanguageResultExecution timeMemory
590796MazaalaiBank (IZhO14_bank)C++17
100 / 100
115 ms8496 KiB
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
using I=int;
bool done;
I main(){
	I n,m,i,j;cin>>n>>m;
	I a[n],b[m];
	pair<I,I>dp[1<<m];
	for(i=0;i<n;i++)cin>>a[i];
	for(i=0;i<m;i++)cin>>b[i];
	sort(a,a+n);sort(b,b+m);
	dp[0]={0,0};
	for(i=1;i<(1<<m)&&!done;i++){
		dp[i]={0,0};
		for(j=0;j<m;j++){
			if(!(i&(1<<j))||dp[i].f>dp[i^(1<<j)].f)continue;
			pair<I,I>&tmp=dp[i^(1<<j)];
			if(tmp.f>dp[i].f)dp[i]=tmp;
			if(a[tmp.f]>=b[j]+tmp.s&&dp[i].s<b[j]+tmp.s)dp[i].s=b[j]+tmp.s;
		}
		if(dp[i].s==a[dp[i].f])dp[i]={dp[i].f+1,0};
		done|=dp[i].f==n;
	}
	cout<<(done?"YES":"NO")<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...