Submission #1123181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123181		KALARRY	Longest beautiful sequence (IZhO17_subsequence)	C++20	23 / 100	6090 ms	1716 KiB

subsequence

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,a[100005],k[100005],dp[100005],par[100005]; //par[i][j] = finishing at i having lenght %d

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 i = 1 ; i <= N ; i++)
        scanf("%d",&k[i]);
    int ans = 0;
    int pos = 0;
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = 1;
        par[i] = 0;
        for(int j = 1 ; j < i ; j++)
            if(__builtin_popcount(a[j] & a[i])==k[i] && dp[j] + 1 > dp[i])
            {
                dp[i] = dp[j] + 1;
                par[i] = j;
            }
        if(dp[i] > ans)
        {
            ans = dp[i];
            pos = i;
        }
    }
    printf("%d\n",ans);
    print_path(pos);
    return 0;
}

Compilation message (stderr)

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

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