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
#include <bits/stdc++.h>
using namespace std;
long long tab[300009];
long long pref[300009];
long long help[300009];
int n,m,q;
long long suma(int l, int p)
{
    return pref[p]-pref[l-1];
}
long long REAL(int l, int p)
{
    for(int i=l+m-1;i<=p;i++)
    {
        help[i]=max(help[i-1],help[i-m]+suma(i-m+1,i));
    }
    long long wynik=help[p];
    for(int i=l;i<=p;i++)
    {
        help[i]=0;
    }
    return wynik;
}
map<pair<int,int>,long long>M;
int main()
{ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);srand(time(0));
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>tab[i];
        pref[i]=(pref[i-1]+tab[i]);
    }
    for(int i=1;i<=q;i++)
    {
        int l,p;
        cin>>l>>p;
        if(p-l+1==m){cout<<max((long long)0,suma(l,p))<<endl;continue;}
        if(p-l+1<m){cout<<0<<endl;continue;}
        if(M.find({l,p})!=M.end()){cout<<M[{l,p}]<<endl;continue;}
        long long wynik=REAL(l,p);
        cout<<wynik<<endl;
        M[{l,p}]=wynik;
    }
    return 0;
}