No.1603 Manhattan Social Distance
タグ : / 解いたユーザー数 177
作問者 :
SPD_9X2
/ テスター :
FSM
penguinman
Problem Statement
SPD-kun is helping to run an event.
The event venue is represented by a grid of size $H \times W$ (a lattice like a shogi board).
It is known that $N$ participants will come to today's event. SPD-kun's job is to assign each participant to a cell of the grid.
Specifically, for each $i\left(1 \le i \le N\right)$-th participant, he chooses integer coordinates $\left(x_i,y_i\right)$ satisfying $1 \le x_i \le H , 1 \le y_i \le W$, and assigns the participant to the cell belonging to both row $x_i$ and column $y_i$.
Multiple people may be assigned to a single cell.
SPD-kun, a self-proclaimed genius of optimization problems who has been instructed to run the event while maintaining social distance, has decided to place the participants according to the following policy.
- Place the participants so as to maximize the sum of the Manhattan distances over all pairs of people.
The Manhattan distance between participants $i$ and $j$ is defined as $|x_i - x_j| + |y_i - y_j|$.
When the position of each participant is determined appropriately, find the maximum possible value of the sum of the Manhattan distances over all pairs of people, that is, the value of $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |x_i - x_j| + |y_i - y_j|$.
Input
$N\ H\ W$
- All inputs are integers.
- $2 \le N \le 10^8$
- $1 \le H,W \le 10^2$
Output
Output the answer on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
3 2 2
Output
4
This can be achieved by placing $1$ person each in $\left(1,1\right) , \left(1,2\right) , \left(2,2\right)$.
Sample 2
Input
100 1 1
Output
0
There is no choice but to pack everyone into $1$ cell.
Sample 3
Input
100000000 100 100
Output
495000000000000000
Note that the answer may not fit in a $32$ bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。