UVA12462 Rectangle

直方图是由在公共基线处对齐且相邻的一系列矩形组成的多边形。 给定一个由 *N* 个矩形构成的直方图, 每个矩形具有相等的宽度 为*1* , 但可以具有不同的高度 $h_i$ 和颜色 $c_i$ 请求出一个**面积最大**的子矩形, 满足: 1. 子矩形完全被包含在直方图中 2. 子矩形覆盖住的矩形的颜色集合需包含所有颜色 一个矩形被覆盖当且仅当该矩形与子矩形的交集面积为正数

多组数据 *T* ( $T\leq 50$) 每组数据第一行为 *N*, *C*. *C* 为颜色的总个数 ( $1\leq N \leq 10^5$, $1\leq C\leq \min(30, N)$ ), 第二行为 $h_i$ ($1\leq h_i\leq 10^9$), 第三行为 $c_i$ ($0\leq c_i\leq C-1$) 数据保证每个颜色都会出现至少一次 最后以两个零结束

对每组数据每行输出 符合题目要求的长方形的最大面积