Submission #1287186

#TimeUsernameProblemLanguageResultExecution timeMemory
1287186repmannLongest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
1668 ms83260 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...