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

const int max_n = 301600;
const int sqmax_n = 600;

int n, k, q;
int a[max_n];
long long pref[max_n];
long long dp[max_n];
long long sdp[max_n];
long long ans[max_n];
long long fdp[61][max_n];

struct Query {
  int a, b;
  int index;
};

std::vector<Query> groups[sqmax_n];

long long brut(int a, int b) {
  if (b - a + 1 < k) return 0;
  for (int i = a + k - 1; i <= b; ++i) {
    dp[i - a] = dp[i - a - 1];
    long long cst = pref[i] - pref[i - k] + dp[i - a - k];
    if (cst > dp[i - a]) dp[i - a] = cst;
  }
  return dp[b - a];
}

int main() {
  scanf("%d %d %d", &n, &k, &q);
  pref[0] = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
  }
  for (int i = 1; i <= 2 * sqmax_n; ++i) a[n + i] = 0;
  n += 2 * sqmax_n;
  for (int i = 1; i <= n; ++i) { 
    pref[i] = pref[i - 1] + a[i];
  } 
  for (int i = 0; i < k; ++i) dp[i] = 0;  
  if (k <= 60 && n >= 10000) {
    for (int i = 0; i < q; ++i) {
      int a, b;
      scanf("%d %d", &a, &b);
      if (b - a <= 2 * sqmax_n) {
        ans[i] = brut(a, b);
      } else {
        Query q;
        q.a = a, q.b = b, q.index = i;
        groups[(a + sqmax_n - 1) / sqmax_n].push_back(q);
      }
    }
    for (int i = 0; i < sqmax_n; ++i) {
      if (groups[i].size() > 0) {
        int a = i * sqmax_n;
        for (int x = 0; x < k; ++x) {
          for (int y = 0; y <= k + x + 1; ++y) {
            fdp[x][y + a - 1] = 0;
          }
        }
        for (int j = 0; j < k; ++j) {
          for (int z = a + k - 1 + j; z <= n; ++z) {
            fdp[j][z] = fdp[j][z - 1];
            long long cst = pref[z] - pref[z - k] + fdp[j][z - k];
            if (cst > fdp[j][z]) fdp[j][z] = cst;
          }
        }
        for (int j = 0; j < groups[i].size(); ++j) {
          sdp[0] = fdp[0][groups[i][j].b];
          for (int z = 1; z < k; ++z) {
            sdp[z] = sdp[z - 1];
            long long cst = pref[a - z - 1 + k] - pref[a - z - 1] + fdp[k - z][groups[i][j].b];
            if (cst > sdp[z]) sdp[z] = cst;
          }
          for (int z = a - k, id = k; z >= groups[i][j].a; --z, ++id) {
            sdp[id] = sdp[id - 1];
            long long cst = sdp[id - k] + pref[z - 1 + k] - pref[z - 1];
            if (cst > sdp[id]) sdp[id] = cst;
          }
          ans[groups[i][j].index] = sdp[a - groups[i][j].a];
        }
      }
    }
    for (int i = 0; i < q; ++i) printf("%lld\n", ans[i]);
  } else {
    for (int i = 0; i < q; ++i) {
      int a, b;
      scanf("%d %d", &a, &b);
      printf("%lld\n", brut(a, b));
    }
  }
  return 0;
}