Submission #1265051

#TimeUsernameProblemLanguageResultExecution timeMemory
1265051tranvinhhuy2010Bank (IZhO14_bank)C++20
100 / 100
94 ms8556 KiB
#include <bits/stdc++.h> using namespace std; const int base = (1 << 20) + 5; int n, m, a[25], b[25], sum[base], dp[base]; int main() { cin >> n >> m; for (int i=1; i<=n; i++) { cin >> a[i]; a[i] += a[i-1]; } for (int i=0; i<m; i++) cin >> b[i]; for (int mask=1; mask<(1 << m); mask++) { int i = __builtin_ctz(mask); sum[mask] = sum[mask ^ (1 << i)] + b[i]; } for (int mask=0; mask<(1 << m); mask++) { if (dp[mask]==n) { cout << "YES"; return 0; } int i = upper_bound(a+1, a+1+n, sum[mask]) - a; for (int j=0; j<m; j++) { if (mask >> j & 1) continue; int mask1 = mask | (1 << j); if (sum[mask1]>a[i]) continue; if (sum[mask1]<a[i]) dp[mask1] = max(dp[mask1], dp[mask]); else dp[mask1] = max(dp[mask1], dp[mask] + 1); } } cout << "NO"; 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...