SRM518 Div1 Medium

500

とりあえず条件の通りに実装して終わり。

"どうせこんな感じだろう"で通してしまった。
正答率を見て問題を選んでいることを後悔した。


他の解法もあるそうなので考えてみよう。

class ConvexSequence {
public:
  long long getMinimum(vector <int> a)
  {
    const int N = a.size();
    lli ret = 0;

    while (true) {
      lli tmp = ret;
      for (int i = 1; i < N - 1; ++i) {
        int b = min(a[i], (a[i - 1] + a[i + 1]) / 2);
        ret += abs(a[i] - b);
        a[i] = b;
      }
      if (tmp == ret) break;
    }

    return ret;
  }