USACO 1.5 Number Triangles

Simple DP problem.

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

void getTriangle(ifstream &fin, vector<vector<int>> &triangle) {
  int total;
  fin >> total;

  int prev = 1;
  for (int i = 0; i < total; ++i) {
    vector<int> current;
    int cur = prev;
    while (cur--) {
      int item;
      fin >> item;
      current.emplace_back(item);
    }
    triangle.push_back(current);
    ++prev;
  }
}

int findMaxPath(vector<vector<int>> &triangle) {
  auto rows = (int)triangle.size();
  if (!rows) return 0;
  if (rows == 1) return triangle[0][0];

  vector<int> table(triangle[rows - 1]);

  for(int i = rows - 2; i >= 0; --i)
    for(int j = 0; j < triangle[i].size(); ++j)
      table[j] = std::max(table[j+1], table[j]) + triangle[i][j];

  return table[0];
}

int main() {
  ifstream fin("numtri.in");
  ofstream fout("numtri.out");

  vector<vector<int>> triangle;
  getTriangle(fin, triangle);

  fout << findMaxPath(triangle) << endl;

  return 0;
}