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
// Autor: Mikołaj Janusz
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

ll highest = 0; 

ll calculate_highest(ll a, ll b, ll k, vector<ll>& sol) {
    ll left_val = 0, val = 0, right_val = 0;
    ll highest_val = 0;
    
    ll l = a, r = a + k-1;
    while (r <= b) {
        left_val = 0;
        right_val = 0;
        val = 0;

        if (l >= a + k) {
            left_val = calculate_highest(a, l-1, k, sol);
        }

        if (r <= b - k) {
            right_val = calculate_highest(r+1, b, k, sol);
        }

        for (ll i = l; i <= r; i++) {
            val += sol[i];
        }

        highest_val = max(highest_val, val + max(0LL, left_val) + max(0LL, right_val));
        l++;
        r++;
    }

    return highest_val;
}

int main() {
    ios::sync_with_stdio(false);
    ll n, k, q;
    cin >> n >> k >> q;
    
    vector<ll> soldiers(n);

    for (ll i = 0; i < n; i++) {
        cin >> soldiers[i];
    }

    for (ll i = 0; i < q; i++) {
        ll l, r;
        cin >> l >> r;
        cout << calculate_highest(l-1, r-1, k, soldiers) << endl;
    }

    return 0;
}