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

struct task {
	int start;
	int end;
	int id;
};

struct task_sort {
	bool operator()(const task& l, const task& r) {
		return l.start != r.start ? l.start < r.start : l.end < r.end;
	}
};

int main() {
	int n, k, q;
	std::cin >> n >> k >> q;
	std::vector<int> soldiers;
	std::vector<long long> solutions;
	std::vector<long long> results;
	soldiers.resize(n);
	solutions.resize(n+1);
	results.resize(q);
	for (int& soldier : soldiers) {
		std::cin >> soldier;
	}

	std::vector<task> ts;
	for (int i = 0; i < q; ++i) {
		int from, to;
		std::cin >> from >> to;
		task t;
		t.start = from;
		t.end = to;
		t.id = i;
		ts.push_back(t);
	}

	std::sort(ts.begin(), ts.end(), task_sort());

	int curr = 0;
	while (curr < q) {
		int last = curr;
		while (last < q && ts[last].start == ts[curr].start) {
			++last;
		}
		int from = ts[last-1].start;
		int to = ts[last-1].end;

		long long best = 0;
		long long power = 0;
		solutions[from - 1] = 0;
		for (int pos = from; pos <= to; ++pos) {
			solutions[pos] = best;

			power += soldiers[pos - 1];
			if (pos - k >= from - 1) {
				long long check = power + solutions[pos - k];
				if (check > best) {
					solutions[pos] = best = check;
				}
				power -= soldiers[pos - k];
			}
			if (pos == ts[curr].end) {
				results[ts[curr].id] = best;
				++curr;
			}
		}
		//std::cout << best << std::endl;
	}

	for (long long result : results) {
		std::cout << result << std::endl;
	}
	
	return 0;
}