problem018.cpp

#include <cmath>
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <vector>

int maximumPathSum(std::vector<int> triangle)
{
 int height = sqrt(2 * triangle.size());
 for (int i = height - 2; i >= 0; --i) {
 int start = i * (i + 1) / 2;
 int end = start + i;
 for (int j = start; j <= end; ++j) {
 triangle[j] += std::max(triangle[j + i + 1], triangle[j + i + 2]);
 }
 }
 return triangle[0];
}

int main(int argc, char* argv[])
{
 if (argc < 2) {
 std::cout << "Usage: " << argv[0] << " <input>\n";
 return 0;
 }
 std::ifstream file(argv[1]);
 if (!file.is_open()) {
 std::cerr << "Cannot open " << argv[1] << '\n';
 return EXIT_FAILURE;
 }
 std::vector<int> triangle;
 int x;
 while (file >> x) {
 triangle.push_back(x);
 }
 std::cout << "Answer: " << maximumPathSum(triangle) << '\n';
 return 0;
}