Submission #841976

#	Time	Username	Problem	Language	Result	Execution time	Memory
841976		hqminhuwu	Longest beautiful sequence (IZhO17_subsequence)	C++14	7 / 100	126 ms	262144 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 = 1e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int n,i,a[N],k[N],ans,dp[2000][2000][22],j,par[N],trace[2000][2000][22],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] - (u << 10);
        forr (j,0,(1 << 10) - 1)
            if (k[i] >= __builtin_popcount(j & u)){
                if (dp[j][v][k[i] - __builtin_popcount(j & u)] > tmp){
                tmp = dp[j][v][k[i] - __builtin_popcount(j & u)];
                par[i] = trace[j][v][k[i] - __builtin_popcount(j & u)];}
             //   cout << j << " " << v << " " << k[i] - __builtin_popcount(j & u) << "\n";
            }
        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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60