No.2227 King Kraken's Attack
タグ : / 解いたユーザー数 82
作問者 : 👑 AngrySadEight / テスター : akakimidori norikame
問題文
$H$ 行 $W$ 列のマス目があり,$i$ 行 $j$ 列目のマスをマス $(i,j)$ と表します.そのマス目内全てのマスに, $1$ 体ずつモンスターがいます.
モンスターは,横攻撃と縦攻撃の2種類の攻撃の両方をそれぞれ $1$ 回以上当てれば倒すことができます.片方の攻撃を当てるだけでは,倒すことはできません.
さて,これから,モンスターへの攻撃手段として次に示す2種類のパンチをそれぞれ $0$ 回以上の好きな回数繰り出すことができます.この2種類のパンチ以外の攻撃手段でモンスターに攻撃することはできません.
- 横パンチ:$1 \leq i \leq H - L_{A} + 1$ を満たす整数 $i$ をひとつ選ぶ.$i$ 行目から $i+L_{A}-1$ 行目までの連続する $L_A$ 行の全てのマスにいるモンスター全てに対して横攻撃を行う.その後,好きなマスを $K_{A}$ マス選び,選んだ全てのマスにいるモンスター全てに対して横攻撃と縦攻撃の両方を行う.
- 縦パンチ:$1 \leq j \leq W - L_{B} + 1$ を満たす整数 $j$ をひとつ選ぶ.$j$ 列目から $j+L_{B}-1$ 列目までの連続する $L_B$ 列の全てのマスにいるモンスター全てに対して縦攻撃を行う.その後,好きなマスを $K_{B}$ マス選び,選んだ全てのマスにいるモンスター全てに対して横攻撃と縦攻撃の両方を行う.
マス目内のモンスターを全て倒すために必要なパンチの回数の最小値を求めてください.すなわち,モンスターを全て倒すのに横パンチを $A$ 回,縦パンチを $B$ 回使ったとするとき,$A+B$ の最小値を求めてください.
制約
- 入力はすべて整数である.
- $1 \leq H,W \leq 10^6$
- $1 \leq L_A \leq H$
- $1 \leq L_B \leq W$
- $0 \leq K_A, K_B \leq HW$
入力
入力は以下の形式で標準入力から与えられる.
$H$ $W$ $L_A$ $L_B$ $K_A$ $K_B$
出力
答えを出力せよ.
サンプル
サンプル1
入力
2 2 1 1 1 2
出力
2
次のように攻撃することで,$2$ 回のパンチで全てのモンスターを倒すことができます.
- 横パンチを行い,$2$ 行目のモンスターに対して横攻撃を行う.その後,マス $(1, 2)$ のモンスターに縦攻撃と横攻撃の両方を行う.
- 縦パンチを行い,$1$ 列目のモンスターに対して縦攻撃を行う.その後,マス $(1, 1)$ とマス $(2,2)$ のモンスターに縦攻撃と横攻撃の両方を行う.
$1$ 回以下のパンチでは全てのモンスターを倒すことはできないため,これが最小回数です.
サンプル2
入力
3 3 1 1 0 0
出力
6
縦パンチ・横パンチをそれぞれ $3$ 回ずつ繰り出さないと,全てのモンスターを倒すことができません.
サンプル3
入力
3 3 1 1 9 9
出力
1
縦パンチか横パンチのどちらかを $1$ 回繰り出すだけで全てのモンスターを倒すことができます.
サンプル4
入力
1000 9982 4 4 35 3
出力
2742
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。