Submission #699667

#	Time	Username	Problem	Language	Result	Execution time	Memory
699667		kim	Global Warming (CEOI18_glo)	C++11	10 / 100	33 ms	4572 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

*/

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:17:9: warning: variable 'dpl' set but not used [-Wunused-but-set-variable]
   17 |     int dpl[2][n];
      |         ^~~

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