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
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = 3e5 + 7;
int a[N];
ll dp[N];
int k;

ll query(int l, int r) {
    ll sum = 0;
    for (int i = l; i < r; ++i) {
        if (i - k >= l)
            sum -= a[i - k];
        sum += a[i];
        dp[i - l + 1] = dp[i - l];
        if (i - l + 1 - k >= 0)
            dp[i - l + 1] = max(dp[i - l + 1], dp[i - l + 1 - k] + sum);
    }
    return dp[r - l];
}

int main() {
    int n, q;
    scanf("%d%d%d", &n, &k, &q);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);

    while (q--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%lld\n", query(l - 1, r));
    }

    return 0;
}