Submission #1218060

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218060		lukasuliashvili	Global Warming (CEOI18_glo)	C++20	100 / 100	78 ms	6472 KiB

glo

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define first fs 
#define sc second 
#define pb push_back
#define int long long 
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=1e6+5;
int ans,suf[N],pref[N],dppr[N],dpsuf[N],a[N];
signed main(){
    int n,x;
    cin>>n>>x;rep(i,1,n){cin>>a[i];dppr[i]=1e18;dpsuf[i]=1e18;}
    rep(i,1,n){
        int idx=lower_bound(dppr+1,dppr+n+1,a[i]-x)-dppr;
        dppr[idx]=a[i]-x;
        pref[i]=idx;
        ans=max(ans,idx);
    }
    
    reverse(a+1,a+n+1);
    rep(i,1,n){
        int idx2=lower_bound(dpsuf+1,dpsuf+n+1,-(a[i]-x))-dpsuf;
        ans=max(ans,pref[n-i+1]+idx2-1);
        int idx=lower_bound(dpsuf+1,dpsuf+n+1,-a[i])-dpsuf;
        dpsuf[idx]=-a[i];
    }
    cout<<ans<<endl;

}

• 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