제출 #590771

#제출 시각아이디문제언어결과실행 시간메모리
590771Mazaalai은행 (IZhO14_bank)C++17
100 / 100
130 ms8632 KiB
#include <bits/stdc++.h> #define ff first #define ss second using namespace std; const int N = 21; const int M = 1<<N; using VI = vector <int>; using PII = pair <int, int>; int n, m; int a[N], b[N], s[N]; PII dp[M]; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen("0.in", "r", stdin); // freopen("0.out", "w", stdout); cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; a[n] = 1e9; int full = (1<<m)-1; dp[0] = {0, 0}; for (int i = 1; i <= full; i++) { dp[i] = {0, 0}; for (int j = 0; j < m; j++) { int prev = i^(1<<j), num = b[j]; PII tmp = dp[prev]; if (i < prev || dp[i].ff > tmp.ff) continue; if (tmp.ff > dp[i].ff) dp[i] = tmp; if (a[tmp.ff] >= num+tmp.ss) dp[i].ss = max(dp[i].ss, num+tmp.ss); } if (dp[i].ss == a[dp[i].ff]) dp[i] = {dp[i].ff+1, 0}; } cout << (dp[full].ff == n ? "YES" : "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...