No.1603 Manhattan Social Distance
タグ : / 解いたユーザー数 169
作問者 : 👑
SPD_9X2
/ テスター :
FSM
penguinman
問題文
SPD君は、イベント運営の手伝いをしています。
イベント会場は $H \times W$ のサイズのグリッド(将棋盤のような格子)で表現されます。
今日のイベントには $N$ 人の参加者が来ることがわかっています。SPD君は、各参加者をグリッドのマス目に割り当てる仕事をします。
具体的には、各 $i\left(1 \le i \le N\right)$ 人目の参加者に関して、 $1 \le x_i \le H , 1 \le y_i \le W$ を満たす整数座標 $\left(x_i,y_i\right)$ を選び、 $x_i$ 行目・$y_i$ 列目の両方に属すマス目に参加者を割り当てます。
一つのマス目に複数人を割り当てても構いません。
ソーシャルディスタンスを保った運営をするように指示された自称最適化問題の天才であるSPD君は、以下の方針で参加者を配置することにしました。
- 全ての人のペアに関してのマンハッタン距離の総和を最大化するように参加者を配置する。
参加者 $i$ と $j$ の間のマンハッタン距離は、 $|x_i - x_j| + |y_i - y_j|$ と定義されます。
適切に各参加者の位置を決めたとき、全ての人のペアに関してのマンハッタン距離の総和、すなわち $\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |x_i - x_j| + |y_i - y_j|$ の値として考えられる最大値を求めてください。
入力
$N\ H\ W$
- 入力は全て整数
- $2 \le N \le 10^8$
- $1 \le H,W \le 10^2$
出力
答えを $1$ 行に出力してください。
最後に改行してください。
サンプル
サンプル1
入力
3 2 2
出力
4
$\left(1,1\right) , \left(1,2\right) , \left(2,2\right)$ に $1$ 人ずつ入れることで達成できます。
サンプル2
入力
100 1 1
出力
0
全員を $1$ マスに詰め込むしかありません。
サンプル3
入力
100000000 100 100
出力
495000000000000000
答えは $32$ bit整数に収まらないことがあることに注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。