Untitled
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...