158772025-03-07 12:03:06UVincePicnic's Tablecpp17Wrong answer 0/1002.035s253232 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n;
    cin>>n;
    vector<ll> h(n+2);
    vector<ll> l(n+1),r(n+1);
    h[0]=LLONG_MAX;
    h[n+1]=LLONG_MAX;
    for (ll i=1;i<=n;i++) cin>>h[i];
    stack<ll> mx;
    mx.push(0);
    for (ll i=1;i<=n;i++){
        while (!mx.empty() && h[mx.top()]<=h[i]) mx.pop();
        l[i]=mx.top();
        mx.push(i);
    }
    stack<ll> mx2;
    mx2.push(n+1);
    for (ll i=n;i>=1;i--){
        while (!mx2.empty() && h[mx2.top()]<=h[i]) mx2.pop();
        r[i]=mx2.top();
        mx2.push(i);
    }

    ll ans=0;
    stack<ll> st;
    st.push(0);
    for (ll i=1;i<=n;i++){
        ll last=-1;
        while (!st.empty() && h[st.top()]<=h[i]) {last=st.top();st.pop();}
        st.push(i);
        if (last==-1 || h[last]!=h[i]) continue;
        ll left=l[last]+1;
        ll right=r[i]-1;

        ll cur=i-last+1;
        if (last-left<right-i){
            cur+=2*(last-left);
            ll mid = (last+i)/2;
            ll push = (i-mid)*2-1;
            if (mid*2!=last+i) push--;
            cur+=min(right-i, push);
        }
        else {
            cur+=2*(right-i);
            ll mid = (last+i)/2;
            ll push = (mid-last)*2-1;
            if (mid*2!=last+i) push++;
            cur+=min(last-left, push);
        }
        ans=max(ans, cur);
    }
    cout<<ans;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask20/10
3Accepted1ms496 KiB
4Accepted1ms316 KiB
5Wrong answer105ms23860 KiB
6Accepted114ms23852 KiB
7Accepted108ms23836 KiB
subtask30/15
8Accepted1ms508 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Wrong answer1ms500 KiB
12Accepted1ms316 KiB
13Wrong answer1ms376 KiB
14Accepted1ms316 KiB
subtask40/15
15Wrong answer2ms508 KiB
16Wrong answer1ms508 KiB
17Accepted1ms316 KiB
18Accepted2ms316 KiB
19Accepted2ms316 KiB
20Accepted1ms316 KiB
21Accepted2ms316 KiB
subtask50/25
22Accepted20ms2700 KiB
23Wrong answer19ms2724 KiB
24Accepted20ms2612 KiB
25Accepted1ms364 KiB
26Wrong answer18ms2612 KiB
27Wrong answer1ms512 KiB
28Accepted1ms500 KiB
29Accepted18ms2788 KiB
30Wrong answer14ms2796 KiB
subtask60/35
31Accepted1.766s253232 KiB
32Accepted1.963s251916 KiB
33Accepted1.843s250932 KiB
34Accepted2.035s251968 KiB
35Accepted1ms316 KiB
36Accepted1.585s235192 KiB
37Wrong answer1.488s235060 KiB
38Wrong answer1ms316 KiB
39Accepted1ms316 KiB
40Wrong answer1.366s235060 KiB