Submission #440755

#	Time	Username	Problem	Language	Result	Execution time	Memory
440755		training4usaco	Longest beautiful sequence (IZhO17_subsequence)	C++11	0 / 100	6099 ms	90668 KiB

subsequence

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    vector<int> a(n + 1), 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(1 << 10, vector<vector<int>>(1 << 10, 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] & ((1 << 10) - 1);  // bottom mask

        int best = 0;
        for(int m = 0; m < (1 << 10); ++i) {
            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 < (1 << 10); ++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;
}

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