Submission #38294

#	Time	Username	Problem	Language	Result	Execution time	Memory
38294		antimirage	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6000 ms	175240 KiB

subsequence

#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>

const int N = 1e5 + 5;

int n, ar[N], k[N], p[N], Bit[N];

std::pair <int, int> ans, dp[1025][1025][21];

std::vector <int> vec;
main ()
{
    for (int i = 0; i <= 1024; i++)
        Bit[i] = __builtin_popcount(i);

    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]);

    for (int i = 1; i <= n; i++)
        scanf("%d", &k[i]);

    for (int i = 1; i <= n; i++)
    {
        int cur = 1, pref = ar[i] >> 10, suf = ar[i] % 1024;

        for (int mask = 0; mask < 1024; mask++)
        {
            int need = k[i] - Bit[ pref & mask ];

            if ( need < 0 || need > 10 ) continue;

            if (cur < dp[mask][suf][need].first + 1)
            {
                cur = dp[mask][suf][need].first + 1;
                p[i] = dp[mask][suf][need].second;
            }
        }
        for (int mask = 0; mask < 1024; mask++)
            if ( dp[pref][mask][ Bit[ mask & suf ] ].first < cur )
                dp[pref][mask][ Bit[ mask & suf ] ] = std::make_pair( cur, i );

        if (cur > ans.first)
            ans = std::make_pair(cur, i);
    }
    printf("%d\n", ans.first);

    int qwe = ans.second;
    while (qwe)
    {
        vec.emplace_back(qwe);
        qwe = p[qwe];
    }
    std::reverse(vec.begin(), vec.end() );

    for (auto x : vec)
        printf("%d ", x);
}

Compilation message (stderr)

subsequence.cpp:13:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:18:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
subsequence.cpp:21:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
                            ^
subsequence.cpp:24:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k[i]);
                           ^

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