제출 #1178358

#제출 시각아이디문제언어결과실행 시간메모리
1178358GoBananas69은행 (IZhO14_bank)C++20
100 / 100
367 ms130768 KiB
#include <algorithm> #include <iostream> #include <vector> using namespace std; typedef long long ll; int n, m; vector<vector<int>> dp; bool solve(int curr, int i, vector<int> &a, vector<vector<int>> &sums) { if (i == n) { return true; } if (dp[curr][i] != -1) { return dp[curr][i] == 1; } int res = 0; for (int &j: sums[a[i]]) { if (j & curr) continue; if (solve(j | curr, i + 1, a, sums)) { return dp[curr][i] = 1; } } return dp[curr][i] = 0; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; vector<int> a(n), b(m); int mx = 0; for (int &i : a) cin >> i; for (int &i : b) { cin >> i; mx += i; } vector<vector<int>> sums(mx + 1); dp.resize((1 << m) + 1, vector<int>(n + 1, -1)); for (int i = 0; i<=(1 << n); ++i) { dp[1 << n][n] = 1; } int t = 1 << m; for (int i = 0; i < t; ++i) { int curr = 0; for (int j = 0; j < m; ++j) { if (i & (1 << j)) curr += b[j]; } if (curr > mx) continue; sums[curr].push_back(i); } for (int &i : a) { if (i > mx) { cout << "NO\n"; return 0; } if (sums[i].empty()) { cout << "NO\n"; return 0; } } if (solve(0, 0, a, sums)) { cout << "YES\n"; } else { cout << "NO\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...