Official Editorial (C++)

Explanation

We process the branches from lowest to highest, calculating for each branch the amount of area it has that is not covered by a subsequent one. Looking at the image of the sample case given in the problem statement, we would be calculating the area outlined in black for each branch.

For each branch, there are two cases:

1. No branch covers the current one. In this case, we add $\frac{dh}{2}$ to the total, as that is the formula for the area of a triangle.
2. A branch covers the current one, turning it into a trapezoid. In this case, we need to use the formula for the area of a trapezoid, which is $\frac{h(b_1+b_2)}{2}$, where $b_1$ and $b_2$ are the lengths of the top and bottom bases.

Implementation

Time Complexity: $\mathcal{O}(N)$

Copy
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

/** @return the area of a trapezoid with the given base lens and height */

Copy
def trap_area(base1: float, base2: float, height: float) -> float:
	""":return: the area of a trapezoid with the given base lens and height"""
	return height * (base1 + base2) / 2


for _ in range(int(input())):
	branch_num, base, height = [int(i) for i in input().split()]
	offsets = sorted(int(i) for i in input().split())
	assert branch_num == len(offsets)