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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <vector>
#include <map>
#include <assert.h>

int k;

int max(int a, int b){
	return a > b ? a : b;
}

void caclucateAggr(std::vector<int> & sol, std::vector<int> & aggr, int k){
	int first = 0;
	for(int i = 0; i < k; ++i) first += sol[i];
	aggr.push_back(first);
	for(int i = k; i < (int)sol.size(); ++i){
		first = first + sol[i] - sol[i-k];
		aggr.push_back(first);
	}
}

typedef std::pair<int,int> IntPair;

std::map<IntPair, int> cache;

int calculateMax(std::vector<int> & aggr, int begin, int end){
	if (begin > end - k + 1)
		return 0;
//	assert(begin < aggr.size());
	IntPair key(begin,end);

	if (!cache.empty() && cache.find(IntPair(begin,end)) != cache.end()){
//		printf("CACHE (%d %d) %d\n", key.first, key.second, cache[key]);
		return cache[key];
	}
//	int res = 0;
//	for(int i = begin; i <= end - k + 1; ++i){
	int res = max(aggr[begin] + calculateMax(aggr, begin + k, end), calculateMax(aggr, begin + 1, end));
//	}
	cache[key] = res;
//	printf("(%d %d) %d\n", key.first, key.second, res);
	return res;
}


int main(){
	int n,q;
	scanf("%d %d %d",&n,&k,&q);
	std::vector<int> sol(n);
	std::vector<int> aggr;
	for(int i = 0; i < n; ++i){
		scanf("%d", &sol[i]);
	}
	caclucateAggr(sol,aggr,k);
//	for(int i = 0; i < (int)aggr.size(); ++i) printf("%d ",aggr[i]);
//	printf("\n");

//	calculateMax(aggr, 0, n - 1);

	for(int i = 0; i < q; ++i){
		int b,e;
		scanf("%d %d", &b,&e);
		--b;
		--e;
		int m = calculateMax(aggr, b, e);
//		if (e + k * 2 >= n - 1 || e - b <= k || b <= k){
//			m = calculateMax(aggr, b, e);
////			printf("LICZYMY OD NOWA\n");
//		} else {
//			int pocz = calculateMax(aggr, b, n - 1);
//			int kon = calculateMax(aggr, e, n - 1);
////			printf("(%d %d) %d %d\n", b, e, pocz, kon);
//			m = pocz - kon;
//		}
//		cache.clear();
		printf("%d\n",m);
//		printf("=============== %d\n",m);
//		break;
	}
	return 0;
}