Maja
레이팅 미적용의견: 0
2 \(s / 64\) \(MB / 110\) points
Maja the Bee pollinates flowers in a magical meadow. The meadow can be represented as a matrix
of \(N\) rows and \(M\) columns. In i {th}{ } row and j {th}{ } column there are \(C\) {i,j}{ } unpollinated flowers.
Maja will start her journey from her hive, which is located in the field in the \(A\) ^{th} row and \(B\) ^{th} column. In
several steps, she will visit some fields of the meadow and then return back to her hive. From each
field, Maja can move to one of its adjacent cells in one of the following directions: left, right, up or
down. Also, Maja will never leave the meadow. Each time Maja flies over some field, she pollinates
all unpollinated flowers growing on the field. But the meadow is magical! As soon as Maja leaves the
field ( \(i\) , \(j\) ), all the pollinated flowers will disappear and \(C\) _{i,j} new unpollinated flowers will grow on that
field.
Since Maja can't fly forever, she will get tired after \(K\) steps and gladly tell her adventurous story to her
bee friends. What is the maximal number of flowers Maja can pollinate if she makes exactly \(K\) steps
and ends her journey back at her hive?
In test cases worth 40% of total points, it will hold \(K\) ≤ 10 000.
2 \(s / 64\) \(MB / 110\) points
The first line contains positive integers \(N\) , \(M\) (2 ≤ \(N\) , \(M \le 100\)), \(A\) (1 ≤ \(A\) ≤ \(N\) ), \(B\) (1 ≤ \(B\) ≤ \(M\) ) and \(K\) (2 ≤
\(K\) ≤ 10 {9}{ }). \(K\) will always be even.
\(N\) lines follows, each containing \(M\) integers describing amount of flowers \(C\) {i,j} (0 ≤ \(C\) ≤10 {9}{ }) located in
i {th}{ } row and j {th}{ } column.
The field containing the hive won’t have any flowers on it.
Print the number from the task statement.
2 2 1 1 2
0 1
2 10
2 2 1 1 4
0 5
5 10
3 3 2 2 6
5 1 0
1 0 3
1 3 3output
output
2
20
15Clarification of sample tests:
In the first sample Maja starts from the field (1, 1), flyes to the field below, pollinates 2 flowers there, and returns
back to the hive.
In the second sample Maja start from the field (1, 1) and can pollinate flowers moving as follows: she moves
right, then down, then up and then left. Notice that Maja visited the field (1, 2) twice, each time pollinating 5
flowers on that field.
평가 및 의견
Maja
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Maja