Submission #1287186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287186		repmann	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	1668 ms	83260 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
int N;
int A[100096], K[100096];
struct State
{
  int i, x;
  const bool operator < (const State &s) const
  {
    return x < s.x;
  }
}DP[11][1 << 10][1 << 10];
int FROM[100096];
int CNT[1 << 10][1 << 10];
int main()
{
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  for(int i = 0; i < 1024; i++)
  {
    for(int j = 0; j < 1024; j++) CNT[i][j] = __builtin_popcount(i & j);
  }
  cin >> N;
  for(int i = 1; i <= N; i++) cin >> A[i];
  for(int i = 1; i <= N; i++) cin >> K[i];
  State best = {0, 0};
  for(int i = 1; i <= N; i++)
  {
    int pref = A[i] & 1023, suff = A[i] >> 10;
    State temp = {0, 0};
    for(int j = 0; j < 1024; j++)
    {
      int k = K[i] - CNT[pref][j];
      if((0 <= k) && (k <= 10)) temp = max(DP[k][j][suff], temp);
    }
    FROM[i] = temp.i;
    temp = {i, temp.x + 1};
    best = max(temp, best);
    for(int j = 0; j < 1024; j++)
    {
      int k = CNT[suff][j];
      DP[k][pref][j] = max(temp, DP[k][pref][j]);
    }
  }
  int index = best.i;
  stack <int> OUT;
  while(index)
  {
    OUT.push(index);
    index = FROM[index];
  }
  cout << OUT.size() << '\n';
  while(OUT.size()) {cout << OUT.top() << " \n"[OUT.size() == 1]; OUT.pop();}

  return 0;
}

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