Submission #1194192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194192		KALARRY	Longest beautiful sequence (IZhO17_subsequence)	C++20	100 / 100	2674 ms	92500 KiB

subsequence

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,a[100005],k[100005],ans[100005],par[100005];
pair<int,int> dp[(1<<10)][(1<<10)][11];

int score(int x,int y)
{
    return __builtin_popcount(x&y);
}

void print_path(int i)
{
    if(i==0)
        return;
    print_path(par[i]);
    printf("%d ",i);
}

int main()
{
    scanf("%d",&N);
    for(int i = 1 ; i <= N ; i++)
        scanf("%d",&a[i]);
    for(int j = 1 ; j <= N ; j++)
        scanf("%d",&k[j]);
    int pos = 0;
    for(int i = 1 ; i <= N ; i++)
    {
        //Case 1: Chose a[i]
        int la = (a[i]>>10);
        int ra = a[i] % (1<<10); 
        ans[i] = 1;
        for(int l = 0 ; l < (1<<10) ; l++)
        {
            int remaining = k[i] - score(l,la); 
            if(remaining >= 0 && remaining <= 10)
            {
                if(ans[i] <= dp[l][ra][remaining].first + 1)
                {
                    ans[i] = dp[l][ra][remaining].first + 1;
                    par[i] = dp[l][ra][remaining].second;
                }
            }
        }
        //Case 2: Find what staes ans[i] affects
        for(int r = 0 ; r < (1<<10) ; r++)
        {
            int cur = score(ra,r);
            if(dp[la][r][cur].first < ans[i])
            {
                dp[la][r][cur].first = ans[i];
                dp[la][r][cur].second = i;
            }
        }
        if(ans[i] > ans[pos])
            pos = i;
    }
    printf("%d\n",ans[pos]);
    print_path(pos);
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
subsequence.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
subsequence.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         scanf("%d",&k[j]);
      |         ~~~~~^~~~~~~~~~~~

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