#P3810. [Coci2015]Stanovi

[Coci2015]Stanovi

题目描述

把一个边长为 NN 和 MM 的矩形楼层划分成若干个小矩形。每个小矩形代表一套公寓,边长必须是正整数,边均与楼层边界平行。公寓内部互不重叠,且恰好覆盖整个楼层。每套公寓都必须有一段正长度的边在楼层外边界上,以便安装窗户。

若某套公寓的边长为 a,ba,b,它的面积偏差记为 (ab−K)2(ab-K)^2。求所有公寓的面积偏差之和的最小值。

输入格式

一行三个整数 N,M,KN,M,K,其中 1≤N,M≤3001\le N,M\le300,1≤K≤100001\le K\le10000。

输出格式

输出一个整数,表示最小总偏差。

样例

3 3 2
1

可划分成四套面积为 22 的公寓和一套面积为 11 的公寓。

2 2 2
0
2 3 4
2

COCI 2014/2015 第 4 轮组委会原题 PDF