Submission #953736

#	Time	Username	Problem	Language	Result	Execution time	Memory
953736		Wael	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	2 ms	1884 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define log(x) (63^__builtin_clzll(x))
//#define endl '\n'
#define all(x) (x).begin() , (x).end() 

pair<int, int> dp[(1 << 10) + 2][(1 << 10) + 2][11];
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i) cin >> k[i];

    int fullDown = (1 << 10) - 1, fullUp = (1 << 20) - 1 - fullDown, ans = 0, last = 0;
    vector<int> prev(n, -1);
    for(int i = 0; i < n; ++i) { 
        int mx = 1, up = ((fullUp & a[i]) >> 10), down = (fullDown & a[i]);
        for(int reqUp = 0; reqUp < (1 << 10); ++reqUp) {
            int common = __builtin_popcount(reqUp & up);
            if(k[i] >= common) {
                auto &state = dp[reqUp][down][k[i] - common];
                if(state.first + 1 > mx) prev[i] = state.second;
                mx = max(mx, state.first + 1);
            }
        }
        if(mx > ans) last = i;
        ans = max(ans, mx);
        for(int reqDown = 0; reqDown < (1 << 10); ++reqDown) {
            int common = __builtin_popcount((reqDown & a[i]));
            dp[up][reqDown][common] = max(dp[up][reqDown][common], {mx, i});
        }
    }

    cout << ans << endl;
    vector<int> indices;
    while(last != -1) {
        indices.push_back(last);
        last = prev[last];
    }
    reverse(all(indices));
    for(auto j : indices) cout << j + 1 << " ";
    cout << endl;

    return;
}

main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    while(t--) solve();
    
    return 0;
}

//dp[need][have]

Compilation message (stderr)

subsequence.cpp:48:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   48 | main() {
      | ^~~~

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