Beacon Activation on a Straight Highway

Problem Statement

Beacon Activation on a Straight Highway Problem Description A straight highway has positions numbered 1 to m . There is one beacon at every position, and the beacon at position j has power p_j (possibly 0 ). There are also n zones. Zone i covers every position from L_i to R_i , both ends included. You choose any subset of the beacons to activate (possibly none, possibly all). The benefit of a zone is then: 0 if no activated beacon lies inside [L_i, R_i] ; otherwise, the power of the activated beacon with the largest position inside [L_i, R_i] , that is, the rightmost activated beacon in that zone. Only the rightmost activated beacon of a zone matters, so activating an extra beacon can lower the benefit of a zone that already had a stronger beacon further left. Several zones may take their benefit from the same beacon. Choose the beacons to activate so that the sum of the benefits of all zones is as large as possible, and report that maximum. Each input file holds several independent te