Submission #1030048

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030048		phoenix	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3596 ms	84756 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;
const int M = (1 << 10);

pair<int, int> ans;
int a[N], k[N];
pair<int, int> dp[M][M][10];
int pr[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> k[i];

    for (int i = 1; i <= n; i++) {
        pair<int, int> cur = {0, 0};
        for (int f = 0; f < (1 << 10); f++) {
            int c = k[i] - __builtin_popcount(f & a[i]);
            if (10 > c && c >= 0)
                cur = max(cur, dp[f][a[i] >> 10][c]);
        }
        pr[i] = cur.second;
        cur.first++;
        cur.second = i;
        ans = max(ans, cur);
        for (int f = 0; f < (1 << 10); f++) {
            int c = __builtin_popcount((a[i] >> 10) & f);
            dp[(a[i] & M - 1)][f][c] = max(dp[(a[i] & M - 1)][f][c], cur);
        }
    }
    cout << ans.first << '\n';
    vector<int> res;
    while (ans.second) {
        res.push_back(ans.second);
        ans.second = pr[ans.second];
    }
    reverse(res.begin(), res.end());
    for (int c : res)
        cout << c << ' ';
    cout << '\n';

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:36:26: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   36 |             dp[(a[i] & M - 1)][f][c] = max(dp[(a[i] & M - 1)][f][c], cur);
      |                        ~~^~~
subsequence.cpp:36:57: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   36 |             dp[(a[i] & M - 1)][f][c] = max(dp[(a[i] & M - 1)][f][c], cur);
      |                                                       ~~^~~

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