Submission #519610

#	Time	Username	Problem	Language	Result	Execution time	Memory
519610		Alex_tz307	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3383 ms	93424 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

void testCase() {
  int n;
  cin >> n;
  vector<int> a(n), k(n);
  for (int &x : a) {
    cin >> x;
  }
  for (int &x : k) {
    cin >> x;
  }
  /// len[i] =def= cel mai lung subsir care satisface proprietatile din enunt si se termina la pozitia i
  /// dp[trueMask][otherMask][set] =def= valoarea maxima len[i] de pana acum astfel incat a[i]
  /// are prima jumatate firstHalf = trueMask si count(secondHalf & otherMask) = set
  /// Astfel, cand vreau sa aflu len[i], pot fixa prima jumatate a mastii de dinainte,
  /// fie aceasta mask si ma intereseaza atunci pentru tranzitie dp[mask][secondHalf][need],
  /// unde need = k[i] - count(firstHalf & mask)
  /// Complexitate: O(N * sqrt(MAX_VAL))
  const int m = (1 << 10);
  const int lg = 10;
  vector<int> len(n, 1), last(n, -1), cnt(m);
  vector<vector<vector<int>>> dp(m, vector<vector<int>>(m, vector<int>(1 + lg, -1)));
  for (int i = 1; i < m; ++i) {
    cnt[i] = __builtin_popcount(i);
  }
  for (int i = 0; i < n; ++i) {
    int firstHalf = 0, secondHalf = 0;
    for (int bit = 0; (1 << bit) <= a[i]; ++bit) {
      if (a[i] & (1 << bit)) {
        if (bit < lg) {
          firstHalf |= (1 << bit);
        } else {
          secondHalf |= (1 << (bit - 10));
        }
      }
    }
    for (int mask = 0; mask < m; ++mask) {
      int need = k[i] - cnt[mask & firstHalf];
      if (0 <= need && need <= lg) {
        int index = dp[mask][secondHalf][need];
        if (index != -1 && len[i] < len[index] + 1) {
          len[i] = len[index] + 1;
          last[i] = index;
        }
      }
    }
    for (int mask = 0; mask < m; ++mask) {
      int common = cnt[mask & secondHalf];
      int index = dp[firstHalf][mask][common];
      if (index == -1 || len[index] < len[i]) {
        dp[firstHalf][mask][common] = i;
      }
    }
  }
  int pos = 0;
  for (int i = 1; i < n; ++i) {
    if (len[pos] < len[i]) {
      pos = i;
    }
  }
  vector<int> sol;
  while (pos != -1) {
    sol.emplace_back(pos + 1);
    pos = last[pos];
  }
  reverse(sol.begin(), sol.end());
  cout << sol.size() << '\n';
  for (int x : sol) {
    cout << x << ' ';
  }
  cout << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

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