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
//Mateusz Piórkowski
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

struct solution_args{
	int l;
	int r;
};
bool operator<(const solution_args& a, const solution_args& b) {
	return (a.l<b.l || (a.l==b.l && a.r<b.r));
}
std::map<solution_args, int> solutions;

int solve(std::vector<int>& soldiers, int k, int l, int r, int* sums){
	if(l>=r) return 0;
	if(solutions.count({l,r})==1){
		return solutions[{l,r}];
	}
	//std::cout << "solve " << k<<" "<<l<<" "<<r<<"\n";
	int sol=sums[l];
	for(int i=l+1 + k-1; i<r; i++){
		if(sums[i]>0){
			//sol=std::max(sol, sums[l]+solve(soldiers, k, i+1, r, sums));
			sol=std::max(sol, sums[l]+solve(soldiers, k, i, r, sums));
		}
	}
	solutions[{l,r}] = sol;
	return sol;
}

void fill_sums(std::vector<int>& soldiers, int* sums, int sums_len, int k){
	for(int i=0; i<sums_len; i++){
		int sum = 0;
		for(int j=0; j<k; j++){
			sum+=soldiers[i+j];
		}
		sums[i] = sum;
	}
	
	/*std::cout << "sums:\n";
	for(int i=0; i<sums_len; i++){
		std::cout << sums[i] << " ";
	}
	std::cout << "\n";*/
}

int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);

	int n,k,q;
	std::cin >> n >> k >> q;
	std::vector<int> soldiers;
	for(int i=0;i<n;i++){
		int exp;
		std::cin >> exp;
		soldiers.push_back(exp);
	}

	int sums_len = n-(k-1);
	int *sums = new int[sums_len];
	fill_sums(soldiers, sums, sums_len, k);

	for(int i=0;i<q;i++){
		int q_l, q_r;
		std::cin >> q_l >> q_r;
		int q_l2 = q_l-1;
		int q_r2 = q_r-(k-1);

		int out=0;
		for(int i=q_l2; i<q_r2; i++){
			if(sums[i]>0){
				//std::cout << "a\n";
				out=std::max(solve(soldiers, k, i, q_r2, sums), out);
			}
		}
		std::cout << out << "\n";
	}
}