Submission #404463

#	Time	Username	Problem	Language	Result	Execution time	Memory
404463		rama_pang	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4045 ms	183544 KiB

subsequence

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int N;
  cin >> N;
  vector<int> A(N);
  vector<int> B(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }

  const int LOG = 20;
  vector<pair<int, int>> dp(N);
  vector<vector<pair<int, int>>> opt(LOG + 1, vector<pair<int, int>>(1 << LOG, {-1, -1}));

  vector<int> popcount(1 << LOG);
  for (int i = 0; i < (1 << LOG); i++) {
    popcount[i] = __builtin_popcount(i);
  }

  for (int i = 0; i < N; i++) {
    dp[i] = {1, -1};
    int upperMe = A[i] >> (LOG / 2);
    int lowerMe = A[i] - (upperMe << (LOG / 2));
    for (int upper = 0; upper < (1 << (LOG / 2)); upper++) {
      int need = B[i] - popcount[upperMe & upper];
      if (0 <= need && need < LOG) {
        auto &v = opt[need][(upper << (LOG / 2)) + lowerMe];
        dp[i] = max(dp[i], {1 + v.first, v.second});
      }
    }
    for (int lower = 0; lower < (1 << (LOG / 2)); lower++) {
      auto &v = opt[popcount[lowerMe & lower]][(upperMe << (LOG / 2)) + lower];
      v = max(v, {dp[i].first, i});
    }
  }

  vector<int> ans;
  int i = max_element(begin(dp), end(dp)) - begin(dp);
  while (i != -1) {
    ans.emplace_back(i);
    i = dp[i].second;
  }

  reverse(begin(ans), end(ans));
  cout << ans.size() << '\n';
  for (auto a : ans) {
    cout << a + 1 << ' ';
  }
  cout << '\n';
  return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60