HongYoung @ 2019-07-15 20:07:32
-
include<iostream>
-
include<cstdio>
-
include<cstring>
-
define ll long long
- using namespace std;
- ll n,k;ll f[100100],s[100100];
- ll a[100100];
- struct ss{
- ll x,y;
- };ss v[100100];
- void read(ll &x)
- {
- int t=0,r=1;
- char c=getchar();
- while(c<'0'||c>'9')(c=='-'?r=-1:0),c=getchar();
- while(c>='0'&&c<='9')
- {
-
t=t*10+c-'0',c=getchar();
- }
- x=t*r;return;
- }
- ll head=0,tail=1;
- ll getmax(ll x)
- {
- ll len=f[x-1]-s[x];
-
- while(head<=tail&&v[head].x<=len)tail--;
- v[++tail].x=len;v[tail].y=x;
- while(v[head].y<x-k&&head<=tail)head++;
- return v[head].x;
-
- }
- int main()
- {
- read(n);read(k);
- for(ll i=1;i<=n;i++)
- read(a[i]),s[i]=s[i-1]+a[i];
- for(int i=1;i<=n;i++)
- f[i]=getmax(i)+s[i];
- printf("%lld",f[n]);
- return 0;
- }