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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Query {
    int l, r, i;
    long long ans;
    [[nodiscard]] int len() const {
        return r - l + 1;
    }
};

void dyn(vector<long long> &ans, const vector<long long> &k_skills, const Query &q, int k) {
    int k1 = k - 1, ql = q.l - 1;
    ans[k1] = max(k_skills[ql + k1], 0ll);
    for (int i = 1; i < q.len() - k1; ++i) {
        ans[k1 + i] = max(ans[k1 + i - 1], ans[i - 1] + k_skills[ql + i + k1]);
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, q;
    cin >> n >> k >> q;
    vector<long long> skills, k_skills;
    skills.resize(n);
    k_skills.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> skills[i];
    }
    long long sum = 0;
    for (int i = 0; i < k; ++i) {
        k_skills[i] = 0;
        sum += skills[i];
    }
    k_skills[k - 1] = sum;
    for (int i = k; i < n; ++i) {
        k_skills[i] = k_skills[i - 1] - skills[i - k] + skills[i];
    }
    vector<Query> queries;
    queries.resize(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].i = i;
        queries[i].ans = -1;
    }
    sort(begin(queries), end(queries), [](const Query &q1, const Query &q2) {
        return q1.l < q2.l || q1.l == q2.l && q1.r > q2.r;
    });
    vector<long long> ans;
    ans.resize(n, 0);
    for (int i = 0; i < q;) {
        Query &cq = queries[i];
        if (cq.len() < k) {
            cq.ans = 0;
            ++i;
            continue;
        }
        dyn(ans, k_skills, cq, k);
        while (queries[i].l == cq.l) {
            queries[i].ans = ans[queries[i].len() - 1];
            ++i;
        }
    }
    sort(begin(queries), end(queries), [](const Query &q1, const Query &q2) {
        return q1.i < q2.i;
    });
    for (int i = 0; i < q; ++i) {
        cout << queries[i].ans << '\n';
    }
}