Submission #226029

#	Time	Username	Problem	Language	Result	Execution time	Memory
226029		emil_physmath	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	5694 ms	262008 KiB

subsequence

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <set>
using namespace std;
#define Bits __builtin_popcount
using uint = unsigned int;
const int maxN = 100'000;
struct DP
{
    int ind, len, prev;
    DP(int ind_ = -1, int len_ = 0, int prev_ = -1)
        : ind(ind_)
        , len(len_)
        , prev(prev_)
    {}
    operator int&() { return len; }
    operator const int&() const { return len; }
};
inline void Upd(DP& a, const DP& rhs)
{
    if (rhs.len + 1 >= a.len)
    {
        a.len = rhs.len + 1;
        a.prev = rhs.ind;
    }
}

DP best[1 << 10][1 << 10][21];
DP dp[maxN];
int a[maxN], k[maxN];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    for (int i = 0; i < n; ++i)
        cin >> k[i];
    for (int i = 0; i < n; ++i)
    {
        dp[i].ind = i;
        if (i == 0)
            dp[i].len = 1, dp[i].prev = -1;
        else
            for (uint lmask = 0; lmask < (1 << 10); ++lmask)
            {
                int lk = Bits(a[i] & (lmask << 10));
                if (lk > k[i]) continue;
                uint rpart = (1 << 10) - 1;
                rpart &= a[i];
                Upd(dp[i], best[lmask][rpart][k[i] - lk]);
            }
        uint lpart = (1 << 10) - 1;
        lpart <<= 10;
        lpart &= a[i];
        lpart >>= 10;
        for (uint mask = 0; mask < (1 << 10); ++mask)
        {
            DP& bst = best[lpart][mask][Bits(a[i] & mask)];
            if (bst.len <= dp[i].len)
                bst = dp[i];
        }
#ifdef MANSON
        cerr << "dp[" << dp[i].ind << "] = " << dp[i].len << ", prev: " << dp[i].prev << '\n';
#endif
    }
    vector<int> ans;
    for (int i = max_element(dp, dp + n) - dp; i != -1; i = dp[i].prev)
        ans.push_back(i);
    cout << ans.size() << '\n';
    reverse(ans.begin(), ans.end());
    for (int i: ans)
        cout << i + 1 << ' ';
}

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