Submission #681675

#	Time	Username	Problem	Language	Result	Execution time	Memory
681675		tvladm2009	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4449 ms	126196 KiB

subsequence

#include <bits/stdc++.h>

using ll = long long;

int const nmax = 100000;
int const base = 10;

int v[5 + nmax], k[5 + nmax];
std::pair<int,int> dp[(1 << base)][(1 << base)][5 + base], sol[5 + nmax];

std::pair<int,int> compare(std::pair<int,int> f1, std::pair<int,int> f2) {
  if(f1.first >= f2.first)
    return f1;
  return f2;
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);

  int n;
  std::cin >> n;
  for(int i = 1;i <= n; i++)
    std::cin >> v[i];
  for(int i = 1;i <= n; i++)
    std::cin >> k[i];

  for(int mask1 = 0;mask1 < (1 << base); mask1++)
    for(int mask2 = 0;mask2 < (1 << base); mask2++)
      for(int i = 0;i <= 10; i++)
        dp[mask1][mask2][i] = {0, 0};
  for(int i = 1;i <= n; i++) {
    int high = (v[i] >> base);
    int low = (v[i] & ((1 << base) - 1));
    sol[i] = {1, 0};
    for(int mask = 0;mask < (1 << base); mask++) {
      int cnt = __builtin_popcount(high & mask);
      int need = k[i] - cnt;
      if(need < 0 || need > base)
        continue;
      sol[i] = compare(sol[i], {dp[mask][low][need].first + 1, dp[mask][low][need].second});
    }
    for(int mask = 0;mask < (1 << base); mask++) {
      int cnt = __builtin_popcount(low & mask);
      if(cnt < 0 || cnt > base)
        continue;
      dp[high][mask][cnt] = compare(dp[high][mask][cnt], {sol[i].first, i});
    }
  }

  int ind = 1;
  for(int i = 1;i <= n; i++)
    if(compare(sol[ind], sol[i]) == sol[i])
      ind = i;
  std::vector<int> seq;
  while(ind > 0) {
    seq.push_back(ind);
    ind = sol[ind].second;
  }
  std::reverse(seq.begin(), seq.end());
  std::cout << seq.size() << "\n";
  for(int i = 0;i < seq.size(); i++)
    std::cout << seq[i] << " ";
  return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(int i = 0;i < seq.size(); i++)
      |                 ~~^~~~~~~~~~~~

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