제출 #524101

#제출 시각아이디문제언어결과실행 시간메모리
524101Sanzhar23Longest beautiful sequence (IZhO17_subsequence)C++14
0 / 100
47 ms91480 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define bug cout << "bug" << endl #define speed ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define all(x) x.begin(), x.end() #define F first #define S second #define pll pair <ll, ll> #define pii pair <int, int> #define triple pair <pair <ll, ll> , ll> #define ull unsigned long long #define ld long double #define pinode pair <node*, node*> const ll INF = 9e18 + 5; const ll inf = 1e9 + 5; const ll N = 1e5 + 5; const ll shift = 2e6; const ll mod = 1e9 + 7; const ll M = 1024 + 5; const ll LOG = 21; const ll sp = 263; const ll block = 500; const double eps = 1e-10; int n, a[N], k[N], len[N], dp[M][M][21], last[N], lg = 10, cnt[M * M]; int main(){ speed; for(int i = 0; i <= M * M - 5; i++) cnt[i] = __builtin_popcount(i); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) cin >> k[i]; memset(dp, -1, sizeof(dp)); for(int i = 1; i <= n; i++){ last[i] = -1; len[i] = 1; int firsthalf = 0, secondhalf = 0; for(int bit = 0; bit < 20; bit++){ if((1 << bit) & a[i]){ if(bit < lg) firsthalf |= (1 << bit); else secondhalf |= (1 << (bit - 10)); } } for(int mask = 0; mask < 1024; mask++){ int need = k[i] - cnt[(mask & firsthalf)]; if(0 <= need && need <= lg){ int index = dp[mask][secondhalf][need]; if(index != -1){ if(len[i] < len[index] + 1){ len[i] = len[index] + 1; last[i] = index; } } } } for(int mask = 0; mask < 1024; mask++){ int common = (mask & secondhalf); int index = dp[firsthalf][mask][common]; if(index == -1 || len[index] < len[i]){ dp[firsthalf][mask][common] = i; } } } int mx = 0, st; for(int i = 1; i <= n; i++){ if(mx < len[i]){ mx = len[i]; st = i; } } vector <int> ans; while(st != -1){ ans.pb(st); st = last[st]; } reverse(all(ans)); cout << ans.size() << endl; for(auto to : ans) cout << to << " "; } /* %I64d %I64d */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...