Best interval through priced segments
National Olympiad — National round
Submission name: segments.cpp
Problem summary
N closed segments on the number line carry signed prices per unit length. Choose two integer cut coordinates; the revenue is the sum, over every segment, of its price times the length of its part between the cuts. Overlaps contribute separately. Maximize revenue.
Input
N; then N triples left endpoint, right endpoint, unit price.
Output
Maximum revenue as an integer.
Constraints
1 ≤ N ≤ 100,000; −10^9 ≤ left < right ≤ 10^9; −10,000 ≤ price ≤ 10,000. A strictly positive optimum is guaranteed.
Worked example
An independently prepared example for this explanation.
Input
2 0 4 3 1 3 -5
Output
3
Solution analysis
- Create +price at each left endpoint and −price at each right endpoint. Sort and group events.
- Between consecutive endpoints the total price density is constant; multiply it by the gap length.
- Apply maximum-subarray DP to these weighted gaps. Within a constant-density gap an optimum cut can move to an endpoint without worsening the revenue.
Why it works
Sweep events compute exactly the sum of all covering prices on every gap. Any interval revenue is a contiguous sum of gap weights; endpoint movement ensures an optimum of this form exists. Kadane’s recurrence maximizes all such sums.
Watch out. Use 64-bit arithmetic for gap length times total density. Do not merge overlapping segments by taking only one price.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Sweep events compute exactly the sum of all covering prices on every gap. Any interval
// revenue is a contiguous sum of gap weights; endpoint movement ensures an optimum of this form
// exists.
#include<iostream>
#include<algorithm>
#include<map>
#include<tuple>
#include<iterator>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
map<long long,long long>ev;
while(n--){
long long l,r,p;
cin>>l>>r>>p;
ev[l]+=p;
ev[r]-=p;
}
long long density=0,prev=ev.begin()->first,cur=0,ans=0;
for(auto[x,delta]:ev){
cur=max(0LL,cur+(x-prev)*density);
ans=max(ans,cur);
density+=delta;
prev=x;
}
cout<<ans<<'\n';
}