Submission #731745

#	Time	Username	Problem	Language	Result	Execution time	Memory
731745		Juan	Bank (IZhO14_bank)	C++17	100 / 100	126 ms	8516 KiB

bank

#include<bits/stdc++.h>
using namespace std;
// #pragma GCC optimize(03)
// #define int long long
#define pii pair<int, int>
#define ff first
#define ss second
const int maxn = 22, INF = 0x3f3f3f3f;

int sal[maxn], notes[maxn];
pii dp[1<<(maxn-1)];

int32_t main(){
	ios::sync_with_stdio(false);
	int n, m; cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> sal[i];
	for(int i = 0; i < m; i++) cin >> notes[i];

	sal[n+1] = INF;
	dp[0] = {0, sal[1]};
	bool found = false;

	for(int mask = 1; mask < (1<<m); mask++){
		for(int e = 0; e < m; e++) if(mask & (1<<e)){
			pii aux = dp[mask^(1<<e)];
			if(aux.ss > notes[e]) aux.ss -= notes[e];
			else if(aux.ss == notes[e]) aux.ff++, aux.ss = sal[aux.ff+1];
			else if(aux.ss < notes[e]) aux.ff = -1;

			dp[mask] = max(dp[mask], aux);
		}

		if(dp[mask].ff == n) {found = true; break;}
	}

	if(found) cout << "YES\n";
	else cout << "NO\n";
}

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