Untitled

 avatar
unknown
plain_text
4 years ago
732 B
8
Indexable
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
const int N = 105;
long long dp[N][N];
int a[N][N];
int max(int a, int b) {
	return a > b ? a : b;
}
long long solve(int i, int j) {
	if (i < 0 || j < 0)
		return 0;
	if (i == 0 && j == 0)
		return a[i][j];
	if (j > i)
		return 0;
	if (dp[i][j] != -1)
		return dp[i][j];
	return dp[i][j] = max(solve(i - 1, j - 1), solve(i - 1, j)) + a[i][j];
}
signed main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j <= i; ++j)
			scanf("%d", &a[i][j]);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			dp[i][j] = -1;
	int ans = 0;
	for (int i = 0; i < n; ++i)
		ans = max(ans, solve(n - 1, i));
	printf("%d", ans);
}
Editor is loading...