Submission #1123199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123199		KALARRY	Longest beautiful sequence (IZhO17_subsequence)	C++20	0 / 100	1 ms	328 KiB

subsequence

//chockolateman

#include<bits/stdc++.h>

using namespace std;

int N,a[100005],k[100005],dp[100005],par[100005];//,best_emf[1000005]; //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]);
        if(a[i] > 10000)
            printf("-1\n");
    }
    for(int i = 1 ; i <= N ; i++)
        scanf("%d",&k[i]);
    int ans = 0;
    int pos = 0;
    dp[0] = -1;
    for(int i = 1 ; i <= N ; i++)
    {
        dp[i] = 1;
        par[i] = 0;
        for(int mask = 0 ; mask < 10000 ; mask++)
                for(int j = 1 ; j < i ; j++)
                    if(a[j]== mask && __builtin_popcount(a[i] & a[j])==k[i] && dp[j] + 1 > dp[i])
                    {
                        dp[i] = dp[j] + 1;
                        par[i] = j;
                    }
        // if(dp[i] > dp[best_emf[a[i]]])
        //     best_emf[a[i]] = i;
        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:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
subsequence.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d",&k[i]);
      |         ~~~~~^~~~~~~~~~~~

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