Submission #936014

#	Time	Username	Problem	Language	Result	Execution time	Memory
936014		atom	Longest beautiful sequence (IZhO17_subsequence)	C++17	23 / 100	6003 ms	2516 KiB

subsequence

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    int n; cin >> n;
    vector <int> a(n + 5), k(n + 5);

    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> k[i];

    vector <int> dp(n + 5, 0), opt(n + 5, -1);
    dp[0] = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            int p = dp[j];
            debug(i, j, p, __builtin_popcount(a[i] & a[j]), k[j] + 1);
            if ((p > 0 && (__builtin_popcount(a[i] & a[j]) == k[i])) || (p == 0)) {
                if (dp[i] < dp[j] + 1) {
                    opt[i] = j;
                    dp[i] = dp[j] + 1;
                }
            }
        }
    }   

    debug(dp);

    int p = 0, ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (ans < dp[i]) {
            p = i;
            ans = dp[i];
        }
    }

    vector <int> ids;
    while (p) {
        ids.push_back(p);
        p = opt[p];
    }
    reverse(ids.begin(), ids.end());
    cout << ans << "\n";
    for (int x : ids) cout << x << " ";
    cout << "\n"; 
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
subsequence.cpp:26:13: note: in expansion of macro 'debug'
   26 |             debug(i, j, p, __builtin_popcount(a[i] & a[j]), k[j] + 1);
      |             ^~~~~
subsequence.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
subsequence.cpp:36:5: note: in expansion of macro 'debug'
   36 |     debug(dp);
      |     ^~~~~

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