IOI '94 - Haninge, Sweden

The Triangle

            7
          3   8
        8   1   0
      2   7   4   4
    4   5   2   6   5   (Figure 1)

Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

• Each step can go either diagonally down to the left or diagonally down to the right.
• The number of rows in the triangle is > 1 but ≤ 100.
• The numbers in the triangle, all integers, are between 0 and 99 inclusive.

Input Format

The first line of input contains the integer n, the number of lines in the triangle. The remaining n lines will contain the values of the triangle.

Output Format

The output should contain one integer, the highest possible sum.

Sample Input

5
7
3 8
8 1 0 
2 7 4 4
4 5 2 6 5

Sample Output

30

All Submissions
Best Solutions

Point Value: 7
Time Limit: 2.00s
Memory Limit: 10.140625M
Added: Dec 25, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

My code works perfectly fine, but I get RE (status=1) for every single test case. Is there something wrong with the compiler?

As mentioned in another thread, this probably isn't solvable in Python with the current judge setup. The interpreter seems to eat too much memory.*

I'm fairly sure your algorithm is fine, though.

*If I'm incorrect on this point I'm sure someone will correct me.

After some testing...
The ratio of rows to memory was exponential.
10 rows took around 5MB
15 rows took around 15MB
while 20 took around 280MB

Most likely you are exceeding the 8MB memory limit. That's a limitation of solving problems in Python, so it would be a good reason to switch to C++ (at least for IOI problems).

I don't think that's the case, as even trying to take in input results in a return error. Also, submissions that worked previously are also failing x.x

Your Python solution on the Best Solutions page is already very close to the memory limit. The judge has probably changed since almost a year ago. There's also the chance that the memory limiter is broken.

but its not even possible that the small test cases are anywhere near the memory limit. If that was the case, most other problems would be unsolvable in Python.

Am I missing something in the problem description ? I see a way to get 35; Start at 7 - > 8 - > 8 - > 7 - > 5.  

Read the problem statement carefully. The diagram at the top is the real representation of the triangle. [quote]Each step can go either diagonally down to the left or diagonally down to the right.[/quote] According to that, you cannot move from the 8 in row 2 to the 8 in row 3 (the only valid moves from the 8 in row 2 is to the 1 or 0 in row 3). Don't be tricked by the input format, which is simply the triangle without the formatting.

Oops , my mistake. Thanks for the speedy response!