Submission #673619

#	Time	Username	Problem	Language	Result	Execution time	Memory
673619		MADE_IN_HEAVEN	Bank (IZhO14_bank)	C++17	100 / 100	225 ms	9556 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define what(a) cout << (#a) << " is " << (a) << '\n';

const int N = 20;
string s;
int  n , m , a[N] , b[N];
pair<int , int> memo[1 << N];
bool visited[1 << N];

pair<int , int> dp(int mask) {

  if (mask == 0) {
    return make_pair(0 , 0);
  }

  if (visited[mask])
    return memo[mask];

  pair<int , int> res = make_pair(-1 , -1);

  for (int i = 0; i < m; i++) if(mask & (1 << i)) {
    auto prev = dp(mask - (1 << i));
    if(prev.first == -1 || prev.second == -1) continue;

    int pos = prev.first;

    if(prev.second + b[i] < a[pos]) res = max(res , make_pair(prev.first , prev.second + b[i]));
    if(prev.second + b[i] == a[pos]) res = max(res , make_pair(prev.first + 1 , 0));
  }

  visited[mask] = true;
  memo[mask] = res;

  if(res.first == n) {
    cout << "YES";
    exit(0);
  }

  return res;
}

void solve() {

  cin >> n >> m;

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

  dp((1 << m) - 1);

  cout << "NO";

  return;
}

int main() {

  //freopen("bank.in" , "r" , stdin);
  //freopen("bank.out" , "w" , stdout);

  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int tt = 1;
  // cin >> tt;
  while (tt--) {
    solve();
  }

  return 0;
}

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