Submission #1225557

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225557		vyaduct	Bank (IZhO14_bank)	C++20	100 / 100	101 ms	8620 KiB

bank

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int mxN = 20;
const int mxD = 1<<mxN;
int a[mxN];
int b[mxN];
int dp[mxD][2];

void solve(){
  int n,m; cin>>n>>m;
  for (int i=0;i<n;i++) cin>>a[i];
  for (int i=0;i<m;i++) cin>>b[i];
  bool ans=false;
  memset(dp, -1, sizeof(dp));
  dp[0][0] = 0;
  dp[0][1] = 0;
  for (int S=1;S<(1<<m);S++){
    // dp[S][0] = max prefix of ppl we can pay
    // dp[S][1] = leftover after paying them
    for (int i=0;i<m;i++){
      if (S & (1<<i) == 0) continue;
      int prev = S^(1<<i);
      if (dp[prev][0] == -1) continue;
    
      int have = dp[prev][1] + b[i];
      int need = a[dp[prev][0]];

      if (have < need){
        dp[S][0] = dp[prev][0];
        dp[S][1] = have;
      }
      else if (have == need){
        dp[S][0] = dp[prev][0]+1;
        dp[S][1] = 0;
      }
    }
    if (dp[S][0] == n) ans = true;
  }
  cout << (ans ? "YES" : "NO") << endl;
}

int main(){
  solve();
  return 0;
}

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