Submission #1290084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290084		kubinsgk8	Global Warming (CEOI18_glo)	C++20	100 / 100	43 ms	6692 KiB

glo

#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;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 13 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 17 / 17
• Subtask 7: 25 / 25