Forzz_ @ 2023-03-04 11:26:36
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define R register
#define U unsigned
#define IL inline
#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
const int M=1e5;
int n,m;
int a[N];
int f[N];
deque<int>q;
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
scanf("%lld%lld",&n,&m);
int sum=0,minn=INF;
q.push_front(0);
for(R int i=1;i<=n;i++){
scanf("%lld",&a[i]);
sum+=a[i];
while(!q.empty()&&i-q.front()>m+1)
q.pop_front();
if(!q.empty())
a[i]+=a[q.front()];
while(!q.empty()&&a[q.back()]>=a[i])
q.pop_back();
q.push_back(i);
if(i>=n-m)
minn=min(minn,a[i]);
}
printf("%lld\n",sum-minn);
return 0;
}
/*
*/
by george0929 @ 2023-05-29 20:03:28
15行INF初值不够大,要1e17 @Forzz_