Submission #1048182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1048182		khanhtb	Global Warming (CEOI18_glo)	C++14	100 / 100	40 ms	7128 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fi first
#define se second
const int maxN=2e5+5;
const ll inf=2e18;
int n,x,a[maxN+1],dp[maxN+1];
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>x;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    vector<ll> b(n+1,inf);
    b[0]=-inf;
    int mx=0;
    for(int i=1;i<=n;i++)
    {
        int k=lower_bound(b.begin(),b.end(),a[i])-b.begin();
        b[k]=a[i];
        dp[i]=k;
        mx=max(mx,k);
    }
    vector<ll> c(n+1,inf);
    c[0]=-inf;
    for(int i=n;i>=1;i--)
    {
        int k=lower_bound(c.begin(),c.end(),x-a[i])-c.begin();
        mx=max(mx,dp[i]+k);
        k=lower_bound(c.begin(),c.end(),-a[i])-c.begin();
        c[k]=-a[i];
    }
    cout<<mx-1;
}

• 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