View Code of Problem 65

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<climits>

using namespace std;


int main()
{
	int T;
	cin >> T;

	while(T > 0) {

		int R;
		cin >> R;

		vector<vector<int>> nums(R, vector<int>(R, INT_MIN));

		for (int i = 0; i < R; i++) {

			for (int j = 0; j <= i; j++)
				cin >> nums[i][j];
		}

		vector<vector<int>> dp(R, vector<int>(R, INT_MIN));
		dp[0][0] = nums[0][0];

		for (int i = 1; i < R; i++) {

			for (int j = 0; j <= i; j++) {

				if (j != 0 && j != i)
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + nums[i][j];

				if(j == 0)
					dp[i][j] = dp[i - 1][j] + nums[i][j];

				if(j == i)
					dp[i][j] = dp[i - 1][j - 1] + nums[i][j];
			}
		}

		int res = INT_MIN;
		for (int i = 0; i < R; i++)
			res = max(res, dp[R - 1][i]);

		cout << res << endl;

		T--;
	}
}