Submission #1240098

#TimeUsernameProblemLanguageResultExecution timeMemory
1240098MasterDebaterBank (IZhO14_bank)C++20
71 / 100
1094 ms11656 KiB
#include<bits/stdc++.h>
using namespace std;
const int p=(1<<20),N=20;
int n,m,a[N],b[N],dp[N][p];
vector<int>v[1001];
bool solve(int i,int bm){
	if(i==n)return 1;
	if(bm==(1<<n)-1)return 0;
	if(dp[i][bm]!=-1){
		dp[i][bm]=0;
		for(int j=0;j<v[a[i]].size();j++)if((v[a[i]][j]&bm)==0)dp[i][bm]|=solve(i+1,bm|v[a[i]][j]);
	}
	return dp[i][bm];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin>>n>>m;
	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++){
		int res=0;
		for(int j=0;j<m;j++)if((i>>j)&1)res+=b[j];
		//if(res==8)cout<<i<<'\n';
		v[res].push_back(i);
	}
	if(solve(0,0))cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...