View Code of Problem 65

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main (){
	int t, n;
	scanf("%d", &t);
	while(t--){
		scanf("%d", &n);
		int a[1010][1010], dp[1010][1010];
		for(int i = 0;i < n;i++){
			for(int j = 0;j <= i;j++){
				scanf("%d", &a[i][j]);
			}
		}
		for(int j = 0;j < n;j++){
			dp[n-1][j] = a[n-1][j];
		}
		for(int i = n-2;i >= 0;i--){
			for(int j = 0;j <= i;j++){
				dp[i][j] = max(dp[i+1][j], dp[i+1][j+1])+a[i][j];
			}
		}
		printf("%d\n", dp[0][0]);
	}

	return 0;
}