問題一覧 > 通常問題

No.3597 Queen Score Attack 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 55
作問者 : 👑 AngrySadEight / テスター : gomaazarasi ぽえ
ProblemId : 13476 / yukicoder contest 506 裏・クイーンコンテスト (順位表) / 自分の提出
問題文最終更新日: 2026-07-24 21:53:09
yukicoder contest 506 裏・クイーンコンテストの他の問題:

問題文

縦 $H$ マス，横 $W$ マスのマス目があります．上から $i(1 \leq i \leq H)$ 番目，左から $j(1 \leq j \leq W)$ 番目のマスを，マス $(i, j)$ と表記します．

時刻 $0$ の時点で，マス $(sx, sy)$ に，クイーンのコマがあります．クイーンのコマは，マス目の範囲内のマスに自由に出入り可能ですが，範囲外のマスには出入りできません．

これから，時刻 $1, 2, \dots, N$ のそれぞれに，次に示す行動のいずれか $1$ つを選択して行うことができます．ただし，クイーンを移動させる際の時間は無視するものとします．

  • クイーンのコマが $1$ 回で移動できるマスを $1$ つ選び，クイーンのコマをそのマスに移動させる．
  • クイーンのコマを移動させない．

また，特定の時刻にクイーンのコマが特定のマスにある場合，スコアが得られます．具体的には，スコアを得られる条件は以下の通りです．

  • 時刻 $i + 0.5$ にクイーンのコマがマス $(x_i, y_i)$ にあった場合，スコア $c_i$ を得る．$(1 \leq i \leq N)$

適切にクイーンのコマを動かしたとき，得られるスコアの最大値を求めてください．

クイーンのコマの移動方法について（クリックで開く）

クイーンのコマは，$1$ 回の移動において，縦・横・斜めの方向に，通る経路のマスが全て出入り可能である限り自由なマス数進むことができます．ただし，今いるマスにとどまることを $1$ 回の移動とみなすことはできません．厳密には，マス $(i, j)$ にあるクイーンのコマは次のような移動が可能です．

  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j - l)$ はクイーンのコマが出入り可能なマスである．

制約

  • 入力は全て整数
  • $2 \leq H, W \leq 5 \times 10^5$
  • $1 \leq N \leq 5 \times 10^5$
  • $1 \leq sx \leq H$
  • $1 \leq sy \leq W$
  • $1 \leq x_i \leq H$
  • $1 \leq y_i \leq W$
  • $1 \leq c_i \leq 10^9$

入力

入力は以下の形式で標準入力から与えられる．

$H$ $W$ $sx$ $sy$ $N$
$x_1$ $y_1$ $c_1$
$x_2$ $y_2$ $c_2$
$\vdots$
$x_N$ $y_N$ $c_N$

出力

答えを出力せよ．

サンプル

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

時刻 $1$ にクイーンのコマをマス $(1, 3)$ に，時刻 $3$ にクイーンのコマをマス $(3, 3)$ に移動させれば，得られるスコアは $4 + 10 = 14$ となります．

これより大きいスコアを得ることはできないため，答えは $14$ となります．

サンプル2
入力
4 4 2 3 5
2 3 4
2 3 5
2 3 6
2 3 7
2 3 8
出力
30

クイーンのコマを $1$ 回も動かさないことで，得られるスコアは $4 + 5 + 6 + 7 + 8 = 30$ となります．

サンプル3
入力
4 4 1 1 10
1 2 324321814
2 4 721647114
4 1 453412415
4 3 939186981
3 1 121412531
2 2 781394161
2 4 531518965
1 1 353108590
4 4 731815057
3 2 247891365
出力
3761649393

答えは $32$ bit 整数に収まらないことがあることに注意してください．

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