Submission #1215951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215951		akamizane	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	37 ms	90696 KiB

subsequence

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

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif

#define int long long

const int B = 10;

int f[1 << 10][1 << 10][11];
vector<int> dp;

int comp(int x, int y){
   return dp[x] > dp[y] ? x : y;
}

void solve(){
   int n;
   cin >> n;
   memset(f, 0, sizeof f);
   vector<int> a(n + 1), k(n + 1), par(n + 1);
   dp.resize(n + 1);
   for (int i = 1; i <= n; i++) cin >> a[i];  
   for (int i = 1; i <= n; i++) cin >> k[i];
   debug(a, k);
   for (int i = 1; i <= n; i++){
      int l = a[i] & ((1 << B) - 1);
      int r = a[i] >> B;
      for (int j = 0; j < (1 << B); j++){
         int cur = k[i] - __builtin_popcount(j & r);
         if (cur >= 0){
            par[i] = comp(par[i], f[l][j][cur]);
         }
      }
      dp[i] = dp[par[i]] + 1;
      for (int j = 0; j < (1 << B); j++){
         f[j][r][__builtin_popcount(j & l)] = comp(f[j][r][__builtin_popcount(j & l)], i);
      }
   }
   int idx = max_element(dp.begin(), dp.end()) - dp.begin();
   vector<int> path;
   while(true){
      path.push_back(idx);
      idx = par[idx];
      if (!idx) break;
   }
   reverse(path.begin(), path.end());
   cout << path.size() << "\n";
   for (auto x : path) cout << x << " ";
}

int32_t main() {
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   int tt = 1;
   // cin >> tt;
   while(tt--) {
      solve();
   }
   return 0;
}

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