Zemljište
레이팅 미적용의견: 0
Matej is, as is well known, the biggest Croatian innovator and businessman. His company
is expanding, which is why he decided to buy a plot of land near Velika Gorica. The
available land is a rectang\(le-sh\)aped region consisting of \(r \times s\) square unit cells. Each
cell has its own price and it’s not possible to purchase only a part of a cell. Matej is
an experienced businessman and he knows that the key to success is not simply to buy
the biggest plot of land or the least expensive one. Instead, he should buy a plot of
land whose price is as close as possible to the magic numbers given to him by Milan the
psychic.
At the beginning of his career, Milan revealed to Matej two magic numbers \(a\) and \(b\) crucial for commercial
success. Therefore, Matej wishes to buy a (nonempty) rectangular plot of land so that the distance
between its price and the magic numbers is as small as possible. The distance between the price and a
single magic number is just the absolute value of their difference, and the distance between the price
and both of the magic numbers is the sum of these absolute differences. Help Matej and determine the
minimum possible distance between the price of the plot of land and the two magic numbers.
Subtask 1 (10 points): \(1 \le r\), \(s \le 20\)
Subtask 2 (20 points): \(1 \le r\), \(s \le 100\)
Subtask 3 (40 points): No additional constraints.
The first line contains positive integers \(r\), \(s\), \(a\) and \(b\) (\(1 \le r\), \(s \le 500\), \(1 \le a\), \(b \le 10^{9}\)) from the problem.
The \(i-th\) of the following \(r\) lines contains a sequence of \(s\) positive integers \(c@@RISE_MATH_BLOCK_0@@ij \le 10^{9}\)), the prices of
the individual cells, in order.
In the only line print the minimum possible distance between the price of the plot of land and the two
magic numbers.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | \(1 \le r\), \(s \le 20\) |
2 | 20점 | \(1 \le r\), \(s \le 100\) |
3 | 40점 | No additional constraints. |
2 2 10 10
1 3
4 123 2 3 4
1 9
1 1
8 133 4 5 3
1 1 1 1
9 6 7 6
8 1 9 72Clarification of the second example:
Matej can buy a plot of land consisting of two adjacent cells of cost 1. The total price is then 1 + 1 = 2,
and the distance between it and the magic numbers is |3 −2| + |4 −2| = 3.
평가 및 의견
Zemljište
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Zemljište