제출 #1358456

#제출 시각아이디문제언어결과실행 시간메모리
135845612345678Global Warming (CEOI18_glo)C++17
28 / 100
2095 ms3372 KiB
#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, x, a[nx], b[nx], lis[nx], lds[nx], res; // lis[i] = lis when considering prefix i
map<int, int> mp;

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>x;
    for (int i=1; i<=n; i++) cin>>a[i], b[i]=-a[i];
    vector<int> v;
    for (int i=1; i<=n; i++)
    {
        auto idx=lower_bound(v.begin(), v.end(), a[i])-v.begin();
        if (idx==v.size()) v.push_back(a[i]);
        else v[idx]=a[i];
        lis[i]=idx+1;
    }   
    v.clear();
    for (int i=n; i>=1; i--)
    {
        auto idx=lower_bound(v.begin(), v.end(), b[i])-v.begin();
        if (idx==v.size()) v.push_back(b[i]);
        else v[idx]=b[i];
        lds[i]=idx+1;
    }
    for (int i=1; i<=n; i++) res=max({res, lis[i], lds[i]});
    for (int i=1; i<=n; i++) for (int j=i+1; j<=n; j++) if (a[i]<a[j]+x) res=max(res, lis[i]+lds[j]);    
    cout<<res;
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…