https://codeforces.com/problemset/problem/1862/E

用一个小根堆，如果是数组每一个位置的前k大或者小的值，可以用小根堆存数组数值，用ans维护总和，一位区间左端点永远在1处，所以可以直接存数值，如果区间左端点不永远在1处，小根堆存下标，超过pop

const int N = 2e5 + 10;
int a[N];
void solve()
{
    int n, m, d; cin >> n >> m >> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] < 0) a[i] = 0;
    }
    priority_queue<int, vector<int>, greater<int> >xg;
    int mmax = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {

        if (a[i] > 0)
        {
            if (xg.size() < m)
            {
                xg.push(a[i]);
                ans += a[i];
            }
            else
            {
                if (a[i] > xg.top())
                {
                    ans -= xg.top();
                    ans += a[i];
                    xg.pop();
                    xg.push(a[i]);
                }
            }
        }
        mmax = max(mmax, ans + (-1 * d * i));
    }
    cout << mmax << '\n';
}