Submission #1294771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294771		LIA	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3218 ms	129904 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)
#define pll pair<ll, ll>
struct State {
  int len, end;
};
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  int mx = 1026;
  v<v<int>> ba(mx, v<int>(mx));

  lp(i, 0, mx) {
    lp(j, 0, mx) { ba[i][j] = __builtin_popcount(i & j); }
  }
  v<int> a(n), k(n);

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

  int ans = 1;
  v<int> pr(n);
  iota(pr.begin(), pr.end(), 0);

  v<v<v<State>>> dp(mx + 1, v<v<State>>(mx + 1, v<State>(11, {0, -1})));
  int sh = 10;
  int best_idx = 0;
  lp(i, 0, n) {
    int l = a[i] >> 10;
    int r = a[i] % (1 << 10);
    int lbs = 1;
    lp(j, 0, mx) {
      ll need = k[i] - ba[j][l];
      if (need < 0 || need > 10)
        continue;
      if (dp[j][r][need].len + 1 > lbs) {
        lbs = dp[j][r][need].len + 1;
        pr[i] = dp[j][r][need].end;
      }
    }

    if (lbs > ans) {
      ans = lbs;
      best_idx = i;
    }
    lp(j, 0, mx) {
      State &NS = dp[l][j][ba[r][j]];
      if (lbs > NS.len) {
        NS.len = lbs;
        NS.end = i;
      }
    }
  }

  cout << ans << '\n';
  vector<int> res;

  while (pr[best_idx] != best_idx) {
    res.push_back(best_idx);
    best_idx = pr[best_idx];
  }
  res.push_back(best_idx);
  reverse(res.begin(), res.end());
  for (int x : res) {
    cout << x + 1 << " ";
  }
}

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