Painting the Barn

题目描述

农夫约翰不擅长同时处理多件事。他经常分心，这使得完成长期项目变得困难。现在，他正尝试给谷仓的一面刷漆，但他总是先刷一小块矩形区域，然后又被照顾奶牛的需求打断，导致谷仓的某些部分被刷了比其他部分更多的漆层。 我们可以将谷仓的一面描述为二维 $x$-$y$ 平面。农夫约翰刷了 $N$ 个矩形，每个矩形的边都与坐标轴平行，并由其左下角与右上角点的坐标描述。 农夫约翰希望给谷仓刷上若干层漆，以便近期不需要再次重刷。然而，他也不想浪费时间刷过多的漆层。事实证明，$K$ 层漆是最优的层数。但是，当他看到恰好被刷了 $K$ 层漆的覆盖面积时，他并不满意。他愿意再刷至多两个额外的矩形来尝试增加这部分面积，前提是这两个矩形互不相交（不共享任何正面积的公共部分）。注意，如果这样做效果最好，他也可以选择不刷新的矩形，或只刷一个新的矩形。

输入格式

第一行输入包含 $N$ 和 $K$（$1 \leq K, N \leq 10^5$）。 接下来的 $N$ 行中，每行包含四个整数 $x_1, y_1, x_2, y_2$，描述一个被刷漆的矩形区域，其左下角为 $(x_1, y_1)$，右上角为 $(x_2, y_2)$。所有 $x$ 和 $y$ 的取值范围均为 $0 \ldots 200$，且所有矩形面积均为正。 与他已经刷过的矩形类似，农夫约翰刷的任何新矩形也必须具有正面积，并且其角点的 $x$ 和 $y$ 坐标都必须在 $0 \ldots 200$ 的范围内。

输出格式

请输出：如果农夫约翰最多再刷两个互不相交的矩形，则谷仓中能够恰好被刷了 $K$ 层漆的最大面积。

3 2
1 1 4 4
3 3 7 6
2 2 8 7

26

提示

题目提供者：Nick Wu 和 Brian Dean

标签: USACO|2019|Gold

来源

USACO|2019|Gold