Submission #1321962

#TimeUsernameProblemLanguageResultExecution timeMemory
1321962vtnooBank (IZhO14_bank)C++20
100 / 100
159 ms16220 KiB
#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<int>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<int, int>
using namespace std;
const int MAXN=2e5+5,LOG=20,INF=1e9;
int sum[1<<20],memo[1<<20];
vi comp[20005],a,b,pref;
bool dfs(int mask){
	if(memo[mask]!=-1)return memo[mask];
	int idx=find(all(pref),sum[mask])-pref.begin();
	if(idx==sz(pref)){
		return memo[mask]=0;
	}
	if(idx==sz(pref)-1)return memo[mask]=1;
	int target=a[idx];
	for(auto nxtMask:comp[target]){
		if((nxtMask&mask)==0){
			memo[mask]=dfs(nxtMask|mask);
			if(memo[mask])return 1;
		}
	}
	return memo[mask]=0;
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	int n,m;cin>>n>>m;
	a.resize(n),b.resize(m);
	L(i,0,n-1)cin>>a[i];
	pref.resize(n+1,0);
	L(i,0,n-1)pref[i+1]=pref[i]+a[i];
	L(i,0,m-1)cin>>b[i];
	L(mask,0,(1<<m)-1){
		int s=0;
		L(i,0,m-1){
			if((1<<i)&mask)s+=b[i];
		}
		sum[mask]=s;
		comp[s].pb(mask);
	}
	me(memo,-1);
	cout<<(dfs(0)?"YES":"NO")<<endl;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...