National Olympiad in Informatics, China, 1997
Day 2, Problem 1 - Perfect Tour
In a tourist city, the streets are in the arrangement of a grid (see figure below). The streets that run east-west are known as landscape streets and the streets that run north-south are known as vacant streets. Landscape streets contain many popular attractions that are suitable for sightseeing tourists. Vacant streets do not contain any establishments worthwhile for tourists to visit. Due to the large number of tourists, landscape streets are designated to be one-way, and individuals may only travel from west to east (left to right on the diagram). However, one may travel in any direction they wish on vacant streets.
A tourist would like to tour the city. He has assigned a score to each landscape street section based on the quality of the sights around it. The score of each landscape is an integer from -100 to +100. The more the tourist likes the sights on that street, the higher the score that he assigns. It is not possible for all of the lines to receive negative scores.
| −50 | −47 | 36 | −30 | −23 |
| 17 | −19 | −34 | −13 | −8 |
| −42 | −3 | −43 | 34 | −45 |
The tourist can begin and end the tour at any two intersections in the city. He would like the overall score of the trip to be as large as possible. Please write a program to help him find an optimal tour route.
Input Format
The first line of input contains two space-separated integers M and N (1 ≤ M ≤ 100, 1 ≤ N ≤ 20000), representing the number of landscape streets and the number of vacant streets respectively. The following M lines each contain N−1 integers from -100 to 100, representing the landscape score that the tourist has assigned to the corresponding landscape street sections, in order from north to south, then from west to east.
Output Format
The output should contain one line - an integer representing the maximum total score obtainable from an optimal tour route.
Sample Input
3 6 -50 -47 36 -30 -23 17 -19 -34 -13 -8 -42 -3 -43 34 -45
Sample Output
84
Explanation
The best route is: start at the intersection of the west-most vacant street and the second north-most landscape street. Pass through the landscape streets with scores 17, −3, 36, and 34 for a total of 17 − 3 + 36 + 34 = 84.
All Submissions
Best Solutions
Point Value: 5
Time Limit: 1.00s
Memory Limit: 16M
Added: Apr 27, 2014
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)
Can you solve the problem with python 3?
Yes.