#include "soccer.h"

#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2100;

int global_ans = 0;

bool mp[maxn][maxn];
int l[maxn], r[maxn];
int dp[2][512][512][512];

bool is_contained(int l1,int r1,int l2,int r2){
    return l2 <= l1 & l1 <= r1 & r1 <= r2;
}

bool is_strictly_contained(int l1,int r1,int l2,int r2){
    return l2 <= l1 & l1 <= r1 & r1 <= r2 && (l1 != l2 || r1 != r2);
}

inline void update(int & x,int u){
    x = max(x, u);
    global_ans = max(global_ans, u);
}

int biggest_stadium_task1(int N){
    int one_x = -1;
    int one_y = -1;
    int n = N;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            if (mp[i][j] == 1){
                one_x = i;
                one_y = j;
                break;
            }
        }
    }
    return n * n - min(one_x, n+1-one_x) * min(one_y,n+1-one_y);
}

int biggest_stadium_task2(int N){
    memset(dp,-1,sizeof dp);
    global_ans = 0;
    int n = N;
    // initialize dp[l][l][x][y]
    for (int i = 1;i <= n;i++){
        int l = -1;
          for (int j = 1;j <= n;j++){
            if (mp[i][j] == 0){
              if (l == -1) l = j;
            }
            else{
              if (l != -1){
                dp[0][i][l][j-1] = j - l;
                l = -1;
              }
            }
          }
        if (l != -1){
          dp[0][i][l][n] = n + 1 - l;
        }
    }
    for (int delta = 0;delta < n - 1;delta++){
        // reset
        memset(dp[1 ^ (delta & 1)], -1, sizeof dp[1 ^ (delta & 1)]);
        for (int l = 1;l <= n;l++){
            int r = l + delta;
            for (int x = 1;x <= n;x++){
                for (int y = x;y <= n;y++){
                    if (dp[delta & 1][l][x][y] == -1) continue;
                    // Growing up?
                    if (l != 1){
                        int i = -1;
                        int j = x;
                        for (;j <= y;j++){
                            if (mp[l-1][j] == 0){
                                if (i == -1) i = j;
                            }
                            else{
                                if (i != -1){
                                    update(dp[1 ^ (delta & 1)][l-1][i][j-1], dp[delta & 1][l][x][y] + (j-i));
                                    i = -1;
                                }
                            }
                        }
                        if (i != -1){
                            update(dp[1 ^ (delta & 1)][l-1][i][j-1], dp[delta & 1][l][x][y] + (j-i));
                        }
                    }
                    // growing down
                    if (r != n){
                      int i = -1;
                      int j = x;
                      for (;j <= y;j++){
                          if (mp[r+1][j] == 0){
                              if (i == -1) i = j;
                          }
                          else{
                              if (i != -1){
                                  update(dp[1 ^ (delta & 1)][l][i][j-1], dp[delta & 1][l][x][y] + (j-i));
                                  i = -1;
                              }
                          }
                      }
                      if (i != -1){
                        update(dp[1 ^ (delta & 1)][l][i][j-1], dp[delta & 1][l][x][y] + (j-i));
                      }
                    }
                }
            }
        }
    }
    return global_ans;
}

int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    int n = N;
    int ones = 0;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            mp[i][j] = F[i-1][j-1];
            ones += mp[i][j];
        }
        mp[i][0] = 1;
        mp[i][n+1] = 1;
    }

    if (ones == 1){
        return biggest_stadium_task1(N);
    }
    if (n <= 500){
        return biggest_stadium_task2(N);
    }

    for (int i = 1;i <= n;i++){
        l[i] = -1;
        r[i] = -1;
        for (int j = 1;j <= n;j++){
            if (mp[i][j] == 0){
              if (l[i] == -1) l[i] = j;
              if (r[i] != -1) return -1;
            }
            else{
              if (l[i] != -1 && r[i] == -1) r[i] = j - 1;
            }
        }
        if (r[i] == -1 && l[i] != -1) r[i] = n;
    }
    l[n+1] = r[n+1] = -1;
    int lower = -1, upper = -1;
    for (int i = 1;i <= n;i++){
        if (l[i] != -1){
            if (lower == -1) lower = i;
            if (upper != -1) return -1;
        }
        else{
            if (lower != -1 && upper == -1) upper = i - 1;
        }
    }
    if (lower != -1 && upper == -1) upper = n;
    bool is_decreasing = false;
    for (int i = lower;i < upper;i++){
        if (is_contained(l[i], r[i], l[i+1], r[i+1])){
            if (is_decreasing && is_strictly_contained(l[i], r[i], l[i+1], r[i+1])) return -1;
        }
        else if (is_strictly_contained(l[i+1], r[i+1], l[i], r[i])){
            if (!is_decreasing) is_decreasing = true;
        }
        else{
            return -1;
        }
    }
    for (int i = lower;i <= upper;i++){
        for (int j = i + 1;j <= upper;j++){
            if (!is_contained(l[i] ,r[i], l[j], r[j]) && !is_contained(l[j], r[j], l[i], r[i])) return -1;
        }
    }
    int tot = 0;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            if (mp[i][j] == 0) tot++;
        }
    }
    return tot;
}