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
#include <bits/stdc++.h>

using namespace std;

int n,k,q,a,b;
long long t[300005];
long long dp[300005];

int main()
{
    scanf("%d%d%d",&n,&k,&q);
    for (int i=1; i<=n; i++)
    {
        scanf("%lld",&t[i]);
        t[i]+=t[i-1];
    }
    for (int j=1; j<=q; j++)
    {
        scanf("%d%d",&a,&b);
        for(int i=a-1; i<=b; i++) dp[i]=0;
        for (int i=a+k-1; i<=b; i++)
        {
            dp[i]=max(dp[i-1],dp[i-k]+t[i]-t[i-k]);
        }
        printf("%lld\n",dp[b]);
    }
}