Submission #551087

#	Time	Username	Problem	Language	Result	Execution time	Memory
551087		fcw	Bank (IZhO14_bank)	C++17	100 / 100	115 ms	8672 KiB

bank

#include <bits/stdc++.h>
#define st first
#define nd second
using lint = int64_t;
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr lint linf = 0x3f3f3f3f3f3f3f3f;
using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int n, m;
	cin>>n>>m;
	vector<int>a(n), b(m);
	for(int& i : a) cin>>i;
	for(int& i : b) cin>>i;
	vector<int>dp(1<<m, -1), cnt(1<<m, -1);
	dp[0] = cnt[0] = 0;
	for(int mask=0;mask<1<<m;mask++){
		if(dp[mask] == -1) continue;
		if(dp[mask] == n){
			cout<<"YES\n";
			return 0;
		}
		for(int i=0;i<m;i++){
			if(mask>>i&1) continue;
			if(cnt[mask] + b[i] < a[dp[mask]]){
				cnt[mask|(1<<i)] = cnt[mask] + b[i];
				dp[mask|(1<<i)] = dp[mask];
			}
			else if(cnt[mask] + b[i] == a[dp[mask]]){
				cnt[mask|(1<<i)] = 0;
				dp[mask|(1<<i)] = dp[mask] + 1;
			}
		}
	}
	cout<<"NO\n";



	return 0;
}

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