Submission #5552775

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const ll INF = 4e18;
const int MAXN = 100010;
int N, K;

struct Seg {
	Seg* ch[2];
	int sz;
	ll add = 0;
	ll ma = -INF;
	Seg(int _sz) : sz(_sz) {
		if (sz > 1) {
			ch[0] = new Seg(sz / 2);
			ch[1] = new Seg(sz - sz / 2);
		} else {
			assert(sz == 1);
		}
	}
	void setmax(int p, ll v) {
		if (sz == 1) {
			// add are useless on leaf vertices
			ma = max(ma, v);
		} else { 
			assert(sz > 1);
			if (p < sz / 2) {
				ch[0]->setmax(p, v - add);
			} else {
				ch[1]->setmax(p - sz / 2, v - add);
			}
			ma = add + max(ch[0]->ma, ch[1]->ma);
		}
	}
	void incr(int a, int b, ll d) {
		if (b <= 0 || sz <= a) {
			// do nothing
		} else if (a <= 0 && sz <= b) {
			ma += d;
			add += d;
		} else {
			ch[0]->incr(a, b, d);
			ch[1]->incr(a - sz / 2, b - sz / 2, d);
			ma = add + max(ch[0]->ma, ch[1]->ma);
		}
	}
	ll getmax(int a, int b) {
		if (b <= 0 || sz <= a) {
			return -INF;
		} else if (a <= 0 && sz <= b) {
			return ma;
		} else {
			return add + max(ch[0]->getmax(a, b), ch[1]->getmax(a - sz / 2, b - sz / 2));
		}
	}
};

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> K;
	Seg* tr = new Seg(N + 1);
	tr->setmax(0, 0);
	for (int i = 0; i < N; i++) {
		ll X; cin >> X;
		int bnd = min(i + K + 1, N + 1);
		ll ma = tr->getmax(i, bnd);
		tr->incr(i + 1, bnd, X);
		tr->setmax(i + 1, ma);
		if (i + K <= N) {
			tr->setmax(i + K, ma + X);
		}
	}
	cout << tr->getmax(N, N + 1) << endl;

	return 0;
}

Submission Info

Judge Result