|
Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Question by Faruk Bulut.
Hexagon
In the figure below there is a hexagon in the figure whose side
length is 3. A route should start one of the nodes in the
uppermost row and ends to one of the nodes in the lowest row.
From a node, the route can continue only diagonally down to the
left or diagonally down to the right. When creating a route
through the honeycomb, you are allowed to make at most one swap
of two numbers on at most one horizontal row of the honeycomb.
(Swapping essentially means that in one chosen row you are
allowed to place the greatest number of that row to any position
on the same row.)
Question:
Write a program that calculates the highest sum of numbers
on any route using the ability of swapping two numbers on
a chosen row.
Restrictions:
- The numbers in the nodes are integers between 0 and 99.
- The side length of the honeycomb is an integer between 1 and 99.
Input specification:
The side length of the honeycomb is in the first
row of input. If the side length is n, the honeycomb
consists of 2n - 1 rows. Numbers in each row
are separated by spaces.
Output specification:
Show one integer: the max sum.
| Sample Input 1 |
Sample Input 2 |
3
1 2 3
3 2 2 1
4 2 8 0 3
5 3 1 2
3 1 4
|
2
53 14
27 2 31
85 30
|
| Sample Output 1 |
Sample Output 2 |
22
|
169
|
Для отправки решений необходимо выполнить вход.
|