Submission #1312213

#TimeUsernameProblemLanguageResultExecution timeMemory
1312213nolqfBank (IZhO14_bank)C++20
19 / 100
72 ms8516 KiB
#include <bits/stdc++.h>

using namespace std;

const int DIM = 1e3;

struct DPEntry {
  int max_pref, rem;
};

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;

  cin >> n >> m;
  vector<int> a(n), b(m);
  for ( int i = 1; i <= n; ++i ) cin >> a[i];
  for ( int i = 0; i < m; ++i ) cin >> b[i];
  vector<DPEntry> dp(1 << m);
  dp[0] = {0, 0};
  for ( int mask = 1; mask < (1 << m); ++mask ) {
    for ( int i = 0; i < m; ++i ) {
      if ( !(mask & (1 << i)) ) continue;
      int p = dp[mask ^ (1 << i)].max_pref;
      int r = dp[mask ^ (1 << i)].rem;
      if ( r + b[i] == a[p + 1] ) {
        dp[mask] = {p + 1, 0};
      } else {
        dp[mask] = {p, r + b[i]};    
      }
    }
    if ( dp[mask].max_pref == n ) {
      cout << "YES\n";
      return 0;
    }
  }
  cout << "NO\n";
  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...