Submission #699655

#	Time	Username	Problem	Language	Result	Execution time	Memory
699655		kim	Global Warming (CEOI18_glo)	C++11	0 / 100	55 ms	3380 KiB

glo

#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]=vec.size();
    }
    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;
}

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