제출 #624336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
624336		ThinGarfield	은행 (IZhO14_bank)	C++11	100 / 100	103 ms	8528 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define mp make_pair
#define F first
#define S second

constexpr int maxn = 20;

int n, m;

int a[maxn];
int b[maxn];

pii note[1 << maxn];  // (can pay 1...k, leftover l)

int main() {
  // ios_base::sync_with_stdio(false);
  // cin.tie(NULL);

  bool ans = false;

  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> a[i];
  for (int i = 0; i < m; i++) cin >> b[i];

  for (int notes = 0; notes < (1 << m); notes++) {
    if (notes == 0) {
      note[notes] = mp(-1, 0);
      continue;
    }
    pii ansp = mp(-1, 0);
    for (int i = 0; i < m; i++) {
      if (!(notes & (1 << i))) continue;
      int prevnote = notes - (1 << i);
      int k = -1, l = -1;
      if (note[prevnote].S + b[i] == a[note[prevnote].F + 1]) {
        k = note[prevnote].F + 1;
        l = 0;
      } else {
        k = note[prevnote].F;
        l = note[prevnote].S + b[i];
      }
      // if (k > ansp.F) ansp = mp(k, l);
      ansp = max(ansp, mp(k, l));
    }
    note[notes] = ansp;
    // cout << bitset<5>(notes).to_string() << " : " << note[notes].F << '\t' << note[notes].S <<
    // '\n';
    if (ansp.F == n - 1) {
      ans = true;
      break;
    }
  }
  cout << (ans ? "YES\n" : "NO\n");

  return 0;
}

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