Submission #667558

#	Time	Username	Problem	Language	Result	Execution time	Memory
667558		I_love_Chou_Giang	Bank (IZhO14_bank)	C++14	100 / 100	96 ms	8524 KiB

bank

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

typedef long long ll;

#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

#define R_EP(i, a, b, s) for (int i = (a); (s) > 0 ? i < (b) : i > (b); i += (s))
#define R_EP1(e) R_EP(i, 0, e, 1)
#define R_EP2(i, e) R_EP(i, 0, e, 1)
#define R_EP3(i, b, e) R_EP(i, b, e, 1)
#define R_EP4(i, b, e, s) R_EP(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define R_EPC(...) GET5(__VA_ARGS__, R_EP4, R_EP3, R_EP2, R_EP1)
#define rep(...) R_EPC(__VA_ARGS__)(__VA_ARGS__)
#define trav(x, a) for (auto x : a) 

template<typename T> inline bool umax(T&x, const T& y) { if (x >= y) return false; x = y; return true; }
template<typename T> inline bool umin(T&x, const T& y) { if (x <= y) return false; x = y; return true; }

const int MOD = int(1e9) + 7;

int N, M, a[20], b[20], nxt[1 << 20], f[1 << 20];

int main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);

  cin >> N >> M;
  rep(i, N) cin >> a[i];
  rep(i, M) cin >> b[i];

  memset(nxt, -1, sizeof(nxt));
  nxt[0] = 0;

  rep(mask, 1 << M) {
    rep(i, M) {
      if (~mask >> i & 1) {
        if (nxt[mask] == -1 || nxt[mask] == N) continue;
        int add = f[mask] + b[i];
        if (add < a[nxt[mask]]) {
          nxt[mask ^ (1 << i)] = nxt[mask];
          f[mask ^ (1 << i)] = add;
        } else if (add == a[nxt[mask]]) {
          nxt[mask ^ (1 << i)] = nxt[mask] + 1;
          f[mask ^ (1 << i)] = 0;
        }
      }
    }
  }

  bool ok = false;
  rep(mask, 1 << M) {
    ok = ok || nxt[mask] == N;
  }

  cout << (ok ? "YES" : "NO") << "\n";

  return 0;
}

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