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
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<list>
#include<set>
using namespace std;

class query {
public:
	int l, r, q;
	query(int l, int r, int q) {
		this->l = l;
		this->r = r;
		this->q = q;
	}
	bool operator < (const query& q2) const{
		return l < q2.l || (l == q2.l && r > q2.r);
	}
};

long long tab[300001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

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

	vector<long long> v;
	for (int i = 0; i < n; i++) {
		long long e;
		cin >> e;
		v.push_back(e);
	}

	vector<query> queries;
	for (int i = 1; i <= q; i++) {
		int l, r;
		cin >> l >> r;
		l -= 1;
		r -= 1;
		queries.push_back(query(l, r, i));
	}
	sort(queries.begin(), queries.end());
	int t = -1;
	vector<query>::iterator it;

	vector<long long> results(q);
	for (it = queries.begin(); it != queries.end(); ++it) {
		int l = it->l;
		int r = it->r;
		int q = it->q;
		if (r - l + 1 < k) {
			results[q - 1] = 0;
		}
		else {
			if (t != l) {
				long long acc = 0;
				for (int i = l; i < l + k && i < n; i++) {
					acc += v[i];
					tab[i] = 0;
				}
				tab[l + k - 1] = max(acc, 0ll);
				for (int i = l + k; i <= r; i++) {
					acc -= v[i - k];
					acc += v[i];
					long long prev = tab[i - 1];
					long long curr = tab[i - k] + acc;
					tab[i] = max(prev, curr);
				}

				t = l;
			}
			results[q - 1] = tab[r];
		}
	}

	for (int i = 0; i < q; i++) {
		cout << results[i] << endl;
	}

	return 0;
}