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 <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define pi pair<int, int>
#define mod 998244353
template<typename T> bool chkmin(T &a, T b){return (b < a) ? a = b, 1 : 0;}
template<typename T> bool chkmax(T &a, T b){return (b > a) ? a = b, 1 : 0;}
ll ksm(ll a, ll b) {if (b == 0) return 1; ll ns = ksm(a, b >> 1); ns = ns * ns % mod; if (b & 1) ns = ns * a % mod; return ns;}
using namespace std;
const int maxn = 300005;
int a[maxn];
ll s[maxn];
ll dp[maxn * 2];
int l[maxn], r[maxn];
vi qq[maxn];
ll ans[maxn];
mt19937 rd;
int grd(int l, int r) {
    return rd() % (r - l + 1) + l;
}
int main() {    
    int fr = clock();
    int n, k, q;
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1; i <= q; i++)
        scanf("%d%d", &l[i], &r[i]), ans[i] = 0, qq[l[i]].pb(i);
    for (int i = 1; i <= n; i++) 
        s[i] = s[i - 1] + a[i];
    for (int i = n; i >= 1; i--) {
        if (i >= k) s[i] -= s[i - k];
        else s[i] = -1e18;
        chkmax(s[i], 0ll);
    }
    vi cr;
    int step = 150;
    chkmax(step, 12000 / k);
    for (int i = 0; i <= step; i++)
        for (int j = 0; j <= step - i; j++) {
            int m = i * k + j;
            if (m <= n && m >= k) cr.pb(m);
        }
    sort(cr.begin(), cr.end());
    cr.erase(unique(cr.begin(), cr.end()), cr.end());
    for (int i = 0; i < maxn; i++)
        dp[i] = 0;
    for (int i = n; i >= 1; i--) {
        for (auto v : cr) { // len, i ~ i + v - 1
            if (i + v - 1 > n) break;
            dp[v] = dp[v - 1];
            chkmax(dp[v], dp[v - k] + s[i + v - 1]);
        }
        for (auto id : qq[i]) {
            int nlen = r[id] - i + 1;
            chkmax(ans[id], dp[nlen]);
        }
    }
    cerr << 1.0 * clock() / CLOCKS_PER_SEC << ' ' << cr.size() << endl;
    
    int rtm = 0;
    while (1.0 * (clock() - fr) / CLOCKS_PER_SEC < 38) {
        rtm += 1;
        if (rtm > 50000) break; 
        int p = grd(1, n); // >= p, < p 
        dp[p - 1] = 0;
        int rs = min(maxn, p + k - 1);
        for (int j = p; j < rs; j++)
            dp[j] = 0;
        for (int j = p + k - 1; j <= n; j++)
            dp[j] = max(dp[j - 1], dp[j - k] + s[j]);
        ll cur = dp[p]; 
        for (int j = p - k + 1; j <= p; j++) dp[j] = 0;
        for (int j = p - k; j >= 1; j--) 
            dp[j] = max(dp[j + 1], dp[j + k] + s[j + k - 1]);
        dp[p] = cur;
        for (int i = 1; i <= q; i++)
            if (l[i] <= p && r[i] >= p)
                chkmax(ans[i], dp[l[i]] + dp[r[i]]);
    }
    cerr << rtm << endl;
    for (int i = 1; i <= q; i++)
        printf("%lld\n", ans[i]);
    return (0-0); 
}