#include "soccer.h"

#include <unordered_map>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int maxn = 2100;

bool mp[maxn][maxn];
int l[maxn], r[maxn];
int global_ans = 0;

ll state_id(ll l,ll r,ll x,ll y){
    return l + (r + (x + y * maxn) * maxn) * maxn;
}


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

unordered_map<ll, int> f, g;

void update(int l,int r,int i,int j,int v){
    ll s = state_id(l,r,i,j);
    if (g.find(s) == g.end()){
      g[s] = v;
    }
    else{
      g[s] = max(v, g[s]);
    }
    global_ans = max(global_ans, v);
}

int biggest_stadium_task2(int N){
    int n = N;
    global_ans = 0;
    // 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){
                f[state_id(i,i,l,j-1)] = j - l;
                global_ans = max(global_ans, j-l);
                l = -1;
              }
            }
          }
        if (l != -1){
          f[state_id(i,i,l,n)] = n+1-l;
          global_ans = max(global_ans, n+1-l);
        }
    }
    for (int delta = 0;delta < n - 1;delta++){
        g.clear();
        for (auto s : f){
          int l = s.first % maxn;
          int r = s.first / maxn % maxn;
          int x = s.first / maxn / maxn % maxn;
          int y = s.first / maxn / maxn / maxn % maxn;
          // 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(l-1,r,i,j-1,s.second + (j-i));
                          i = -1;
                      }
                  }
              }
              if (i != -1){
                  update(l-1,r,i,j-1,s.second + (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(l,r+1,i,j-1,s.second + (j-i));

                        i = -1;
                    }
                }
            }
            if (i != -1){
              update(l,r+1,i,j-1,s.second + (j-i));
            }
          }
        }
        f = g;
    }
    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 <= 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;
}