NC23619（小A的柱状图 ）

感受

思路

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
int sum[maxn], h[maxn];
int l[maxn], r[maxn];
int n;
void solve1(){
    stack<int> stk;
    int i = 1;
    for(; i <= n; i++){
        while(!stk.empty() && h[stk.top()] > h[i]) r[stk.top()] = i - 1, stk.pop();
        stk.push(i);
    }
    while(!stk.empty()) r[stk.top()] = i - 1, stk.pop();
}
void solve2(){
    stack<int> stk;
    int i = n;
    for(; i >= 1; i--){
        while(!stk.empty() && h[stk.top()] > h[i]) l[stk.top()] = i + 1, stk.pop();
        stk.push(i);
    }
    while(!stk.empty()) l[stk.top()] = i + 1, stk.pop();
}
void print(){
    for(int i = 1; i <= n; i++){
        printf("l[%d] = %d r[%d] = %d\n", i, l[i], i, r[i]);
    }
}
int main(){
    scanf("%d", &n);
    int x;
    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        sum[i] = sum[i - 1] + x;
    }
    for(int i = 1; i <= n; i++){
        scanf("%d", &h[i]);
    }
    solve1(); solve2();
    ll ans = 0;
    //print();
    for(int i = 1; i <= n; i++){
        ans = max(ans, (ll)1 * (sum[r[i]] - sum[l[i] - 1]) * h[i]);
    }
    printf("%lld\n", ans);
    return 0;
}