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
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <string>
#include <list>
#include <algorithm>

#define MAXN 100010
#define MAXQ 100010

using namespace std;

struct query {
	int l, r, pos;
};


int n, k, q;
int input[MAXN];

vector<query> queries[MAXQ];

long long q_answer[MAXQ];
long long query_answers[MAXQ];

long long range_value[MAXN];


void visit(int start_index) {
	vector<query> current_queries = queries[start_index];
	
	long long t[n];
	int start[n], end[n];
	for (int i = 0; i < n; ++i) {t[i] = start[i] = end[i] = 0;}
	
	for (int i = start_index; i < n-k+1; ++i) {
		//printf("========== ITERATION %d ========\n", i);
		if (i == start_index) {
			if (range_value[i] > 0) {
				t[i] = range_value[i];
				start[i] = i;
				end[i] = i + k - 1;
			}
		}
		// nasza wartość jest niedodatnia, weź poprzedni wynik lub zostaw 0
		else if (range_value[i] <= 0) {
			t[i] = t[i-1];
			start[i] = start[i-1];
			end[i] = end[i-1];
		}
		// nasza wartość jest dodatnia
		else {
			// sprawdźmy czy zaczęcie tutaj nie jest lepsze
			if (range_value[i] > t[i]) {
				t[i] = range_value[i];
				start[i] = i;
				end[i] = i+k-1;
			}
			// sprawdźmy czy po prostu wzięcie poprzedniego nie jest lepsze
			if (t[i-1] > t[i]) {
				t[i] = t[i-1];
				start[i] = start[i-1];
				end[i] = end[i-1];
			}
			for (int j = 1; j <= k; ++j) {
				int index = i - j;
				if (index < 0) continue;
				//printf("Porównujemy z indeksem %d\n", index);
// porównujemy się z wcześniejszym polem odległym o INDEX
				if (index >= start_index) {
					//printf("Indeks mieści się w tablicy\n");
					// wcześniejsze pole ma większą wartość ale "zachodzi" na nasze pole.
					if (end[index] >= i && t[index] > t[i]) {
						//printf("Wcześniejsze pole %d ma większą wartość %lld, ale zachodzi (end=%d).\n", index, t[index], end[index]);
						t[i] = t[index];
						start[i] = start[index];
						end[i] = end[index];
					}
					// wcześniejsze pole ma większą wartość i nie "zachodzi" na nasze pole, więc warto dodać nasze.
					else if (end[index] < i && t[index] + range_value[i] > t[i]) {
						//printf("Wcześniejsze pole %d + nowy przedział ma większą wartość %lld + %lld, i nie zachodzi (end=%d).\n", index, t[index], range_value[i], end[index]);
						t[i] = t[index] + range_value[i];
						start[i] = start[index];
						end[i] = i + k - 1;
					}
				}

			}
		}
	}

		
	//for (int i = 0; i < n; ++i) {
	//	cout << t[i] << " ";
	//}
	//cout << endl;
	
	for (int i = 0; i < current_queries.size(); ++i) {
		int left = current_queries[i].l;
		int right = current_queries[i].r;
		int pos = current_queries[i].pos;
		if (right - left < k - 1) query_answers[pos] = 0;
		else if (right - left == k - 1) query_answers[pos] = max(0LL, range_value[left]);
		else query_answers[pos] = t[right-k+1];
	}

};


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	// Read input
	cin >> n >> k >> q;
	for (int i = 0; i < n; ++i) { cin >> input[i]; }
	
	// Read queries
	for (int i = 0; i < q; ++i) {
		int left, right;
		cin >> left >> right;
		left--;
		right--;
		queries[left].push_back(query());
		queries[left].back().l = left; queries[left].back().r = right; queries[left].back().pos = i;
	}	
	
	// Prepare range_value
	long long sum = 0;
	for (int i = 0; i < k; ++i) sum += input[i];
	range_value[0] = sum;
	for (int i = 1; i < n-k+1; ++i) {
		sum = sum - input[i-1] + input[i+k-1];
		range_value[i] = sum;
	}
	//for (int i = 0; i < n; ++i) cout << range_value[i] << " ";
	//cout << endl;

	

	// Do dynamic
	for (int i = 0; i < n; ++i) {
		if (queries[i].size() > 0) {
			visit(i);
		}
	}
	
	for (int i = 0; i < q; ++i) {
		cout << query_answers[i] << endl;
	}
	
}