/*暴力50*/#include<iostream>#include<cstdio>#include<cstring>#define maxn 100010#define ll long longusing namespace std;ll n,k,f[maxn][110],a[maxn],ans;ll init(){    ll x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}int main(){    n=init();k=init();    for(int i=1;i<=n;i++)        a[i]=init();    for(int i=1;i<=n;i++)        for(int j=0;j<=k;j++){            if(j>0)f[i][j]=max(f[i][j],f[i-1][j-1]+a[i]);            f[i][0]=max(f[i][0],f[i-1][j]);            ans=max(ans,f[i][j]);            ans=max(ans,f[i][0]);        }    printf("%lld",ans);    return 0;}

/*暴力的算法不好优化啊QAQ问了一下长郡中学的shenben学弟换一个状态 f[i]表示前i个且选了第i个的最大值n*n的做法是枚举前面的没选的最大的f[j-1]+a[j+1]+a[j+2]+...+a[i]转移就是 f[i]=max(f[j-1]+a[j+1]+a[j+2]+...+a[i]) 考虑到选j与i无关 所以只要找max f[j-1]-s[j] 这里选就选一段 只要保证了i-j<=k就好了优化嘛 单调队列 里面自然是维护 f[j-1]-s[j] 的最大值时效性上面说的 i-j<=k然后 维护下前缀和 */#include<cstdio>#define maxn 1000010#define ll long longusing namespace std;ll n,k,x,a[maxn],f[maxn],q[maxn],head,tail,ans;ll max(ll a,ll b){    return a<b?b:a;}ll init(){    ll x=0,f=1;char s=getchar();    while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();}    while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();}    return x*f;}void ins(ll x){    while(f[q[tail]-1]-a[q[tail]]<f[x-1]-a[x]&&head<=tail)        tail--;    q[++tail]=x;}int main(){    n=init();k=init();    for(int i=1;i<=n;i++){        x=init();        a[i]=x+a[i-1];    }    ins(1);    for(int i=1;i<=n;i++){        int p=q[head];        f[i]=f[p-1]+a[i]-a[p];        ans=max(ans,f[i]);        if(i-q[head]==k)head++;        if(i!=n)ins(i+1);    }    printf("%lld\n",ans);    return 0;}