便宜上 \(h_0=0,h_{N+1}=0\) とします。 答えは \(\displaystyle\dfrac{1}{2}\sum_{k=0}^N\left|h_{k+1}-h_k\right|\) です。

例えば、入力例 2 ではこのようになるので、答えは \(\dfrac{1}{2}(3+2+1+1+2+1)=5\) です。

これを計算することで \(O(N)\) 時間で答えを出すことができます。 以下ではこれを示します。

まず、\(\displaystyle\dfrac{1}{2}\sum_{k=0}^N\left|h_{k+1}-h_k\right|\) 回以上の水やりが必要であることを示します。

水やりをする回数を \(X\) として、\(X\) 回の水やりを整数の組 \((l_i,r_i)\ (1\leq i\leq X)\) で表すことにします。
また、整数 \(k\ (0\leq k\leq N+1)\) に対して、\(l_i=k\) となる \(i\) の個数を \(\mathit{cl}_k\)、\(r_i=k\) となる \(i\) の個数を \(\mathit{cr}_k\) と書くことにします。
\(l_i, r_i\) は \(1\) 以上 \(N\) 以下の数なので \[\qquad\ \displaystyle\sum_{k=1}^N\mathit{cl}_k=\sum_{k=1}^N\mathit{cr}_k=X\ \qquad\cdots(1)\] と \[\mathit{cl}_0=\mathit{cr}_0=\mathit{cl}_{N+1}=\mathit{cr}_{N+1}=0\quad\cdots(2)\] が成り立つことに注意してください。

\(0\leq k\leq N\) について、 \(h_k\) と \(h_{k+1}\) の差を考えると、次が成り立っている必要があります。

\[h_k-h_{k+1}=\mathit{cl}_{k+1}-\mathit{cr}_k\]

\(\mathit{cl}_{k+1},\mathit{cr}_k\) はいずれも \(0\) 以上の整数なので、次のような不等式が成り立ちます。

\[\mathit{cl}_{k+1}\geq h_k-h_{k+1}\]

\[\phantom{{}_{+l}}\mathit{cr}_k\geq h_{k+1}-h_k\]

\(\mathit{cl}_{k+1}\geq0,\mathit{cr}_k\geq0\) と合わせて、次の式を得ます。

\[\mathcal{cl}_{k+1}+\mathit{cr}_k\geq\left|h_{k+1}-h_k\right|\]

\(0\leq k\leq N\) について両辺を全部加えると、

\[\sum_{k=1}^N\mathcal{cl}_k+\sum_{k=1}^N\mathcal{cr}_k+\mathcal{cl}_{N+1}+\mathcal{cr}_0\geq\sum_{k=0}^N\left|h_{k+1}-h_k\right|\]

となります。\((1)\) と \((2)\) を使うと、左辺は \(2X\) であることがわかるので、結局

\[X\geq\dfrac{1}{2}\sum_{k=0}^N\left|h_{k+1}-h_k\right|\]

となり、示されました。

次に、実際に \(\displaystyle\dfrac{1}{2}\sum_{k=0}^N\left|h_{k+1}-h_k\right|\) 回の水やりで条件が満たせることを確認します。

上の図のように、\(h_{k+1}>h_k\) であるような \(k\) について、それぞれの高さでヒストグラムの中を進めるだけ右に進んだところを \(l\) として \((k,l)\) に操作することを考えると、必ずそれぞれの \(k\) と高さに対して \(l\) が対応し、条件を満たせることがわかります。

例えば、入力例2では次のようになります。

よって、\(\displaystyle\dfrac{1}{2}\sum_{k=0}^N\left|h_{k+1}-h_k\right|\) 回の水やりで条件が満たせます。

以上より、答えが \(\displaystyle\dfrac{1}{2}\sum_{k=0}^N\left|h_{k+1}-h_k\right|\) であることが示されました。

この方針でACするコードは次のようになります。 C++での提出

#include<bits/stdc++.h>

int main(){
  using namespace std;
  
  int N;
  cin >> N;
  
  vector<int> h(N + 2);
  for(int i = 0; i < N; ++i)cin >> h[i + 1];
  
  int answer = 0;
  for(int i = 0; i < N + 1; ++i)answer += abs(h[i + 1] - h[i]);
  
  cout << answer / 2 << endl;
  
  return 0;
}

Python での提出

N = int(input())

h = [0] + list(map(int, input().split())) + [0]

ans = 0

for i in range(0, N + 1):
  ans += abs(h[i + 1] - h[i])

print(ans // 2)