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

long long glowna[3 * 100000 + 7];
long long sumy[3 * 100000 + 7];
long long odpowiedzi[3 * 100000 + 7];

long long super_tablica[3 * 100000 + 7];

long long n, k, q;
long long ostatnie = -1;

void licz(long long mini, long long akt)
{
    akt -= k;
    akt++;

    super_tablica[akt] = max((long long)0, sumy[akt]);
    akt--;
    while(akt >= mini)
    {
        super_tablica[akt] = max(sumy[akt] + super_tablica[akt + k], super_tablica[akt + 1]);
        akt--;
    }
}

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

    cin >> n >> k >> q;

    for(long long i = 1; i <= n; i++)
    {
        cin >> glowna[i];
    }

    sumy[n] = glowna[n];
    for(long long i = n - 1; i > 0; i--)
    {
        sumy[i] = sumy[i + 1] + glowna[i];
        if(i + k <= n)
            sumy[i] -= glowna[i + k];
    }

    vector<pair<pair<long long, long long>, long long>> pytania(q);
    for(long long i = 0; i < q; i++)
    {
        cin >> pytania[i].first.second >> pytania[i].first.first;
        pytania[i].second = i;
    }

    sort(pytania.begin(), pytania.end());

    for(auto &p : pytania)
        swap(p.first.first, p.first.second);


    //
    //licz(n);
    // for(auto p : pytania)
    // {
    //     if(ostatnie != p.first.second)
    //         licz(p.first.second);

    //     odpowiedzi[p.second] = super_tablica[p.first.first];
    // }
    for(auto p : pytania)
    {
        if(ostatnie != p.first.second)
            licz(p.first.first, p.first.second);

        odpowiedzi[p.second] = super_tablica[p.first.first];
    }

    for(long long i = 0; i < q; i++)
        cout << odpowiedzi[i] << "\n";

    
    return 0;

}