018.cpp

Go to the documentation of this file.

#include <iostream>
#include <fstream>
using namespace std;

const unsigned short rows=15;

class triangle 
{
        unsigned short x[rows][rows];
        unsigned label[rows][rows];
public:
        triangle()
        {
                unsigned short* p1 = &(x[0][0]);
                unsigned *p2 = &(label[0][0]);
                for(int i=0;i<rows*rows;i++,p1++,p2++)
                { 
                        *p1=0;
                        *p2=0;
                }
        }
        void push(unsigned short k)
        {
                static unsigned short row=0;
                static unsigned short col=0;
                x[row][col]=k;
                if(row==0)
                {
                        row++;
                        label[0][0]=k;//set label
                        return;
                }
                else if(row==col)
                {
                        row++;
                        col=0;
                        return;
                }
                else col++;
        }
        void label_row(unsigned short n)
        {
                for(int k=0;k<=n-1;k++)
                {
                        //evaluate label directly below
                        unsigned tmp_label = label[n-1][k]+x[n][k];
                        if(tmp_label > label[n][k])
                        label[n][k] = tmp_label;
                        //evalulate label at bottom right corner
                        label[n][k+1] = label[n-1][k]+x[n][k+1];
                }
        }
        //find the max sum
        unsigned maxN()
        { 
        unsigned m = label[rows-1][0];
                for(int k=1;k<rows;k++)
                if(m<label[rows-1][k])
                m = label[rows-1][k];
                return m;
        }
};
void import(triangle *N)
{
        ifstream input;
        input.open("018.txt");
        unsigned short x;
        for(unsigned k=1;k<=(rows+1)*rows/2;k++)
        {
                input >> x;
                N->push(x);
        }
}
int main()
{
        triangle N;
        import(&N);
        for(unsigned short r=1;r<rows;r++)
        N.label_row(r);
        cout << N.maxN() << endl;
        return 0;
}