Advanced Graph Algorithms→ Disjoint-set datastructure (union-find)→ Advertising hoardings
Downtown Siruseri is booming and the main road is now lined with a continuous row of skyscrapers. For aesthetic reasons, the Siruseri Municipal Corporation had banned advertising hoardings along the main road.
The High Court has squashed the Municipal Corporation's ban as unconstitutional and ruled that rectangular hoardings may be put up parallel to the main road, along the walls of the skyscrapers lining the road. The only restriction is that a hoarding may not extend above the height of any building along its length.
Advertising agencies across the city are buzzing witth excitement at the news and accounts executives are busy calculating how large they can make their hoardings, in terms of total area, to collect maximum revenue from advertisers.
For instance suppose the Siruseri skyline appears as follows, where the number at the top of each building specifies its height while the number at the bottom of each building specifies its width, both quantities measured in metres.
80
70 ---------
--------- 55 | |
50 | | 50 ------| |
---| |------ | | | 40
30 | | | | | | |------
------| | | | | | | |
| | | | |10 | | | |
| | | | |---| | | |
| | | | | | | | |
===========================================================
20 10 30 20 10 20 30 20
In this situation, the biggest legal hoarding spans the second, third and fourth buildings with an area of 60 × 50 = 3000 square metres. The next best possibility is a hoarding of 70 × 40 = 2800 square metres, spanning the last three buildings.
Your task is to compute the maximum area that a hoarding can have for a given arrangement of skyscrapers.