UOJ Logo Universal Online Judge

UOJ

#133. 【UR #9】电路手动分析

统计

在设计电路的过程中,常常要手动分析电路。

我们故事的主人公 —— 奸笑熊是一个参加了 NOI2015 结果遗憾退役的 OIer。

马上就要回班搞高考了,奸笑熊不免有点伤感。于是奸笑熊开始玩电路散散心。

奸笑熊的电路有 $n \times m$ 个节点,排成 $n$ 行 $m$ 列。任意两个相邻节点之间连着一条导线。如果两个节点 $(x_1, y_1), (x_2, y_2)$ 满足 $\lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert = 1$ 则称这两个节点相邻。

奸笑熊定义一个电路的复杂程度为最大的非负整数 $s$ 满足可以选出 $s$ 个节点使得任意两个被选中的节点间都有一根导线相连。

奸笑熊手里还有 $r$ 根导线,可以连在 $r$ 对节点之间。奸笑熊希望新加上不超过 $r$ 根导线后,电路的复杂程度最大。

请你帮奸笑熊手动分析他的电路,告诉他复杂程度最大是多少。

输入格式

共一行,包含三个整数 $n, m, r$。保证 $n, m \geq 1$,$r \geq 0$。

输出格式

共一行,包含一个整数表示答案。

C/C++ 输入输出 long long 时请用 %lld。C++ 可以直接使用 cin/cout 输入输出。

样例一

input

2 2 0

output

2

explanation

不能加导线。所以只能选择两个相邻的节点,复杂程度为 $2$。

样例二

input

2 3 3

output

4

限制与约定

测试点编号$n, m$ 的规模$r$ 的规模
1$n, m \leq 4$$r \leq 13$
2
3
4$n = 1, m \leq 10^9$$r \leq 10^{18}$
5
6$n, m \leq 1000$
7
8$n, m \leq 10^9$
9
10

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载