제출 #1290084

#제출 시각아이디문제언어결과실행 시간메모리
1290084kubinsgk8Global Warming (CEOI18_glo)C++20
100 / 100
43 ms6692 KiB
#include<bits/stdc++.h>
using namespace std;

//_______________________________________________


const int N=2e5+2;

long long n, x;

long long a[N];

long long dp1[N], dp2[N];

long long ans[N];

long long dapan=0;

//_______________________________________________


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>x;

    for(int i=1; i<=n; i++)cin>>a[i];

    for(int i=0; i<=n; i++)dp1[i]=dp2[i]=INT_MAX;

    for(int i=1; i<=n; i++)
    {
        int pos=lower_bound(dp1+1, dp1+n+1, a[i])-dp1;

        ans[i]=pos;

        dp1[pos]=a[i];

        dapan=max(dapan, ans[i]);

    }




    for(int i=n; i>=1; i--)
    {
        int pos=lower_bound(dp2, dp2+n+1, -a[i]+x)-dp2;

        dapan=max(dapan, pos+ans[i]);


        pos=lower_bound(dp2, dp2+n+1, -a[i])-dp2;

        dp2[pos]=-a[i];

    }

    cout<<dapan;





    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...