제출 #88442

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88442		xiaowuc1	은행 (IZhO14_bank)	C++14	71 / 100	1077 ms	15628 KiB

bank

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

mt19937 g1;

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

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

unordered_set<int> solve(vector<int> v, int leftover) {
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  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);
    }
    // shuffle(values.begin(), values.end(), g1);
    for(int i = 0; i < n; i++) {
      (i % 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();
}

컴파일 시 표준 에러 (stderr) 메시지

bank.cpp: In function 'std::unordered_set<int> solve(std::vector<int>, int)':
bank.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
bank.cpp:40: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