Submission #672490

#	Time	Username	Problem	Language	Result	Execution time	Memory
672490		dsyz	Bank (IZhO14_bank)	C++17	100 / 100	125 ms	16768 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	ll A[N];
	ll B[M];
	for(ll i = 0;i < N;i++){
		cin>>A[i];
	}
	for(ll i = 0;i < M;i++){
		cin>>B[i];
	}
	bool ok = 0;
	pair<ll,ll> dp[1ll<<M]; //maximum prefix of A done by bitmask, remaining sum of B not used 
	memset(dp,0,sizeof(dp));
	for(ll i = 0;i < (1ll << M);i++){
		for(ll j = 0;j < M;j++){
			if(!((i >> j) & 1)){
				continue;
			}
			ll k = i ^ (1 << j); //previous state without jth banknote
			pair<ll,ll> res = dp[k];
			res.second += B[j];
			if(A[res.first] == res.second){
				res.first++;
				res.second = 0;
			}
			dp[i] = max(dp[i],res);
			if(dp[i].first >= N) ok = 1;
		}
	}
	if(ok){
		cout<<"YES"<<'\n';
	}else{
		cout<<"NO"<<'\n';
	}
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:19:24: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<long long int, long long int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   19 |  memset(dp,0,sizeof(dp));
      |                        ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from bank.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<long long int, long long int>' declared here
  211 |     struct pair
      |            ^~~~

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