Submission #657469

#	Time	Username	Problem	Language	Result	Execution time	Memory
657469		marche	Bank (IZhO14_bank)	C++14	100 / 100	108 ms	8532 KiB

bank

#include<bits/stdc++.h>
using namespace std;
#define fr first
#define sc second
pair<int,int> dp[(1 <<20)];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;	
	cin >> n >> m;
	vector<int>a(n);
	vector<int>b(m);
	for (int i= 0 ; i<n; i++)cin >> a[i];
	for(int i = 0; i<m; i++)cin >> b[i];
	// let S be a binary number < 2^n which indicates which people have already received salary
	// dp[s][]
	// look at problem from another perspective
	// let S be a binary number indicating which bank notes have been taken
	// dp[s][i] = max number of people with S notes taken if i people have been considered
	// dp[s] inidcates how many people can be payed if S = {1,1,1,1,0,0,1,0,1..,0}have been taken
	
	memset(dp, -1, sizeof(dp));
	dp[0] = {0,0};
	for (int i = 0; i<(1 << m); i++){
	    for (int j = 0; j<m; j++){
	       if ((1 << j) & i == 0)continue;
	       int p = i ^ (1 << j);
	       if (dp[p].fr == -1)continue;
	       int nx = dp[p].sc + b[j];
	       if (nx == a[dp[p].fr]){
	           dp[i].fr = dp[p].fr + 1;
	           dp[i].sc = 0;
	       }else if (nx < a[dp[p].fr]){
	           dp[i].fr = dp[p].fr;
	           dp[i].sc = nx;
	       }
	    }
	    if (dp[i].fr == n){
	        cout<<"YES"<<endl;
	        return 0;
	    }
	}
	cout<<"NO";
	return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:22:27: warning: 'void* memset(void*, int, size_t)' writing to an object of type 'struct std::pair<int, int>' with no trivial copy-assignment [-Wclass-memaccess]
   22 |  memset(dp, -1, sizeof(dp));
      |                           ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from bank.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~
bank.cpp:26:26: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   26 |         if ((1 << j) & i == 0)continue;
      |                        ~~^~~~

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