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


using namespace std;

int sub1(long long* pre, int m, int s, int k, int si)
{
    if (!m)
        return 0;
    if (si > s - 1)
        return 0;
    int ik = pre[si] + sub1(pre, m - 1, s, k, si + k);
    int em = sub1(pre, m, s, k, si + 1);
    return max(ik, em);
}

int main()
{
    int n, k ,q;
    std::cin >> n >> k >> q;
    int zol[n];
    for(int i=0;i<n;i++)
			std::cin >> zol[i];
		for(int i=0;i<q;i++) {
			int l, r;


			std::cin >> l >> r;
			int* begin = zol + l - 1;
			int len = r-l+1;
			int arrlen = len+1-k;
			if(len < k) {
				std::cout << 0 << '\n';
				continue;
			}
			if(arrlen == 0) {
				long long sum = 0;
        for(int i=0;i<k;i++)
					sum += begin[i];
        std::cout << sum << '\n';
				continue;
			}

			long long pre[len+1-k] = {0};
			for(int i=0; i<k; i++)
				pre[0] += begin[i];
			for(int i = 1; i <= len - k; i++)
				pre[i] += pre[i-1] + begin[i+k-1] - begin[i-1];

			int ml = len/k;
			long long maxv = LLONG_MIN;
			for(int i=1;i<=ml;i++) {
        long long nw = sub1(pre, i, len + 1 - k, k, 0);
        if(nw > maxv)
					maxv = nw;
			}
			std::cout << maxv << '\n';
		}

}