比赛 近期练习题回顾 评测结果 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;
}