Submission #1007322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007322		Essa2006	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4738 ms	208084 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mdo (ll)(1000000007)

vector<vector<vector<array<int, 2>>>> dp(1024, vector<vector<array<int, 2>>>(1024, vector<array<int, 2>>(20)));

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



    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 ans = 0, ind = 0;
    vector<int> Prv(n, -1);
    for (int i = 0; i < n; i++) {
        int low = 0, up = 0;
        for (int j = 0; j < 10; j++) {
            low += ((1 << j) & A[i]);
        }
        for (int j = 10; j < 20; j++) {
            if ((1 << j) & A[i]) {
                up += (1 << (j - 10));
            }
        }

        int res = 1;
        for (int x = 0; x < (1 << 10); x++) {
            if (K[i] - __builtin_popcount(x & low) < 0) {
                continue;
            }
            if (dp[x][up][K[i] - __builtin_popcount(x & low)][0] + 1 > res) {
                res = dp[x][up][K[i] - __builtin_popcount(x & low)][0] + 1;
                Prv[i] = dp[x][up][K[i] - __builtin_popcount(x & low)][1];
            }
        }

        if (res > ans) {
            ind = i, ans = res;
        }
        for (int x = 0; x < (1 << 10); x++) {
            if (res > dp[low][x][__builtin_popcount(x & up)][0]) {
                dp[low][x][__builtin_popcount(x & up)][0] = res;
                dp[low][x][__builtin_popcount(x & up)][1] = i;
            }
        }

    }


    vector<int> Ans;
    Ans.push_back(ind);
    while (Prv[ind] != -1) {
        ind = Prv[ind];
        Ans.push_back(ind);
    }

    cout << Ans.size() << endl;
    reverse(all(Ans));
    for (int i = 0; i < Ans.size(); i++) {
        cout << Ans[i] + 1 << ' ';
    }
}

Compilation message (stderr)

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

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