Submission #1240098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240098		MasterDebater	Bank (IZhO14_bank)	C++20	71 / 100	1094 ms	11656 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<<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;
}

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