Submission #1089923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089923		ventusliberum	Bank (IZhO14_bank)	C++17	100 / 100	86 ms	8784 KiB

bank

/**
 *    title:  Bank
**/
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define si(x) int(x.size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
template <class T, class U> inline bool chmax(T &a, U b) { return (a < b ? a = b, 1 : 0); }
template <class T, class U> inline bool chmin(T &a, U b) { return (b < a ? a = b, 1 : 0); }
template <class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { rep(i, si(v)) os << (i ? " " : "") << v[i]; return os; }
using ll = long long;
constexpr int inf = 1001001001;
constexpr long long infll = 4004004004004004004LL;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(m);
  cin >> a >> b;

  vector<int> dp(1<<m, -1);
  vector<int> rest(1<<m);
  dp[0] = 0;
  for (int i = 1; i < (1<<m); i++) {
    rep(j, m) {
      if (~i>>j&1) continue;
      int bits = i^1<<j;
      if (dp[bits] == -1) continue;
      int amt = rest[bits] + b[j];
      if (amt < a[dp[bits]]) {
        dp[i] = dp[bits];
        rest[i] = amt;
      } else if (amt == a[dp[bits]]) {
        dp[i] = dp[bits] + 1;
        rest[i] = 0;
      }
      if (dp[i] == n) {
        cout << "YES\n";
        return 0;
      }
    }
  }
  cout << "NO\n";
}

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