P6100 [USACO19FEB] Painting the Barn G

Farmer John is not very good at multitasking. He often gets distracted and has trouble finishing long-term projects. Right now, he is painting one side of a barn, but he keeps focusing on very small areas and then gets interrupted by the need to take care of the cows, causing some parts of the barn to have more layers of paint than others. We describe the barn wall as an $X$-$Y$ plane, and each painted region is a rectangle. FJ draws $N$ rectangles on this plane, and the sides of each rectangle are all parallel to the coordinate axes. Therefore, we describe a rectangle by the coordinates of its bottom-left corner and top-right corner. FJ wants to paint enough layers so that he will not need to repaint again in the near future. However, he also does not want to waste time applying too much paint. It turns out that exactly $K$ layers of paint is the ideal amount. But because the area painted exactly $K$ times is too small, FJ is not very happy. He decides to draw at most two **non-overlapping** rectangles to increase this area (here, “overlapping” means the intersection area of the two rectangles is greater than $0$; if two rectangles only share an edge or a point, they are not considered overlapping). Of course, it is also allowed to draw no new rectangles, or only draw one new rectangle.

The first line contains two integers $N, K$ ($1 \leq N, K \leq 10^5$). The next $N$ lines each contain four integers $x_1, y_1, x_2, y_2$ ($0 \leq x_1, y_1, x_2, y_2 \leq 200$), describing a rectangle. Its bottom-left corner is $(x_1, y_1)$, and its top-right corner is $(x_2, y_2)$. It is guaranteed that all rectangles have positive area, i.e. none of them degenerates into a line segment or a point. Just like the existing rectangles, for any newly drawn rectangle, the bottom-left and top-right coordinates must also be integers, the coordinates must be within $0 \sim 200$, and the area must also be positive.

Output the maximum area that is painted exactly $K$ times.

Translated by ChatGPT 5