V11WATER - Nước đọng

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;

#define N 100005

int h[N], hl[N], hr[N], n;

int main() {
    scanf("%d",&n); for(int i = 0; i < n;++i) scanf("%d",h+i);
    stack<int> st;
    int mx = 0;
    for(int i=0;i<n;++i) {
        mx = max(mx, h[i]);
        hl[i] = mx;
        /*while(!st.empty() && st.top() <= h[i]) st.pop();
        hl[i] = st.empty() ? h[i] : st.top();
        st.push(h[i]);*/
    }
    //while(!st.empty()) st.pop();
    mx = 0;
    for(int i=n-1;i>=0;--i) {
        mx = max(mx, h[i]);
        hr[i] = mx;
        /*while(!st.empty() && st.top() <= h[i]) st.pop();
        hr[i] = st.empty() ? h[i] : st.top();
        st.push(h[i]);*/
    }
#ifndef ONLINE_JUDGE
    for(int i = 0; i < n; ++i) printf("%d ", hl[i]); putchar(10);
    for(int i = 0; i < n; ++i) printf("%d ", hr[i]); putchar(10);
#endif
    long long res = 0;
    for(int i = 0; i < n; ++i) res += min(hl[i],hr[i]) - h[i];
    printf("%lld\n", res);
    return 0;
}

Download