V11WATER - Nước đọng
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
long long a[100001],n,maxl[100001],maxr[100001],max,maxi;
long long A[100001],KQ;
long long min(long long a, long long b)
{
if(a<b) return a;
return b;
}
int main()
{
// freopen("V11WATER.in","r",stdin);
scanf("%lld",&n);
for(int i = 1;i<=n;i++)
scanf("%lld",&a[i]);
maxl[1] = 1;
max = a[1];
for(int i = 2;i<=n;i++)
{
if(a[i]>max)
{
maxl[i] = i;
max = a[i];
}
else maxl[i] = maxl[i-1];
}
maxr[n] = n;
max = a[n];
for(int i = n-1;i>=1;i--)
{
if(a[i]>max)
{
maxr[i] = i;
max = a[i];
}
else maxr[i] = maxr[i+1];
}
for(int i = 1;i<=n;i++)
{
if(a[i]<min(a[maxl[i]],a[maxr[i]]))
KQ = KQ + min(a[maxl[i]],a[maxr[i]]) - a[i];
}
printf("%lld",KQ);
// getch();
}