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