Submission #342041

#	Time	Username	Problem	Language	Result	Execution time	Memory
342041		casperwang	Bank (IZhO14_bank)	C++14	100 / 100	148 ms	8684 KiB

bank

#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
template<class T> bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
template<class T> bool chmax(T &a, T b) { return b > a ? (a = b, true) : false; }
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template<class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 20;
int n, m;
int a[MAXN];
int b[MAXN];
pii dp[1<<MAXN];
bool tf;

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }
  sort(b, b+m, greater<int>());
  for (int i = 1; i < (1<<m); i++) {
    dp[i] = pii(-1, -1);
    for (int j = 0; j < m; j++) {
      if (!(i&(1<<j))) continue;
      pii tmp = dp[i^(1<<j)];
      if (tmp.ss + b[j] == a[tmp.ff]) {
        tmp.ff++, tmp.ss = 0;
      } else if (tmp.ff < n && tmp.ss + b[j] < a[tmp.ff]) {
        tmp.ss += b[j];
      }
      dp[i] = max(dp[i], tmp);
    }
  }
  for (int i = 1; i < (1<<m); i++) {
    if (dp[i].ff == n) tf = 1;
  }
  cout << (tf ? "YES\n" : "NO\n");
}

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