Submission #1123197

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123197		KALARRY	Longest beautiful sequence (IZhO17_subsequence)	C++20	7 / 100	318 ms	327680 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]);
    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 < (1<<8) ; mask++)
            // if(__builtin_popcount(a[i] & mask) == k[i])// && dp[best_emf[mask]] + 1 > dp[i])
            // {
                for(int j = 1 ; j < i ; j++)
                    if(__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: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: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 60