#include "soccer.h"
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

const int MAXN = 2e3 + 5;
const int INF = 1e9 + 7;

int ans = 0;
int grid[MAXN][MAXN];
int down[MAXN][MAXN];
int dp[MAXN][MAXN];
int prv[MAXN][MAXN], nxt[MAXN][MAXN];   //prv higher, prv lower
int len[MAXN][MAXN];

void magic(int row, int u, int l, int r) {
//    cout << "row, u, l, r: " << row << " " << u << " " << l << " " << r << endl;
    dp[row][u] = down[row][u] * (r - l + 1);
    len[row][u] = r - l + 1;

    if(prv[row][u] != -1) {
        magic(row, prv[row][u], l, u - 1);
        dp[row][u] = max(dp[row][u], dp[row][prv[row][u]] + (r - u + 1) * down[row][u]);
    }
    if(nxt[row][u] != -1) {
        magic(row, nxt[row][u], u + 1, r);
        dp[row][u] = max(dp[row][u], dp[row][nxt[row][u]] + (u - l + 1) * down[row][u]);
    }

    if(dp[row - 1][u] != -INF) dp[row][u] = max(dp[row][u], dp[row - 1][u] + (len[row][u] - len[row - 1][u]) * down[row][u]);

    ans = max(ans, dp[row][u]);
}

int biggest_stadium(int n, vector<vector<int>> f) {
    for(int i = 0; i <= n + 1; ++i) for(int j = 0; j <= n + 1; ++j) grid[i][j] = 0;
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) grid[i][j] = f[i - 1][j - 1];
    }

    for(int i = n; i >= 1; --i) {
        for(int j = 1; j <= n; ++j) {
            if(grid[i][j]) down[i][j] = 0;
            else down[i][j] = down[i + 1][j] + 1;
        }
    }

    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= n; ++j) {
            dp[i][j] = -INF;
            prv[i][j] = nxt[i][j] = -1;
        }
    }

    for(int i = 1; i <= n; ++i) {
        int l = 1, r = 0;
        while(l <= n) {
            r = l;

            if(grid[i][l] == 1) {
                while(r <= n && grid[i][r]) ++r;
                l = r;
//                cout << "skipped to " << l << endl;
                continue;
            }

            while(r < n && grid[i][r + 1] == 0) ++r;

            stack<int> st;

            for(int j = l; j <= r; ++j) {
                while(st.size() && down[i][st.top()] > down[i][j]) {
                    prv[i][j] = st.top();
                    st.pop();
                }
                if(st.size()) nxt[i][st.top()] = j;
                st.push(j);
            }

            while(st.size() > 1) st.pop();

            magic(i, st.top(), l, r);

            l = r + 1;
        }

    }

    return ans;
}