Luogu P1004 - Square access

As shown above, the image shows a N×NN \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 AA, move rightwards and downwards without backing, to the square of lower right corner BB. 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 AA to BB 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, NN and the distribution of the values of treasures, find the maximum revenue the thief can get.

How to submit:

The pastebin below has 1010 inputs. Each input has the format:

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

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

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

Then submit the sum of all the outputs.

Inputs are here

Luogu Problem Set


Problem Loading...

Note Loading...

Set Loading...