問題一覧 > 通常問題

No.1225 I hate I hate Matrix Construction

レベル : / AI推定難易度 : 900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 225
作問者 : tyawanmusi / テスター : nok0
お気に入りにしたユーザー ProblemId : 4833 / 自分の提出
問題文最終更新日: 2026-07-10 19:43:52
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 265 (順位表) の他の問題:

Original Inspiration

I hate Matrix Construction
It is an interesting problem.

Problem Statement

You are given an integer $N$ and arrays $S,T$ of length $N$.

Consider an $N \times N$ matrix $a$ satisfying the following conditions.

  • $a_{i,j}=0,1$
  • If $S_i = 0$, the bitwise OR of row $i$ is $0$
  • If $S_i = 1$, the bitwise OR of row $i$ is $1$
  • If $S_i = 2$, the bitwise AND of row $i$ is $1$
  • If $T_j = 0$, the bitwise OR of column $j$ is $0$
  • If $T_j = 1$, the bitwise OR of column $j$ is $1$
  • If $T_j = 2$, the bitwise AND of column $j$ is $1$

It is guaranteed that a matrix $a$ satisfying the conditions exists.

Find the minimum value of $\sum_{i=1}^{N} \sum_{j=1}^{N} a_{i,j}$.

Constraints

  • All inputs are integers
  • $1 \le N \le 500$
  • $0 \le S_i \le 2$
  • $0 \le T_i \le 2$
  • It is guaranteed that a matrix $a$ satisfying the conditions exists

Input

$N$
$S_1\ \ S_2\ \dots \ S_N$
$T_1\ \ T_2\ \dots \ T_N$

The $1$st line contains $N$.
The $2$nd line contains $S$, separated by spaces.
The $3$rd line contains $T$, separated by spaces.

Output

Output the answer on $1$ line.
End the output with a newline.

Sample

Sample 1
Input
3
1 1 0
1 0 1
Output
2

Examples of matrices satisfying the conditions include $\left(\begin{array}{ccc} 1 & 0 & 1 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array}\right)$, $\left(\begin{array}{ccc} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 0 \end{array}\right)$, and $\left(\begin{array}{ccc} 1 & 0 & 0 \\ 1 & 0 & 1 \\ 0 & 0 & 0 \end{array}\right)$.

Sample 2
Input
3
0 1 2
1 1 1
Output
4

Examples of matrices satisfying the conditions include $\left(\begin{array}{ccc} 0 & 0 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array}\right)$ and $\left(\begin{array}{ccc} 0 & 0 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \end{array}\right)$.

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