Submission #1240108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240108		MasterDebater	Bank (IZhO14_bank)	C++20	100 / 100	433 ms	59904 KiB

bank

#include<bits/stdc++.h>
using namespace std;
const int p=(1<<20),N=20+5;
int n,m,a[N],b[N],dp[N][p];
vector<int>v[10001];
bool solve(int i,int bm){
	if(i==n)return 1;
	if(bm==0)return 0;
	bool res=0;
	for(int j=0;j<v[a[i]].size();j++){
		int br=v[a[i]][j];
		if((bm&br)==br and !dp[i+1][bm^br]){
			dp[i+1][bm^br]=1;
			res|=solve(i+1,bm^br);
		}
	}
	return res;
}
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,(1<<m)-1))cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}

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