제출 #1006944

#제출 시각아이디문제언어결과실행 시간메모리
1006944RifalLongest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> #include <fstream> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define endl '\n' #define mod 1000000007 #define INF 1000000000 #define INF2 2000000000 #define fi first #define se second using namespace std; double const EPS = 1e-14; const int P = 1007; typedef long long ll; using namespace __gnu_pbds; typedef long long ll; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key const int Max = 300; const int M = 1e5 + 5; int dp[Max], last[Max]; int where[M]; int cnt(int val) { int tot = 0; for(int i = 0; i < 21; i++) { if((val&(1<<i)) > 0) tot++; } return tot; } int main() { ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); int n; cin >> n; int arr[n+1], k[n+1]; int mx = 0; for(int i = 1; i <= n; i++) { cin >> arr[i]; mx = max(arr[i],mx); } for(int i = 1; i <= n; i++) cin >> k[i]; for(int i = 1; i <= n; i++) { for(int j = 0; j <= mx; j++) { if(dp[j] != 0 && cnt(arr[i]&j) == k[i]) { if(dp[arr[i]] < dp[j]+1) { dp[arr[i]] = dp[j]+1; where[i] = last[j]; last[arr[i]] = i; } } } if(dp[arr[i]] == 0) { dp[arr[i]] = 1; last[arr[i]] = i; } } pair<int,int> sol = {}; for(int i = 1; i <= n; i++) { if(sol.fi < dp[arr[i]]) { sol.fi = dp[arr[i]]; sol.se = i; } } vector<int> order; while(sol.se != 0) { order.push_back(sol.se); sol.se = where[sol.se]; } cout << order.size() << endl; for(int i = order.size()-1; i >= 0; i--) { cout << order[i] << ' '; } cout << endl; } /*7 1 4 3 3 3 4 4 2 1 2 4 6 7 4 7 1 4 2 0 2 2*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...