시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 55 | 17 | 15 | 28.302% |
Lord Pooty has a $n$ by $m$ board of integers $A$ and would like to draw an L. However, he would like to maximise the sum of integers on the tiles covered by L. The L can be rotated in all 4 possible orientations such that the sides are parallel to the board. Each side of the L may not necessarily be drawn (a straight line is possible). Some examples of valid Ls are shown below:
Formally, you want to choose $3$ points, $(x_1, y_1)$, $(x_2, y_1)$ and $(x_1, y_2)$ (which may not necessarily be distinct) on the board $A$ such that
$$V = \sum_{i = \min{(x_1, x_2)}}^{\max{(x_1, x_2)}}{A_{i,y_1}} + \sum_{j = \min{(y_1, y_2)}}^{\max{(y_1, y_2)}}{A_{x_1,j}} - A_{x_1, y_1} $$
is maximised.
Your program must read from standard input.
The input starts with a line with two integers $n$ and $m$ where $n$ and $m$ are height and width of the board. This is followed by $n$ lines of $m$ integers, representing the board.
Your program must print to standard output.
The output should contain a single integer on a single line, the maximum $V$ possible.
번호 | 배점 | 제한 |
---|---|---|
1 | 5 | $1 ≤ n, m ≤ 2$ |
2 | 10 | $n = 1$ |
3 | 15 | $1 ≤ n, m ≤ 100$ |
4 | 15 | $1 ≤ n, m ≤ 300$ |
5 | 25 | $0 ≤ A_{i,j} ≤ 10^9$ for $1 ≤ i ≤ n$ and $1 ≤ j ≤ m$ |
6 | 30 | No additional restrictions |
2 2 8 1 3 4
15
In this example, you choose 8, 3, 4 to form an L.
This testcase is valid for subtasks 1, 3, 4, 5 and 6.
1 8 -2 -1 8 -2 9 0 -2 1
15
You draw a line covering 8, -2 and 9.
This testcase is valid for subtasks 2, 3, 4, and 6.
Olympiad > National Olympiad in Informatics (Singapore) > Qualification > NOI 2022 Qualification 1번