Submission #807831

#	Time	Username	Problem	Language	Result	Execution time	Memory
807831		gun_gan	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	4249 ms	93280 KiB

subsequence

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

const int MX = 1e5 + 5;
int N;
int a[MX], k[MX];
pair<int,int> dp[1 << 10][1 << 10][11];
int pdp[MX], ddp[MX];

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);
      
      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 = 1; i <= N; i++) {
            int left = a[i] >> 10;
            int right = a[i] % (1 << 10);

            for(int l = 0; l < 1 << 10; l++) {
                  int b = k[i] - __builtin_popcount(l & left);
                  if(b < 0 || b > 10) continue;

                  if(dp[l][right][b].first + 1 > ddp[i]) {
                        ddp[i] = dp[l][right][b].first + 1;
                        pdp[i] = dp[l][right][b].second;
                  }
            }

            if(ddp[i] < 1) ddp[i] = 1;

            for(int r = 0; r < 1 << 10; r++) {
                  int b = __builtin_popcount(r & right);
                  if(dp[left][r][b].first < ddp[i]) {
                        dp[left][r][b].first = ddp[i];
                        dp[left][r][b].second = i;
                  }
            }
      }

      int pos = 0;
      for(int i = 1; i <= N; i++) {
            if(ddp[pos] < ddp[i]) 
                  pos = i;
      }

      vector<int> ans;
      while(1) {
            ans.push_back(pos);
            pos = pdp[pos];
            if(!ddp[pos]) break;
      }

      reverse(ans.begin(), ans.end());
      cout << ans.size() << '\n';
      for(auto x : ans) cout << x << " ";
      cout << '\n';
}

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