HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Contests > IMPC 2017 > problem:


5. 51129 - Hexagon

IMPC 2017

Start: May.27.2017 at 09:25:00 AM
Finish: May.27.2017 at 01:00:00 PM
The contest is finished!
• Contest scoreboard

Contest problems

• 1. 51125 - Filling an Array 3
• 2. 51126 - Dr. Fllanxha
• 3. 51127 - Maze solver
• 5. 51129 - Hexagon
• 6. 51130 - Permutation of Everything

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
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



Для отправки решений необходимо выполнить вход.

www.contester.ru