Submission #1196482

#TimeUsernameProblemLanguageResultExecution timeMemory
1196482mkrtich_2010_Bank (IZhO14_bank)C++20
71 / 100
1102 ms166968 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); vector<int> b(m); vector<vector<int>> dp(1 << m, vector<int>(n)); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < m; i++) cin >> b[i]; vector<vector<int>> c(1001); for (int i = 0; i < (1 << m); i++) { int sum = 0; for (int j = 0; j < m; j++) { if (i & (1 << j)) { sum += b[j]; } if (sum <= 1000) c[sum].push_back(i); } } for (auto i : c[a[0]]) { dp[i][0] = 1; } for (int i = 0; i < (1 << m); i++) { for (int j = 0; j < n - 1; j++) { if (dp[i][j] == 0) continue; for (int k : c[a[j + 1]]) { if (i & k) continue; dp[i | k][j + 1] = 1; } } if (dp[i][n - 1] == 1) { cout << "YES" << endl; return 0; } } cout << "NO" << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...