問題一覧 > 通常問題

No.2100 [Cherry Alpha C] Two-way Steps

レベル : / AI推定難易度 : 1050 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 96
作問者 : 👑 Kazun / テスター : butsurizuki sapphire__15
お気に入りにしたユーザー ProblemId : 5720 / 自分の提出
問題文最終更新日: 2022-10-14 21:00:17
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 364 (Do you know Cherry Contest?) (順位表) の他の問題:

Problem Statement

There are $N$ platforms. They are named platform $1$, platform $2$, $\cdots$, platform $N$, in this order. The height of platform $i~(1 \leq i \leq N)$ is $H_i$.

There are also $M$ staircases, and the $j~(1 \leq j \leq M)$-th staircase bidirectionally connects platform $X_j$ and platform $Y_j$ with a staircase of $\left|H_{X_j}-H_{Y_j} \right|$ steps. Note that the $2$ platforms connected by a staircase never have equal heights.

Using these staircases, one can move from one platform to another. Strictly speaking, a move from platform $a$ to platform $b$ using a staircase is as follows:

  • If $H_a < H_b$, move from platform $a$ to platform $b$ by going up $(H_b-H_a)$ steps.
  • If $H_a > H_b$, move from platform $a$ to platform $b$ by going down $(H_a-H_b)$ steps.
As mentioned above, $H_a=H_b$ cannot occur.

Now, there are Cherry-chan and Zelkova-kun. The situations, goals, and conditions of these 2 people are as follows.

  • Cherry-chan: She is initially on platform $1$. She wants to get to platform $N$ by moving through $0$ or more staircases. However, when moving from platform $a$ to platform $b$ using a staircase, $a \lt b$ must hold. That is, each move must increase the platform number.
  • Zelkova-kun: He is initially on platform $N$. He wants to get to platform $1$ by moving through $0$ or more staircases. However, when moving from platform $a$ to platform $b$ using a staircase, $a \gt b$ must hold. That is, each move must decrease the platform number.
  • Common to the 2 people: When moving between platforms using staircases, they cannot go up staircases 2 times in a row.

Answer the following question for each of Cherry-chan and Zelkova-kun.

  • Is it possible to achieve the goal by moving between platforms while satisfying the conditions? Also, since the $2$ people both love going up stairs, if the goal can be achieved, find the maximum total number of steps gone up during the movement (steps gone down are not counted).

Constraints

  • $2 \leq N \leq 10^5$
  • $1 \leq M \leq 1.5 \times 10^5$
  • $0 \leq H_i \leq 10^9 \quad (1 \leq i \leq N)$
  • $1 \leq X_j \lt Y_j \leq N \quad (1 \leq j \leq M)$
  • $H_{X_j} \neq H_{Y_j} \quad (1 \leq j \leq M)$
  • $j \neq k \Rightarrow (X_j, Y_j) \neq (X_k, Y_k) \quad (1 \leq j \leq M, 1 \leq k \leq M)$
  • All inputs are integers.

Input

$N$ $M$
$H_1$ $\cdots$ $H_N$
$X_1$ $Y_1$
$\vdots$
$X_M$ $Y_M$

Output

The output consists of $2$ lines.

  • On line $1$, for Cherry-chan, print -1 if it is impossible to move between platforms while satisfying the conditions; otherwise, print the maximum total number of steps gone up.
  • On line $2$, for Zelkova-kun, print -1 if it is impossible to move between platforms while satisfying the conditions; otherwise, print the maximum total number of steps gone up.

Do not forget the newline at the end.

Sample

Sample 1
Input
5 5
0 10 15 5 20
1 5
1 2
2 3
3 4
4 5
Output
20
10

Cherry-chan and Zelkova-kun can achieve their goals by moving as follows, and these moves maximize the total number of steps gone up.

  • Cherry-chan: platform $1$ $\to$ platform $5$ (going up $20$ steps)
  • Zelkova-kun: platform $5$ $\to$ platform $4$ $\to$ platform $3$ $\to$ platform $2$ $\to$ platform $1$ (going up $10$ steps)

Note that Cherry-chan cannot move as follows.

  • Cherry-chan ($\times$): platform $1$ $\to$ platform $2$ $\to$ platform $3$ $\to$ platform $4$ $\to$ platform $5$
This is because she goes up staircases $2$ times in a row in the move platform $1$ $\to$ platform $2$ $\to$ platform $3$.

Sample 2
Input
3 2
4 6 46
1 2
2 3
Output
-1
0

  • Cherry-chan: She cannot get to platform $N$ while satisfying the conditions. Thus, -1 must be printed.
  • Zelkova-kun: Note that steps gone down are not counted.

Sample 3
Input
8 10
31 41 59 26 53 58 97 93
1 8
2 7
3 5
1 4
5 8
4 5
2 5
6 7
4 7
3 7
Output
62
5
Sample 4
Input
4 1
1 2 3 4
2 3
Output
-1
-1

In the first place, platform $1$ and platform $N$ are not necessarily connected by staircases, even indirectly.

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