Submission #603299

#	Time	Username	Problem	Language	Result	Execution time	Memory
603299		izanbf	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	41 ms	90984 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1.01e5;
// dp[prefix][suffix][num] : length of the largest beautiful sequence ending
//                           in a position with left bits equal to <prefix>,
//                           and having <num> common right bits with <suffix>
int dp[1<<10][1<<10][11];
int jp[1<<10][1<<10][11];
int previ[MAXN];
int a[MAXN];
int k[MAXN];

inline int left_bits(int v)  {  return v >> 10;    }
inline int right_bits(int v) {  return v & ((1<<10) - 1);     }
inline int bitcount(int v)   {  return __builtin_popcount(v); }

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

    int n;
    cin >> n;
    memset(dp, 0, sizeof(dp));
    memset(jp, 0xff, sizeof(jp));
    memset(previ, 0xff, sizeof(previ));

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

    int ans = -1;
    int last = -1;

    for (int i = 0; i < n; ++i) {
        int longest = 0;

        for (int pref = 0; pref < (1<<10); ++pref) {
            int common_left = bitcount(pref & left_bits(a[i]));
            int required_common_right = k[i] - common_left;
            if (required_common_right >= 0 and required_common_right <= 10) {
                int length = 1 + dp[pref][right_bits(a[i])][required_common_right];
                if (length > longest) {
                    longest = length;
                    previ[i] = jp[pref][right_bits(a[i])][required_common_right];
                }
            }
        }

        for (int suff = 0; suff < (1<<10); ++suff) {
            int& length = dp[left_bits(a[i])][suff][bitcount(right_bits(a[i]) & suff)];
            if (length < longest) {
                length = longest;
                jp[left_bits(a[i])][suff][bitcount(right_bits(a[i]) & suff)] = i;
            }
        }
        
        if (longest > ans) {
            ans = longest;
            last = i;
        }
    }

    vector<int> seq;
    while (last != -1) {
        seq.push_back(last);
        last = previ[last];
    }
    reverse(seq.begin(), seq.end());

    cout << seq.size() << endl;
    for (int i = 0; i < seq.size(); ++i) {
        if (i > 0) cout << ' ';
        cout << 1+seq[i];
    }
    cout << endl;
}

Compilation message (stderr)

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

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