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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cassert>

#undef DEBUGP

#ifdef DEBUGP
#include <iostream>
#endif
using namespace std;

const int MAXN = 300000;
const int MAXSOLS = 444;//sqrt(MAXN);//TODO:adjust
typedef long long ll;

unsigned short solind[MAXN];
ll soldiff[MAXN];
int a[MAXN];

ll csum[MAXN+1];
ll dp_b[MAXSOLS*(MAXN+1)];
//ll dp_b[MAXSOLS][MAXN+1];

unsigned short sols = 0;

#define csol (sols-1)
#define dp(i,j) (dp_b[(i)*(n+1)+(j)])
//#define dp(i,j) (dp_b[i][j])

int main() {
	int n, k, q;
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 0; i < n; ++i) {
		scanf("%d", a+i);
		if (i < k) {
			csum[k] += a[i];
		} else {
			csum[i+1] = csum[i] + a[i] - a[i-k];
		}
	}
	// TODO: lazy calc for l?
	for (int l = 1; l <= n - k+1; ++l) {
		if(solind[l]) {
			continue;
		}
		if (sols*(n+1) >= MAXSOLS*(MAXN+1))
			break;
		solind[l] = ++sols;
		soldiff[l] = 0;
		//assert(sols <= MAXSOLS);
		//for (int i = l-1; i < l+k-1; ++i)
		//	dp[csol][i] = 0;
		for (int i = l+k-1; i <= n; ++i) { //TODO: lazy r?
			dp(csol,i) = max(dp(csol,i-1), csum[i]+dp(csol,i-k));
		}
	}
	for (int i = 0; i < q; ++i) {
		int l, r;
		scanf("%d%d", &l, &r);
		if (/*l>n-k+1 || r < k ||*/ r-l + 1 < k)
			printf("0\n");
		else
			printf("%lld\n", dp(solind[l] ? solind[l]-1 : sols-1, r) - soldiff[l]);
	}
	return 0;
}