Submission #1202981

#TimeUsernameProblemLanguageResultExecution timeMemory
1202981lmquanLongest beautiful sequence (IZhO17_subsequence)C++17
0 / 100
327 ms327680 KiB
#define taskname "" #include <algorithm> #include <iostream> #include <vector> using namespace std; const int kN = 100005; const int kB = 10; struct T { int i, j, k; T(int _i = -1, int _j = -1, int _k = -1) : i(_i) , j(_j), k(_k) {} }; int n, a[kN], k[kN], d[kN], trace[kN]; pair<int, int> dp[(1 << kB) + 1][(1 << kB) + 1][kB + 1]; vector<int> p; int main() { if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { cin >> k[i]; } for (int i = 0; i <= (1 << kB); i++) { for (int j = 0; j <= (1 << kB); j++) { for (int k = 0; k <= kB; k++) { dp[i][j][k] = make_pair(0, -1); } } } for (int i = 1; i <= n; i++) { d[i] = 1; } for (int i = 1; i <= n; i++) { int l = a[i] >> kB, r = a[i] % (1 << kB); for (int j = 0; j < (1 << kB); j++) { if (k[i] >= __builtin_popcount(j & l) && (k[i] - __builtin_popcount(j & l)) <= kB && dp[j][r][k[i] - __builtin_popcount(j & l)].first + 1 > d[i]) { d[i] = dp[j][r][k[i] - __builtin_popcount(j & l)].first + 1; trace[i] = dp[j][r][k[i] - __builtin_popcount(j & l)].second; } } for (int j = 0; j < (1 << kB); j++) { if (d[i] > dp[l][j][__builtin_popcount(r & j)].first) { dp[l][j][__builtin_popcount(r & j)] = make_pair(d[i], i); } } } int ind = -1, len = 0; for (int i = 1; i <= n; i++) { if (d[i] > len) { len = d[i]; ind = i; } } cout << len << '\n'; for (int i = ind; i != -1; i = trace[i]) { p.push_back(i); } reverse(p.begin(), p.end()); for (int x : p) { cout << x << ' '; } return 0; }

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(taskname".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |     freopen(taskname".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...