#include "soccer.h"

#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2100;


bool mp[maxn][maxn];
int l[maxn], r[maxn];

struct state{
    int l,r,x,y;
    int val;
};

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);
}

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){
    int n = N;
    // initialize dp[l][l][x][y]
    vector<state> s1, s2;
    int ret = 0;
    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){
                s1.push_back((state){i,i,l,j-1,j-l});
                ret = max(ret, j-l);
                l = -1;
              }
            }
          }
        if (l != -1){
          s1.push_back((state){i,i,l,n,n+1-l});
          ret = max(ret, n+1-l);
        }
    }
    for (int delta = 0;delta < n - 1;delta++){
        s2.clear();
        for (auto s : s1){
          int l = s.l;
          int r = s.r;
          int x = s.x;
          int y = s.y;
          // 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){
                          s2.push_back((state){l-1,r,i,j-1,s.val + (j-i)});
                          ret= max(ret, s.val + (j-i));
                          i = -1;
                      }
                  }
              }
              if (i != -1){
                s2.push_back((state){l-1,r,i,j-1,s.val + (j-i)});
                ret= max(ret, s.val+ (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){
                        s2.push_back((state){l,r+1,i,j-1,s.val + (j-i)});
                        ret = max(ret, s.val + (j-i));
                        i = -1;
                    }
                }
            }
            if (i != -1){
              s2.push_back((state){l,r+1,i,j-1,s.val + (j-i)});
              ret = max(ret, s.val + (j-i));
            }
          }
        }
        s1 = s2;
    }
    return ret;
}

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 <= 2000){
        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;
}