记录编号	138632	评测结果	AAAAAAAAAA
题目名称	773.[USACO Open11] 修剪草坪	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	0.062 s
提交时间	2014-11-06 07:53:37	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
using namespace std;
int n,k,i,j,p;
long long a[100001]={0},f[100001]={0},zui[100001]={0},head=1,tail=0;
void getmax(int x)
{
	long long y=f[x]-a[x+1];
	while(head<=tail&&y>f[zui[tail]]-a[zui[tail]+1])tail--;
	zui[++tail]=x;
}
int main()
{
	freopen("mowlawn.in","r",stdin);
	freopen("mowlawn.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]+=a[i-1];
	if(k>=n)
	{
		printf("%lld\n",a[n]);
		return 0;
	}
	f[1]=a[1];
	for(i=2;i<=k;i++)
	{
		f[i]=a[i];
		getmax(i-1);
	}
	for(i=k+1;i<=n;i++)
	{
        while(zui[tail]-zui[head]>=k)head++;
		f[i]=f[zui[head]]-a[zui[head]+1]+a[i];
		getmax(i-1);
	}
	printf("%lld\n",f[n]);
	return 0;
}