CSL的矩阵

发布时间: 2018年1月21日 17:53   最后更新: 2018年1月29日 10:29   时间限制: 3000ms   内存限制: 128M

CSL毕竟是上海全能王,他的魔方玩的炉火纯青,矩阵也不例外。现在CSL拿到了一个$n*m$的矩阵,行列均从1开始。每个位置的元素是由他的位置决定的,假设元素位于第$i$行,第$j$列

$$f(i,j) = \min \lbrace i,n-i+1,r \rbrace  \times \min \lbrace j,m-j+1,r \rbrace $$

现在CSL想要从这么多元素中取出$k$个元素,使他们的和最大。请问你最大的和是多少。

多组输入,每组输入三个数字,$n$,$m$,$r$,$k$,含义如题中所述。
$1 ≤ n, m ≤ 10^5$
$1 ≤ r ≤ min(n, m)$
$1 ≤ k ≤ min(n·m, 10^5)$

每组输入输出一个整数表示最大的和。

复制
3 3 2 3
8

basic algorithm

Weekly Training 2018.1.21