제출 #989037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
989037		tch1cherin	은행 (IZhO14_bank)	C++17	100 / 100	140 ms	8796 KiB

bank

#include <bits/stdc++.h>
using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  vector<int> a(N);
  for (int &value : a) {
    cin >> value;
  }
  vector<int> b(M);
  for (int &value : b) {
    cin >> value;
  }
  vector<int> pref(N + 1);
  for (int i = 0; i < N; i++) {
    pref[i + 1] = pref[i] + a[i];
  }
  vector<int> dp(1 << M), sum(1 << M);
  dp[0] = 1;
  for (int mask = 1; mask < (1 << M); mask++) {
    for (int i = 0; i < M; i++) {
      if ((mask >> i) & 1) {
        sum[mask] += b[i];
      }
    }
    dp[mask] = -1;
    int P = upper_bound(pref.begin(), pref.end(), sum[mask]) - pref.begin();
    for (int i = 0; i < M; i++) {
      if ((mask >> i) & 1) {
        if (dp[mask ^ (1 << i)] == P || (dp[mask ^ (1 << i)] == P - 1 && pref[P - 1] == sum[mask])) {
          dp[mask] = P;
        }
      }
    }
  }
  cout << (dp.back() == N + 1 ? "YES\n" : "NO\n");
}

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