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
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = b; a <= i; i--)
#define cat(x) cerr << #x << " = " << x << '\n';
using ll = long long;
using namespace std;

const int N = 300300;
const int M = 10000;

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

int n, k, q;
ll s[N], Ls[N], Rs[N], res[N], dpL[N], dpR[N], dp[M + 1][M + 1];

vector<query> vq;

void solve(int l, int r, vector<query> v) {
	if (v.empty())
		return;

	int m = (l + r) / 2;

	vector<query> L, M, R;
	for (auto q : v) {
		if (q.r < m)
			L.push_back(q);
		else if (q.l > m)
			R.push_back(q);
		else
			M.push_back(q);
	}

	solve(l, m, L);
	solve(m + 1, r, R);

	if (M.empty())
		return;

	auto fooL = [&](int x) {
		dpL[x + 1] = 0;
		for (int i = x; i >= l; i--) {
			dpL[i] = dpL[i + 1];
			if (i + k <= x + 1)
				dpL[i] = max(dpL[i], dpL[i + k] + Ls[i]);
		}
	};

	auto fooR = [&](int x) {
		dpR[x - 1] = 0;
		for (int i = x; i <= r; i++) {
			dpR[i] = dpR[i - 1];
			if (x - 1 <= i - k)
				dpR[i] = max(dpR[i], dpR[i - k] + Rs[i]);
		}
	};

	fooL(m);
	fooR(m + 1);

	for (auto q : M)
		res[q.id] = dpL[q.l] + dpR[q.r];

	for (int i = l; i <= m; i++) {
		int j = i + k - 1;
		if (m < j && j <= r) {
			fooL(i - 1);
			fooR(j + 1);
			for (auto q : M)
				if (q.l <= i && j <= q.r)
					res[q.id] = max(res[q.id], Ls[i] + dpL[q.l] + dpR[q.r]);
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin >> n >> k >> q;

	rep(i, 1, n) {
		cin >> s[i];
		s[i] += s[i - 1];
	}

	rep(i, 1, n - k + 1)
		Ls[i] = s[i + k - 1] - s[i - 1];

	rep(i, k, n)
		Rs[i] = s[i] - s[i - k];

	rep(i, 1, q) {
		int l, r;
		cin >> l >> r;
		vq.push_back({l, r, i});
	}

	if (n > M) {
		solve(1, n, vq);
	}
	else {
		rep(i, 1, n)
			rep(j, i + k - 1, n)
				dp[i][j] = max(dp[i][j - 1], dp[i][j - k] + Rs[j]);
		for (auto q : vq)
			res[q.id] = dp[q.l][q.r];
	}

	rep(i, 1, q)
		cout << res[i] << '\n';
	return 0;
}