Submission #1263734

#TimeUsernameProblemLanguageResultExecution timeMemory
1263734backBank (IZhO14_bank)C++20
0 / 100
1 ms836 KiB
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n), b(m); for (int &x : a) cin >> x; for (int &x : b) cin >> x; int sumA = accumulate(a.begin(), a.end(), 0); int sumB = accumulate(b.begin(), b.end(), 0); if (sumA != sumB) { cout << "NO\n"; return 0; } int N = 1 << m; vector<int> sum(N, 0); for (int mask = 1; mask < N; mask++) { int lb = mask & -mask; int bit = __builtin_ctz(lb); sum[mask] = sum[mask ^ lb] + b[bit]; } vector<vector<int>> subs(sumA + 1); for (int mask = 0; mask < N; mask++) { if (sum[mask] <= sumA) subs[sum[mask]].push_back(mask); } vector<char> dp(N, 0); dp[0] = 1; for (int x : a) { vector<char> ndp(N, 0); for (int mask = 0; mask < N; mask++) if (dp[mask]) { int rem = (~mask) & (N - 1); for (int sub : subs[x]) { if ((sub & mask) == 0) ndp[mask | sub] = 1; } } dp.swap(ndp); } cout << (dp[N - 1] ? "YES\n" : "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...