제출 #952891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
952891		NeroZein	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	3 ms	21596 KiB

subsequence

#include "bits/stdc++.h"
using namespace std;

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int M = 1 << 10; 
const int N = 1e5 + 5; 

int a[N], k[N];
int dp[N], pre[N];
int best[M][M][10], id[M][M][10];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i]; 
  }
  for (int i = 1; i <= n; ++i) {
    cin >> k[i]; 
  }
  
  for (int i = 1; i <= n; ++i) {
    for (int x = 0; x < M; ++x) {//fix first 10 bits.
      int t = k[i] - __builtin_popcount(a[i] & x); 
      if (t < 0) continue; 
      int suf = a[i] >> 10;
      if (best[x][suf][t] >= dp[i]) {
        dp[i] = best[x][suf][t] + 1;
        pre[i] = id[x][suf][t];
      }
    }
    for (int x = 0; x < M; ++x) {
      int pref = a[i] & (M - 1);
      int cnt = __builtin_popcount(a[i] & x);
      if (dp[i] > best[pref][x][cnt]) {
        id[pref][x][cnt] = i; 
        best[pref][x][cnt] = dp[i]; 
      }
    }
  }
  int ind = max_element(dp + 1, dp + 1 + n) - dp;
  vector<int> seq;
  while (ind) {
    seq.push_back(ind); 
    ind = pre[ind]; 
  }
  reverse(seq.begin(), seq.end()); 
  cout << seq.size() << '\n';
  for (int i : seq) {
    cout << i << ' ';
  }
  return 0;
}

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