제출 #1337582

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1337582		piolk	Global Warming (CEOI18_glo)	C++20	100 / 100	42 ms	2756 KiB

glo

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

constexpr int inf=2e9;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,x;
    cin>>n>>x;

    vector<int> l(n);
    for (int i=0;i<n;i++) cin>>l[i];

    vector<int> lis(n);

    vector<int> dp(n+1,inf);
    dp[0]=-inf;
    for (int i=0;i<n;i++){
        int pos=lower_bound(dp.begin(),dp.end(),l[i])-dp.begin();
        dp[pos]=min(dp[pos],l[i]);

        lis[i]=pos;
    }

    int ans=0;

    dp.assign(n+1,-inf);
    dp[0]=inf;
    for (int i=n-1;i>=0;i--){
        int right=lower_bound(dp.begin(),dp.end(),l[i]-x,greater<int>())-dp.begin();
        ans=max(ans,lis[i]+right-1);

        int pos=lower_bound(dp.begin(),dp.end(),l[i],greater<int>())-dp.begin();
        dp[pos]=max(dp[pos],l[i]);
    }

    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