Submission #1240101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240101		MasterDebater	Bank (IZhO14_bank)	C++20	71 / 100	153 ms	13868 KiB

bank

#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<<m)-1)return 0;
	dp[i][bm]=1;
	bool res=0;
	for(int j=0;j<v[a[i]].size();j++){
		if((v[a[i]][j]&bm)==0 and !dp[i+1][bm|v[a[i]][j]]){
			res|=solve(i+1,bm|v[a[i]][j]);
		}
	}
	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,0))cout<<"YES\n";
	else cout<<"NO\n";
	return 0;
}

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