Submission #345489

#	Time	Username	Problem	Language	Result	Execution time	Memory
345489		_ani	Longest beautiful sequence (IZhO17_subsequence)	C++17	40 / 100	6009 ms	2704 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1'000'02;
int k[N], a[N], dp[N], hrashqiverj[N], p[N], hrashq[258];
int main(){
    int n;
    cin >> n;
    bool ok = true;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] >= 256) ok = false;
    }
    for (int i = 0; i < n; i++)
        cin >> k[i];
    if (!ok){
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
            p[i] = i;
            for(int j = 0; j < i; j++) {
                int tmp = (a[j] & a[i]);
                if (__builtin_popcount(tmp) == k[i]) {
                    if(dp[i] < dp[j] + 1){
                        dp[i] = dp[j] + 1;
                        p[i] = j;
                    }
                }
            }
        }
    }
    else {
        for(int i = 0; i < n; i++) {
            dp[i] = 1;
            p[i] = i;
            for(int j = 0; j < 256; j++) {
                int tmp = a[i] & j;
                if(__builtin_popcount(tmp) == k[i]) {
                        if(dp[i] < hrashq[j] + 1) {
                            dp[i] = hrashq[j] + 1;
                            p[i] = hrashqiverj[j];
                        }
                }
            }
            //cerr << dp[i] << ' ';
            if(hrashq[a[i]] < dp[i]) {
                hrashq[a[i]] = max(hrashq[a[i]], dp[i]);
                hrashqiverj[a[i]] = i;
            }
        }
    }
    vector<int> ban;
    int ind = max_element(dp, dp + n) - dp;
    cout << dp[ind] << '\n';
    while(p[ind] != ind){
        ban.push_back(ind + 1);
        ind = p[ind];
    }
    ban.push_back(ind + 1);
    reverse(ban.begin(), ban.end());
    for(int a: ban) {
        cout << a << ' ';
    }
    return 0;
}

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