Submission #852756

#	Time	Username	Problem	Language	Result	Execution time	Memory
852756		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	9 ms	47704 KiB

subsequence

#include <bits/stdc++.h>
#define ll pair<int,int>
using namespace std;

int a[100001];
int k[100001];
int dp[1024][1024][11];
int vt[1024][1024][11];
int kq[100001];
int bef[100001];
vector<int> lmao;

signed main() 
{
    // freopen("guard.in","r",stdin);
    // freopen("guard.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
    }
    for (int i=1;i<=n;i++)
    {
        cin >> k[i];
    }
    int end=0;
    int maxx=0;
    for (int i=1;i<=n;i++)
    {
        int lf=a[i]>>10;
        int rt=a[i]&((1<<10)-1);
        for (int i2=0;i2<(1<<10);i2++)
        {
            int kk=__builtin_popcount(i2&rt);
            if ((k[i]-kk>=0) and (k[i]-kk<=10)) 
            {
                if (kq[i]<dp[lf][i2][k[i]-kk]+1) bef[i]=vt[lf][i2][k[i]-kk];
                kq[i]=max(dp[lf][i2][k[i]-kk]+1,kq[i]);
            }
        }
        // if (kq[i]==1)
        // {
        //     int kk=__builtin_popcount(a[i]);
        //     if ()
        // }
        for (int i2=0;i2<(1<<10);i2++)
        {
            int kk=__builtin_popcount(i2&lf);
            if (dp[i2][rt][kk]<kq[i]) vt[i2][rt][kk]=i;
            dp[i2][rt][kk]=max(kq[i],dp[i2][rt][kk]);
        }
        if (maxx<kq[i]) end=i;
        maxx=max(maxx,kq[i]);
    }
    cout << maxx << '\n';
    while (end!=0)
    {
        lmao.push_back(end);
        end=bef[end];
    }
    sort (lmao.begin(),lmao.end());
    for (int i=0;i<lmao.size();i++) cout << lmao[i] << " " ;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:66:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (int i=0;i<lmao.size();i++) cout << lmao[i] << " " ;
      |                  ~^~~~~~~~~~~~

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