제출 #953905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
953905		Wael	Longest beautiful sequence (IZhO17_subsequence)	C++14	40 / 100	6009 ms	125720 KiB

subsequence

#include <bits/stdc++.h>
using namespace std;
#define log(x) (63^__builtin_clzll(x))
//#define endl '\n'
#define all(x) (x).begin() , (x).end() 
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n), k(n);
    for(int i = 0; i < n; ++i) cin >> a[i];
    for(int i = 0; i < n; ++i) cin >> k[i];
 
    int fullDown = (1 << 10) - 1, fullUp = (1 << 20) - 1 - fullDown, ans = 0, last = 0;
    vector<int> prev(n, -1);
    int M = 1 << 10;
    vector<vector<vector<pair<int, int>>>> dp(M, vector<vector<pair<int, int>>>(M, vector<pair<int, int>>(11, {0, 0})));
    for(int i = 0; i < n; ++i) { 
        int mx = 1, up = ((fullUp & a[i]) >> 10), down = (fullDown & a[i]);
        for(int reqUp = 0; reqUp < (1 << 10); ++reqUp) {
            int common = __builtin_popcount((reqUp & up));
            if(k[i] >= common && k[i] - common <= 10) {
                auto state = dp[reqUp][down][k[i] - common];
                if(state.first + 1 > mx) prev[i] = state.second;
                mx = max(mx, state.first + 1);
            }
        }
        if(mx > ans) last = i;
        ans = max(ans, mx);
        for(int reqDown = 0; reqDown < (1 << 10); ++reqDown) {
            int common = __builtin_popcount((reqDown & a[i]));
            dp[up][reqDown][common] = max(dp[up][reqDown][common], {mx, i});
        }
    }
 
    vector<int> indices;
    while(last != -1) {
        indices.push_back(last);
        last = prev[last];
    }
    assert(indices.size() == ans);
    reverse(all(indices));
 
    cout << ans << endl;
 
    for(auto j : indices) cout << j + 1 << " ";
    cout << endl;
 
    return;
}
 
main() {
    ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    while(t--) solve();
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from subsequence.cpp:1:
subsequence.cpp: In function 'void solve()':
subsequence.cpp:41:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |     assert(indices.size() == ans);
      |            ~~~~~~~~~~~~~~~^~~~~~
subsequence.cpp: At global scope:
subsequence.cpp:52:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 | main() {
      | ^~~~

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