## IOI '18 P6 - Meetings

View as PDF

Points: 50 (partial)
Time limit: 4.5s
Memory limit: 768M

Problem type
Allowed languages
C++

There are mountains lying in a horizontal row, numbered from through from left to right. The height of the mountain is . Exactly one person lives on the top of each mountain.

You are going to hold meetings, numbered from through . The meeting () will be attended by all the people living on the mountains from to , inclusive . For this meeting, you must select a mountain as the meeting place (). The cost of this meeting, based on your selection, is then calculated as follows:

• The cost of the participant from each mountain is the maximum height of the mountains between the mountains and , inclusive. In particular, the cost of the participant from the mountain is , the height of the mountain .
• The cost of the meeting is the sum of the costs of all participants.

For each meeting, you want to find the minimum possible cost of holding it.

Note that all participants go back to their own mountains after each meeting; so the cost of a meeting is not influenced by the previous meetings.

#### Implementation Details

You should implement the following function:

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R);

• H: an array of length , representing the heights of the mountains.
• L and R: arrays of length , representing the range of the participants in the meetings.
• This function should return an array of length . The value of () must be the minimum possible cost of holding the meeting .
• Note that the values of and are the lengths of the arrays, and can be obtained as indicated in the implementation notice.

#### Example

Let , , , , and .

The grader calls minimum_costs([2, 4, 3, 5], [0, 1], [2, 3]).

The meeting has and , so will be attended by the people living on the mountains , , and . If the mountain is chosen as the meeting place, the cost of meeting is calculated as follows:

• The cost of the participant from the mountain is .
• The cost of the participant from the mountain is .
• The cost of the participant from the mountain is .
• Therefore the cost of the meeting is .

It is impossible to hold the meeting at a lower cost, so the minimum cost of the meeting is .

The meeting has and , so will be attended by the people living on the mountains , , and . If the mountain is chosen as the meeting place the cost of the meeting is calculated as follows:

• The cost of the participant from the mountain is .
• The cost of the participant from the mountain is .
• The cost of the participant from the mountain is .
• Therefore the cost of the meeting is .

It is impossible to hold the meeting at a lower cost, so the minimum cost of the meeting is .

• ()
• ()
• ()