제출 #699654

#제출 시각아이디문제언어결과실행 시간메모리
699654kimGlobal Warming (CEOI18_glo)C++11
0 / 100
59 ms4580 KiB
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define s second
#define f first

const int N=1e6;
bool prime[N+10];
int dp[N+10];

int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    int n,k; cin>>n>>k;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    vector<int> vec;
    int dpl[n];
    for(int i=0;i<n;i++){
        auto itr=lower_bound(vec.begin(),vec.end(),arr[i]);
        if(itr==vec.end()) vec.push_back(arr[i]);
        else *itr=arr[i];
        dpl[i]=itr-vec.begin()+1;
    }
    vec.clear();
    int dpr[n];
    for(int i=n-1;i>=0;i--){
        auto itr=lower_bound(vec.begin(),vec.end(),arr[i],greater<int>());
        if(itr==vec.end()) vec.push_back(arr[i]);
        else *itr=arr[i];
        dpr[i]=itr-vec.begin()+1;
    }
    int ans=-1;
    for(int i=0;i<=n-2;i++){
        auto itr=upper_bound(arr+i+1,arr+n,arr[i]-k);
        if(itr==arr+n) continue;
        ans=max(ans,dpl[i]+dpr[itr-arr]);
    }
    cout<<ans;
    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...