Colorful Cookie

基本方針

$W$ の制約が小さいので、長方形領域の横の長さを $1$ から $W$ まで全探索することを考えます。

長方形領域の横の長さを $w$ で固定した場合、長方形領域の縦の長さは $\left\lfloor \frac{H}{w} \right\rfloor$ とするのが最適となります。

縦方向の探索には、要素を $1$ 個ずつ伸ばしていく方法や、累積和を使うなどして高速化すれば AC することができます。

実装例(C++)

余談

初期の案では制約が $1 \leq H,W \leq 2000$ でしたが、自分の力では解けませんでした。