Submission #1294552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294552		LIA	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	1 ms	336 KiB

subsequence

//
// Created by liasa on 23/11/2025.
//
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v vector
#define lp(i, s, e) for (int i = s; i < e; ++i)

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

  int n;
  cin >> n;
  v<int> a(n), k(n);
  lp(i, 0, n) cin >> a[i];
  lp(i, 0, n) cin >> k[i];

  int ans = 0, idx = 0, mx = 257;
  v<v<int>> dp(n + 1, v<int>(mx, 1));
  v<v<int>> pr(n + 1, v<int>(mx, -1));

  set<int> in;
  lp(i, 1, n + 1) {
    dp[i] = dp[i - 1];
    pr[i] = pr[i - 1];
    ll val = a[i - 1];
    for (auto it : in) {
      ll dpv = dp[i - 1][it];
      ll andi = __builtin_popcount(it & val);
      if (andi == k[i - 1]) {
        if (dp[i][val] < dpv + 1) {
          dp[i][val] = dpv + 1;
          pr[i][val] = it;
        }
      }
    }
    in.insert(val);
    if (ans < dp[i][val]) {
      ans = dp[i][val];
      idx = i;
    }
  }
  cout << ans << '\n';

  ll cur_idx = idx;
  ll cur_num = a[idx - 1];
  v<ll> ansi;

  while (cur_idx != 0 && cur_num != -1) {
    ll nxt = pr[cur_idx][cur_num];
    ansi.push_back(cur_num);
    cur_num = nxt;
    cur_idx--;
  }

  reverse(ansi.begin(), ansi.end());
  for (auto it : ansi)
    cout << it << " ";
}

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