Submission #366524

#	Time	Username	Problem	Language	Result	Execution time	Memory
366524		nicolaalexandra	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5729 ms	48688 KiB

subsequence

#include <bits/stdc++.h>
#define DIMN 100010
#define DIM (1<<10) + 2
using namespace std;

int v[DIMN],w[DIMN],dp[DIMN],fth[DIMN];
int poz[DIM][DIM][11];
vector <int> sol;
int n,i;

int main (){

    //ifstream cin ("subsequence.in");
    //ofstream cout ("subsequence.out");

    cin>>n;
    for (i=1;i<=n;i++)
        cin>>v[i];

    for (i=1;i<=n;i++)
        cin>>w[i];

    /// dp[i] - lg maxima a unei secv terminate cu i
    /// poz[mask_left][mask_right][nr] - poz secv max care are conf mask_left+mask_right si iau nr biti de 1 din prima jumatate
    int m = 10;

    for (i=1;i<=n;i++){

        int mask_right = (v[i] & ((1<<m)-1));
        int mask_left = (v[i]>>m);

        int maxi = 0, sol_poz = 0;
        for (int mask=0;mask<(1<<m);mask++){
            int cnt = w[i] - __builtin_popcount(mask & mask_right); /// atatia biti imi trb in stanga
            if (cnt < 0 || cnt > m)
                continue;

            int x = poz[mask_left][mask][cnt];
            if (dp[x] + 1 > dp[i]){
                dp[i] = dp[x] + 1;
                fth[i] = x;
            }
        }

        dp[i] = max (dp[i],1);

        /// actualizez dinamica
        for (int mask=0;mask<(1<<m);mask++){
            int cnt = __builtin_popcount(mask & mask_left);

            if (dp[i] > dp[poz[mask][mask_right][cnt]])
                poz[mask][mask_right][cnt] = i;
        }
    }

    int maxi = -1, x = 0;
    for (int i=1;i<=n;i++)
        if (dp[i] > maxi){
            maxi = dp[i];
            x = i;
        }

    if (!maxi){
        cout<<"1\n1";
        return 0;
    }

    cout<<maxi<<"\n";
    while (x){
        sol.push_back(x);
        x = fth[x];
    }

    for (i=sol.size()-1;i>=0;i--)
        cout<<sol[i]<<" ";

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:32:13: warning: unused variable 'maxi' [-Wunused-variable]
   32 |         int maxi = 0, sol_poz = 0;
      |             ^~~~
subsequence.cpp:32:23: warning: unused variable 'sol_poz' [-Wunused-variable]
   32 |         int maxi = 0, sol_poz = 0;
      |                       ^~~~~~~

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