[COCI 2021/2022 #6] Zemljište

Luogu

IDLGP8343

Time2000ms

Memory512MB

DifficultyP3

2021COCI（克罗地亚）

有一块地，大小为 $r \times s$，$\rm Matej$ 想买下它。这块地每个 $1\times1$ 的正方形都有不同的价格。设一片非空子矩阵价格总和为 $m$，则这片子矩阵的权值为 $|m-a|+|m-b|$，您需要找到最小权值的子矩阵。您只需要输出最小权值即可。 ## Input 第一行包含四个正整数 $r$, $s$ , $a$ 和 $b$ 。下面 $r$ 行，第 $i$ 行，有 $s$ 个正整数，第 $j$ 个数表示 $c_{i,j}$，表示价格。 ## Output 一行一个整数 $v$，表示最小非空子矩阵的权值。 [samples] ## Note ### 样例解释 2 ![](https://cdn.luogu.com.cn/upload/image_hosting/2mzt4qih.png) 如图，总价格是$1 + 1 = 2$，这块地的权值是 $|3−2| + |4−2| =3$。 ### 数据范围：对于 $14\%$ 的数据：$1\le r,s\le20$ 对于 $28\%$ 的数据：$1\le r,s\le100$ 对于 $100\%$ 的数据：$1\le r,s\le500$，$1\le a,b,c_{i,j}\le10^9$ ##### 本题分值与 [COCI 2021-2022#6](https://hsin.hr/coci/contest6_tasks.pdf) 分值相同，满分 $70$ 分

Samples

Input #1

2 2 10 10
1 3
4 1

Output #1

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[COCI 2021/2022 #6] Zemljište",
    "description": {
      "content": "有一块地，大小为 $r \\times s$，$\\rm Matej$ 想买下它。这块地每个 $1\\times1$ 的正方形都有不同的价格。   设一片非空子矩阵价格总和为 $m$，则这片子矩阵的权值为 $|m-a|+|m-b|$，您需要找到最小权值的子矩阵。   您只需要输出最小权值即可。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8343"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "有一块地，大小为 $r \\times s$，$\\rm Matej$ 想买下它。这块地每个 $1\\times1$ 的正方形都有不同的价格。  \n\n设一片非空子矩阵价格总和为 $m$，则这片子矩阵的权值为 $|m-a|+|m-b|$，您需要找到最小权值的子矩阵。  \n\n您只需要输出最小权值即可。\n\n## Input\n\n第一行包含四个正整数 $r$, $s$ , $a$ 和 $b$ 。\n\n下面 $r$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments