Submission #651935

#	Time	Username	Problem	Language	Result	Execution time	Memory
651935		pauloamed	Bank (IZhO14_bank)	C++14	100 / 100	440 ms	27732 KiB

bank

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

const int MAXS = 20010;
const int MAXN = 20;
const int MAXB = (1 << 20);
 
vector<int> salsum2masks[MAXS];
vector<int> notesum2masks[MAXS];

int T = 0;
bool fa[MAXN][MAXB];

vector<int> sos(vector<int> input, vector<int> query){
  for(auto x : input) fa[T][x] = 1;
 
  // SOS pd
  for(int i = 0;i < MAXN; ++i){
    for(int mask = 0; mask < MAXB; ++mask){
      if(mask & (1<<i)) fa[T][mask] += fa[T][mask^(1<<i)];
    }
  }
  
  vector<int> ret;
  for(auto x : query){
    if(fa[T][x]) ret.push_back(x);
  }

  T++;
  return ret;
}
 
int main(){
  cin.tie(NULL)->sync_with_stdio(false);

  int n, m; cin >> n >> m;

  vector<int> sal(n);
  for(auto &x : sal) cin >> x;

  vector<int> notes(m);
  for(auto &x : notes) cin >> x;

  for(int i = 0; i < (1 << m); ++i){
    int sum = 0;
    for(int j = 0; j < m; ++j) if((i >> j) & 1){
      sum += notes[j];
    }
    notesum2masks[sum].push_back(i);
  }

  vector<int> curr_ans = notesum2masks[sal[0]];

  int sum = sal[0];
  for(int i = 1; i < n; ++i){
    sum += sal[i];
    curr_ans = sos(curr_ans, notesum2masks[sum]);
    if(curr_ans.empty()) break;
  }

  if(curr_ans.empty()) cout << "NO\n";
  else cout << "YES\n";

  

}

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