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;
}