Submission #440758

#TimeUsernameProblemLanguageResultExecution timeMemory
440758training4usacoLongest beautiful sequence (IZhO17_subsequence)C++11
23 / 100
6047 ms92212 KiB
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    // cout << n <<  endl;

    vector<int> a(n + 1);
    vector<int> k(n + 1);

    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    for(int i = 1; i <= n; ++i) {
        cin >> k[i];
    }

    vector<int> dp(n + 1);
    vector<int> from(n + 1);

    vector<vector<vector<int>>> store(1024, vector<vector<int>>(1024, vector<int>(11)));
    // best index if we have a mask for the first 10 bits and a mask for the second 10 bits and we need i setbits in the first 10

    for(int i = 1; i <= n; ++i) {
        int lmask = a[i] >> 10; // top mask
        int rmask = a[i] & 1023;  // bottom mask

        int best = 0;
        for(int m = 0; m < 1024; ++m) {
            int numset = 0;
            for(int j = 0; j < 20; ++j) {
                if((m & rmask) & (1 << j)) {
                    ++numset;
                }
            }
            int need = k[i] - numset;

            if(need > 10 || need < 0) {
                continue;
            }

            if(dp[best] < dp[store[lmask][m][need]]) {
                best = store[lmask][m][need];
            }
        }

        dp[i] = 1 + dp[best];
        from[i] = best;

        for(int m = 0; m < 1024; ++m) {
            int numset = 0;
            for(int j = 0; j < 20; ++j) {
                if((m & lmask) & (1 << j)) {
                    ++numset;
                }
            }
            
            if(dp[store[m][rmask][numset]] < dp[i]) {
                store[m][rmask][numset] = i;
            }
        }
    }

    int highest = 1;
    for(int i = 1; i <= n; ++i) {
        if(dp[highest] < dp[i]) {
            highest = i;
        }
    }

    vector<int> answer;
    while(highest) {
        answer.push_back(highest);
        highest = from[highest];
    }

    sort(answer.begin(), answer.end());
    cout << answer.size() << endl;
    for(int i = 0; i < (int)answer.size(); ++i) {
        cout << answer[i] << " ";
    }
    cout << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...