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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> agility, sums = {0};
    int x;
    for(int i = 0; i < n; ++i) {
        cin >> x;
        agility.push_back(x);
        sums.push_back(x + sums.back());
    }
    int left, right;
    for(int qi = 0; qi < q; ++qi) {
        cin >> left >> right;
        --left;
        --right;
        long long best_result = 0, current;
        vector<long long> partial_sum;
        for(int i = left + k - 1; i <= right; ++i) {
            current = max(0, sums[i + 1] - sums[i - k + 1]);
            if(i >= left + 2 * k - 1) {
                current += partial_sum[i - (left + k - 1) - k];
            }
            best_result = max(current, best_result);
            partial_sum.push_back(best_result);
        }
        cout << best_result << endl;
    }
}