Submission #1110579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110579		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	141 ms	88908 KiB

bank

#include <iostream>
#include <vector>
#include <iomanip>
#include <cstring>
using namespace std;

int n, m;
int ppl[20], note[20];
int dp[20][1<<20];
vector<int> sumIndex[1001];


void buildSumIndex() {
  vector<int> sums(1 << m, 0);
  for (int i = 0; i < (1 << m); ++i) {
    for (int j = 0; j < m; ++j) {
      if ((1 << j) & i) {
        sums[i] = note[j] + sums[(1<<j) ^ i];
        if (sums[i] <= 1000) {
          sumIndex[sums[i]].push_back(i);
        }
        break;
      }
    }
  }
}


int solve(int kPpl, int freeNote) {
  if (kPpl == n) return 1;
  if (dp[kPpl][freeNote] != -1) return dp[kPpl][freeNote];

  dp[kPpl][freeNote] = 0;
  for (auto s : sumIndex[ppl[kPpl]]) {
    if ((s & freeNote) == s) {
      dp[kPpl][freeNote] = solve(kPpl + 1, (s ^ freeNote));
      if (dp[kPpl][freeNote]) break;
    }
  }
  return dp[kPpl][freeNote];
}


int main() {
  cin >> n >> m;
  for (int i = 0; i < n; ++i) cin >> ppl[i];
  for (int i = 0; i < m; ++i) cin >> note[i];

  buildSumIndex();
  memset(dp, -1, sizeof(dp));
  int ans = solve(0, (1 << m) - 1);
  cout << (ans ? "YES" : "NO") << endl;

  return 0;
}

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