Submission #1127937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127937		nolqf	Bank (IZhO14_bank)	C++20	0 / 100	0 ms	324 KiB

bank

#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;
using ll = long long;

ifstream fin( "bank.in" );
ofstream fout( "bank.out" );

const int DIM = 20;
const int INF = 2e9;

int s[DIM], b[DIM];
int rem[1 << DIM];

int main() {
  ios_base::sync_with_stdio(0);
  fin.tie(0);
  int n, m;

  fin >> n >> m;
  for ( int i = 0; i < n; ++i ) {
    fin >> s[i];
  }
  for ( int i = 0; i < m; ++i ) {
    fin >> b[i];
  }
  vector<int> pref(1 << m, -1);
  pref[0] = 0;
  for ( int mask = 0; mask < (1 << m); ++mask ) {
    for ( int i = 0; i < m; ++i ) {
      int prev_mask = mask ^ (1 << i);
      if ( !(mask & (1 << i)) || pref[prev_mask] == -1 ) continue;
      int need = s[pref[prev_mask]];
      int sum = rem[prev_mask] + b[i];
      if ( sum == need ) {
        if ( pref[mask] < pref[prev_mask] + 1 ) {
          pref[mask] = pref[prev_mask] + 1;
          rem[mask] = 0;
        }
      } else if ( sum < need ) {
        if ( pref[mask] < pref[prev_mask] ) {
          pref[mask] = pref[prev_mask];
          rem[mask] = sum;
        }
      }
    }
    if ( n == pref[mask] ) {
      fout << "YES\n";
      return 0;
    }
  }
  fout << "NO\n";
  fin.close();
  fout.close();
  return 0;
}

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