제출 #1336705

#제출 시각아이디문제언어결과실행 시간메모리
1336705nguyenkhangninh99Longest beautiful sequence (IZhO17_subsequence)C++20
100 / 100
5690 ms125288 KiB
#include <bits/stdc++.h>
using namespace std;

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.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];

    vector<vector<vector<pair<int, int>>>> banhhe(1 << 10, vector<vector<pair<int, int>>>(1 << 10, vector<pair<int, int>>(11, {-1, -1})));
    //[x][y][c] lưu pair. max len, kết thúc
    //x = 10 bit lớn hơn của thg hiện tại
    //y = 10 bit nhỏ hơn của thg tiếp theo giả định
    //c = bitcnt của 10 bit nhỏ thg hiện tại và 10 bit nhỏ thg giả định.

    vector<pair<int,int>> dp(n, {0, -1});
    for(int i = 0; i < n; i++){
        int pre = a[i] % (1 << 10), suf = a[i] / (1 << 10);
        for(int mask = 0; mask < (1 << 10); mask++){ //xét tất cả trường hợp 10 bit lớn của thg trc  
            int cnt = __builtin_popcount(mask & pre);
            if(cnt <= k[i] && k[i] - cnt <= 10) dp[i] = max(dp[i], banhhe[mask][suf][k[i] - cnt]);
        }
        dp[i].first++;
        for(int mask = 0; mask < (1 << 10); mask++){ //update tất cả trường hợp 10 bit nhỏ của thg tiếp theo
            int bit = __builtin_popcount(suf & mask);
            banhhe[pre][mask][bit] = max(banhhe[pre][mask][bit], {dp[i].first, i});
        }
    }

    int u = max_element(dp.begin(), dp.end()) - dp.begin();

    cout << dp[u].first << "\n";
    deque<int> ans;
    while(u >= 0){
        ans.push_front(u+1);
        u = dp[u].second;
    }
    for(int x: ans) cout << x << " ";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...