Submission #606793

#TimeUsernameProblemLanguageResultExecution timeMemory
606793jjianglyBank (IZhO14_bank)C++14
44 / 100
1081 ms320 KiB
#include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define siz(x) int(x.size()) #define ll long long #define ar array #define vt vector #define inf INT_MAX #define lnf LLONG_MAX const int nxm = int(2e5) + 7; int n, m, a[25], b[25]; namespace sub1 { void exe() { bool ok = false; function<void(int, int)> work = [&](int idx, int v) { if (idx == m) { ok = (v == a[0] ? true : ok); return; } work(idx + 1, v + b[idx]); work(idx + 1, v); }; work(0, 0); cout << (ok ? "YES" : "NO") << "\n"; } }; namespace sub2 { void exe() { vt<int> p(m); iota(all(p), 0); bool ok = false; do { int cnt = 0, sum = 0; for (int i = 0; i < m; ++i) { sum += b[p[i]]; if (sum == a[cnt]) { ++cnt; sum = 0; } if (cnt >= n) { break; } } if (cnt == n) { ok = true; } } while (next_permutation(all(p))); cout << (ok ? "YES" : "NO") << "\n"; } }; namespace sub4 { void exe() { vt<vt<int>> f(1005); for (int mask = 0; mask < (1 << m); ++mask) { int sum = 0; for (int i = 0; i < m; ++i) { if (mask >> i & 1) { sum += b[i]; } } if (sum <= 1000) { f[sum].push_back(mask); } } vt<bool> dp((1 << m), false); dp[0] = true; int tot = 0; for (int i = 0; i < n; ++i) { tot += a[i]; vt<bool> ndp((1 << m), false); ndp = dp; for (int j = 0; j < m; ++j) { for (int mask = 0; mask < (1 << m); ++mask) { if (mask >> j & 1 || !ndp[mask]) { continue; } ndp[mask ^ (1 << j)] = true; } } fill(all(dp), false); for (int v : f[tot]) { if (ndp[v]) { dp[v] = true; } } } bool ok = false; for (int mask = 0; mask < (1 << m); ++mask) { ok = dp[mask] ? true : ok; } cout << (ok ? "YES" : "NO") << "\n"; } }; int subtask() { if (n == 1) { return 1; } else if (n <= 10) { return 2; } return 4; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; ++i) { cin >> a[i]; } for (int i = 0; i < m; ++i) { cin >> b[i]; } if (n > m) { cout << "NO\n"; } if (subtask() == 1) { sub1::exe(); } else if (subtask() == 2) { sub2::exe(); } else { sub4::exe(); } 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...