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
#define make_pair mp
#define emplace_back pb
#include <bits/stdc++.h>
using namespace std;
mt19937 mt_rand(time(0));
const int N = 3e5 + 5;
int n, k, q;
long long tab[N], res[N], sum[N], dp1[N], dp2[N];

struct query {
    int l, r, id;
};

vector<query> queries;

void count(int l, int r, vector<query> &quer) {
    if(quer.empty() || l > r) return;
    int mid = (l + r) / 2;

    vector<query> right(0), left(0), middle(0);
    for(auto qq : quer) {
        if(qq.l > mid) right.pb(qq);
        else if(qq.r < mid) left.pb(qq);
        else middle.pb(qq);
    }
    count(l, mid - 1, left);
    count(mid + 1, r, right);

    if(middle.empty()) return;

    int pocz = max(l, mid - k + 2);
    int kon = min(r, pocz + k - 2);

    for(int i=pocz;i<=kon;i++) {
        long long val = sum[i];
        int le = i - k;
        int ge = i + k;

        if(le >= l) dp1[le] = max(sum[le], (long long)0);
        for(int j=le-1;j>=l;j--) {
            dp1[j] = dp1[j+1];
            if(j + k <= le) dp1[j] = max(dp1[j], sum[j] + dp1[j+k]);
            else dp1[j] = max(dp1[j], sum[j]);
        }

        if(ge <= r) dp2[ge] = max(sum[ge], (long long)0);
        for(int j=ge+1;j<=r;j++) {
            dp2[j] = dp2[j-1];
            if(j - k >= ge) dp2[j] = max(dp2[j], sum[j] + dp2[j-k]);
            else dp2[j] = max(dp2[j], sum[j]);
        }

        for(auto qq : middle) {
            long long ll = dp1[qq.l];
            if(qq.l > le) ll = 0;
            long long rr = dp2[qq.r];
            if(qq.r < ge) rr = 0;
            if(qq.l > i || qq.r < i) ll -= val;
            res[qq.id] = max(res[qq.id], val + ll + rr);
        }
    }

    int le = pocz - 1;
    int ge = kon + 1;

    if(le >= l) dp1[le] = max(sum[le], (long long)0);
    for(int j=le-1;j>=l;j--) {
        dp1[j] = dp1[j+1];
        if(j + k <= le) dp1[j] = max(dp1[j], sum[j] + dp1[j+k]);
        else dp1[j] = max(dp1[j], sum[j]);
    }

    if(ge <= r) dp2[ge] = max(sum[ge], (long long)0);
    for(int j=ge+1;j<=r;j++) {
        dp2[j] = dp2[j-1];
        if(j - k >= ge) dp2[j] = max(dp2[j], sum[j] + dp2[j-k]);
        else dp2[j] = max(dp2[j], sum[j]);
    }

    for(auto qq : middle) {
        long long ll = dp1[qq.l];
        if(qq.l > le) ll = 0;
        long long rr = dp2[qq.r];
        if(qq.r < ge) rr = 0;
        res[qq.id] = max(res[qq.id], ll + rr);
    }
}

int main() {
	scanf("%d%d%d", &n, &k, &q);
    for(int i=1;i<=n;i++) scanf("%lld", &tab[i]);
    for(int i=1;i<=n;i++) tab[i] += tab[i-1];
    for(int i=k;i<=n;i++) sum[i-k+1] = tab[i] - tab[i-k];
    n -= (k - 1);
    for(int i=1;i<=q;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        b -= (k - 1);
        if(a <= b) {
            query qq = {a, b, i};
            queries.pb(qq);
        }
    }
    count(1, n, queries);
    for(int i=1;i<=q;i++) printf("%lld\n", res[i]);
	return 0;
}