#PU923. USACO 2019 February Contest, Gold — Problem 3. Painting the Barn

    ID: 1394 传统题 文件IO:paintbarn 2000ms 256MiB 尝试: 0 已通过: 0 难度: 提高+/省选- 上传者: 标签>USACO赛事:feb19来源:usaco.orgscoring:equal_test_cases贪心

USACO 2019 February Contest, Gold — Problem 3. Painting the Barn

USACO 2019 February Contest, Gold — Problem 3. Painting the Barn

题目描述

Farmer John is not good at multitasking. He gets distracted often, making it hard to complete long projects. Currently, he is trying to paint one side of his barn, but he keeps painting small rectangular areas and then getting sidetracked by the needs of tending to his cows, leaving some parts of the barn painted with more coats of paint than others. We can describe the side of the barn as a 2D xx-yy plane, on which Farmer John paints NN rectangles, each with sides parallel to the coordinate axes, each described by the coordinates of its lower-left and upper-right corner points. Farmer John wants to apply several coats of paint to the barn so it doesn't need to be repainted again in the immediate future. However, he doesn't want to waste time applying an excessive number of coats of paint. It turns out that KK coats of paint is the optimal amount. However, looking at the amount of area covered by KK coats of paint, he is not very happy. He is willing to paint up to two additional rectangles to try and increase this area, as long as these two rectangles are disjoint (not sharing any positive amount of area in common). Note that he can also decide to paint zero new rectangles or just one new rectangle if this ends up being the best thing to do.

输入格式

The first line of input contains NN and KK (1≤K,N≤1051 \leq K, N \leq 10^5). Each of the remaining NN lines contains four integers x1,y1,x2,y2x_1, y_1, x_2, y_2 describing a rectangular region being painted, with lower-left corner (x1,y1)(x_1, y_1) and upper-right corner (x2,y2)(x_2, y_2). All xx and yy values are in the range 0…2000 \ldots 200, and all rectangles have positive area. Like the rectangles he already painted, any new rectangles that Farmer John paints must have positive area, and their corner points must have xx and yy coordinates in the range 0…2000 \ldots 200.

输出格式

Please output the maximum area of the barn that could be covered by exactly KK coats of paint, if Farmer John paints up to two additional disjoint rectangles.

数据范围

(见题面原文)

样例

样例 1

3 2
1 1 4 4
3 3 7 6
2 2 8 7
26
Problem credits: Nick Wu and Brian Dean