Submission #475613

#	Time	Username	Problem	Language	Result	Execution time	Memory
475613		nohaxjustsoflo	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2420 ms	97512 KiB

subsequence

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
typedef long long ll;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> order_set;


const int mxN = 5e5+5;
const int mod = 998244353;
const int mxlogN = 20;
const int mxK = 26;

int pc[1<<20];
int dp[1<<10][1<<10][11];
int pre[1<<10][1<<10][11];
int dp2[mxN];
int pre2[mxN];
int aa[mxN];
int kk[mxN];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    for(int i = 0; i < (1<<20); i++) pc[i] = __builtin_popcount(i);
    int n; cin >> n;
    int ans = 0;
    int last = -1;
    for(int i = 0; i < n; i++) cin >> aa[i];
    for(int i = 0; i < n; i++) cin >> kk[i];
    for(int i = 0; i < n; i++)
    {
        int a =aa[i], k = kk[i];
        int cur = 0;
        int p = -1;
        int lef = (a>>10);
        int rig = a-(lef<<10);
        for(int j = 0; j < (1<<10); j++)
        {
            int c = pc[lef&j];///izaberi levi deo
            if(c <= k && k-c <= 10) /// neam vise od k, ostatak manji od 10
            {
                if(dp[j][rig][k-c] > cur)
                {
                    cur = dp[j][rig][k-c];
                    p = pre[j][rig][k-c];
                }
            }
        }
        cur++;
        pre2[i] = p;
        dp2[i] = cur;
        if(cur > ans)
        {
            ans = cur;
            last = i;
        }
        for(int j = 0; j < (1<<10); j++)
        {
            int c = pc[rig&j];
            if(dp2[i] > dp[lef][j][c]) ///ja kao [lef][j] da mi fali c copova mogu transition u ovaj
            {
                dp[lef][j][c] = dp2[i];
                pre[lef][j][c] = i;
            }
        }
    }
    vector<int> arr;
    while(last != -1)
    {
        arr.push_back(last+1);
        last = pre2[last];
    }
    cout << arr.size() << "\n";
    for(int i = arr.size()-1; i >= 0; i--) cout << arr[i] << " ";
    cout << "\n";
}

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