제출 #38336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38336		antimirage	Longest beautiful sequence (IZhO17_subsequence)	C++11	40 / 100	6000 ms	174856 KiB

subsequence

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

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;

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

컴파일 시 표준 에러 (stderr) 메시지

subsequence.cpp:15:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:20:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
subsequence.cpp:23:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
                            ^
subsequence.cpp:26: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