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.


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



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:

Comments (Search)

For test case #10, N = 20,001. Limits state 1 <= N <= 20,000

How can I optimize my code?
Can you solve the problem with python 3?

Your approach is needlessly complex.

Is it possible to have a negative output?

It is not possible for all of the lines to receive negative scores. You can also choose where to start and stop, so using this information we can deduce that if you have the correct solution, it cannot be negative.