Submission #1226216

#TimeUsernameProblemLanguageResultExecution timeMemory
1226216chuchucharlesBank (IZhO14_bank)C++20
19 / 100
126 ms5544 KiB
#include <bits/stdc++.h> using namespace std; int n, m, a[25], b[25], sum[1 << 20]; bool dp[1 << 20]; signed main () { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; if (i) a[i] += a[i - 1]; } for (int i = 0; i < m; i++) cin >> b[i]; for (int mask = 0; mask < (1 << m); mask++) { sum[mask] = 0; for (int i = 0; i < m; i++) if (mask >> i & 1) sum[mask] += b[i]; } dp[0] = true; for (int mask = 0; mask < (1 << m); mask++) { if (!dp[mask]) continue; if (sum[mask] == a[n - 1]) { cout << "YES"; return 0; } auto it = upper_bound(a, a + n, sum[mask]); if (it == a + n) continue; int re = *it - sum[mask]; for (int i = 0; i < m; i++) { if (mask >> i & 1) continue; dp[mask | (1 << i)] = (b[i] <= re); } } cout << "NO"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...