Submission #1000351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000351		Hanksburger	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	3322 ms	48144 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
int dp[100001], pre[100001], ind[1024][1024][11], a[100001], k[100001];
stack<int> s;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, cur, ans=0;
    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=1; i<=n; i++)
    {
        int cnt1=0, cnt2=0;
        for (int j=0; j<10; j++)
            if (a[i]&(1<<j))
                cnt1++;
        for (int j=10; j<20; j++)
            if (a[i]&(1<<j))
                cnt2++;
        dp[i]=1;
        for (int j=0; j<1024; j++)
        {
            int cnt=0;
            for (int l=0; l<10; l++)
                if (a[i]&j&(1<<l))
                    cnt++;
            if (k[i]-cnt<0 || k[i]-cnt>cnt2)
                continue;
            int index=ind[j][a[i]>>10][k[i]-cnt];
            if (index && dp[i]<dp[index]+1)
            {
                dp[i]=dp[index]+1;
                pre[i]=index;
                //cout << "dp " << i << " = dp " << index << " + 1 = " << dp[i] << "\n";
                //cout << "pre " << i << " = " << index << '\n';
                //cout << '\n';
            }
        }
        for (int j=0; j<1024; j++)
        {
            int cnt=0;
            for (int l=0; l<10; l++)
                if ((a[i]>>10)&j&(1<<l))
                    cnt++;
            int index=ind[a[i]%(1<<10)][j][cnt];
            if (!index || dp[index]<dp[i])
            {
                ind[a[i]%(1<<10)][j][cnt]=i;
                //if (j<=15)
                //    cout << "ind " << a[i]%(1<<10) << ' ' << j << ' ' << cnt << " = " << i << '\n';
            }
        }
        if (ans<dp[i])
        {
            ans=dp[i];
            cur=i;
        }
    }
    cout << ans << '\n';
    while (cur)
    {
        s.push(cur);
        cur=pre[cur];
    }
    while (!s.empty())
    {
        cout << s.top() << ' ';
        s.pop();
    }
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:68:20: warning: 'cur' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |         cur=pre[cur];
      |             ~~~~~~~^

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