1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

constexpr size_t limit = 3e5+5;

int n, k, q, a[limit], i, l, r;
long long b[limit], maks, s;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> q;
	for(i=1; i<=n; ++i) {
		cin >> a[i];
	}
	while(q--) {
		cin >> l >> r;
		// cerr << l << '-' << r << endl;
		// 1 2 3 4 5 6 7 8
		//         + + +
		//         -     +
		s = 0, maks = 0;
		for(i=l-1; i<min(l-1+k,r+1); ++i) s += a[i];
		for(i=l-1+k; i<=r; ++i) {
			s += a[i] - a[i-k];
			maks = max(maks, b[i-k]);
			b[i] = maks + max(s, 0ll);
			// cerr << i << ' ' << s << ' ' << b[i] << endl;
		}
		for(i=max(l-1+k, r-k+1); i<=r; ++i) {
			// cerr << maks << ' ' << b[i] << endl;
			maks = max(maks, b[i]);
		}
		cout << maks << '\n';
		for(i=l-1+k; i<=r; ++i)
			b[i] = 0;
	}
	
}