Submission #919487

#	Time	Username	Problem	Language	Result	Execution time	Memory
919487		KactusJack	Longest beautiful sequence (IZhO17_subsequence)	C++14	23 / 100	6020 ms	25176 KiB

subsequence

#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for(int i = 1; i <= n; i++){
        cin >> b[i];
    }
    vector<vector<int>> dp(n+1, vector<int> (20)), from(n+1, vector<int> (20));
    int len = 0, j = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(__builtin_popcount(a[j]&a[i]) == b[i] && 1+dp[j][b[j]] > dp[i][b[i]]){
                dp[i][b[i]] = 1+dp[j][b[j]];
                from[i][b[i]] = j;
            }
        }
        if(dp[i][b[i]] > len){
            len = dp[i][b[i]];
            j = i;
        }
    }
    len++;
    vector<int> v;
    while(j && v.size() < len){
        v.push_back(j);
        j = from[j][b[j]];
    }
    reverse(v.begin(), v.end());
    cout << len << '\n';
    for(int x : v){
        cout << x << ' ';
    }
    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:35:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     while(j && v.size() < len){
      |                ~~~~~~~~~^~~~~

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