Yet Another Subarray Problem cf1197D

题目

题面

You are given an array a1,a2,…,an and two integers m and k.

You can choose some subarray al,al+1,…,ar−1,ar.

The cost of subarray al,al+1,…,ar−1,ar is equal to ∑i=lrai−k⌈(r−l+1)/m⌉, where ⌈x⌉ is the least integer greater than or equal to xx.

The cost of empty subarray is equal to zero.

For example, if m=3m=3, k=10k=10 and a=[2,−4,15,−3,4,8,3]a=[2,−4,15,−3,4,8,3], then the cost of some subarrays are:

·       a3…a3:15−k⌈1/3⌉=15−10=5

·       a3…a4:(15−3)−k⌈2/3⌉=12−10=2

·       a3…a5:(15−3+4)−k⌈3/3⌉=16−10=6

·       a3…a6:(15−3+4+8)−k⌈4/3⌉=24−20=4

·       a3…a7:(15−3+4+8+3)−k⌈5/3⌉=27−20=7

Your task is to find the maximum cost of some subarray (possibly empty) of array a.

 

Input

The first line contains three integers nn, mm, and kk (1≤n≤3⋅10^5,1≤m≤10,1≤k≤10^91≤n≤3⋅10^5,1≤m≤10,1≤k≤10^9).

The second line contains nn integers a1,a2,…,ana1,a2,…,an (−109≤ai≤109−109≤ai≤109).

Output

Print the maximum cost of some subarray of array a.

Examples

Input

7 3 10

2 -4 15 -3 4 8 3

Output

7

Input

5 2 1000

-13 -4 -9 -20 -11

Output

0

思路

这可以理解是一个01背包的拓展（就是一个板子题），思路是将所取数组的长度对m取余来减少状态量

代码

#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
long long dp[300010][20]/*第一个代表所取数组的末尾，第二个代表长度对m取余*/, a[300010];
int main()
{
	int n, m, k;
	//freopen("F:/y.txt", "r", stdin);
	while (~scanf("%d %d %d", &n, &m, &k))
	{
		memset(dp, -0x3f3f3f3f, sizeof(dp));
		dp[0][m - 1] = 0;
		long long ans = 0;
		for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
		for (int i = 1; i <= n; i++)
			for (int j = 0; j < m; j++)
			{
				if (j == 0)/*当j=0时，[(r-l+1)/m]将会加1，所以判断a[i]-k
                            与dp[i - 1][m - 1] + a[i] - k的大小来保证dp[][]中的是最大值*/
					dp[i][j] = max(dp[i - 1][m - 1] + a[i] - k, a[i] - k);
				else/*当j!=0时，数组的长度加1不会影响[(r-l+1)/m]的大小*/
					dp[i][j] = dp[i - 1][j - 1] + a[i];
				ans = max(ans, dp[i][j]);
			}
		printf("%lld\n", ans);
	}
	return 0;
}