제출 #664883

#제출 시각아이디문제언어결과실행 시간메모리
664883AstraytLongest beautiful sequence (IZhO17_subsequence)C++17
40 / 100
6035 ms21024 KiB
//君の手を握ってしまったら //孤独を知らないこの街には //もう二度と帰ってくることはできないのでしょう //君が手を差し伸べた 光で影が生まれる //歌って聞かせて この話の続き //連れて行って見たことない星まで //さユリ - 花の塔 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define int ll #define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define pii pair<int,int> #define pb push_back #define ff first #define ss second #define mp make_pair #define maxn 200005 #define mod 1000000007 void solve(){ int n; cin >> n; vector<int> a(n + 1, 0), k(n + 1); vector<pii> dp(n + 1, mp(0ll, 0ll)), mx((1<<20) + 1, mp(0, 0)); for(int i = 1; i <= n; ++i) cin >> a[i]; for(int i = 1; i <= n; ++i) cin >> k[i]; set<int> st; if(n <= 5000){ for(int i = 1; i <= n; ++i){ dp[i] = mp(1, i); for(int j = i - 1; j >= 1; --j){ int x = (a[i] & a[j]); int cnt = 0; while(x) cnt += (x & 1), x >>= 1; if(cnt != k[i]) continue; dp[i] = max(dp[i], mp(1 + dp[j].ff, j)); } } }else{ for(int i = 1; i <= n; ++i){ dp[i] = mp(1, i); for(int j:st){ int x = (a[i] & j), cnt = 0; while(x) cnt += (x & 1), x >>= 1; if(cnt != k[i]) continue; if(mx[j].ss != 0) dp[i] = max(dp[i], mp(mx[j].ff + 1, mx[j].ss)); } mx[a[i]] = max(mx[a[i]], mp(dp[i].ff, i)); st.insert(a[i]); } } int cur = (max_element(dp.begin(), dp.end()) - dp.begin()); cout << dp[cur].ff << '\n'; vector<int> ans; while(cur != dp[cur].ss){ ans.pb(cur); cur = dp[cur].ss; } ans.pb(cur); reverse(ans.begin(), ans.end()); for(int x:ans) cout << x << ' '; } signed main(){ starburst int t = 1; //cin >> t; 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...