Submission #36962

#	Time	Username	Problem	Language	Result	Execution time	Memory
36962		nickyrio	Longest beautiful sequence (IZhO17_subsequence)	C++14	100 / 100	4973 ms	48784 KiB

subsequence

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i<= b; ++i)
#define FORD(i, a, b) for (int i = a; i>=b; --i)
#define REP(i, a) for (int i = 0; i<a; ++i)
#define N 100100
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define IO cin.tie(NULL);cout.tie(NULL);
#define taskname "TEST"
using namespace std;

int n, a[N], k[N], cnt[1024], dp[1024][1024][11], f[N], bef[N];
vector<int> res;
int main() {
    //freopen(taskname".inp","r",stdin);
    //freopen(taskname".out","w",stdout);
    IO;
    scanf("%d", &n);
    FOR(i, 1, n) scanf("%d", &a[i]);
    FOR(i, 1, n) scanf("%d", &k[i]);
    REP(i, 1 << 10) cnt[i] = __builtin_popcount(i);
    //
    f[0] = 0;int ans = 0;
    FOR(i, 1, n) {
        int A = a[i] / 1024, B = a[i] % 1024;
        int best = 0;
        REP(newB, 1024) {
            int C = k[i] - cnt[B & newB];
            if (C > 10 || C < 0) continue;
            if (f[best] < f[dp[A][newB][C]]) best = dp[A][newB][C];
        } 
        f[i] = f[best] + 1;
        bef[i] = best;
        if (f[i] > f[ans]) ans = i;
        //
        REP(newA, 1024) {
            int C = cnt[A & newA];
            if (f[dp[newA][B][C]] < f[i]) {
                dp[newA][B][C] = i;
            }
        }
    }
    printf("%d\n", f[ans]);
    while (ans > 0) {
        res.push_back(ans);
        ans = bef[ans];
    }
    while (!res.empty()) printf("%d ", res.back()), res.pop_back();
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:18:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
                    ^
subsequence.cpp:19:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &a[i]);
                                    ^
subsequence.cpp:20:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%d", &k[i]);
                                    ^

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