제출 #1006669

#제출 시각아이디문제언어결과실행 시간메모리
1006669vqpahmadLongest beautiful sequence (IZhO17_subsequence)C++17
23 / 100
136 ms2048 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 = 5003; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; int dp[MAXN], prv[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)); for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) if (__popcount(a[i]&a[j]) == k[i] && ckmax(dp[i], dp[j] + 1)) prv[i] = j; int mx = *max_element(dp, dp + n); vector<int> ans; for (int i = 0; i < n; i++){ if (dp[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...