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

#define int long long

int n,k,q;
vector<int> v;
vector<int> pref_sum;

int solve(int l, int r)
{
    vector<int> dp;
    dp.resize(r-l+1);

    auto dp_get = [&dp, &l](int ix){
        ix -= l;
        if(ix < 0) return 0ll;
        return dp[ix];
    };

    auto dp_set = [&dp, &l](int ix, int val){
        // cerr << "ix: " << ix << " val: " << val << endl;
        dp[ix-l] = val;
    };

    for(int i = l; i <= r; i++)
    {
        int new_val = dp_get(i-1);
        // we take [i-k+i, ..., i
        if(i - k + 1 >= l)
        {
            int take_k = dp_get(i-k) + pref_sum[i] - pref_sum[i-k];
            // cerr << "take_k " << take_k << endl;
            new_val = max(new_val, take_k);
        }
        dp_set(i, new_val);
    }
    return dp[r-l];
}


main()
{
ios_base::sync_with_stdio(false);
cin >> n >> k >> q;
v.resize(n+1);
for(int i=1; i<=n; i++)
    cin >> v[i];

pref_sum.resize(n+1);
for(int i=1; i<=n; i++)
    pref_sum[i] = pref_sum[i-1] + v[i];

while(q--)
{
    int a,b; cin >> a >> b;
    cout << solve(a, b) << endl;
}

return 0;
}