# Luogu P1004 - Square access

As shown above, the image shows a $N \times N$ square, and some of them have treasures. The number denotes the value of treasures.

A thief wants to get as many treasures as possible, in order not to be caught by police, he can only start from the square of the upper left corner $A$, move rightwards and downwards without backing, to the square of lower right corner $B$. Along the way on each trial, he can take away the treasure of the squares. Unfortunately, he only has two trials, that is, he will go from $A$ to $B$ twice. Notice that on the second chance, the treasures taken away on the first chance can't be taken again.

Given the size of the square, $N$ and the distribution of the values of treasures, find the maximum revenue the thief can get.

How to submit:

The pastebin below has $10$ inputs. Each input has the format:

• A number $N (1 \leq N \leq 50)$, the size of the square.

• $N \times N$ numbers, the distribution of the values of treasures.

You should output: A number $M$, the maximum revenue the thief can get.

Then submit the sum of all the outputs.

Luogu Problem Set

×