Lazy Cows

Description

Farmer John regrets having applied high-grade fertilizer to his pastures since the grass now grows so quickly that his cows no longer need to move around when they graze. As a result, the cows have grown quite large and lazy... and winter is approaching.

Farmer John wants to build a set of barns to provide shelter for his immobile cows and believes that he needs to build his barns around the cows based on their current locations since they won't walk to a barn, no matter how close or comfortable.

## The cows' grazing pasture is represented by a 2 x B (1 <= B <= 15,000,000) array of cells, some of which contain a cow and some of which are empty. N (1 <= N <= 1000) cows occupy the cells in this pasture:

| | cow | | | | cow | cow | cow | cow |

| | cow | cow | cow | | | | | |

Ever the frugal agrarian, Farmer John would like to build a set of just K (1 <= K <= N) rectangular barns (oriented with walls parallel to the pasture's edges) whose total area covers the minimum possible number of cells. Each barn covers a rectangular group of cells in their entirety, and no two barns may overlap. Of course, the barns must cover all of the cells containing cows.

By way of example, in the picture above if K=2 then the optimal solution contains a 2x3 barn and a 1x4 barn and covers a total of 10 units of area.
Input

• Line 1: Three space-separated integers, N, K, and B.

• Lines 2..N+1: Two space-separated integers in the range (1,1) to (2,B) giving the coordinates of the cell containing each cow. No cell contains more than one cow.
Output

• Line 1: The minimum area required by the K barns in order to cover all of the cows.
Sample Input

8 2 9
1 2
1 6
1 7
1 8
1 9
2 2
2 3
2 4
Sample Output

10

1个回答

《MySQL 性能优化》之理解 MySQL 体系结构

Python+OpenCV实时图像处理

2020年一线城市程序员工资大调查

python爬取百部电影数据，我分析出了一个残酷的真相
2019年就这么匆匆过去了，就在前几天国家电影局发布了2019年中国电影市场数据，数据显示去年总票房为642.66亿元，同比增长5.4%；国产电影总票房411.75亿元，同比增长8.65%，市场占比 64.07%；城市院线观影人次17.27亿，同比增长0.64%。 看上去似乎是一片大好对不对？不过作为一名严谨求实的数据分析师，我从官方数据中看出了一点端倪：国产票房增幅都已经高达8.65%了，为什...

Windows可谓是大多数人的生产力工具，集娱乐办公于一体，虽然在程序员这个群体中都说苹果是信仰，但是大部分不都是从Windows过来的，而且现在依然有很多的程序员用Windows。 所以，今天我就把我私藏的Windows必装的软件分享给大家，如果有一个你没有用过甚至没有听过，那你就赚了????，这可都是提升你幸福感的高效率生产力工具哦！ 走起！???? NO、1 ScreenToGif 屏幕，摄像头和白板...

C语言荣获2019年度最佳编程语言

AI 没让人类失业，搞 AI 的人先失业了

2020年，冯唐49岁：我给20、30岁IT职场年轻人的建议

B站是个宝，谁用谁知道???? 作为一名大学生，你必须掌握的一项能力就是自学能力，很多看起来很牛X的人，你可以了解下，人家私底下一定是花大量的时间自学的，你可能会说，我也想学习啊，可是嘞，该学习啥嘞，不怕告诉你，互联网时代，最不缺的就是学习资源，最宝贵的是啥？ 你可能会说是时间，不，不是时间，而是你的注意力，懂了吧！ 那么，你说学习资源多，我咋不知道，那今天我就告诉你一个你必须知道的学习的地方，人称...

【蘑菇街技术部年会】程序员与女神共舞，鼻血再次没止住。（文末内推）

Java校招入职华为，半年后我跑路了

​两年前不知如何编写代码的我，现在是一名人工智能工程师

loonggg读完需要5分钟速读仅需 2 分钟大家好，我是你们的校长。我知道大家在家里都憋坏了，大家可能相对于封闭在家里“坐月子”，更希望能够早日上班。今天我带着大家换个思路来聊一个问题...

&lt;!DOCTYPE html&gt; &lt;html lang="en"&gt; &lt;head&gt; &lt;meta charset="UTF-8"&gt; &lt;meta name="viewport" content="width=device-width, initial-scale=1.0"&gt; &lt;meta http-equiv="X...
Spring框架|JdbcTemplate介绍

B 站上有哪些很好的学习资源?

24岁的程序员，还在未来迷茫，不知道能不能买得起房子

Java培训四个月能学会吗