제출 #1265386

#제출 시각아이디문제언어결과실행 시간메모리
1265386herreinsteinLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
0 ms320 KiB
#include <bits/stdc++.h> #define int long long int #define ff first #define ss second const int MOD = 998244353; const int N = 2e5 + 5; using namespace std; int a[N], b[N]; pair<int, int> dp[N]; void solve(){ int n; cin >> n; dp[0] = {0, -1}; for(int i = 1; i <= n; i++){ cin >> a[i]; dp[i] = {1, 0}; } for(int i = 1; i <= n; i++){ cin >> b[i]; } if(n <= 5005){ for(int i = 2; i <= n; i++){ for(int j = 1; j < i; j++){ if(__builtin_popcount(a[i] & a[j]) == b[i]) { if(dp[i].ff < dp[j].ff + 1){ dp[i] = {dp[j].ff+1, j}; } } } } } else{ pair<int, int> mx[256]; for(int i = 0; i < 256; i++) mx[i] = {0, 0}; for(int i = 1; i <= n; i++){ for(int j = 0; j < 256; j++){ if(__builtin_popcount(a[i] & j) == b[i]){ if(dp[i].ff < mx[j].ff + 1){ dp[i] = {mx[j].ff+1, mx[j].ss}; } } } if(mx[a[i]].ff < dp[i].ff){ mx[a[i]] = {dp[i].ff, i}; } } } int mx = 0, k; for(int i = 1; i <= n; i++){ if(dp[i].ff > mx) mx = dp[i].ff, k = i; } cout << dp[k].ff << endl; vector<int> pth; while(dp[k].ss != -1){ pth.push_back(k); k = dp[k].ss; } for(int i = pth.size()-1; i > -1; i--) cout << pth[i] << " "; cout << endl; } int32_t main(){ int t; cin >> t; // t = 1; while(t--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...