Submission #38340

#	Time	Username	Problem	Language	Result	Execution time	Memory
38340		antimirage	Longest beautiful sequence (IZhO17_subsequence)	C++14	0 / 100	0 ms	174712 KiB

subsequence

#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
#include <time.h>
#pragma GCC optimize ("O3")

#define QWE clo\
ck()


const int N = 1e5 + 5;

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

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

std::vector <int> vec;

int 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);

        if (QWE > 1000 * 5.5) break;
    }
    printf("%d\n", ans.first);

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

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

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:25:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
subsequence.cpp:28:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
                            ^
subsequence.cpp:31:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &k[i]);
                           ^

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