lhz2022 @ 2024-10-06 10:59:01
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() puts("I WILL AK")
#define N 100007
int a[N],b[N],dp[N],que[N],ll,rr,n,m;
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
b[i]=b[i-1]+a[i];
}
for(int i=1;i<=n;++i){
dp[i]=dp[que[ll]-1]-b[que[ll]]+b[i];
while(ll<=rr&&dp[que[rr]-1]-b[que[rr]]<=dp[i]-b[i+1]){
rr--;
}
que[++rr]=i;
while(ll<=rr&&que[rr]-que[ll]>=m) ++ll;
}
cout<<dp[n];
return 0;
}
by lhz2022 @ 2024-10-06 10:59:31
30pts求条
by __Tonycyt__ @ 2024-10-06 11:02:17
btd