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
#include <iostream>
#include <cstdint>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <numeric>
#include <set>
#include <tuple>

using namespace std;

int main()
{
    int n,k,q;

    cin>>n>>k>>q;
    vector<int> a;

    copy_n(istream_iterator<int>(cin), n, back_inserter(a));

    vector <int64_t> w_oddzialow(a.size(),0);

    int64_t w_oddzailu =0;
    for (int i=0; i<k;i++){
        w_oddzailu += a[i];
    }
    w_oddzialow[k-1]=w_oddzailu;
    for (int i=k; i<n;i++){
        w_oddzailu += a[i];
        w_oddzailu -= a[i-k];
        w_oddzialow[i]=w_oddzailu;
    }

    vector<int64_t> optimum (n,0);

    for (int test =0; test<q; test++){
        int l,r;
        cin>>l>>r;
        if (r-l+1<k){
            cout<<"0\n";
            continue;
        }
        l--;
        r--;
        for (int i =l; i<l+k; i++)
            optimum[i]=0;

        optimum[l+k-1] = max<int64_t>(w_oddzialow[l+k-1],0);
        for (int i=l+k; i<=r; i++){
            optimum[i] = max<int64_t>(max(optimum[i-1], w_oddzialow[i]+optimum[i-k]),0ll);
        }
        cout<<max<int64_t>(optimum[r],0)<<'\n';

    }
    return 0;
}