Submission #1312223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312223		nolqf	Bank (IZhO14_bank)	C++20	100 / 100	102 ms	8516 KiB

bank

#include <bits/stdc++.h>

using namespace std;

const int DIM = 1e3;

struct DPEntry {
  int max_pref, rem;
  
  bool operator< ( const DPEntry &oth ) const {
    return max_pref < oth.max_pref || (max_pref == oth.max_pref && rem < oth.rem); 
  }
};

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

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

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29