Expert.
Put your skills to the test.

Problem summary

Over N weeks, buy one ton, sell one ton, or do nothing each week. Inventory cannot be negative and must finish at zero. Storing one ton from week i to j costs S(j−i). Given possibly negative prices, maximize profit.

Constraints

0 ≤ N,S,|Pi| ≤ 10^6.

Worked example

Official example, transcribed with whitespace restored from the PDF.

5 3
-2 10 6 23 20

24

Solution analysis

1. Replace price Pi by qi=Pi−S·i. A ton bought in week i and sold in week j then earns qj−qi, exactly accounting for storage. This reduces the problem to unit-capacity trading without storage costs.
2. Maintain a min-heap of candidate purchase prices. At current price q, if the cheapest candidate h is smaller than q, increase the answer by q−h, remove h, and insert q as a replacement candidate. Always insert q once more for the current week. The replacement permits revising a previously selected sale: a future better sale can take over that earlier purchase.
3. If an apparent plan uses a week both to sell and buy at the same adjusted price, cancel that pair and directly match the earlier purchase to the later sale; its profit is unchanged. Thus the heap representation still gives a valid one-action-per-week plan. In the sample buying in weeks 1 and 3 and selling in weeks 4 and 5 earns 24.

Why it works

One may view each week as a candidate buy, with each profitable extraction matching the cheapest currently exchangeable buy to the new sale. Exchanging any other buy for the cheapest cannot decrease profit. The extra copy of the sale price represents the option to replace this sale with a later sale, preserving the already earned difference. This exchange rule inductively maintains the maximum attainable profit for the prefix. Any intermediate sell-and-buy at the same week cancels without changing profit or negative-inventory feasibility, so the optimum represented by the heap is attainable under the original action limit.

Watch out. Use Pi−S·i, not Pi+S·i; adjusted prices and profit need 64-bit integers.

An independently written complete program with standard headers.

#include<functional>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long storage;
    cin>>n>>storage;
    priority_queue<long long,vector<long long>,greater<long long>>candidates;
    long long answer=0;
    for(int i=0;i<n;++i){
        long long price;
        cin>>price;
        long long adjusted=price-storage*i;
        if(!candidates.empty()&&candidates.top()<adjusted){
            answer+=adjusted-candidates.top();
            candidates.pop();
            // This copy permits replacing the current sale by a later one.
            candidates.push(adjusted);
        }
        candidates.push(adjusted);
    }
    cout<<answer<<'\n';
}