Submission #440766

#	Time	Username	Problem	Language	Result	Execution time	Memory
440766		training4usaco	Longest beautiful sequence (IZhO17_subsequence)	C++11	40 / 100	6054 ms	46992 KiB

subsequence

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

#define N 100000

int dp[N + 1];
int from[N + 1];
int a[N + 1];
int k[N + 1];
int store [1024][1024][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

int main() {
    ios_base::sync_with_stdio(false); 
    cin.tie(0);  
    cout.tie(0);

    int n;
    cin >> n;
    // cout << n <<  endl;

    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 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 = __builtin_popcount(m & rmask);
            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 =__builtin_popcount(m & lmask);
            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: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 0 / 60