Submission #38292

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

subsequence

#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )

using namespace std;

const int N = 1e5 + 5;

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

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

vector <int> vec;

main ()
{
    for (int i = 0; i <= 1024; i++)
        Bit[i] = __builtin_popcount(i);

    cin >> 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].fr + 1)
            {
                cur = dp[mask][suf][need].fr + 1;
                p[i] = dp[mask][suf][need].sc;
            }
        }
        for (int mask = 0; mask < 1024; mask++)
        {
            if ( dp[pref][mask][ Bit[ mask & suf ] ].fr < cur )
                dp[pref][mask][ Bit[ mask & suf ] ] = mk( cur, i );
        }
        ans = max(ans, mk(cur, i) );
    }
    cout << ans.fr << endl;

    int qwe = ans.sc;
    while (qwe)
    {
        vec.pb(qwe);
        qwe = p[qwe];
    }
    reverse(all(vec));
    for (auto x : vec)
        printf("%d ", x);
}

Compilation message (stderr)

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