1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
#define MAX(a,b) (((a)>(b))?(a):(b))
using ll=long long;
const int C=500001;

ll a[C], csc[C], dp[C];
int main(){
	int n, k, q, i, l, r;

	scanf ("%d %d %d", &n, &k, &q);
	for (i=1; i<=n; i++) scanf ("%lld", &a[i]);
	for (i=1; i<n; i++) csc[i] = csc[i-1] + a[i];

	while (q--){
		scanf ("%d %d", &l, &r);
		for (i=l+k-1; i<=r; i++){
			dp[i] = MAX(dp[i-1], dp[i-k] + csc[i] - csc[i-k]);
		}
		printf ("%lld\n", dp[r]);
		for (i=l+k-1; i<=r; i++) dp[i] = 0;
	}

return 0;}