Submission #1308224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308224		xnoel	Global Warming (CEOI18_glo)	C++20	100 / 100	95 ms	4644 KiB

glo

#include<bits/stdc++.h>
using namespace std;

int main(){
    //freopen("1.in","r",stdin);
    int n,d;
    cin>>n>>d;
    vector<int> v(n);
    for (int i=0;i<n;i++) cin>>v[i];

    vector<int> left(n);
    
    vector<int> dp1;
    for (int i=0;i<n;i++) {
        int x=v[i];
        auto it = lower_bound(dp1.begin(), dp1.end(), x);
        int idx = it - dp1.begin();
        if (it == dp1.end()) {
            dp1.push_back(x);
        } else {
            *it = x;
        }
        left[i]=idx+1;
    }

    vector<int> r_v=v;
    reverse(r_v.begin(),r_v.end());
    for (int i=0;i<n;i++) {r_v[i]*=-1;}
    vector<int> right(n);
    vector<int> dp2;
    for (int i=0;i<n;i++) {
        int x=r_v[i];
        int new_x=x+d;
        
        auto new_it=lower_bound(dp2.begin(), dp2.end(), new_x);
        int new_idx=new_it - dp2.begin();
        right[i]=new_idx+1;


        auto it = lower_bound(dp2.begin(), dp2.end(), x);
        int idx = it - dp2.begin();
        if (it == dp2.end()) {
            dp2.push_back(x);
        } else {
            *it = x;
        }
    }

    reverse(right.begin(),right.end());
    int ans=0;
    for (int i=0;i<n;i++) {
        ans=max(ans,left[i]+right[i]-1);
    }
    cout<<ans<<"\n";
    return 0;
   
}

• 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