Submission #1004733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004733		liaochengle	Bank (IZhO14_bank)	C++17	0 / 100	3 ms	29016 KiB

bank

#include <bits/stdc++.h>
using namespace std;

const int N =20;
const int M =21;
//前m个banknote, N
int dp[M][1<<N];
int salary[N];
int banknote[M];

int main(){

    
    int n, m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
	cin>>salary[i];
    for(int i=0;i<m;i++)
	cin>>banknote[i];

    for(int i=0;i<=m;i++)
	dp[i][0] = 1;

    for(int s=1;s<(1<<n);s++  ){
	for(int bk=1;bk<=m;bk++){
	    dp[bk][s] = dp[bk-1][s];
	    for(int p=0;p<n;p++){
		//cout<<'p'<<p<<'\n';
		if((s&(1<<p))==0)
		    continue;
		int ind = bk-1;
		int sum = 0;
		while(sum < salary[p] && ind>=0){
		    sum += banknote[ind];
		    ind--;
		}
		if(ind<0 || sum != salary[p]){
		    continue;
		}
		ind++;
		//cout<<"now "<<bk<<' '<<bitset<5>(s)<<' '<<bitset<5>(s^(1<<p))<<' '<<(ind-1)<<' '<<dp[ind][s^(1<<p)]<<'\n';
		dp[bk][s] = max(dp[bk][s], dp[ind][s^(1<<p)]);
	    }
	}
    }
    if(dp[m][(1<<n)-1])
	cout<<"YES\n";
    else
	cout<<"NO\n";
    return 0;

}

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