제출 #1257251

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1257251		dosts	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2511 ms	193404 KiB

subsequence

//Siga Siga?! YES!
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e18,N = 3e3+1,MOD =  998244353;

struct State {
    int ans = 0,lst = 0;
};

bool better(State& s1,State s2) {
    if (s1.ans < s2.ans || (s1.ans == s2.ans && s1.lst < s2.lst)) {
        s1 = s2;
        return true;
    }
    return false;
};


State dp[1024][1024][11];
int pc[1024][1024];

void solve() {  
    int n;
    cin >> n;
    vi a(n+1),k(n+1);
    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<1024;i++) {
        for (int j = 0;j<1024;j++) {
            pc[i][j] = __builtin_popcountll(i&j);
        }
    }
    State best;
    vector<State> opt(n+1);
    vi lst(n+1);
    for (int i=1;i<=n;i++) {
        int l = a[i] >> 10;
        int r = a[i] & (1023);
        lst[i] = i;
        opt[i] = {1,i};
        for (int j = 0;j<(1LL<<10);j++) {
            int need = k[i]-pc[l][j];
            if (need < 0 || need > 10) continue;
            if (better(opt[i],State{dp[j][r][need].ans+1,i})) {
                lst[i] = dp[j][r][need].lst;
            }
        }
        better(best,opt[i]);
        for (int j = 0;j<(1LL<<10);j++) {
            better(dp[l][j][pc[r][j]],opt[i]);
        }
    }
    cout << best.ans << '\n';
    vi ans;
    while (1) {
        ans.push_back(best.lst);
        if (best.lst != lst[best.lst]) best = opt[lst[best.lst]];
        else break;
    } 
    for (int i = ans.size()-1;i>=0;i--) cout << ans[i] << ' ';
    cout << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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