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
#include <cstdio>
#include <cstdlib>
#include <cstring>

const int NN = 300300;

typedef long long int lli;

int V[NN];
lli S[NN];
lli R[NN];
lli A[NN];

struct Question {
  int l;
  int r;
  int index;
} questions[NN];

lli _max(lli a, lli b) { return a > b ? a : b; }

lli sum(int r, int k) { return S[r] - S[r - k]; }

lli compute(int l, int r, int k) {
  if (k > r - l)
    return 0;

  memset(R + l, 0, (r - l + 1) * sizeof(lli));
  int c = l + k - 1;
  R[c] = _max(0, sum(c, k));
  for (++c; c < r; ++c) {
    R[c] = _max(R[c - 1], R[c - k] + sum(c, k));
  }
  return R[r - 1];
}

int main() {

  int N, K, Q;
  scanf("%d%d%d", &N, &K, &Q);

  lli sum = 0;
  for (int i = 0; i < N; ++i) {
    scanf("%d", &V[i]);
    sum += V[i];
    S[i] = sum;
  }

  // char x[486];
  // char *y = x;

  for (int i = 0; i < Q; ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    questions[i] = {l, r, i};
    // printf("%lld\n", compute(l - 1, r, K));
    // y+=sprintf(y,"%lld\n", compute(l - 1, r, K));
  }

  qsort(questions, Q, sizeof(Question), [](const void *va, const void *vb) {
    const Question *a = (const Question *)va;
    const Question *b = (const Question *)vb;
    if (a->l == b->l) {
      return b->r - a->r;
    } else {
      return a->l - b->l;
    }
  });

  int last_l = -1;
  for (int i = 0; i < Q; ++i) {
    Question *q = questions + i;
    if (K > q->r - q->l + 1) {
      A[q->index] = 0;
    } else if (last_l == q->l) {
      A[q->index] = R[q->r - 1];
    } else {
      A[q->index] = compute(q->l - 1, q->r, K);
      last_l = q->l;
    }
  }

  for (int i = 0; i < Q; ++i) {
    printf("%lld\n", A[i]);
  }

  // printf("%s", x);
  return 0;
}