E - Max Vector

Contest Duration: 2024-04-21(Sun) 12:00 - 2024-04-21(Sun) 14:00 (local time) (120 minutes) Back to Home

E - Max Vector Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $800$ 点

問題文

長さ $N$ の正整数列 $X=(X_1,X_2,\dots,X_N),Y=(Y_1,Y_2,\dots,Y_N)$ が与えられます。

また、長さ $N$ の正整数列が $M$ 個与えられます。 $i$ 個目の正整数列は $A_i = (A_{i,1},A_{i,2},\dots,A_{i,N})$ です。

あなたは $i = 1,2,\dots,M$ の順に以下の操作のうちどちらかを行います。どちらを選ぶかは各 $i$ に対して独立に決めることが出来ます。

$1 \le j \le N$ を満たす全ての整数 $j$ に対して $X_j$ を $\max(X_j,A_{i,j})$ に置き換える。
$1 \le j \le N$ を満たす全ての整数 $j$ に対して $Y_j$ を $\max(Y_j,A_{i,j})$ に置き換える。

操作終了時の $\sum_{j=1}^{N} (X_j + Y_j)$ の最小値を求めてください。

制約

$1 \le N \le 10$
$1 \le M \le 500$
$1 \le X_j,Y_j,A_{i,j} \le 500$

入力

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

 $N$   $M$ 
 $X_1$   $X_2$   $\dots$   $X_N$ 
 $Y_1$   $Y_2$   $\dots$   $Y_N$ 
 $A_{1,1}$   $A_{1,2}$   $\dots$   $A_{1,N}$ 
 $A_{2,1}$   $A_{2,2}$   $\dots$   $A_{2,N}$ 
 $\vdots$ 
 $A_{M,1}$   $A_{M,2}$   $\dots$   $A_{M,N}$

出力

答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

最適な操作列の一例として、以下のようなものがあります。

$X_j$ を $\max(X_j,A_{1,j})$ に置き換える。 $X=(4,5,2)$ となる。
$Y_j$ を $\max(Y_j,A_{2,j})$ に置き換える。 $Y=(3,2,5)$ となる。

このように操作をすると、 $\sum_{j=1}^{N} (X_j + Y_j) = 21$ が達成できます。

入力例 2Copy

Copy

出力例 2Copy

Copy

入力例 3Copy

Copy

5 12
330 68 248 387 491
295 366 376 262 192
280 121 17 168 455
288 179 210 378 490
150 275 165 264 287
66 331 207 282 367
303 215 456 214 18
227 326 103 443 427
395 57 107 350 227
318 231 146 2 116
57 325 124 383 260
147 319 23 177 445
254 198 32 85 56
68 177 356 41 471

出力例 3Copy

Copy

Score: $800$ points

Problem Statement

You are given two length- $N$ sequences of positive integers: $X=(X_1,X_2,\dots,X_N)$ and $Y=(Y_1,Y_2,\dots,Y_N)$ .

Additionally, you are given $M$ length- $N$ sequences of positive integers. The $i$ -th sequence is $A_i = (A_{i,1},A_{i,2},\dots,A_{i,N})$ .

For each $i = 1,2,\dots,M$ , you must perform one of the following operations. You can independently choose which operation to perform for each $i$ .

Replace $X_j$ with $\max(X_j,A_{i,j})$ for all integers $j$ such that $1 \le j \le N$ .
Replace $Y_j$ with $\max(Y_j,A_{i,j})$ for all integers $j$ such that $1 \le j \le N$ .

Find the minimum possible value of $\sum_{j=1}^{N} (X_j + Y_j)$ after all operations.

Constraints

$1 \le N \le 10$
$1 \le M \le 500$
$1 \le X_j, Y_j, A_{i,j} \le 500$

Input

The input is given from Standard Input in the following format:

 $N$   $M$ 
 $X_1$   $X_2$   $\dots$   $X_N$ 
 $Y_1$   $Y_2$   $\dots$   $Y_N$ 
 $A_{1,1}$   $A_{1,2}$   $\dots$   $A_{1,N}$ 
 $A_{2,1}$   $A_{2,2}$   $\dots$   $A_{2,N}$ 
 $\vdots$ 
 $A_{M,1}$   $A_{M,2}$   $\dots$   $A_{M,N}$

Output

Print the answer.

Sample Input 1Copy

Copy

Sample Output 1Copy

Copy

One optimal sequence of operations is as follows:

Replace $X_j$ with $\max(X_j,A_{1,j})$ , making $X = (4,5,2)$ .
Replace $Y_j$ with $\max(Y_j,A_{2,j})$ , making $Y = (3,2,5)$ .

This sequence of operations achieves $\sum_{j=1}^{N} (X_j + Y_j) = 21$ .

Sample Input 2Copy

Copy

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

5 12
330 68 248 387 491
295 366 376 262 192
280 121 17 168 455
288 179 210 378 490
150 275 165 264 287
66 331 207 282 367
303 215 456 214 18
227 326 103 443 427
395 57 107 350 227
318 231 146 2 116
57 325 124 383 260
147 319 23 177 445
254 198 32 85 56
68 177 356 41 471

Sample Output 3Copy

Copy