Submission #824325

#	Time	Username	Problem	Language	Result	Execution time	Memory
824325		TS_2392	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	2499 ms	96388 KiB

subsequence

#include <bits/stdc++.h>
#define bp __builtin_popcount
using namespace std;
const int N = 1e5 + 3;
int n, a[N], k[N], f[1024][1024][11], cnt_bit[1 << 20], trace[N];
int res, save, best[1024][1024][11];
//f[mask][v][i] trong nhung day co gia tri cuoi a + v * 2 ^ 10 t/m bp(a & mask) == i thi do day cua day dai nhat la
bool maximize(int &a, int b){
    if(a < b){
        a = b;
        return true;
    }
    return false;
}
int main(){
  	ios_base::sync_with_stdio(false);
  	cin.tie(NULL); cout.tie(NULL);
    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 < 1 << 20; ++i) cnt_bit[i] = bp(i);
    for(int i = 1; i <= n; ++i){
        int ans = 0;
        int mask1 = a[i] >> 10;
        int mask2 = a[i] & 1023;
        for(int v = 0; v < 1024; ++v){
            int need = k[i] - cnt_bit[mask2 & v];
            if(need < 0 || need > 10) continue;
            if(maximize(ans, f[mask1][v][need])) trace[i] = best[mask1][v][need];
        }
        ++ans;
        if(maximize(res, ans)) save = i;
        for(int v = 0; v < 1024; ++v) if(maximize(f[v][mask2][cnt_bit[mask1 & v]], ans)){
            best[v][mask2][cnt_bit[mask1 & v]] = i;
        }
    }
    cout << res << '\n';
    vector<int> res_ind;
    while(save > 0){
        res_ind.push_back(save);
        save = trace[save];
    }
    for(int i = res_ind.size() - 1; i >= 0; --i) cout << res_ind[i] << ' ';
    return 0;
}

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