Abundant Resources [全国統一プログラミング王決定戦本戦 A]

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_a

前提知識

• 累積和

解説

https://atcoder.jp/contests/nikkei2019-final/submissions/4312713

累積和を知っていれば、それぞれの整数Kについて全探索できると分かる。
練習のために尺取法みたいに実装するのもいいかもしれない。
累積和を使えば、ある区間の総和がO(1)で計算できる。
なので、全てのkについて、その中で全ての区間（左端を全探索すると考える）について全探索するとO(NK)で間に合う。

int N;
ll A[3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];
 
    Ruisekiwa<ll> rui(A, A + N);
    rep(k, 1, N + 1) {
        ll ans = -1;
        rep(i, 0, N) chmax(ans, rui.get(i, i + k));
        cout << ans << endl;
    }
}