AGC008B Contiguous Repainting

• 概要

N個の整数列が与えられる。連続するK(<=N)個を選び、全てを白で塗るか全てを黒で塗る（この操作は何回でもおこなうことができる）。色は上書きされる。 黒く塗られた整数の総和の最大値をもとめよ

• 方針

操作順を逆に考える。

そのまま）何回かK個を塗る操作をおこなったあと、最後にK個を白or黒で塗る操作を行う。
逆）最後の操作で塗ったK個の色が確定させ、次の最後から二番目の操作で塗った色を確定させる。（色は上書きされない）　　

K区間以外は自由な色に確定させることが可能。のでKの区間を探索し、区間の和が>0なら黒、そうでなければ白とする。それ以外の区間はai > 0なら黒、そうでなければ白とする。

単純にやると計算量がO(N²)でアウト。そこで、単純な累積和(=ai)と、0より大きい要素のみの累積和(=bi)を予め求めておく。すると、Kの区間が決まると、K区間の和はaiを使ってO(1)、それ以外の区間の和もbiを使ってO(1)で求まる。よって計算量O(N)でいける。

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
int main() {
    int n, k;
    cin >> n >> k;
    vector<ll> v(n+1), a(n+1, 0), b(n+1, 0);
    for(int i=1;i<n+1;i++) cin >> v[i];
 
    for(int i=1;i<n+1;i++) {
        a[i] += v[i] + a[i-1];
    }
    for(int i=1;i<n+1;i++) {
        if(v[i] > 0)
            b[i] += v[i] + b[i-1];
        else
            b[i] = b[i-1];
    }
 
    ll ans = -1e15;
    for(int i=1;i <= n - k + 1;i++) {
        ll ans_i = 0;
        ll k_range_sum = a[i+k-1] - a[i-1];
 
        ans_i += max<ll>(k_range_sum, 0);
        ans_i += b[i-1];
        ans_i += (b[n] - b[i+k-1]);
        ans = max<ll>(ans, ans_i);
    }
 
    cout << ans << endl;
}