Submission #710827

#	Time	Username	Problem	Language	Result	Execution time	Memory
710827		MinaRagy06	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6014 ms	3152 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl    '\n'
#define int     long long

signed main()
{
    lesgooo;
    int n;
    cin >> n;
    int a[n], b[n]{};
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    int dp[n]{};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < i; j++) if (__builtin_popcount(a[i] & a[j]) == b[i]) dp[i] = max(dp[i], dp[j]);
        dp[i]++;
    }
    int mx = 0, pos = 0;
    for (int i = 0; i < n; i++)
    {
        if (dp[i] > mx) mx = dp[i], pos = i;
    }
    stack<int> s;
    while (dp[pos] > 1)
    {
        s.push(pos);
        for (int j = 0; j < pos; j++) if (__builtin_popcount(a[pos] & a[j]) == b[pos] && dp[j] + 1 == dp[pos]) {pos = j; break;}
    }
    cout << s.size()+1 << endl;
    cout << pos+1 << " ";
    while (s.size()) cout << s.top()+1 << " ", s.pop();
    return 0;
}

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