Submission #1091531

#TimeUsernameProblemLanguageResultExecution timeMemory
1091531stdfloatGlobal Warming (CEOI18_glo)C++17
55 / 100
2091 ms4568 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define all(v) (v).begin(), v.end() int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n >> x; vector<int> a(n); for (auto &i : a) cin >> i; if (!x) { vector<int> v; for (int i = 0; i < n; i++) { if (v.empty() || v.back() < a[i]) v.push_back(a[i]); else v[lower_bound(all(v), a[i]) - v.begin()] = a[i]; } return cout << (int)v.size() << '\n', 0; } if (x == (int)1e9) { vector<int> v, v2(n); for (int i = 0; i < n; i++) { if (v.empty() || v.back() < a[i]) v.push_back(a[i]); else v[lower_bound(all(v), a[i]) - v.begin()] = a[i]; v2[i] = (int)v.size(); } deque<int> u; int ans = (int)v.size(); for (int i = n - 1; i > 0; i--) { if (u.empty() || u[0] > a[i]) u.push_front(a[i]); else u[upper_bound(all(u), a[i]) - u.begin() - 1] = a[i]; ans = max(ans, v2[i - 1] + (int)u.size()); } return cout << ans << '\n', 0; } int ans = 0; vector<int> v; for (int i = 0; i < n; i++) { vector<int> u = v; for (int j = i; j < n; j++) { a[j] += x; if (u.empty() || u.back() < a[j]) u.push_back(a[j]); else u[lower_bound(all(u), a[j]) - u.begin()] = a[j]; a[j] -= x; } ans = max(ans, (int)u.size()); if (v.empty() || v.back() < a[i]) v.push_back(a[i]); else v[lower_bound(all(v), a[i]) - v.begin()] = a[i]; } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...