제출 #1006682

#제출 시각아이디문제언어결과실행 시간메모리
1006682vqpahmadLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
221 ms262144 KiB
#include<bits/stdc++.h> using namespace std; #ifdef ONPC #include"debug.h" #else #define debug(...) 42 #endif #define endl '\n' #define ll long long #define pii pair<int,int> #define F first #define S second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } const int mod = 1e9 + 7; const int MAXN = 1e5 + 2; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; int dp[MAXN], pos[MAXN], prv[MAXN], val[MAXN]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); 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]; memset(prv, -1, sizeof(prv)); memset(dp, -1, sizeof(dp)); for (int i = 0; i < n; i++){ for (int j = 0; j < 256; j++) if (__popcount(a[i]&j) == k[i] && ckmax(dp[a[i]], dp[j] + 1)) val[i] = dp[a[i]], pos[a[i]] = i, prv[i] = pos[j]; if (ckmax(dp[a[i]], 0)) pos[a[i]] = i; } int mx = *max_element(val, val + n); vector<int> ans; for (int i = 0; i < n; i++){ if (val[i] == mx){ int cur = i; while (prv[cur] != -1){ ans.pb(cur); cur = prv[cur]; } ans.pb(cur); break; } } reverse(all(ans)); cout << sz(ans) << endl; for (auto it : ans) cout << it + 1 << ' '; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...