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

using namespace std;

void solve(){
    int n, k ,q;
    cin >> n >> k >> q;

    vector<int> strength(n+1,0);
    for(int i = 1; i <= n; i++) cin >> strength[i];

    vector<long long> ksum(n+1, 0);
    for(int i = 1; i <= k; i++) ksum[k] += strength[i];
    for(int i = k + 1; i <= n; i++) ksum[i] = ksum[i-1] + strength[i] - strength[i-k];
    
    vector<long long> dp(n+1, 0);
    
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;

        if(r - l + 1 < k) {
            cout << 0 << "\n";
            continue;    
        }

        for(int j = l - 1; j < l + k - 1; j++) dp[j] = 0;
        for(int j = l + k - 1; j <= r; j++) dp[j] = dp[j-1] >= dp[j-k] + ksum[j] ? dp[j-1] : dp[j-k] + ksum[j];

        cout << dp[r] << "\n";
    } 
}

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

    solve();

    return 0;
}