Submission #1318152

#TimeUsernameProblemLanguageResultExecution timeMemory
1318152kawhietGlobal Warming (CEOI18_glo)C++20
100 / 100
44 ms2780 KiB
#include <bits/stdc++.h> using namespace std; constexpr int inf = 2e9; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, x; cin >> n >> x; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> dp(n, inf), p(n); for (int i = 0; i < n; i++) { int j = ranges::lower_bound(dp, a[i]) - dp.begin(); dp[j] = a[i]; p[i] = j + 1; } ranges::fill(dp, inf); int ans = ranges::max(p); for (int i = n - 1; i >= 0; i--) { int pos = ranges::lower_bound(dp, -a[i] + x) - dp.begin(); ans = max(ans, p[i] + pos); int j = ranges::lower_bound(dp, -a[i]) - dp.begin(); dp[j] = -a[i]; } cout << ans << '\n'; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...