思路

先化简总能量的表达式。若在日期 $i_1<i_2<\dots<i_k$ 采集，记 $i_0=0$，则

$$\sum_{j=1}^{k}\left(a_{i_j}-d\cdot(i_j-i_{j-1})\right)=\sum_{j=1}^{k}a_{i_j}-d\cdot i_k$$

也就是说，无论中间隔了多少天，时间衰减只取决于最后一次采集的日期 $i_k$。于是可以把问题拆成两部分：

• 枚举最后一天 $i$；
• 在 $1\sim i$ 中选出至多 $m$ 个正数（数值取 $a_j$），使它们的和尽量大，答案为 $\max(\text{和}-d\cdot i)$。

用小根堆维护当前选中的值（至多 $m$ 个，堆顶是其中最小值），从左到右扫描：

• 若 $a_i\le 0$：跳过。选它只会让和变小，还要额外支付时间衰减；
• 若堆中不足 $m$ 个：直接加入，堆顶即最小值，此时以 $i$ 结尾的最优集合发生了变化，更新答案；
• 若堆已满且 $a_i$ 大于堆顶：用 $a_i$ 替换堆顶（相当于从已选集合中换掉最小的一个），同样更新答案。

为什么只在「入堆」和「替换堆顶」时更新答案？ 其余情况下以 $i$ 结尾的最优集合与上一步相同，而衰减项 $d\cdot i$ 随 $i$ 增大而增大，因此不可能比之前更优，无需再更新。

允许一次都不采集，所以答案初值为 $0$。

复杂度： 每个测试用例时间 $O(n\log m)$，多组数据合计 $O(\sum n\log n)$；空间 $O(m)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << '\n'
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;

const int N = 2e5+10, inf = 1e18;
int a[N];

void go(){
    int n,m,d;cin>>n>>m>>d;          // n 天、最多采集 m 天、每天衰减 d
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    // 小根堆保存当前选中的 m 个最大值，堆顶是其中最小值
    priority_queue<int, vector<int>, greater<int>>pq;
    int ans = 0, tot = 0, idx = 0;   // ans 答案、tot 选中元素之和、idx 最后一次采集的日期

    for(int i=1;i<=n;i++){

        if(a[i]<=0){continue;}       // 非正数永远不值得采集
        else{
            if(pq.size()<m){
                // 还没选满，直接加入
                pq.push(a[i]);

                tot += a[i];
                idx = i;
                ans = max(ans, tot - idx*d);   // 以 i 为最后一天的收益

            }else if(a[i]>pq.top()){
                // 已选满且当前值更大，替换掉堆顶的最小值
                tot -= pq.top();
                tot += a[i];

                pq.pop();
                pq.push(a[i]);

                idx = i;
                ans = max(ans, tot - idx*d);
            }

        }
    }

    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int _=1;
    cin >>_;                         // 多组测试数据
    while(_--){
        go();
    }
    return 0;
}