No.3430 Flip the Grid
問題文最終更新日: 2026-01-12 11:32:14
English (AI translation)
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 YNUCPC Contest 2
(順位表)
の他の問題:
Problem Statement
There is a grid with $H$ rows and $W$ columns, and each cell has $A_{i,j}$ written on it. $A_{i,j}$ is either $0$ or $1$.
Consider the following operation.
- Choose a $2\times2$ subgrid and flip the $01$ values of its $4$ cells.
Formally, choose integers $i,j \ (1 \leq i \leq H-1, 1 \leq j \leq W-1)$, and for each of $A_{i,j},A_{i,j+1},A_{i+1,j},A_{i+1,j+1}$, replace it with $1$ if it is $0$, and with $0$ if it is $1$.
Find the minimum possible sum of all numbers written on the grid after performing this operation $0$ or more times.
Input
- $2 \leq H,W\leq 2000$
- $A_{i,j} \in \lbrace0, 1\rbrace$
- All input values are integers.
The input is given from Standard Input in the following format.
$H$ $W$
$A_{1,1}$ $A_{1,2}$ $\dots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\dots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\dots$ $A_{H,W}$
Output
Find the minimum possible sum of all numbers written on the grid after performing the operation $0$ or more times.
Print a newline at the end.
Sample
Sample 1
Input
2 3 0 1 1 1 1 1
Output
1
By flipping the $4$ cells $A_{12}, A_{13}, A_{22}, A_{23}$, the sum of the numbers on the grid becomes $1$.
The sum cannot be made any smaller.
Sample 2
Input
3 3 1 1 1 1 1 1 1 1 1
Output
3
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
まみめ
kidodesu