Submission #1030053

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030053		phoenix	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1941 ms	83896 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 cnt[M];

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 = 0; i < M; i++)
        cnt[i] = __builtin_popcount(i);

    for (int i = 1; i <= n; i++) {
        pair<int, int> cur = {0, 0};
        for (int f = 0; f < M; f++) {
            int c = k[i] - cnt[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 < M; f++) {
            int c = cnt[(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:39:25: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |             dp[a[i] & M - 1][f][c] = max(dp[a[i] & M - 1][f][c], cur);
      |                       ~~^~~
subsequence.cpp:39:54: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   39 |             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