Editorial for Lamp

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

To solve the problem, it's enough to iterate on the given list once. We can take bench counts for each place that we can build the lamp on.

In the solution below, \(bench\_count\) holds the total bench count between \(i\) and \(i-2k-1\). This means that at \(i^{th}\) iteration, we actually calculate the total bench count if the lamp is built on \(i-k\). So we need to subtract the bench count in \(i-2*k-1\) and add the bench count in \(i\).

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int siz = 300005;

ll arr[siz];
ll n, k, bench_count, max_bench_count;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>arr[i];
        int removed_index=i-2*k-1;
        if(removed_index>=0) bench_count-=arr[removed_index];
        bench_count+=arr[i];
        max_bench_count=max(max_bench_count, bench_count);
    }

    cout<<max_bench_count;
}