$O(n^2)$ 过十万。

暴力卡卡常即可AC。逆序循环总是有好处的。

#include<cstdio>
#define RI register int
char buf[1<<18],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p1=buf,p2=p1+fread(buf,1,1<<18,stdin),p1==p2)?EOF:*p1++)
const int inf=1073741823;typedef long long LL;int FL;char CH;template<typename T>bool in(T&a){if(CH==EOF)return 0;for(FL=1,CH=getchar(),a=0;(CH<'0'||CH>'9')&&CH!=EOF;CH=getchar())if(CH=='-')FL=-1;for(;CH>='0'&&CH<='9'&&CH!=EOF;CH=getchar())a=a*10+CH-'0';return a*=FL,1;}template<typename T,typename...Args>int in(T&a,Args&...args){return in(a)+in(args...);}
const int maxn=1e5+10;
int a[maxn],n,k;LL f[maxn],ss;
const LL LINF=1ll<<50;
LL min(LL a,LL b){return a<b?a:b;}
int main(){
	in(n,k);
	for(RI i=n;i;--i)in(a[i]),ss+=a[i],f[i]=LINF;
	f[0]=LINF;
	register LL rs;
	for(RI i=n,j;i>=n-k;--i){
		rs=LINF;
		j=n+1;
		for(;j>i;--j)rs=min(rs,f[j]);
		f[i]=rs+a[i];
	}for(RI i=n-k-1,j;~i;--i){
		rs=LINF;
		j=i+k+1;
		for(;j>i;--j)rs=min(rs,f[j]);
		f[i]=rs+a[i];
	}
	printf("%lld\n",ss-f[0]);
	return 0;
}

这数据强度堪忧（