제출 #1343216

#제출 시각아이디문제언어결과실행 시간메모리
1343216PakinDioxideGlobal Warming (CEOI18_glo)C++17
100 / 100
40 ms4172 KiB
#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    ll x; cin >> x;
    ll a[n]; for (auto &e : a) cin >> e;
    int dp1[n], dp2[n];
    vector <int> v;
    for (int i = 0; i < n; i++) {
        auto it = lower_bound(v.begin(), v.end(), a[i]);
        if (it == v.end()) v.emplace_back(a[i]), dp1[i] = v.size();
        else *it = a[i], dp1[i] = it - v.begin() + 1;
    }
    v.clear();
    for (int i = n-1; i >= 0; i--) {
        dp2[i] = lower_bound(v.begin(), v.end(), -a[i] + x) - v.begin();
        auto it = lower_bound(v.begin(), v.end(), -a[i]);
        if (it == v.end()) v.emplace_back(-a[i]);
        else *it = -a[i];
    }
    int mx = 0;
    for (int i = 0; i < n; i++) mx = max(mx, dp1[i] + dp2[i]);
    cout << mx << '\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...