Submission #38304

#	Time	Username	Problem	Language	Result	Execution time	Memory
38304		Just_Solve_The_Problem	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	5836 ms	93448 KiB

subsequence

#include <bits/stdc++.h>

using namespace std;

#define pii pair < int, int >
#define fr first
#define sc second

const int N = (int)1e5 + 7;
const int m = 1 << 10;

int a[N], k[N];
int bit[m];
pii dp[m][m][11];
int par[N];

main () {
    int n; scanf ("%d", &n);
    for (int j = 0; j < 2; j++)
        for (int i = 1; i <= n; i++)
            if (!j)
                scanf ("%d", a + i);
            else
                scanf ("%d", k + i);

    for (int i = 1; i < m; i++) {
        bit[i] = __builtin_popcount(i);
    }
    int ans, ansid;
    ans = ansid = 0;
    for (int i = 1; i <= n; i++) {
        int pr = (a[i] >> 10);
        int sf = (a[i] % m);
        int mx = 1, id = 0;
        for (int j = 0; j < m; j++) {
            int need = k[i] - bit[j & pr];
            if (need < 0 || need > 10) continue;
            if (mx < dp[j][sf][need].fr + 1) {
                mx = dp[j][sf][need].fr + 1;
                id = dp[j][sf][need].sc;
            }
        }
        par[i] = id;
        for (int j = 0; j < m; j++) {
            int need = bit[j & sf];

            if (dp[pr][j][need].fr < mx) {
                dp[pr][j][need] = {mx, i};
            }
        }
        if (ans < mx) {
            ans = mx;
            ansid = i;
        }
    }
    cout << ans << endl;
    vector < int > asd;
    while (ansid) {
        asd.push_back(ansid);
        ansid = par[ansid];
    }
    reverse(asd.begin(), asd.end());
    for (auto to : asd) {
        cout << to << ' ';
    }
}

Compilation message (stderr)

subsequence.cpp:17:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
subsequence.cpp: In function 'int main()':
subsequence.cpp:18:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int n; scanf ("%d", &n);
                            ^
subsequence.cpp:22:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
                 scanf ("%d", a + i);
                                    ^
subsequence.cpp:24:36: 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: 60 / 60