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

using namespace std;
using LL = long long;

int main()
{
	int n, k, q, l, r;
	
	cin >> n >> k >> q;

	vector<int> a(n);

	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}

	vector<LL> squads(n);

	for (int i = 0; i < k; ++i)
	{
		squads[k - 1] += a[i];
	}

	for (int i = k; i < n; ++i)
	{
		squads[i] = squads[i - 1] + a[i] - a[i - k];
	}

	vector<vector<LL>> res = vector<vector<LL>>(n, vector<LL>(n));

	for (int i = 0; i < n; ++i)
	{
		for (int j = i + k - 1; j < n; ++j)
		{
			res[i][j] = (j > i ? res[i][j - 1] : 0);
			LL add = (j - k >= i ? res[i][j - k] : 0);
			res[i][j] = max(res[i][j], squads[j] + add);
		}
	}

	for (int qq = 0; qq < q; ++qq)
	{
		cin >> l >> r;
		--l; --r;

		cout << res[l][r] << endl;
	}

	return 0;
}