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

struct query {
    int l,r;
    int pos;
    long long res = 0;
};

bool cmp_query(query &a,query &b) {

    if(a.l == b.l)
        return a.r < b.r;
    return a.l < b.l;

}

bool cmp_pos(query &a,query &b) {
    return a.pos < b.pos;
}
int main() {

    ios_base::sync_with_stdio(0);
    int n,q,range;
    cin >> n >> range >> q;
    vector<long long> vec(n);
    for(int k=0;k<n;k++)
        cin >> vec[k];
    vector<query> tab;
    for(int k=0;k<q;k++){
        int l,r;
        cin >> l >> r;
        query t = {l,r,k,0};
        tab.push_back(t);
    }
    sort(tab.begin(),tab.end(),cmp_query);
    vector<long long> DP(n+3,0);
    int current_size = 0;
    int last_l = -1;
    int last_r = 0;
    long long sum =0;
    for(int i=0;i<q;i++) {
        int l = tab[i].l;
        int r = tab[i].r;
        if(last_l == l && last_r == r) {
            tab[i].res = tab[i-1].res;
            continue;
        }
        if(r-l+1 < range)
            tab[i].res = 0;
        else {
            if(last_l !=l) {
                current_size = range;
                sum = 0;
                for(int k=l;k<l+range;k++) {
                    DP[k-l] = 0;
                    sum+=vec[k-1];
                }
                DP[current_size] = (max(sum,(long long)0));
                current_size++;
                for(int k=l+range;k<=r;k++) {
                    sum +=vec[k-1];
                    sum -= vec[k-range-1];
                    DP[current_size] = (max(DP[k-range-l+1] + sum,DP[current_size-1]));
                    current_size++;

                }
                tab[i].res =DP[current_size-1];
                last_l = l;
                last_r = r;
            }
            else {
                for(int k=last_r+1;k<=r;k++) {
                    sum +=vec[k-1];
                    sum -= vec[k-range-1];
                    DP[current_size] = max(DP[k-range-l+1] + sum,DP[current_size-1]);
                    current_size++;

                }
                tab[i].res = DP[current_size-1];
                last_l = l;
                last_r = r;
            }

        }
     }
     sort(tab.begin(),tab.end(),cmp_pos);
     for(auto t:tab)
        cout <<t.res <<endl;
}