제출 #1275066

#제출 시각아이디문제언어결과실행 시간메모리
1275066bayengGlobal Warming (CEOI18_glo)C++20
100 / 100
54 ms3136 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int n, x;
    cin >> n >> x;
    int a[n+2];
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    vector<int>lis(n+2), dp, tmp;
    lis[1] = 1;
    tmp.push_back(a[1]);
    for(int i=2;i<=n;i++){
        if(a[i]>tmp.back()){
            tmp.push_back(a[i]);
            lis[i] = tmp.size();
        }
        else{
            int ind = lower_bound(tmp.begin(), tmp.end(), a[i])-tmp.begin();
            lis[i] = ind+1;
            tmp[ind] = a[i];
        }
        // for(auto v:tmp){cout << v << " ";}
        // cout << "| " << lis[i];
        // cout << endl;
    }
    int ans = 1;
    ans = max(ans, lis[n]);
    dp.push_back(a[n]*-1);
    for(int i=n-1;i>=1;i--){
        int nex = a[i]*-1;
        int cari = lower_bound(dp.begin(),dp.end(), nex+x)-dp.begin();
        // cout << cari << " " << lis[i] << endl;
        ans = max(ans, lis[i] + cari);
        if(nex>dp.back()){dp.push_back(nex);}
        else{
            int ind = lower_bound(dp.begin(), dp.end(), nex)-dp.begin();
            dp[ind] = nex;}
        // for(auto v:dp){cout << v << " ";}
        // cout << endl;
    }
    cout << ans << endl;
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...