思路
假设我们选择了第 \(p_1,p_2 \cdots p_x\) 场电影，那么减去的舒畅值是 \(d\times(p_1+p_2-p_1+\cdots+p_x-p_{x-1})=d\times p_x\) 所以减去的舒畅值，只与最后一场电影的天数有关。
所以我们可以枚举最后一场电影在第几天，假设在 \(i\) 天。
那么，减去的舒畅值是固定的 \(i\times d\)，所以我们需要在前 \(i\) 场电影中，选择权值最大的 \(m\) 场，特别的，如果某场电影的舒畅值是负数，我们就不选，因为这场电影对答案的贡献是负的。
现在，我们需要思考的是如何快速地求出前 \(i\) 个整数中所有非负整数前 \(m\) 大的数之和。
赛时没想到好方法，只想到了优先队列，时间复杂度应该是过不了的，但是居然 AC 了。
AC code
#include<bits/stdc++.h>
using namespace std;
long long T,n,m,d,a;
long long sum,ans;
priority_queue<long long,vector<long long>,greater<long long> >q;
int main()
{
scanf("%lld",&T);
while(T--)
{
while(!q.empty()) q.pop();
scanf("%lld%lld%lld",&n,&m,&d),ans=sum=0;
for(long long i=1;i<=n;++i)
{
scanf("%lld",&a);
if(a<0) continue;
q.push(a),sum+=a;
if(q.size()>m) sum-=q.top(),q.pop();
ans=max(ans,sum-d*i);
}
printf("%lld\n",ans);
}
}
优化
大概是出题人没卡优先队列吧，上面的程序可以卡成 \(\operatorname{TLE}\) 的，赛时以拿分为主，平时练习以彻底解决为主。所以，我们需要思考一种正确的复杂度的做法，也就是另一种可以得到数据顺序的数据结构，但是如果涉及了排序，时间复杂度至少都是 \(O(logn)\)。
但是有一种不需要排序也能得到顺序的方式，那就是桶排，单纯的桶排想要找最小还是很麻烦，于是我们想到了 \(\operatorname{set}\)。
\(\operatorname{set}\) 有一个功能是 \(\operatorname{begin()}\) 可以求出这个集合最小的数字。（蒟蒻的我在看官方程序前都不知道）
所以我们只需要一个套了 \(\operatorname{pair}\) 的 \(\operatorname{set}\) 就可以代替上面的优先队列的相关操作。具体可以看官方程序。