제출 #1110579

#제출 시각아이디문제언어결과실행 시간메모리
1110579vjudge1은행 (IZhO14_bank)C++17
100 / 100
141 ms88908 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...