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

const int limit = 300010;
ll sumy[limit];
ll wynik[limit];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, k, q, start, kon;
    ll a, suma = 0;
    queue <ll> rm;
    cin >> N >> k >> q;

    for (int i = 1; i <= N; i++) {
        cin >> a;
        suma += a;
        rm.push(a);
        wynik[i] = -1;
        if (rm.size() > k) {
            suma -= rm.front();
            rm.pop();
        }
        if (i >= k)
            sumy[i] = suma;
    }

    vector <pair <pair <int, int>, int> > v;
    vector <pair <int, ll> > odp;
    for (int i = 0; i < q; i++) {
        cin >> start >> kon;
        v.push_back({{start, kon}, i});
    }
    sort(v.begin(), v.end());

    start = 0;
    kon = 0;
    ll score = 0;
    for (int i = 0; i < q; i++) {
        auto e = v[i].first;
        
        if (e.first == start) {
            for (int z = kon + 1; z <= e.second; z++) {
                wynik[z] = 0;
                if (z > start) {
                    wynik[z] = wynik[z - 1];
                    if (z >= start + k - 1) {
                        wynik[z] = max(wynik[z], wynik[z - k] + sumy[z]);
                    }
                }
            }
        }
        else {
            int licz = 0;
            wynik[e.first - 1] = 0;
            for (int z = e.first; z <= e.second; z++) {
                score = 0;
                if (z > e.first) {
                    score = wynik[z - 1];
                    if (z >= e.first + k - 1) {
                        score = max(score, wynik[z - k] + sumy[z]);
                    }
                }
                wynik[z] = score;
            }
            start = e.first;
        }
        kon = e.second;

        odp.push_back({v[i].second, wynik[kon]});
    }
    sort(odp.begin(), odp.end());

    for (int i = 0; i < q; i++) {
        cout << odp[i].second << "\n";
    }
}