제출 #945265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
945265		vjudge1	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2449 ms	93564 KiB

subsequence

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 1e5  + 2;
const int base = ((1 << 20) - 1) ^ ((1 <<  10) - 1);
int val[(1 << 10)][(1 << 10)][22];
int a[N  + 2];
int  k[N  + 2];
int bit_count[(1 << 10)];
int dp[N + 2];
int tv[N + 2];
void solve() {
    int n;
    cin >> n;
    for(int i = 0 ; i <(1 << 10) ; i ++){
        bit_count[i] = __builtin_popcount(i);
    }
    for(int i  = 1; i <= n ; i ++)cin >> a[i];
    for(int i = 1; i <= n ;i ++)cin >> k[i];
    int res = 0;
    for(int i = 1; i <= n ; i ++){
        int first =  a[i] ^ (a[i] & base);
        int second = a[i] >> 10;
        for(int j = 0 ; j < (1 << 10) ;j ++){
            int x = bit_count[(j & first)];
            if(k[i] < x) continue;
            if(dp[tv[i]] < dp[val[second][j][k[i] - x]]){
                tv[i] = val[second][j][k[i] - x];
            }
        }
        dp[i] = dp[tv[i]] + 1;
        for(int j = 0 ; j < ( 1 << 10) ; j ++){
          //  if(j == 0) cout << first << " " <<bit_count[j & second] << "\n";
            if(dp[val[j][first][bit_count[j & second]]] < dp[i]){
              //  cout << j << " " << first << " " << bit_count[j & second]  << " " << i <<"\n";
                val[j][first][bit_count[j & second]] = i;
            }
        }
        if(dp[res] < dp[i])res = i;
    }
    vector < int > ans;
    while(res > 0){
        ans.push_back(res);
        res =tv[res];
    }
    reverse(ans.begin() , ans.end());
    cout << ans.size() << '\n';
    for(auto vl : ans)cout << vl << " ";
    
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    #define _ "test."
    if (fopen(_ "inp", "r")) {
        freopen(_ "inp", "r", stdin);
        freopen(_ "out", "w", stdout);
    }
    
    solve();
}

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

subsequence.cpp: In function 'int main()':
subsequence.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(_ "inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:59:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen(_ "out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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