Submission #486570

#	Time	Username	Problem	Language	Result	Execution time	Memory
486570		ntabc05101	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2415 ms	53604 KiB

subsequence

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

#define taskname "radare"

const int mxN = 100001;
const int mxBit = 10;
const int hlfBit = 10;
const int mxMsk = 1 << 20;

array<int, 2> dp[mxBit + 1][mxMsk];
int nBit[mxMsk];

template<class T, class U>
bool maxz(T &a, U b) {
  if (a < b) {
    a = b; return true;
  }
  return false;
}

void sol() {
  int n; cin >> n;
  int a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  array<int, 2> res = {0, 0};
  int prv[n + 1];
  prv[0] = 0;
  for (int i = 1, y; i <= n; i++) {
    cin >> y;
    auto &x = a[i - 1];
    array<int, 2> cur = {0, 0};
    int lmsk = x >> 10, rmsk = x & 1023;
    for (int msk = 0; msk < 1024; msk++) {
      auto &c = nBit[rmsk & msk];
      if (c <= y && y - c <= hlfBit) {
        cur = max(cur, dp[y - c][(lmsk << 10) | msk]);
      }
    }
    prv[i] = -cur[1]; 
    cur[0]++; cur[1] = -i;
    res = max(res, cur);
    for (int msk = 0; msk < 1024; msk++) {
      auto &c = nBit[lmsk & msk];
      dp[c][(msk << 10) | rmsk] = max(dp[c][(msk << 10) | rmsk], cur);
    }
  }
  
  cout << res[0] << "\n";
  vector<int> ans;
  res[1] *= -1;
  while (res[1]) {
    ans.push_back(res[1]);
    res[1] = prv[res[1]];
  }
  reverse(ans.begin(), ans.end());
  for (auto &x: ans) {
    cout << x << " ";
  }
}

int main() {
  if (fopen(taskname".inp", "r")) {
    freopen(taskname".inp", "r", stdin);
    freopen(taskname".out", "w", stdout);
  }
  else {
    if (fopen(taskname".in", "r")) {
      freopen(taskname".inp", "r", stdin);
      freopen(taskname".out", "w", stdout);
    }
  }
  
  cin.tie(0)->sync_with_stdio(0);
  
  for (int msk = 0; msk < 1024; msk++) {
    nBit[msk] = __builtin_popcount(msk);
  }
  
  int tt = 1; //cin >> tt;
  for (int t = 1; t <= tt; t++) {
    sol(); cout << "\n";
  }
  
  return 0;
}

Compilation message (stderr)

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

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