The Triangle

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; cin >> n;
    10    vector<vector<int>> v(n);
    11    for (int i = 1; i <= n; i++) {
    12        for (int j = 0; j < i; j++) {
    13            int x; cin >> x;
    14            v[i - 1].push_back(x);
    15        }
    16    }
    17    vector<vector<int>> dp(n);
    18    for (int i = 0; i < n; i++) {
    19        dp[i].assign(i + 1, 0);
    20    }
    21    dp[0][0] = v[0][0];
    22    for (int i = 1; i < n; i++) {
    23        for (int j = 0; j <= i; j++) {
    24            if (j < i) {
    25                dp[i][j] = max(dp[i][j], dp[i - 1][j] + v[i][j]);
    26            }
    27            if (j > 0) {
    28                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + v[i][j]);
    29            }
    30        }
    31    }
    32    int ans = 0;
    33    for (int i = 0; i < n; i++) {
    34        ans = max(ans, dp[n - 1][i]);
    35    }
    36    cout << ans << '\n';
    37    return 0;
    38}