解析

把题目标签写在数据范围上的一道题

由于k过大，显然无法dp

那就只能贪了

一开始被完全带跑偏了…

想的是把序列降序排列然后从后往前划分…

这个思路能很简单的写出nkdp

然后就卡住了…

算看了一半题解吧

看到第一段“考虑分成k组”后退出来了

有了这个线头后面就非常顺

以后还是要努力培养在推不出好的性质时打破第一印象的能力

考虑正解

清零k次等价于把boss分成不多于k组

每次把新元素加入的同时获得原来集合内元素和的代价

所以只需要维护集合的元素和即可

考虑把所有集合放入大根堆

降序加入元素

显然正的元素直接全放一组是最好的

如果现在是负的元素

如果堆顶还是正的那就加进去，不难发现，因为后面的元素更小，这样能尽可能让这个集合发挥余热（性感理解一下），肯定还是好的

如果堆顶负了我们就尽可能的让新元素成为一个新的集合

感性理解一下，在啥都是负的时候，我们肯定是让所有的元素从大到小蛇形分布，这样使产生贡献的元素都是相对负的不厉害的

如果极小值全塞到一起肯定是不好的

（为什么我的贪心分析全是感性理解啊qwq）

代码

#include<bits/stdc++.h>const int N=1e6+100;const int mod=1e9+7;#define ll long longusing namespace std;inline ll read() {ll x(0),f(1);char c=getchar();while(!isdigit(c)) {if(c=='-')f=-1;c=getchar();}while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;}int n,m;ll a[N],ans;bool cmp(ll x,ll y){return x>y;}priority_queue<ll>q;int main(){n=read();m=read();++m;for(int i=1;i<=n;i++) a[i]=read();sort(a+1,a+1+n,cmp);for(int i=1;i<=n;i++){ll x=a[i];if(q.empty()||(q.top()<0&&(signed)q.size()<m)){q.push(x);}else{ll o=q.top();q.pop();ans+=o;o+=x;q.push(o);}}printf("%lld\n",ans);}/*1281239*/