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
#include <iostream>

using namespace std;

int n, k, q;
long long dp[300001];
long long s[300005];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k >> q;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		s[i] += s[i-1];
	}
	
	for (int i = n; i > k; i--) s[i] -= s[i-k];
	
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (r - l + 1 < k) cout << "0\n";
		else {
			dp[l+k-1] = max(0ll, s[l+k-1]);
			int kon = min(r, l + 2*k-2);
			for (int i = l + k; i <= kon; i++) {
				dp[i] = max(dp[i-1], s[i]);
			}
			if (l+k <= r) for (int i = kon+1; i<=r; i++) {
				dp[i] = max(dp[i-1], s[i] + dp[i-k]);
			}
			//for (int i=l; i<=r; i++) cerr<<dp[i] <<' ';
			//cerr<<endl;
			cout << dp[r] << '\n';
			fill(dp+l, dp+r+1,0);
		}
	}
}