oj.uz

Submission #1004716

# Submission time Handle Problem Language Result Execution time Memory
1004716 2024-06-21T13:12:19 Z liaochengle Bank (IZhO14_bank) C++14
0 / 100
 43 ms 412 KB 
#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(){
    freopen("bank.in","r",stdin);
    freopen("bank.out","w",stdout);
    
    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 bk=1;bk<=m;bk++){
	for(int s=1;s<(1<<n);s++){
	    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;

}

Compilation message

bank.cpp: In function 'int main()':
bank.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen("bank.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bank.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen("bank.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -