View Code of Problem 65

#include<bits/stdc++.h>
using namespace std;
int mp[1005][1005];
int dfs(int i, int j,int n) {
	if (i > n || j > n || i < 1 || j < 1)
		return 0;
	if (!mp[i][j])
		return 0;

	if (mp[i][j]) {
		int n1 = mp[i][j] + dfs(i + 1, j, n);	
		int n2 = mp[i][j] + dfs(i + 1, j+1, n);
		return max(n1, n2);
	}
}
int main() {
	int k;
	cin >> k;
	while (k--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				scanf("%d", &mp[i][j]);
			}
		}
		int ans = dfs(1, 1, n);
		cout << ans << endl;
	}
	return 0;
}