Problem SUMTRIAN Problem - CodeChef
I got wrong answer
result, but I tested with many inputs and the answer was always correct. Could anyone give me a hint where I missed? Thanks in advance. Here is my solution, I used DP:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <cassert>
#include <bitset>
#include <fstream>
#include <iomanip>
#include <set>
#include <stack>
using namespace std;
void trim_left(string& s) {
int i = 0;
while (s[i] == ' ') {
i++;
}
s = s.substr(i);
}
void trim_right(string& s) {
int i = s.length() - 1;
while (s[i] == ' ') {
i--;
}
s = s.substr(0, i + 1);
}
vector<int> triangle_tokenize(const string& line, int fix_size) {
vector<int> result(fix_size, 0);
int n = 0;
int factor = 1;
int j = 0;
for (int i = 0, len = line.length(); i < len; ++i) {
if (line[i] != ' ') {
n += factor * (line[i] - 48);
factor = 10;
if (i == len - 1) {
(n > 10) ? result[j] = (n % 10) * 10 + (n / 10) : result[j] = n;
}
}
else {
(n > 10) ? result[j] = (n % 10) * 10 + (n / 10) : result[j] = n;
// reset
factor = 1;
n = 0;
j++;
}
}
return result;
}
int find_max_triangle_sum(vector<vector<int> >& triangle) {
int size = triangle.size();
for (int i = 1; i < size; ++i) {
for (int j = 0; j <= i; ++j) {
if (j == 0)
triangle[i][j] += triangle[i - 1][j];
else
triangle[i][j] += max(triangle[i - 1][j], triangle[i - 1][j - 1]);
}
}
int last_row = size - 1;
int largest_sum = triangle[last_row][0];
for (int j = 1; j < size; ++j) {
if (triangle[last_row][j] > largest_sum)
largest_sum = triangle[last_row][j];
}
return largest_sum;
}
void inout_find_max_triangle_sum() {
int test_cases;
cin >> test_cases;
string line;
int size;
int temp;
while (test_cases--) {
cin >> size;
temp = size;
vector<vector<int> > triangle;
cin.ignore(80, '\n');
while (temp--) {
getline(cin, line);
trim_left(line);
trim_right(line);
triangle.push_back(triangle_tokenize(line, size));
}
cout << find_max_triangle_sum(triangle) << '\n';
}
}
int main() {
inout_find_max_triangle_sum();
return 0;
}