Submission #842065

#	Time	Username	Problem	Language	Result	Execution time	Memory
842065		hqminhuwu	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3901 ms	102316 KiB

subsequence

#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = _b; _a <= _c; ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> _c;)
#define forf(_a,_b,_c) for(_a = _b; _a < _c; ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 2e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int qq = (1 << 10);

int n,i,a[N],k[N],ans,dp[qq][qq][12],j,par[N],trace[qq][qq][12],pos;
vector <int> res;
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    forr (i,1,n)
        cin >> a[i];
    forr (i,1,n)
        cin >> k[i];
    forr (i,1,n){
        int tmp = 0, u = a[i] >> 10, v = a[i] % (1 << 10);
        forr (j,0,(1 << 10) - 1){
            int w = k[i] - __builtin_popcount(j & u);
            if (w < 0 || w > 10) continue;
                if (dp[j][v][w] > tmp){
                tmp = dp[j][v][w];
                par[i] = trace[j][v][w];}
        }
        if (ans < tmp + 1)
            ans = tmp + 1, pos = i;
        forr (j,0,(1 << 10) - 1){
            int w = __builtin_popcount(j & v);
            if (tmp + 1 > dp[u][j][w]){
                dp[u][j][w] = tmp + 1;
                trace[u][j][w] = i;
            }
        }
        //cout << par[i] << "\n";
    }
    cout << ans << "\n";
    while (ans--){
        res.pb(pos);
        pos = par[pos];
    }
    ford (i,res.size() - 1,0)
    cout << res[i] << " ";
    return 0;
}
/*



*/

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