問題一覧 > 通常問題

No.2227 King Kraken's Attack

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 79
作問者 : AngrySadEightAngrySadEight / テスター : akakimidoriakakimidori norikamenorikame
2 ProblemId : 8788 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-02-24 22:18:29

問題文

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。