题解 | 能量辐射

#include <iostream>
#include<vector>
#include<stack>
using namespace std;

struct Station{
    int h,v;
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<Station>s(n);
    if(n<2){
        cout<<0<<endl;
        return 0;
    }
    vector<long long>cnt(n,0);
    for(int i=0;i<n;i++){
        cin>>s[i].h>>s[i].v;
    }
    vector<int>left_h(n,-1);
    stack<int>st;
    for(int i=0;i<n;i++){
        while(!st.empty()&&s[st.top()].h<=s[i].h)st.pop();
        if(!st.empty())left_h[i]=st.top();
        st.push(i);
    }
    vector<int>right_h(n,n);
    st=stack<int>();
    for(int i=n-1;i>=0;i--){
        while(!st.empty()&&s[st.top()].h<=s[i].h)st.pop();
        if(!st.empty())right_h[i]=st.top();
        st.push(i);
    }
    for(int i=0;i<n;i++){
        int l=left_h[i];
        int r=right_h[i];
        if(l!=-1)cnt[l]+=s[i].v;
        if(r!=n)cnt[r]+=s[i].v;
    }
    long long maxv=0;
    for(long long v:cnt){
        if(v>maxv)maxv=v;
    }
    cout<<maxv<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")