問題一覧 > 通常問題

No.2227 King Kraken's Attack

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

問題文

HHWW 列のマス目があり,iijj 列目のマスをマス (i,j)(i,j) と表します.そのマス目内全てのマスに, 11 体ずつモンスターがいます.

モンスターは,横攻撃縦攻撃の2種類の攻撃の両方をそれぞれ 11 回以上当てれば倒すことができます.片方の攻撃を当てるだけでは,倒すことはできません.

さて,これから,モンスターへの攻撃手段として次に示す2種類のパンチをそれぞれ 00 回以上の好きな回数繰り出すことができます.この2種類のパンチ以外の攻撃手段でモンスターに攻撃することはできません.

  • 横パンチ1iHLA+11 \leq i \leq H - L_{A} + 1 を満たす整数 ii をひとつ選ぶ.ii 行目から i+LA1i+L_{A}-1 行目までの連続する LAL_A 行の全てのマスにいるモンスター全てに対して横攻撃を行う.その後,好きなマスを KAK_{A} マス選び,選んだ全てのマスにいるモンスター全てに対して横攻撃と縦攻撃の両方を行う.
  • 縦パンチ1jWLB+11 \leq j \leq W - L_{B} + 1 を満たす整数 jj をひとつ選ぶ.jj 列目から j+LB1j+L_{B}-1 列目までの連続する LBL_B 列の全てのマスにいるモンスター全てに対して縦攻撃を行う.その後,好きなマスを KBK_{B} マス選び,選んだ全てのマスにいるモンスター全てに対して横攻撃と縦攻撃の両方を行う.

マス目内のモンスターを全て倒すために必要なパンチの回数の最小値を求めてください.すなわち,モンスターを全て倒すのに横パンチAA 回,縦パンチBB 回使ったとするとき,A+BA+B の最小値を求めてください.

制約

  • 入力はすべて整数である.
  • 1H,W1061 \leq H,W \leq 10^6
  • 1LAH1 \leq L_A \leq H
  • 1LBW1 \leq L_B \leq W
  • 0KA,KBHW0 \leq K_A, K_B \leq HW

入力

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

HH WW LAL_A LBL_B KAK_A KBK_B

出力

答えを出力せよ.

サンプル

サンプル1
入力
2 2 1 1 1 2
出力
2

次のように攻撃することで,22 回のパンチで全てのモンスターを倒すことができます.

  • 横パンチを行い,22 行目のモンスターに対して横攻撃を行う.その後,マス (1,2)(1, 2) のモンスターに縦攻撃と横攻撃の両方を行う.
  • 縦パンチを行い,11 列目のモンスターに対して縦攻撃を行う.その後,マス (1,1)(1, 1) とマス (2,2)(2,2) のモンスターに縦攻撃と横攻撃の両方を行う.

11 回以下のパンチでは全てのモンスターを倒すことはできないため,これが最小回数です.

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

縦パンチ・横パンチをそれぞれ 33 回ずつ繰り出さないと,全てのモンスターを倒すことができません.

サンプル3
入力
3 3 1 1 9 9
出力
1

縦パンチか横パンチのどちらかを 11 回繰り出すだけで全てのモンスターを倒すことができます.

サンプル4
入力
1000 9982 4 4 35 3
出力
2742

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