제출 #38338

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

subsequence

#include <stdio.h>
#include <utility>
#include <vector>
#include <algorithm>
#include <time.h>
#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;

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 (clock() > CLOCKS_PER_SEC * 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);
}

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

subsequence.cpp: In function 'int main()':
subsequence.cpp:21:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
subsequence.cpp:24:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]);
                            ^
subsequence.cpp:27: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