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
#include<bits/stdc++.h>
using namespace std;
long long sumy[300010];
long long dp[300010];
int main()
{
	int n, k, q, i, l, r;
	scanf("%d%d%d", &n, &k, &q);
	for(i=1;i<=n;i++)
	{
		int a;
		scanf("%d", &a);
		sumy[i]=sumy[i-1]+a;
	}
	while(q--)
	{
		scanf("%d%d", &l, &r);
		if(r-l+1<k)
		{
			printf("0\n");
			continue;
		}
		//for(i=0;i<=n;i++)
		//	dp[i]=0;
		dp[l-1]=0;
		dp[l+k-2]=0;
		for(i=l;i<=r;i++)
		{
			if(i>=l+k-1)
				dp[i]=max(dp[i-1], dp[i-k]+sumy[i]-sumy[i-k]);
			else
				dp[i]=0;
		}
		printf("%lld\n", dp[r]);
	}
}