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
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;

typedef vector<pair<pair<int, int>, LL*>> Q;

int k, n;
void solve(int A, int B, vector<LL>& pref, Q& qrs) {
  if (qrs.empty()) return;

  // fprintf(stderr, "\nRecurrsion for %d and %d\n", A, B);

  int C = (A+B)/2;
  int D = min(n, B+k);
    
  vector<vector<LL>> ts;
  for (int i=0; i<min(k, n-C); ++i) {
    int p = C+i;
    ts.push_back(vector<LL>(D - A + 1, 0ll));
    auto& t = ts.back();
    for (int j=p+1; j<=D; ++j) {
      //fprintf(stderr, "j = %d, p = %d, k = %d, j-p >= k = %d\n", j, p, k, j-p >= k);
      if (j-p >= k) {
        t[j-A] = max(t[j-A-k] + pref[j] - pref[j-k],
                     t[j-A-1]);
      } else {
        t[j-A] = t[j-A-1];
      }
    }
    for (int j=p-1; j>=A; --j) {
      //fprintf(stderr, "j = %d, p = %d, k = %d, j-p >= k = %d\n", j, p, k, p-k >= j);
      if (p-k >= j) {
        t[j-A] = max(t[j-A+k] + pref[j+k] - pref[j],
                     t[j-A+1]);
      } else {
        t[j-A] = t[j-A+1];
      }
    }
    
    //fprintf(stderr, "Between %d and %d (%d) with slit at %d, dp result for %d is:\n", A, B, D, C, p);
    //for (LL v : t) //fprintf(stderr, "%lld ", v);
    //fprintf(stderr, "\n");
  }

  Q lqrs, rqrs;
  for (auto& q : qrs) {
    auto& [qq, s] = q;
    auto [l, r] = qq;
    if (r - l < k) continue;
    if (r < C + k) { lqrs.push_back(q); continue; }
    if (l > C) { rqrs.push_back(q); continue; }

    for (auto& t : ts) {
      *s = max(*s, t[l-A] + t[r-A]);
    }
    // fprintf(stderr, "Answering %d %d: %lld\n", l, r, *s);
  }
  ts.clear();
  
  solve(A, C, pref, lqrs);
  solve(C, B, pref, rqrs);
}

int main() {
  int q; scanf("%d %d %d", &n, &k, &q);
  vector<int> a(n);
  for (int i=0; i<n; ++i) scanf("%d", &a[i]);

  vector<LL> ans(q, 0ll);  
  Q qrs(q);
  for (int i=0; i<q; ++i) {
    scanf("%d %d", &qrs[i].first.first, &qrs[i].first.second);
    --qrs[i].first.first;
    qrs[i].second = &ans[i];
  }

  vector<LL> pref(n+1, 0ll);
  for (int i=0; i<n; ++i) pref[i+1] = pref[i] + a[i];

  solve(0, n, pref, qrs);

  for (int i=0; i<q; ++i) fprintf(stdout, "%lld\n", ans[i]);
  return 0;
}