Submission #1202985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202985		lmquan	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4108 ms	92468 KiB

subsequence

#define taskname ""
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int kN = 100005;
const int kB = 10;

struct T {
  int i, j, k;
  T(int _i = -1, int _j = -1, int _k = -1) : i(_i) , j(_j), k(_k) {}
};

int n, a[kN], k[kN], d[kN], trace[kN];
pair<int, int> dp[(1 << kB) + 1][(1 << kB) + 1][kB + 1];
vector<int> p;

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  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 = 0; i <= (1 << kB); i++) {
    for (int j = 0; j <= (1 << kB); j++) {
      for (int k = 0; k <= kB; k++) {
        dp[i][j][k] = make_pair(0, -1);
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    d[i] = 1;
  }
  memset(trace, -1, sizeof trace);

  for (int i = 1; i <= n; i++) {
    int l = a[i] >> kB, r = a[i] % (1 << kB);
    for (int j = 0; j < (1 << kB); j++) {
      if (k[i] >= __builtin_popcount(j & l) && (k[i] - __builtin_popcount(j & l)) <= kB && dp[j][r][k[i] - __builtin_popcount(j & l)].first + 1 > d[i]) {
        d[i] = dp[j][r][k[i] - __builtin_popcount(j & l)].first + 1;
        trace[i] = dp[j][r][k[i] - __builtin_popcount(j & l)].second;
      }
    }
    for (int j = 0; j < (1 << kB); j++) {
      if (d[i] > dp[l][j][__builtin_popcount(r & j)].first) {
        dp[l][j][__builtin_popcount(r & j)] = make_pair(d[i], i);
      }
    }
  }

  int ind = -1, len = 0;
  for (int i = 1; i <= n; i++) {
    if (d[i] > len) {
      len = d[i];
      ind = i;
    }
  }
  cout << len << '\n';

  for (int i = ind; i != -1; i = trace[i]) {
    p.push_back(i);
  }

  reverse(p.begin(), p.end());
  for (int x : p) {
    cout << x << ' ';
  }

  return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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