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
#include <iostream>
#include <cmath>
#include <climits>

using namespace std;

int greatestKsumInRange(int *k_sums, int n, int k, int l, int r)
{
	if (k > r-l+1) return 0;
	
	int *maxsum = new int[r-l+1-k+1];
	
	for (int i=0;i<k && i<=r-l+1-k;++i)
	{
		maxsum[i] = max(0,k_sums[l+i]);
	}
	
	for (int i=k;i<=r-l-k+1;++i)
	{
		maxsum[i] = 0;
		for (int j=max(i-2*k+1,0);j<=i-k;++j)
		{
			if (maxsum[j] > maxsum[i]) maxsum[i] = maxsum[j];
		}
		maxsum[i] += max(0,k_sums[l+i]);
	}
	
	int res = 0;
	for (int j=max(r-l-2*k+2,0);j<=r-l-k+1;++j)
	{
		if (maxsum[j] > res) res = maxsum[j];
	}
	delete[] maxsum;
	return res;
}

int main()
{
	int n,k,q;
	cin >> n >> k >> q;
	
	int *soldiers = new int[n];
	int *prefix_sums = new int[n+1];
	int *k_sums = new int[n-k+1];
	prefix_sums[0] = 0;
	for (int i=0;i<n;++i)
	{
		cin >> soldiers[i];
		prefix_sums[i+1] = prefix_sums[i]+soldiers[i];
	}
	
	for (int i=0;i<n-k+1;++i)
	{
		k_sums[i] = prefix_sums[i+k] - prefix_sums[i];
	}
	
	int l, r;
	for (int i=0;i<q;++i)
	{
		cin >> l >> r;
		--l; 
		--r; // l i r sa podane w zakresie od 1 od n, zmieniamy ten zakres na "komputerowy" od 0 do n-1
		cout << greatestKsumInRange(k_sums, n,k,l,r) << endl;
	}
	delete[] soldiers;
	delete[] prefix_sums;
	delete[] k_sums;
}