Submission #133861

#	Time	Username	Problem	Language	Result	Execution time	Memory
133861		Kastanda	Longest beautiful sequence (IZhO17_subsequence)	C++11	100 / 100	4378 ms	79624 KiB

subsequence

// ItnoE
#include<bits/stdc++.h>
using namespace std;
const int N = 100005, SQ = 1024;
int n, A[N], P[N];
pair < int , int > dp[21][SQ][SQ];
inline void Max(pair < int , int > &a, pair < int , int > b) {a = max(a, b);}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &A[i]);
    int Mx = 0, Bi = 0;
    for (int i = 1; i <= n; i ++)
    {
        int k, a = A[i];
        scanf("%d", &k);
        pair < int , int > Bst = {0, 0};
        if (__builtin_popcount(a) >= k)
            for (int j = 0; j < SQ; j ++)
                if (k >= __builtin_popcount(a >> 10 & j))
                    Max(Bst, dp[k - __builtin_popcount(a >> 10 & j)][j][a & 1023]);
        P[i] = Bst.second; Bst.first ++; Bst.second = i;
        for (int j = 0; j < SQ; j ++)
            Max(dp[__builtin_popcount(a & j)][a >> 10][j], Bst);
        if (Bst.first > Mx)
            Mx = Bst.first, Bi = i;
    }
    vector < int > R;
    while (Bi)
        R.push_back(Bi), Bi = P[Bi];
    reverse(R.begin(), R.end());
    printf("%d\n", (int)R.size());
    for (int v : R)
        printf("%d ", v);
    return 0;
}

Compilation message (stderr)

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

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