(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #172961

#TimeUsernameProblemLanguageResultExecution timeMemory
172961VEGAnnLongest beautiful sequence (IZhO17_subsequence)C++14
100 / 100
5795 ms92912 KiB
#include <bits/stdc++.h> #define sz(x) ((int)x.size()) #define PB push_back #define all(x) x.begin(),x.end() using namespace std; const int N = 100100; const int PW = 10; const int VL = (1 << PW); const int oo = 2e9; const int K = 11; vector<int> vc; int n, a[N], k[N], pr[N], f[N], ans = 0, nm = -1, ff[VL][VL][K], loc[VL][VL][K]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> k[i]; for (int i = 0; i < n; i++) { f[i] = 1; int fi = a[i] % VL, se = (a[i] >> 10); for (int pf = 0; pf < VL; pf++){ int kl = k[i] - __builtin_popcount(pf & fi); if (kl >= 0 && kl < 11 && f[i] < ff[pf][se][kl] + 1){ f[i] = ff[pf][se][kl] + 1; pr[i] = loc[pf][se][kl]; } } for (int ns = 0; ns < VL; ns++){ int kl = __builtin_popcount(ns & se); if (ff[fi][ns][kl] < f[i]){ ff[fi][ns][kl] = f[i]; loc[fi][ns][kl] = i; } } if (ans < f[i]){ ans = f[i]; nm = i; } } for (;;){ vc.PB(nm + 1); if (f[nm] == 1) break; nm = pr[nm]; } reverse(all(vc)); cout << sz(vc) << '\n'; for (int x : vc) cout << x << " "; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...