Tough Journey [CODE FESTIVAL 2018 Final E]

https://beta.atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_e

解説

https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3623338

見方を変えて解く。
ある街で飲むペットボトルをどこで買うかということを考える。
ペットボトルはK本まで持つことができるので、K-1個前の街までで買うことができる。
最適な動きを考えると、その中で一番安いペットボトルを買うのが良い。
よって、全ての街について最安なペットボトルをセグメントツリーで見つけてきて、総和を取ると答え。

（先頭から貪欲に最適に動いていくのでも正解できそう）

int N, K, A[101010];
SegTree<int, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) {
        cin >> A[i];
        st.update(i, A[i]);
    }
 
    ll ans = 0;
    rep(i, 0, N) ans += st.get(max(0, i - K + 1), i + 1);
    cout << ans << endl;
}