#ifdef ONLINE_JUDGE
#include "soccer.h"
#endif
#pragma once
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
int dp[2005][2005];
short pos[2005][2005], L[2005][2005], R[2005][2005];
int biggest_stadium(int n, std::vector<std::vector<int>> aa) {
    int ans = 0;
    vector<vector<pair<int, int>>>tong(n + 1, vector<pair<int, int>>());

    for (int j = 1; j <= n; j++)
        for (int i = 1; i <= n; i++) {
            dp[i][j] = 0;

            if (aa[i - 1][j - 1])
                pos[i][j] = i;
            else
                pos[i][j] = pos[i - 1][j];

            tong[i - pos[i][j]].push_back(make_pair(i, j));
        }

    for (int i = 1; i <= n; i++) {
        L[i][0] = 0;

        for (int j = 1; j <= n; j++)
            if (aa[i - 1][j - 2])
                L[i][j] = j - 1;
            else
                L[i][j] = L[i][j - 1];

        R[i][n + 1] = n + 1;

        for (int j = n; j; j--)
            if (aa[i - 1][j])
                R[i][j] = j + 1;
            else
                R[i][j] = R[i][j + 1];
    }

    for (int d = 1; d <= n; ++d) {
        for (auto [i, j] : tong[d]) {
            if (pos[i][j] ^ i - 1)
                R[i][j] = min(R[i][j], R[i - 1][j]), L[i][j] = max(L[i][j], L[i - 1][j]);

            dp[i][j] = dp[i - 1][j] + R[i][j] - L[i][j] - 1;

            if (L[i][j] > 0) {
                int len = pos[i][L[i][j]] - pos[i][j];
                dp[i][j] = max(dp[i][j], dp[i][L[i][j]] + len * (R[i][j] - L[i][j] - 1));
            }

            if (R[i][j] <= n) {
                int len = pos[i][R[i][j]] - pos[i][j];
                dp[i][j] = max(dp[i][j], dp[i][R[i][j]] + len * (R[i][j] - L[i][j] - 1));
            }

            ans = max(ans, dp[i][j]);
        }
    }

    return ans;
}