제출 #1134967

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1134967		bleahbleah	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	5539 ms	170316 KiB

subsequence

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

//#ifndef DLOCAL
   //#define cin fin
   //#define cout fout
   //ifstream cin("subsequence.in");
   //ofstream cout("subsequence.out");
//#endif

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
#define real samiosugitralala
pii dp[1 << 20][20];
int ppc[1 << 20];

const int nmax = 2e5 + 5;
int lst[nmax], sum[nmax];
int v[nmax], k[nmax];

signed main() {
   for(int i = 0; i < (1 << 20); i++) ppc[i] = ppc[i >> 1] + (i & 1);
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n;
   for(int i = 1; i <= n; i++) cin >> v[i];
   for(int j = 1; j <= n; j++) cin >> k[j];
   reverse(v + 1, v + n + 1);
   reverse(k + 1, k + n + 1);
   const int B = 25001;
   pii globalbest(0, 0);
   for(int i = 1; i <= n; i++) {
      pii best = dp[v[i]][0];
      for(int j = i - 1; j % B != 0; j--) 
         if(ppc[v[j] & v[i]] == k[j]) best = max(best, make_pair(sum[j], j));
      tie(sum[i], lst[i]) = best;
      sum[i]++;
      globalbest = max(globalbest, make_pair(sum[i], i));
      
      if(i % B == 0) {
         //cerr << "wah\n";
         for(int step = 0; step < 20; step++) 
            for(int msk = 0; msk < (1 << 20); msk++) 
               dp[msk][step] = pii{0, 0};
         for(int j = 1; j <= i; j++) {
            if(k[j] > ppc[v[j]]) continue;
            dp[v[j]][k[j]] = max(dp[v[j]][k[j]], make_pair(sum[j], j));
         }
         pii a, b;
         for(int step = 0; step < 20; step++) {
            for(int msk = 0; msk < (1 << 20); msk++) {
               if(msk & (1 << step)) continue;
               for(int h = 0; h < 19; h++) {
                  a = dp[msk][h], b = dp[msk | (1 << step)][h];
                  dp[msk][h] = max(a, b);
                  dp[msk | (1 << step)][h] = max(a, dp[msk | (1 << step)][h + 1]);
               }
            }
         }
      }
   }
   
   cout << globalbest.first << '\n';
   vector<int> vo;
   while(globalbest.second != 0) {
      vo.emplace_back(globalbest.second);
      globalbest.second = lst[globalbest.second];
   }
   for(auto &x : vo) x = n + 1 - x, cout << x << ' ';
   cout << '\n';
   
   
   reverse(v + 1, v + n + 1);
   reverse(k + 1, k + n + 1);
   for(int i = 1; i < sz(vo); i++) {
      if(ppc[v[vo[i]] & v[vo[i - 1]]] != k[vo[i]]) { cerr << "muie\n"; while(true); }
   }
}

/**
      Binecuvanteaza Doamne Ukraina.
--
*/ 

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