問題一覧 > 通常問題

No.2227 King Kraken's Attack

レベル : / AI推定難易度 : 1400 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 86
作問者 : 👑 AngrySadEight / テスター : akakimidori norikame
お気に入りにしたユーザー ProblemId : 8788 / 自分の提出
問題文最終更新日: 2023-02-24 22:18:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 378 (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns, and the cell in row $i$ and column $j$ is denoted by cell $(i,j)$. Every cell in the grid contains $1$ monster.

A monster can be defeated by landing both of the 2 types of attacks, a horizontal attack and a vertical attack, on it at least $1$ time each. Landing only one of the attacks does not defeat it.

Now, as your means of attacking the monsters, you can throw each of the following 2 types of punches any number of times, $0$ or more. You cannot attack the monsters by any means other than these 2 types of punches.

  • Horizontal punch: Choose one integer $i$ satisfying $1 \leq i \leq H - L_{A} + 1$. Perform a horizontal attack on all monsters in all cells of the $L_A$ consecutive rows from row $i$ to row $i+L_{A}-1$. Then, choose any $K_{A}$ cells and perform both a horizontal attack and a vertical attack on all monsters in all the chosen cells.
  • Vertical punch: Choose one integer $j$ satisfying $1 \leq j \leq W - L_{B} + 1$. Perform a vertical attack on all monsters in all cells of the $L_B$ consecutive columns from column $j$ to column $j+L_{B}-1$. Then, choose any $K_{B}$ cells and perform both a horizontal attack and a vertical attack on all monsters in all the chosen cells.

Find the minimum number of punches required to defeat all monsters in the grid. That is, if you use horizontal punches $A$ times and vertical punches $B$ times to defeat all the monsters, find the minimum value of $A+B$.

Constraints

  • All inputs are integers.
  • $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$

Input

The input is given from standard input in the following format.

$H$ $W$ $L_A$ $L_B$ $K_A$ $K_B$

Output

Output the answer.

Sample

Sample 1
Input
2 2 1 1 1 2
Output
2

By attacking as follows, you can defeat all the monsters with $2$ punches.

  • Throw a horizontal punch and perform a horizontal attack on the monsters in row $2$. Then, perform both a vertical attack and a horizontal attack on the monster in cell $(1, 2)$.
  • Throw a vertical punch and perform a vertical attack on the monsters in column $1$. Then, perform both a vertical attack and a horizontal attack on the monsters in cell $(1, 1)$ and cell $(2,2)$.

It is impossible to defeat all the monsters with $1$ or fewer punches, so this is the minimum.

Sample 2
Input
3 3 1 1 0 0
Output
6

You cannot defeat all the monsters unless you throw vertical punches and horizontal punches $3$ times each.

Sample 3
Input
3 3 1 1 9 9
Output
1

You can defeat all the monsters just by throwing either a vertical punch or a horizontal punch $1$ time.

Sample 4
Input
1000 9982 4 4 35 3
Output
2742

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