Number Triangles</h1> </center>

Consider the number triangle shown below. Write a program that calculates the highest sum of numbers that can be 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. </p>

          7          3   8        8   1   0      2   7   4   4    4   5   2   6   5 </pre>
 In the sample above, the route from 7 to 3 to 8 to 7 to 5 produces the highest sum: 30.  </p>

PROGRAM NAME: numtri</h3>

INPUT FORMAT</h3>  The first line contains R (1 <= R <= 1000), the number of rows. Each subsequent line contains the integers for that particular row of the triangle.  All the supplied integers are non-negative and no larger than 100.

SAMPLE INPUT (file numtri.in) </h3>
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 </pre>

OUTPUT FORMAT</h3>  A single line containing the largest sum using the traversal specified.

SAMPLE OUTPUT (file numtri.out)</h3>
30 
/*
ID: hippo he
LANG: C++
TASK: numtri
*/
#include
#include
#include
using namespace std;
int prev[2][1000][1000];
int R;
void input(){
    ifstream file("numtri.in");
    file>>R;
    memset(prev,-1,sizeof(prev));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j <= i; j++) {
            file>>prev[0][i][j];
        }
    }
}
int max(int i,int j){
    if(i==R-1)return prev[1][i][j]=prev[0][i][j];
    else if(-1!=prev[1][i][j])return prev[1][i][j];
    else{
        if(max(i+1,j)>max(i+1,j+1))
            return prev[1][i][j]=prev[0][i][j]+max(i+1,j);
        else return prev[1][i][j]=prev[0][i][j]+max(i+1,j+1);
    }
}
int main(int argc, const char *argv[])
{
    input();
    ofstream file("numtri.out");
    file<    return 0;
}

</pre>
</div>