Submission #699665

#	Time	Username	Problem	Language	Result	Execution time	Memory
699665		kim	Global Warming (CEOI18_glo)	C++11	22 / 100	42 ms	3924 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

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[2][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[0][i]=vec.size();
        dpl[1][i]=*vec.rbegin();
    }
    int ans=vec.size();
    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();
    }
    for(int i=0;i<=n-2;i++){
        auto itr=upper_bound(arr+i+1,arr+n,dpl[1][i]-k);
        if(itr==arr+n) continue;
        ans=max(ans,dpl[0][i]+dpr[itr-arr]);
    }
    cout<<ans;
    return 0;
}
/*

10 0
2 4 1 2 5 6 3 9 10 1

8 10
7 3 5 12 2 7 3 4

*/

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