제출 #902679

#제출 시각아이디문제언어결과실행 시간메모리
902679Ghetto은행 (IZhO14_bank)C++17
19 / 100
155 ms2516 KiB
#include <bits/stdc++.h> using namespace std; const int MAX_N = 20 + 2, MAX_M = MAX_N; int n, m; int a[MAX_N], b[MAX_M]; int pref_sum[MAX_N]; void precomp() { for (int i = 1; i <= n; i++) pref_sum[i] = pref_sum[i - 1] + a[i]; } bool dp[1 << MAX_M]; int main() { // freopen("bank.in", "r", stdin); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= m; i++) cin >> b[i]; precomp(); for (int mask = (1 << m) - 1; mask >= 0; mask--) { int b_sum = 0; for (int i = 1; i <= m; i++) if (mask & (1 << (i - 1))) b_sum += b[i]; if (upper_bound(a + 1, a + 1 + n, b_sum) == a + 1 + n) { dp[mask] = true; continue; } int left = *upper_bound(a + 1, a + 1 + n, b_sum) - b_sum; for (int i = 1; i <= m; i++) { if (mask & (1 << (i - 1))) continue; if (b[i] > left) continue; if (dp[mask ^ (1 << (i - 1))]) dp[mask] = true; } } cout << ((dp[0]) ? "YES" : "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...