제출 #1339356

#제출 시각아이디문제언어결과실행 시간메모리
1339356i_love_springLongest beautiful sequence (IZhO17_subsequence)C++20
23 / 100
6089 ms1604 KiB
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long 
const int inf = 2e9;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n;i++) 
        cin >> a[i];
    
    for (int i = 1; i <= n;i++)
        cin >> b[i];
    
    vector<int> dp(n + 1, 1);
    for (int i = n - 1; i >= 1;i--) {
        for (int j = n;j > i;j--) {
            if (__builtin_popcount(a[i] & a[j]) == b[j]) 
                dp[i] = max(dp[i], dp[j] + 1);
        }
    }

    int mx = 1;
    for (int i = 1; i <= n;i++) {
        if (dp[mx] < dp[i])
            mx = i;
    }

    vector<int> ans;
    int j = mx;
    for (int i = 0; i < dp[mx];i++) {
        ans.push_back(j);
        for (int k = j + 1; k <= n; k++) {
            if ((__builtin_popcount(a[k] & a[j]) == b[k]) && dp[k] == dp[mx] - (int)(ans.size())) {
                j = k;
                break;
            }
        }
    }
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";

}

int32_t main() { 

#ifdef Behruz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif 

    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    solve();

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...