問題一覧 > 通常問題

No.596 Mail Delivery

レベル : / AI推定難易度 : 2750 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 3
作問者 : 37zigen / テスター : はむこ
お気に入りにしたユーザー ProblemId : 1367 / 自分の提出
問題文最終更新日: 2020-01-10 16:52:46
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 177 (順位表) の他の問題:

Problem Statement

Houses and mailboxes are lined up on a number line.
Pieces of mail, each labeled with its destination house, have been posted in the mailboxes.
All pieces of mail must be collected from the mailboxes and delivered to their destination houses.
Find the minimum required travel distance.

The start and end points of the delivery may be chosen freely.
Also, any number of pieces of mail can be carried at once.

Input

$N$ $M$
$x_1$ $d_1$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_1}$
$x_2$ $d_2$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_2}$
$\vdots$
$x_M$ $d_M$
$y_1$ $y_2$ $y_3$ ⋯⋯ $y_{d_M}$

$1 \leq N \leq 7×10^6$
$1 \leq M \leq 5×10^5$
$0 \leq x_i < N$
$0 \leq y_i < N$
$1 \leq d_i ∧ \sum{d_i} \leq 10^6$

Houses and mailboxes are located at integer coordinates in [$0$,$N$). $M$ is the number of mailboxes.
$x_i$ is the position of the $i$-th mailbox.
$d_i$ is the number of pieces of mail in the $i$-th mailbox.
$y_j$ on the line following $x_i$ $d_i$ is the position of the destination house of the $j$-th letter in the $i$-th mailbox.

Note that the coordinates of a piece of mail's destination and of the mailbox it was posted in may be the same.

Output

Find the minimum travel distance required to deliver all pieces of mail to their destinations.

Sample

Sample 1
Input
6 1
0 1
1
Output
1

Sample 2
Input
9 4
0 3
2 7 6
6 2
8 5
1 4
2 7 0 1
4 2
1 6
Output
14

Sample 3
Input
10 5
5 1
1
9 2
0 4
6 3
8 7 2
1 4
2 7 0 1
4 2
1 6
Output
17

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