/ Vijos / 题库 /

损坏的牛棚

损坏的牛棚

时间限制:1秒  内存限制:256M


【题目描述】

  FJ买了一个矩形的 \(n\) 行 \(m\) 列的牧场。不幸的是,他发现某些 1 x 1 的区域被损坏了,所以它不可能在把整个牧场建造成牛棚了。 FJ数了一下,发现有 \(p\) 个 1 x 1 的损坏区域。

  现请你帮助他找到不包含损坏区域的面积最大的矩形的牛棚。

【输入格式】

  第 \(1\) 行: 三个空格隔开的整数 \(n, m\)和 \(P\)。
  第 \(2..p+1\) 行: 每行包含两个空格隔开的整数:\(x y\),给出一个损坏区域的行号和列号。对同一个损坏区域可能有多次描述。

【输出格式】

  牛棚的最大可能面积

【输入输出样例】

 Input

3 4 2
1 3
2 1

 Output

6

【子任务】

  测试点1:\(n=5, m=6, p=5\)
  测试点2:\(n=10, m=10, p=10\)
  测试点3:\(n=20, m=15, p=17\)
  测试点4:\(n=50, m=50, p=100\)
  测试点5:\(n=98, m=100, p=1089\)
  测试点6:\(n=50, m=300, p=3000\)
  测试点7:\(n=1000, m=1000, p=5000\)
  测试点8:\(n=2000, m=1500, p=25000\)
  测试点9:\(n=3000, m=2500, p=30000\)
  测试点10:\(n=3000, m=3000, p=100000\)

【来源】

  Mr.he

信息

ID
2082
难度
(无)
分类
动态规划 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者