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
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define squad_val(l) ((l) == 0 ? pref[k-1] : pref[(l)+k-1] - pref[(l)-1])

int main() {

    int n, k, q;
    cin >> n >> k >> q;

    vector<int> a (n);

    for (int i=0; i<n; ++i)
        cin >> a[i];

    vector<ll> pref (n);

    pref[0] = a[0];
    for (int i=1; i<n; ++i)
        pref[i] = pref[i-1] + a[i];

    vector<vector<vector<ll>>> t;

    int min_d = 1;
    int min_exp = 0;
    while (min_d < k * k) {
        ++min_exp;
        min_d <<= 1;
    }

    int d = min_d;
    int exp_d = 0; // d == 2^(exp_d + min_exp)

    if (n >= min_d) {

        t.emplace_back(n, vector<ll>(k, 0));

        for (int i = 0; i < n - (d-1) + k - 1; ++i) {
            vector<ll> dp(d, 0);
            dp[k - 1] = max(squad_val(i), 0LL);
            for (int j = k; j < d; ++j)
                if (i + j <= n - 1)
                    dp[j] = max(dp[j - 1], dp[j - k] + squad_val(i + j - k + 1));
            for (int l1 = max (0, i - (n-d)); l1 < k; ++l1)
                t[exp_d][i][l1] = dp[d - 1 - l1];
        }

        d <<= 1;
        ++exp_d;

        while (d <= n) {
            t.emplace_back(n, vector<ll>(k, 0));
            for (int i = 0; i < n - (d-1) + k - 1; ++i)
                for (int l1 = max (0, i - (n-d)); l1 < k; ++l1)
                    for (int l2 = 0; l2 < k; ++l2)
                        if (l2 <= l1)
                            t[exp_d][i][l1] = max(t[exp_d][i][l1],
                                                  t[exp_d - 1][i][l2] + t[exp_d - 1][i + d / 2 - l2][l1 - l2]);
                        else
                            t[exp_d][i][l1] = max(t[exp_d][i][l1],
                                                  t[exp_d - 1][i][l2] + squad_val(i + d / 2 - l2) + t[exp_d - 1][i + d / 2 + k - l2][k + l1 - l2]);
            d <<= 1;
            ++exp_d;
        }
    }

    for (int qq=0; qq<q; ++qq) {
        int l, r;
        cin >> l >> r;

        --l;
        --r;

        int real_l = l;

        int rest = r - l + 1;
        exp_d = 0;
        d = min_d;
        while (2*d <= rest) {
            d *= 2;
            ++exp_d;
        }

        vector<ll> dp(k, 0);
        vector<ll> dp2(k, 0);

        bool first_segment = true;

        while (rest >= min_d) {
            for (int l1=0; l1<k; ++l1)
                for (int l2=0; l2<=(first_segment ? 0 : k-1); ++l2)
                    if (l2 <= l1)
                        dp2[l1] = max(dp2[l1], dp[l2] + t[exp_d][l-l2][l1-l2]);
                    else
                        dp2[l1] = max(dp2[l1], dp[l2] + squad_val(l-l2) + t[exp_d][l-l2+k][k+l1-l2]);

            l += d;
            rest -= d;
            first_segment = false;
            dp = dp2;

            while (d > rest) {
                d /= 2;
                --exp_d;
            }
        }

        //reszta liniowym DP
        reverse(dp.begin(),dp.end());
        dp.resize(k+rest);
        for (int j=0; j<rest; ++j)
            dp[k+j] = max(dp[k+j-1], dp[j] + (l+j-k+1 >= real_l ? squad_val(l+j-k+1) : 0));

        cout << dp[k+rest-1] << endl;
    }

    return 0;
}