#include "soccer.h"

#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 2100;

bool mp[maxn][maxn];
int l[maxn], r[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);
}

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

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