제출 #1278062

#제출 시각아이디문제언어결과실행 시간메모리
1278062tagizadeGlobal Warming (CEOI18_glo)C++17
100 / 100
48 ms4364 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    ll x;
    if (!(cin >> n >> x)) return 0;
    vector<ll> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    vector<int> pref(n);
    const ll INF = (ll)9e18;
    vector<ll> dp(n, INF);
    int ans = 0;

    for (int i = 0; i < n; ++i) {
        int pos = lower_bound(dp.begin(), dp.end(), a[i]) - dp.begin();
        dp[pos] = a[i];
        pref[i] = pos + 1;
        ans = max(ans, pref[i]);
    }

    fill(dp.begin(), dp.end(), INF);
    for (int i = n - 1; i >= 0; --i) {
        int pos = lower_bound(dp.begin(), dp.end(), -a[i] + x) - dp.begin();
        ans = max(ans, pref[i] + pos);
        int ins = lower_bound(dp.begin(), dp.end(), -a[i]) - dp.begin();
        dp[ins] = -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...