サッカー (Soccer)
日本語
Language
Contribute a translation- Time limit
- 3000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
あなたは JOI リーグの名門サッカークラブに所属するマネージャーである．
クラブには \(N\) 人の選手が所属しており，選手には \(1\) から \(N\) までの番号が付けられている．選手たちは優勝を目指してグラウンドで日々練習をしている．グラウンドは縦 \(H\) メートル，横 \(W\) メートルの長方形の形状をしている．グラウンドの縦方向は南北方向に平行であり，横方向は東西方向に平行である．グラウンドの北西隅から南に \(i\) メートル，東に \(j\) メートル進んだ地点を地点 \((i, j)\) と呼ぶことにする．
練習が終わったあと，練習に使用したボールを片付けなければならない．片付け開始時点では，選手 \(i\) (\(1 \leqq i \leqq N\)) は地点 \((S_i, T_i)\) におり，ボールは選手 \(1\) のみが \(1\) つ所持している状態である．あなたは選手 \(N\) とともに地点 \((S_N, T_N)\) におり，あなたがボールを回収すること，すなわちボールを地点 \((S_N, T_N)\) に移動させることで片付けは完了する．片付けの過程であなたは移動できない．
あなたは選手たちに行動を指示することができる．選手たちは何か行動すると，その行動に応じて疲労度を蓄積してしまう．
以下の行動のうち，ボールを所持している選手は行動 (i), (ii), (iii) を，それ以外の選手は行動 (ii), (iv) を実行できる．
(i) 東西南北 \(4\) 方向のうち \(1\) 方向および正整数 \(p\) を指定する．その方向にボールを蹴り，ボールをちょうど \(p\) メートルだけ移動させる．蹴った選手はこの行動では移動せず，ボールを所持していない状態になる．疲労度は \(A \times p + B\) だけ増加する．
(ii) 東西南北 \(4\) 方向のうち \(1\) 方向を指定する．その方向に \(1\) メートル移動する．もしも移動する選手がボールを所持している場合，ボールと一緒に移動する．ボールの有無にかかわらず疲労度は \(C\) だけ増加する．
(iii) ボールをその場に置き，ボールを所持していない状態になる．疲労度は増加しない．
(iv) ボールを所持する．疲労度は増加しない．この操作はボールと同一地点にいる選手のみが，他に誰もボールを所持していない場合に限り実行可能である．
選手やボールがグラウンドの外に出たり，複数の選手が同一地点に存在したりしてもかまわないことに注意せよ．
練習後の選手にあまり多く疲労度を蓄積させないために，あなたは片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を求めることにした．
課題
グラウンドの大きさおよび選手たちの位置が与えられたとき，片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を求めるプログラムを作成せよ．
Input
標準入力から以下の入力を読み込め．
- \(1\) 行目には \(2\) 個の整数 \(H, W\) が空白を区切りとして書かれている．これらはグラウンドが縦に \(H\) メートル，横に \(W\) メートルの長方形の形状をしていることを表している．
- \(2\) 行目には疲労度の増加に関する \(3\) 個の整数 \(A, B, C\) が空白を区切りとして書かれている．
- \(3\) 行目には整数 \(N\) が書かれている．これは選手が \(N\) 人いることを表している．
- 続く \(N\) 行のうち \(i\) 行目 (\(1 \leqq i \leqq N\)) には \(2\) つの整数 \(S_i, T_i\) が空白を区切りとして書かれている．これらは片付け開始時点で選手 \(i\) が地点 \((S_i, T_i)\) にいることを表している．
Output
標準出力に，片付けによって生じる選手たちの疲労度の合計値として考えられる最小値を \(1\) 行で出力せよ．
Constraints
すべての入力データは以下の条件を満たす．
- \(1 \leqq H \leqq 500\)．
- \(1 \leqq W \leqq 500\)．
- \(0 \leqq A \leqq 1\,000\,000\,000\)．
- \(0 \leqq B \leqq 1\,000\,000\,000\)．
- \(0 \leqq C \leqq 1\,000\,000\,000\)．
- \(2 \leqq N \leqq 100\,000\)．
- \(0 \leqq S i \leqq H\) (\(1 \leqq i \leqq N\))．
- \(0 \leqq Ti \leqq W\) (\(1 \leqq i \leqq N\))．
- \((S_1, T_1) \neq (S_N, T_N)\)．
Subtasks
小課題 1 [5 点]
- \(N = 2\) を満たす．
小課題 2 [30 点]
以下の条件を満たす．
- \(N \leqq 1\,000\)．
- \(A = 0\)．
小課題 3 [65 点]
追加の制限はない．
Examples
6 5 1 3 6 3 1 1 0 4 6 5
26
入力例 \(1\) は，小課題 \(1\) および小課題 \(2\) の条件を満たしていない．この入力例では，グラウンドは下図の状態となっている．図において，白い丸は選手を，黒い丸はボールを表している．あなたは \((6, 5)\) にいる．
この場合，以下のように行動すればよい．
- 選手 \(1\) が所持しているボールを東に \(3\) メートル蹴る．疲労度は \(1 \times 3 + 3 = 6\) だけ上昇し，ボールは \((1, 4)\) に移動する．
- 選手 \(2\) が南に \(1\) メートル移動し，ボールを所持する．疲労度は \(6\) だけ上昇する．
- 選手 \(2\) が東に \(1\) メートル移動する．疲労度は \(6\) だけ上昇する．
- 選手 \(2\) が所持しているボールを南に \(5\) メートル蹴る．疲労度は \(1 \times 5 + 3 = 8\) だけ上昇し，ボールは \((6, 5)\) に移動する．
この場合，疲労度の合計値は \(6 + 6 + 6 + 8 = 26\) となり，これが最小値となる．
3 3 0 50 10 2 0 0 3 3
60
入力例 \(2\) は，小課題 \(1\) および小課題 \(2\) の条件を満たしている．入力例 \(2\) において，ボールを蹴る必要はない．
4 3 0 15 10 2 0 0 4 3
45
入力例 \(3\) は，小課題 \(1\) および小課題 \(2\) の条件を満たしている．
4 6 0 5 1000 6 3 1 4 6 3 0 3 0 4 0 0 4
2020
入力例 \(4\) は，小課題 \(1\) の条件を満たしておらず，小課題 \(2\) の条件を満たしている．同じ地点に複数の選手がいる場合が含まれることに注意せよ．
Notes
JOI 2017 · JCIOI · CC BY-SA 4.0
Tags
No tags yet