158742025-03-07 11:47:43UVincePicnic's Tablecpp17Wrong answer 0/1002.608s211764 KiB
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ll n;
    cin>>n;
    vector<ll> h(n+2);
    vector<int> l(n+1),r(n+1);
    h[0]=LLONG_MAX;
    h[n+1]=LLONG_MAX;
    for (int i=1;i<=n;i++) cin>>h[i];
    stack<int> mx;
    mx.push(0);
    for (int i=1;i<=n;i++){
        while (!mx.empty() && h[mx.top()]<=h[i]) mx.pop();
        l[i]=mx.top();
        mx.push(i);
    }
    stack<int> mx2;
    mx2.push(n+1);
    for (int 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<int> st;
    st.push(0);
    for (int i=1;i<=n;i++){
        int 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;
        int left=l[last]+1;
        int right=r[i]-1;

        ll cur=i-last+1;
        if (last-left<right-i){
            cur+=2*(last-left);
            int mid = (last+i)/2;
            int push = (i-mid)*2-1;
            if (mid*2!=last+i) push++;
            cur+=min(right-i, push);
        }
        else {
            cur+=2*(right-i);
            int mid = (last+i)/2;
            int 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
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask20/10
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Wrong answer206ms17964 KiB
6Accepted209ms17848 KiB
7Accepted211ms17972 KiB
subtask30/15
8Accepted1ms316 KiB
9Accepted1ms316 KiB
10Accepted1ms316 KiB
11Wrong answer1ms508 KiB
12Accepted1ms316 KiB
13Wrong answer1ms316 KiB
14Accepted1ms316 KiB
subtask40/15
15Wrong answer4ms416 KiB
16Wrong answer1ms316 KiB
17Accepted1ms316 KiB
18Accepted4ms316 KiB
19Accepted3ms520 KiB
20Accepted1ms316 KiB
21Accepted3ms316 KiB
subtask50/25
22Wrong answer52ms2864 KiB
23Wrong answer50ms2732 KiB
24Accepted52ms2864 KiB
25Accepted1ms316 KiB
26Wrong answer50ms2868 KiB
27Wrong answer1ms512 KiB
28Accepted1ms508 KiB
29Accepted50ms2732 KiB
30Wrong answer32ms2544 KiB
subtask60/35
31Time limit exceeded2.599s209584 KiB
32Time limit exceeded2.601s210864 KiB
33Time limit exceeded2.601s211764 KiB
34Time limit exceeded2.601s210740 KiB
35Accepted1ms316 KiB
36Time limit exceeded2.592s208188 KiB
37Time limit exceeded2.594s205876 KiB
38Wrong answer1ms316 KiB
39Accepted1ms316 KiB
40Time limit exceeded2.608s202480 KiB