問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 82
作問者 : 👑 KazunKazun / テスター : sapphire__15sapphire__15 butsurizukibutsurizuki
0 ProblemId : 5720 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-10-14 21:00:17

問題文

$N$ 個の足場がある. これらはそれぞれ足場 $1$, 足場 $2$, $\cdots$, 足場 $N$ の順に名付けられている. 足場 $i~(1 \leq i \leq N)$ の高さは $H_i$ である.

また, $M$ 個の階段があり, $j~(1 \leq j \leq M)$ 番目の階段は足場 $X_j$ と足場 $Y_j$ を $\left|H_{X_j}-H_{Y_j} \right|$ 段の階段で双方向に繋いでいる. なお, 階段で繋いでいる $2$ つの足場の高さが等しいことはない.

これらの階段を用いてある足場から別の足場へ移動することができる. 厳密には, 階段を用いて足場 $a$ から足場 $b$ へ移動するような移動について,

  • $H_a < H_b$ ならば, $(H_b-H_a)$ 段の階段を上って足場 $a$ から足場 $b$ へ移動する.
  • $H_a > H_b$ ならば, $(H_a-H_b)$ 段の階段を下って足場 $a$ から足場 $b$ へ移動する.
ということになる. なお, $H_a=H_b$ となることは前述した通り, 起こり得ない.

今, チェリーちゃんとゼルコバ君がいる. この2人の状況と達成したい目標, 条件は以下の通りである.

  • チェリーちゃん: 最初, 足場 $1$ にいる. $0$ 個以上の階段を用いて移動することによって, 足場 $N$ へ移動したい. ただし, 階段を用いて足場 $a$ から足場 $b$ へ移動する場合, $a \lt b$ を満たしていなければならない. つまり, 足場の番号が増加するような移動でなければならない.
  • ゼルコバ君: 最初, 足場 $N$ にいる. $0$ 個以上の階段を用いて移動することによって, 足場 $1$ へ移動したい. ただし, 階段を用いて足場 $a$ から足場 $b$ へ移動する場合, $a \gt b$ を満たしていなければならない. つまり, 足場の番号が減少するような移動でなければならない.
  • 2人共通: 階段を用いた足場の移動において, 2回連続で階段を上るような移動はできない.

チェリーちゃんとゼルコバ君それぞれについて以下の問に答えよ.

  • 条件を満たしながら足場を移動して目標を達成できるか? また, $2$ 人とも階段を上ることが大好きなため, 目標を達成できるならば移動における上る段数 (下る段数についてはカウントしない) の総和の 最大値 を求めよ.

制約

  • $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)$
  • 入力は全て整数である.

入力

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

出力

出力は $2$ 行からなる.

  • $1$ 行目にはチェリーちゃんについて, 条件を満たしながら足場を移動することが不可能な場合, -1 と出力し, 可能な場合, 上る段数の総和の最大値を出力せよ.
  • $2$ 行目にはゼルコバ君について, 条件を満たしながら足場を移動することが不可能な場合, -1 と出力し, 可能な場合, 上る段数の総和の最大値を出力せよ.

最後に改行を忘れないこと.

サンプル

サンプル1
入力
5 5
0 10 15 5 20
1 5
1 2
2 3
3 4
4 5
出力
20
10

チェリーちゃんとゼルコバ君はそれぞれ次のように移動することによって, 条件を達成でき, しかもこれらが上る段数の総和を最大にする.

  • チェリーちゃん: 足場 $1$ $\to$ 足場 $5$ ( $20$ 段上る)
  • ゼルコバ君: 足場 $5$ $\to$ 足場 $4$ $\to$ 足場 $3$ $\to$ 足場 $2$ $\to$ 足場 $1$ ( $10$ 段上る)

なお, チェリーちゃんについて次のように移動することはできない.

  • チェリーちゃん ($\times$): 足場 $1$ $\to$ 足場 $2$ $\to$ 足場 $3$ $\to$ 足場 $4$ $\to$ 足場 $5$
これは, 足場 $1$ $\to$ 足場 $2$ $\to$ 足場 $3$ の移動において $2$ 回連続で階段を上っているからである.

サンプル2
入力
3 2
4 6 46
1 2
2 3
出力
-1
0

  • チェリーちゃん: 条件を満たすように足場 $N$ へ移動することはできない. よって, -1 を出力しなければいけない.
  • ゼルコバ君: 階段を下る場合, その段数はカウントしないことに注意せよ.

サンプル3
入力
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
出力
62
5
サンプル4
入力
4 1
1 2 3 4
2 3
出力
-1
-1

そもそも足場 $1$ と足場 $N$ が階段によって間接的にも繋がっているとは限らない.

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