Submission #713693

#	Time	Username	Problem	Language	Result	Execution time	Memory
713693		iulia13	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	3438 ms	97556 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
const int M = 1024;
const int K = 11;
int a[N];
int k[N];
int nr[M][M];
pair<int, int> dp[M][M][K], from[N];
vector <int> v;
int main()
{
  //  freopen("g.in", "r", stdin);
//    freopen("g.out", "w", stdout);
    int n;
    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 < M; i++)
        for (int j = 0; j < M; j++)
            nr[i][j] = __builtin_popcount(i & j);
    for (int i = 1; i <= n; i++)
    {
        pair <int, int> ans = {0, 0};
        int f = (a[i] >> 10);
        int s = a[i] % M;
        for (int j = 0; j < M; j++)
            if (nr[s][j] <= k[i] && k[i] - nr[s][j] <= 10)
                ans = max(ans, dp[j][f][k[i] - nr[j][s]]);
        ans.first++;
        from[i] = ans;
        for (int j = 0; j < M; j++)
            dp[a[i] & (M - 1)][j][nr[f][j]] = max(dp[a[i] & (M - 1)][j][nr[f][j]], {ans.first, i});

    }
    int idx = 0;
    for (int i = 1; i <= n; i++)
        if (from[idx].first < from[i].first)
            idx = i;
    cout << from[idx].first;
    while(idx)
    {
        v.push_back(idx);
        idx = from[idx].second;
    }
    cout << endl;
    reverse(v.begin(), v.end());
    for (auto x : v)
        cout << x <<" ";
    return 0;
}

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