Submission #88438

#	Time	Username	Problem	Language	Result	Execution time	Memory
88438		xiaowuc1	Bank (IZhO14_bank)	C++14	71 / 100	1082 ms	13352 KiB

bank

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, m;
int bases[20];
vector<int> masks[1001];

void analyze(unordered_set<int>& lhs, unordered_set<int>& rhs) {
  for(int out: lhs) {
    int mask = -1+(1<<m)-out;
    for(int t = mask; t >= 0; t--) {
      t &= mask;
      if(rhs.count(t)) {
        cout << "YES\n";
        exit(0);
      }
    }
  }
}

unordered_set<int> solve(vector<int> v, int leftover) {
  unordered_set<int> ret;
  ret.insert(0);
  for(int i = 0; i < v.size(); i++) {
    unordered_set<int> nret;
    for(int out2: ret) {
      for(int out: masks[v[i]]) {
        if(out&out2) continue;
        if(__builtin_popcount(out | out2) + (leftover + v.size()-i-1) > m) continue;
        nret.insert(out | out2);
      }
    }
    ret = nret;
  }
  return ret;
}

void solve() {
  cin >> n >> m;
  vector<int> a, b;
  {
    vector<int> values;
    for(int i = 0; i < n; i++) {
      int t;
      cin >> t;
      values.push_back(t);
    }
    sort(values.begin(), values.end());
    for(int i = 0; i < n; i++) {
      (i < n/2 ? a : b).push_back(values[i]);
    }
  }
  for(int i = 0; i < m; i++) cin >> bases[i];
  for(int mask = 1; mask < (1<<m); mask++) {
    int v = 0;
    int t = mask;
    while(v <= 1000 && t) {
      v += bases[__builtin_ctz(t)];
      t &= t-1;
    }
    if(v <= 1000) masks[v].push_back(mask);
  }
  unordered_set<int> reta = solve(a, b.size());
  unordered_set<int> retb = solve(b, a.size());
  if(reta.size() > retb.size()) {
    analyze(retb, reta);
  }
  else {
    analyze(reta, retb);
  }
  for(int outa: reta) {
    for(int outb: retb) {
      if((outa&outb) == 0) {
        cout << "YES\n";
        return;
      }
    }
  }
  cout << "NO\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
}

Compilation message (stderr)

bank.cpp: In function 'std::unordered_set<int> solve(std::vector<int>, int)':
bank.cpp:27:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
bank.cpp:32:71: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(__builtin_popcount(out | out2) + (leftover + v.size()-i-1) > m) continue;
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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