记录编号	519762	评测结果	AAAAAAAAAA
题目名称	[USACO Open11] 修剪草坪	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2018-11-01 22:07:53	内存使用	3.36 MiB

#include <cstdio>
#include <iostream>
#include <queue>
using namespace std;
long long n,k,ans;
long long e[100005];
long long f[100005],d[100002];

long long sum[100005];
deque<int> q;
int main()
{
	freopen("mowlawn.in","r",stdin);
	freopen("mowlawn.out","w",stdout);
	cin >> n >> k;
	for (long long i = 1; i <= n; ++i)
	{
		scanf("%lld",e+i);
		sum[i] = sum[i-1]+e[i];
	}

	q.push_back(0);
	for (long long i = 1; i <= n; ++i)
	{
		d[i] = f[i-1]-sum[i];
		while(q.size()>1&&d[q.back()]<d[i])
			q.pop_back();
		q.push_back(i);
		while(q.size()>1&&q.front() < i-k )
			q.pop_front();
		f[i] = d[q.front()]+sum[i];
	}
	
	cout << f[n];
	return 0;
}