제출 #731745

#제출 시각아이디문제언어결과실행 시간메모리
731745Juan은행 (IZhO14_bank)C++17
100 / 100
126 ms8516 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...