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

long long int *a; // sumy częściowe wartości żołnierzy
long long int **b; // odpowiedzi dla każdych (i,d), gdzie i - początek, d - długość pomniejszona o k

int main()
{
    int n, k, q;
    scanf("%d%d%d", &n, &k, &q);
    a = new long long int[n+1];
    b = new long long int*[n-k+1];
    for (int i = 0; i <= n-k; i++)
        b[i] = new long long int[n-i-k+1];
    a[0] = 0LL;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &a[i+1]);
        a[i+1] += a[i];
    }
    
    for (int i = n-k; i > n-2*k; i--) // i - początek, tylko jedna k-tka się zmieści
    {
        long long int tmp = a[i+k] - a[i]; // suma k elementów począwszy od i
        if (tmp < 0) tmp = 0;
        b[i][0] = tmp; // jeśli długość jest k, to mamy dokładnie jedną możliwość
        for (int d = 1; d <= n-i-k; d++) // d - długość pomniejszona o k
        {
            b[i][d] = tmp; // albo bierzemy sumę od i...
            if (b[i][d] < b[i+1][d-1]) b[i][d] = b[i+1][d-1]; // ...albo najlepszą opcję dalej
        }
    }
    
    for (int i = n-2*k; i >= 0; i--) // i - początek
    {
        long long int tmp = a[i+k] - a[i]; // suma k elementów począwszy od i
        if (tmp < 0) tmp = 0;
        b[i][0] = tmp; // jeśli długość jest k, to mamy dokładnie jedną możliwość
        for (int d = 1; d < k; d++) // d - długość pomniejszona o k
        {
            b[i][d] = tmp; // albo bierzemy sumę od i...
            if (b[i][d] < b[i+1][d-1]) b[i][d] = b[i+1][d-1]; // ...albo najlepszą opcję dalej
        }
        for (int d = k; d <= n-i-k; d++) // d - długość pomniejszona o k
        {
            b[i][d] = tmp + b[i+k][d-k]; // albo bierzemy sumę od i i optymalnie uzupełniamy...
            if (b[i][d] < b[i+1][d-1]) b[i][d] = b[i+1][d-1]; // ...albo najlepszą opcję dalej
        }
    }
    
    int l, r;
    for (int i = 0; i < q; i++)
    {
        scanf("%d%d", &l, &r);
        if (r-l+1 < k)
            printf("0\n");
        else
            printf("%lld\n", b[l-1][r-l+1-k]);
    }
    
    return 0;
}