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
#include<cstdio>
#include<algorithm>

using namespace std;

typedef long long LL;

const int MAXN = 3*100000 + 1;

int n, k, q;
int a[MAXN];
LL prefix[MAXN];
LL dp[MAXN];


LL sum(int l, int r) {
    return prefix[r-1] - prefix[l-1];
}


LL solve(int l, int r) {
    for(int i = l-1; i < l+k-1; i++) dp[i] = 0; 
    prefix[l-1] = 0;
    for(int i = l; i < r; i++) prefix[i] = prefix[i-1] + a[i];
    for(int i = l+k-1; i < r; i++) {
        dp[i] = max(dp[i-1], dp[i-k] + sum(i-k+1, i+1));
    }
    return dp[r-1];
}

int main() {
    scanf("%d %d %d", &n, &k, &q);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < q; i++) {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%lld\n", solve(l, r+1));
    }

}