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
#include <cstdio>
#include <vector>
#include <map>
using namespace std;

#define FOR(i,a,b) for(int (i)=(int)(a); (i)!=(int)(b); ++(i))
typedef long long int lli;

int n, k, q, L, R;
vector<int> A;
vector<lli> LS;

inline lli get_sum(int l, int r) {
    lli result = LS[r];
    if (l>=1) result -= LS[l-1];
    return result;
}

map<int, vector<pair<int,int> > > questions;
vector<lli> tmp, result;
int main() {
    scanf("%d %d %d", &n, &k, &q);
    A.resize(n); tmp.resize(n); LS.resize(n); result.resize(n, 0);
    FOR(i,0,n) scanf("%d", &A[i]);

    LS[0] = (lli)(A[0]);
    FOR(i,1,n) LS[i] = LS[i-1] + (lli)(A[i]);

    FOR(i,0,q) {
        scanf("%d %d", &L, &R); --L; --R;
        questions[L].push_back(make_pair(R, i));
    }

    for(map<int, vector<pair<int,int> > >::iterator it = questions.begin(); it != questions.end(); ++it) {
        int L = it->first;
        int R = L;
        vector<pair<int,int> > &qlist = it->second;
        FOR(i,0,qlist.size()) R = max(R, qlist[i].first);
        FOR(j,L,R+1) {
            tmp[j] = 0;
            if (j-1 >= L) tmp[j] = tmp[j-1];
            int start_pos = j-k+1;
            if (start_pos >= L) {
                lli sum = max((lli)(0), get_sum(start_pos, j));
                if (start_pos > L) sum += tmp[start_pos - 1];
                tmp[j] = max(tmp[j], sum);
            }
        }
        FOR(i,0,qlist.size()) result[qlist[i].second] = tmp[qlist[i].first];
    }

    FOR(i,0,q) printf("%lld\n", result[i]);
}