比赛 |
近期练习题回顾 |
评测结果 |
AAAAAAAAAA |
题目名称 |
修剪草坪 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.072 s |
代码语言 |
C++ |
内存使用 |
16.71 MiB |
提交时间 |
2018-10-20 23:36:58 |
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
long long ans,f[100005],q[100005],n,m,t,w,a[100005],z[100005];
int main(){
freopen("mowlawn.in","r",stdin);
freopen("mowlawn.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++){scanf("%lld",&a[i]);ans=ans+a[i];}
t=1;w=1;q[1]=z[1]=0;
for(int i=1;i<=n+1;i++){
while(t>0&&i-z[t]>m+1)t++;
f[i]=q[t]+a[i];w++;q[w]=f[i];z[w]=i;
while(w>t&&q[w]<q[w-1]){
q[w-1]=q[w];
z[w-1]=z[w];
w--;
}
}
printf("%lld",ans-f[n+1]);
return 0;
}