問題一覧 > 通常問題

No.3292 World Map Distance

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 : kona0001 / テスター : tobisatis RyosukeFukatani koba-e964 ir5 drken1215
ProblemId : 12639 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-10-03 01:32:58

問題文

横 $X$ マス、縦 $Y$ マスのグリッドがあり、このグリッドの左から $x$ 番目、下から $y$ 番目のマスを $(x,y)$ と表記します。

グリッド上には $N$ 点の目的地があり、それぞれの場所は $(x_i, y_i)$にあります。

このグリッド上における $2$ つのマス間の距離を次のように定義します。

  • $1$ 回の移動で上下左右に隣接するマスのいずれかに移動できるときの、片方のマスからもう片方のマスに辿り着くために必要な最短移動回数。 ただし、グリッドの「右端と左端」および「上端と下端」は繋がっており、自由に移動できる。より具体的に、マス $(1,y)$ とマス $(X,y)$ 間 、マス $(x,1)$ とマス $(x,Y)$ 間は $1$ 回で移動できる。

グリッド上のマスを自由に $1$ つ選び、$N$ 個の目的地との距離の総和を求める時、この値は最大でいくつになるでしょうか?

制約

  • $1 \le N \le 2 \times 10^5$
  • $1 \le X,Y \le 10^9$
  • $1 \le x_i \le X$
  • $1 \le y_i \le Y$
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられます。

$N\ X\ Y$
$x_1\ y_1$
$x_2\ y_2$
$\vdots$
$x_N\ y_N$

出力

グリッド上のマスを $1$ つ選んだ時の、$N$ 個の目的地との距離の総和の最大値を出力してください。最後に改行してください。

サンプル

サンプル1
入力
3 5 4
1 1
2 3
3 1
出力
9

例えばマス $(5,3)$ を選ぶとき

  • マス $(5,3)$ と 目的地 $1$ $(1,1)$ との距離は $3$
  • マス $(5,3)$ と 目的地 $2$ $(2,3)$ との距離は $2$
  • マス $(5,3)$ と 目的地 $3$ $(3,1)$ との距離は $4$

となり、距離の総和は $9$ です。これよりも距離の総和を大きくできるマスは存在しないため、 $9$ が答えです。

サンプル2
入力
2 2 2
1 1
1 1
出力
4

複数の目的地が同じマスに存在することもあります。

サンプル3
入力
4 9 9
1 1
1 9
9 1
9 9
出力
32

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。