Submission #393546

#	Time	Username	Problem	Language	Result	Execution time	Memory
393546		SirCovidThe19th	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	22 ms	45432 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
/*
dp[i][j][k] - given that there must be k set bits in i(which is a mask
for possible values of first 10 bits of another value that is valid
with the current value)
and j is last 10 bits - j consists of only values we have seen
so far -> crucial to understanding

first loop through all possible values for j(read dp description). 
we can then calculate(variable b)
the amount of set bits required in i(which is the left 10).
so: dp[left][possible value][k] -> we do this to find index
with longest chain that includes the current value

then we update dp array. loop through all possible values
for i; given that j(read dp description) is right(the variable).
*/
int main(){
    int n;
    cin >> n;
    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];

    int popCnt[1024];
    for (int i = 0; i < 1024; i++) popCnt[i] = __builtin_popcount(i);

    
    static int dp[1024][1024][11];
    memset(dp, 0, sizeof(dp));
    //at index i what is the longest chain you can form
    int best[n+1];
    fill(best, best+n+1, 0);
    //at index i what is the first element in the longest
    //chain you can form so far
    int store[n+1];
    
    for (int i = 1; i <= n; i++){
        int right = a[i]&1023;
        int left = a[i]>>10;
        int idx = 0;

        for (int mask = 0; mask < 1024; mask++){
            int b = k[i]-popCnt[(right&mask)];
            if (b >= 0 and b <= 10)
                if (best[dp[left][mask][b]] > best[idx])
                    idx = dp[left][mask][b];
        }

        best[i] = best[idx]+1;
        store[i] = idx;

        for (int mask = 0; mask < 1024; mask++){
            int b = max(popCnt[(left&mask)]-popCnt[right], 0);
            if (best[i] > best[dp[mask][right][b]])
                dp[mask][right][b] = i;
        }
    }

    int pos = max_element(best, best+n+1)-best;
    vector<int> res;
    while (pos != 0){
        res.push_back(pos);
        pos = store[pos];
    }
    reverse(res.begin(), res.end());
    cout<<res.size()<<endl;
    for (int i = 0; i < res.size(); i++) cout<<res[i]<<" ";
} 

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |     for (int i = 0; i < res.size(); i++) cout<<res[i]<<" ";
      |                     ~~^~~~~~~~~~~~

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