問題一覧 > 通常問題

No.3292 World Map Distance

レベル : / AI推定難易度 : 1600 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 38
作問者 : kona0001 / テスター : tobisatis RyosukeFukatani koba-e964 ir5 drken1215
お気に入りにしたユーザー ProblemId : 12639 / 自分の提出
問題文最終更新日: 2025-10-03 01:32:58
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 485 (順位表) の他の問題:

Problem Statement

There is a grid with a width of $X$ cells and a height of $Y$ cells. The cell that is $x$-th from the left and $y$-th from the bottom of this grid is denoted by $(x,y)$.

There are $N$ destinations on the grid, located at $(x_i, y_i)$ respectively.

The distance between $2$ cells on this grid is defined as follows.

  • The minimum number of moves required to get from one cell to the other, where $1$ move takes you to a cell adjacent vertically or horizontally. However, the "right edge and left edge" and the "top edge and bottom edge" of the grid are connected, and you can move across them freely. More specifically, you can move between cell $(1,y)$ and cell $(X,y)$, and between cell $(x,1)$ and cell $(x,Y)$, in $1$ move.

Choose any $1$ cell on the grid freely and compute the sum of its distances to the $N$ destinations. What is the maximum possible value of this sum?

Constraints

  • $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$
  • All inputs are integers.

Input

The input is given from standard input in the following format.

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

Output

Output the maximum possible sum of the distances to the $N$ destinations when $1$ cell on the grid is chosen. Add a newline at the end.

Sample

Sample 1
Input
3 5 4
1 1
2 3
3 1
Output
9

For example, when cell $(5,3)$ is chosen:

  • The distance between cell $(5,3)$ and destination $1$ $(1,1)$ is $3$.
  • The distance between cell $(5,3)$ and destination $2$ $(2,3)$ is $2$.
  • The distance between cell $(5,3)$ and destination $3$ $(3,1)$ is $4$.

Thus, the sum of the distances is $9$. No cell can make the sum of the distances larger than this, so the answer is $9$.

Sample 2
Input
2 2 2
1 1
1 1
Output
4

Multiple destinations may be located at the same cell.

Sample 3
Input
4 9 9
1 1
1 9
9 1
9 9
Output
32

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