先注意到我们娱乐值损耗的多少只与最后一场电影有关系，所以假设最后一场电影看的下标为 \(k\)，那么最后就要减去 \(d \times k\)。
得出这个性质之后开个小根堆反悔贪心即可，首先 \(a_i<0\) 的没必要考虑，对于 \(a_i>0\) 的，如果还没到 \(m\) 场电影，我们就直接往里塞就可以，如果到了，我们就进行反悔操作，取出已选的贡献最小的那场电影，然后看看会不会更优，如果会的话就加进去。
算是反悔贪心板子题，时间复杂度 \(O(n\log n)\)。
然后就是一定要记得开 long long，吃了两发。
#include <cstdio>
#include <queue>
#include <algorithm>
typedef long long ll;
int t;
int n,m,d;
int a[200005];
void solve() {
scanf("%d",&t);
while(t--) {
scanf("%d%d%d",&n,&m,&d);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
std::priority_queue<int> q;
int tot=0;
ll ans=0,sum=0;
for(int i=1;i<=n;i++) {
if(a[i]<0) continue;
if(tot<m) {
tot++;
q.push(-a[i]);//大根堆每次存相反数作用就是小根堆
sum+=a[i];
} else if(-q.top()<a[i]) {//反悔操作
sum+=q.top();
q.pop();
sum+=a[i];
q.push(-a[i]);
}
ans=std::max(ans,sum-1ll*d*i);
}
printf("%lld\n",ans);
}
}
int main() {
solve();
return 0;
}