# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
422625 | 2021-06-10T09:21:46 Z | snasibov05 | Global Warming (CEOI18_glo) | C++14 | 0 ms | 0 KB |
#include <iostream> #include <vector> using namespace std; #define oo 1000000000 int main() { int n, x; cin >> n >> x; vector<int> v(n); for (int i = 0; i < n; ++i) { cin >> v[i]; } int sz = 1; vector<int> dp(n); vector<int> c(n+1, oo); c[0] = 0; c[1] = v[0]; dp[0] = 1; for (int i = 1; i < n; ++i) { if (v[i] < c[1]) c[1] = v[i], dp[i] = 1; else if (v[i] > c[sz]) c[sz+1] = v[i], dp[i] = ++sz; else { int k = lower_bound(c.begin(), c.end(), v[i]) - c.begin(); c[k] = v[i]; dp[i] = k; } } int ans = dp[n-1]; c.assign(n+1, 0); c[0] = oo; c[1] = v[n-1] + x; dp[n-1] = 1; sz = 1; for (int i = n-2; i >= 0; --i){ if (v[i] > c[1]) ans = max(ans, dp[i]); else if (v[i] < c[sz]) ans = max(ans, dp[i] + sz); else{ int k = upper_bound(c.rbegin(), c.rend(), v[i]) - c.rbegin(); k = n - k; ans = max(ans, dp[i] + k - 1); } if (v[i] + x > c[1]) c[1] = v[i] + x; else if (v[i] + x < c[sz]) c[++sz] = v[i] + x; else{ int k = upper_bound(c.rbegin(), c.rend(), v[i] + x) - c.rbegin(); k = n - k + 1; c[k] = v[i] + x; } } cout << ans << "\n"; return 0; }