沿用 easy version 的思路:考虑如果到目前已经放了 \(2\) 个集合及以上,那么接下来只要轮换放置就可以避免「用同一个账号连续发出两个帖子」。所以在放了 \(2\) 个集合以后只要找到剩下前 \(k-2\) 大的数放即可。
于是一定是把前 \(x\) 个数放在第一个集合,第 \(x+1\) 放在第二个集合,剩下的选出前 \(k-2\) 大放在剩下集合。
然后直接倒着枚举 \(x\),用堆(priority_queue)维护剩余的前 \(k-2\) 大的数,计算即可。
const int N=500005;
int n,m,T;
ll a[N];
priority_queue<ll>p;
ll sum,ans;
inline void add(ll x)
{
sum+=x;
p.push(-x);
ll u=-p.top();
sum-=u;
p.pop();
}
void work()
{
n=read(),m=read()-2;
for (int i=1;i<=n;i++) a[i]=read();
ll tot=a[1];
sum=0;
while (!p.empty()) p.pop();
for (int i=n-m+1;i<=n;i++) sum+=a[i],p.push(-a[i]);
for (int i=2;i<=n-m-1;i++) tot-=min(a[i-1],a[i]);
ans=tot+sum+a[n-m];
for (int i=n-m-1;i>=2;i--)
{
add(a[i+1]);
tot+=min(a[i],a[i-1]);
ans=max(ans,tot+sum+a[i]);
}
printf("%lld\n",ans);
return;
}