Adding up Triangles (UVa Live Archive Africa and the Middle East - Africa and Arab - 2008/2009 Alexandria - Egypt)

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4364

問題

中に数値の書かれたn列の三角形が与えられる。三角形の値とはその中に書かれている数値の和である。部分三角形の値で最大の値を求めよ。
n<=400

解法

てきとうに列の和を保持しておくなどしてO(n^3)で計算すれば良い。