救民于水火

#include <bits/stdc++.h>
using namespace std;
const long long maxn = 2e2 + 10;
int n;
int ans;
int dp[maxn][maxn], a[maxn][maxn], tmp[maxn][maxn];
void check(int x) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
        }
    }
    ans = max(ans, x + dp[n][n]);
}
void dfs(int x, int y, int cnt) {
    if (x > n || y > n)
        return;
    a[x][y] = 0;
    if (x == n && y == n) {
        check(cnt);
        a[x][y] = tmp[x][y];
        return;
    }
    dfs(x + 1, y, cnt + a[x + 1][y]);
    dfs(x, y + 1, cnt + a[x][y + 1]);
    a[x][y] = tmp[x][y];
}
int main() {
    cin >> n;
    int x, y, t;
    while (cin >> x >> y >> t && x != 0 && y != 0 && t != 0) {
        a[x][y] = t;
        tmp[x][y] = t;
    }
    dfs(1, 1, a[1][1]);
    cout << ans;
    return 0;
}