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
#include <bits/stdc++.h>

long long Max_Subs(long long *pref, int size, int k, int num) {
	auto **dp = new long long *[num];
	for (int i = 0; i < num; ++i)
		dp[i] = new long long [size + 1];

	for (int i = 0; i < num; ++i)
		for (int j = 0; j <= size; ++j)
			dp[i][j] = 0;

	for (int i = 0; i < num; ++i) {
		for (int j = k; j <= size; ++j) {
			dp[i][j] = *(pref + j) - *(pref + j - k);
			if (i != 0) dp[i][j] += dp[i - 1][j - k];
			dp[i][j] = std::max(dp[i][j], dp[i][j - 1]);
		}
	}
	
	long long output = 0;
	for (int i = 0; i < num; ++i)
		output = std::max(output, dp[i][size]);
	for (int i = 0; i < num; ++i)
		delete [] dp[i];
	delete [] dp;

	return output;
}

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

	int n, k, q;
	std::cin >> n >> k >> q;

	auto *tab = new long long [n + 1];
	tab[0] = 0;
	for (int i = 0; i < n; ++i)
		std::cin >> tab[i + 1];

	auto *pref = new long long [n + 1];
	pref[0] = 0;
	for (int i = 1; i <= n; ++i)
		pref[i] = pref[i - 1] + tab[i];

	while (q > 0) {
		int l, r;
		std::cin >> l >> r;
		if ((r - l + 1) / k == 0) std::cout << 0 << '\n';
		else std::cout << Max_Subs(pref + l - 1, r - l + 1, k, (r - l + 1) / k) << '\n';
		--q;
	}

	return 0;
}