Histogram

Time limit4sMemory limit1024 MB

Summary

Given a histogram of N bars, find the maximum total area of at most K non-overlapping rectangles for K = 1, 2, and 3.

Level: Hard8 of 10
Topics: Stack, Dynamic programming, Divide and conquer
Solved: No attempts yet

Problem

Consider a histogram made of $N$ rectangles whose bases are parallel to the floor, placed side by side on the floor. Each rectangle has width 1, and the height of the $i$ -th rectangle from the left is the integer $H_i$ .

The figure below shows one example of a possible histogram.

Inside this histogram, choose at most $K$ rectangles that satisfy all of the following: each base is parallel to the floor, the interiors of any two rectangles do not overlap (they may touch at corners and edges), and every side length is an integer. The goal is to maximize the sum of their areas. Call this maximum $f(K)$ .

Write a program that computes $f(1)$ , $f(2)$ , and $f(3)$ .

Constraints

$1 \le N \le 500\,000$
$1 \le H_i \le 500\,000$ ( $1 \le i \le N$ )

Examples1

Example 1
Input
```
1
1
```
Expected output
```
1
1
1
```