Contest Duration: - (local time) (100 minutes) Back to Home

## E - Bomber Editorial by evima

When a bomb is placed to $$(A, B)$$, then the targets to destroy on the $$A$$-th or the $$B$$-th column can be destroyed. Therefore, let $$R_A$$ be the number of bombs in the $$A$$-th row, and $$C_B$$ be the number of bombs in the $$B$$-th column, then the number of bombs that will explode will be about $$R_A + C_B$$.

Since only $$R_A$$ is dependent on $$A$$ and only $$C_B$$ is dependent on $$B$$, it may seem that $$A$$ and $$B$$ can be determined independently, but the problem is that the number of bombs that explodes is not always $$R_A + C_B$$.

If a target to destroy exists on the coordinates $$(A, B)$$, $$1$$ is added to both $$R_A$$ and $$C_B$$, but there is only one target to destroy, so the actual number of targets to destroy will be $$R_A + C_B - 1$$. Therefore, after finding the maximum value for $$A$$ and $$B$$ independently, it has to be checked whether there exists a pair $$(A, B)$$ such that both $$R_A$$ and $$C_B$$ is maximum and there is not a target to destroy on the coordinates $$(A, B)$$. While the number of $$(A, B)$$ may be very large, there are at most $$M$$ squares that targets to destroy exist, so the number of searches can be kept down to no more than $$M$$ times, which is small enough to do brute-force search.

If such pair exists, then the answer is $$\max(R) + \max(C)$$, otherwise the answer is $$\max(R) + \max(C) - 1$$.

Sample Code(TODO)

posted:
last update: