제출 #952896

#제출 시각아이디문제언어결과실행 시간메모리
952896NeroZeinLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
49 ms860 KiB
#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int N = 5002;

int a[N], k[N];
int dp[N], pre[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> k[i];
  }
  for (int i = 1; i <= n; ++i) {
    dp[i] = 1; 
    for (int j = 1; j < i; ++j) {
      if (__builtin_popcount(a[i] & a[j]) == k[i]) {
        if (dp[i] <= dp[j]) {
          dp[i] = dp[j] + 1;
          pre[i] = j; 
        }
      }
    }
  }
  int ind = max_element(dp + 1, dp + 1 + n) - dp;
  vector<int> seq;
  while (ind) {
    seq.push_back(ind); 
    ind = pre[ind]; 
  }
  reverse(seq.begin(), seq.end()); 
  cout << seq.size() << '\n';
  for (int i : seq) {
    cout << i << ' ';
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...